malloc & sysmalloc

HackTricks 지원

할당 순서 요약

(이 요약에서는 검사 과정을 설명하지 않고 일부 경우를 생략했습니다)

  1. __libc_malloc은 tcache에서 청크를 가져오려고 시도하며, 없는 경우 _int_malloc을 호출합니다.

  2. _int_malloc:

    1. 아레나를 생성하려고 시도합니다.

    2. 올바른 크기의 fast bin 청크가 있는 경우 사용합니다.

      1. 다른 fast 청크로 tcache를 채웁니다.

    3. 올바른 크기의 small bin 청크가 있는 경우 사용합니다.

      1. 해당 크기의 다른 청크로 tcache를 채웁니다.

    4. 요청된 크기가 small bin용이 아닌 경우, fast bin을 unsorted bin으로 병합합니다.

    5. unsorted bin을 확인하고, 충분한 공간이 있는 첫 번째 청크를 사용합니다.

      1. 찾은 청크가 더 큰 경우, 해당 부분을 반환하고 나머지를 unsorted bin에 추가합니다.

      2. 요청된 크기와 동일한 크기의 청크인 경우, 반환 대신 tcache를 채우기 위해 사용합니다 (tcache가 가득 차면 다음 청크를 반환합니다).

      3. 확인한 작은 크기의 각 청크에 대해 해당하는 small 또는 large bin에 넣습니다.

    6. 요청된 크기의 인덱스에서 large bin을 확인합니다.

      1. 요청된 크기보다 큰 첫 번째 청크부터 검색을 시작하고, 찾은 경우 해당 청크를 반환하고 나머지를 small bin에 추가합니다.

    7. 끝까지 다음 인덱스의 large bin을 확인합니다.

      1. 다음 큰 인덱스부터 청크를 확인하고, 첫 번째 찾은 청크를 사용하여 요청된 크기에 대해 사용하고 나머지를 unsorted bin에 추가합니다.

    8. 이전 bin에서 아무것도 찾지 못한 경우, 최상위 청크에서 청크를 가져옵니다.

    9. 최상위 청크가 충분히 크지 않은 경우 sysmalloc을 사용하여 확장합니다.

__libc_malloc

malloc 함수는 실제로 __libc_malloc을 호출합니다. 이 함수는 원하는 크기의 사용 가능한 청크가 tcache에 있는지 확인합니다. 해당 청크가 있는 경우 사용하고, 그렇지 않은 경우 단일 스레드인지 확인하고 그 경우에는 메인 아레나에서 _int_malloc을 호출하며, 그렇지 않은 경우 스레드의 아레나에서 _int_malloc을 호출합니다.

__libc_malloc 코드

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

#if IS_IN (libc) void * __libc_malloc (size_t bytes) { mstate ar_ptr; void *victim;

_Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2, "PTRDIFF_MAX is not more than half of SIZE_MAX");

if (!__malloc_initialized) ptmalloc_init (); #if USE_TCACHE /* int_free also calls request2size, be careful to not pad twice. */ size_t tbytes = checked_request2size (bytes); if (tbytes == 0) { __set_errno (ENOMEM); return NULL; } size_t tc_idx = csize2tidx (tbytes);

MAYBE_INIT_TCACHE ();

DIAG_PUSH_NEEDS_COMMENT; if (tc_idx < mp_.tcache_bins && tcache != NULL && tcache->counts[tc_idx] > 0) { victim = tcache_get (tc_idx); return tag_new_usable (victim); } DIAG_POP_NEEDS_COMMENT; #endif

if (SINGLE_THREAD_P) { victim = tag_new_usable (_int_malloc (&main_arena, bytes)); assert (!victim || chunk_is_mmapped (mem2chunk (victim)) || &main_arena == arena_for_chunk (mem2chunk (victim))); return victim; }

arena_get (ar_ptr, bytes);

victim = _int_malloc (ar_ptr, bytes); /* Retry with another arena only if we were able to find a usable arena before. */ if (!victim && ar_ptr != NULL) { LIBC_PROBE (memory_malloc_retry, 1, bytes); ar_ptr = arena_get_retry (ar_ptr, bytes); victim = _int_malloc (ar_ptr, bytes); }

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

victim = tag_new_usable (victim);

assert (!victim || chunk_is_mmapped (mem2chunk (victim)) || ar_ptr == arena_for_chunk (mem2chunk (victim))); return victim; }

</details>

