Heap_기초 1

정리

오늘 정리는 힙 공부를 하면서 여기저기 많이 들려보았지만 fkillrra님의 블로그를 보고 추천영상을 받아 그것을 기초로 정리하였다.

마지막 부분에 reference를 첨부했으니 그 글을 보는 것을 추천한다.

 

또한 이 글은 힙에 대한 기초적인 내용의 이해를 위해 glibc_2.23버전에서 실습하였다. (ubuntu16.04)

---

 

메모리 구조에 대해 공부를 하다보면 위와 같은 자료를 많이 보았을 것이다.

이번 포스팅에서는 위에 구조에서 나누어진 Code(text), Data, Heap, Stack 영역 중 Heap 영역에 대해서 정리를 할 예정이다.

Heap

Heap이란 프로그램이 실행되는 도중 동적으로 할당하고 해제하여 사용하는 메모리 영역을 의미한다.

C 에서 사용하는 malloc 함수가 대표적인 메모리 할당 함수이며, 이렇게 할당된 공간을 다 사용하고 난 후 해제해주는 것이 free이다.

동적 메모리 할당자의 종류

현존하는 메모리 할당자는 매우 많으며 그 중 일부분에 대해서만 정리를 해보겠다.

1. tcmalloc
   • thread - caching memory allocation의 약자로 구글에서 만든 메모리 할당 라이브러리이다.
2. Jemalloc
   • Jason Evans씨가 만든 메모리 할당자(앞글자를 따 je)이다. Facebook에서 사용된다.
3. Libumem
   • Libumem은 응용 안에서 메모리 관리 버그를 찾아내는데 사용되는 라이브러리이다. 솔라리스 9 업데이트 3 이상부터 포함되었다.
4. dlmalloc(중요)
   • 리눅스에서 힙 관리에 사용되는 메모리 할당자이다.
5. ptmalloc(중요)
   • dlmalloc이 사용되다가 쓰레드 기능이 추가된 ptmalloc이 현재 리눅스에서 사용되어지고 있다.

• 따라서 현재 우분투에서 사용되는 메모리 할당자의 기본 알고리즘은 ptmalloc의 근간이었던 dlmalloc과 동일하다.

Heap은 어떻게 생기고 없어질까?

char *p = malloc(size)
// 원하는 size만큼 malloc을 호출하여 동적 메모리 할당
free(p)
// 사용한 메모리를 free하여 반환

heap을 호출하기 전

heap을 호출한 후

위에 두 사진처럼 힙은 런타임시에 호출한 후에 0x21000만큼 미리 메모리 영역을 할당한 뒤 이 사이즈 안에서 사용한다.

free함수 호출한 후

여기서 주의해야 할 점이 있는데 free함수를 호출하면 할당을 해제한다고 생각하여 heap영역이 사라진다고 생각할 수 있으나 그렇지 않고 그대로 남아있게 된다.

chunk

// malloc.c 파일에 chunk 구조
// line 1147
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if allocated            | |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             User data starts here...                          .
        .                                                               .
        .             (malloc_usable_size() bytes)                      .
        .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of chunk                                     |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

malloc.c 파일에서는 힙 할당에 대한 chunk 구조를 위와 같이 표현하였다. 이것을 도형을 이용하여 간단하게 표현하면 아래와 같아진다.

• mem

  malloc.c 소스코드를 보면 malloc을 통해 할당받은 메모리 영역을 표현하는 이름

• chunk

  header(사이즈 정보)와 mem을 포함하는 영역

• size

  현재 chunk의 크기와 3가지 속성(flag)를 나타냄

  32bit는 8byte, 64bit는 16byte 단위로 정렬

• prev_size

  인접한 앞쪽 chunk의 크기를 나타냄

  앞쪽 청크가 free될 때 prev_size 부분이 초기화 됨

chunk size

• size

  현재 chunk의 크기와 3가지 속성(flag)를 나타냄

  32bit는 8byte, 64bit는 16byte 단위로 정렬

왜 사이즈만이 아니라 3가지 속성도 같이 나타내게 했을까?

그 이유는 32bit환경에서 8byte 단위로 정렬되어 하위 3byte가 사용되지 않기 때문이다.

• 8byte 단위 정렬

prev_inuse bit (0x1) (가장 중요)

• prev_inuse bit (0x1)

  인접한 이전 chunk가 할당되면 1

  인접한 이전 chunk가 해제되면 0

• prev_inuse bit가 실질적으로 내포하는 의미

  이전 청크는 병합의 후보로 간주되어선 안된다.

• example

heap1과 heap2가 할당된 상태에서 heap2의 size를 봅시다.

heap2의 size는 heap2와 인접한 heap1이 할당되어 있기 때문에 heap2 chunk의 크기와 활성화된 prev_inuse bit의 값을 더한 값이 된다.

할당을 해제하게 되면 prev_inuse bit는 비활성화 된다.

is_mmaped bit (0x2)

• is_mmaped bit (0x2)

  mmap으로 할당되었으면 1

  mmap으로 할당되지 않았으면 0

non_main_arena bit (0x4)

• non_main_arena bit (0x4)

  thread arena에 속하면 1

  thread arena에 속하지 않으면 0

chunk의 종류

chunk의 종류는 크게 3가지로 나뉜다.

• Allocated chunk

• Freed chunk

• Top chunk

  해외 문서에서는 Top chunk를 wildness chunk라고 부르기도 함

Allocated chunk

char *p = malloc(size)

위 코드(malloc())를 호출했을 때 heap영역에 생기는 chunk이며, free된 chunk와 구분하기 위해 Allocated chunk라고 부른다.

#include <stdio.h>
#include <stdlib.h>

void main(){
    char *heap1 = malloc(16);
}

다음과 같은 코드를 이용해 메모리를 직접 보도록 하자.

