Содержание


Инструменты программирования в ядре: Часть 64. Распределители памяти

Comments

В предыдущей статье мы рассмотрели принципиальные основы механизмов выделения памяти, существующих в ОС Linux. В этой статье мы рассмотрим несколько вариантов использующихся реализаций таких механизмов.

Распределители памяти

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

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

Подход, применявшийся в Linux для выделения больших регионов (называемый buddy memory allocation), выделяет по запросу блок, размер которого кратен степени 2 и превышает запрошенный размер (т.е. используется подход best-fit). При освобождении блока предпринимается попытка слить все свободные соседние блоки в освобождаемый свободный блок. Такой подход позволяет снизить фрагментирование и повысить эффективность управления свободным пространством, но может существенно увеличить непродуктивное расходование памяти.

Алгоритм распределителя, использующийся в kmalloc(), начиная с версий ядра 2.6, в качестве основного механизма для текущего выделения небольших блоков памяти называется сляб алокатор (slab allocation). Слябовый распределитель был впервые предложен Джефом Бонвиком (Jeff Bonwick) и реализован в SunOS в середине 90-х годов. Принцип такого распределителя состоит в том, что последовательные запросы на выделение памяти под объекты равного размера удовлетворяются из области одного кэша (сляба), а запросы на объекты другого размера (пусть отличающиеся от первого случая самым незначительным образом) — удовлетворяются из другого такого же кэша.

Примечание: Сам термин сляб переводится как «облицовочная плитка», что очень близко к его техническому значению, так как любую вынутую из плоскости плитку можно заменить другой такой же, если их размеры в точности совпадают.

Использование алокатора SLAB (по умолчанию) может быть отменено при новой сборке ядра (параметр CONFIG_SLAB). Подобное решение применяется для небольших и встроенных систем, где используется другой алокатор SLOB. Алокатор SLOB выстраивает участки выделяемой памяти в единый линейный связный список. и может сэкономить до 512KБ памяти по сравнению со SLAB. Но этот способ страдает уже названными недостатками, главный из которых — фрагментация.

Начиная с версии ядра 2.6.22, появляется распределитель SLUB, разработанный Кристофом Лэйметром (Christoph Lameter), но это ещё одна реализация базовой идеи распределителя SLAB. В отличие от SLOB, ориентированного на малые конфигурации, SLUB предназначен для систем с большими и огромными объёмами RAM. Его идея состоит в том, чтобы уменьшить непроизводительные расходы на управляющие структуры слябов при их больших объёмах. Для этого управление организуется не на основе единичных страниц памяти, а на основе объединения таких страниц в группы, и управлении уже на базе групп страниц.

Точно узнать об используемой версии распределителя можно по конфигурационным параметрам, с которыми собиралось ядро, например:

$ cat /boot/config-2.6.32.9-70.fc12.i686.PAE | grep CONFIG_SLOB 
# CONFIG_SLOB is not set 
$ cat /boot/config-2.6.32.9-70.fc12.i686.PAE | grep CONFIG_SLAB 
# CONFIG_SLAB is not set 
CONFIG_SLABINFO=y 
$ cat /boot/config-2.6.32.9-70.fc12.i686.PAE | grep CONFIG_SLUB 
CONFIG_SLUB_DEBUG=y 
CONFIG_SLUB=y 
...

Далее в оставшейся части статьи мы подробно рассмотрим только слябовый распределитель SLAB.

Слябовый распределитель

Текущее состояние слябового распределителя можем узнать в файловой системе /proc, где можно получить достаточно информации и о самом принципе работы слябового распределения:

$ cat /proc/slabinfo 
slabinfo - version: 2.1 
# name     ... : tunables ... : slabdata ... 
...
kmalloc-8192  28     32     8192  4   8 : tunables  0  0  0 : slabdata  8    8    0
kmalloc-4096  589    648    4096  8   8 : tunables  0  0  0 : slabdata  81   81   0
kmalloc-2048  609    672    2048  6   8 : tunables  0  0  0 : slabdata  42   42   0
kmalloc-1024  489    512    1024  16  4 : tunables  0  0  0 : slabdata  32   32   0
kmalloc-512   3548   3648   512   16  2 : tunables  0  0  0 : slabdata  28   28   0
kmalloc-256   524    656    256   16  1 : tunables  0  0  0 : slabdata  41   41   0
kmalloc-128   13802  14304  128   32  1 : tunables  0  0  0 : slabdata  47   447  0
kmalloc-64    12460  13120  64    64  1 : tunables  0  0  0 : slabdata  205  205  0
kmalloc-32    12239  12800  32   128  1 : tunables  0  0  0 : slabdata  100  100  0
kmalloc-16    25638  25856  16   256  1 : tunables  0  0  0 : slabdata  101  101  0
kmalloc-8     11662  11776  8    512  1 : tunables  0  0  0 : slabdata  23   23   0
...

