Анатомия распределителя памяти slab в Linux

Узнайте, как Linux управляет памятью

Хорошая производительность операционной системы зависит от способности системы эффективно управлять ресурсами. Раньше было нормой использование распределителей памяти типа heap, но производительность страдала вследствие фрагментации и необходимости перераспределения памяти. В наше время ядро Linux® использует появившийся в системе Solaris, но использовавшийся во встроенных системах в течение достаточно долгого времени метод распределения памяти как объектов, исходя из их размера. Эта статья описавает идеи, лежащие в основе механизма slab allocator (распределитель slab), и исследует его интерфейсы и приемы использования.

М. Тим Джонс, инженер-консультант, Emulex

M. Tim JonesM. Тим Джонс (M. Tim Jones) является архитектором встраиваимого программного обеспечения и автором работ: Программирование Приложений под GNU/Linux, Программирование AI-приложений и Использование BSD-сокетов в различных языках программирования. Он имеет опыт разработки процессоров для геостационарных космических летательных аппаратов, а также разработки архитектуры встраиваемых систем и сетевых протоколов. Сейчас Тим работает инженером-консультантом в корпорации Эмулекс (Emulex Corp.) в г.Лонгмонт, Колорадо.



22.08.2007

Динамическое управление памятью

Цель управления памятью состоит в предоставлении метода, при помощи которого память может динамически распределяться между различными пользователями и различными целями. Метод управления памятью должен делать следующее:

  • Минимизировать время, необходимое на управление памятью
  • Максимально увеличить доступную память для общего использования (минимизировать ее непроизводительные расходы на управление)

Управление памятью -- в конечном счете игра с нулевым исходом в ходе поиска компромисса. Вы можете разработать алгоритм, управление которым не требует большого количества памяти, но он отнимет много времени на управление доступной памятью. Вы также можете разработать алгоритм, который эффективно управляет памятью, но использует несколько больше памяти. И наконец, требования для конкретного приложения приводят к разумному компромиссу.

Раньше менеджеры памяти использовали стратегию распределения, базирующуюся на heap (пространство для динамического выделения памяти). В этом методе большой блок памяти (называемый heap ) используется для обеспечения памятью пользовательских целей. Когда пользователям требуется блок памяти, они запрашивают кусок памяти требуемого размера. Менеджер heap проверяет доступную память (используя специальный алгоритм) и возвращает блок. Отдельные алгоритмы используют при этом поиске first-fit (первый встречающийся в heap блок, который соответствует запросу) и best-fit (блок в heap, наиболее соответствующий запросу). Когда пользователи заканчивают использовать память, они возвращают ее в heap.

Основная проблема стратегии распределения, базирующейся на heap, -- фрагментация. Выделяемые блоки памяти возвращаются в различном порядке и в разное время. Это приводит к тому, что в heap образуются дыры, требующие большого времени для эффективного управления свободной памятью. Этот алгоритм стремится использовать память эффективнее (выделяя необходимую), но требует много времени для обслуживания heap.

Другой подход, называемый buddy memory allocation, -- более быстрый метод, который делит память на разделы с размером, кратным степени 2, и пытается распределить запросы памяти, используя подход best-fit. Когда пользователь освобождает память, проверяется блок buddy, чтобы увидеть все смежные свободные соседние блоки. Эти блоки, если они есть, объединяются для минимизации фрагментирования. Этот алгоритм несколько более эффективен по временным характеристикам, но вследствие использования подхода best-fit может непроизводительно расходовать память.

Эта статья сфокусирована на описании механизмов, предоставляемых ядром Linux для управления памятью и, в частности, на механизмах, предоставляемых slab allocation.

Кэш slab

Распределитель памяти slab, используемый в Linux, базируется на алгоритме, впервые введенном Джефом Бонвиком (Jeff Bonwick) для операционной системы SunOS. Распределитель Джефа строится вокруг объекта кэширования. Внутри ядра значительное количество памяти выделяется на ограниченный набор объектов, например, дескрипторы файлов и другие общие структурные элементы. Джеф основывался на том, что количество времени, необходимое для инициализации регулярного объекта в ядре, превышает количество времени, необходимое для его выделения и освобождения. Его идея состояла в том, что вместо того, чтобы возвращать освободившуюся память в общий фонд, оставлять эту память в проинициализированном состоянии для использования в тех же целях. Например, если память выделена для mutex, функцию инициализации mutex (mutex_init) необходимо выполнить только один раз, когда память впервые выделяется для mutex. Последующие распределения памяти не требуют выполнения инициализации, поскольку она уже имеет нужный статус от предыдущего освобождения и обращения к деконструктору.

