ptmalloc2 allocator

ptmalloc2는 리눅스 glibc에서 사용하는 메모리 할당자이다. ptmalloc2는 glibc 2.23버전과 glibc 2.26 이후 버전 동작 방식이 tcache로 인해 조금 달라졌다. glibc 2.23 기준으로 설명하겠다.

해당 페이지는 dreamhack.io 사이트의 강의를 참고해 정리하고 이해못한 내용을 추가로 작성해둔것이니 참고사이트의 사이트를 참고하시기바랍니다.

ptmalloc2 allocator

ptmalloc2에서 힙 청크는 malloc_chunk를 사용한다.

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;
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

• prev_size : 이전 힙 청크가 해제되었을 경우 해제된 힙 청크의 크기를 저장. 만약 힙 청크가 할당되어있을 경우 데이터 영역으로 사용.
• size : 할당된 현재 힙청크의 크기를 저장하고있다. 또한 3개의 비트 플래그가 존재한다.
• Flags(3bit)
  • PREV_INUSE(P) : 해당 비트는 이전 힙 청크가 해제된 경우 설정.
  • IS_MMAPPED(M) : 해당 비트는 현재 청크가 mmap 시스템콜을 사용하여 할당된 경우 설정.
  • NON_MAIN_ARENA(N) : 해당 비트는 현재 청크가 main_arena에서 관리하지 않을 경우 설정.
• FD(Forward pointer) : FD 포인터가 위치한 주소가 실제로 데이터 영역의 시작 부분, 힙 청크가 해제되었을 때 동일한 bin에 존재하는 다음 힙 청크를 저장.
• BK(Backward pointer) : 동일한 bin에서 이전 Free 청크의 포인터를 가리킴.
• fd_nextsize : large bin에서 사용되는 포인터, 현재 힙 청크의 크기보다 작은 힙 청크의 주소를 가리킴.
• bk_nextsize : large bin에서 사용하는 포인터, 현재 힙 청크 보다 큰 청크의 주소를 가리킴.

Chunk

동적으로 할당된 힙 메모리는 하나의 청크(Chunk)라고 부르며, 청크는 malloc_chunk 구조체를 사용한다.

• Allocate Chunk : malloc이나 calloc 함수 등 동적 메모리 할당 함수를 통해 할당된 청크
• Free Chunk : free 함수 등 동적 메모리 해제 함수를 통해 해제된 청크
• Top Chunk : 힙 메모리의 마지막에 위치해 있는 청크

Top Chunk의 마지막은 힙 메모리 영역의 끝. 따라서 메모리 할당 요청이 들어왔을 때, 사용할 적절한 Free Chunk가 없으면 Top Chunk를 쪼개어 사용
{: .prompt-tip}

• Last Remainder Chunk : 작은 사이즈의 할당 요청이 들어왔을 때, Free Chunk가 쪼개지고 남은 청크

bin

bin이란 위에서 Chunk가 할당되고 free가 되었을때 만들어지는 Free Chunk를 관리하는 역할을 한다. 이때 freelist 구조체를 통해서 관리하게되는데 freelist란 동적으로 메모리를 할당하고 해제할 때 메모리 관리의 효율을 높이기 위해 할당되지 않은 영역을 관리하는 연결리스트이다.

• Fastbin
  • 16~64 byte (32bit)
  • 32~128 byte (64bit)
• Unsortedbin
• Smallbin
  • 크기 < 512 byte (32bit)
  • 크기 < 1024 byte (64bit)
• Largebin
  • 크기 >= 512 byte (32bit)
  • 크기 >= 1024 byte (64bit)

위와 같은 bin들이 사용되고 있고 해제되는 청크의 크기에맞게 bin에 들어가게 된다.

fastbin

fastbin은 작은 크기의 힙 청크를 할당하고 해제할 때 사용되는 bin이다.
fastbin은 다른 bin과는 달리 단일 연결리스트를 사용하고 메모리 검증 루틴이 적기 때문에 다른 bin중 할당 및 해제 속도가 가장 빠르다. 또한 LIFO(Last In First Out) 방식으로 청크를 처리하며, 다른 두개의 청크가 인접해 있어도 하나의 청크로 병합되지 않는다.

 

free(fastbin)

우선 fastbin을 free하는 과정을 알아보겠다.

  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
