Менеджер пам’яті Delphi, Комерція, Різне, статті

Введення


Багато стандартні типи даних, такі, як класи, інтерфейси, рядки, динамічні масиви, неявно працюють з динамічною пам’яттю. Найчастіше користувач навіть і не підозрює, скільки звернень до динамічної пам’яті відбувається в тій чи іншій сходинці коду. Розміри об’єктів у динамічній пам’яті можуть коливатися від декількох байт (рядки) до багатьох мегабайт (користувальницькі виклики функцій 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 з метою резервування пам’яті. Спочатку цей список не містить елементів. При роботі адміністратора використовуються константи:



Коротко опишемо призначення та особливості кожної з функцій, що входять до складу адміністратора.





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, можна сміливо брати в цьому блоці значення прапорів. Очевидно, що вони всі рівні нулю. Тому отримуємо, що



  1. Даний блок не є заповнювачем (про них нижче).
  2. Даний блок не є використовуваним.
  3. Попередній фрагмент зайнятий (що цілком природно, тому що в противному випадку, як ми побачимо пізніше, менеджер пам’яті 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.



  1. Намагаємося знайти в масиві smallTab блок в точності потрібного розміру.
  2. Намагаємося виділити пам’ять з поточного фрагмента.
  3. Намагаємося знайти блок відповідного розміру на початку списку avail.
  4. Переглядаємо всі залишилися елементи в списку avail, починаючи з елемента, на який вказує rover.
  5. Переглядаємо масив smallTab, і, якщо в ньому знаходиться блок більшого розміру, використовуємо його для виділення пам’яті.
  6. Виділяємо пам’ять.
  7. Намагаємося виділити пам’ять з поточного фрагмента. Оскільки при виділенні пам’яті вона автоматично додається до поточного виділяється фрагмент, ця спроба є останньою, незважаючи на те, що формально (по тексту програми) коштує перехід на пункт 3. Цикл repeat .. until в тілі функції TryHarder використовується як мітка оператора goto і виконується не більше одного разу.

Таким чином, при виділенні пам’яті засобами стандартного менеджера пам’яті Delphi:



  1. При спробі запиту блоку пам’яті розміром до 4 Кб, якщо існує невикористовуваний блок в точності необхідного розміру, він буде повернутий.
  2. Якщо існує невикористовуваний фрагмент пам’яті, що має під собою фізичну пам’ять, в який може поміститися запитуваний блок, то нового виділення пам’яті не відбудеться.

Алгоритм звільнення пам’яті


Алгоритм звільнення пам’яті вже не є лінійним, як алгоритм виділення пам’яті. Однак він також не представляє великої складності, оскільки більшість розвилок пов’язано з об’єднанням суміжних вільних блоків. Алгоритм наведено на малюнку 10.




Малюнок 10.


Отже, звільнений блок поміщається в один з таких списків:



  1. Якщо він межує з поточним виділеним фрагментом, то додається до нього.
  2. Якщо його розмір менше, ніж cSmallSize, він поміщається у відповідний список з масиву smallTab.
  3. Блок поміщається в список 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 новий файл, в якому зареєструвати новий менеджер пам’яті.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*