Принцип работы алокатора прост: сляб с указанием размера должен быть создан (зарегистрирован) вызовом kmem_cache_create(), а потом из него можно "черпать" элементы фиксированного размера вызовами kmem_cache_alloc() (в который скорее всего и ретранслируется вызов kmalloc()). Все сопутствующие описания можно найти в файле <linux/slab.h>.

Но эта чёткая картина "размывается" при переходе к деталям реализации, так как прототип функции kmem_cache_create() менялся от версии к версии.

В версии 2.6.18 и практически во всей литературе этот вызов описан так:

kmem_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 flags ),
                  void (*dtor)( void*, kmem_cache_t*, unsigned long flags ) );
  • name— строка c названием кэша;
  • size— размер элементов кэша (единый и общий для всех элементов);
  • offset— смещение первого элемента от начала кэша (для обеспечения соответствующего выравнивания по границам страниц достаточно указать 0, что означает выравнивание по умолчанию);
  • flags— опциональные параметры (может быть 0);
  • ctor, dtorконструктор и деструктор, вызываемые при размещении-освобождении каждого элемента, но с некоторыми ограничениями, так как, хотя деструктор и будет вызываться, но не гарантируется, что это произойдёт сразу после удаления объекта.

Но в версии 2.6.24 прототип этого вызова меняется, и деструктор исчезает из его описания, а версиях 2.6.32, 2.6.35 и 2.6.35 меняется прототип конструктора, так что вызов выглядит уже так:

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

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

Флаги создания (параметр flags) по большей части относятся к отладочным опциям и также могут меняться в разных версиях ядра. Ниже перечислены некоторые из флагов

  • SLAB_HWCACHE_ALIGN— расположение каждого элемента в слябе должно выравниваться по строкам процессорного кэша, это может существенно поднять производительность, но приводит к дополнительному расходованию памяти;
  • SLAB_POISON— начально заполняет сляб предопределённым значением (A5A5A5A5) для обнаружения выборки неинициализированных значений;

В типовом случае для параметра flags можно установить нулевое значение.

Как и для любой операции выделения, существует обратная операция по уничтожению сляба:

int kmem_cache_destroy( kmem_cache_t *cache );

Операция уничтожения будет выполнена успешна, если только все объекты, полученные из кэша, были возвращены в него. Таким образом, модуль должен проверить статус, возвращённый kmem_cache_destroy()— ошибка указывает на утечку памяти в модуле, так как некоторые объекты не были возвращены.

После того, как кэш объектов был создан, можно выделять объекты из него следующим вызовом:

void *kmem_cache_alloc( kmem_cache_t *cache, int flags );

Здесь flags— те же, что передаются kmalloc().

Полученный объект должен быть возвращён когда в нём отпадёт необходимость:

void kmem_cache_free( kmem_cache_t *cache, const void *obj );

Несмотря на изменчивость API сляб алокатора, вы сможете охватить весь диапазон версий ядра, используя директивы условной трансляции препроцессора. В листинге 1 представлен сокращённый код модуля slab, использующего такой алокатор, а полный код примера можно найти в архиве slab.tgz в разделе "Материалы для скачивания".

Листинг 1. Модуль ядра, использующий сляб алокатор
static int size = 7;  // для наглядности  простые числа
module_param( size, int, 0 );
static int number = 31;
module_param( number, int, 0 );
   
static void* *line = NULL;
         
