Главная » Ядро Linux » Уровень слябового распределителя памяти

0

Выделение и освобождение структур  данных — это одна  из наиболее частых  операций, которые выполняются в любом  ядре.  Для  того  чтобы  облегчить  процедуру частого выделения и освобождения данных  при программировании,  вводятся списки свободных ресурсов (free list). Список свободных ресурсов  содержит некоторый набор уже выделенных структур  данных.  Когда  коду необходим новый  экземпляр структуры данных, он  может  взять  одну  структуру  из  списка свободных ресурсов, вместо того  чтобы  выделять  необходимый объем  памяти и заполнять его данными соответствующей структуры.  Позже, когда  структура  данных  больше  не нужна, она снова возвращается в список свободных ресурсов, вместо  того чтобы  освобождать память. В этом смысле  список свободных ресурсов  представляет собой  кэш  объектов, в котором хранятся объекты  одного  определенного, часто  используемого типа.

Одна  из наибольших проблем, связанных со списком свободных ресурсов  в ядре, это то, что над ними  нет никакого централизованного контроля. Когда  ощущается недостаток свободной памяти, нет  никакой возможности взаимодействовать между ядром  и всеми  списками свободных ресурсов, которые в такой  ситуации должны уменьшить размер  своего  кэша, чтобы  освободить память.  В ядре  нет никакой информации о случайно созданных списках свободных ресурсов.  Для  исправления положения и для универсальности кода  ядро  предоставляет уровень  слябового распределения памяти (slab layer), который также  называется просто  слябовым распределителем памяти (slab allocator). Уровень  слябового распределения памяти выполняет функции общего  уровня  кэширования структур данных.

Концепции слябового распределения памяти впервые были  реализованы в операционной системе  SunOS 5.4 фирмы Sun  Microsystems’. Для уровня  кэширования структур  данных  в операционной системе  Linux  используется такое  же название и похожие  особенности реализации.

Уровень  слябового распределения памяти служит для достижения следующих  целей.

• Часто  используемые структуры  данных, скорее  всего, будут часто  выделяться и освобождаться, поэтому  их следует кэшировать.

• Частые  операции выделения и освобождения памяти могут привести к фрагментации памяти (к невозможности найти  большие участки  физически однородной  памяти). Для предотвращения этого, кэшированные списки свободных ресурсов  организованы непрерывным образом в физической памяти. Так как структуры  данных  возвращаются снова  в список свободных  ресурсов, то в результате никакой фрагментации не возникает.

• Список  свободных ресурсов  обеспечивает улучшенную  производительность при  частых  выделениях и освобождениях объектов, так  как  освобожденные объекты  сразу же готовы  для нового  выделения.

• Если  распределитель памяти может  использовать дополнительную  информацию, такую  как  размер  объекта, размер  страницы памяти и общий  размер  кэша, то появляется возможность принимать в критических ситуациях более интеллектуальные решения.

5   И  позже  документированы в работе  Bonwirk J."The  Slab Allocator:  An Object-Caching Kernel  Memory

Allocator,"  USENIX,  1994.

у

• Если  кэш  организован, как связанный с определенным процессором (т.е. для каждого  процессора в системе  используется свой уникальный отдельный кэш), то выделение и освобождение структур  данных  может  выполняться без использования SMP-блокиропок.

• Если  распределитель памяти рассчитан на доступ  к неоднородной  памяти (Non-Uniform Memory  Access NUMA), то появляется возможность выделения памяти с того же узла (node), на котором эта память  запрашивается.

• Хранимые объекты  могут быть  "окрашены’,  чтобы  предотвратить отображение разных  объектов на одни  и те же строки  системного кэша.

Уровень  слябового распределения памяти в ОС  Linux  был реализован с учетом

указанных  принципов.

Устройство слябового распределителя памяти

Уровень  слябового распределения памяти делит  объекты  па группы, которые называются кэшами (cache). Разные кэши  используются для хранения объектов различных типов.  Для каждого  типа объектов существует  свой уникальный кэш.  Например, один  кэш  используется для  дескрипторов процессов  (список свободных структур struc t   task_struct) , а другой— для  индексов файловых систем  (struc t  inode). Интересно, что интерфейс krnalloc  ()  построен на базе уровня  слябового распределения  памяти и использует семейство кэшей общего  назначения.

Далее  кэши  делятся  на слябы (буквально slab — однородная плитка, отсюда  и название  всей подсистемы). Слябы  занимают одну или несколько физически смежных страниц памяти. Обычно сляб занимает только  одну страницу памяти. Каждый кэш может  содержать несколько слябов.

