Подсистема управления памятью одна из самых важных. От её быстродействия и от того насколько эффективно она распоряжается оперативной памятью зависят все остальные подсистемы.
При рассмотрении подсистемы памяти важно знать и понимать, какие типы памяти есть и про какие говорят. Далее будут рассматриваться два типа памяти:
- Физическая - оперативная память машины.
- Линейная - виртуальная память, она может быть больше, чем реально физической памяти у вас есть.
Вся физическая память разбита на страничные кадры. Размер страничного кадра - платформозависимая величина, для x86 она обычно равна 4 Кб, хотя может быть и 4 Мб. Каждый физический кадр описывается фундаментальной структурой данных - struct page (include/linux/mm_types.h). Структура используется, чтобы отслеживать состояние страничного кадра: свободен или выделен, кому он принадлежит, что на нём хранится: данные, код и т.д. Struct page организована в блоки двойных слов для выполнения над ними атомарных операций, работающих с двойными словами. Опишем некоторые важные поля struct page:
- atomic_t _refcount - количество ссылок на структуру page. Из функции init_free_pfn_range() (mm/init.c) следует, что если _refcount равен 0, то страничный кадр свободен, если >0, то кем-то или чем-то занят.
- unsigned long flags - содержит флаги, описывающие состояние страничного кадра. Все флаги описаны в файле (include/linux/page-flags.h).
Физическая память 32-битной машины в Linux разделяется на 3 части - зоны:
- ZONE_DMA - первые 16 Мб физической памяти,
- ZONE_NORMAL - занимает адреса с 16 Мб по 896 Мб,
- ZONE_HIGHMEM - содержит страничные кадры выше 896 Мб
Такое разбиение физической памяти в 32 битных системах связано с тем, что в них можно адресовать только лишь 4 Гб линейной памяти, при этом процессу необходимо работать, как в пользовательском режиме, так и в режиме ядра, например, для выполнения системных вызовов. Потому линейное пространство адресов процесса разбивается на несколько частей: 3 Гб под пользователя и 1 Гб под ядро. В первых 3 Гб в адресах до 0xС0000000 процесс работает в режиме обычного пользователя, а адреса выше 0xС0000000 используются в режиме суперюзера. Зоны NORMAL и DMA напрямую отображаются в 4-ый Гб линейного адресного пространства. К объектам, расположенным в этих областях, всегда можно получить доступ, так как для них существуют линейные адреса. А вот HIGHMEM зона содержит кадры, к которым ядро так просто обратится не может. Из-за того, что HIGHMEM содержит кадры, линейные адреса которых просто напросто не существуют в 32-битной системе. Потому функция для выделения страничных кадров - alloc_page() возвращает указатель(линейный адрес) не на первый страничный кадр, а на первый страничный дескриптор, описывающий этот кадр. При этом все дескрипторы страничных кадров находятся в NORMAL зоне, потому для них всегда существует линейный адрес. Для отображения верхних адресов в линейное адресное пространство используются верхние 128 МБ NORMAL адресов. Вообще для отображения HIGHMEM есть несколько техник:
- постоянное отображение,
- временное отображения,
- работа с несмежными областями памяти.
Linux - современная кроссплатформенная операционная система, а такая система обязана уметь эффективно работать с многопроцессорными системами. В таких системах существует несколько подходов к реализации компьютерной памяти. Первая - Uniform memory access (UMA). В этой схеме доступ ко всей физической памяти примерно равноценен по времени, потому нет абсолютно никакой разницы для производительности операционной системы к каким адресам обращаться. Надо заметить, что не в каждой вычислительной системе поддерживается одинаковый доступ к памяти, потому в Linux в качестве базовой модели поддерживается - Non-Uniform memory access (NUMA). В этой модели физическая память системы разделяется на несколько узлов. Каждый узел описывается структурой pg_data_t (include/linux/mmzone.h). Каждый узел потенциально может содержать любую из зон памяти, потому структура pg_data_t содержит их описатели. Все дескрипторы страничных кадров узлов хранятся в глобальном массиве zone_mem_map, который располагается в описателе соответсвующей зоны:
pg_data_t
|
________________node_zones_______________
/ | \
ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM
| | |
zone_mem_map zone_mem_map zone_mem_map
Красота такого подхода при работе с памятью заключается в том, что UMA представляется просто, как NUMA с одним узлом, что так же позволяет использовать везде одинаковые методы - универсальность во всём, так сказать.
На 64-битных машинах, физическая память так же разделяется на 3 части, но в силу объективных причин, реальные 64-битные машины не могут сейчас содержать все 2^64 степени байт памяти. В x86, например, поддерживается память только до 2^48 байт = 256 Тб, что, согласитесь, достаточно много. Так как реальной физической памяти много меньше линейной, то у 64-битных систем надобность в HIGHMEM зоне пока отсутствует, она нулевая, а вся помять делиться между DMA и NORMAL.
Теперь мы знаем, как Linux описывает доступную ему физическую память, пришло время разобрать, как ядро работает с памятью. Для этого важно разобрать, как Linux её выделяет, или, иными словами, как работают аллокаторы.
Самый первый доступный ядру алокатор памяти - bootmem(mm/bootmem.c). bootmem алокатор используется только при загрузке ядра для начального выделения физической памяти до того, как подсистема управления памятью станет доступной. bootmem работает очень прямолинейно по алгоритму первый подходящий - ищет первый свободный кусок(страницу) физической памяти и выдаёт. Для представления физической памяти использует bitmap, если 1, то страница занята, если 0, то свободна. Для выделения памяти меньше страницы он записывает PFN последней такой алокации, и следующая маленькая локация будет, если возможно, располагаться на той же физической странице. Алокатор с алгоритмом первый наиболее подходящий, не сильно страдает от фрагментации, но из-за использования bitmap крайне медленный.
/include/linux/bootmem.h
/*
* node_bootmem_map is a map pointer - the bits represent all physical
* memory pages (including holes) on the node.
*/
typedef struct bootmem_data {
unsigned long node_min_pfn;
unsigned long node_low_pfn;
void *node_bootmem_map;
unsigned long last_end_off;
unsigned long hint_idx;
struct list_head list;
} bootmem_data_t;После начальной загрузки и инициализации памяти ядру становятся доступны другие аллокаторы:
---------------
| kmalloc |
------------------------
| kmemcache | vmalloc|
------------------------
| buddy |
------------------------
Buddy - аллокатор смежных страничных кадров, а не линейных страниц, так как для некоторых задач, таких как DMA нужны именно смежные физические страницы, потому что DMA-устройства работают с памятью напрямую. Ещё одной причиной такого подхода является то, что это позволяет не трогать таблицы страниц ядра, что ускоряет работу с памятью. Проблема аллокаторов смежных страниц - внешняя фрагментация, потому в buddy аллокаторе в Linux применяется стандартный подход - разбиение всех доступных страничных кадров на списки по степени двойки: 1, 2, 4, 8, 16, …, 1024. 1024*4096 = 4МВ. Физический адрес первого страничного кадра в блоке кратен размеру группы. Алгоритм работы: хотим выделить 256 кадров. Аллокатор проверит в списке 256, если нет, заглянет в 512, если есть возьмёт 256 кадров, а оставшиеся поместит в список 256. Если и в 512 нет, то проверяет в 1024, если есть, то возвращает 256 кадров запросившему, а оставшиеся 768 разобьёт по двум спискам 512 и 256, если и в 1024 нет, то сигналит об ошибке. У системы buddy есть глобальный объект, хранящий дескрипторы всех доступных кадров, а на каждом отдельном процессоре есть свои локальные списки доступных кадров, если в локальных списках закончилась память, то он подтягивает из глобального и наоборот возвращает если в локальных они свободны. У каждой зоны свой собственный buddy аллокатор. Для работы с buddy аллокатором необходимо использовать функции alloc_page/__rmqueue()(mm/page_alloc.c) - выделение, __free_pages()- освобождение. При работе с этими функциями необходимо отключать прерывания и брать спин блокировку zone->lock.
- Быстрее bootmem(не использует bitmap).
- Можно выделять несколько страничных кадров подряд.
- Нельзя выделить меньше страничного кадра, всегда выделяет >= PAGESIZE.
- Выделяет только идущие по очереди в физической памяти, что всё равно приводит к фрагментации.
У работы со смежными физическими областями есть свои плюсы в виде быстрой работы с памятью, однако и минусы в виде внешней фрагментации. В Linux есть возможность работать с несмежными областями физической памяти, к которым можно обращаться через смежные области линейного пространства. Начало области линейного пространства, где отображаются несмежные области физического, можно получить из макроса VMALLOC_START, конец - VMALLOC_END. Каждая несмежная область памяти описывается структурой(include/linux/vmalloc.h)
struct vm_struct {
struct vm_struct *next; // <- список
void *addr; // линейный адрес первой ячейки
unsigned long size; // size + 4096(окно безопасности между несмежными областями)
unsigned long flags; // тип памяти, отображаемой несметной области
struct page **pages;
unsigned int nr_pages;
phys_addr_t phys_addr;
const void *caller;
};Выделение страниц производится функцией void *vmalloc(unsigned long size) (mm/vmalloc.c). size - размер запрашиваемой области. Выделяет память кратно странице, потому первым делом округляет size до кратного странице размера. Он выдаёт последовательные страницы, но уже в виртуальном адресном пространстве. vmalloc берёт физические страницы у buddy по страничному кадру. Освобождать память можно с помощью vfree(). Минус заключается в том, что наступает фрагментация, но уже в виртуальном памяти, плюс появляется необходимость обращаться в таблицы страниц, что долго. Потому vmalloc редко вызывают. Его применяют для модулей, буферы ввода /вывода, сетевого экрана,отображение верхней памяти.
Очевидно, что для работы с маленькими областями памяти произвольной длины не buddy, не vmalloc не подходят, из-за их расточительности. Потому в Linux есть ещё одна система памяти - kmemcache, которая позволяет выделять память под небольшие объекты в пределах страничного кадра. Однако тут надо быть осторожнее, так как может возникнуть проблема внутренней фрагментации. Вообще говоря под kmemcache скрывается аде целых 3 системы: SLAB/SLUB/SLOB. Суть этих систем достаточно похожа, но имеются и существенные отличия:
- SLOB - для встраиваемых подсистем, отсюда следует то, что он использует минимум памяти и показывает низкую производительность, так же страдает от внутренней фрагментации.
- SLAB - был введён в солярисе и изначально был только он, но системы становились большими и SLAB стал себя плохо показывать в системах с большим количеством процессоров.
- SLUB - эволюция SLAB - быстрее, выше, сильнее.
Сначала опишем интерфейс SLAB. Slab базируется на нескольких наблюдениях. Во-первых, ядро часто запрашивает и возвращает области памяти одного и того же размера для различных структур, потому для ускорения можно не освобождать, а оставлять их в кеше для себя, а потом переиспользовать, что сэкономит время. Лучше как можно реже обращаться к buddy, так как каждое обращение к нему загрязняет аппаратный кэш. Так же можно создать объекты размером не кратным двойки, если к ним происходит частое обращение, что ещё может улучшить работу аппаратного кэша. Slab группирует объекты в кэш. Каждый кэш - хранилище объектов одного типа( размера). Кеш имеет несколько slab-списков: с полностью свободными объектами, частично свободными и полностью занятыми. Кэш работает с гранулярностью 1-2-4-8 страниц.
kmem_cache slab - список
________
| |——————> | | - | | - | | - полностью свободны
| |
| |
| |——————> | | - | | - | | - частично свободны
| |
| |——————> | | - | | - | | - полностью заняты
| |
Для того чтобы пользоваться struct kmem_cache надо получить хэндл через функцию:
struct kmem_cache *kmem_cache_create(size);size - фикцисрованный размер, который мы потом хотим получать. После можно выделить память с помощью:
void kmem_cache_alloc(kc, flags);И освобождать:
void kmem_cache_free(kc);Уничтожить кэш можно с помощью:
kmem_cache_destroy()Всю информацию по SLAB можно получить в /proc/slabinfo.
Под SLAB тоже нужно было выделять память, дескриптор описывающий SLAB мог лежать: У другого kmem_cache - off-slab. Дескриптор slab может лежать в голове страницы, которую выдаёт buddy - on-slab. Но buddy выдавал нам страницу и struct page, который по размеру совпадал со slab -> struct page можно забрать у системы и использовать его под slab. Потому появился slub. Минус SLAB allocator - выделяет объекты константного размера, хотя нам не всегда известен размер объекта под который нужно выделить память.
Более высокого уровня аллокатор kmalloc/kfree(include/linux/slab.h). Он обращается к необходимому kmem_cache, получая его через статическую функцию kmalloc_index(size). В статической функции, если размер будет известен на этапе компиляции, то вызов функции будет компилятором заменён на итоговый индекс.:
static __always_inline int kmalloc_index(size_t size)
{
...
if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
return 1;
if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
return 2;
if (size <= 8)
return 3;
...
}- 0 = zero alloc
- 1 = 65 .. 96 bytes
- 2 = 129 .. 192 bytes
- n = (2$^{n-1}$+1) .. 2$^n$ //todo
Кэши размером 0/ 8/ 16/ 32/ 64/ 96/ 128/ 192 /256 …/2$^{26}$. 96 и 192 - эвристически вычисленные часто запрашиваемые значения.
Все аллокаторы работаю с группой флагов gfp_flags(include/linux/gfp.h) - get free page flags. Изначально они появились в buddy потом просочись на уровни повыше.
Типы флагов:
- Откуда выделять: __GFP_DMA (Get Free Page), __GFP_HIGHMEM, __GFP_DMA32. По умолчанию система старается выделять память в ZONE_NORMAL.
- Поведение при нехватке памяти - контекст, в котором мы работаем по сути.
Если памяти нет, то её нужно найти, например:
- в дисковом кэше - требуется брать мютекс;
- ядерном кэше - требуется брать мютекс;
- освободить грязный дисковый кэш - требуется брать мютекс и обращаться к файловой системе и блокам;
- swap требуется брать мютекс и обращаться к блокам;
- kill кого-нибудь; Пример, __GFP_ATOMIC - ничего нельзя делать и buddy вернёт NULL. __GFP_NOFS - используются кэшами и буферами, чтобы быть уверенными, что их рекурсивно не позовут. __GFP_NOIO.
- Всё остальное - __GFP_ZERO - память которую выдаст аллокатор должен быть забит нулями. __GFP_TEMPORARY - мне нужно выделить страницу подержу её недолго и верну. (пути) GFP_NORETRY GFP_NOFAIL