Bins & Memory Allocations

AWS 해킹 학습 및 실습:HackTricks Training AWS Red Team Expert (ARTE) GCP 해킹 학습 및 실습: HackTricks Training GCP Red Team Expert (GRTE)

HackTricks 지원

구독 요금제를 확인하세요!
💬 Discord 그룹 또는 텔레그램 그룹에 참여하거나 트위터 🐦 @hacktricks_live를 팔로우하세요.
HackTricks 및 HackTricks Cloud 깃허브 저장소에 PR을 제출하여 해킹 요령을 공유하세요.

기본 정보

각 청크가 저장되는 효율성을 향상시키기 위해 모든 청크가 하나의 연결된 목록에만 있는 것이 아니라 여러 유형의 bins가 있습니다. 이러한 것들을 bins라고 하며 5 종류의 bins가 있습니다: 62 small bins, 63 large bins, 1 unsorted bin, 10 fast bins 그리고 스레드 당 64개의 tcache bins가 있습니다.

각 unsorted, small, large bins의 초기 주소는 동일한 배열 내에 있습니다. 인덱스 0은 사용되지 않으며, 1은 unsorted bin, bins 2-64는 small bins이고 bins 65-127는 large bins입니다.

Tcache (스레드별 캐시) Bins

스레드는 자체 힙을 가지려고 노력하지만 (Arenas 및 Subheaps 참조), 많은 스레드를 가진 프로세스(예: 웹 서버)는 다른 스레드와 힙을 공유할 수 있습니다. 이 경우, 주요 해결책은 lockers의 사용입니다. 이는 스레드를 상당히 느리게 만들 수 있습니다.

따라서 tcache는 각 스레드 당 하나의 fast bin과 유사합니다. 이는 청크를 병합하지 않는 단일 연결 목록입니다. 각 스레드에는 64개의 단일 연결 tcache bins가 있습니다. 각 bin은 64비트 시스템에서 24에서 1032바이트, 32비트 시스템에서 12에서 516바이트 범위 내의 최대 7개의 동일한 크기 청크를 가질 수 있습니다.

스레드가 청크를 해제할 때, 그것이 tcache에 할당되기에 너무 크지 않고 해당 tcache bin이 가득 차지 않았다면 (이미 7개의 청크가 있는 경우), 거기에 할당될 것입니다. tcache로 이동할 수 없는 경우, 전역 bins에서 찾거나 새로 생성하기 위해 힙 잠금을 기다려야 합니다. 청크가 할당될 때, Tcache에 필요한 크기의 무료 청크가 있는 경우 사용하고, 그렇지 않으면 힙 잠금을 기다려 전역 bins에서 찾거나 새로 생성해야 합니다. 또한 최적화가 있으며, 이 경우 힙 잠금을 사용하는 동안 스레드는 요청된 크기의 힙 청크(7개)로 Tcache를 채우므로 필요한 경우 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 옵코드에 중단점을 설정하여 디버깅합니다. 그런 다음 gef를 사용하여 사용 중인 tcache bin을 볼 수 있습니다:
```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 구조체 및 함수

다음 코드에서는 최대 bins 및 인덱스 당 청크 수, 이중 해제를 피하기 위해 생성된 tcache_entry 구조체, 그리고 각 스레드가 각 bin의 주소를 저장하는 데 사용하는 tcache_perthread_struct 구조체를 볼 수 있습니다.

```c // From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c

/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */

define TCACHE_MAX_BINS 64

define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1)

/* Only used to pre-fill the tunables. */

define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

/* When "x" is from chunksize(). */

define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)

/* When "x" is a user-provided size. */

define usize2tidx(x) csize2tidx (request2size (x))

/* With rounding and alignment, the bins are... idx 0 bytes 0..24 (64-bit) or 0..12 (32-bit) idx 1 bytes 25..40 or 13..20 idx 2 bytes 41..56 or 21..28 etc. */

