Для покращення ефективності зберігання блоків кожен блок не зберігається лише в одному зв'язаному списку, а існує кілька типів. Це біни, існує 5 типів бінів: 62 малих бінів, 63 великих бінів, 1 неупорядкований бін, 10 швидких бінів та 64 біни tcache на кожен потік.
Початкова адреса кожного неупорядкованого, малого та великого бінів знаходиться в одному масиві. Індекс 0 не використовується, 1 - це неупорядкований бін, біни 2-64 - це малі біни, а біни 65-127 - це великі біни.
Біни кешу Tcache (для кожного потоку)
Навіть якщо потоки намагаються мати свій власний стек (див. Арени та Підстеки), існує можливість того, що процес з великою кількістю потоків (наприклад, веб-сервер) закінчиться спільним стеком з іншими потоками. У цьому випадку основним рішенням є використання замків, які можуть значно уповільнити роботу потоків.
Коли потік вивільняє блок, якщо він не занадто великий для виділення в tcache та відповідний бін tcache не заповнений (вже 7 блоків), він буде виділений туди. Якщо він не може перейти до tcache, йому доведеться зачекати, поки стек буде розблокований, щоб виконати операцію вивільнення глобально.
Коли блок виділяється, якщо є вільний блок потрібного розміру в Tcache, він використовує його, якщо немає, йому доведеться зачекати, поки стек буде розблокований, щоб знайти його в глобальних бінах або створити новий.
Тут також є оптимізація, в цьому випадку, під час блокування стеку, потік заповнить свій Tcache блоками стеку (7) потрібного розміру, тому в разі потреби він знайде їх в Tcache.
Приклад додавання блоку tcache
```c #include #include
int main(void) { char *chunk; chunk = malloc(24); printf("Address of the chunk: %p\n", (void *)chunk); gets(chunk); free(chunk); return 0; }
Зкомпілюйте його та відлагодьте його з точкою зупинки в опкоді ret з функції main. Потім за допомогою gef ви можете побачити використання біна tcache:
```bash
gef➤ heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=1] ← Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
Структури та Функції Tcache
У наступному коді можна побачити максимальні біни та частки на індекс, створену структуру tcache_entry для уникнення подвійних вивільнень та tcache_perthread_struct, структуру, яку кожен потік використовує для зберігання адрес кожного індексу біна.
Індекси Tcache
Tcache має кілька блоків в залежності від розміру та початкові вказівники на перший фрагмент кожного індексу та кількість фрагментів на кожен індекс розташовані всередині фрагмента. Це означає, що знаходячи фрагмент з цією інформацією (зазвичай перший), можна знайти всі початкові точки tcache та кількість фрагментів Tcache.
Швидкі блоки
Швидкі блоки призначені для прискорення виділення пам'яті для невеликих фрагментів, тримаючи недавно звільнені фрагменти в швидкодійній структурі. Ці блоки використовують підхід "Останнім прийшов - першим вийшов" (LIFO), що означає, що останній звільнений фрагмент перший, який буде використаний при новому запиті на виділення. Ця поведінка є вигідною для швидкості, оскільки швидше вставляти та видаляти з верхушки стеку (LIFO) порівняно з чергою (FIFO).
Крім того, швидкі блоки використовують однозв'язні списки, а не двозв'язні, що подальше покращує швидкість. Оскільки фрагменти в швидких блоках не об'єднуються з сусідніми, немає потреби в складній структурі, яка дозволяє видалення з середини. Однозв'язний список є простішим та швидшим для цих операцій.
Основна ідея полягає в тому, що заголовок (вказівник на перший фрагмент для перевірки) завжди вказує на останній звільнений фрагмент такого розміру. Таким чином:
Коли виділяється новий фрагмент такого розміру, заголовок вказує на вільний фрагмент для використання. Оскільки цей вільний фрагмент вказує на наступний для використання, ця адреса зберігається в заголовку, щоб наступне виділення знало, де отримати доступний фрагмент.
Коли фрагмент звільняється, вільний фрагмент збереже адресу поточного доступного фрагмента, а адреса цього ново звільненого фрагмента буде поміщена в заголовок.
Максимальний розмір зв'язаного списку - 0x80, і вони організовані так, що фрагмент розміром 0x20 буде в індексі 0, фрагмент розміром 0x30 буде в індексі 1...
Фрагменти в швидких блоках не встановлені як доступні, тому вони залишаються як швидкі блоки протягом певного часу замість можливості об'єднання з іншими вільними фрагментами, які оточують їх.
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711/*FastbinsAn array of lists holding recently freed small chunks. Fastbinsare not doubly linked. It is faster to single-link them, andsince chunks are never removed from the middles of these lists,double linking is not necessary. Also, unlike regular bins, theyare not even processed in FIFO order (they use faster LIFO) sinceordering doesn't much matter in the transient contexts in whichfastbins are normally used.Chunks in fastbins keep their inuse bit set, so they cannotbe consolidated with other free chunks. malloc_consolidatereleases all chunks in fastbins and consolidates them withother free chunks.*/typedefstruct malloc_chunk *mfastbinptr;#definefastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])/* offset 2 to use otherwise unindexable first 2 bins */#definefastbin_index(sz) \((((unsignedint) (sz)) >> (SIZE_SZ ==8?4:3)) -2)/* The maximum fastbin request size we support */#defineMAX_FAST_SIZE (80* SIZE_SZ /4)#defineNFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) +1)
Невідсортований бін
Невідсортований бін - це кеш, який використовує менеджер купи для прискорення виділення пам'яті. Ось як це працює: коли програма звільняє фрагмент, і якщо цей фрагмент не може бути виділений в tcache або fast bin і не конфліктує з верхнім фрагментом, менеджер купи не відразу поміщає його в певний малий або великий бін. Замість цього він спочатку намагається об'єднати його з будь-якими сусідніми вільними фрагментами, щоб створити більший блок вільної пам'яті. Потім він поміщає цей новий фрагмент в загальний бін, який називається "невідсортований бін".
Коли програма потребує пам'яті, менеджер купи перевіряє невідсортований бін, щоб побачити, чи є там достатньо великий фрагмент. Якщо він знаходить один, він використовує його відразу. Якщо не знаходить підходящого фрагмента в невідсортованому біні, він переміщає всі фрагменти у цьому списку до відповідних бінів, або малих, або великих, в залежності від їх розміру.
Зверніть увагу, що якщо більший фрагмент розбивається на 2 половини, і решта більша за MINSIZE, його буде повернуто назад у невідсортований бін.
Отже, невідсортований бін - це спосіб прискорити виділення пам'яті шляхом швидкого повторного використання недавно звільненої пам'яті та зменшення потреби в часовитратних пошуках та об'єднаннях.
Зверніть увагу, що навіть якщо фрагменти належать до різних категорій, якщо доступний фрагмент конфліктує з іншим доступним фрагментом (навіть якщо вони початково належать до різних бінів), вони будуть об'єднані.
Малі біни
Малі біни швидші за великі біни, але повільніші за швидкі біни.
Кожен бін з 62 матиме частини одного розміру: 16, 24, ... (з максимальним розміром 504 байти в 32-бітних системах та 1024 в 64-бітних). Це допомагає прискорити пошук біна, де має бути виділено місце, а також вставку та видалення записів у цих списках.
Ось як розраховується розмір малого біна в залежності від індексу біна:
Найменший розмір: 2*4*індекс (наприклад, індекс 5 -> 40)
Найбільший розмір: 2*8*індекс (наприклад, індекс 5 -> 80)
На відміну від малих бінів, які керують частинами фіксованих розмірів, кожен великий бін обробляє діапазон розмірів частин. Це більш гнучко, дозволяючи системі пристосовуватися до різних розмірів без необхідності окремого біна для кожного розміру.
У розподільчій пам'яті великі біни починаються там, де закінчуються малі біни. Діапазони для великих бінів поступово збільшуються, що означає, що перший бін може охоплювати частини від 512 до 576 байтів, тоді як наступний охоплює від 576 до 640 байтів. Ця модель продовжується, і найбільший бін містить всі частини понад 1 МБ.
Великі біни повільніше працюють порівняно з малими бінами, оскільки їм потрібно сортувати та шукати через список різних розмірів частин, щоб знайти найкраще відповідне для виділення. Коли частина вставляється в великий бін, її потрібно відсортувати, а коли виділяється пам'ять, системі потрібно знайти відповідну частину. Ця додаткова робота робить їх повільнішими, але оскільки великі виділення менш поширені, це прийнятний компроміс.
Є:
32 біни діапазону 64 байти (збігаються з малими бінами)
16 бінів діапазону 512 байтів (збігаються з малими бінами)
8 бінів діапазону 4096 байтів (частково збігаються з малими бінами)
4 біни діапазону 32768 байтів
2 біни діапазону 262144 байти
1 бін для залишкових розмірів
Верхній Чанк
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711/*TopThe top-most available chunk (i.e., the one bordering the end ofavailable memory) is treated specially. It is never included inany bin, is used only if no other chunk is available, and isreleased back to the system if it is very large (seeM_TRIM_THRESHOLD). Because top initiallypoints to its own bin with initial zero size, thus forcingextension on the first malloc request, we avoid having any specialcode in malloc to check whether it even exists yet. But we stillneed to do so when getting memory from system, so we makeinitial_top treat the bin as a legal but unusable chunk during theinterval between initialization and the first call tosysmalloc. (This is somewhat delicate, since it relies onthe 2 preceding words to be zero during this interval as well.)*//* Conveniently, the unsorted bin can be used as dummy top on first call */#defineinitial_top(M) (unsorted_chunks (M))
Зазвичай, це фрагмент, що містить усі доступні у купі пам'яті. Коли виконується malloc і вільний фрагмент для використання відсутній, цей верхній фрагмент буде зменшувати свій розмір, надаючи необхідний простір. Вказівник на Верхній Фрагмент зберігається в структурі malloc_state.
Крім того, спочатку можна використовувати неупорядкований фрагмент як верхній фрагмент.
Останній залишок
Коли використовується malloc і блок розділяється (наприклад, з невпорядкованого баку або з верхнього блоку), блок, створений з решти розділеного блоку, називається Останнім залишком, а його вказівник зберігається в структурі malloc_state.
Потік виділення
Перевірте:
Потік вивільнення
Перевірте:
Перевірки безпеки функцій купи
Перевірте перевірки безпеки, які виконуються в широко використовуваних функціях в купі, в:
