Впровадження malloc() та free() — спочатку повторне використання старої пам’яті

(Оригінал опубліковано як Реалізація malloc() та free() — спочатку повторне використання старої пам'яті в Suspension of Disbelief.)

У попередньому пості цієї серії про реалізацію malloc() та free(), ми показали, як можна повторно використовувати блоки пам'яті та зменшувати хіп, звільняючи новіші блоки. Однак поточна функція вводить тонку проблему: вона надає пріоритет повторному використанню новіших блоків, що може призвести до збільшення споживання пам'яті з часом. Чому це відбувається? Давайте розберемося.

Зменшення хіпу через повторне використання нових блоків

Розглянемо наступний сценарій. Спочатку ми виділяємо чотири блоки пам'яті:

void *ptr1 = abmalloc(8);  
void *ptr2 = abmalloc(8);  
void *ptr3 = abmalloc(8);  
void *ptr4 = abmalloc(8);

Структуру пам'яті можна уявити ось так:

Тепер ми звільняємо перший та третій блоки...

abfree(ptr1);  
abfree(ptr3);]

...що призводить до такої структури:

Далі виділяємо ще один блок такого ж розміру:

void *ptr5 = abmalloc(8);

Оскільки функція abmalloc() починає шукати найбільш новий вільний блок, вона використовує блок, що знаходиться на верху. Якщо тепер ми звільняємо останній блок:

Якщо ми зараз звільнимо останній блок...

abfree(ptr4);

...ми зможемо зменшити розмір хіпу лише на один блок по 8 байт, оскільки попередній блок вже не є вільним:

Повторне використання старих блоків

Тепер уявімо той самий сценарій, але з однією зміною: наша функція починає шукати вільні блоки з найстарішого. Початкова структура буде така ж...

...і знову звільняємо перший та третій блоки пам'яті:

Цього разу буде використано перший блок:

Тепер, коли ми звільняємо останній блок, ми матимемо два вільні блоки на верху, що дозволяє нам зменшити хіп на два блоки по 8 байт:

Цей приклад ілюструє, як, надаючи пріоритет новим блокам, ми в кінцевому підсумку накопичуємо старі невикористовувані блоки, що призводить до витрат пам'яті і зайвого росту хіпу. Рішення полягає в модифікації стратегії пошуку, надаючи пріоритет повторному використанню старих блоків.

Реалізація пріоритету старих блоків

Щоб вирішити цю проблему, ми почнемо з додавання вказівника на наступний блок у заголовку.
Ми також створимо глобальний вказівник на перший блок, щоб ми могли почати пошук з нього:

typedef struct Header {  
 struct Header *previous, *next;  
 size_t size;  
 bool available;  
} Header;  
Header *first = NULL;  
Header *last = NULL;

Ми створимо блоки пам'яті з заголовками в двох різних ситуаціях, тому давайте зробимо невелике рефакторування: ми винесемо цю логіку в допоміжну функцію, яка виділяє і ініціалізує заголовок (включаючи встановлення поля next в NULL):

Header *header_new(Header *previous, size_t size, bool available) {  
 Header *header = sbrk(sizeof(Header) + size);  
 header->previous = previous;  
 header->next = NULL;  
 header->size = size;  
 header->available = false;  
 return header;  
}

З цією новою функцією ми можемо спростити логіку всередині abmalloc():

void *abmalloc(size_t size) {   
 if (size == 0) {   
 return NULL;   
 }   
 Header *header = last;   
 while (header != NULL) {   
 if (header->available && (header->size >= size)) {   
 header->available = false;   
 return header + 1;   
 }   
 header = header->previous;   
 }   
 last = header_new(last, size, false);   
 return last + 1;   
}

Тепер у нас є доступ до перших і останніх блоків, і маючи блок, ми можемо дізнатися попередній та наступний. Ми також знаємо, що коли вказівник на перший блок дорівнює нулю, жодні блоки ще не були виділені. У такому разі ми виділяємо блок негайно і ініціалізуємо і перший, і останній:

void *abmalloc(size_t size) {   
 if (size == 0) {   
 return NULL;   
 }   
 if (first == NULL) {   
 first = last = header_new(NULL, size, false);   
 return first + 1;   
 }]