/* This is another arbitrary limit, which tunables can change. Each tcache bin will hold at most this number of chunks. */

define TCACHE_FILL_COUNT 7

/* Maximum chunks in tcache bins for tunables. This value must fit the range of tcache->counts[] entries, else they may overflow. */

define MAX_TCACHE_COUNT UINT16_MAX

[...]

typedef struct tcache_entry { struct tcache_entry next; / This field exists to detect double frees. */ uintptr_t key; } tcache_entry;

/* There is one of these for each thread, which contains the per-thread cache (hence "tcache_perthread_struct"). Keeping overall size low is mildly important. Note that COUNTS and ENTRIES are redundant (we could have just counted the linked list each time), this is for performance reasons. */ typedef struct tcache_perthread_struct { uint16_t counts[TCACHE_MAX_BINS]; tcache_entry *entries[TCACHE_MAX_BINS]; } tcache_perthread_struct;

</details>

`__tcache_init` 함수는 `tcache_perthread_struct` obj의 공간을 생성하고 할당하는 함수입니다.

<details>

<summary>tcache_init 코드</summary>
```c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3241C1-L3274C2

static void
tcache_init(void)
{
mstate ar_ptr;
void *victim = 0;
const size_t bytes = sizeof (tcache_perthread_struct);

if (tcache_shutting_down)
return;

arena_get (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
if (!victim && ar_ptr != NULL)
{
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}


if (ar_ptr != NULL)
__libc_lock_unlock (ar_ptr->mutex);

/* In a low memory situation, we may not be able to allocate memory
- in which case, we just keep trying later.  However, we
typically do this very early, so either there is sufficient
memory, or there isn't enough memory to do non-trivial
allocations anyway.  */
if (victim)
{
tcache = (tcache_perthread_struct *) victim;
memset (tcache, 0, sizeof (tcache_perthread_struct));
}

}

Tcache Indexes

티캐시에는 크기에 따라 여러 개의 bin이 있으며 각 인덱스의 첫 번째 청크를 가리키는 초기 포인터와 인덱스 당 청크 수가 청크 내부에 위치합니다. 이는 이 정보를 포함하는 청크(일반적으로 첫 번째 청크)를 찾으면 모든 티캐시 초기 포인트와 Tcache 청크 수를 찾을 수 있다는 것을 의미합니다.

Fast bins

Fast bins는 작은 청크에 대한 메모리 할당 속도를 높이기 위해 최근에 해제된 청크를 빠른 액세스 구조에 유지함으로써 설계되었습니다. 이러한 bin은 후입선출(LIFO) 방식을 사용하며, 새로운 할당 요청이 있을 때 가장 최근에 해제된 청크가 재사용되는 첫 번째가 됩니다. 이 동작은 속도 측면에서 유리하며, 후입선출(LIFO) 스택의 맨 위에 삽입하고 제거하는 것이 선입선출(FIFO) 큐보다 빠릅니다.

게다가 fast bins는 단일 연결 리스트를 사용하며 이는 속도를 더 향상시킵니다. Fast bins의 청크는 이웃과 병합되지 않기 때문에 중간에서 제거할 수 있는 복잡한 구조가 필요하지 않습니다. 단일 연결 리스트는 이러한 작업에 대해 더 간단하고 빠릅니다.

기본적으로 여기서 발생하는 일은 헤더(확인할 첫 번째 청크를 가리키는 포인터)가 항상 해당 크기의 최신 해제된 청크를 가리키고 있다는 것입니다. 그래서:

해당 크기의 새로운 청크가 할당되면, 헤더는 사용할 수 있는 무료 청크를 가리킵니다. 이 무료 청크가 사용할 다음 청크를 가리키고 있기 때문에, 이 주소는 헤더에 저장되어 다음 할당이 사용 가능한 청크를 어디서 가져올지 알 수 있습니다.
청크가 해제되면, 무료 청크는 현재 사용 가능한 청크의 주소를 저장하고, 이 새로 해제된 청크의 주소가 헤더에 넣어집니다.

연결 리스트의 최대 크기는 0x80이며, 청크의 크기가 0x20인 경우 인덱스 0에, 크기가 0x30인 경우 인덱스 1에 위치합니다.

Fast bins의 청크는 사용 가능하게 설정되지 않으므로 주변의 다른 무료 청크와 병합할 수 있는 대신 어느 정도의 시간 동안 fast bin 청크로 유지됩니다.

// 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)

빠른 바인 청크 예제 추가

```c #include #include

