Heap - glibc 2.23 (2)

Heap - glibc 2.23 (_int_free)

---

_int_free()

1. _int_Free()

static void
_int_free (mstate av, mchunkptr p, int have_lock)

• mstate : struct malloc_state *의 다른 이름(typedef)이다.
• av : 아레나를 가리키는 포인터이다.
• mchunkptr : struct malloc_chunk *의 다른 이름이다.
• p : 사용자가 해제하려는 청크를 가리키는 포인터이다.
• have_lock : 아레나의 락(mutex)을 획득했는지 여부를 나타내는 플래그이다.

 

{
  INTERNAL_SIZE_T size;        /* its size */
  mfastbinptr *fb;             /* associated fastbin */
  mchunkptr nextchunk;         /* next contiguous chunk */
  INTERNAL_SIZE_T nextsize;    /* its size */
  int nextinuse;               /* true if nextchunk is used */
  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
  mchunkptr bck;               /* misc temp for linking */
  mchunkptr fwd;               /* misc temp for linking */

  const char *errstr = NULL;
  int locked = 0;

• size : 해제할 청크 p의 크기를 저장한다.
• fb : 청크가 fastbin에 들어갈 경우, fastbin의 헤드를 가리킬 포인터이다.
• nextchunk : 물리적으로 p 바로 다음 위치한 청크를 가리킨다.
• nextsize : nextchunk의 크기이다.
• nextinuse : nextchunk가 사용 중인지 여부를 나타내는 플래그이다.
• prevsize : 물리적으로 p 바로 이전에 위치한 청크의 크기이다.
• bck, fwd : unlink와 bin에 청크를 삽입할 때 포인터를 임시로 저장하는 다용도 변수이다.
• errstr, locked : 오류 처리 및 락 확인 변수이다.

 

  size = chunksize (p);

• size 필드의 하위 3개 비트(P, M, A 플래그)를 제거하여 순수 크기만 size에 저장한다.

 

유효성 및 보안 검사 코드

  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
      || __builtin_expect (misaligned_chunk (p), 0))

• p > -size : p + size 연산이 주소 공간의 끝을 넘어 다시 0에 가까운 주소로 돌아오는 경우를 감지한다.
• misaligned_chunk(p) : 해제하려는 청크의 시작 주소 p가 메모리 정렬(alignment) 규칙이 맞는지 확인한다.

__builtin_expect

---

컴파일러 내장 함수이다.

long __builtin_expect(long exp, long c)

exp라는 표현식의 결과가 c일 것이라고 강력하게 예상한다고 컴파일러에게 알려준다.

 

if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))

• size < MINSIZE : size 필드값이 시스템이 정의한 최소 청크 크기(MINSIZE)보다 작은지 확인한다.
• !aligned_OK(size) : size 값 자체가 메모리 정렬 규칙에 맞는지 확인한다.

__glibc_unlikely

---

가독성을 위한 매크로이다.

__builtin_expect를 더 읽기 쉽게 만들어주는 glibc 라이브러리 내의 매크로

__glibc_unlikely(조건문)은 “이 조건문은 항상 거짓일 것이다”라는 의미

 

check_inuse_chunk(av, p);

• 해제하려는 청크 p가 현재 사용중(in-use) 상태가 맞는지 확인한다.
• p 바로 다음 청크의 PREV_INUSE 비트를 확인하는 방식으로 동작한다.
• double free를 방지한다.

 

fastbin 처리 로직

1. 진입 조건

  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

• size ≤ get_max_fast() : 해제하려는 청크의 크기가 max_fast 이하의 작은 청크여야지만 if 블록으로 진입한다.
• && (chunk_at_offset(p, size) != av->top) : TRIM_FASTBINS 옵션이 활성화된 경우에만 적용된다 해제할 청크가 top chunk와 인접해 있다면 fastbin에 넣지 않고 일반 처리 경로로 보낸다.

 

2. 보안 검사(heap overflow)

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

