Heap 영역 정리

참고용 link : http://tribal1012.tistory.com/78

이 글은 ptmalloc2에 대한 내용입니다. 계속 작성 중.....

--------------------------------------------------------------------------------------------------------------------------------------

용어 설명

• Arena : Main을 포함한 모든 각 Threads에 대한 힙 영역이라고 할 수 있다. 모든 Threads가 각자의 Arena를 가지진 못 하고 32bit와 64bit System과 시스템의 Core 갯수에 따라 Arena의 갯수에 제한(모든 Thread에 대해 할당하다간 자원 고갈이 심각할 것임)이 있고, 제한을 넘어 Arena가 필요한 경우는 기존에 사용하던 Arena를 재사용(Use After Free 가능??)한다.
• Chunk : Arena가 관리하는 힙 영역을 구성하고 있는 사용되거나 해제되었거나 미사용한 힙 영역
• Bin : free로 해제된 Chunk들을 관리하기 위한 연결리스트, 해제된 Chunk의 크기에 따라 세세하게 분류(fast, small, large)하여 관리된다.

malloc_info 구조체(Heap_Header)

typedef struct _heap_info {
  mstate ar_ptr;    /* 현재 heap을 담당하고 있는 Arena */
  struct _heap_info *prev;  /* 이전 heap 영역 */
  size_t size;      /* 현재 size(bytes) */
  size_t mprotect_size; /* mprotected(PROT_READ|PROT_WRITE) size(bytes) */
  char pad[(-6*SIZE_SZ)&MALLOC_ALIGN_MASK]; /* 메모리 정렬 */
  /* sizeof(heap_info) + 2*SIZE_SZ는 MALLOC_ALIGN_MASK의 배수 */
} heap_info;

Arena는 각 Threads에 대한 힙 영역이기 때문에 힙 영역의 공간이 부족하면 새로운 영역에 추가로 할당받기 때문에 여러 개의 힙 영역을 가질 수 있다(Main Thread 제외). 이런 힙 영역은 어떤 Arena가 관리하고 있는지, 힙 영역의 크기가 어느정도인지, 이전에 사용하던 heap 영역의 정보가 어디에 있는지를 저장할 필요가 있다. 이런 정보를 저장하기 위한 구조체가 malloc_info 구조체이며, 힙에 대한 정보를 저장하기 때문에 Heap_Header라고도 할 수 있다(Main Thread는 확장을 해서 쓰기 때문에 제외).

malloc_state 구조체(Arena Header)

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;
 
  /* Flags (formerly in max_fast).  */
  int flags;
 
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
 
  /* topchunk의 base address */
  mchunkptr top;
 
  /* 가장 최근의 작은 요청으로부터 분리된 나머지 */
  mchunkptr last_remainder;
 
  /* 위에서 설명한대로 pack된 일반적인 bins */
  mchunkptr bins[NBINS * 2 - 2];
 
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
 
  /* 연결 리스트 */
  struct malloc_state *next;
 
  /* 해제된 아레나를 위한 연결 리스트 */
  struct malloc_state *next_free;
 
  /* 현재 Arena의 시스템으로부터 메모리 할당  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

위의 Heap_Header에서는 단순히 힙 영역에 대한 정보만을 저장하였기 때문에, 힙 영역에서도 어떤 부분을 사용하면 되는지에 대해 Arena는 이를 관리하기 때문에 알고 있을 필요가 있다. malloc_state 구조체는 각 Arena에 하나씩 주어지고, 해제된 Chunk를 관리하는 연결리스트 bin과 최상위 Chunk인 top chunk와 같은 Arena에 대한 정보를 저장한다.

malloc_chunk 구조체(Chunk Header) : http://tribal1012.tistory.com/45

struct malloc_chunk {
 
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
 
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
 
  /* large block에서만 사용하고 해당 bin list의 크기 순서를 나타냄  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

힙 영역은 사용자에 의해 할당되거나, 해제되거나 하면 Chunk라는 단위로 관리된다. malloc_chunk는 현재 chunk의 크기와 바로 인접한 이전 chunk의 크기를 저장하고, 해제된 chunk는 bin에 의해 연결리스트로 관리되기 때문에 이중 연결리스트를 위한 포인터 주소를 저장한다. 마지막으로 있는 2개의 chunk 포인터는 large bin을 위해서만 사용된다. large bin은 다른 bin과 다르게 연결리스트에 크기를 대략적으로 관리하기 때문에 연결리스트 내부에서 크기 순으로 추가적인 연결리스트를 가진다.

malloc 소스코드 매크로 정리

기본적인 자료형 크기 및 메모리 정렬 매크로

#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif
 
#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
/*
   32bit size_t의 크기는 4(SIZE_SZ)
   64bit size_t의 크기는 8(SIZE_SZ)
*/
 
 
#ifndef MALLOC_ALIGNMENT
#if !SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_16)
#define MALLOC_ALIGNMENT       (2 *SIZE_SZ < __alignof__ (long double)      \
                                  ? __alignof__ (long double) : 2 *SIZE_SZ)