Якщо first більше не NULL, це означає, що блоки вже були виділені, і ми почнемо шукати блок, який можна повторно використовувати. Ми будемо використовувати змінну header як ітератор, але замість того, щоб починати з найбільш нового блоку, пошук почнеться з найстарішого:

Header *header = first;

На кожній ітерації ми будемо рухатися до наступного блоку в послідовності, замість того щоб повертатися до попереднього блоку:

while (header != NULL) {   
 if (header->available && (header->size >= size)) {   
 header->available = false;   
 return header + 1;   
 }   
 header = header->next;   
 }

Логіка залишається такою ж: якщо ми знаходимо доступний блок достатнього розміру, він повертається. В іншому випадку, якщо не знайдений жоден блок для повторного використання після того, як ми пройдемо весь список, виділяється новий блок:

last = header_new(last, size, false);

Тепер нам потрібно скоригувати блок, який був останнім (після виділення, це другий з останніх). Він вказував на NULL, але тепер він має вказувати на новий блок. Для цього ми встановлюємо поле next попереднього блоку на новий останній блок:

last->previous->next = last;   
 return last + 1;   
}

Коригування в abfree()

Функція abfree() в основному зберігає ту саму структуру, але тепер ми повинні обробляти деякі крайні випадки. Коли ми звільняємо блоки вгорі хіпу, новий блок стає останнім, як ми вже робимо в цьому фрагменті:

last = header->previous;  
 brk(header)

Тут вказівник header посилається на останній ненульовий блок, що доступний у стеку. У нас є два можливих сценарії:

1. поточний блок має попередній блок, який стане новим останнім блоком. У цьому випадку ми повинні встановити вказівник next цього блоку на NULL.
2. поточний блок не має попереднього блоку (тобто, це перший і найстаріший блок). Коли він звільняється, стек стає порожнім.
   У цьому випадку, замість того щоб намагатися оновити поле неіснуючого блоку, ми просто встановлюємо first в NULL, що вказує на те, що більше немає виділених блоків.

Ось як ми це реалізуємо:

last = header->previous;   
 if (last != NULL) {   
 last->next = NULL;   
 } else {   
 first = NULL;   
 }   
 brk(header);

Висновок

Наші функції abmalloc() та abfree() тепер виглядають ось так:

typedef struct Header {  
 struct Header *previous, *next;  
 size_t size;  
 bool available;  
} Header;  

Header *first = NULL;  
Header *last = NULL;  
Header *header_new(Header *previous, size_t size, bool available) {  
 Header *header = sbrk(sizeof(Header) + size);  
 header->previous = previous;  
 header->next = NULL;  
 header->size = size;  
 header->available = false;  
 return header;  
}  
void *abmalloc(size_t size) {  
 if (size == 0) {  
 return NULL;  
 }  
 if (first == NULL) {  
 first = last = header_new(NULL, size, false);  
 return first + 1;  
 }  
 Header *header = first;  
 while (header != NULL) {  
 if (header->available && (header->size >= size)) {  
 header->available = false;  
 return header + 1;  
 }  
 header = header->next;  
 }  
 last = header_new(last, size, false);  
 last->previous->next = last;  
 return last + 1;  
}  
void abfree(void *ptr) {  
 if (ptr == NULL) {  
 return;  
 }  
 Header *header = (Header*) ptr - 1;  
 if (header == last) {  
 while ((header->previous != NULL) && header->previous->available) {  
 header = header->previous;  
 }  
 last = header->previous;  
 if (last != NULL) {  
 last->next = NULL;  
 } else {  
 first = NULL;  
 }  
 brk(header);  
 } else {  
 header->available = true;  
 }  
 }

Ці зміни дозволяють нам зекономити значно більше пам'яті. Проте, ще залишаються проблеми, які треба вирішити. Наприклад, розглянемо наступний сценарій: ми запитуємо виділення блоку пам'яті розміром 8 байт, а abmalloc() повторно використовує блок, скажімо, 1024 байти. Очевидно, що це є витратою пам'яті.

Ми побачимо, як вирішити цю проблему в наступному пості.

Перекладено з: Implementing malloc() and free() — old memory reused first