• 해제하려는 청크(p)가 아닌 물리적으로 그 다음 청크의 헤더를 검사한다.
  • 다음 청크의 size가 비정상적으로 작거나 (≤ 2 * SIZE_SZ)
  • 다음 청크의 size가 비정상적으로 크거나(≥ av→system_mem)
• fastbin은 속도를 위해 보통 mutex락 없이 진입한다. 따라서 av→system_mem값 비교시 경쟁 조건이 발생할 수 있기 때문에 바로 오류를 내지 않고 한번 더 검사한다.

 

3. 삽입 준비

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    set_fastchunks(av);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);

• free_perturb : 해제된 메모리의 사용자 데이터 영역을 특정 패턴으로 덮어써서 UAF취약점 악용을 어렵게 만든다
• set_fastchunks(av) : 아레나에 fastbin 청크가 최소 하나 이상 있음을 알리는 플래그를 설정한다.
• idx = fastbin_index(size) : 청크 크기에 맞는 올바른 fastbinsY 배열의 인덱스를 계산한다.
• fb = &fastbin (av, idx) : fb가 해당 fastbin리스트의 시작점(head)를 가리키도록 한다.

 

4. 핵심 삽입 및 검사 루프

    mchunkptr old = *fb, old2;
    unsigned int old_idx = ~0u;
    do
      {
	if (__builtin_expect (old == p, 0))
	  {
	    errstr = "double free or corruption (fasttop)";
	    goto errout;
	  }
		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 (old == p) : Double Free 방어 로직이다. 해제하려는 청크 p가 old와 같으면 double free bug가 발생하므로 오류를 발생시킨다.
• p->fd = old2 = old
  • old2 = old : 현재 fastbin의 맨 앞 청크 값을 old2에 복사한다.
  • p→fd = old2 : old2의 값을 p→fd에 복사한다.
• while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2) : fb의 값이 old2의 값과 같은지 비교한다.
  • 같으면 (성공) : fb의 값을 p로 바꾸고 연산이 성공했음을 알린다.
  • 다르면 (실패) : fb의 값을 바꾸지 말고 fb에 들어있는 값을 old에 복사 후 연산 실패를 알린다.

old2 는 왜 필요할까?

---

old2는 while문에서 루프가 시작될 때 fb값을 저장하는 스냅샷 역할을 한다.

만약 old2 없이 old만 사용한다면 catomic연산이 실패했을 때 old값이 업데이트 되면서 비교해야 할 원래의 기준점을 잃어버리게 된다.

 

5. 최종 일관성 검사

    if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
      {
	errstr = "invalid fastbin entry (free)";
	goto errout;
      }
  }

• 삽입하기 직전 리스트의 맨 앞에 있던 청크(old)의 크기 인덱스(old_idx)가 지금 막 삽입한 청크의 인덱스(idx)와 같은지 비교한다. → 모든 fastbin 리스트에는 같은 크기의 청크만 있어야 하기 때문에 두 인덱스가 다르면 이미 리스트가 손상되었다는 의미이다.

 

일반 청크 처리 로직 (Unsorted bin)

1. 진입 조건

else if (!chunk_is_mmapped(p)) {

• fastbin 크기보다 크고 mmap으로 할당된 청크가 아닐 때 이 경로로 진입한다.

 

2. 동기화 및 안전 검사

if (! have_lock) {
      (void)mutex_lock(&av->mutex);
      locked = 1;
    }

    nextchunk = chunk_at_offset(p, size);

    /* Lightweight tests: check whether the block is already the
       top block.  */
    if (__glibc_unlikely (p == av->top))
      {
	errstr = "double free or corruption (top)";
	goto errout;
      }
    /* Or whether the next chunk is beyond the boundaries of the arena.  */
    if (__builtin_expect (contiguous (av)
			  && (char *) nextchunk
			  >= ((char *) av->top + chunksize(av->top)), 0))
      {
	errstr = "double free or corruption (out)";
	goto errout;
      }
    /* Or whether the block is actually not marked used.  */
    if (__glibc_unlikely (!prev_inuse(nextchunk)))
      {
	errstr = "double free or corruption (!prev)";
	goto errout;
      }

    nextsize = chunksize(nextchunk);
    if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (nextsize >= av->system_mem, 0))
      {
	errstr = "free(): invalid next size (normal)";
	goto errout;
      }