#else
#define MALLOC_ALIGNMENT       (2 *SIZE_SZ)
#endif
#endif
 
#define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
/*
   MALLOC_ALIGNMENT는 64bit는 16, 32bit는 8
   MALLOC_ALIGN_MASK는 64bit는 15, 32bit는 7
*/

libc_mallopt() 함수에서 사용되는 매크로 및 기본 값 : http://egloos.zum.com/studyfoss/v/5209389

#ifndef M_MXFAST
#define M_MXFAST            1
#endif
//fastbin의 최대 크기를 설정(최대 80)
 
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)   // 64 or 128
#endif
//fastbin의 default 최대 크기
 
#define M_TRIM_THRESHOLD       -1
//trim 임계값 설정
 
#ifndef DEFAULT_TRIM_THRESHOLD
#define DEFAULT_TRIM_THRESHOLD (128 * 1024)
#endif
//trim default 임계 값, 병합한 chunk가 이 임계값을 넘어서면 trim 실시
 
#define M_TOP_PAD              -2
//top chunk의 여유 공간 설정
 
#ifndef DEFAULT_TOP_PAD
#define DEFAULT_TOP_PAD        (0)
#endif
//top chunk의 기본 여유 공간, 항상 이 만큼의 여유 공간을 둠
 
#ifndef DEFAULT_MMAP_THRESHOLD_MIN
#define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
#endif
//mmap 임계값, 이 값보다 큰 경우 sbrk() 대신 mmap 사용
 
#ifndef DEFAULT_MMAP_THRESHOLD_MAX
#if __WORDSIZE == 32 // 32bit
#define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
#else  // 64bit
#define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
#endif
#endif
//mmap 임계값 최대치
 
#define M_MMAP_THRESHOLD      -3
//mmap 임계값 설정
 
#ifndef DEFAULT_MMAP_THRESHOLD
#define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN
#endif
//mmap 기본 임계값
 
#define M_MMAP_MAX             -4
//mmap으로 할당할 수 있는 chunk의 최대 개수
 
#ifndef DEFAULT_MMAP_MAX
#define DEFAULT_MMAP_MAX       (65536)
#endif
//mmap으로 할당할 수 있는 chunk의 기본 최대 개수
 
#define M_ARENA_TEST -7
//core의 갯수로 테스트해서 결정된 Arena 갯수를 사용자가 변경
#define M_ARENA_MAX  -8
//Arena의 최대 갯수 변경

chunk 관련 매크로

#define chunk2mem(p)   ((void*)((char*)(p) + 2*SIZE_SZ))
// prev_size와 size 때문에 8 or 16 더함
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
// heap address는 prev_size와 size 다음을 가리키므로 chunk의 주소는 8 or 16을 뺀 주소
 
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))
// chunk의 최소 크기는 16 or 32
 
#define MINSIZE  \
  (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
// chunk의 최소 크기는 16 or 32, mask 값을 이용해 메모리 정렬 
#define aligned_OK(m)  (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
// Mask로 정렬 확인, mask로 정렬하기 때문에 0이 정상임
#define misaligned_chunk(p) \
  ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
   & MALLOC_ALIGN_MASK)