В Linux распределитель slab использует эти и другие идеи для создания распределителя памяти, который будет эффективно использовать и пространство, и время.

Рисунок 1 иллюстрирует верхний уровень организации структурных элементов slab. На самом высоком уровне находится cache_chain, который является связанным списком кэшей slab. Это полезно для алгоритмов best-fit, которые ищут кэш, наиболее соответствующий размеру нужного распределения (осуществляя итерацию по списку). Каждый элемент cache_chain -- это ссылка на структуру (называемая cache (кэш)). Это определяет совокупность объектов заданного размера, которые могут использоваться.

Рисунок 1. Главные структуры распределителя slab
Рисунок 1. Главные структуры распределителя slab

Каждый кэш содержит список slab'ов, которые являются смежными блоками памяти (обычно страницы). Существует три slab:

slabs_full
Slab'ы, которые распределены полностью.
slabs_partial
Slab'ы, которые распределены частично.
slabs_empty
Slab'ы, которые являются пустыми или не выделены под объекты.

Обратите внимание, что slab'ы в списке slabs_empty -- основные кандидаты на reaping. Это процесс, при помощи которого память, используемая slab'ами, обеспечивает возврат в операционную систему для дальнейшего использования.

В списке slab'ов все slab'ы -- смежные блоки памяти (одна или более смежных страниц), которые разделяются между объектами. Эти объекты -- основные элементы, которые выделяются из специального кэша и возвращаются в него. Обратите внимание, что slab -- минимальное распределение распределителя slab, поэтому если необходимо увеличить его, это минимум, на который он может увеличиться. Обычно через slab происходит распределение множества объектов.

Поскольку объекты распределяются и освобождаются из slab, отдельные slab могут перемещаться между списками slab'ов. Например, когда все объекты в slab израсходованы, они перемещаются из списка slabs_partial в список slabs_full. Когда slab полон и объект освобождается, он перемещается из списка slabs_full в список slabs_partial. Когда освобождаются все объекты, они перемещаются из списка slabs_partial в список slabs_empty.

Мотивация к использованию slab

Распределитель кэша slab имеет некоторые преимущества по сравнению с традиционной схемой управления памятью. Во-первых, ядра обычно полагаются на выделение маленьких объектов, которые распределяются множество раз в течение работы системы. Это обеспечивается распределителем кэша slab через кэширование объектов сходных размеров, таким образом избегая часто встречающихся проблем фрагментации. Распределитель slab также поддерживает фрагментацию общих объектов, таким образом избегая необходимости повторно инициализировать объекты для той же цели. Наконец, распределитель slab поддерживает выравнивание аппаратного кэша и coloring, который позволяет объектам с различными кэшами занимать те же самые строки кэша для увеличения использования кэша и лучшей производительности.


Функции API

Рассмотрим API (application program interface -- прикладной программный интерфейс) для создания новых кэшей slab, добавления памяти в кэш, удаления кэша, а также функции для выделения и освобождения объектов из них.

Первый этап -- создание вашей структуры кэша slab, которую вы можете создать статически как:

struct struct kmem_cache *my_cachep;

Эта ссылка затем используется другими функциями кэша slab для создания, удаления, распределения и т.д. Структура kmem_cache содержит данные, относящиеся к конкретным CPU-модулям, набор настроек (доступных через файловую систему proc), статистических данных и элементов, необходимых для управления кэшем slab.

kmem_cache_create

Функция ядра kmem_cache_create используется для создания нового кэша. Обычно это происходит во время инициализации ядра или при первой загрузке модуля ядра. Его прототип определен как:

struct kmem_cache *
kmem_cache_create( const char *name, size_t size, size_t align,
                       unsigned long flags;
                       void (*ctor)(void*, struct kmem_cache *, unsigned long),
                       void (*dtor)(void*, struct kmem_cache *, unsigned long));

Аргумент name определяет имя кэша, которое используется файловой системой proc (в /proc/slabinfo) для идентификации этого кэша. Аргумент size определяет размер объектов, которые должны быть созданы для этого кэша, с аргументом align, определяющим необходимое выравнивание для каждого объекта. Аргумент flags определяет опции, разрешенные для кэша. Эти флаги показаны в Таблице 1.