• if (! have_lock) : have_lock 파라미터가 false였다면 mutex_lock을 호출하여 아레나를 잠근다.

1. Top chunk 중복 해제 검사

if (__glibc_unlikely (p == av->top))

• 해제하려는 청크의 포인터 p가 현재 아레나의 top포인터와 같은 주소를 가리키는지 직접 비교한다. → top chunk는 항상 사용 중으로 간주되는 청크로 free(p)의 대상이 될 수 없다.

2. 경계 초과 검사

if (__builtin_expect (contiguous (av)
			  && (char *) nextchunk
			  >= ((char *) av->top + chunksize(av->top)), 0))

• nextchunk(p 바로 다음 청크)의 주소가 av→top 청크의 끝 주소보다 크거나 같은지 확인한다. → 아레나의 유효한 힙 영역을 벗어났는지 확인한다.

3. PREV_INUSE 비트 검사 (double free 방어)

if (__glibc_unlikely (!prev_inuse(nextchunk)))

• nextchunk의 size 필드에 있는 PREV_INUSE 비트를 확인한다.

4. 다음 청크 헤더 손상 검사

if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (nextsize >= av->system_mem, 0))

• nextchunk의 size 필드 값을 검사한다.
  • size가 최소 청크 헤더 크기(2 * SIZE_SZ)보다 작은지 확인한다.
  • size가 아레나 전체 시스템 메모리(av→system_mem)보다 크거나 같은지 확인한다.

 

3. 데이터 파기 (UAF 공격 방어)

free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

• chunk2mem(p) : malloc 이 사용자에게 반환하는 실제 메모리 영역이다
• size - 2 * SIZE_SZ : 청크의 전체 크기(size)에서 헤더 크기를 뺀 순수 사용자 데이터 영역의 크기를 계산한다.
• free_perturb() : 해제된 청크의 사용자 데이터 영역 전체를 특정 바이트 패턴으로 덮어씌운다.

 

4. 뒤로 병합(Backward Consolidation)

    if (!prev_inuse(p)) {
      prevsize = p->prev_size;
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      unlink(av, p, bck, fwd);
    }

• if (!prev_inuse(p)) : 물리적으로 바로 이전 청크가 free 상태일 때만 이 블록이 실행된다.
• prevsize = p->prev_size : p의 prev_size 필드를 읽어 이전 청크의 크기를 가져온다.
• size += prevsize : 현재 청크의 크기를 저장하고 있는 size에 이전 청크의 크기 prev_size를 더하여 병합될 전체 크기를 계산한다.
• p = chunk_at_offset(p, -((long) prevsize)) : (mchunkptr)((char*)p - prevsize) 연산을 통해 포인터 p 자체를 이전 청크의 시작 주소로 뒤로 이동시킨다.
• unlink(av, p, bck, fwd) : p가 가리키는 청크(원래의 이전 청크)를 bin에서 제거하는 매크로이다.

chunk_at_offset 은 뭘까?

---

#define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s)))

glibc에서 chunk_at_offset 매크로는 위와 같이 정의되어 있다.

 

 

(long) prevsize는 왜 있을까?

---

prevsize의 타입 INTERNAL_SIZE_T는 unsigned(부호 없는 정수)이다.

부호 없는 정수에 마이너스(-) 연산을 바로 적용하면 의도치 않은 큰 양수 값으로 변할 수 있기 때문에 (long)으로 먼저 부호 있는 정수로 형변환 한 뒤 안전하게 음수로 만들어 계산한다.

 

