[glibc2.23] Heap bins 정리 2 (Unsorted bin)

unsorted bin

unsorted bin 은 다음에 정리할 small bin 과 large bin 크기의 힙 chunk 가 해제되면

이후 재할당을 위해 사용되는 bin이다. 

-> unsorted bin 의 개수는 1개이다. 

-> unsorted bin 은 FIFO 구조를 사용한다.

 

다음은 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;
}

위 코드는 unsorted bin 의 일부이다.

여기서는 unsorted bin의 size와 할당 요청이 들어온 크기인 nb를 비교합니다.

이 두 개가 같은 크기라면 기존의 unsorted bin에 들어간 영역을 재사용한다. 

 

unsorted bin 의 코드중 다른걸 봐보자.

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;
}

맨 위부터 if문 부터 알아보자.

현재 chunk 가 smallbin 크기이고, unsorted bin에 속해있는 chunk가 last_remainder chunk 라면

(last_remainder chunk 란? -> 사용자 요청에 의해 발생한 가장 최근 chunk)

이를 분할해서 남은 크기만큼을 unsorted bin에 할당한다. 

근데 만약 last_remainder chunk의 크기가 small_bin 에 속해있다면 

remainder->fd_nextsize = NULL

remainder ->bk_nextsize = NULL 이 된다. 

 

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;

위 코드를 보면

smallbin 의 크기가 unsorted bin 에 남아있다면

해당 chunk는 smallbin으로 옮겨진다. 

이는 크기를 검사하고 smallbin 중 해당 크기에 적합한 배열을 찾아 smallbin에 존재하는 청크와 FD, BK를 연결한다.

 

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;

만약 다음 할당 요청까지 large bin의 크기가 unsorted bin에 남아있다면 해당 청크는 large bin으로 옮겨집니다. 이는 크기를 검사하고 large bin 중 해당 크기에 적합한 배열을 찾아 large bin에 존재하는 청크와 fd_nextsize, bk_nextsize를 연결하고 FD, BK를 연결한다.

 

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

 

위 코드를 보면  clear_inuse_bit_at_offset(nextchunk, 0) 을 통해 

인접한 다음 chunk의 prev_inuse 를 0으로 만든다. 

이후 새롭게 해제된 chunk를 연결리스트에 포함시킨다. 

또한, large bin 이 아닌 chunk가 해제되면

unsorted bin 에서 사용하지 않는 fd, bk 를 모두 NULL로 초기화한다.

 

 

※정리 

unsorted bin 은 1개의 bins 로 이루어져 있다.

unsorted bin 은 fastbin 이 아닌 값이 할당이 되고 해제 되었을 때 unsorted bin 크기에서 이전에 할당했던 size만큼을 뺀 값이 저장된다.  =>  해제된 chunk 를 reuse 하기위해 존재한다. 

unsorted bin 은 이중 연결리스트를 사용하고, FIFO 구조를 사용한다.