Linux Kernel (Ядро линукса) (часть 1)

Окрашивание участков памяти

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

Прежде чем обсудить окрашивание участков, мы должны рассмотреть схему расположения объектов в кэше. Возьмем кэш, объекты которого выровнены в оперативной памяти. Это означает, что адрес объекта должен быть кратен заданному положительному значению, скажем, ain. Даже с учетом ограничений по выравниванию, существует масса способов разместить объекты внутри участка памяти. Выбор того или иного способа зависит от решений, принятых в отношении следующих переменных:
- пит— количество объектов, которые могут храниться в участке памяти (значение этой переменной находится в поле пит дескриптора кэша);
- osize — размер объекта, включая байты выравнивания;
- dsize — размер дескриптора участка плюс общий размер всех дескрипторов объектов, с округлением до наименьшего числа, кратного размеру строчки аппаратного кэша. Значение этой переменной равно 0, если дескрипторы участка и объектов хранятся вне участка памяти;
- free — количество неиспользованных байтов (байтов, не присвоенных ни одному объекту) внутри участка.
Длина участка памяти в байтах может быть выражена следующим образом:
длина участка = {пит х osize) + dsize+ free
Значение free всегда меньше osize, потому что в противном случае было бы возможно разместить в участке дополнительные объекты. Однако free может быть больше ain.

Slab-аллокатор использует free свободных байтов для окрашивания участка. Термин "цвет” взят лишь для того, чтобы провести различие между участками и позволить аллокатору памяти распределить объекты по разным линейным адресам. В результате ядро выжимает” максимальную производительность из аппаратного кэша процессора.

Участки, имеющие разные цвета, хранят свои первые объекты в разных местах памяти, удовлетворяя при этом требования по выравниванию. Количество свободных цветов равно f ree/ain (это значение хранится в поле colour дескриптора кэша). Таким образом, первый цвет обозначается нулем, а последний— числом (free/ain)-l. (В частном случае, когда free меньше ain, в поле colour записывается ноль, для всех участков используется цвет 0, но, в действительности, количество цветов равно одному.)

Если участок окрашен цветом col, смещение первого объекта (относительно начального адреса участка) равно col х ain + dsize байтов. На рис. 8.6 показано, как расположение объектов внутри участка зависит от цвета этого участка. Окрашивание фактически приводит к перемещению определенной части свободной области в участке от конца к началу.

