ptmalloc2에 관한 정보..

chunk의 크기에 대한 정보..

• 할당할 수 있는 메모리 사이즈는 16바이트의 배수로 정렬된다고 한다. 즉, 필요 바이트 수가 32라면 32바이트가 할당되고, 33이 되는 순간 48바이트가 할당되는 식이다. 그런데 malloc에는 헤더가 존재하고, 이 헤더가 가지는 크기가 16바이트이다. 기본 16바이트를 가지고 있기 때문에 32바이트를 할당하려고 하면 48바이트가 할당되게 된다.
• 이상한 점
  • 그렇다면, 33바이트를 할당시키려고 하면 총 48 < 33 + 16 < 64 이므로 64바이트가 할당되어야 할 텐데, 실제로 할당된 바이트 수를 보면 48바이트가 할당되었다고 나온다.
  • ????
• 해결
  • chunk의 구조를 보면 첫 8바이트는 prev_size에 해당한다.
  • prev_size가 필요한 이유 : chunk가 할당 해제될 때에 이전 chunk 또한 free 상태라면 병합이 되게 된다. (두 번째 8바이트의 in_use flag를 통해 알 수 있음)
  • 병합을 하려면 그 이전 chunk의 헤더의 값을 수정해야 하는데, 이 때에 prev_size를 이용해서 헤더에 접근할 수 있게 된다.
  • 즉, 이전 chunk가 free일 때에만 prev_size값이 유의미한 값이 되므로 이전 chunk가 사용중일 때에는 해당 공간을 이전 chunk의 데이터 영역으로 사용할 수 있게 만들면 효율이 늘어날 것이다.
  • 그러므로 33바이트를 할당한다고 64바이트가 실제로 할당되는 것이 아니라, 48바이트를 할당하되 다음 chunk의 시작부분 8바이트를 당겨쓰기 때문에 64바이트가 할당되게 된다.
  • 실제로 40바이트까지 할당하려고 하면 48바이트가 할당되고, 41바이트로 넘어가는 순간 64바이트로 늘어나게 된다.

main_arena의 bin에 대한 정보..

• small bin, large bin에서 chunk를 관리할 때, 원형 더블 링크드리스트로 관리된다고 한다. 이것까지는 OK였음.
• 그런데 main_arena의 메모리 값을 살펴보던 도중, 이상한 점을 발견함.
  
• 주목할 부분은 bins 부분인데, 잘 보면 같은 값 두 개가 16씩 증가하면서 배열을 이루고 있다.
• 처음에는 앞의 값이 head, 뒤의 값이 tail인 상태로 원형 리스트를 이루는가보다 라고 생각을 했는데, 실제 malloc된 chunk의 데이터를 보니 bin에 들어가고 나서 fd, bk값으로 이 배열에 적혀있던 주소값이 등록되어 있는 것을 알 수 있다. (사진은 귀찮아서 안 올림)
• 아니 그러면 어차피 넣고 뺄 때에 head, tail로만 접근을 하는데, 그러면은 굳이 배열에 적혀있던 주소값을 fd, bk에 넣을 이유가 있음??
• 그런데 병합과정을 보면, 이전 chunk를 병합을 하고 끝나는 것이 아니라 병합한 크기에 맞는 bin으로 옮기는 작업도 동반된다. 그래서 bin의 linked list에서 중간에 빼내는 경우도 실제로 존재한다.
• 실제로 소스 코드를 보았을 때,
  
  head, tail 구분 없이 unlink를 진행하는 것을 볼 수 있다.
• 아니 그러면 head, tail이 아니고 dummy node가 존재해야 하는 것 아님? 그런데 bins 배열에는 chunk 헤더가 존재하는 것이 아니라 그냥 16바이트만 존재하잖아.
• 그러면 사실 bins에 원래 적혀있던 주소가 그 지점의 주소가 아니라 16바이트 이전 지점의 주소가 아닐까?? 라고 의심하게 됨.
• 실제로 pwndbg로 main_arena 메모리 관찰.
  
  bins의 배열이 시작되는 지점인 main_arena+112를 봤을 때, 메모리는 b8bf0을 가리키지만 실제 저장된 값은 b8be0, 즉 16만큼 차이나게 된다.
• 실제로 struct malloc_chunk의 구조를 보면,
  
  fd, bk 가 16바이트 이후의 지점에 위치하는 것을 알 수 있다!!!!
• 결론 : 실제 bins 내부에는 struct malloc_chunk가 존재하지는 않지만, dummy node의 역할을 하게끔 주소가 잘 설정되어 있다!!

main_arena의 메모리 구조

• 사실 bins에 대해서만 살펴볼 것이다.

• malloc_state 구조체에 대해서 보면,
  
  mchunkptr bins[NBINS * 2 - 2];
  라고 선언이 되어있다.

• 실제 bins의 구성 요소는

  • 2 unused bins
  • 1 unsorted bin
  • 62 small bins
  • 63 large bins

  로 이루어져 있다.