다음은 코드에서 항상 반환된 포인터에 `tag_new_usable` 태그가 지정됨을 주목하세요:
```c
void *tag_new_usable (void *ptr)

Allocate a new random color and use it to color the user region of
a chunk; this may include data from the subsequent chunk's header
if tagging is sufficiently fine grained.  Returns PTR suitably
recolored for accessing the memory there.

_int_malloc

이 함수는 다른 bins와 top chunk를 사용하여 메모리를 할당하는 함수입니다.

  • 시작

일부 변수를 정의하고 요청된 메모리 공간이 가져야 하는 실제 크기를 얻는 것으로 시작합니다:

Fast Bin

필요한 크기가 Fast Bins 크기 내에 있는 경우, fast bin에서 청크를 사용하려고 시도합니다. 기본적으로 크기에 따라 유효한 청크가 위치해야 하는 fast bin 인덱스를 찾고, 그 중 하나를 반환합니다. 또한, tcache가 활성화된 경우 해당 크기의 tcache bin을 fast bins로 채웁니다.

이러한 작업을 수행하는 동안 여기에서 일부 보안 검사가 실행됩니다:

  • 청크가 정렬되지 않은 경우: malloc(): unaligned fastbin chunk detected 2

  • 전방 청크가 정렬되지 않은 경우: malloc(): unaligned fastbin chunk detected

  • fast bin 내의 인덱스 때문에 반환된 청크의 크기가 올바르지 않은 경우: malloc(): memory corruption (fast)

  • tcache를 채우기 위해 사용된 어떤 청크가 정렬되지 않은 경우: malloc(): unaligned fastbin chunk detected 3

malloc_consolidate

만약 작은 청크가 아니라면, 큰 청크이며, 이 경우 메모리 단편화를 피하기 위해 **malloc_consolidate**가 호출됩니다.

Unsorted bin

잠재적으로 유효한 청크를 사용하기 위해 unsorted bin을 확인할 때입니다.

시작

이것은 bk 방향으로 unsorted bin을 탐색할 for 루프로 시작됩니다. while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))와 같이 끝 (arena 구조체)에 도달할 때까지 계속 진행합니다.

또한, 새로운 청크가 고려될 때마다 일부 보안 검사가 수행됩니다:

  • 청크 크기가 이상할 경우 (너무 작거나 너무 큼): malloc(): invalid size (unsorted)

  • 다음 청크 크기가 이상할 경우 (너무 작거나 너무 큼): malloc(): invalid next size (unsorted)

  • 다음 청크가 표시하는 이전 크기가 청크의 크기와 다른 경우: malloc(): mismatching next->prev_size (unsorted)

  • victim->bck->fd == victim 또는 victim->fd == av (arena)가 아닌 경우: malloc(): unsorted double linked list corrupted

  • 항상 마지막 것을 확인하고 있기 때문에, fd는 항상 arena 구조체를 가리켜야 합니다.

  • 다음 청크가 이전이 사용 중이 아님을 나타내지 않는 경우: malloc(): invalid next->prev_inuse (unsorted)

성공적이었다면, 청크를 반환하고 끝내고, 그렇지 않으면 함수를 계속 실행합니다...

사이즈가 같은 경우

요청된 사이즈가 청크의 사이즈와 정확히 같은 경우, 해당 청크를 bin에서 제거하도록 계속합니다:

  • tcache가 비어있지 않은 경우, tcache에 추가하고 tcache 청크를 사용할 수 있다는 것을 계속 나타냅니다.

  • tcache가 가득 찬 경우, 그냥 사용하여 반환합니다.

_int_malloc 제한 사항

이 시점에서 사용 가능한 tcache에 저장된 어떤 청크가 있고 제한이 도달했다면, tcache 청크를 반환합니다.

또한, MAX_ITERS에 도달하면 루프를 탈출하고 다른 방법으로 청크를 얻습니다 (top chunk).

return_cached가 설정된 경우, 더 큰 검색을 피하기 위해 tcache에서 청크를 반환합니다.

적합한 청크를 찾지 못한 경우 계속 진행합니다.

Large Bin (다음으로 큰)

정확한 대형 빈 안에 사용할 수있는 청크가 없는 경우, 모든 다음 대형 빈을 순환하면서 (즉시 더 큰 것부터 시작하여) 하나를 찾을 때까지 계속합니다.

나누어진 청크의 나머지는 정렬되지 않은 빈에 추가되고, last_reminder가 업데이트되며 동일한 보안 검사가 수행됩니다:

  • bck->fd-> bk != bck: malloc(): corrupted unsorted chunks2

sysmalloc

sysmalloc 시작

만약 arena가 null이거나 요청된 크기가 너무 크면 (그리고 허용된 mmaps가 남아있는 경우) 공간을 할당하고 반환하기 위해 sysmalloc_mmap을 사용합니다.

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

/*
sysmalloc handles malloc cases requiring more memory from the system.
On entry, it is assumed that av->top does not have enough
space to service request for nb bytes, thus requiring that av->top
be extended or replaced.
*/

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
mchunkptr old_top;              /* incoming value of av->top */
INTERNAL_SIZE_T old_size;       /* its size */
char *old_end;                  /* its end address */

long size;                      /* arg to first MORECORE or mmap call */
char *brk;                      /* return value from MORECORE */

long correction;                /* arg to 2nd MORECORE call */
char *snd_brk;                  /* 2nd return val */

INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
char *aligned_brk;              /* aligned offset into brk */

mchunkptr p;                    /* the allocated/returned chunk */
mchunkptr remainder;            /* remainder from allocation */
unsigned long remainder_size;   /* its size */


size_t pagesize = GLRO (dl_pagesize);
bool tried_mmap = false;


/*
If have mmap, and the request size meets the mmap threshold, and
the system supports mmap, and there are few enough currently
allocated mmapped regions, try to directly map this request
rather than expanding top.
*/

if (av == NULL
|| ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
&& (mp_.n_mmaps < mp_.n_mmaps_max)))
{
char *mm;
if (mp_.hp_pagesize > 0 && nb >= mp_.hp_pagesize)
{
/* There is no need to issue the THP madvise call if Huge Pages are
used directly.  */
mm = sysmalloc_mmap (nb, mp_.hp_pagesize, mp_.hp_flags, av);
if (mm != MAP_FAILED)
return mm;
}
mm = sysmalloc_mmap (nb, pagesize, 0, av);
if (mm != MAP_FAILED)
return mm;
tried_mmap = true;
}

/* There are no usable arenas and mmap also failed.  */
if (av == NULL)
return 0;

sysmalloc 확인 사항

이는 이전 top 청크 정보를 가져와 다음 조건 중 일부가 참인지 확인하며 시작됩니다:

  • 이전 힙 크기가 0인 경우 (새로운 힙)

  • 이전 힙의 크기가 MINSIZE보다 크고 이전 Top이 사용 중인 경우

  • 힙이 페이지 크기에 맞게 정렬되어 있는지 (0x1000이므로 하위 12비트는 0이어야 함)

그런 다음 다음을 확인합니다:

  • 이전 크기가 요청된 크기의 청크를 만들기에 충분한 공간이 없는지 확인합니다

sysmalloc checks

```c /* Record incoming configuration of top */