Окрашивание эффективно, когда значение free достаточно велико. Очевидно, что если выравнивание объектов не требуется, или количество неиспользуемых байтов внутри участка меньше требуемого выравнивания freearray[smp_processor_id()];
if (ac->avail) {ac->touched = 1;
objp = ((void )(ac+1))[—ac->avail];} else
objp = cache_alloc_refill(cachep, flags); local_irq_restore(save_flags); return objp;}
Вначале функция пытается получить свободный объект из локального кэша. Если свободный объект есть в наличии, то поле avail содержит индекс в локальном кэше, относящийся к элементу, указывающему на последний освобожденный объект. Поскольку массив локального кэша расположен непосредственно после дескриптора ас, фрагмент кода ((void) (ас+щ [—ас-> avail] извлекает адрес этого свободного объекта и уменьшает значение ac->avaii. Функция cache aiioc refiii вызывается для пополнения локального кэша и получения свободного объекта, если свободных объектов в локальном кэше не оказалось.

Функция cache aiioc refiii о выполняет следующие действия:

1. Сохраняет в локальной переменной ас адрес дескриптора локального кэша:
ас = cachep->array[smp_processor_id()];
2. Получает спин-блокировку cachep->spinlock.
3. Если кэш участков содержит совместно используемый локальный кэш, и этот совместно используемый локальный кэш содержит какое-то количество свободных объектов, функция пополняет локальный кэш данного процессора, перенося в него до ac->batchcount указателей из совместно используемого. Затем она переходит к шагу .
4. Пытается пополнить локальный кэш, занося в него до ac->batchcount указателей на свободные объекты, расположенные в участках кэша:
• просматривает списки siabs partiai и siabs free дескриптора кэша и получает адрес siabp дескриптора участка, являющегося либо частично заполненным, либо вовсе пустым. Если такой дескриптор не обнаруживается, функция переходит к шагу 5;
• для каждого свободного объекта в участке функция увеличивает поле inuse дескриптора участка, заносит адрес объекта в локальный кэш и обновляет значение в поле free так, чтобы оно хранило индекс следующего свободного объекта в участке:
slabp->inuse++;
((void)(ас+1))[ac->avail++] =
slabp->s_mem + slabp->free cachep->obj_size; slabp->free = ((kmem_bufctl_t)(slabp+1))[slabp->free];
• заносит, если необходимо, очищенный участок в соответствующий СПИСОК, либо slab_full, либо slab_partial.
5. На этом шаге количество указателей, добавленных в локальный кэш, уже хранится в поле ac->avaii. Функция уменьшает значение поля free objects структуры kmem_iist3 именно на эту величину, отмечая, что эти объекты более не свободны.
6. Освобождает cachep->spinlock.
7. Если сейчас поле ac->avaii больше 0 (имело место пополнение кэша), функция устанавливает поле ac->touched в единицу и возвращает указатель на свободный объект, который был последним занесен в локальный кэш:
return ((void)(ас+1))[—ac->avail];
8. В противном случае пополнения кэша не было. Функция вызывает функцию cache grow () для получения нового участка и, следовательно, новых свободных объектов.
9. Если работа функции cache growO закончилась неудачей, описываемая функция возвращает null; в противном случае она возвращается к шагу 1 и повторяет всю процедуру.
Освобождение объекта в участке
Функция kmem cache fгее освобождает объект, ранее выделенный slab- аллокатором для некоторой функции ядра. Ее параметрами являются cachep, адрес дескриптора кэша, и objp, адрес освобождаемого объекта:
void kmem_cache_free(kmem_cache_t cachep, void objp)
{unsigned long flags; struct array_cache ac;
local_irq_save(flags);
ac = cachep->array[smp_processor_id()]; if (ac->avail == ac->limit)cache_flusharray(cachep, ac) ;
((void)(ac+1))[ac->avail++] = objp; local_irq_restore(flags);}
Вначале функция проверяет, имеется ли в локальном кэше место под еще один указатель на свободный объект. Если это так, указатель добавляется в локальный кэш, и функция возвращает управление. В противном случае она сперва вызывает функцию cache f lusharray о для очистки локального кэша, а затем заносит указатель в локальный кэш.

Функция cachef lusharray выполняет следующие действия:
1. Получает спин-блокировку cachep->spinlock.
2. Если кэш участков содержит совместно используемый локальный кэш, и этот совместно используемый локальный кэш еще не заполнен, функция пополняет совместно используемый локальный кэш, перенося в него до ac->batchcount указателей из локального кэша данного процессора. Затем она переходит к шагу
3. Вызывает функцию free biocko, чтобы вернуть slab-аллокатору до ас-> batchcount объектов, находящихся в этот момент в локальном кэше. Для каждого объекта с адресом objp функция выполняет следующие действия:
• увеличивает поле lists. free objects дескриптора кэша;
• определяет адрес дескриптора участка, содержащего объект:
slabp = (struct slab )(virt_to_page(objp)->lru.prev);
Вспомним, что поле lru.prev дескриптора страницы участка указывает на соответствующий дескриптор участка.
• удаляет дескриптор участка из списка кэша участков (либо cachep-> lists.slabs_partial, либо cachep->lists.slabs_full);
• вычисляет индекс объекта внутри участка:
objnr = (objp — slabp->s_mem) / cachep->objsize;
• сохраняет в дескрипторе объекта текущее значение поля siabp->free и записывает в поле siabp->free индекс объекта (последний освобожденный объект будет выделен первым, когда потребуется):
((kmem_bufctl_t )(slabp+1))[objnr] = slabp->free; slabp->free = objnr;
• уменьшает поле siabp->inuse;
• если siabp->inuse равно 0 (все объекты в участке свободны), и количество свободных объектов во всем кэше участков (cachep-> lists, free objects) больше максимума, хранящегося В поле cachep-> free iimit, то функция освобождает страничный кадр (или несколько кадров) участка памяти для зонного аллокатора страничных кадров:
cachep->lists.free_objects -= cachep->num; slab_destroy(cachep, slabp);
Значение в поле cachep->free_limit обычно равно cachep->num + (1+N) x cachep->batchcount, где N — количество процессоров в системе.
• в противном случае, если значение siab->inuse равно 0, но количество свободных объектов во всем кэше участков меньше предельного значения cachep->f ree iimit, функция вставляет дескрипторы участка в список cachep->lists.slabs_fгее;
• наконец, если значение siab->inuse больше нуля, значит, участок заполнен частично, и функция заносит его дескриптор в список cachep-> lists.slabs_partial.
4. Освобождает спин-блокировку cachep->spinlock.
5. Обновляет поле avail дескриптора локального кэша, вычитая количество объектов, перемещенных в совместно используемый локальный кэш или освобожденных для slab-аллокатора.
6. Сдвигает все действующие указатели в локальном кэше в начало массива этого локального кэша. Данный шаг необходим, потому что первые указатели на объекты были удалены из локального кэша, и остальные должны быть передвинуты.
Объекты общего назначения
Как было сказано ранее в этой главе, нечастые запросы на области памяти обрабатываются с помощью группы общих кэшей, объекты которых имеют размеры, геометрически распределенные в диапазоне от 32 до 131 072 байтов.
Объекты этого типа можно получить, вызвав функцию kmaiiocO, которая эквивалентна следующему коду:
void kmalloc(size_t size, int flags)
{struct cache_sizes csizep = malloc_sizes; kmem_cache_t cachep; for (; csizep->cs_size; csizep++) { if (size > csizep->cs_size) continue;if (flags & GFP_DMA)
cachep = csizep->cs_dmacachep;else
cachep = csizep->cs_cachep; return kmem_cache_alloc(cachep,
flags);}return NULL;}
Функция пользуется таблицей maiioc sizes, чтобы найти размер, являющийся степенью двойки и ближайший к запрошенному размеру. Затем она вызывает функцию kmem cache aiioc, чтобы выделить объект, передавая ей либо дескриптор кэша для страничных кадров, пригодных для ISA DMA, либо дескриптор кэша для "нормальных” кадров, в зависимости от того, установил ли вызывающий процесс флаг gfp_dma.
Объекты, полученные при помощи функции kmaiiocO, могут быть освобождены функцией kf гее :
void kfree(const void objp)
{kmem_c a с he_t c; unsigned long flags; if (!objp) return; local_irq_save(flags) ;с = (kmem_cache_t )(virt_to_page(objp)->lru.next);kmem_cache_free(c, (void )objp); local_irq_restore(flags);}
Нужный дескриптор кэша идентифицируется с помощью подполя iru.next дескриптора первого страничного кадра, содержащего область памяти. Область памяти освобождается функцией kmem_cache_f гее.