Каждый сляб содержит некоторое количество объектов, которые представляют собой кэшируемые структуры  данных.  Каждый сляб  может быть в одном  из трех состояний:  полный (full), частично заполненный (partial)  и пустой  (empty). Полный сляб не содержит свободных объектов (все объекты  сляба  выделены для  использования). Частично заполненный сляб  содержит часть  выделенных и часть  свободных объектов.  Когда  некоторая часть ядра  запрашивает новый  объект, то этот  запрос  удовлетворяется из частично заполненного сляба, если такой  существует.  В противном случае  запрос  выполняется из пустого  сляба.  Если  пустого  сляба  не  существует, то он создается. Очевидно, что полный сляб  никогда не может удовлетворить запрос, поскольку в нем нет свободных объектов. Такая  политика уменьшает фрагментацию памяти.

В качестве  примера рассмотрим структуры  inode, которые являются представлением  в оперативной памяти индексов дисковых файлов (см. главу 12). Эти структуры часто  создаются и удаляются, поэтому  есть смысл  управлять  ими  с помощью слябового  распределителя памяти. Структуры struc t  inode  выделяются из кэша  inode_ cachep  (такое  соглашение по присваиванию названий является стандартом). Этот кэш  состоит  из одного  или более слябов, скорее  всего слябов  много, поскольку много объектов. Каждый сляб  содержит максимально возможное количество объектов типа  struc t   inode.  Когда  ядро  выделяет  новую  структуру типа  struc t  inode, возвращается указатель  на  уже выделенную, но  не используемую структуру из частично заполненного сляба или, если такого  нет, из пустого  сляба.  Когда ядру больше  не нужен  объект  типа  inode, то слябовый распределитель памяти помечает  этот  объект

как  свободный. На  рис.  11.1  показана диаграмма взаимоотношений  между  кэшами, слябами и  объектами.

Объект

Сляб

Объект

Объект

Кэш

Объект

Сляб

Объект

Рис. 11.1. Взаимоотношения между кэшами,  слябами и объектами

Каждый кэш   представляется  структурой kmem_cache_s.  Эта  структура содержит три  списка slab_full ,  slab_partia l  и   slab_empty ,  которые хранятся в  структуре kmem_list3 .  Эти  списки содержат все  слябы, связанные с данным кэшем. Каждый сляб  представлен  следующей структурой  struc t   slab , которая является дескриптором  сляба.

struct slab {

struct list head list; /* список полных, частично заполненных или пустых слябов */

unsigned long colouroff; /* смещение для окрашивания слябов */

void *s_mem;          /* первый объект сляба */

unsigned int inuse;   /* количество выделенных объектов */

kmem_bufctl_t free;   /* первый свободный объект, если есть*/

};

Дескриптор сляба  выделяется или  за  пределами сляба,  в  кэше   общего   назначения, или  в начале  самого  сляба.  Дескриптор хранится внутри  сляба, либо  если  общий  размер  сляба  достаточно мал, либо  если  внутри  самого  сляба  остается достаточно  места, чтобы  разместить дескриптор.

Слябовый распределитель создает  новые  слябы, вызывая интерфейс ядра  нижнего уровня  для  выделения  памяти   __get_free_page s  ()   следующим образом.

static void *kmem getpagss(kmem cache_t *cachep, int flags, int nodeid)

{

struct page *page;

void *addr;

int i;

flags |= cachep->gfpflags;

if (likely(nodeid == -1)) {

addr =(void*)  get_free_pages(flags,cachep->gfporder);

if (!addr)

return NULL;

page =virt_to_page(addr) ;

} else {

page = alloc_pages_node(nodeid, flags, cachep->gfporder);

if (!page)

return NULL;

addr=page_address(page);

}

i = (1 << cachep->gfporder);

if (cachep->flags & SLAB_RECLAIM_ACCOUNT)

atomic_add(i, &slab_reclaim_pages);

add_page_state(nr_slab, i);

while (i–) { SetPageSlab(page);

page++;

}

return addr;

}

Первый  параметр этой  функции указывает на  определенный кэш,  для  которого нужны   новые   страницы памяти.  Второй   параметр  содержит флаги,  которые  предаются  в  функцию   __get_free_page s   () .  Следует  обратить   внимание на  то, как значения этих  флагов  объединяются с другими  значениями с помощью логической операции ИЛИ.  Данная операция дополняет флаги  значением флагов  кэша, которые используются по  умолчанию и  которые обязательно должны  присутствовать п значении  параметра flags .  Количество страниц памяти — целая  степень  двойки — хранится  в поле  cachep->gfporder .  Рассмотренная функция выглядит более  сложной, чем это  может  показаться сначала,  поскольку она  также  рассчитана на  NUMA-системы (Non-Uniform Memory  Access, системы с неоднородным доступом  к памяти). Если  параметр   nodei d  на  равен   -1 , то  предпринимается попытка выделить   память   с  того же узла памяти, на котором выполняется запрос. Такое  решение позволяет получить более  высокую   производительность для  NUMA-систем. Для  таких  систем  обращение к  памяти других узлов  приводит к снижению производительности.

