Введение
Многие стандартные типы данных, такие, как классы, интерфейсы, строки, динамические массивы, неявно работают с динамической памятью. Зачастую пользователь даже и не подозревает, сколько обращений к динамической памяти происходит в той или иной строчке кода. Размеры объектов в динамической памяти могут колебаться от нескольких байт (строки) до многих мегабайт (пользовательские вызовы функций GetMem и AllocMem, а также создание динамических массивов). Достаточно трудно представить себе, какое количество строк и объектов может находиться в памяти во время работы программы. Естественно, что в такой ситуации требуется наличие быстрого и экономичного менеджера памяти, какой и предоставляется Delphi. Приведу цитату Евгения Рошаля, который в описании новых возможностей своей программы Far (версия 1.70 beta 2, сборка 321 от 16.12.2000) писал: «Для компиляции FAR Manager использовался Borland C/C++ 5.02. MSVC 6 SP4 не оправдал ожиданий (FAR 1.70 beta 1) и добавил тормозов (работа с выделением памяти для мелких объектов)». Известно, что менеджеры памяти в Borland C/C++, Borland C++ Builder и Delphi имеют общие алгоритмы работы. В данной статье я постараюсь в общих чертах описать принципы работы менеджера памяти Delphi.
Зачем это нужно? Ведь, казалось бы, работает себе и работает, зачем его трогать? Это нужно по нескольким причинам. Во-первых, никогда не помешает разбор чужого кода, особенно если это грамотный код. Это возможность научиться чему-либо новому, а также получить эстетическое наслаждение. Во-вторых, никогда не лишне поглубже разобраться в чем-то, убедиться в тех вещах, в которых вы ранее не были уверены или же, наоборот, найти слабые места, о которых вы ранее и не подозревали, чтобы в будущем писать более эффективный код.
Вся реализация менеджера памяти (за исключением некоторых объявлений в интерфейсной части модуля System.pas) расположена в файле GetMem.inc, хранящемся в каталоге $(DELPHI)/Source/Rtl/Sys. Менеджер памяти Delphi полностью реализован на Object Pascal, без использования ассемблерных вставок. Заметим еще, что в Kylix нет своего менеджера памяти, поэтому вызовы GetMem, FreeMem и ReallocMem сводятся к соответствующим вызовом malloc, realloc и free из стандартной C-библиотеки.
Для понимания работы менеджера памяти Delphi вам понадобятся знание принципов работы виртуальной памяти в Windows, а также понимание принципов работы четырех функций: VirtualAlloc, VirtualFree, LocalAlloc и LocalFree. Эта информация выходит за рамки данной статьи, и может быть получена либо из книги Джеффри Рихтера "Windows для профессионалов, 4-е издание", либо из MSDN.
Прежде всего, условимся о смысле используемых терминов. Основная путаница возникает из-за того, что менеджер памяти Delphi сам использует услуги менеджера виртуальной памяти Windows. Блок памяти, свободный с точки зрения программы, может считаться выделенным с точки зрения Windows. Итак, фрагмент памяти будем называть свободным, если он целиком состоит из страниц свободной памяти в смысле Windows. Фрагмент памяти будем называть зарезервированным, если он целиком состоит из страниц памяти, зарезервированных приложением. Фрагмент памяти будем называть выделенным, если он состоит целиком из страниц памяти, под которые выделена физическая память. Соответственно, фрагмент памяти будем называть не выделенным, если он состоит из страниц, зарезервированных приложением, но под которые не выделено физической памяти. Фрагмент памяти будем называть используемым, если он был передан Delphi-программе. И, наконец, фрагмент памяти будем называть неиспользуемым, если под ним расположена физическая память, но в настоящее время он не используется приложением Delphi. Вся иерархия памяти представлена на рис. 1.
Рисунок 1.
Структура менеджера памяти Delphi
Менеджер памяти Delphi состоит из четырех администраторов, а также отладочных и диагностических функций. Схема зависимости администраторов представлена на рисунок 2. Расскажем коротко о каждом из них.
Рисунок 2.
Первый из них - администратор описателей блоков. Его задача - предоставить остальным администраторам функции для работы с двунаправленными кольцевыми списками. Как мы увидим позже, вся информация о выделенной и зарезервированной памяти хранится в таких списках. При этом возникает проблема, состоящая в том, что элементы подобных списков необходимо создавать динамически. Администратор описателей блоков решает эту проблему, обращаясь к главной куче процесса.
Администратор зарезервированной памяти отвечает за память, зарезервированную менеджером памяти Delphi. В силу особенностей реализации менеджера виртуальной памяти Windows, этот администратор обрабатывает также запросы на передачу и на возврат физической памяти в указанном регионе.
Главной функцией администратора выделенной памяти является обработка запросов по выделению и освобождению памяти. Он хранит также информацию обо всей зарезервированной, но еще не выделенной памяти.
Администратор используемой памяти является самым низкоуровневым администратором. Он непосредственно общается с самим приложением Delphi, удовлетворяя его запросы на выделение и освобождение памяти. Он хранит в себе информацию обо всей выделенной памяти.
Одной из особенностей работы всех администраторов (кроме администратора описателей блоков) является то обстоятельство, что они работают по принципу "можно больше, нельзя меньше". При запросе администратор может выделить больше запрашиваемого количества памяти, и уже администратор более низкого уровня должен решать, как ему использовать остаток. Так, скажем, при попытке зарезервировать область памяти размером 100 байт (обращение от администратора выделенной памяти к администратору зарезервированной памяти), все равно будет зарезервирован регион в 1 Мб, и администратор выделенной памяти сам должен будет решить, как ему поступать с остатком. Соответственно при попытке освобождения памяти администратор может освободить меньший фрагмент.
Сделаем также ряд замечаний по поводу схемы обработки ошибок менеджером памяти Delphi. Если функция возвращает выделенный блок памяти, то в случае ошибки возвращается блок со значением addr, равным nil. В случае ошибки при освобождении памяти устанавливается глобальная переменная heapErrorCode. Кроме того, ряд функций, возвращающих значение типа Boolean, сигнализируют о случившейся ошибке, возвращая значение False.
Опишем еще пару переменных - initialized, которая проверяет, инициализирован ли менеджер памяти, и heapLock - критическую секцию для обеспечения синхронизации при многопоточности. Отметим, что вход в критическую секцию происходит только в том случае, когда глобальная переменная IsMultiThread установлена в True. Это одна из причин, по которым потоки должны создаваться вызовом функции BeginThread, а не напрямую при помощи функции CreateThread.
Администратор описателей блоков
Почти вся информация о зарезервированной, выделенной и невыделенной памяти хранится в виде кольцевых двунаправленных списков. Главным их преимуществом является то, что для удаления элемента из такого списка достаточно знать лишь указатель на этот элемент (см., например, функцию DeleteBlock). Администратор описателей блоков предоставляет остальным администраторам функции для работы с такими списками, а также для динамического выделения в памяти элементов этих списков.
В листинге 1 приведены все объявления, относящиеся к данному администратору.
type
TBlock = packed record
addr: PChar;
size: Integer;
end;
PBlockDesc = ^TBlockDesc;
TBlockDesc = packed record
next: PBlockDesc;
prev: PBlockDesc;
addr: PChar;
size: Integer;
end;
PBlockDescBlock = ^TBlockDescBlock;
TBlockDescBlock = packed record
next: PBlockDescBlock;
data: array [0..99] of TBlockDesc;
end;
var
blockDescBlockList: PBlockDescBlock;
|
Обратим внимание на то, что менеджер памяти Delphi различает такие понятия, как блок (TBlock) и описатель блока (TBlockDesc). Блок задает фрагмент памяти и содержит в себе указатель на начало фрагмента и его длину. Блоки используются в основном для передачи параметров и при объявлении локальных переменных. Время жизни блока обычно ограничивается той процедурой или функцией, где он объявлен. Описатель блока - это элемент двунаправленного списка, который описывает некоторый фрагмент памяти.
Элементы кольцевых двунаправленных списков, кроме указателей на предыдущий и последующий элементы, хранят также информацию о начальном адресе фрагмента памяти и его длине. Обычно в таких списках можно выделить корневой элемент. Это элемент списка, который содержит нулевые значения в адресе и размере блока, и служит, с одной стороны, началом списка, и, с другой стороны, индикатором конца списка. Если у кольцевого двунаправленного списка есть корневой элемент, он не может быть пустым, т. е. он должен содержать по крайней мере один этот корневой элемент. Все элементы кольцевого двунаправленного списка можно обойти в цикле, приведенном в листинге 2.
var
root: TBlockDesc;
bd: PBlockDesc;
...
bd := root.next;
while bd <> @root do begin
{TODO: тело цикла}
...
bd := bd.next;
end;
|
Сразу отметим, что кольцевые двунаправленные списки, которые используются менеджером памяти Delphi, бывают двух типов. Основное различие типов - в способе выполнения операций вставки блока в список и удаления блока из списка. При добавлении блока в список первого типа, остальные блоки в списке остаются без изменений. Как следствие, удалить из такого списка мы можем лишь тот блок, который был вставлен в него ранее. При добавлении блока в список второго типа проверяется, не граничит ли добавляемый блок с остальными блоками в списке. Если это так, то происходит "слияние" блоков, т. е. все граничащие между собой блоки заменяются одним. Соответственно, удалить из такого списка можно любой блок памяти, лишь бы он содержался внутри одного из блоков, присутствующих в списке. В этом случае может произойти "расщепление" блока на два. Использование списков второго типа позволяет избежать фрагментации памяти.
Рассмотрим теперь динамическое выделение памяти под описатели. Все данные, относящиеся к администратору описателей блоков, хранятся в виде двух однонаправленных списков. В первом из них (blockDescBlockList) хранятся сами описатели группами по сто. Во втором списке (blockDescFreeList) хранятся свободные в настоящий момент описатели, а в качестве связи между ними используется поле next описателя. Каждый из описателей находится в одной из структур типа TBlockDescBlock списка blockDescBlockList, а если описатель свободен, то также и в списке blockDescFreeList. Типичное состояние администратора описателей блоков приведено на рисунке 3.
Рисунок 3.
Кратко опишем функции администратора описателей блоков.
function GetBlockDesc: PBlockDesc; |
Данная функция создает новый описатель блока.
procedure MakeEmpty(bd: PBlockDesc); |
Эта процедура принимает в качестве параметра указатель на корневой элемент списка, в котором устанавливает указатели следующего и предыдущего элемента на самого себя. Таким образом, список становится пустым. Вызывается только на этапе инициализации или деинициализации менеджера памяти.
function AddBlockAfter(prev: PBlockDesc; const b: TBlock): Boolean; |
Данная функция динамически создает описатель для блока b и добавляет его (описатель) непосредственно перед элементом prev. В качестве элемента prev в текущей реализации менеджера памяти всегда используется указатель на корневой элемент списка первого типа. Таким образом, функция добавляет описатель блока в начало списка. В случае успеха функция возвращает True.
procedure DeleteBlock(bd: PBlockDesc); |
Данная процедура удаляет описатель блока из списка первого типа и освобождает этот описатель.
function MergeBlockAfter(prev: PBlockDesc; const b: TBlock) : TBlock; |
Данная функция добавляет указанный блок памяти в двунаправленный кольцевой список второго типа (см. выше). Возвращаемым значением является блок памяти, образовавшийся в результате слияния добавляемого блока с уже существующими. В случае ошибки значение addr в возвращаемом блоке установлено в nil.
function RemoveBlock(bd: PBlockDesc; const b: TBlock): Boolean; |
Данная функция удаляет блок памяти из кольцевого двунаправленного списка второго типа. В случае успеха функция возвращает True.
Администратор зарезервированной памяти
Администратор зарезервированной памяти содержит информацию обо всех обращениях менеджера памяти к функции VirtualAlloc с целью резервирования фрагмента памяти. Эта информация нужна для того, чтобы в дальнейшем производить передачу физической памяти региону зарезервированного адресного пространства, а также чтобы производить освобождение памяти. Напомним, что при освобождении фрагмента памяти с помощью функции VirtualFree необходимо указать в точности тот адрес, который был получен функцией VirtualAlloc при резервировании этого фрагмента. Кроме того, за один вызов VirtualAlloc мы можем передавать физическую память только внутри диапазона адресов, зарезервированных одним вызовом VirtualAlloc. Поэтому при хранении информации о памяти, зарезервированной менеджером памяти Delphi, используются списки первого типа. Ведь иначе при слиянии двух блоков мы потеряем адреса, которые возвращались функцией VirtalAlloc, а значит, не сумеем впоследствии освободить память. Кроме того невозможно будет корректно передать физическую память фрагментам, лежащим в смежных областях, выделенных при помощи двух разных вызовов VirtualAlloc.
Этой особенностью поведения менеджера виртуальной памяти Windows объясняется и присутствие в администраторе зарезервированной памяти функций Commit и Decommit, которые производят соответственно передачу и возврат физической памяти со страниц зарезервированного фрагмента, но не имеют ограничений, присущих функциям VirtualAlloc и VirtualFree. Но для корректного выполнения таких операций необходимо обладать информацией обо всех вызовах функции VirtualAlloc с целью резервирования адресного пространства. Наличие этих функций в администраторе зарезервированной памяти также позволило выделить все обращения к менеджеру виртуальной памяти Windows в один администратор.
В листинге 3 приведены все объявления, относящиеся к данному администратору.
var
spaceRoot: TBlockDesc;
const
cSpaceAlign = 64*1024; // 64Kb
cSpaceMin = 1024*1024; // 1Mb
cPageAlign = 4*1024; // 4Kb
|
Таким образом, администратор зарезервированной памяти содержит единственный кольцевой двунаправленный список spaceRoot, в котором хранится описание всех обращений к функции VirtualAlloc с целью резервирования памяти. Первоначально этот список не содержит элементов. При работе администратора используются константы:
- cSpaceAlign, показывающая, по какой границе будут выравниваться резервируемые фрагменты памяти;
- cSpaceMin, показывающая минимальный размер блока памяти, который будет зарезервирован;
- cPageAlign, задающая размер страницы.
Коротко опишем назначение и особенности каждой из функций, входящих в состав администратора.
function GetSpace(minSize: Integer): TBlock; |
Резервирует регион памяти размером, как минимум, равным minSize байт. Возвращает блок памяти, который был фактически зарезервирован. В случае ошибки возвращает в поле addr блока памяти значение nil. Зарезервированная память имеет атрибут доступа PAGE_NOACCESS.
function GetSpaceAt(addr: PChar; minSize: Integer): TBlock; |
Резервирует регион памяти по указанному адресу addr размером, как минимум, равным minSize байт. Возвращает блок памяти, который был фактически зарезервирован. В случае ошибки возвращает в поле addr блока памяти значение nil. Зарезервированная память имеет атрибут доступа PAGE_READWRITE.
Данная функция обладает одной интересной особенностью, а именно, она может зарезервировать фрагмент памяти, который имеет размер меньше запрашиваемого. Подробнее эта особенность будет рассмотрена при описании функции GetCommittedAt.
function FreeSpace(addr: Pointer; maxSize: Integer): TBlock; |
Пытается освободить по указанному адресу addr не более чем maxSize байт. Возвращает блок памяти, который был фактически освобожден. Если память не освобождалась, функция возвратит в поле addr блока памяти значение nil. В случае ошибки устанавливает переменную heapErrorCode в значение cReleaseErr.
function Commit(addr: Pointer; minSize: Integer): TBlock; |
Функция выделяет фрагмент памяти по указанному адресу addr размером не менее minSize байт. В случае ошибки возвращает в поле addr блока памяти значение nil. Выделенная страница памяти будут иметь атрибуты доступа PAGE_READWRITE.
function Decommit(addr: Pointer; maxSize: Integer): TBlock; |
Функция пытается вернуть физическую память по указанному адресу addr, но не более чем maxSize байт. Результат функции - адрес возвращаемого блока физической памяти. Если физическая память не была возвращена, функция возвратит значение nil в поле addr блока памяти. В случае ошибки устанавливает переменную heapErrorCode в значение cDecommitErr.
Администратор выделенной памяти
Администратор выделенной памяти хранит информацию о зарезервированной, но не выделенной памяти. Обратите внимание на игру слов: администратор занимается выделенной памятью, но хранит информацию о не выделенной . Этот администратор обрабатывает запросы на выделение памяти от администратора используемой памяти. Поэтому он хранит информацию о невыделенной, но зарезервированной памяти, чтобы из этих запасов удовлетворять потребности администратора используемой памяти. Если запаса не выделенной памяти не хватает, администратор обращается к администратору зарезервированной памяти.
В листинге 4 приведены все объявления, относящиеся к данному администратору.
const
cCommitAlign = 16*1024; // 16Kb
var
decommittedRoot: TBlockDesc;
|
Администратор выделенной памяти содержит один двунаправленный список decommittedRoot, в котором содержится информация обо всей зарезервированной, но не выделенной памяти. Первоначально список не содержит элементов. Память добавляется и удаляется из списка decommittedRoot при помощи вызовов MergeBlockAfter и RemoveBlock, таким образом, в этом списке не может содержаться двух смежных фрагментов памяти (т. е. это список второго типа). Кроме этого, в работе администратора используется одна константа - cCommitAlign, которая показывает, по какой границе будут выравниваться запросы на выделение памяти.
Расскажем немного о взаимодействии между администраторами зарезервированной памяти и выделенной памяти. Для всех фрагментов памяти, которые входят в список decommittedRoot, администратор выделенной памяти производит передачу физической памяти, пользуясь функцией Commit администратора зарезервированной памяти. Если же для удовлетворения запроса администратору зарезервированной памяти не хватает зарезервированной, но не выделенной памяти, он вызывает GetSpace. Соответственно администратор выделенной памяти возвращает физическую память при помощи вызова функции Decommit администратора зарезервированной памяти. После этого указанный фрагмент добавляется к списку decommittedRoot, и производится контрольная проверка на снятие резервирования с нового фрагмента памяти, образованного слиянием освобождаемого блока памяти с теми, которые уже находились в списке decommittedRoot.
Следует обратить внимание на одну особенность поведения функции GetCommittedAt администратора выделенной памяти. Данная функция в цикле вызывает функцию GetSpaceAt до тех пор, пока размер зарезервированного пространства не превысит запрашиваемый размер (см. особенности функции GetSpaceAt). Но при этом данному фрагменту памяти будет соответствовать несколько описателей в списке spaceRoot. Для чего это было сделано? Вспомним, что вызов функции VirtualAlloc для освобождения страницы (флаг MEM_RELEASE) должен в точности соответствовать вызову VirtualAlloc, который резервировал память. Таким образом, при очередном уменьшении размера блока (или при его освобождении), менеджер памяти будет в состоянии вернуть системе хотя бы часть зарезервированных фрагментов, в которых располагался этот блок памяти.
Коротко опишем каждую из функций администратора выделенной памяти.
function GetCommitted(minSize: Integer): TBlock; |
Выделяет область памяти размером не меньше minSize байт. Возвращает блок памяти, который был фактически выделен. В случае ошибки возвращает в поле addr блока памяти значение nil.
function GetCommittedAt(addr: PChar; minSize: Integer): TBlock; |
Выделяет область памяти по указанному адресу addr размером не меньше minSize байт. Возвращает блок памяти, который был фактически выделен. В случае ошибки возвращает в поле addr блока памяти значение nil.
function FreeCommitted(addr: PChar; maxSize: Integer): TBlock; |
Пытается вернуть физическую память по указанному адресу addr, но не более чем maxSize байт. Возвращает блок памяти, с которого была возвращена физическая память. Если память не освобождалась, функция возвратит в поле addr блока памяти значение nil.
Администратор используемой памяти
Алгоритм работы этого администратора, с одной стороны, является самым запутанным из всех, но, с другой стороны, и самым интересным. Он хранит информацию обо всей выделенной памяти и непосредственно общается с самим приложением Delphi, удовлетворяя его запросы. Для начала опишем все структуры данных, которые используются в нем. Все константы, типы и переменные, которые используются администратором выделенной памяти, представлены в листинге 5.
const
cAlign = 4; // Выравнивание всех выделенных блоков по границе 4
cThisUsedFlag = 2; // Флаг - блок используется программой
cPrevFreeFlag = 1; // Флаг - предыдущий блок свободен
cFillerFlag = Integer($80000000); // Флаг - ?
cFlags = cThisUsedFlag or cPrevFreeFlag or cFillerFlag;
// Максимальный размер свободного фрагмента, который будет храниться
// в массиве smallTab
cSmallSize = 4*1024;
cDecommitMin = 15*1024; //Минимальный размер выделяемой физической памяти
type
PFree = ^TFree;
TFree = packed record
prev: PFree;
next: PFree;
size: Integer;
end;
PUsed = ^TUsed;
TUsed = packed record
sizeFlags: Integer;
end;
TSmallTab = array [sizeof(TFree) div cAlign .. cSmallSize div cAlign]
of PFree;
VAR
avail : TFree; // ?
rover : PFree; // Странник ?
remBytes : Integer; // Количество свободных байт в curAlloc
// Текущий указатель, по которому производиться выделение
curAlloc : PChar;
smallTab : ^TSmallTab; // Массив свободных огрызков
committedRoot: TBlockDesc; // Массив свободной физической памяти
|
В выделенных фрагментах памяти блоки идут один за другим. Всего различают три типа блоков. Это используемые блоки, неиспользуемые блоки и заполнители. Администратор памяти оперирует с блоками, размеры которых выровнены по границе cAlign байт. Размер блока хранится в самом блоке памяти. Поскольку в настоящее время cAlign равен четырем, то, очевидно, два младших бита несущественны и могут использоваться как флаги. Третий флаг возникает при использовании самого старшего бита, что ограничивает размеры выделяемых блоков двумя гигабайтами. Формат размера приведен на рисунке 4.
Рисунок 4.
Размер блока также включает в себя всю служебную информацию, которая хранится в блоке (например, если мы выделяем 99 байт памяти, то полученный размер блока будет равен 104 байтам, из них 1 байт уйдет на выравнивание и 4 байта на значение размера и флаги).
Опишем назначение каждого из флагов. Флаг cThisUsedFlag показывает, что данный фрагмент памяти используется приложением Delphi. Флаг cPrevFreeFlag указывает, что предыдущий фрагмент памяти свободен. Флаг cFillerFlag указывает на то, что данный фрагмент памяти является заполнителем.
Используемые блоки - это фрагменты памяти, выделенные приложением Delphi. Они имеют формат, показанный на рисунке 5. Мы видим, что четыре байта памяти, расположенные по отрицательному смещению от указателя, который вернула функция GetMem, являются размером блока (не забывайте, что размер блока содержит еще и флаги), остальная же его часть целиком и полностью находится в ведении приложения. Служебная часть используемого блока памяти описана в структуре TUsed.
Рисунок 5.
Неиспользуемые фрагменты имеют формат, показанный на рисунке 6. Несмотря на то, что сумма всех составляющих блока равна 16 байтам, минимальный размер блока может быть равен (!) 12 байтам. В этом случае поле size1 накладывается на поле size2, и никакого искажения информации не происходит. Поскольку любой используемый блок памяти может стать впоследствии неиспользуемым, минимальный размер блока, выделенного менеджером памяти Delphi, равен 12 (или, с точки зрения приложения, 8) байтам.
Рисунок 6.
Отметим еще одну особенность свободного блока. Несмотря на то, что он начинается элементом prev, можно смело брать в этом блоке значения флагов. Очевидно, что они все равны нулю. Поэтому получаем, что
- Данный блок не является заполнителем (о них ниже).
- Данный блок не является используемым.
- Предыдущий фрагмент занят (что вполне естественно, так как в противном случае, как мы увидим позже, менеджер памяти Delphi объединил бы указанные свободные блоки).
Таким образом, первые четыре байта любого блока (как используемого, так и неиспользуемого) содержат значения флагов, по которым можно определить, используется ли данный блок, и т. д.
Служебная часть неиспользуемого блока памяти, расположенная в начале блока, описана в структуре TFree. Служебная часть неиспользуемого блока памяти, расположенная в конце блока, описана в структуре TUsed.
Теперь о заполнителях и щелях. Виртуальное адресное пространство, не имеющее под собой физической памяти, и граничащее с выделенными менеджером памяти фрагментами, называется щелью (gap). Заполнитель - это специфический блок памяти, который располагается либо сразу после, либо непосредственно перед щелью. Выделенный фрагмент памяти обязательно заканчивается заполнителем. Таким образом, это дает возможность смело адресоваться к блоку, который расположен непосредственно за текущим, если только текущий блок не является заполнителем. Размер заполнителя - от четырех до двенадцати байт. Заполнитель имеет формат, показанный на рисунке 7. Как и в случае со свободным блоком, значения size1 и size2 могут накладываться друг на друга. Значение флагов cFillerFlag и cUsedBlock для заполнителя установлены в 1, а значение флага cPrevFree зависит от того, является ли предшествующий блок используемым. Начало и конец заполнителя описываются структурой TUsed. Работа с заполнителями организована таким образом, что всякий раз после выделения блока памяти (если он граничит с уже использующимися) происходит стирание недействительных заполнителей и, при необходимости, создание новых.
Рисунок 7.
Опишем структуры памяти, входящие в состав администратора используемой памяти. Прежде всего, отметим двунаправленный кольцевой список decommittedRoot, который описывает всю выделенную память, имеющуюся в распоряжении менеджера памяти Delphi. Первоначально этот список не содержит элементов.
Массив указателей smallTab хранит указатели на двунаправленные списки, состоящие из неиспользуемых блоков небольшого размера. Наибольший размер, информация о котором хранится в этом массиве, равен cSmallSize байт, что в настоящее время составляет 4 Кб. Заметим также, что элементы массива smallTab являются только указателями на элементы двунаправленного кольцевого списка, но, в отличие от таких структур, как spaceRoot, decommittedRoot и committedRoot, не являются корневыми элементами. В случае, когда свободных элементов указанного размера нет, соответствующий указатель в массиве smallTab равен nil. В качестве связей в двунаправленном списке используются поля prev и next структуры TFree в начале неиспользуемого блока. Место под массив smallTab выделяется в локальной куче процесса. Первоначально все указатели содержат значения nil.
Переменная avail является корневым элементом двунаправленного кольцевого списка, который содержит фрагменты памяти, большие чем cSmallSize. Первоначально этот список не содержит элементов. Переменная rover (переводится как "скиталец") указывает на блок памяти, который был в последний раз добавлен к списку avail. Первоначально переменная rover указывает на avail.
Переменные curAlloc и remBytes содержат соответственно указатель на текущий выделяемый фрагмент и размер этого фрагмента. Что это за фрагмент? Всякий раз, когда администратор используемой памяти обращается к администратору выделенной памяти за новой порцией памяти, образуется довольно большой фрагмент неиспользуемой памяти. Этот фрагмент оформляется как текущий выделяемый фрагмент. При удовлетворении запросов приложения, первым делом производится поиск свободного фрагмента в точности требуемого размера. Если таковой не найден, то будет произведена попытка выделить память из текущего выделяемого фрагмента. Текущий выделяемый фрагмент может иметь и нулевую длину, если он, например, расположен непосредственно перед щелью. Текущий выделяемый фрагмент не содержится ни в одном из перечисленных выше списков. Чтобы поместить его в один из таких списков, используется функция SysFreeMem (!), т. е. данный блок первоначально оформляется как используемый программой, а затем функция SysFreeMem помещает его в один из существующих списков. Первоначально curAlloc равен nil, а remBytes - нулю.
Рисунок 8.
Теперь мы в состоянии взглянуть на менеджер памяти Delphi в целом. Типичное его состояние приведено на рисунке 8. Перед тем, как рассмотреть алгоритмы выделения, перераспределения и удаления памяти, опишем назначение каждой функции, входящей в администратор используемой памяти.
function InitAllocator: Boolean; |
Инициализирует менеджер памяти. В случае успеха возвращает True.
procedure UninitAllocator; |
Освобождает всю память, занимаемую или выделенную менеджером памяти Delphi.
procedure DeleteFree(f: PFree); |
Удаляет указанный свободный блок из всех списков, в которых он присутствует. Передаваемый параметр - указатель на начало свободного блока памяти.
function FindCommitted(addr: PChar): PBlockDesc; |
Находит элемент списка committedRoot, содержащий указанный адрес addr. В случае ошибки устанавливает переменную heapErrorCode в cBadCommittedList.
procedure FillBeforeGap(a: PChar; size: Integer); |
Вызывается для того, чтобы создать заполнитель перед фрагментом, не имеющим под собой физической памяти. В качестве параметров передаются: указатель на начало последнего фрагмента в блоке выделенной памяти a и его размер size. В случае необходимости вставляет новый неиспользуемый блок памяти.
procedure InternalFreeMem(a: PChar); |
Вызывается для блоков памяти, которые были оформлены менеджером памяти как используемые, чтобы поместить их в соответствующие списки свободных блоков. Выполняет коррекцию статистики занятого пространства и вызывает SysFreeMem.
procedure FillAfterGap(a: PChar; size: Integer); |
Вызывается для оформления фрагмента памяти после щели. В зависимости от размера свободного блока либо создает заполнитель, либо добавляет новый свободный фрагмент. В качестве параметров передается указатель на начало фрагмента памяти a, а также его размер size.
function FillerSizeBeforeGap(a: PChar): Integer; |
Вызывается для уничтожения заполнителя в случае, когда выделяемый фрагмент памяти граничит снизу с уже выделенным фрагментом. В качестве параметра a передается указатель на начало вновь выделяемого фрагмента памяти (либо, что то же самое, указатель на конец ранее выделенного фрагмента). Возвращает размер неиспользуемого фрагмента памяти в конце ранее выделенного фрагмента. В случае ошибки устанавливает значение heapErrorCode в одно из следующих значений: cBadFiller1, cBadFiller2, cBadFiller3.
function FillerSizeAfterGap(a: PChar): Integer; |
Вызывается для уничтожения заполнителя в случае, когда выделяемый фрагмент памяти граничит сверху с уже выделенным фрагментом. В качестве параметра a передается указатель на конец вновь выделяемого фрагмента памяти (либо, что тоже самое, указатель на начало ранее выделенного фрагмента). Возвращает размер неиспользуемого фрагмента памяти в начале ранее выделенного блока.
function DecommitFree(a: PChar; size: Integer): Boolean; |
Производит попытку возвратить физическую память, но не более чем size байт. При необходимости устанавливает заполнители.
procedure InsertFree(a: Pointer; size: Integer); |
Добавляет новый свободный блок памяти, начинающийся по адресу a и занимающий size байт, в какой-либо из существующих списков в зависимости от размера блока, его местоположения и т. д.
procedure FreeCurAlloc; |
Помещает память, хранящуюся в текущем выделяемом фрагменте (который начинается по адресу curAlloc и занимает remBytes байт) в один из существующих списков в зависимости от размера блока, его местоположения и т. д.
function MergeCommit(b: TBlock): Boolean; |
Добавляет новый блок памяти b в список committedRoot. В случае «слияния» блоков, все заполнители, оказавшиеся в середине блока, уничтожаются. В случае успешного завершения возвращает True.
function NewCommit(minSize: Integer): Boolean; |
Запрашивает у администратора выделенной памяти фрагмент размером не менее minSize байт, после чего вызывает для него функцию MergeCommit. В случае успешного завершения возвращает True.
function NewCommitAt(addr: Pointer; minSize: Integer): Boolean; |
Запрашивает у администратора выделенной памяти фрагмент памяти размером не менее minSize байт, начинающийся по адресу addr, после чего вызывает для него функцию MergeCommit. В случае успешного завершения возвращает True.
function SearchSmallBlocks(size: Integer): PFree; |
Производит поиск наименьшего блока памяти, имеющего размер больше, чем size байт, в массиве smallTab. В случае удачного завершения возвращает указатель на начало такого блока. Если такого блока не оказалось, возвращает nil.
function TryHarder(size: Integer): Pointer; |
Вызывается функцией SysGetMem в случае, когда простые попытки выделить память потерпели неудачу. Передаваемый параметр size - размер запрашиваемого блока. Возвращает выделенный блок памяти.
function SysGetMem(size: Integer): Pointer; |
Реализация функции GetMem, предоставляемая менеджером памяти Delphi. Передаваемый параметр size - размер запрашиваемого блока. Возвращает выделенный блок памяти. Подробнее о работе этой функции, а также функции TryHarder смотри в разделе «Алгоритм выделения памяти».
function SysFreeMem(p: Pointer): Integer; |
Реализация функции FreeMem, предоставляемая менеджером памяти Delphi. Передаваемый параметр p - указатель на освобождаемый блок памяти. В случае удачного освобождения памяти возвращает cHeapOk (нуль). В случае ошибки возвращает ее код. Подробнее о работе этой функции можно прочитать в разделе «Алгоритм освобождения памяти».
function ResizeInPlace(p: Pointer; newSize: Integer): Boolean; |
Выполняет попытку перераспределения памяти по указанному адресу p без переноса существующего блока. В случае удачного завершения (когда удалось изменить размер блока на newSize) возвращает True.
function SysReallocMem(p: Pointer; size: Integer): Pointer; |
Реализация функции ReallocMem, предоставляемая менеджером памяти Delphi. Передаваемые параметры - запрашиваемый размер блока и указатель на фрагмент памяти. Возвращает указатель на новый перераспределенный фрагмент памяти (или nil, если перераспределить память не удалось). Подробнее о работе этой функции, а также о функции ResizeInPlace, рассказано в разделе «Алгоритм перераспределения памяти».
Алгоритмы
Алгоритм выделения памяти
Алгоритм выделения памяти достаточно прост - в цикле перебираются все списки в порядке приоритета, и если находится нужный фрагмент, то его и возвращают программе. Схема алгоритма выделения памяти приведена на рисунке 9. Ниже мы приведем описание всех попыток, в том порядке, в котором они производятся.
Рисунок 9.
- Пытаемся найти в массиве smallTab блок в точности нужного размера.
- Пытаемся выделить память из текущего выделяемого фрагмента.
- Пытаемся найти блок подходящего размера в начале списка avail.
- Просматриваем все оставшиеся элементы в списке avail, начиная с элемента, на который указывает rover.
- Просматриваем массив smallTab, и, если в нем находится блок большего размера, используем его для выделения памяти.
- Выделяем память.
- Пытаемся выделить память из текущего выделяемого фрагмента. Поскольку при выделении памяти она автоматически добавляется в текущий выделяемый фрагмент, эта попытка является последней, несмотря на то, что формально (по тексту программы) стоит переход на пункт 3. Цикл repeat..until в теле функции TryHarder используется как метка оператора goto и выполняется не более одного раза.
Таким образом, при выделении памяти средствами стандартного менеджера памяти Delphi:
- При попытке запроса блока памяти размером до 4 Кб, если существует неиспользуемый блок в точности требуемого размера, он будет возвращен.
- Если существует неиспользуемый фрагмент памяти, имеющий под собой физическую память, в который может поместиться запрашиваемый блок, то нового выделения памяти не произойдет.
Алгоритм освобождения памяти
Алгоритм освобождения памяти уже не является линейным, как алгоритм выделения памяти. Однако он также не представляет большой сложности, поскольку большинство развилок связано с объединением смежных свободных блоков. Алгоритм приведен на рисунке 10.
Рисунок 10.
Итак, освобожденный блок помещается в один из следующих списков:
- Если он граничит с текущим выделяемым фрагментом, то добавляется к нему.
- Если его размер меньше, чем cSmallSize, он помещается в соответствующий список из массива smallTab.
- Блок помещается в список avail. Указатель rover устанавливается на него.
Кроме того, можно быть уверенным в том, что, если суммарный размер блока превысит значение cDecommitMin, произойдет возврат физической памяти со страниц, которые целиком находились внутри блока.
Алгоритм перераспределения памяти
Алгоритм перераспределения памяти, как и следовало ожидать, работает по-разному при уменьшении и увеличении размера фрагмента. Разберем алгоритмы раздельно. Алгоритм, который используется при уменьшении размера блока, представлен на рисунке 11, а алгоритм, который используется при увеличении размера блока - на рисунке 12. Если при расширении фрагмента не удалось произвести изменения размера по месту, будет выделен новый фрагмент нужного размера, и в него будет скопировано содержимое старого блока.
Рисунок 11.
Все сказанное ранее об алгоритмах выделения и освобождения памяти остается справедливым и в случае перераспределения памяти. Можно только добавить, что если расширение блока по месту физически не производится, то выделения нового фрагмента и копирования старого фрагмента в него не произойдет.
Рисунок 12.
В случае уменьшения размера блока обратим внимание на необходимость следить за тем, чтобы не образовывались неиспользуемые фрагменты памяти размера, меньшего, чем sizeof(TFree) байт. Поэтому в подобной ситуации размер блока сохраняется прежним.
В случае увеличения размера блока никаких глобальных действий (таких, как удаление свободного блока, объединения блоков) не производится, пока не выяснится, что перераспределение памяти по месту выполнимо.
Сделаем некоторые выводы. Во-первых, менеджер памяти Delphi особенно эффективно работает с блоками размером до 4 Кб. Во-вторых, при интенсивной работе с блоками, размер которых превышает 4 Кб, эффективность работы менеджера памяти Delphi несколько падает. Главным образом это происходит из-за того, что такие элементы не проиндексированы и хранятся в виде списка, так что поиск нужного фрагмента может занять продолжительное время. В-третьих, интенсивная работа с блоками, размер которых составляет 10-40 Кб, приведет к неоправданно частому выделению и возврату физической памяти. Ну и, в четвертых, необходимо по мере возможности избегать вызовов перераспределения памяти (по крайней мере, в сторону увеличения размера блока). В частности, для больших растущих фрагментов лучше, в обход менеджера памяти, пользоваться функциями VirtualAlloc и VirtualFree, а для очень больших фрагментов имеет смысл воспользоваться функциями AWE (Address Windowing Extensions). Если же для вашего приложения критично динамическое выделение памяти, а менеджер памяти Delphi не удовлетворяет ваши потребности, что возникает весьма редко, то, прежде чем искать альтернативные менеджеры памяти, можно попытаться настроить работу стандартного менеджера памяти через используемые им константы. Для этого нужно либо непосредственно внести изменения в файл GetMem.inc и перекомпилировать модуль system.pas, либо, что рекомендуется, написать на основе GetMem.inc новый файл, в котором зарегистрировать новый менеджер памяти.