int main(void) { char *chunks[8]; int i;

// Loop to allocate memory 8 times for (i = 0; i < 8; i++) { chunks[i] = malloc(24); if (chunks[i] == NULL) { // Check if malloc failed fprintf(stderr, "Memory allocation failed at iteration %d\n", i); return 1; } printf("Address of chunk %d: %p\n", i, (void *)chunks[i]); }

// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }

return 0; }

참고로 동일한 크기의 8개 청크를 할당하고 해제하는 방법을 살펴보세요. 이렇게 하면 tcache가 가득 차고 여덟 번째 청크는 fast 청크에 저장됩니다.

컴파일하고 `main` 함수의 `ret` 옵코드에서 중단점을 설정하여 디버깅하세요. 그런 다음 `gef`를 사용하여 tcache bin이 가득 찼고 하나의 청크가 fast bin에 있는 것을 볼 수 있습니다:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=7] ←  Chunk(addr=0xaaaaaaac1770, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1750, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1730, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1710, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac16f0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac16d0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20]  ←  Chunk(addr=0xaaaaaaac1790, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
Fastbins[idx=1, size=0x30] 0x00

Unsorted bin

Unsorted bin은 힙 매니저가 메모리 할당을 빠르게 만들기 위해 사용하는 캐시입니다. 다음은 그 작동 방식입니다: 프로그램이 청크를 해제하면서, 이 청크가 tcache나 fast bin에 할당될 수 없고 top 청크와 충돌하지 않는 경우, 힙 매니저는 즉시 특정 small 또는 large bin에 넣지 않습니다. 대신, 먼저 이웃하는 다른 빈 청크와 병합하여 더 큰 빈 메모리 블록을 만들려고 합니다. 그런 다음, 이 새로운 청크를 "unsorted bin"이라고 불리는 일반적인 bin에 넣습니다.

프로그램이 메모리를 요청할 때, 힙 매니저는 unsorted bin을 확인하여 충분한 크기의 청크가 있는지 확인합니다. 하나를 찾으면 즉시 사용합니다. unsorted bin에서 적합한 청크를 찾지 못하면, 이 목록의 모든 청크를 해당 크기에 따라 소형 또는 대형 bin으로 이동시킵니다.

더 큰 청크가 2개의 반으로 나뉘고 나머지가 MINSIZE보다 크면, unsorted bin에 다시 넣습니다.

따라서 unsorted bin은 최근에 해제된 메모리를 빠르게 재사용하여 메모리 할당을 가속화하고, 시간이 많이 소요되는 검색 및 병합 필요성을 줄입니다.

다른 카테고리의 청크이더라도 사용 가능한 청크가 다른 사용 가능한 청크와 충돌하는 경우 (원래 서로 다른 bin에 속해 있더라도), 병합됩니다.

unsorted chunk 예제 추가

```c #include #include

int main(void) { char *chunks[9]; int i;

// Loop to allocate memory 8 times for (i = 0; i < 9; i++) { chunks[i] = malloc(0x100); if (chunks[i] == NULL) { // Check if malloc failed fprintf(stderr, "Memory allocation failed at iteration %d\n", i); return 1; } printf("Address of chunk %d: %p\n", i, (void *)chunks[i]); }

// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }

return 0; }

**동일한 크기의 9개 청크를 할당하고 해제하는 방법에 주목하세요. 이렇게 하면 tcache를 채우고 여덟 번째 청크는 fastbin에 너무 크기 때문에 unsorted bin에 저장되며 아홉 번째 청크는 해제되지 않아서 아홉 번째와 여덟 번째가 top chunk와 병합되지 않습니다.**

`main` 함수의 `ret` 옵코드에서 중단점을 설정하여 컴파일하고 디버깅합니다. 그런 다음 `gef`를 사용하여 tcache bin이 가득 찼고 하나의 청크가 unsorted bin에 있는 것을 볼 수 있습니다:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=15, size=0x110, count=7] ←  Chunk(addr=0xaaaaaaac1d10, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1c00, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1af0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac19e0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac18d0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac17c0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] unsorted_bins[0]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→   Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in unsorted bin.

작은 Bins

작은 Bins은 큰 Bins보다 빠르지만 fast bins보다는 느립니다.

62개의 각 bin은 동일한 크기의 청크를 가집니다: 16, 24, ... (32비트에서는 최대 504바이트, 64비트에서는 1024바이트). 이는 공간이 할당되어야 하는 bin을 찾고 이러한 목록에 항목을 삽입하고 제거하는 속도에 도움이 됩니다.

작은 bin의 크기는 bin의 인덱스에 따라 다음과 같이 계산됩니다:

가장 작은 크기: 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))

작은 청크 예시 추가

```c #include #include

int main(void) { char *chunks[10]; int i;

// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }

chunks[9] = malloc(0x110);

return 0; }

9개의 동일한 크기의 청크를 할당하고 해제하는 방법에 주목하십시오. 이렇게 하면 **tcache가 가득 차게** 되고 여덟 번째 청크는 **fastbin에 너무 크기 때문에** unsorted bin에 저장됩니다. 아홉 번째 청크는 해제되지 않으므로 아홉 번째와 여덟 번째는 **top 청크와 병합되지 않습니다**. 그런 다음 0x110 크기의 더 큰 청크를 할당하면 **unsorted bin의 청크가 small bin으로 이동**합니다.

이를 컴파일하고 `main` 함수의 `ret` 옵코드에서 중단점을 설정하여 디버깅합니다. 그런 다음 `gef`를 사용하여 tcache bin이 가득 차고 한 개의 청크가 small bin에 있는 것을 볼 수 있습니다:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=15, size=0x110, count=7] ←  Chunk(addr=0xaaaaaaac1d10, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1c00, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac1af0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac19e0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac18d0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac17c0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  Chunk(addr=0xaaaaaaac12a0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] small_bins[16]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→   Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in 1 small non-empty bins.

대형 bins

작은 bins가 고정된 크기의 청크를 관리하는 반면, 각 대형 bin은 청크 크기 범위를 처리합니다. 이는 더 유연하며, 시스템이 다양한 크기를 수용할 수 있도록 하여 각 크기마다 별도의 bin이 필요하지 않습니다.

메모리 할당기에서 대형 bins는 작은 bins가 끝나는 곳에서 시작합니다. 대형 bins의 범위는 점진적으로 커지며, 첫 번째 bin은 512에서 576바이트의 청크를 포함할 수 있으며, 다음 bin은 576에서 640바이트를 포함할 수 있습니다. 이 패턴은 계속되어, 가장 큰 bin은 1MB 이상의 모든 청크를 포함합니다.

대형 bins는 작은 bins보다 작업 속도가 느립니다. 왜냐하면 할당에 최적의 적합한 청크를 찾기 위해 다양한 청크 크기 목록을 정렬하고 검색해야하기 때문입니다. 대형 bin에 청크가 삽입되면 정렬되어야 하며, 메모리가 할당될 때 시스템은 적절한 청크를 찾아야 합니다. 이 추가 작업으로 인해 느려지지만, 대형 할당이 작은 할당보다 적기 때문에 수용할 만한 트레이드오프입니다.

다음과 같은 대형 bins가 있습니다:

64B 범위의 32개 bins (작은 bins와 충돌)
512B 범위의 16개 bins (작은 bins와 충돌)
4096B 범위의 8개 bins (일부는 작은 bins와 충돌)
32768B 범위의 4개 bins
262144B 범위의 2개 bins
나머지 크기를 위한 1개 bin

대형 bin 크기 코드

```c // From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

#define largebin_index_32(sz) (((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) : ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) : ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) : ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) : ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) : 126)

#define largebin_index_32_big(sz) (((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) : ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) : ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) : ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) : ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) : 126)

// XXX It remains to be seen whether it is good to keep the widths of // XXX the buckets the same or whether it should be scaled by a factor // XXX of two as well. #define largebin_index_64(sz) (((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) : ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) : ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) : ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) : ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) : 126)

#define largebin_index(sz) (SIZE_SZ == 8 ? largebin_index_64 (sz) : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) : largebin_index_32 (sz))

</details>

<details>

<summary>대규모 청크 예제 추가</summary>
```c
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
char *chunks[2];

chunks[0] = malloc(0x1500);
chunks[1] = malloc(0x1500);
free(chunks[0]);
chunks[0] = malloc(0x2000);

return 0;
}