• 그런데 왜 변수 선언 시에 -2를 하는가?

• 이것 또한 최적화 문제인듯.

• 0번째 idx에는 unused bin이 와야 하지만, 최적화로 인해서 0번째 idx는 아예 없애버리고 unsorted부터 시작하게 만들었다.(사실 원래 이게 맞는 것일수도? dreamhack에서는 0번째, 127번째가 unused라고 하긴 했었음)

결합 방법

• 뒤의 chunk와 결합
  • 뒤 뒤의 chunk의 prev_inuse bit확인 -> 결합
• 앞의 chunk와 결합
  • 자신의 prev_inuse bit 확인 -> 결합

tcache, fastbin 외의 다른 bins들은 왜 비효율적이게 doubly linked list를 사용할까?

• 자료구조 다시 공부해야 될 듯...
• 병합 과정이 일어나는 도중에 bins에서 unlink가 이루어지게 되는데, list의 구조를 유지해 주기 위해서 이전 fd, 이후 bk값을 바꾸어 주어야 한다. 그런데 여기서 single linked list를 사용하게 되면 이전 fd값을 바꾸어주기 위한 bk가 없으므로 불가능함. 그래서 double이 꼭 필요하다...

fastbin에서 병합이 일어나는 경우도 존재함.

• 애초에 빠른 것을 목적으로 했기 때문에 메모리 효율성에서 문제가 발생한다. 그래서 한 번씩 flush해 주게 됨. (unsorted bin으로)
• flush하는 경우
  • large bin의 범위에 해당하는 malloc이 호출되었을 경우
  • FASTBIN_CONSOLIDATION_THREDHOLD 을 초과하는 chunk가 free되었을 경우(0x10000 in default)
  • malloc_trim 또는 mallopt가 호출되는 경우

0x20000보다 더 큰 malloc이 발생했을 경우 chunk가 아닌 mmap으로 관리된다. 물론 free시에는 munmap이 호출됨.

large bin 에서 사용되는 fd_nextsize, bk_nextsize는 어디에 쓰일까??

• 일단 fd, bk에 대해서 살펴보자.
• large bin은 하나의 bin에 여러 사이즈의 chunk들이 들어있을 수 있으므로 효율적으로 탐색을 수행하기 위해 내림차순으로 정렬된 상태로 list에 chunk들이 들어가게 된다.
• 단순히 내림차순으로만 탐색이득을 보는 것이 아니라, fd_nextsize, bk_nextsize를 추가적으로 이용한다.
• 같은 크기를 가지는 chunk들 중 제일 앞의 chunk만 fd_nextsize, bk_nextsize를 가지며, fd_nextsize는 다음으로 작은 chunk들 중 제일 앞 chunk, bk_nextsize는 다음으로 큰 chunk들 중 제일 앞 chunk를 가리키게 된다. 물론 제일 큰 사이즈의 chunk의 경우 bk_nextsize는 제일 작은 chunk를 가리킨다.
• 이렇게 하는 이유?
  • 당연히 탐색속도가 더 빨라진다.
  • doubly linked list이므로 관리도 수월함.

top chunk와 병합 이후에 top_chunk의 크기가 m_trim_threshold보다 커지게 되면 top_chunk의 크기를 줄인다.

main_arena symbol을 찾을 수 없는 경우가 있는데, 이 경우에는 __malloc_hook + 0x10의 위치에 main_arena가 존재한다는 것을 알고 있으면 된다. 추가로, unsorted bin에 원래 적혀있던 주소 (bins[0])는 main_arena + 96에 해당한다.

libc버전에 따른 malloc 과정의 차이

• libc-2.3x (몇인지는 정확히 모르겠음. 아마 최신일듯?)
  
  여기 보면은 malloc을 tcache에서 해올 때 전제조건에 tcache->counts[tc_idx] > 0 이 달려있다.
• libc-2.27
  
  얘는 2.27 버전인데, tcache->entries[tc_idx] != NULL인 경우에 할당해 준다. 즉, double free에 의해서 값이 한 번 오염되면, NULL이 아닌 경우에는 계속 malloc을 해준다는 뜻임.

free도 한번 볼까용

• free는 다를 게 없네.
• 심지어 count변수가 없어서 그런건가 했더니 그런 것도 아님.
• key값은 따로 없다.

key를 사용하는 tcache의 경우, key값의 leak을 막기 위해서 malloc 후에 key위치에 해당하는 바이트를 0으로 초기화한다.

• 여기서 주의할 점
  got overwrite를 할 때나, 이런 저런 overwrite 기법을 쓸 때에 key 값이 0으로 초기화됨으로 인해서 오작동을 일으키는 경우가 있는지 꼭 확인해 보아야 한다.
• 나 같은 경우에 got overwrite를 하는데 free를 overwrite 했더니 그 바로 다음에 있던 puts의 got가 NULL로 초기화가 되어서 고장이 나서 작동이 안 한 경우가 있었다.