Таблица 1. Неполный список опций для kmem_cache_create (как определено флагами)
ОпцияОписание
SLAB_RED_ZONEВставить маркеры в начало и конец объекта для поддержки проверки переполнения буфера.
SLAB_POISONЗаполнить slab известным образцом, чтобы обеспечить мониторинг объектов в кэше (объекты, принадлежащие кэшу, но измененные извне).
SLAB_HWCACHE_ALIGNУстановить, что объекты в этом кэше должны быть выравнены согласно аппаратным строкам кэша.

Аргументы ctor и dtor определяют необязательные объекты конструктор и деконструктор. Конструктор и деконструктор -- callback-функции, предусмотренные пользователем. Когда новый объект выделяется из кэша, он может быть инициализирован через конструктор.

После того как кэш создан, ссылка на него возвращается функцией kmem_cache_create. Обратите внимание, что эта функция не выделяет память кешу. Вместо этого при попытке выделить объекты из кэша (изначально он пуст) ему выделяется память при помощи команды refill. Это та же команда, которая используется для добавления кэшу памяти, когда все его объекты израсходованы.

kmem_cache_destroy

Функция ядра kmem_cache_destroy используется для удаления кэша. Этот запрос выполняется модулями ядра, когда они выгружаются. Перед вызовом этой функции кэш должен быть пуст.

void kmem_cache_destroy( struct kmem_cache *cachep );

kmem_cache_alloc

Для выделения объектов из поименованного кэша используется функция kmem_cache_alloc. Вызывающий код передает кэш, из которого выделяется объект, и набор флагов:

void kmem_cache_alloc( struct kmem_cache *cachep, gfp_t flags );

Эта функция возвращает объект из кэша. Обратите внимание, что если кэш в настоящее время пуст, эта функция может вызвать cache_alloc_refill, чтобы добавить в кэш памяти. Варианты флага для kmem_cache_alloc такие же, как и для kmalloc. В Таблице 2 представлен неполный список вариантов флагов.

Таблица 2. Варианты флагов для функций ядра kmem_cache_alloc и kmalloc
ФлагОписание
GFP_USERВыделить память для пользователя User (этот запрос может войти в состояние sleep).
GFP_KERNELВыделить память из RAM ядра (этот запрос может войти в состояние sleep).
GFP_ATOMICПринудительный запрет на sleep при этом вызове (полезно для программ обработки прерываний).
GFP_HIGHUSERВыделить из high memory.

kmem_cache_zalloc

Функция ядра kmem_cache_zalloc похожа на kmem_cache_alloc, за исключением того, что она выполняет memset объекта для его очистки перед возвращением объекта.

kmem_cache_free

Для освобождения объекта для дальнейшего использования slab используется kmem_cache_free. При вызове передается ссылка на кэш и на объект, который должен быть освобожден.

void kmem_cache_free( struct kmem_cache *cachep, void *objp );

kmalloc and kfree

Наиболее распространенные функции управления памятью в ядре -- kmalloc и kfree. Прототипы этих функций определены как:

void *kmalloc( size_t size, int flags );
void kfree( const void *objp );

Обратите внимание, что в kmalloc необходимые для распределения аргументы -- только размер объектов и набор флагов (см. неполный список в Таблице 2). Но kmalloc и kfree используют кэш slab точно так же, как определенные ранее функции. Вместо того чтобы вызывать определенный кэш slab, из которого выделяется объект, функция kmalloc повторяет через доступные кэши поиск того, который соответствует запрошенному размеру. Когда он найден, объект выделяется (при помощи __kmem_cache_alloc). Чтобы освободить объект при помощи kfree, кэш, из которого был выделен объект, определяется вызовом virt_to_cache. Эта функция возвращает ссылку на кэш, которая затем используется в запросе к __cache_free для освобождения объекта.

Прочие функции

Кэш slab API предоставляет ряд других полезных функций. Функция kmem_cache_size возвращает размер объектов, которыми управляет кэш. Вы также можете восстановить имя данного кэша (как определено во время создания кэша) через запрос к kmem_cache_name. Кэш может быть сокращен путем освобождения свободных slab'ов в кэше. Этого можно достигнуть при помощи вызова kmem_cache_shrink. Обратите внимание, что это действие (называемое reaping) автоматически периодически выполняется ядром (через kswapd).

unsigned int kmem_cache_size( struct kmem_cache *cachep );
const char *kmem_cache_name( struct kmem_cache *cachep );
int kmem_cache_shrink( struct kmem_cache *cachep );