old_top = av->top; old_size = chunksize (old_top); old_end = (char *) (chunk_at_offset (old_top, old_size));

brk = snd_brk = (char *) (MORECORE_FAILURE);

/* If not the first time through, we require old_size to be at least MINSIZE and to have prev_inuse set. */

assert ((old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0));

/* Precondition: not enough current space to satisfy nb request */ assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));

</details>

### 메인 아레나가 아닌 sysmalloc

먼저 이 힙을 위해 이전 힙을 **확장**하려고 할 것입니다. 그게 불가능하면 **새 힙을 할당**하고 그것을 사용할 수 있도록 포인터를 업데이트하려고 할 것입니다.\
마지막으로 그것이 작동하지 않으면 **`sysmalloc_mmap`**을 호출해 보세요.&#x20;

<details>

<summary>메인 아레나가 아닌 sysmalloc</summary>
```c
if (av != &main_arena)
{
heap_info *old_heap, *heap;
size_t old_heap_size;

/* First try to extend the current heap. */
old_heap = heap_for_ptr (old_top);
old_heap_size = old_heap->size;
if ((long) (MINSIZE + nb - old_size) > 0
&& grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
{
av->system_mem += old_heap->size - old_heap_size;
set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
| PREV_INUSE);
}
else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
{
/* Use a newly allocated heap.  */
heap->ar_ptr = av;
heap->prev = old_heap;
av->system_mem += heap->size;
/* Set up the new top.  */
top (av) = chunk_at_offset (heap, sizeof (*heap));
set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);

/* Setup fencepost and free the old top chunk with a multiple of
MALLOC_ALIGNMENT in size. */
/* The fencepost takes at least MINSIZE bytes, because it might
become the top chunk again later.  Note that a footer is set
up, too, although the chunk is marked in use. */
old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
set_head (chunk_at_offset (old_top, old_size + CHUNK_HDR_SZ),
0 | PREV_INUSE);
if (old_size >= MINSIZE)
{
set_head (chunk_at_offset (old_top, old_size),
CHUNK_HDR_SZ | PREV_INUSE);
set_foot (chunk_at_offset (old_top, old_size), CHUNK_HDR_SZ);
set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
_int_free (av, old_top, 1);
}
else
{
set_head (old_top, (old_size + CHUNK_HDR_SZ) | PREV_INUSE);
set_foot (old_top, (old_size + CHUNK_HDR_SZ));
}
}
else if (!tried_mmap)
{
/* We can at least try to use to mmap memory.  If new_heap fails
it is unlikely that trying to allocate huge pages will
succeed.  */
char *mm = sysmalloc_mmap (nb, pagesize, 0, av);
if (mm != MAP_FAILED)
return mm;
}
}

sysmalloc 메인 아레나

메모리가 필요한 양을 계산하기 시작합니다. 연속적인 메모리를 요청하여 이전에 사용되지 않은 메모리를 사용할 수 있게 됩니다. 또한 일부 정렬 작업이 수행됩니다.

sysmalloc 메인 아레나

```c // From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L2665C1-L2713C10