Для  образовательных целей  можно  убрать  код,  рассчитанный на  NUMA-системы, и  получить  более  простой  вариант функции  kraem_getpages ()   в следующем виде.

static inline void * kmem_getpages(kmem_cache_t *cachep, unsigned long flags)

{

void *addr;

flags |= cachep->gfpflags;

addr = (void*)  get_free_pages(flags, cachep->gfporder);

return addr;

}

Память освобождается с помощью функции  kmem_freepages () , которая вызывает функцию free_page s ()  для  освобождения необходимых страниц кэша.  Конечно, назначение уровня   слябового распределения — это  воздержаться от  выделения и освобождения страниц памяти. На  самом  деле  слябовый распределитель использует функции выделения памяти только  тогда, когда  в данном кэше  не  доступен ни  один частично заполненный или  пустой  сляб.  Функция освобождения памяти вызывается только   тогда, когда  становится мало  доступной памяти  и  система пытается освободить  память или  когда  кэш  полностью ликвидируется.

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

Интерфейс слябового распределителя памяти

Новый кэш  можно создать  с помощью вызова  следующей функции.

kmern_cache_t * kmem_cache_create (const char *name, size_t size, size_t offset, unsigned long flags,

void (*ctor) (void*, kmem_cache_t *,unsigned long), void (*dtor) (void*, kmem_cache_t *,unsigned long))

Первый параметр — это  строка, которая содержит имя  кэша. Второй  параметр — это  размер  каждого  элемента кэша. Третий параметр — это  смещение первого объекта в слябе.  Он  нужен  для  того, чтобы  обеспечить необходимое выравнивание по  границам страниц памяти. Обычно достаточно указать  значение, равное нулю, которое соответствует выравниванию  по  умолчанию.  Параметр  flag s  указывает  опциональные  параметры,  которые управляют поведением кэша.  Он  может  быть  равен  нулю, что  выключает все  специальные особенности поведения,  или  состоять из  одного или  более  значений, показанных ниже  и объединенных с помощью логической операции ИЛИ.

• SLAB_NO_REAP — этот  флаг  указывает, что  кэш  не  должен  автоматически  "убирать  мусор"  (т.е.  освобождать память, в которой хранятся неиспользуемые  объекты)   при  нехватке памяти  в системе.  Обычно этот  флаг  не нужно устанавливать, поскольку если  этот  флаг  установлен, то созданный кэш  может  помешать нормальной  работе  системы при  нехватке памяти.

• SLAB_HWCACHE_ALIGN — этот  флаг  указывает уровню  слябового  распределения памяти,  что  расположение каждого   объекта  в слябе  должно  выравниваться по строкам процессорного кэша.  Это  предотвращает так  называемое "ошибочное распределение",  когда  два  или  более  объектов  отображаются в  одну  и  ту же строку  системного кэша,  несмотря на  то  что  они  находятся по  разным адресам  памяти. При  использовании этого  флага  возрастает производительность, но  это  делается  ценой увеличения занимаемой  памяти, потому  что  строгое  выравнивание приводит к тому, что  часть  памяти  сляба  не  используется. Степень

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

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

• SLABPOSON—  этот  флаг  указывает на  необходимость заполнения  слябов  известным числовым значением  (а5а5а5а5). Эта  операция называется  "отравлением"  (poisoning)  и служит  для  отслеживания доступа  к  неинициализированной памяти.

• SLAB_RED_ZONE  — этот  флаг  указывает на  необходимость выделения так  называемых  "красных зон"  (red zone)  для  облегчения детектирования  переполнений буфера.

• SLAB_PANIC — этот  флаг  указывает на  необходимость перевода ядра  в  состояние  паники, если  выделение памяти было  неудачным. Данный флаг  полезен, если  выделение памяти  всегда  должно завершаться успешно,  как,  например, в случае  создания кэша   структур  VMA  (областей виртуальной  памяти,  см.  главу 14, "Адресное  пространство процесса") при  загрузке  системы.

• SLAB_CACHE_DMA — этот  флаг  указывает уровню  слябового распределения,  что все  слябы  должны выделяться в памяти, с  которой возможны операции  прямого  доступа  к  памяти. Это  необходимо,  когда  объекты используются  в  операциях ПДП и должны находиться в зоне  ZONE_DMA. В противном случае  эта возможность не  нужна  и этот  флаг  не  нужно  устанавливать.

Два  последних параметра cto r  и  dto r — это  конструктор и деструктор кэша  соответственно. Конструктор вызывается,  когда  в  кэш  добавляются новые   страницы памяти.  Деструктор вызывается,  когда  из  кэша  удаляются страницы памяти.  Если указан  деструктор, то должен  быть указан  и конструктор. На  практике кэши ядра  ОС Linux  обычно не  используют функции  конструктора и деструктора.  В качестве этих параметров можно указывать значение NULL.

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