5. 다음 청크 상태 확인

    if (nextchunk != av->top) {
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

• if (nextchunk != av->top) : 다음 청크가 top 청크가 아닌 경우를 처리한다.
• nextinuse = inuse_bit_at_offset(nextchunk, nextsize) : nextchunk의 사용 여부를 판단해서 nextinuse에 저장한다.

 

6. 앞으로 병합(forward consolidation)

			if (!nextinuse) {
				unlink(av, nextchunk, bck, fwd);
				size += nextsize;
      } else
				clear_inuse_bit_at_offset(nextchunk, 0);

• if (!nextinuse) : 다음 청크가 free일 경우 처리한다.
• unlink(av, nextchunk, bck, fwd) : nextchunk를 현재 속해있는 bin(Unsorted, Small, Large bin 중 하나)에서 제거하는 매크로이다.
• size += nextsize : unlink로 분리한 nextchunk의 크기(nextsize)를 현재 병합된 청크의 크기를 담고 있는 size에 더한다.
• clear_inuse_bit_at_offset(nextchunk, 0) : 만약 청크가 사용 중이라면 nextchunk의 PREV_INUSE 필드를 0으로 설정한다.

 

7. Unsorted Bin에 청크 삽입

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

 

1. Unsorted Bin 포인터 준비 및 무결성 검사

      bck = unsorted_chunks(av);
      fwd = bck->fd;
      if (__glibc_unlikely (fwd->bk != bck))

• bck = unsorted_chunks(av) : unsorted_chunks 매크로를 통해 Unsorted bin의 헤드 주소를 가져와 bck 포인터에 저장한다. → unsorted bin은 bins[1]이므로 bck는 bins 배열의 시작 부분을 가리키게 된다.
• fwd = bck->fd : bck→fd는 현재 Unsorted bin의 가장 첫 번째 청크를 가리킨다. 이 주소를 fwd에 저장한다.
• if (__glibc_unlikely (fwd->bk != bck)) : 이중 연결 리스트의 무결성 검사이다.

2. 새로운 청크(p)를 리스트의 맨 앞에 삽입

      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;

• p->fd = fwd : 새로 삽입될 청크 p의 fd(앞쪽) 포인터가, 기존의 첫 번째 청크였던 fwd를 가리키게 한다.
• p->bk = bck : p의 bk(뒤쪽) 포인터가 리스트의 헤드인 bck를 가리키게 한다.
• bck->fd = p : 리스트의 헤드(bck)의 fd 포인터가 새로운 첫 번째 청크인 p를 가리키도록 업데이트 한다.
• fwd->bk = p : 기존의 첫 번째 청크였던 fwd의 bk 포인터가 p를 가리키도록 업데이트한다.

3. Large bin을 위한 사전 정리

      if (!in_smallbin_range(size))
				{
				  p->fd_nextsize = NULL;
				  p->bk_nextsize = NULL;
				}

• if (!in_smallbin_range(size)) 만약 병합된 청크의 크기가 Small bin의 범위를 넘어 Large bin에 속할 크기라면 이 블록이 실행된다.
• p->fd_nextsize = NULL; p->bk_nextsize = NULL : fd_nextsize와 bk_nextsize 포인터를 NULL로 초기화 한다.

4. 최종 상태 및 검증

      set_head(p, size | PREV_INUSE);
      set_foot(p, size);

      check_free_chunk(av, p);

• set_head(p, size | PREV_INUSE) : p의 헤더(size 필드)에 병합된 최종 크기(size)와 PREV_INUSE 비트(1)를 함께 기록한다.
• set_foot(p, size) : 청크의 맨 끝부분(물리적으로 다음 청크의 prev_size 필드 위치)에 자신의 크기르 한번 더 기록한다. (뒤로 병합을 위해)
• check_free_chunk(av, p) : 디버깅 모드에서 free된 청크의 상태가 유효한지 최종 확인한다.

PREV_INUSE를 왜 1로 기록할까?

---

free된 청크 자체의 PREV_INUSE 비트는 항상 1로 설정된다.

free된 청크의 prev_size는 유효하지 않기 때문에 물리적으로 다음 청크가 이 free 청크를 볼 때 prev_size를 읽어려는 시도를 하지 않도록 막기 위함이다.

 

8. Top Chunk 과의 병합

    else {
      size += nextsize;
      set_head(p, size | PREV_INUSE);
      av->top = p;
      check_chunk(av, p);
    }

• size += nextsize : size는 현재까지 병합된 청크와 바로 다음 top chunk가 합쳐진 새로운 top chunk의 크기를 계산한다.
• set_head(p, size | PREV_INUSE) : set_head 매크로를 이용해 p의 헤더(size필드)에 방금 계산한 새로운 size를 기록한다.
• av->top = p : 아레나(av)가 관리하는 top chunk 포인터 av→top이 기존의 top chunk 시작 주소가 아닌 새로운 시작 주소 p를 가리키도록 한다.
• check_chunk(av, p) : 디버깅 모드에서 새로 만들어진 top chunk의 상태가 유효한지 검사하는 매크로이다.

 

9. 후처리 후 메모리 반환

    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
      if (have_fastchunks(av))
				malloc_consolidate(av);

      if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
			if ((unsigned long)(chunksize(av->top)) >=
			    (unsigned long)(mp_.trim_threshold))
			  systrim(mp_.top_pad, av);
#endif
      } else {
			heap_info *heap = heap_for_ptr(top(av));

			assert(heap->ar_ptr == av);
			heap_trim(heap, mp_.top_pad);
      }
    }

    if (! have_lock) {
      assert (locked);
      (void)mutex_unlock(&av->mutex);
    }
  }

 