else /* av == main_arena */

{ /* Request enough space for nb + pad + overhead */ size = nb + mp_.top_pad + MINSIZE;

/* If contiguous, we can subtract out existing space that we hope to combine with new space. We add it back later only if we don't actually get contiguous space. */

if (contiguous (av)) size -= old_size;

/* Round to a multiple of page size or huge page size. If MORECORE is not contiguous, this ensures that we only call it with whole-page arguments. And if MORECORE is contiguous and this is not first time through, this preserves page-alignment of previous calls. Otherwise, we correct to page-align below. */

#ifdef MADV_HUGEPAGE /* Defined in brk.c. */ extern void *__curbrk; if (_glibc_unlikely (mp.thp_pagesize != 0)) { uintptr_t top = ALIGN_UP ((uintptr_t) _curbrk + size, mp.thp_pagesize); size = top - (uintptr_t) __curbrk; } else #endif size = ALIGN_UP (size, GLRO(dl_pagesize));

/* Don't try to call MORECORE if argument is so big as to appear negative. Note that since mmap takes size_t arg, it may succeed below even if we cannot call MORECORE. */

if (size > 0) { brk = (char *) (MORECORE (size)); if (brk != (char *) (MORECORE_FAILURE)) madvise_thp (brk, size); LIBC_PROBE (memory_sbrk_more, 2, brk, size); }

### sysmalloc 메인 아레나 이전 오류 1

이전에 반환된 값이 `MORECORE_FAILURE`인 경우 `sysmalloc_mmap_fallback`을 사용하여 메모리를 다시 할당하십시오.

</details>
```c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L2715C7-L2740C10

if (brk == (char *) (MORECORE_FAILURE))
{
/*
If have mmap, try using it as a backup when MORECORE fails or
cannot be used. This is worth doing on systems that have "holes" in
address space, so sbrk cannot extend to give contiguous space, but
space is available elsewhere.  Note that we ignore mmap max count
and threshold limits, since the space will not be used as a
segregated mmap region.
*/

char *mbrk = MAP_FAILED;
if (mp_.hp_pagesize > 0)
mbrk = sysmalloc_mmap_fallback (&size, nb, old_size,
mp_.hp_pagesize, mp_.hp_pagesize,
mp_.hp_flags, av);
if (mbrk == MAP_FAILED)
mbrk = sysmalloc_mmap_fallback (&size, nb, old_size, MMAP_AS_MORECORE_SIZE,
pagesize, 0, av);
if (mbrk != MAP_FAILED)
{
/* We do not need, and cannot use, another sbrk call to find end */
brk = mbrk;
snd_brk = brk + size;
}
}

sysmalloc 메인 아레나 계속

이전 작업이 MORECORE_FAILURE를 반환하지 않았다면, 작업이 성공했다면 일부 정렬을 생성합니다:

sysmalloc 메인 아레나 이전 오류 2

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

if (brk != (char *) (MORECORE_FAILURE)) { if (mp_.sbrk_base == 0) mp_.sbrk_base = brk; av->system_mem += size;

/* If MORECORE extends previous space, we can likewise extend top size. */

if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE)) set_head (old_top, (size + old_size) | PREV_INUSE);

else if (contiguous (av) && old_size && brk < old_end) /* Oops! Someone else killed our space.. Can't touch anything. */ malloc_printerr ("break adjusted to free malloc space");

/* Otherwise, make adjustments:

  • If the first time through or noncontiguous, we need to call sbrk just to find out where the end of memory lies.

  • We need to ensure that all returned chunks from malloc will meet MALLOC_ALIGNMENT

  • If there was an intervening foreign sbrk, we need to adjust sbrk request size to account for fact that we will not be able to combine new space with existing space in old_top.

  • Almost all systems internally allocate whole pages at a time, in which case we might as well use the whole last page of request. So we allocate enough more memory to hit a page boundary now, which in turn causes future contiguous calls to page-align. */

else { front_misalign = 0; end_misalign = 0; correction = 0; aligned_brk = brk;

/* handle contiguous cases / if (contiguous (av)) { / Count foreign sbrk as system_mem. */ if (old_size) av->system_mem += brk - old_end;

/* Guarantee alignment of first new chunk made from this space */

front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK; if (front_misalign > 0) { /* Skip over some bytes to arrive at an aligned position. We don't need to specially mark these wasted front bytes. They will never be accessed anyway because prev_inuse of av->top (and any chunk created from its start) is always true after initialization. */

correction = MALLOC_ALIGNMENT - front_misalign; aligned_brk += correction; }

/* If this isn't adjacent to existing space, then we will not be able to merge with old_top space, so must add to 2nd request. */

correction += old_size;

/* Extend the end address to hit a page boundary */ end_misalign = (INTERNAL_SIZE_T) (brk + size + correction); correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;

assert (correction >= 0); snd_brk = (char *) (MORECORE (correction));

/* If can't allocate correction, try to at least find out current brk. It might be enough to proceed without failing.

Note that if second sbrk did NOT fail, we assume that space is contiguous with first sbrk. This is a safe assumption unless program is multithreaded but doesn't use locks and a foreign sbrk occurred between our first and second calls. */

if (snd_brk == (char *) (MORECORE_FAILURE)) { correction = 0; snd_brk = (char *) (MORECORE (0)); } else madvise_thp (snd_brk, correction); }

/* handle non-contiguous cases / else { if (MALLOC_ALIGNMENT == CHUNK_HDR_SZ) / MORECORE/mmap must correctly align / assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0); else { front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK; if (front_misalign > 0) { / Skip over some bytes to arrive at an aligned position. We don't need to specially mark these wasted front bytes. They will never be accessed anyway because prev_inuse of av->top (and any chunk created from its start) is always true after initialization. */

aligned_brk += MALLOC_ALIGNMENT - front_misalign; } }

/* Find out current end of memory */ if (snd_brk == (char *) (MORECORE_FAILURE)) { snd_brk = (char *) (MORECORE (0)); } }

/* Adjust top based on results of second sbrk */ if (snd_brk != (char *) (MORECORE_FAILURE)) { av->top = (mchunkptr) aligned_brk; set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE); av->system_mem += correction;

/* If not the first time through, we either have a gap due to foreign sbrk or a non-contiguous region. Insert a double fencepost at old_top to prevent consolidation with space we don't own. These fenceposts are artificial chunks that are marked as inuse and are in any case too small to use. We need two to make sizes and alignments work out. */

if (old_size != 0) { /* Shrink old_top to insert fenceposts, keeping size a multiple of MALLOC_ALIGNMENT. We know there is at least enough space in old_top to do this. */ old_size = (old_size - 2 * CHUNK_HDR_SZ) & ~MALLOC_ALIGN_MASK; set_head (old_top, old_size | PREV_INUSE);

/* Note that the following assignments completely overwrite old_top when old_size was previously MINSIZE. This is intentional. We need the fencepost, even if old_top otherwise gets lost. */ set_head (chunk_at_offset (old_top, old_size), CHUNK_HDR_SZ | PREV_INUSE); set_head (chunk_at_offset (old_top, old_size + CHUNK_HDR_SZ), CHUNK_HDR_SZ | PREV_INUSE);

/* If possible, release the rest. / if (old_size >= MINSIZE) { _int_free (av, old_top, 1); } } } } } } / if (av != &main_arena) */

</details>

### sysmalloc 종료

아레나 정보를 업데이트하여 할당을 완료합니다
```c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L2921C3-L2943C12

if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
av->max_system_mem = av->system_mem;
check_malloc_state (av);

/* finally, do the allocation */
p = av->top;
size = chunksize (p);

/* check that one of the above allocation paths succeeded */
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (p, nb);
av->top = remainder;
set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, p, nb);
return chunk2mem (p);
}

/* catch all failure paths */
__set_errno (ENOMEM);
return 0;

sysmalloc_mmap

Last updated