malloc()을 호출한 뒤 rax레지스터에 반환되는 값은 할당된 chunk의 주소이므로 위와 같은 방식으로 할당된 chunk를 찾아갔다.

처음 할당된 chunk이므로 prev_size는 0으로 초기화 되어있는것을 확인할 수 있다.

size는 mem으로 사용된 16byte와 header로 할당된 16byte 그리고 활성화된 prev_inuse bit 1byte를 합친 0x21이 된 것을 확인할 수 있다. ( 맨 처음 할당된 chunk의 경우 prev_inuse는 활성화 된다.)

mem(16) + header(16) + prev_inuse(1) = 33 = 0x21

Freed chunk

free(p)

위 코드 (free())를 호출한 경우, 해제된 chunk를 의미한다.

freed chunk의 경우 실제로 반환되는 것이 아니라 힙 영역에 남아있으며, Allocated chunk 구조에서 Freed chunk 구조로 변경된다.

구조를 보면 freed chunk는 할당 해제된 chunk들을 효율적으로 관리하기 linked list로 관리하며 이러한 특성상 linked list를 가리킬 포인터가 필요하며 그것이 fd와 bk이다.

fd와 bk의 의미는 아래와 같다.

fd : Forward pointer to next chunk in list
bk : Back pointer to previous chunk in list

이 때 512byte보다 크기가 큰 chunk를 large chunk라고 하며, 이렇게 크기가 큰 경우 비슷한 크기끼리 관리하는 heap의 특성상 크기가 작은 freed chunk와 구분하기 위해 fd_next_size, bk_next_size 를 이용하여 관리한다.

#include <stdio.h>
#include <stdlib.h>

void main(){
    char *heap1 = malloc(0x90);
    char *heap2 = malloc(0x90);

    free(heap1);
    free(heap2);
}

다음과 같은 코드를 이용해 메모리를 살펴보았다.

free 함수 호출 후 다음과 같이 fd와 bk가 생겨 double linked list로 관리하는 것을 확인할 수 있다.

Top chunk(wildness chunk)

힙 영역에 가장 마지막에 위치하며 새롭게 할당되면 top chunk에서 분리해서 반환하고 top chunk에서 인접한 chunk가 free되면 병합한다.

#include <stdio.h>
#include <stdlib.h>

void main(){
    char *heap1 = malloc(0x90);
    char *heap2 = malloc(0x90);
    
    free(heap2);
    free(heap1);
}

일반적으로 top chunk는 0x21000의 사이즈를 가지며 재사용 가능한 chunk가 존재하지 않고, 할당해야 하는 chunk를 top chunk가 감당할 수 있을 때 top chunk에서 쪼개어 할당한다는 특징을 가지고 있다.

위에 사진을 보면 top chunk의 사이즈는 0x20ec1이라는 값을 가지고 있는데 이는 prev_inuse bit 0x1을 제외한 0xa0의 사이즈의 chunk를 두번 호출한 뒤의 사이즈다

0x21000 - 0xa0 - 0xa0 = 0x20ec0 // top chunk size

또한 앞서 인접한 chunk가 free되면 top chunk에 병합시킨다고 하였는데 실제로 free 한 후 top chunk에 병합된 것을 확인할 수 있었다.

---

요약

• Heap

  동적 할당 메모리이다.

  할당자의 종류는 다양하게 있다.

  대표적인 것으로 glibc 의 dlmalloc과 ptmalloc2가 있다.

• chunk

  • allocated chunk

    malloc() 호출 시 생기는 chunk

  • freed chunk

    free() 호출 시 생기는 chunk

    bk와 fd가 생기며 linked list로 관리된다.

  • top chunk

    malloc()이 호출 되었을 때 top chunk의 size가 충분하다면 top chunk에서 분할하여 할당시켜준다.

    인접한 chunk에 free()가 호출 되었을 때 병합시키는 역할도 한다.

---

삽질

• glibc 버전

  그냥 무작정 힙 공부해야지 하고 영상을 보고 따라했는데 내가 사용하는 ubuntu의 glibc 버전은 2.31이었고 영상에 glibc는 2.23버전이었다. (또한 대부분의 블로그도 2.23으로 실습을 하더라)

  glibc_2.26? 버전부터는 tcachebin이라는 것이 생겼으며 맨 처음 이곳에 할당을 하고 그 후부터 fast bin과 같은 원래 사용하던 bin에 할당한다는 것을 알게되었다. 그래서 선배의 추천으로 docker를 이용하여 ubuntu16.04를 깔아 glibc_2.23의 환경으로 실습을 다시 시작했다.

• free 실습

  영상에서는 double linked list라서 bk와 fd라는 두개의 link가 생겨야 한다고 하는데 계속 single linked list로 link가 하나밖에 생기지 않더라....

  알고보니 bin이라는 힙 메모리에서 할당/해제되는 chunk들을 관리하기 위한 알고리즘이 다양한 종류가 있는데 fast bin과 small bin, large bin 등 종류가 엄청 많았다.

  fast bin은 0x60byte 이하의 chunk들을 관리하는데 이 fast bin이라는 놈은 single linked list라고 한다.

  그래서 정상적으로 fd와 bk를 모두 보려면 double linked list를 사용하는 small bin 또는 large bin을 이용해야하는데 이것은 chunk의 size를 0x60보다 크게 주면 해결되었다.

---

Reference

https://www.youtube.com/watch?v=l0GVitgBPf0&ab_channel=koreangang // 힙 추천 영상

 

 

 

 

 

 

https://hackstoryadmin.tistory.com/entry/What-is-heap-part1

What is heap - part1

https://velog.io/@woounnan/SYSTEM-Heap-Basics-Bin

PWNABLE] Heap Basics - Bin