#if TRIM_FASTBINS
      /*
    If TRIM_FASTBINS set, don't place chunks
    bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {
    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
    || __builtin_expect (chunksize (chunk_at_offset (p, size))
                 >= av->system_mem, 0))
      {
    /* We might not have a lock at this point and concurrent modifications
       of system_mem might have let to a false positive.  Redo the test
       after getting the lock.  */
    if (have_lock
        || ({ assert (locked == 0);
          mutex_lock(&av->mutex);
          locked = 1;
          chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
            || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
          }))
      {
        errstr = "free(): invalid next size (fast)";
        goto errout;
      }
    if (! have_lock)
      {
        (void)mutex_unlock(&av->mutex);
        locked = 0;
      }
      }
    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
    set_fastchunks(av);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);
    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;
    unsigned int old_idx = ~0u;
    do
      {
    /* Check that the top of the bin is not the record we are going to add
       (i.e., double free).  */
    if (__builtin_expect (old == p, 0))
      {
        errstr = "double free or corruption (fasttop)";
        goto errout;
      }
    /* Check that size of fastbin chunk at the top is the same as
       size of the chunk that we are adding.  We can dereference OLD
       only if we have the lock, otherwise it might have already been
       deallocated.  See use of OLD_IDX below for the actual check.  */
    if (have_lock && old != NULL)
      old_idx = fastbin_index(chunksize(old));
    p->fd = old2 = old;
      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
    if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
      {
    errstr = "invalid fastbin entry (free)";
    goto errout;
      }
  }

위의 코드는 free 함수에서 fastbin 청크를 처리하는 코드이다. 청크가 해제될 때 해당 청크가 fastbin 크기의 범위에 속해 있다면 line 1의 조건문을 통과한다.
이후 line 37에서 현재 청크의 크기에 해당하는 fastbin의 리스트를 가져오고 만약 fastbin freelist에 먼저 저장되어있는 청크가 존재한다면 line 56에서 그 청크의 주소를 현재 해제된 청크의 FD에 저장한다.

 

malloc(fastbin)

다음은 fastbin에 청크를 할당하는 과정이다.

  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
      idx = fastbin_index (nb);
      mfastbinptr *fb = &fastbin (av, idx);
      mchunkptr pp = *fb;
      do
        {
          victim = pp;
          if (victim == NULL)
            break;
        }
      while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
             != victim);
      if (victim != 0)
        {
          if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
            {
              errstr = "malloc(): memory corruption (fast)";
            errout:
              malloc_printerr (check_action, errstr, chunk2mem (victim), av);
              return NULL;
            }
          check_remalloced_chunk (av, victim, nb);
          void *p = chunk2mem (victim); //return chunk ptr
          alloc_perturb (p, bytes); //init
          return p;
        }
    }

line 4에서 현재 요청된 fastbin 크기와 부합하는 fastbin 인덱스를 찾고 line 12에서 선택된 청크의 FD를 참조하여 대상 청크의 FD가 가르키는 청크를 fastbin의 첫 번째 리스트로 업데이트하여 LIFO 구조를 유지한다.

unsorted bin

unsorted bin은 smallbin과 large bin 크기의 힙 청크가 해제되면 이후 재할당을 위해 사용되는 bin이다.

bin의 개수는 1개이며, 해당 bin의 용도는 해제된 청크를 재사용하기 위해 존재한다. unsorted bin은 크기의 제한이 없기 때문에 다양한 크기의 힙 청크가 저장될 수 있다. 또한 unsorted bin은 이중 연결 리스트를 사용하며 해제된 청크를 재사용하기 위해서는 해제된 청크의 크기보다 작거나 동일한 크기의 청크가 할당되어야 한다.

unsorted bin은 FIFO 구조를 사용한다. 아래의 unsorted bin1~4는 청크가 할당될때의 과정이다.

 

malloc(unsorted bin1)

unsorted bin의 size와 할당 요청이 들어온 크기인 nb를 비교해 같은 크기라면 기존의 unsorted bin에 들어간 영역을 재사용한다.

/* Take now instead of binning if exact fit */
INTERNAL_SIZE_T nb;               /* normalized request size */
checked_request2size (bytes, nb);
size = chunksize (victim);
if (size == nb)
{
    set_inuse_bit_at_offset (victim, size);
    if (av != &main_arena)
      victim->size |= NON_MAIN_ARENA;
    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
}

malloc(unsorted bin2)

할당 요청이 들어온 크기가 smallbin 크기에 속하고, 현재 unsorted bin에 저장된 청크의 크기보다 작으며 unsorted bin에 존재하는 청크가 분할된 last_remainder 청크라면 이를 분할하여 남은 청크를 unsorted bin과 last_remainder에 저장함.