static int sco = 0;
static
#if LINUX_VERSION_CODE > KERNEL_VERSION(2,6,31)
void co( void* p ) {
#else
void co( void* p, kmem_cache_t* c, unsigned long f ) {
#endif
   *(int*)p = (int)p;
   sco++;
} 
#define SLABNAME "my_cache"
struct kmem_cache *cache = NULL;
   
static int __init init( void ) {
   int i;
   if( size < sizeof( void* ) ) {
      printk( KERN_ERR "invalid argument\n" );
      return -EINVAL;
   }
   line = kmalloc( sizeof(void*) * number, GFP_KERNEL );
   if( !line ) {
      printk( KERN_ERR "kmalloc error\n" );
      goto mout;
   }
   for( i = 0; i < number; i++ )
      line[ i ] = NULL;
#if LINUX_VERSION_CODE < KERNEL_VERSION(2,6,32)
   cache = kmem_cache_create( SLABNAME, size, 0, SLAB_HWCACHE_ALIGN, co, NULL );
#else
   cache = kmem_cache_create( SLABNAME, size, 0, SLAB_HWCACHE_ALIGN, co );
#endif 
   if( !cache ) {
      printk( KERN_ERR "kmem_cache_create error\n" );
      goto cout;
   }
   for( i = 0; i < number; i++ )
      if( NULL == ( line[ i ] = kmem_cache_alloc( cache, GFP_KERNEL ) ) ) {
         printk( KERN_ERR "kmem_cache_alloc error\n" );
         goto oout;
      }
   printk( KERN_INFO "allocate %d objects into slab: %s\n", number, SLABNAME );
   printk( KERN_INFO "object size %d bytes, full size %ld bytes\n", 
           size, (long)size * number );
   printk( KERN_INFO "constructor called %d times\n", sco );
   return 0;
oout:
   for( i = 0; i < number; i++ )
      kmem_cache_free( cache, line[ i ] );
cout:
   kmem_cache_destroy( cache );
mout:
   kfree( line );
   return -ENOMEM;
}
module_init( init );

static void __exit exit( void ) {
   int i;
   for( i = 0; i < number; i++ )
      kmem_cache_free( cache, line[ i ] );
   kmem_cache_destroy( cache );
   kfree( line );
}
module_exit( exit );

Ниже представлен результат запуска данного примера:

$ sudo insmod ./slab.ko$ dmesg | tail -n300 | grep -v audit
allocate 31 objects into slab: my_cache
object size 7 bytes, full size 217 bytes
constructor called 257 times
$ cat /proc/slabinfo | grep my_
# name   <active_objs> <num_objs> <objsize> ...
my_cache  256  256  16  256  1 : tunables  0  0  0 : slabdata  1  1  0
$ sudo rmmod slab

Как видно, объекты размером 7 байт благополучно разместились в новом слябе с именем my_cache, отображаемом в /proc/slabinfo, организованным с размером элементов 16 байт, а конструктор при размещении 31 объекта вызывался 257 раз. Обратите внимание на важное обстоятельство: при создании сляба никак не указывается реальный или максимальный объём памяти, находящейся под управлением этого сляба, так как это динамическая структура, "добирающая" количество страниц памяти, необходимое для размещения требуемого числа элементов данных (с учётом их размера). Увеличенное число вызовов конструктора можно объяснить необходимостью переразмещения существующих элементов при последующих запросах и эффектами SMP (2 ядра) и перераспределения данных между процессорами. Запустим этот же тест на однопроцессорном Celeron и более старой версии ядра:

$ sudo /sbin/insmod ./slab.ko$ /sbin/lsmod | grep slab
slab                    7052  0
$ dmesg | tail -n3
allocate 31 objects into slab: my_cache
object size 7 bytes, full size 217 bytes
constructor called 339 times
$ cat /proc/slabinfo | grep my_
# name   <active_objs> <num_objs> <objsize> ...
my_cache  31  339  8  339  1 : tunables  120  60  8 : slabdata  1  1  0
$ sudo /sbin/rmmod slab

Число вызовов конструктора не уменьшилось, а даже возросло, а вот размер объектов, под который создан сляб, изменился с 16 на 8.

Примечание: Если рассмотреть 3 первых поля вывода /proc/slabinfo, то и в первом и во втором случае видно, что под сляб было размечено некоторое фиксированное количество объектов (339 в последнем примере), которые укладываются в начальный объём сляба (меньше или порядка 1-й страницы физической памяти).

Если запустить показанный тест с большим размером блока и числом блоков для размещения (заметно больше показанных выше значений), то можно наблюдать интересную ситуацию, когда распределитель памяти начнёт настолько активно отбирать память у системы, что постепенно "угаснут" все графические приложения и подсистема X11, но текстовые консоли останутся работоспособными.

Механизм пула памяти

Ещё одна вариация на тему распределителя памяти, в том числе и сляб-алокатора — это механизм пула памяти:

#include <linux/mempool.h>
mempool_t *mempool_create( int min_nr,
                           mempool_alloc_t *alloc_fn, mempool_free_t *free_fn,
                           void *pool_data );

Пул памяти сам по себе является интерфейсом к алокатору (к тому же кэшу, например). Само наименование "пул" предполагает, что такой механизм будет всегда поддерживать "в горячем резерве" некоторое количество объектов для распределения. Параметр вызова min_nr определяет минимальное число выделенных объектов, которые всегда должны быть в наличии в пуле. Фактическое выделение и освобождение объектов по запросам обслуживают вызовы alloc_fn() и free_fn(), имеющие следующие прототипы, которые должны быть реализованы пользователем:

typedef void* (*mempool_alloc_t)( int gfp_mask, void *pool_data );
typedef void (*mempool_free_t)( void *element, void *pool_data );

Последний параметр mempool_create()pool_data передаётся последним параметром в вызовы alloc_fn() и free_fn().

Но в большинстве случаев всю работу можно переложить на стандартные обработчики-распределители, так как в <linux/mempool.h> объявлено несколько групп API для разных распределителей памяти. Существуют две функции (mempool_alloc_slab() и mempool_free_slab()), предназначенные для уже рассмотренного сляб алокатора и выполняющие соответствующие согласования между прототипами выделения пула памяти и kmem_cache_alloc() и kmem_cache_free(). Таким образом, код, инициализирующий пул памяти, который будет использоваться сляб алокатором для управления памятью, часто выглядит следующим образом:

// создание нового сляба 
kmem_cache_t *cache = kmem_cache_create( ... );
// создание пула, который будет распределять память из этого сляба
mempool_t *pool = mempool_create( MY_POOL_MINIMUM,
                                  mempool_alloc_slab, mempool_free_slab, cache );

После того, как пул был создан, объекты могут быть выделены и освобождены с помощью вызовов:

void *mempool_alloc_slab( gfp_t gfp_mask, void *pool_data );
void mempool_free_slab( void *element, void *pool_data );

После инициализации пула памяти функция выделения будет вызвана достаточное число раз для создания предопределённых объектов. Когда после этого вызовы mempool_alloc_slab() попытаются запросить новые объекты, то будет возвращен один из уже предопределённых объектов (если такие имеются в наличии). При освобождении объекта вызовом mempool_free_slab() он сохраняется в пуле, если количество предопределённых объектов в настоящее время ниже минимального, в противном случае он будет возвращён в систему.

Примечание: Такие же группы API существуют и для kmalloc()-версии распределителя пула памяти (mempool_kmalloc()) и для страничного распределителя памяти (mempool_alloc_pages()).

Размер пула памяти можно изменять динамически:

int mempool_resize( mempool_t *pool, int new_min_nr, int gfp_mask );

В случае успеха этот вызов изменяет размеры пула так, чтобы в нём имелось по крайней мере new_min_nr объектов.

Когда необходимость в пуле памяти исчезает, то он возвращается системе вызовом:

void mempool_destroy( mempool_t *pool );

Страничное выделение

В ситуации, когда требуется блок размером в несколько машинных страниц (более одной), используется следующий вызов из <linux/gfp.h>:

struct_page * alloc_pages( gfp_t gfp_mask, unsigned int order )

Этот вызов выделяет 2**order смежных страниц (непрерывный участок) физической памяти, но полученный физический адрес потребуется конвертировать в логический для использования вызовом:

void *page_address( struct_page * page )

Если физический адрес не требуется, то логический адрес можно получить с помощью вызовов:

  • unsigned long __get_free_page( gfp_t gfp_mask )— выделяет одну страницу;
  • unsigned long get_zeroed_page( gfp_t gfp_mask )— выделяет одну страницу и заполняет её нулями;
  • unsigned long __get_free_pages( gfp_t gfp_mask, unsigned int order )— выделяет несколько (2**order) последовательных страниц в непрерывной области.

Принципиальное отличие выделенного таким способом участка памяти от аналогичного участка, выделенного при помощи kmalloc(), состоит в том, что участок, выделенный механизмом страничного выделения, всегда будет выровнен на границу страницы.

В любом случае, выделенную страничную область после использования необходимо возвратить по логическому или физическому адресу способом, симметричным тому, который использовался для выделения:

void __free_pages( unsigned long addr, unsigned long order );
void free_page( unsigned long addr );
void free_pages( unsigned long addr, unsigned long order );

При попытке освободить число страниц, отличное от ранее выделенного, карта памяти становится повреждённой и система позднее будет разрушена.

Заключение

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


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=937727
ArticleTitle=Инструменты программирования в ядре: Часть 64. Распределители памяти
publish-date=07182013