[glibc2.23] Heap bins 정리1 (fastbins)

워게임 푸는데 뭔가 제데로 알고있다고 생각되지 않아서 다시 정리하고자 한다. 

 

Fastbin : 작은 크기의 heap chunk를 할당하고 해제할 때 사용하는 bin이다.

Fastbin 의 특징

-> 단일 연결 리스트 사용

-> 할당 및 해제 속도가 빠름

-> 할당, 해제시 LIFO (후입 선출) 방식으로 처리

-> 두 개의 청크가 인접해 있어도 하나의 청그로 병합되지 않음.

 

다음은 free 소소코드의 일부다.

  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())   //get_max_fast() 는 fastbin 의 최대 크기를 가져옴
#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;
      }
  }

 

 

위에서부터 천천히 분석해 보도록 하겠다. 

먼저, chunk free 시 해당 chunk가 fastbin 크기에 들어간다면 멘 윗줄의 조건문을 통과한다.

이후 쭉쭉 내려가다 보면 

fb = &fastbin(av,idx)		//fastbin 에 현재 chunk 의 크기에 해당하는 index를 가져옴. 

부분이 있는데 이 코드는 현재 chunk 의 크기에 해당하는 fastbin의 리스트를 가져온다.

그런데 해당 fastbin freelist 에 이전에 저장되어 있던 chunk가 존재한다면 

p->fd = old2 = old;		//새로 free 된 chunk 가 이전에 free되었던 chunk에 들어간다. 

위 코드에서 그 chunk 주소를 현재 free된 chunk 의 FD 에 저장한다. 

=> 이로인해 해제된 chunk 가 fastbin의 단일 연결 리스트가 된다는 것을 알 수 있다.

 

 

다음은 malloc 소스코드 중 일부이다. 

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

코드를 보면 

mfastbinptr *fb = &fastbin (av, idx);		//현재 요청된 fastbin의 크기와 맞는 fastbin의 index를 찾는다.

위 코드는 현재 요청된 fastbin의 크기와 맞는 fastbin index를 찾는 코드인데,

mchunkptr pp = *fb;			//여기서 mchunkptr pp 에 fastbin에 속한 인덱스의 주소가 들어간다. 

do
        {
          victim = pp;
          if (victim == NULL)
            break;
        }
      while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
             != victim);

이후 do_while() 문으로 들어가는데, 

victim = pp 로 들어가는데, 

if문에서 victim == NULL 인지 검사한다. (즉, fastbin 이 존재하는지 검사하는것) 

만약 존재하지 않다면 종료, 

그렇지 않으면 선택한 chunk의 FD 를 참조해 대상 chunk 의 FD 가 가리키는 chunk를 fastbin 의 첫번째 

리스트로 업데이트해 LIFO 구조를 유지한다.