Bins & Memory Allocations

Підтримайте HackTricks

Основна інформація

Для покращення ефективності зберігання блоків кожен блок не зберігається лише в одному зв'язаному списку, а існує кілька типів. Це біни, існує 5 типів бінів: 62 малих бінів, 63 великих бінів, 1 неупорядкований бін, 10 швидких бінів та 64 біни tcache на кожен потік.

Початкова адреса кожного неупорядкованого, малого та великого бінів знаходиться в одному масиві. Індекс 0 не використовується, 1 - це неупорядкований бін, біни 2-64 - це малі біни, а біни 65-127 - це великі біни.

Біни кешу Tcache (для кожного потоку)

Навіть якщо потоки намагаються мати свій власний стек (див. Арени та Підстеки), існує можливість того, що процес з великою кількістю потоків (наприклад, веб-сервер) закінчиться спільним стеком з іншими потоками. У цьому випадку основним рішенням є використання замків, які можуть значно уповільнити роботу потоків.

Отже, tcache схожий на швидкий бін на кожен потік тим, що це однозв'язний список, який не об'єднує блоки. Кожен потік має 64 однозв'язних біни tcache. Кожен бін може містити максимум 7 блоків однакового розміру від 24 до 1032 байт на 64-бітних системах та від 12 до 516 байт на 32-бітних системах.

Коли потік вивільняє блок, якщо він не занадто великий для виділення в 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

/*
Fastbins

An array of lists holding recently freed small chunks.  Fastbins
are not doubly linked.  It is faster to single-link them, and
since chunks are never removed from the middles of these lists,
double linking is not necessary. Also, unlike regular bins, they
are not even processed in FIFO order (they use faster LIFO) since
ordering doesn't much matter in the transient contexts in which
fastbins are normally used.

Chunks in fastbins keep their inuse bit set, so they cannot
be consolidated with other free chunks. malloc_consolidate
releases all chunks in fastbins and consolidates them with
other free chunks.
*/

typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)


/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (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)

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > CHUNK_HDR_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)

Функція для вибору між малими та великими блоками:

#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

Великі біни

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

У розподільчій пам'яті великі біни починаються там, де закінчуються малі біни. Діапазони для великих бінів поступово збільшуються, що означає, що перший бін може охоплювати частини від 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

/*
Top

The top-most available chunk (i.e., the one bordering the end of
available memory) is treated specially. It is never included in
any bin, is used only if no other chunk is available, and is
released back to the system if it is very large (see
M_TRIM_THRESHOLD).  Because top initially
points to its own bin with initial zero size, thus forcing
extension on the first malloc request, we avoid having any special
code in malloc to check whether it even exists yet. But we still
need to do so when getting memory from system, so we make
initial_top treat the bin as a legal but unusable chunk during the
interval between initialization and the first call to
sysmalloc. (This is somewhat delicate, since it relies on
the 2 preceding words to be zero during this interval as well.)
*/

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M)              (unsorted_chunks (M))

Зазвичай, це фрагмент, що містить усі доступні у купі пам'яті. Коли виконується malloc і вільний фрагмент для використання відсутній, цей верхній фрагмент буде зменшувати свій розмір, надаючи необхідний простір. Вказівник на Верхній Фрагмент зберігається в структурі malloc_state.

Крім того, спочатку можна використовувати неупорядкований фрагмент як верхній фрагмент.

Останній залишок

Коли використовується malloc і блок розділяється (наприклад, з невпорядкованого баку або з верхнього блоку), блок, створений з решти розділеного блоку, називається Останнім залишком, а його вказівник зберігається в структурі malloc_state.

Потік виділення

Перевірте:

Потік вивільнення

Перевірте:

Перевірки безпеки функцій купи

Перевірте перевірки безпеки, які виконуються в широко використовуваних функціях в купі, в:

Посилання

Last updated