if (in_smallbin_range (nb) &&
  bck == unsorted_chunks (av) &&
  victim == av->last_remainder &&
  (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
  /* split and reattach remainder */
  remainder_size = size - nb;
  remainder = chunk_at_offset (victim, nb);
  unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
  av->last_remainder = remainder;
  remainder->bk = remainder->fd = unsorted_chunks (av);
  if (!in_smallbin_range (remainder_size))
  {
      remainder->fd_nextsize = NULL;
      remainder->bk_nextsize = NULL;
  }
  set_head (victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
  set_head (remainder, remainder_size | PREV_INUSE);
  set_foot (remainder, remainder_size);
  check_malloced_chunk (av, victim, nb);
  void *p = chunk2mem (victim);
  alloc_perturb (p, bytes);
  return p;
}

malloc(unsorted bin3)

다음 할당 요청까지 smallbin의 크기가 unsorted bin에 남아있다면 해당 청크는 smallbin으로 옮겨짐.

if (in_smallbin_range (size))
{
    victim_index = smallbin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;
}
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

malloc(unsorted bin4)

다음 할당 요청까지 large bin의 크기가 unsorted bin에 남아있다면 해당 청크는 large bin으로 옮겨짐.

else
{
    victim_index = largebin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;
    if (fwd != bck)
    {
        /* Or with inuse bit to speed comparisons */
        size |= PREV_INUSE;
        /* if smaller than smallest, bypass loop below */
        assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
        if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
        {
            fwd = bck;
            bck = bck->bk;
            victim->fd_nextsize = fwd->fd;
            victim->bk_nextsize = fwd->fd->bk_nextsize;
            fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
        }
        else
        {
            assert ((fwd->size & NON_MAIN_ARENA) == 0);
            while ((unsigned long) size < fwd->size)
            {
                fwd = fwd->fd_nextsize;
                assert ((fwd->size & NON_MAIN_ARENA) == 0);
            }
            if ((unsigned long) size == (unsigned long) fwd->size)
            /* Always insert in the second position.  */
                fwd = fwd->fd;
            else
            {
                victim->fd_nextsize = fwd;
                victim->bk_nextsize = fwd->bk_nextsize;
                fwd->bk_nextsize = victim;
                victim->bk_nextsize->fd_nextsize = victim;
            }
            bck = fwd->bk;
          }
        }
        else
            victim->fd_nextsize = victim->bk_nextsize = victim;
        }
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

free(unsorted bin)

smaillbin 혹은 large bin 크기의 청크가 해제되면 unsorted bin에 삽입되게된다. 먼저 clear_inuse_bit_at_offset 매크로를 사용하여 인접한 다음 청크의 prev_inuse 비트를 0으로 만들고 새롭게 해제된 청크를 이중 연결 리스트에 포함시킨다.

만약 large bin 범위에 속해있는 청크가 해제되었을 경우에는 unsorted bin에서 사용하지 않는 fd_nextsize, bk_nextsize를 모두 NULL로 초기화한다.
{: .prompt-tip}

else
  clear_inuse_bit_at_offset(nextchunk, 0);
      /*
  Place the chunk in unsorted chunk list. Chunks are
  not placed into regular bins until after they have
  been given one chance to be used in malloc.
      */
  bck = unsorted_chunks(av);
  fwd = bck->fd;
  if (__glibc_unlikely (fwd->bk != bck))
  {
      errstr = "free(): corrupted unsorted chunks";
      goto errout;
  }
      p->fd = fwd;
      p->bk = bck;
  if (!in_smallbin_range(size))
  {
      p->fd_nextsize = NULL;
      p->bk_nextsize = NULL;
  }
  bck->fd = p;
  fwd->bk = p;
  set_head(p, size | PREV_INUSE);
  set_foot(p, size);
  check_free_chunk(av, p);

smallbin

smallbin은 512 바이트 미만의 사이즈로 청크가 해제되었을 때 unsorted bin에 리스트가 추가된 후 저장되는 bin이다.
bin의 개수는 62개이며, 이중 연결리스트를 사용한다. 해당 bin에는 두 개의 해제된 청크가 인접해 있을 수 없다. 즉, 인접해 있다면 하나의 청크로 병합된다.

smallbin은 FIFO 구조를 사용한다.

smallbin 크기의 힙 청크가 해제되면 unsorted bin을 거쳐 smallbin에 할당되게 된다.

 

malloc(smallbin)

smallbin 크기의 힙 청크가 해제되면 앞에서 말했던 것처럼 unsorted bin을 거쳐 smallbin에 할당되게 된다.
우선 line 1에서 현재 요청된 크기가 smallbin 크기에 부합하는지 검사한 후, line 3에서 smallbin에 해당되는 배열을 선정한다.
line 6에서 반환될 청크를 main_arena에서 얻어오면서 smallbin의 연결리스트가 비어있는지 확인한다. 만약 비어있다면 malloc_consolidate 함수를 호출하여 존재하는 fastbin과 병합한다. 그러나 비어있지 않다면 line 9에서 smallbin인 힙 청크를 재할당하는 코드를 실행한다.
line 17에서 인접한 청크에 prev_inuse 비트를 설정하고 반한될 청크 뒤에 존재하는 청크를 main_arena가 BK로 가르키게 하고, 해당 청크의 FD는 main_arena를 가르키케 설정하여 이중 연결 리스트를 만들고 smallbin의 첫번째 리스트로 만든다.

if (in_smallbin_range (nb))
{
  idx = smallbin_index (nb);
  bin = bin_at (av, idx);
  if ((victim = last (bin)) != bin)
    {
      if (victim == 0) /* initialization check */
        malloc_consolidate (av);
      else
        {
          bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
            {
              errstr = "malloc(): smallbin double linked list corrupted";
              goto errout;
            }
          set_inuse_bit_at_offset (victim, nb);
          bin->bk = bck;
          bck->fd = bin;
          if (av != &main_arena)
            victim->size |= NON_MAIN_ARENA;
          check_malloced_chunk (av, victim, nb);
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }
}

large bin

large bin은 512 바이트 이상의 큰 크기의 청크가 해제되었을 때 사용하는 bin이다.

large bin의 개수는 63개이며, 이중 연결리스트를 사용한다. large bin 청크의 구조체는 다른 bin과는 다르게 fd_nextsize와 bk_nextsize를 사용한다. 이는 다른 크기의 large bin 청크들을 리스트로 연결하기 위해 사용된다.

large bin은 FIFO 구조를 사용한다.

 

malloc(large bin)

line 1에서 요청된 크기가 large bin 크기인지 검사한다. 그리고 line 5에서 large bin이 비어있는지, 혹은 가장 큰 청크가 요청된 크기보다 큰지 검사한다. 이후 line 9에서 victim->bk_nextsize를 순회하면서 요청된 크기에 부합하는 청크를 찾는다.
line 17에서는 반환될 청크를 제외한 앞 뒤 청크들의 연결리스트를 유지하기 위해 unlink 매크로를 사용한다.
다음으로 line 26에서 large bin 청크가 요청된 크기보다 큰 경우 remainder_size를 검사하여 MINSIZE보다 크면 unsorted bin과 연결리스트를 만들어 저장한다. 만약 last_remainder 청크의 크기가 large bin의 크기인 경우 쓰이지 않는 헤더인 fd_nextsize와 bk_nextsize를 NULL로 초기화한다.
마지막으로 line 47에서 반환될 청크의 prev_inuse 비트를 설정하고 분할되어 남은 청크인 last_remainder 청크 또한 prev_inuse 비트를 설정해 현재 반환될 청크가 할당된 상태임을 나타낸다.

      if (!in_smallbin_range (nb))
        {
          bin = bin_at (av, idx);
          /* skip scan if empty or largest chunk is too small */
          if ((victim = first (bin)) != bin &&
              (unsigned long) (victim->size) >= (unsigned long) (nb))
            {
              victim = victim->bk_nextsize;
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb)))
                victim = victim->bk_nextsize;
              /* Avoid removing the first entry for a size so that the skip
                 list does not have to be rerouted.  */
              if (victim != last (bin) && victim->size == victim->fd->size)
                victim = victim->fd;
              remainder_size = size - nb;
              unlink (av, victim, bck, fwd);
              /* Exhaust */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
                }
              /* Split */
              else
                {
                  remainder = chunk_at_offset (victim, nb);
                  /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;
      if (__glibc_unlikely (fwd->bk != bck))
                    {
                      errstr = "malloc(): corrupted unsorted chunks";
                      goto errout;
                    }
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;
                  if (!in_smallbin_range (remainder_size))
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                    }
                  set_head (victim, nb | PREV_INUSE |
                            (av != &main_arena ? NON_MAIN_ARENA : 0));
                  set_head (remainder, remainder_size | PREV_INUSE);
                  set_foot (remainder, remainder_size);
                }
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }

main_arena

main_arena는 brk 시스템 콜을 사용하여 할당된 힙을 효율적으로 관리하기 위해 존재하는 malloc_state 구조체이다. main_arena에는 힙 청크를 관리하기 위한 배열과 포인터가 선언되어 있다.
top chunk의 크기보다 큰 사이즈의 할당 요청이 들어오면 mmap 시스템 콜을 사용하여 새로운 페이지를 할당하고, 이렇게 할당된 힙은 main_arena에서 관리하지 않는다.

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

해당 구조체는 각각의 스레드가 서로 간섭하지 않고 서로 다른 메모리 영역에서 액세스 할 수 있도록 도와주는 역할을 하게 된다.

참고사이트

-https://learn.dreamhack.io/16#1