int kmem_cache_destroy(kmem_cache_t *cachep)

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

• Все  слябы кэша являются пустыми. Действительно, если в каком-либо слябе  существует объект, который все  еще используется, то  как можно  ликвидировать кэш?

• Никто не будет обращаться к кэшу во  время и особенно после вызова  функции kmem_cache_destroy () . Эту  синхронизацию должен обеспечить  вызывающий код.

В  случае успешного выполнения  функция  возвращает нуль, в других случаях возвращается ненулевое значение.

После того как кэш создан, из него можно получить объект путем вызова следующей функции.

void * kmem_cache_alloc(kmem_cache_t *cachep, int flags)

Эта функция возвращает указатель на объект из кэша, на который указывает параметр cachep. Если ни в  одном из слябов нет свободных объектов, то  уровень слябового распределения должен получить новые страницы памяти с  помощью функции kmem_getpages  () ,  значение параметра flag s   передается  в   функцию__get_free _ page s () . Это те  самые флаги, которые были рассмотрены ранее. Скорее всего, необходимо указывать GFP_KERNEL или GFP_ATOMIC.

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

void kmem_cache_free(kmem_cache_t *cachep, void *objp)

Данная функция помечает объект, на который указывает параметр objp, как свободный.

Пример использования слябового распределителя памяти

Давайте рассмотрим пример из реальной жизни, связанный с работой со структурами task_struc t (дескрипторы процессов). Показанный ниже код в несколько более сложной форме приведен в файле kernel/fork.с .

В ядре определена глобальная переменная, в которой хранится указатель на кэш объектов task_struct :

kmem_cache_t *task_struct_cachep;

Во время инициализации ядра, в функции forkini t (), этот кэш создается следующим образом.

task_struct_cachep = kmem_cache_create("task_struct", sizeof(struct task_struct), ARCH_M1N_TASKALIGN, SLAB_PANIC,

NULL, NULL);

Данный вызов  создает  кэш  с  именем  "task_struct" ,  который предназначен для хранения объектов тина  struc t    task_struct .  Объекты  создаются с начальным смещением в слябе, равным ARCH_MIN_TASKALIGN  байт, и положение всех объектов выравнивается по  границам строк  системного кэша, значение этого  выравнивания зависит  от  аппаратной платформы.  Обычно значение выравнивания  задается  для  каждой аппаратной платформы с  помощью  определения  препроцессора  LI_CACHE_BYTES, которое равно  размеру  процессорного кэша  первого  уровня  в байтах.  Конструктор и деструктор   отсутствуют.   Следует  обратить   внимание, что  возвращаемое значение  не проверяется на  рапенство NULL,  поскольку указан  флаг  SLAB_PANIC. В случае, когда при  выделении памяти произошла ошибка,  слябовый распределитель памяти вызовет функцию pani c () .  Если  этот  флаг  не  указан, то нужно  проверять возвращаемое значение на  равенство NULL,  что  сигнализирует об  ошибке. Флаг  SLAB_PANIC  здесь используется потому,  что  этот  каш  является  необходимым для  работы  системы  (без дескрипторов процессов работать  как-то не  хорошо).

Каждый раз,  когда  процесс  вызывает функцию  for k () , должен  создаваться новый  дескриптор процесса (вспомните главу 3, "Управление процессами"). Это  выполняется следующим образом в  функции  dup_task_struc t ()  ,  которая вызывается из функции do_for k ()  .

struct task_struct *tsk;

tsk = kmem_cache_alloc(task struct_cachep, GFP_KERNEL);

if (!tsk)

return NULL;

Когда процесс завершается, если нет  порожденных процессов, которые ожидают на завершение родительского процесса, то  дескриптор освобождается и  возвращается обратно в  кэш task_struct_cachep .  Эти действия выполняются в  функции free_task_struc t () , как показано ниже (где   параметр ts k  указывает на удаляемый дескриптор).

kmem_cache_free(task_struct_cachep, tsk);

Так как дескрипторы процессов принадлежат к основным компонентам ядра и всегда необходимы, то  кэш task_struct_cache p  никогда не ликвидируется. Если бы  он ликвидировался, то  делать это  необходимо было бы  следующим образом.

int err;

err = kmem_cache_destroy (task_struct_cachep);

if (err)

/* ошибка ликвидации кэша */

Достаточно просто, не так ли?  Уровень слябопого распределения памяти скрывает все  низкоуровневые операции, связанные с выравниванием, "раскрашипанием", выделением и  освобождением памяти,  "сборкой мусора" в случае нехватки памяти. Коли часто необходимо создавать много объектов одного типа, то  следует подумать об  использовании слябового кэша. И уж  точно не нужно писать свою реализацию списка свободных ресурсов!

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии