[glibc2.23] Heap bins 정리 4 (largebin)

large bin 

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

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

large bin 만의 특성이 있는데 이는 fd_nextsize , bk_nextsize 를 사용한다

 

     if (!in_smallbin_range (nb))		// large bin >= 512
        {
          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;
            }
        }

 

 

맨 위부터 분석 해 보자면 large bin에 들어있는 크기인지 검사한다. 

이후 large bin 이 비어있는지, 혹은 가장 큰 chunk가 요청했던 크기보다 큰지 검사한다. 

while (((unsigned long) (size = chunksize (victim)) < (unsigned long) (nb)))

이후 위 반복문을 반복하면서 사용자의 요청에 부합하는 chunk를 찾는다. 

 

unlink (av, victim, bck, fwd);

fd , bk 의 연결리스트를 유지하기 위해 unlink 함수가 쓰인다.

 

  /* 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;

이후 large bin chunk 가 요청된 크기보다 큰 경우 remainder_size 를 검사해 

MINSIZE 보다 크면 현재 chunk가 unsorted_chunk 에 들어가고

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

마지막으로 반환될 chuhnk의 prev_inuse 비트를 설정하고 

분활되어 남은 remainder chunk 또한 prev-inuse bit 를 설정해 현재 반환될 chunk가 할당되었다는 것을 나타낸다.