Пример использования кэша slab

Следующий отрывок кода демонстрирует процесс создания нового кэша slab, выделения и освобождения объектов из кэша и затем удаления кэша. Для начала объект kmem_cache должен быть определен и проинициализирован (см. Листинг 1). Этот конкретный кэш содержит объекты размером 32 байта и выравнен согласно требованиям аппаратного кэша (как определено аргументом flags SLAB_HWCACHE_ALIGN).

Листинг 1. Создание нового кэша slab
static struct kmem_cache *my_cachep;

static void init_my_cache( void )
{

   my_cachep = kmem_cache_create( 
                  "my_cache",            /* Name */
                  32,                    /* Object Size */
                  0,                     /* Alignment */
                  SLAB_HWCACHE_ALIGN,    /* Flags */
                  NULL, NULL );          /* Constructor/Deconstructor */

   return;
}

Выделив кэш slab, вы можете выделить их его объект. В Листинге 2 представлен пример выделения и освобождения объекта из кэша. Здесь также показаны две другие функции.

Листинг 2. Выделение и освобождение объектов
int slab_test( void )
{
  void *object;

  printk( "Cache name is %s\n", kmem_cache_name( my_cachep ) );
  printk( "Cache object size is %d\n", kmem_cache_size( my_cachep ) );

  object = kmem_cache_alloc( my_cachep, GFP_KERNEL );

  if (object) {

    kmem_cache_free( my_cachep, object );

  }

  return 0;
}

Наконец, Листинг 3 -- пример удаления кэша slab. При вызове необходимо гарантировать, что никакие попытки выделения объектов из кэша не будут выполняться в процессе удаления.

Листинг 3. Удаление кэша slab
static void remove_my_cache( void )
{

  if (my_cachep) kmem_cache_destroy( my_cachep );

  return;
}

Интерфейс proc для slab

Система proc предоставляет простой метод контроля за всеми кэшами slab, активными в системе. Этот файл, называемый /proc/slabinfo, помимо предоставления некоторых настроек, которые доступны из пользовательского пространства, предоставляет подробную информацию обо всех кэшах slab. Текущая версия slabinfo предоставляет header, чтобы сделать вывод более удобным для чтения. Для каждого кэша slab в системе предусмотрено количество объектов, количество активных объектов и размер объекта (в дополнение объектам и страницам, выделенным через slab). Также предусматривается ряд настроек и данные slab.

Для настройки конкретного кэша slab просто вызовите команду echo с указанием имени кэша и трех настраиваемых параметров в формате строк из файла /proc/slabinfo. Следующий пример иллюстрирует, как увеличить limit и batchcount, оставляя shared factor таким, каким он был (формат следующий "cache name limit batchcount shared factor"):

# echo "my_cache 128 64 8" > /proc/slabinfo

Поле limit показывает максимальное количество объектов, которые будут помещены в кэш для каждого CPU. Поле batchcount -- максимальное количество глобальных объектов кэша, которые будут переданы кэш процессора при освобождении. Параметр shared показывает характер разделения для систем Symmetric MultiProcessing (SMP).

Обратите снимание, что для настройки параметров в файловой системе proc для кэша slab вы должны иметь привилегии суперпользователя.


Распределитель SLOB

Для небольших встроенных систем существует подсистема, эмулирующая slab, называемая SLOB. Эта замена slab полезна в небольших встроенных системах Linux, но, несмотря на то, что она сохраняет до 512KB памяти, она страдает от фрагментации и низкого уровня масштабирования. Если CONFIG_SLAB отключен, ядро возвращается к распределителю SLOB. Более подробную информацию см. ниже а разделе Ресурсы.


Идем дальше

Исходный код для распределителя кэша slab действительно один из наиболее читабельных фрагментов ядра Linux. За исключением косвенных ссылок, которые присутствуют в вызовах функций, исходник интуитивно понятен и обычно снабжен хорошими комментариями. Если вы хотели бы знать больше о распределителе кэша slab, я предлагаю начать с наиболее современной документации для этого механизма. Раздел Ресурсы предлагает несколько источников, которые описывают распределитель кэша slab, но, к сожалению, все они являются устаревшими для текущей реализации версии 2.6.

Ресурсы

Научиться

Получить продукты и технологии

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=249918
ArticleTitle=Анатомия распределителя памяти slab в Linux
publish-date=08222007