1. 후처리 (힙 메모리 반환 시도)

if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD)

• size가 FASTBIN_CONSOLIDATION_THRESHOLD(보통 64KB)라는 매우 큰 임계값보다 크거나 같을 때만 이 블록이 실행된다.

2. 사전 작업

if (have_fastchunks(av))
				malloc_consolidate(av);

• have_fastchunks(av) : 아레나에 fastbin 청크가 존재하는지(FASTCHUNKS_BIT 플래그 확인) 먼저 검사한다.
• malloc_consolidate(av) : fastbin 청크가 남아있다면 malloc_consolidate 함수를 호출한다. → fastbinsY 배열을 전부 순회하며 모든 Fastbin 청크들을 꺼내, 일반적인 병합 과정을 거쳐 Unsorted bin으로 옮긴다.

3. 실제 메모리 반환

      if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
			if ((unsigned long)(chunksize(av->top)) >=
			    (unsigned long)(mp_.trim_threshold))
			  systrim(mp_.top_pad, av);
#endif
      } else {
			heap_info *heap = heap_for_ptr(top(av));

			assert(heap->ar_ptr == av);
			heap_trim(heap, mp_.top_pad);
      }
    }

• systrim(메인 아레나) : 메인 아레나 힙은 보통 sbrk() 시스템 콜로 관리된다.
  • systrim 함수는 sbrk()에 음수 값을 전달하여 프로그램 브레이크를 뒤로 이동시키고 이를 통해 운영체제에 실제 메모리를 반환한다.
• heap_trim(쓰레드 아레나) : 쓰레드 아레나는 mmap()으로 할당된 별도의 힙을 사용한다.
  • heap_trim 함수는 해당 힙의 끝부분에 사용되지 않는 메모리 페이지가 충분히 많으면 munmap() 시스템 콜을 통해 해당 페이지들을 시스템에 반환한다.

4. 락 해제

    if (! have_lock) {
      assert (locked);
      (void)mutex_unlock(&av->mutex);
    }
  }

• if (! have_lock) : _int_free 함수가 처음에 락 없이 호출되어 이 블록의 맨 앞에서 직접 mutex_lock을 호출했는지 확인한다.
  • 락을 직접 걸었다면 mutex_unlock을 호출하여 아레나의 잠금을 해제한다.

 

mmap 된 청크 처리

  else {
    munmap_chunk (p);
  }
}

• 해제하려는 p 가 다음 조건을 모두 만족할 때 실행된다.
  • fastbin 크기보다 크다.
  • size 필드의 IS_MMAPPED 필드가 1로 설정되어 있다.
• munmap_chunk (p) : munmap_chunk는 p포인터로부터 mmap으로 할당받았던 영역의 시작 주소와 전체 크기를 알아내어 해당 영역 전체를 시스템에 돌려준다.