ОС. Работа с памятью в ядре

Лекция 2

Ограничения

• Рассматриваем Unix-like систему, т. е. интерфейс между ядром и процессом состоит из:
• brk и sbrk
• mmap/unmap
• Рассматриваем платформу с аппаратной поддержкой paging
• Мы оставляем в стороне сложные NUMA архитектуры
• Примеры из ядра Linux
• с незначительными изменениями применимы и к freebsd
• возможно и другим Unix-like системам

Представление frame-ов в ядре

• Опишем структуру, которая представляет страницу
• различные флаги
• ссылка на владельца
• в Linux для этого есть struct page
• Просто массив структур
• есть простое однозначное отображение между индексом в массиве и frame-ом
• в Linux называется mem_map, инициализируется функцией free_area_init_nodes (впрочем проследить это по коду весьма не просто: http://lxr.free-electrons.com/source/arch/x86/mm/init.c#L715)
• Все frame-ы разделены на зоны:
• ZONE_NORMAL
• ZONE_DMA
• ZONE_HIGH

Аллокация frame-ов

• Всем нужны frame-ы
• вся память поделена на frame-ы
• эффективная аллокация frame-ов критична для производительности
• Требования к алгоритму аллокации
• часто страницы аллоцируются группами - не хочется аллоцировать frame-ы по одному
• само собой быстрый
• чем проще тем лучше - главный инженерный принцип
• Возможные варианты:
• связать все свободные страницы в список - дешево, сердито и медленно
• битовая карта - дешево, сердито и неудобно.
• Buddy Allocator

Buddy Allocator, определения

• Будем аллоцировать только блоки по 2^k frame-ов
• k - будем называть порядком блока
• блок идентифицируется первым frame-ом в блоке
• в каждой структуре для frame-а храним признак занятости блока, в котором соответствующий frame является первым, а также порядок блока
• свободные блоки каждого уровня связаны в списки
• Блоки страниц порядка k объединены попарно (buddies)
• frame-ы, в индексе которых k-1 наименее значимых бит 0 являются первыми в блоке порядка k
• блоки соседние, если все биты индексов их первых frame-ов кроме k-ого совпадают
• индекс первого frame-а соседнего блока легко находится по формуле:

buddy = pfn ^ (1 << k)

То же самое, но в картинках

Аллокация

• Вход: k - порядок блока
• Выход: индекс первого frame-а блока
• Алгоритм:
• идем по спискам свободных блоков начиная от списка для блоков порядка k
• если нашли не пустой список, достаем из него блок, назовем его текущим и путь его порядок будет n
• пока n > k, делим текущий блок на два блока порядка n - 1: один из них добавляем в список свободных блоков порядка n - 1, второй делаем текущим блоком
• устанавливаем в первом фрейме текущего блока признак занятости
• возвращаем индекс первого frame-а текущего блока

Освобождение

• Вход: индекс первого frame-а блока и его порядок
• Выход: отсутствует, но блок будет освобожден
• Алгоритм:
• обозначим входной блок как текущий
• найдем парный блок, если он есть
• пока парный блок есть, для него не установлен признак занятости и его порядок совпадает с порядком текущего блока
• удаляем парный блок из списка свободных блоков
• объединяем парный и текущий блоки, назовем это блок текущим
• найдем парный блок для текущего блока
• устанавливаем для текущего блока правильный порядок
• снимаем для текущего блока бит занятости
• добавляем текущий блок в список свободных блоков соответствующего порядка

Сложность Buddy Allocator-а

• Различных порядков не может быть очень много
• если вам нужно 64 бита на адрес и вы используете страницы по 4КБ, то достаточно 52 списков
• Вставка и удаление из списка O(1)
• Проверка порядка и занятости O(1)
• Аллокация и освобождение занимают по log(N), где N - количество frame-ов, но фактически O(1)
• на практике нет необходимости выделять блоки огромного размера (т. е. даже 52 списков не будет):
• в Linux максимальный порядок 11, если не задан явно другой

SLUB/SLOB/SLAB

• Buddy Allocator очень хорош, но гранулярность слишком большая
• узлы списков, деревьев и других связанных структур
• служебные структуры и различные дескрипторы
• Аллокатор блоков фиксированного размера
• если все блоки имеют одинаковый размер жизнь проще
• блоки одного типа можно повторно не инициализировать
• имея аллокатор блоков фиксированного размера можно построить аллокатор блоков произвольного размера (аналог malloc)
• cache coloring
• SLUB/SLOB/SLAB - различные реализации кеширующего аллокатора
• оригинальная статья: https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a

Память процесса

Память процесса, продолжение

• Память процесса разбита на сегменты
• сегмент, как правило, представляет непрерывный диапазон виртуальных адресов
• сегмент, как правило растет только в одну сторону, либо не изменяется
• mmap area, как правило, особый случай
• В Linux для каждого сегмента заводится структура vm_area_struct
• хранит виртуальный адрес начала и конца региона
• различные флаги (READ/WRITE/EXECUTE)
• массивы страниц, соответствующих этому региону
• sbrk/brk - просто аллокация/освобождение страниц и добавление их в соответсвующий vm_area_struct
• mmap/munmap - создание нового vm_area_struct

Q&A