2개의 큰 할당이 수행되고, 그 중 하나가 해제됩니다 (unsorted bin에 넣음) 그리고 더 큰 할당이 이루어집니다 (unsorted bin에서 large bin으로 이동됨).

이를 컴파일하고 main 함수의 ret 옵코드에 중단점을 걸어 디버깅합니다. 그런 다음 gef를 사용하여 tcache bin이 가득 차 있고 하나의 청크가 large bin에 있는 것을 볼 수 있습니다:

gef➤  heap bin
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
All tcachebins are empty
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
──────────────────────────────────────────────────────────────────────── Large Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] large_bins[100]: fw=0xaaaaaaac1290, bk=0xaaaaaaac1290
→   Chunk(addr=0xaaaaaaac12a0, size=0x1510, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in 1 large non-empty bins.

최상위 청크

// 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 구조체에 저장됩니다.

또한, 처음에는 정렬되지 않은 청크를 최상위 청크로 사용할 수 있습니다.

최상위 청크 예시 관찰

```c #include #include

int main(void) { char *chunk; chunk = malloc(24); printf("Address of the chunk: %p\n", (void *)chunk); gets(chunk); return 0; }

컴파일하고 `main`의 `ret` 옵코드에서 중단점을 걸고 디버깅한 후 malloc이 주소 `0xaaaaaaac12a0`을 반환하는 것을 확인했고, 다음은 청크들입니다:
```bash
gef➤  heap chunks
Chunk(addr=0xaaaaaaac1010, size=0x290, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac1010     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12a0     41 41 41 41 41 41 41 00 00 00 00 00 00 00 00 00    AAAAAAA.........]
Chunk(addr=0xaaaaaaac12c0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12c0     41 64 64 72 65 73 73 20 6f 66 20 74 68 65 20 63    Address of the c]
Chunk(addr=0xaaaaaaac16d0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac16d0     41 41 41 41 41 41 41 0a 00 00 00 00 00 00 00 00    AAAAAAA.........]
Chunk(addr=0xaaaaaaac1ae0, size=0x20530, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)  ←  top chunk

최상위 청크가 주소 0xaaaaaaac1ae0에 있는 것을 확인할 수 있습니다. 마지막 할당된 청크가 0xaaaaaaac12a0에 크기가 0x410인 것이었기 때문에 이는 놀라운 사실이 아닙니다. 0xaaaaaaac12a0 + 0x410 = 0xaaaaaaac1ae0입니다. 또한 최상위 청크의 길이를 청크 헤더에서 확인할 수도 있습니다:

gef➤  x/8wx 0xaaaaaaac1ae0 - 16
0xaaaaaaac1ad0:	0x00000000	0x00000000	0x00020531	0x00000000
0xaaaaaaac1ae0:	0x00000000	0x00000000	0x00000000	0x00000000