heap

dreamhack에서 use after free내용을 보다가 이해가 되지 않아서 정리를 하고 넘어가자.

먼저 chunk에 대해서 알아보자.

참고: https://rninche01.tistory.com/entry/heap3-glibc-malloc2-feat-chunk?category=838537

<청크의 크기>

32bit system: 8bytes의 배수로 할당

64bit system: 16bytes의 배수로 할당

 

example

debugging

gdb로 example을 디버깅해보자. malloc을 두번 한 후 heap을 보자.

1바이트, 2바이트를 요구했지만 0x20(32byte)씩 할당되었다.

 

그리고, 왜 malloc은 하나 했지만 청크는 3개가 생기는지 보자.

현재 malloc을 한번했는데, chunk는 3개가 있다. Allocated chunk 2개와 Top chunk이다.

vmmap으로 보면 heap영역은 0x555555559000 ~ 0x55555557a000이다.

첫번째 allocated chunk가 0x555555559000 ~ 0x555555559290

(0x555555559000+0x290    =0x555555559290)

두번째 allocated chunk가 0x555555559290 ~ 0x5555555592b0

(0x555555559290+0x20      =0x5555555592b0)

                   Top chunk가 0x5555555592b0 ~ 0x55555557a000

(0x5555555592b0+0x20d51=0x55555557a000)

로서 세 청크를 모두 합치면 heap영역이 된다.

 

free후 bins을 보자.

현재 5번 malloc한후 모두 free한 상황.

보면, tcachebins에서 0x20사이즈 청크가 2개, 0x30사이즈 청크가 3개이다.

첫번째 청크의 fd는 0x0 두번째 청크의 fd는 0x5555555592a0로 두개가 연결되어있다. (linked list인거같은데, Singly linked list인지, Doubly linked list인지, Circular linked list는 모르겠다..)

fastbins, unsortedbin, smallbins, largebins는 없다.

보아하니, tcachebins, fastbins, unsortedbin, smallbins, largebins들이 bins의 종류인것 같다.

 

잘 정리된 블로그를 보니, tchahebins는 glibc 2.26이후에 나왔다고 한다. (ㅠㅠ)

참고:https://rninche01.tistory.com/entry/heap4-glibc-malloc3-feat-bin?category=838537

small bin, large bin, fast bin, unsorted bin 네가지의bin을 설명하고 있다.

 

dreamhack-use after free의 설명을 보니, [해제할 청크가 탑 청크와 맞닿으면 안 된다는 것입니다. unsorted bin에 포함되는 청크와 탑 청크는 병합 대상이므로, 이 둘이 맞닿으면 청크가 병합됩니다. 이를 피하려면 청크 두 개를 연속으로 할당하고, 처음 할당한 청크를 해제해야 합니다.] 라고 한다.

tchahebins는 topchunk와 인접해도 병합되지 않고, 나머지bins는 topchunk와 맞다으면 병합되는것이다.(아마도)

 

ptmalloc에서는 총 128개의 bin으로 구성되어있다고 한다.

1개의 unsorted bin, 62개의 small bin, 63개의 large bin으로 구성되어있고, 2개는 쓰지 않는다고 한다.

small bin은 32바이트 이상 1024바이트 미만의 크기를 갖는 청크들이 보관된다.

small bin[0]은 32바이트부터 시작해서 16바이트씩 늘어나 small bin[61]은 1008바이트의 청크들이 보관된다.

small bin[i]의 크기는 16*(i+2) 바이트.

small bin은 원형이중연결리스트(circulat doubly-linked list) 구조이다.

small bin의 청크들은 ptmalloc의 병합대상이다. 메모리상에서 인접한 두 청크가 해제되어있고, 이들이 small bin에 들어있다면 이 둘은 병합된다.

 

fast bin은 일정 크기보다 작은 청크들을 관리하는 bin이다.

크기가 작은 청크들은 큰 청크들보다 자주 할당되고 해제되기 때문에 속도를 중시하기 위해 만들어진 bin이다.

리눅스에서는 32바이트 이상, 128바이트 이하의 청크들을 fast bin에 저장한다.

fast bin은 단일 연결 리스트 구조이다.

fast bin의 청크들은 메모리상에서 인접해도 병합대상이 아니다.

 

large bin은 1024바이트 이상의 크기를 갖는 청크들이 보관된다.

large bin은 하나의 인덱스에 여러 크기의 청크들이 보관된다. large bin[0]은 1024바이트 이상, 1088바이트 미만.

large bin[32]는 3072바이트 이상, 3584바이트 미만의 청크들이 보관된다. 범위는 로그적으로 증가한다.

large bin은 이중원형리스트 구조이다.

large bin은 메모리상에서 인접하다면 병합대상이다.

 

unsorted bin은 fast bin에 들어가지 않는 모든 청크들이다. (?? 무슨말이지.. small bin과 large bin은 어디가고)

unsorted bin은 원형이중연결리스트(circulat doubly-linked list) 구조이다.

 

tcache(thread locat cache)는 각 쓰레드에 독립적으로 할당되는 캐시 저장소이다.

tcache는 32바이트 이상, 1040바이트 이하의 청크들이 보관된다. (총 64개이다)

tcache는 단일 연결 리스트 구조이다.

tcache의 청크들은 메모리상에서 인접해도 병합대상이 아니다.

리눅스는 각 tcache에 들어갈 수 있는 청크의 개수를 7개로 제한하고 있다. 8개부터는 적절한 bin에 저장된다.