4 | Содержание
| 6
Управление памятью.
Используемый тип управления: Страничная организация памяти, плоская
модель (с fs=0 и особой трактовкой сегментного регистра gs). Нижние 2 Гб
виртуальной памяти (диапазон адресов 0-0x7FFFFFFF включительно) отводятся
приложению (и свои для каждого процесса), верхние 2 Гб - для системы (и
разделяются между всеми процессами). Программы грузятся по нулевому адресу.
GDT описана в [data32.inc, gdts], LDT не используется. В регистр gs
загружается селектор, описывающий сегмент на 8 Мб, описыващий область
памяти, выделяемую для работы с графическими данными (упоминавшуюся при
описании работы системы с видеокартой), выводимыми на экран - для
vesa2-видеорежимов c LFB туда просто маппится этот LFB, для ega/vga и
cga-режимов это специально выделяемая при загрузке память, а для
vesa1.2-режимов селектор имеет нулевую базу.
Принцип отображения адресного пространства: Стандартным образом,
через таблицы страниц. Файла подкачки нет. Для преобразования адресов
выполнены следующие утверждения:
- преобразование нетождественно;
- преобразование нижних 2 Гб зависит от текущего процесса, преобразование
верхних 2 Гб не меняется при переключении задач;
- преобразование меняется на время вызовов APM и V86;
- инициализирует системную таблицу страниц процедура init_mem из init.inc;
- начальный кусок системных адресов [OS_BASE, OS_BASE+a), где OS_BASE =
0x80000000 (const.inc), маппится на начало физической памяти [0,a) "почти
тривиально" - вычитанием OS_BASE;
- длина системного куска a = HEAP_BASE+HEAP_MIN_SIZE-OS_BASE;
- первые 4 Мб (куда входит само ядро и часть системных таблиц) маппятся
одной "длинной" страницей;
- размер остальных страниц - по 4Кб;
- Для 4К-страниц действует двухтабличное PDE-PTE преобразование линейных
адресов в физические:
- старшие 10 бит линейного адреса указывают номер элемента в каталоге
таблиц (PDE), расположенному в статической области ядра по линейному
адресу sys_pgdir;
- этот элемент содержит физический адрес соответствующей таблицы страниц
(PTE), элементы которого адресуются битами 21..12 линейного адреса;
- обращаться к таблицам страниц можно только из ring-0, по линейным
адресам [0xFDC00000, 0xFE000000) (4 Мб, начиная с page_tabs из const.inc);
- в принципе, таблицы страниц PTE - это динамические структуры,
создаваемые и удаляемые менеджером памяти по мере необходимости;
- однако, для линейных адресов [OS_BASE, OS_BASE+b) действует "плоское"
отображение PDE -> PTE, очень сильно упрощающее код самого менеджера
памяти. Длина этого диапазона b равна размеру доступной физической памяти,
но не может превышать 2Гб. Таблицы страниц для этого диапазона образуют
статический массив длиной 4К x (b>>22 - 1) в системной области; первая
таблица этого массива расположена после (sys_pgmap + (b>>25));
- элемент таблицы страниц с установленным битом присутствия представляет
страницу в памяти;
- элемент таблицы страниц со сброшенным битом присутствия, но
установленным 1-м битом (маска 2) соответствует ситуации, когда страница
должна быть выделена при первом обращении к ней (обработчик #PF при
обнаружении исключения из-за обращения к такой странице выделяет страницу
физической памяти, маппит по соответствующему линейному адресу и возвращает
управление);
- таблицу страниц для процесса создаёт функция [core/taskman.inc|
create_app_space] и удаляет [core/taskman.inc|destroy_app_space];
- схема работы create_app_space:
- на вход получает размер памяти, указанный в заголовке бинарника
([app_size]), и сам загруженный в память ядра бинарник (указатель
[img_base] + размер [img_size]);
- захватывает мьютекс pg_data.pg_mutex, контролирующий запись в таблицы
страниц;
- проверяет, достаточно ли свободной физической памяти для приложения;
если недостаточно, возвращает ошибку;
- выделяет новую страницу [dir_addr] под PDE, маппит её по линейному
адресу [tmp_task_pdir] (чтобы к ней можно было обращаться; место в
системном адресном пространстве для этой цели было зарезервировано при
загрузке), обнуляет user-mode указатели на PTE и копирует kernel-mode
часть; заменяет вход PDE, соответствующий page_tabs, указателем на себя
([dir_addr]);
- устанавливает созданную PDE как текущую таблицу страниц (дальнейшие
махинации с page_tabs пойдут внутрь [dir_addr], создаваемой таблицы);
- создаёт нужное (для описания всей памяти [app_size]) количество
страниц PTE, заносит указатели на них в PDE;
- маппит в адресное пространство нового процесса загруженный бинарник;
- если при компиляции ядра константа GREEDY_KERNEL ненулевая, то
помечает оставшиеся страницы в памяти приложения значением 2 (упомянутом
ранее - физическую память выделит обработчик #PF, когда она будет нужна);
а если нулевая - выделяет физическую память под все остальные страницы;
- размаппит страницу [dir_addr] из линейного адреса [tmp_task_pdir];
- возвращается; текущая таблица страниц соответствует адресному
пространству нового процесса.
- схема работы destroy_app_space:
- захватывает мьютекс pg_data.pg_mutex;
- выясняет, является ли текущий поток последним в своём процессе
(проходит по списку потоков в поисках потоков с тем же адресным
пространством); если нет - освобождает мьютекс и выходит;
- маппит таблицу PDE по линейному адресу [tmp_task_pdir], чтобы с ней
можно было работать;
- проходит по всем user-mode элементам (элементы PDE - указатели на
PTE), каждую выделенную страницу с PTE маппит по линейному адресу
[tmp_task_ptab] (место в адресном пространстве ядра, как и для
[tmp_task_pdir], было зарезервировано при загрузке системы), вызывает
вспомогательную процедуру destroy_page_table (которая в свою очередь
проходит по элементам теперь уже PTE, освобождая все выделенные страницы)
и освобождает саму страницу с PTE;
- освобождает страницу с таблицей PDE;
- размаппит страницы из [tmp_task_ptab] и [tmp_task_pdir];
- освобождает мьютекс pg_data.pg_mutex
При управлении памятью бывают разные задачи.
А. Управление физической памятью.
- Есть функция выделения одной физической страницы [core/memory.inc,
alloc_page],
- функция выделения нескольких физических страниц [core/memory.inc,
alloc_pages], выделяющая связный диапазон, причём кратный 8 страницам,
- функция освобождения ранее выделенной физической страницы
[core/memory.inc, free_page].
Система хранит массив битов, который для каждой физической страницы
описывает, выделена она или свободна, а также вспомогательные переменные:
подсказку [page_start] - нижнюю границу при поиске свободной страницы
(указатель внутри битового массива, относительно которого известно, что все
предшествующие данные забиты единицами, а соответствующие страницы
выделены), указатель [page_end] на конец массива, число свободных страниц
[pg_data.pages_free].
Физические страницы выделяются по принципу first-fit, возвращается первый
подходящий вариант (первая свободная страница либо первый свободный блок
нужной длины).
Б. Управление адресным пространством ядра.
В core/heap.inc есть alloc_kernel_space и free_kernel_space, которые
соответственно выделяют и освобождают непрерывный диапазон в адресном
пространстве ядра.
В. Управление памятью ядра.
>
- Есть функция получения физического адреса по указанному линейному
[core/memory.inc, get_pg_addr],
- функция маппинга указанной физической страницы по указанному линейному
адресу [core/memory.inc, map_page] (стандартное добавление элемента в
таблицу страниц; работает и с user-mode пространством), способная также
размаппить страницу (нулевой элемент таблицы страниц соответствует свободной
линейной странице),
- аналогичная функция для непрерывного блока адресов [core/memory.inc,
commit_pages],
- обратная ей [core/memory.inc, unmap_pages],
- функция [core/memory.inc, release_pages], которая принимает линейный
адрес и размер блока и одновременно размаппит из линейных адресов и
освобождает физические страницы из этого блока.
- а также функция [core/memory.inc, map_io_mem], создающая проекцию
заданного блока физических страниц в адресном пространстве ядра (вызывает
alloc_kernel_space, а потом добавляет в таблицу страниц преобразование
указанных физических адресов на только что выделенные линейные),
- общая функция выделения памяти ядра [core/heap.inc, kernel_alloc],
которая одновременно выделяет место в адресном пространстве ядра, физическую
память, устанавливает соответствие между ними и возвращает линейный адрес
блока. Алгоритм работы: выделяет нужный диапазон линейных адресов
(alloc_kernel_space); если запрошено A*8+B страниц, 0<=B<8, то выделяет
непрерывный блок из A*8 страниц через alloc_pages и маппит по нужным
линейным адресам, а потом B раз выделяет по одной физической странице
(alloc_page) и тоже маппит по нужным адресам,
- обратная ей функция освобождения памяти ядра [core/heap.inc,
kernel_free], основывающаяся на release_pages и free_kernel_space.
Г. Куча ядра для маленьких блоков памяти.
Файл core/malloc.inc предоставляет функции malloc и free, предназначенные
для выделения маленьких блоков памяти (kernel_alloc/kernel_free из
предыдущего пункта работают только с целыми страницами, что может быть
много). Как сказано в комментариях (которым нет причин не верить), всё
основано на коде Doug Lea ftp://gee.cs.oswego.edu/pub/misc/malloc.c . При
загрузке [core/malloc.inc, init_malloc] под кучу выделяется 256 Кб через
kernel_alloc, и malloc/free оперируют исключительно внутри этой области.
Д. Работа с памятью приложений.
Когда-то довольно давно адресное пространство приложения было обязано быть
непрерывным диапазоном, который для приложения начинался с нулевого адреса;
с тех пор в структуре, возвращаемой функцией 9 для
потока, есть поля "адрес процесса в памяти" и "размер используемой памяти"
(точнее, лимит = размер-1). В то время единственной возможностью по
динамическому перераспределению памяти было изменение размера адресного
пространства, и с того времени идёт сисфункция 64,
[core/memory.inc, new_mem_resize]. Которая при уменьшении используемой
памяти проходит по "лишнему" пространству и освобождает выделенные страницы
(free_page), при увеличении сначала выделяет дополнительные страницы под
таблицы PTE (если нужно), а потом проходит по "добавляемому" пространству и
выделяет запрошенные страницы через alloc_page+map_page. Кроме того, в конце
она вызывает вспомогательную функцию update_mem_size, которая проходит по
списку потоков и для всех потоков текущего процесса обновляет поле с
размером памяти в структуре потока.
Но ясно, что при таком подходе далеко не всегда можно освободить память,
которая стала ненужной. Поэтому была написана куча для приложений, функции
init_heap, user_alloc, user_free, user_realloc из core/heap.inc. Они
работают с отдельными страницами и блоками страниц.
Использование кучи несовместимо с перераспределением памяти сисфункцией 64, так что для активации режима кучи нужно
вызвать соответствующую сисфункцию, которая инициализирует кучу (init_heap)
и после которой функция 64 будет всегда возвращать ошибку. Организация
данных: есть некоторые поля в структуре потока, хранящие базу кучи и размер
адресного пространства, отводимого под кучу; в куче бывают выделенные и
свободные блоки (все блоки занимают целое число страниц), все блоки
организованы в односвязный список следующим образом. Информация о
физических страницах для линейных адресов хранится в таблице страниц, при
этом "нормальные" элементы таблицы либо нулевые (страница не выделена,
обращаться к ней нельзя), либо имеют установленный бит присутствия (страница
выделена и находится в памяти), либо имеют установленный 1-й бит (был запрос
на выделение страницы, но она будет выделена при первом обращении).
Информация о блоке размещается там же, в элементе таблицы страниц,
предшествующем собственно блоку, и в таком элементе младшие два бита
нулевые, зато установлен либо 2-й бит (маска FREE_BLOCK=4), соответствующий
свободному блоку, либо 3-й бит (маска USED_BLOCK=8); старшие 32-12 = 20 бит
содержат длину блока, это и организует односвязный список всех блоков.
Кстати, при таком хранении информации любые два блока разделены хотя бы
одной свободной страницей. Выделение блока - алгоритм first-fit, в цикле по
блокам находим первый свободный блок подходящего размера; если он оказался в
точности запрошенного размера, то он просто переводится в статус занятого,
иначе от него отделяется хвост, остающийся свободным блоком. В любом случае
страницы нового блока помечаются значением 2 (отложенное выделение
физической памяти). Функция освобождения блока освобождает все выделенные
страницы из блока через free_page, помечает блок как свободный, после чего
проходит по списку блоков, объединяя соседние свободные блоки в один
свободный блок. Функция перераспределения блока при уменьшении размера
блока освобождает лишние страницы и либо создаёт новый свободный блок, либо
расширяет следующий свободный блок, а при увеличении размера блока смотрит,
есть ли сразу после запрошенного блока свободный блок нужного размера (можно
ли увеличить запрошенный блок на месте), если нет, то ищет свободный блок
полного размера (тоже first-fit), перемаппит все физические страницы из
старого блока в новый, помечает старый блок как свободный и запускает
объединение свободных блоков; добавленные страницы в любом случае помечаются
значением 2. Все три функции в конце работы вызывают update_mem_size.
Стандартной процедуры для работы с блоками меньше страниц нет. В различных
библиотеках для ЯВУ есть различные реализации malloc/realloc/free на основе
системных функций, но это уже зависит от конкретной программы. Некоторые
программы вообще обходятся без маленьких блоков и неплохо себя чувствуют.
6. API для других подсистем ядра - ранее описанные функции. API для
драйверов: AllocPage, AllocPages, FreePage, GetPgAddr, MapPage, MapIoMem,
CommitPages, ReleasePages, AllocKernelSpace, FreeKernelSpace, KernelAlloc,
KernelFree, UserAlloc, UserFree, Kmalloc, Kfree (это malloc/free из кучи
малых блоков ядра).
API для приложений: сисфункции 64, 68.11, 68.12, 68.13, 68.20, 18.16, 18.17, 18.20.
4 | Содержание
| 6
Pterox' DocPack R6. Last Edition: 29.05.2010. История выпусков