// 메모리 정렬이 제대로 안 된 chunk인지 확인
 
#define REQUEST_OUT_OF_RANGE(req)                                 \
  ((unsigned long) (req) >=                              \
   (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
// 요청한 크기가 범위를 벗어난 크기인지 체크
 
#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
//요청한 크기를 16 or 32bit의 배수로 정렬
 
#define checked_request2size(req, sz)                             \
  if (REQUEST_OUT_OF_RANGE (req)) {                          \
      __set_errno (ENOMEM);                              \
      return 0;                                      \
    }                                          \
  (sz) = request2size (req);
//요청한 크기가 범위를 벗어난 값인지 체크한 후, 문제가 없다면 정렬해서 반환
 
#define PREV_INUSE 0x1
#define prev_inuse(p)       ((p)->size & PREV_INUSE)
// prev_inus 세팅 확인
#define IS_MMAPPED 0x2
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
// is_mmapped 세팅 확인
#define NON_MAIN_ARENA 0x4
#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
// non_main_arena 세팅 확인
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
// size의 특수 비트 3개 전부 더한 값
#define chunksize(p)         ((p)->size & ~(SIZE_BITS))
// size의 특수 비트를 제외한 순수 size
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))
// 다음 chunk의 주소
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - ((p)->prev_size)))
// 이전 chunk의 주소
#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))
// chunk에 s만큼 더한 주소
 
