Память как у пингвина: Работа памяти в Linux
Начнем издалека. В спецификации любого компьютера и в частности сервера непременно числится надпись «N гигабайт оперативной памяти» — именно столько в его распоряжении находится физической памяти.
Задача распределения доступных ресурсов между исполняемым программным обеспечением, в том числе и физической памяти, лежит на плечах операционной системы, в нашем случае Linux. Для обеспечения иллюзии полной независимости, она предоставляет каждой из программ свое независимое виртуальное адресное пространство и низкоуровневый интерфейс работы с ним. Это избавляет их от необходимости знать друг о друге, размере доступной физической памяти и текущей её занятости. Адреса в виртуальном пространстве процессов называют логическими.
Для отслеживания соответствия между физической и виртуальной памятью ядро Linux использует иерархический набор структур данных в своей служебной области физической памяти (только оно работает с ней напрямую), а также специализированные аппаратные контуры, которые в совокупности называют MMU.
Следить за каждым байтом памяти в отдельности было бы накладно, по-этому ядро оперирует достаточно большими блоками памяти — страницами, типовой размер которых составляет 4 килобайта.
Также стоит упомянуть, что на аппаратном уровне как правило есть поддержка дополнительного уровня абстракции в виде «сегментов» оперативной памяти, с помощью которых можно разделять программы на части. В отличии от других операционных систем, в Linux она практически не используется — логический адрес всегда совпадает с линейным (адресом внутри сегмента, которые сконфигурированы фиксированным образом).
Как многие знают, существует виртуальная память — это то, что создаёт операционная система для работы программ с ней. Это сама ОЗУ и все SWAP разделы. Выделяемая память процессу может быть либо резидентная, либо виртуальная. В листинге ниже видно у процессов резидентную (rss) и виртуальную память (vsz). Эта память отображается в KB.
Виртуальная память (VSZ) — это память которую выделили процессу, но не факт что он успел в эту память что-то записать.
Резидентная память (RSS) — это память которую процесс занял, то есть что-то сохранил в виртуальную память. Именно резидентная память показывает сколько процесс потребляет физической памяти.
Приложение может запросить много памяти, а использовать малую её часть. Поэтому почти всегда rss меньше чем vsz.
Раздел подкачки (SWAP) — это раздел на жестком диске, куда помещаются:
Если какие-то данные из rss сбрасываются в swap то rss освобождается, а vsz нет. От сюда следует что данные процесса, которые лежат в swap, входят в виртуальную память этого процесса.
Linux умеет работать не только с разделом подкачки, но и с файлом подкачки. То есть данные из резидентной памяти могут сбрасываться в специальный файл, который лежит на жёстком диске.
И файл и раздел подкачки имеет тот же самый формат что и оперативная память. То есть данные в оперативной памяти хранятся в виде страниц, и в подкачку сбрасываются в виде таких же страниц.
Посмотреть более подробно на используемую память процесса поможет файл /proc/
Кластеры — это блоки на уровне файловой системы, с которыми происходит работа. Запись и чтение происходит блоками. Размер по умолчанию — 4KB.
Вся виртуальная память состоит из страниц. Страницы — это набор ячеек памяти в виртуальном пространстве, которому сопоставлена реальная память на диске. Страницы бывают обычные — 4 килобайта и huge page — блоки по 2 мегабайтам, либо гигабайту. Используется, когда происходит работа с большими данными, например базами данных (также структура таблицы страниц становится оптимальнее).
Страницы бывают грязные и чистые. Чистые — не подвергались изменению, грязные — подвергались. Например, вы загрузили библиотеку — это чистая страница, т.к. ты её не изменял и она может быть спокойно забыта. А если загружен файл, который был изменен после загрузки — то он становится грязным. Его нужно записать на диск, прежде чем забывать.
Больше всего в системе память занимает страничный кеш (Page Cache). Вся работа с файлами на диске (запись или чтение) идет через Page Cache. Запись в linux всегда быстрее чтения, так как запись вначале идет в Page Cache, а затем сбрасывается на диск. А при чтении ядро ищет файл в Page Cache, и если не находит читает файл с диска. Узнать сколько сейчас система тратит памяти на Page Cache можно выполнив команду free:
$ free -h
total used free shared buff/cache available
Mem: 976Mi 74Mi 764Mi 0,0Ki 137Mi 765Mi
Swap: 974Mi 0B 974Mi
Страничный кеш показан в колонке buff/cache. Как мы видим у нас занято 137MB страничным кешем. Хотя тут не только Page Cache, тут также находится Buffer, который тоже связан с файлами на диске.
Посмотреть информацию по Page Cache и Buffer отдельно можно в файле /proc/meminfo:
egrep "^Cach|^Buff" /proc/meminfo
Buffers: 16012 kB
Cached: 101220 kB
При создании нового файла, запись идет в cache, а страницы памяти для этого файла помечаются как грязные (dirty). Раз в какой-то промежуток времени грязные страницы сбрасываются на диск, и если таких страниц будет слишком много, то они тоже сбросятся на диск. Управлять этим можно через параметры sysctl (sudo nano /etc/sysctl.conf):
vm.dirty_expire_centisecs — интервал сброса грязных страниц на диск в сотых долях секунд (100 = 1с);
vm.dirty_ratio — объем оперативной памяти в процентах который может быть выделен под Page Cache.
$ sudo sysctl vm.dirty_expire_centisecs
vm.dirty_expire_centisecs = 3000
$ sudo sysctl vm.dirty_ratio
vm.dirty_ratio = 20Существует утилита — vmtouch, она может показать какой процент указанного файла находится в страничном кеше. Но её нужно скачивать из git и устанавливать:
$ sudo apt update
$ sudo apt install git make gcc
$ git clone https://github.com/hoytech/vmtouch.git
$ cd vmtouch
$ make
$ sudo make install
$ vmtouch /etc/passwd
Files: 1
Directories: 0
Resident Pages: 1/1 4K/4K 100%
Elapsed: 6.3e-05 seconds
Видно что весь файл /etc/passwd сейчас находится в Page Cache (Resident Pages).
Узнать объем грязных страниц можно из файла /proc/meminfo. А команда sync записывает грязные страницы на диск:
$ grep Dirty /proc/meminfo
Dirty: 24 kB
# sync
$ grep Dirty /proc/meminfo
Dirty: 0 kB
HugePages
Поговорим немного про большие страницы HugePages. Особенности таких страниц:
размер таких страниц равен 2MB;
приложение должно уметь работать с такими страницами;
эти страницы никогда не сбрасываются в swap.
Выделить под HugePages страницы можно параметром sysctl:
vm.nr_hugepages = <число страниц> (так если указать 1024 то выделится 1024×2МБ=2048MB).
vm.hugetlb_shm_group =
— только члены этой группы могут использовать HugePages.
После исправления /etc/sysctl.conf нужно перезагрузиться и посмотреть на результат в файле /proc/meminfo:
$ egrep "HugePages_T|HugePages_F" /proc/meminfo
HugePages_Total: 1024
HugePages_Free: 1024
Выделено 1024 страниц и все они свободны. При этом у нас 2GB памяти не сможет использоваться обычными приложениями, которые не умеют работать с HugePages. Поэтому не всегда нужно выделять HugePages.
Методы управления подсистемой памяти
swap
С файловой памятью всё просто: если данные в ней не менялись, то для её вытеснения делать особо ничего не нужно — просто перетираешь, а затем всегда можно восстановить из файловой системы.
С анонимной памятью такой трюк не работает: ей не соответствует никакой файл, по-этому чтобы данные не пропали безвозвратно, их нужно положить куда-то ещё. Для этого можно использовать так называемый «swap» раздел или файл. Можно, но на практике не нужно. Если swap выключен, то анонимная память становится невытесняемой, что делает время обращения к ней предсказуемым.
Может показаться минусом выключенного swap, что, например, если у приложения утекает память, то оно будет гарантированно зря держать физическую память (утекшая не сможет быть вытеснена). Но на подобные вещи скорее стоит смотреть с той точки зрения, что это наоборот поможет раньше обнаружить и устранить ошибку.
mlock
По-умолчанию вся файловая память является вытесняемой, но ядро Linux предоставляет возможность запрещать её вытеснение с точностью не только до файлов, но и до страниц внутри файла.
Для этого используется системный вызов mlock на области виртуальной памяти, полученной с помощью mmap. Если спускаться до уровня системных вызовов не хочется, рекомендую посмотреть в сторону консольной утилиты vmtouch, которая делает ровно то же самое, но снаружи относительно приложения.
Несколько примеров, когда это может быть целесообразно:
У приложения большой исполняемый файл с большим количеством ветвлений, некоторые из которых срабатывают редко, но регулярно. Такого стоит избегать и по другим причинам, но если иначе никак, то чтобы не ждать лишнего на этих редких ветках кода — можно запретить им вытесняться.
Индексы в базах данных часто физически представляют собой именно файл, с которым работают через
mmap, аmlockнужен чтобы минимизировать задержки и число операций ввода-вывода на и без того нагруженном диске (-ах).Приложение использует какой-то статический словарь, например с соответствием подсетей IP-адресов и стран, к которым они относятся. Вдвойне актуально, если на одном сервере запущено несколько процессов, работающих с этим словарем.
OOM killer
Перестаравшись с невытесняемой памятью не трудно загнать операционную систему в ситуацию, когда физическая память кончилась, а вытеснять ничего нельзя. Безысходной она выглядит лишь на первый взгляд: вместо вытеснения память можно освободить.
Происходит это достаточно радикальными методами: послуживший названием данного раздела механизм выбирает по определенному алгоритму процесс, которым наиболее целесообразно в текущий момент пожертвовать — с остановкой процесса освобождается использовавшаяся им память, которую можно перераспределить между выжившими. Основной критерий для выбора: текущее потребление физической памяти и других ресурсов, плюс есть возможность вмешаться и вручную пометить процессы как более или менее ценные, а также вовсе исключить из рассмотрения. Если отключить OOM killer полностью, то системе в случае полного дефицита ничего не останется, как перезагрузиться.
cgroups
По-умолчанию все пользовательские процессы наравне претендуют на почти всю физически доступную память в рамках одного сервера. Это поведение редко является приемлемым. Даже если сервер условно-однозадачный, например только отдает статические файлы по HTTP с помощью nginx, всегда есть какие-то служебные процессы вроде syslog или какой-то временной команды, запущенной человеком. Если же на сервере одновременно работает несколько production процессов, например, популярный вариант — подсадить к веб-серверу memcached, крайне желательно, чтобы они не могли начать «воевать» друг с другом за память в случае её дефицита.
Для изоляции важных процессов в современных ядрах существует механизм cgroups, c его помощью можно разделить процессы на логические группы и статически сконфигурировать для каждой из групп сколько физической памяти может быть ей выделено. После чего для каждой группы создается своя почти независимая подсистема памяти, со своим отслеживанием вытеснения, OOM killer и прочими радостями.
Механизм cgroups намного обширнее, чем просто контроль за потреблением памяти, с его помощью можно распределять вычислительные ресурсы, «прибивать» группы к ядрам процессора, ограничивать ввод-вывод и многое другое. Сами группы могут быть организованы в иерархию и вообще на основе cgroups работают многие системы «легкой» виртуализации и нынче модные Docker-контейнеры.
Но на мой взгляд именно контроль за потреблением памяти — самый необходимый минимум, который определенно стоит настроить, остальное уже по желанию/необходимости.
NUMA
В многопроцессорных системах не вся память одинакова. Если на материнской плате предусмотрено N процессоров (например, 2 или 4), то как правило все слоты для оперативной памяти физически разделены на N групп так, что каждая из них располагается ближе к соответствующему ей процессору — такую схему называют NUMA.
Таким образом, каждый процессор может обращаться к определенной 1/N части физической памяти быстрее (примерно раза в полтора), чем к оставшимся (N-1)/N.
Ядро Linux самостоятельно умеет это всё определять и по-умолчанию достаточно разумным образом учитывать при планировании выполнения процессоров и выделении им памяти. Посмотреть как это все выглядит и подкорректировать можно с помощью утилиты numactl и ряда доступных системных вызовов, в частности get_mempolicy/set_mempolicy.
Работа с памятью в Linux
Подсистема управления памятью одна из самых важных. От её быстродействия и от того насколько эффективно она распоряжается оперативной памятью зависят все остальные подсистемы.
При рассмотрении подсистемы памяти важно знать и понимать, какие типы памяти есть и про какие говорят. Далее будут рассматриваться два типа памяти:
Физическая — оперативная память машины.
Линейная — виртуальная память, она может быть больше, чем реально физической памяти у вас есть.
Вся физическая память разбита на страничные кадры. Размер страничного кадра — платформозависимая величина, для 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
Самый первый доступный ядру алокатор памяти — 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
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.
Плюсы buddy:
Минусы buddy:
Нельзя выделить меньше страничного кадра, всегда выделяет >= PAGESIZE.
Выделяет только идущие по очереди в физической памяти, что всё равно приводит к фрагментации.
Vmalloc
У работы со смежными физическими областями есть свои плюсы в виде быстрой работы с памятью, однако и минусы в виде внешней фрагментации. В 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 редко вызывают. Его применяют для модулей, буферы ввода /вывода, сетевого экрана, отображение верхней памяти.
Kmemcache
Очевидно, что для работы с маленькими областями памяти произвольной длины не 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 - список
________
| |——————> | | - | | - | | - полностью свободны
| |
| |
| |——————> | | - | | - | | - частично свободны
| |
| |——————> | | - | | - | | - полностью заняты
| |
(include/linux/slub_def.h)
Для того чтобы пользоваться 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/ 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
User memory management
Запросы ядра на выделение памяти: alloc_pages () и kmalloc (), приводят к немедленному выделению памяти, если могут быть удовлетворены. Это оправдано, потому что:
Ядро — самый приоритетный компонент системы, его запросы критические.
Ядро себе доверяет, предполагается, что в ядре нет ошибок.
Для процессов, работающих в режиме пользователя, всё иначе:
Запросы процесса на память можно отложить.
В коде пользователя могут быть ошибки, потому нужно быть готовым к обработке ошибок. Когда процесс запрашивает память, он получает не новые страничные кадры, а право обращаться к новым линейным адресам.
Адресное пространство процесса
Адресное пространство процесса — линейные адреса, к которым процесс может обращаться. Ядро может динамически изменять адресное пространство процесса с помощью добавления или удаления областей памяти (vm_area_struct).
Процесс может получить новые области памяти, например, с помощью вызывов: malloc (), calloc (), mmap (), brk (), shmget () + shmat (), posix_memalign (), mmap () и т.д. В основе всех этих вызовов лежит void *mmap (void *addr, size_t length, int prot, int flags, int fd, off_t offset); :
Дескриптор памяти
Вся информация относительно адресного пространства процесса хранится в mm_struct (дескриптор памяти), на который указывает поле mm в task_struct.
task_struct
_________
| … | mm_struct
--------- _________
| mm | -> | … |
--------- ---------
| … | | mmap | -> vm_area_struct * (VMA) – список двунап.
--------- ---------
| pgd | - указатель на глобальный каталог страниц
---------
Описание структур mm_struct и vm_area_struct монжо найти в /include/linux/mm_types.h.
Область памяти
struct vm_area_struct {
/* The first cache line has the info for VMA tree walking. */
unsigned long vm_start; /* Our start address within vm_mm. */
unsigned long vm_end; /* The first byte after our end address
within vm_mm. */
/* linked list of VM areas per task, sorted by address */
struct vm_area_struct *vm_next, *vm_prev;
...................
struct rb_node vm_rb;
………..
/* Function pointers to deal with this struct. */
const struct vm_operations_struct *vm_ops;
}У области памяти есть два поля vm_start и vm_end, обозначающие соответственно адрес начала и первого бита после конца выделенной области. Если применить mmap () с одинаковыми аргументами, то ядро не будет создавать новый VMA, а просто изменит vm_end уже существующего.
Все области памяти объеденены в двунаправленный список, где они упорядочены по возрастанию адресов. Для того чтобы не приходилось пробегаться по всему списку при выделении, возвращении памяти или поиску VMA, которому принадлежит адрес, все VMA так же объединены в красно-чёрное дерево.
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */
struct rb_root {
struct rb_node *rb_node;
};mm_struct → pgd — указатель на глобальный каталог страниц каждого процесса. На x86 при переключении процесса mm_struct → pgd помещается в cr3. Изменение cr3 в свою очередь приводит к сбросу TLB. Однако, у двух task_struct может быть один и тот же mm, например, у двух потоков, тогда изменения cr3 не будет, что существенно ускоряет работу с памятью.
Помимо потоков переключение cr3 так же не происходит для kernel_thread. Для них просто нет необходимости в областях памяти, так как они всегда обращаются к фиксированным линейным адресам выше TASK_SIZE = PAGE_OFFSET = 0xffff880000000000 (x86_64). Потому собственный mm kernel_thread в task_struct просто не нужен, он равен NULL. Зато в task_struct есть active_mm, равный active_mm вытесненного процесса.
Ещё одним интересным полем в VMA является vm_ops, оно определяет операции, которые можно выполнять для конкретной области памяти.
Работа с областями памяти
Описание функций:
do_mmap () (/mm/mmap.c) — выделение новой области памяти
do_munmap () (/mm/mmap.c) — возвращение области памяти
find_vma ()(/mm/mmap.c) — поиск области ближайшей к данному адресу
find_vma_intersection () (/include/linux/mm.h) — поиск области, содержащей адрес.
get_unmapped_area () (/mm/mmap.c) — поиск свободного интервала
insert_vm_struct () (/mm/mmap.c) — внесение области в список дескрипторов
Выделение интервала линейных адресов
Линейные адреса, которые выделяются, могут быть связаны с файлом (FILE) или нет (ANON). При этом, процесс, который запрашивает память, может владеть ими совместно с кем-то (MAP_SHARED) или уникально (MAP_PRIVATE).
do_mmap
FILE | ANON | |
|---|---|---|
MAP_SHARED | vma→file (get_page) | файл на tmpfs (shmat) |
MAP_PRIVATE | library (COW) | HIGHMEM, ZERO (buddy) |
Отложенное выделение
Как было сказано выше, запросы пользовательского процесса на память можно отложить до момента, когда память действительно понадобиться. Для этого используется механизм обработки исключения page fault, сигнализирующего об отсутствие страницы.
В x86 каждая запись в таблице страниц выровнена по 4096(2^12), потому первые 12 бит несут служебную информацию относительно страницы, например:
0 бит — P (Present) Flag
1 бит — R/W (Read/Write) Flag
2 бит — U/S (User/Supervisor) Flag
Таким образом, если выставить P бит в ноль, то при обращении к данной области памяти будет генерироваться исключение. При генерировании исключения адрес, который его вызвал, сохранится в регистре cr2. Итоговый алгоритм можно представить в виде диаграммы.
page fault
\/
Принадлежит ли адрес пространству процесса?
Да / Нет \
\/ \/
Соответствуют ли права доступа? Исключение возникло в режиме пользователя?
Да / Нет\ Да / Нет \
\/ \/ \/ \/
Выделить новый Послать SIGSEGV Ошибка ядра: уничтожить процесс
страничный кадр
Если обращение происходит рядом со stack VMA — область созданная с флагом MAP_GROWDOWN, то происходит расширение области.
Заключение
Вся информация взята из открытых источников.
Документация физической памяти в ядре Linux
Документация на русском «Управлению памятью в Linux»