#define inuse(p)                                  \
  ((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
// 현재 chunk가 사용 중인지 확인
#define set_inuse(p)                                  \
  ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
// 현재 chunk에 사용 중 표시
#define clear_inuse(p)                                  \
  ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
// 현재 chunk에 prev_inuse 제거
 
#define inuse_bit_at_offset(p, s)                          \
  (((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
// 다음 또는 이전 chunk가 사용 중인지 확인
#define set_inuse_bit_at_offset(p, s)                          \
  (((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
// 다음 또는 이전 chunk에 사용 중 표시
#define clear_inuse_bit_at_offset(p, s)                          \
  (((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))
// // 다음 또는 이전 chunk에서 prev_inuse 제거
 
#define set_head_size(p, s)  ((p)->size = (((p)->size & SIZE_BITS) | (s)))
/* Set size/use field */
#define set_head(p, s)       ((p)->size = (s))
/* size에 특정한 비트를 세팅할 때 (chunk를 사용하지 않을 때만 사용) */
#define set_foot(p, s)       (((mchunkptr) ((char *) (p) + (s)))->prev_size = (s))
/* 다음 chunk의 prev_size 갱신 */

bin과 binmap 관련 매크로

#define next_bin(b)  ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))
// bins[]에서 다음 bin을 가져오기 위해 사용
 
#define first(b)     ((b)->fd)        // 해당 binlist의 첫 번째 chunk를 가져올 때 사용
#define last(b)      ((b)->bk)        // 해당 binlist의 마지막 chunk를 가져올 때 사용
 
#define unlink(P, BK, FD) {        /* binlist에서 chunk 제거 */     \
    FD = P->fd;                                      \
    BK = P->bk;                                      \
    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))        /*fake chunk check*/    \
      malloc_printerr (check_action, "corrupted double-linked list", P);      \
    else {                                      \
        FD->bk = BK;                                  \
        BK->fd = FD;                                  \
        if (!in_smallbin_range (P->size)                \ /*large bin의 크기이며,*/
            && __builtin_expect (P->fd_nextsize != NULL, 0)) {    \ /*fd_nextsize가 채워져 있다면*/
            assert (P->fd_nextsize->bk_nextsize == P);  \
            assert (P->bk_nextsize->fd_nextsize == P);    \
            /* 이전 chunk의 fd가 P인지 확인 */
            if (FD->fd_nextsize == NULL) {                      \ /* 다음 chunk의 fd_nextsize가 NULL인 경우 */
                if (P->fd_nextsize == P)                 \  /* P의 fd_nextsize가 자기자신인지 확인 */
                  FD->fd_nextsize = FD->bk_nextsize = FD;           \ /* FD도 자기자신으로 */
                else {                                  \
                    FD->fd_nextsize = P->fd_nextsize;              \
                    FD->bk_nextsize = P->bk_nextsize;                  \
                    P->fd_nextsize->bk_nextsize = FD;                  \
                    P->bk_nextsize->fd_nextsize = FD;               \ /* 자기자신이 아니라면 FD와 P를 제대로 연결 */
                  }                                  \
              } else {                                  \
                P->fd_nextsize->bk_nextsize = P->bk_nextsize;              \
                P->bk_nextsize->fd_nextsize = P->fd_nextsize;              \ /* 복구 */
              }                                       \
          }                                      \
      }                                          \
}
 
#define NBINS             128        // bin의 갯수
#define NSMALLBINS         64        // small bin의 갯수
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT    // 64bit는 16, 32bit는 8
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)    //0
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)   // (64) * (16 or 8)
 
#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
//large bin의 최소 크기보다 작으면 small bin
 
#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
   + SMALLBIN_CORRECTION)   // 크기에 16 or 8을 나눈 값이 크기에 맞는 small bin의 index가 됨
 
#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))
//system에 맞는 index 연산 사용
 
#define bin_index(sz) \
  ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
//size로 smallbin인지 largebin인지 확인하여 index 획득
 
#define unsorted_chunks(M)          (bin_at (M, 1))
#define initial_top(M)              (unsorted_chunks (M))
// Arena의 bins의 첫 번째 bin 주소
 
#define BINMAPSHIFT      5
#define BITSPERMAP       (1U << BINMAPSHIFT)  // 32
#define BINMAPSIZE       (NBINS / BITSPERMAP) // 128/32 = 4
 
#define idx2block(i)     ((i) >> BINMAPSHIFT)
#define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
//bin index에 맞는 map block과 bit 획득
 
#define mark_bin(m, i)    ((m)->binmap[idx2block (i)] |= idx2bit (i))
#define unmark_bin(m, i)  ((m)->binmap[idx2block (i)] &= ~(idx2bit (i)))
#define get_binmap(m, i)  ((m)->binmap[idx2block (i)] & idx2bit (i))
//bin의 매핑 정보를 마킹하여 표시함
 
typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
/* offset 2부터 사용, 안 그럼 맨 앞의 bin 2개는 색인 불가능 */
// 크기를 3 또는 4만큼 우측 시프트한 후, 2를 빼면 fastbin index
#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)
// 64bit는 160, 32bit는 80
#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
//request2size로 최소 사이즈 확인과 메모리 정렬 + 1 -> 8 또는 16으로 나눈 후 2감소
#define FASTBIN_CONSOLIDATION_THRESHOLD  (65536UL)
#define FASTCHUNKS_BIT        (1U)
#define have_fastchunks(M)     (((M)->flags & FASTCHUNKS_BIT) == 0)     //세팅되면 0 반환, 안 세팅되어 있다면 1반환
#define clear_fastchunks(M)    catomic_or (&(M)->flags, FASTCHUNKS_BIT)
#define set_fastchunks(M)      catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
// FASTCHUNKS_BIT 확인, 세팅, 해제
#define NONCONTIGUOUS_BIT     (2U)
#define contiguous(M)          (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M)       (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M)   ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M)      ((M)->flags &= ~NONCONTIGUOUS_BIT)
// 아레나의 flags에서 NONCONTIGUOUS_BIT 확인, 세팅, 해제
 
#define set_max_fast(s) \
  global_max_fast = (((s) == 0)                              \
                     ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
// fastbin의 최대 크기 설정
#define get_max_fast() global_max_fast
// fastbin의 최대 크기를 가져옴

함수 호출 과정, 알고리즘 : http://files.cnblogs.com/files/hseagle/demo.pdf

malloc분석.h

malloc 함수 호출 순서 : libc_malloc() -> int_malloc() -> sysmalloc()

1. libc_malloc() 함수에서 사용하는 Thread에 맞게 Arena를 설정한 후, int_malloc() 함수 호출
2. int_malloc() 함수에서는 재사용할 수 있는 bin을 탐색하여 재할당하고, 마땅한 bin이 없다면 top chunk에서 분리해서 할당
3. top chunk가 요청한 크기보다 작은 경우, sysmalloc() 함수 호출
4. sysmalloc() 함수를 통해 시스템에 메모리를 요청해서 top chunk의 크기를 확장하고 대체
   ※ sysmalloc() 함수는 기존의 영역을 해제한 후, 새로 할당함

free 함수 호출 순서 : libc_free() -> int_free() -> systrim() or heap_trim() or munmap_chunk()

1. libc_free() 함수에서 mmap으로 할당된 메모리인지 확인한 후, 맞을 경우 munmap_chunk() 함수를 통해 메모리 해제
2. 아닌 경우, 해제하고자 하는 chunk가 속한 Arena의 포인터를 획득한 후, int_free() 함수 호출
3. chunk를 해제한 후, 크기에 맞는 bin을 찾아 저장하고 top chunk와 병합을 할 수 있다면 병합 수행
4. 병합된 top chunk가 너무 커서 Arena의 크기를 넘어선 경우, top chunk의 크기를 줄이기 위해 systrim() 함수 호출
5. 문제가 없다면, heap_trim() 함수 호출
6. mmap으로 할당된 chunk라면 munmap_chunk()를 호출

Bins

Arena_Header의 fastbinY와 Bins를 볼 것이다. fastbinY는 fast bin의 binlist를 저장한 배열이고, Bins는 unsorted bin, small bin, large bin의 binlist를 저장한 배열이다.

fastbin : 모든 bin 중에서 메모리의 할당과 해제가 가장 빠른 bin

• chunk의 크기 : 16 ~ 80 Bytes, 기본 최대 크기는 64 Bytes(mallopt() 함수로 확장)
• bin의 개수 : 10개, 16 Bytes부터 시작해서 8 Bytes씩 증가
• 단일 연결리스트 : binlist의 추가와 제거는 가장 앞 부분에서 이루어짐(LIFO)
• 병합 없음 : 해제된 chunk 2개가 연속해서 있을 수 있음

간단한 소스코드로 위의 내용을 확인해볼 것이다.

#include <stdlib.h>
 
int main(void) {
    char* ptr1 = NULL;
    char* ptr2 = NULL;
    char* ptr3 = NULL;
 
    ptr1 = (char*) malloc(48);
    ptr2 = (char*) malloc(48);
    ptr3 = (char*) malloc(8);
 
    free(ptr1);
    free(ptr2);
    free(ptr3);
 
    return 0;
}

다음과 같은 프로그램을 작성한 뒤, 14번째 줄의 3번째 free까지 마친 후의 fast bin을 보면 다음과 같다.

• ptr3은 요청한 크기 8 + 헤더 8이 합쳐져 총 16 Bytes의 chunk가 만들어져 fastbin의 0번째 인덱스의 binlist에 추가되었다.

• ptr1은 56 Bytes의 chunk가 만들어져 fastbin의 5번째 인덱스의 binlist에 추가되었다.

• ptr2도 56 Bytes의 chunk이기 때문에 5번째 인덱스의 binlist의 맨 앞에 추가되었다.

• 여기서 3개의 힙 영역을 연속해서 할당하고 해제하였지만, size에 prev_inuse가 설정되어 병합이 되지 않고 fastbin에 들어가 있는 것을 볼 수 있다. 

Bins : Bins 배열은 unsorted bin, small bin, large bin을 수용한다. 총 127개이며, 1개의 특수한 bin과 126개의 환형 이중 연결리스트의 bin으로 구성된다.

• Bin 0 : 특수한 목적으로 사용
• Bin 1 : unsorted bin
• Bin 2 ~ 63 : small bin
• Bin 64 ~ 126 : large bin

unsorted bin : small chunk와 large chunk가 free() 함수로 해제된 경우, 우선적으로 저장되는 bin, 크기와 상관없이 저장하기 때문에 메모리 할당과 반환의 속도가 빠르다.

• chunk의 크기 : 정해져 있지 않아, 다양한 크기의 chunk가 저장됨
• bin의 개수 : 1개
• 환형 이중 연결리스트 : FIFO 방식(큐) 
• bin 재배치 : unsorted bin의 모든 chunk는 재할당을 위한 1번의 기회가 주어진다. 재할당에 실패한 경우, 크기에 따라 small bin이나 large bin에 재배치
• NON_MAIN_ARENA : unsorted chunk는 해당 플래그를 절대 세팅하지 않음

small bin : 512 Bytes 미만의 chunk가 저장되는 bin, 메모리 할당과 반환의 속도는 fast bin보다는 느리고, large bin보다는 빠르다.

• chunk의 크기 : 512 Bytes 미만
• bin의 개수 : 62개, 8 Bytes씩 증가
• 환형 이중 연결리스트 : list 중간에서 chunk를 제거할 수 있기 때문에 사용. 노드의 추가는 맨 앞, 노드의 삭제는 가장 오래된 chunk인 맨 뒤부터 시작함(FIFO)
• 병합 : 해제된 2개의 chunk는 반드시 병합 수행

※ 이중 연결리스트 형태를 가진 fast bin을 생각하면 됨

large bin : 512 Bytes 이상의 chunk가 저장되는 bin, 메모리 할당과 반환의 속도는 가장 느리다.

• chunk의 크기 : 512 Bytes 이상
• bin의 개수 : 63개, 대략적인 크기의 chunk를 저장
• 32개의 bin : 64 Bytes씩 증가
• 16개의 bin : 512 Bytes씩 증가
• 8개의 bin : 4096 Bytes씩 증가
• 4개의 bin : 32768 Bytes씩 증가
• 2개의 bin : 262144 Bytes씩 증가
• 1개의 bin : 이 외의 남은 크기의 chunk
• 하나의 bin에 다양한 크기의 chunk가 저장되기 때문에 bin 내부에서 적당한 크기의 chunk를 찾기 쉽도록 내림차순으로 정렬하여 저장, 가장 앞쪽이 가장 큰 chunk가 되고 가장 뒷쪽이 가장 작은 chunk가 됨
• fd_nextsize와 bk_nextsize를 사용하여 크기 순으로 정렬, 동일한 크기의 chunk 끼리는 연결되지 않음 
• 환형 이중 연결리스트 : list 중간에서 chunk가 추가되고 제거될 수 있기 때문에 사용
• 병합 : 해제된 2개의 chunk는 반드시 병합 수행

※ 참고 : http://studyfoss.egloos.com/5206220

top chunk : Arena의 메모리 끝부분에 위치한 chunk를 top chunk라고 부름. 어떤 bin에도 속하지 않는다. 만약, top chunk의 크기가 사용자가 요청한 크기보다 작은 경우, 

• 최상의 best fit : 별 다른 chunk가 없는 경우 사용자가 요청한 크기만큼 분할하여 사용
• 확장 : 만약, top chunk의 크기가 사용자가 요청한 크기보다 작은 경우, sysmalloc() 함수를 통해 mmap, sbrk syscall을 호출하여 확장
  ※ sysmalloc() 함수는 메모리르 한 번 해제한 후, 재할당하는 식으로 확장
• 병합 : top chunk와 인접한 top chunk의 이전 chunk를 해제 시, top chunk와 병합(fast bin은 제외)
• 측소 : top chunk가 병합에 의해 m_trim_threshold보다 크기가 커졌다면, top chunk의 크기 축소

last remainder : 분할을 통해 재할당한 bin의 분할되고 남은 나머지 chunk이다. 연속된 작은 크기의 할당을 할 때, 분할되고 남은 나머지를 사용할 수 있도록 하기 때문에 지역 참조성을 증가시키는데 도움이 됨.

• 남기는 시점 : unsorted bin 재사용, binmap 탐색