About Heap(2)

이전 글에서 malloc_chunk 구조체를 통해서

chunk의 구조에 대해서 간략하게 알아봤다.

이번에는 malloc,free시의 chunk에 대해 알아보고 bin에 대해서도 작성하고자 한다.

---

1.1 Allocated Chunk

prev_size

: 이전 청크가 해제된 경우, 해제된 이전 청크의 주소를 prev_size에 저장을 한다.

  만약 이전 청크가 할당되어 있는 경우에는 이전 Chunk의 사용자 데이터가 배치 된다.

 

size

: 할당된 청크의 크기를 저장하고, 하위 3bit는 flag정보를 저장한다.

 

    About Flag

    NON_MAIN_ARENA [A] (0x4)

    : Sub Arena로 할당을 받았을 시 1로 설정,

    Main Arena로 할당을 받았을 시 0로 설정

 

    IS_MMAPPED [M] (0x2)

    : mmap을 통해 할당된 경우 1로 설정.

    (※이전 글에서 언급했다시피 크기가 큰 사이즈는 mmap을 통해 힙 메모리 할당)

    이러한 청크들은 bin내에 속하지 않고 free시 munmap을 통해 해제.

 

    PREV_INUSE [P] (0x1)

    :현재 청크 바로 전의 청크가 할당되어 있는 경우 1로 설정됨.

 

1.2 Free Chunk

prev_size

: 서로 인접한 free chunk가 있을 시 하나의 단일 free chunk로 결합된다.

  따라서, 항상 해제된 청크의 이전 청크를 할당하고 있어서, prev_size는 이전 청크의 사용자 데이터를 저장하고 있다.

 

size

: free된 chunk의 크기를 저장한다.

 

fd

: 동일한 bin내에서 다음 청크를 가리킨다.

 

bk

: 동일한 bin내에서 이전 청크를 가리킨다.

 

Bins

:Freelist data structures으로 free chunk들을 크기를 기준으로 bin에 할당하게 된다.

• Fast bin
• Unsotred bin
• Small bin
• Large bin

fastbinsY: 이 배열은 fast bins 수용한다.

bins: 이 배열은 unsotred,small 그리고 large bin을 수용한다.

       전체적으로 126개의 bins이 있고, 아래와 같이 나뉜다:

 

• Bin 1- Unsorted bin
• Bin2 to Bin 63 - Small bin
• Bin 64 to Bin 126 - Large bin

 

Fast Bin

: Chunk의 사이즈가 16~80 byres인것을 fast chunk라고 부른다.

  fast chunk를 수용한 bin을 fast bin이라고 부른다.

  다른 bins들에 비해서 fast bins은 메모리 할당과 해제가 빠르다.

• bin의 개수 - 10
  • 각 fast bin은 free chunk로 구성된 단일 연결리스트(binlist)를 가진다. list의 중간에서 fastbins 청크들이 제거 될수가 없기 때문에 사용이 된다. LIFO 구조를 이용해서 list의 앞과 끝에서만 추가,제거가 일어난다.
• 청크의 크기 - 각 8bytes
  • Fast bin은 각 8bytes 크기를 갖는 청크의 binlist를 갖는다. 예) 첫번째 fastbin(index 0)은 16bytes 크기의 청크 binlist를 가지며, 두번째 fastbin(index 1)은 24bytes 크기의 청크 binlist를 갖는식으로 이루어진다.                (동일한 크기의 fastbin끼리 binlist를 갖는 것 같음(??))
  • fast bin 내부의 청크는 동일한 크기다.
• Malloc 초기화시, fastbin의 최대 크기는 64(!80)bytes으로 설정되어있다. 따라서 기본 청크의 크기는 16~64인 경우, fast chunk로 분류된다.
• 병합 없음 - 서로 인접해 있을 수 있는 청크는 단일 연결 리스트로 결합되지 않는다. 병합을 하지 않으면                                외부 파편화가 일어날 수도 있지만 해제 속도는 빠르다.
• Malloc(fast chunk) -
  • 초기 fast bin의 최대크기와 fast bin의 인덱스들은 비어있기 때문에 사용자가 fast chunk를 요청할지라도      fast bin 대신 small bin이 할당 될 수 있다.
  • 이후 비어있지 않게되면 fast bin 인덱스는 해당되는 binlist를 검색을 하여 계산된다.
  • 위에서 반환된 첫번째 청크는 삭제되고 사용자에게 반환된다.
• Free(fast chunk) -
  • Fast bin 인덱스는 해당되는 binlist로부터 검색을하여 계산된다.
  • free chunk는 위에서 반환된 binlist의 앞쪽에 추가된다.

 

 

 

Unsorted Bin

: small이나 large chunk가 free가 되었을 때 해당 bins으로 바로 들어가는 것이 아니라

 unsorted bin으로 들어가게 된다. 이러한 방식은 최근 해제된 같은 크기의 청크가 있다면

 재사용을 하게 만들어준다. 해당 과정에서 한번 검색을 거쳤음에도 사용이 되지 않은 chunk들은

 각자 자신이 속해야하는 bin list로 들어가게된다.

 

 

Small Bin

: 사이즈가 512bytes 보다 작은 chunk를 small chunk라고 부른다. small chunk들은 small bins으로 속하게 된다.

 small bins은 large bins보다 메모리 할당과 해제부분에서 더 빠르다.(fast bins보다는 느림)

• bin의 개수 - 62
  
  • 각 small bin은 free chunks로 이루어진 이중 연결리스트를 갖는다. 이중연결리스트는 list의 중간에서 small bin chunk를 해제를 할 수 있기 때문에 사용된다. 추가는 앞쪽에서 이루어지고 삭제는 뒤쪽 끝에서 발생한다. -FIFO
• 청크의 크기 - 각 8bytes
  • small bin은 각 8bytes의 사이즈를 갖는 청크 binlist를 갖는다. 예) 첫 번째 small bin(Bin 2)은 16bytes 크기의 청크 binlist를 갖고, 두 번째 small bin (Bin 3)은 24bytes 크기의 청크 binlist를 갖는 식으로 이루어진다.
  • small bin 내부 청크 크기는 동일하며 그러한 이유로 정렬이 필요없다.
• 병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 연결 리스트로 결합된다. 병합은 외부 단편화를 제거했지만 해제하는 속도는 느려졌다.
• Malloc(small chunk) -
  • 초기의 small bin은 NULL이다.이러한 이유로 사용자가 small chunk를 요청하더라도 small bin code 대신에 unsorted bin code로 할당될 수 있다.
  • 또한 malloc이 처음 호출될 떄, small bin, large bin의 datastructures(bins)는 malloc_state이 초기화되어 있기 때문에 찾을 수가 있다. bin이 비어있는 자기 자신을 가리키고 있기 때문이다.
  • 이후 small bin이 비어있지 않게되면, 해당하는 binlist의 마지막 청크가 제거되고 사용자에게 반환된다.
• free(small chunk) -
  • 이 청크를 해제하는 동안 이전, 다음 청크가 free되어있는지 확인을 하고 해제가 되있는 경우 병합한다. 각각의 연결된 연결리스트로부터 청크를 해제하고 새로 합병된 청크를 unsorted bin의 연결 리스트에 추가한다.

Large Bin

: 청크의 크기가 512 bytes보다 크거나 같은 경우를 large chunk라고 부른며 large bins은 large chunk에 속하게 된다.

 large bins은 small bins보다 메모리 할당과 해제 면에서 느리다.

 

• bin의 개수 - 63
  • 각 large bin은 free chunks로 이루어진 이중 연결리스트를 갖는다. 청크를 아무 곳에서나 해제 추가 할 수 있기 때문에 이중 연결 리스트를 사용한다.
• 63개의 bins:
  • 32개의 bins은 각 64bytes의 크기를 가지는 청크의 binlist를 갖는다. 예) 첫 번째 large bin(Bin 65)은 512~568bytes 크기의 청크 binlist를 갖고, 두 번째 large bin (Bin 66)은 576~632bytes 크기의 청크 binlist를 갖는 식으로 이루어진다.
  • 16개의 bin은 각 512bytes 크기를 가지는 청크의 binlist를 갖는다.
  • 8개의  bin은 각 4,096bytes 크기를 가지는 청크의 binlist를 갖는다.
  • 4개의  bin은 각 32,768bytes 크기를 가지는 청크의 binlist를 갖는다.
  • 2개의  bin은 각 262,144bytes 크기를 가지는 청크의 binlist를 갖는다.
  • 1개의  bin은 각 남은크기를 가지는 청크의 binlist를 갖는다.
  • small bin과 달리, large bin 내부의 청크는 동일한 크기를 갖지 않는다. 따라서 내림차순으로 저장된다. 가장 큰 청크는 가장 앞에 저장되고, 가장 작은 청크는 가장 뒷쪽에 저장된다.
• 병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 연결 리스트로 결합된다.
• Malloc(large chunk) - 
  • 초기의 large bins은 NULL이다.이러한 이유로 사용자가 large chunk를 요청하더라도 large bin code 대신에 next largest bin code로 할당될 수 있다.
  • 또한 malloc이 처음 호출될 떄, small bin, large bin의 datastructures(bins)는 malloc_state이 초기화되어 있기 때문에 찾을 수가 있다. bin이 비어있는 자기 자신을 가리키고 있기 때문이다.
  • 이후에 large bin이 비어있지 않게 되면, largest chunk의 크기가 사용자가 요청한 크기보다 크면, binlist를 맨 뒤부터 앞까지 확인하여, 사용자가 요청한 크기와 비슷하거나 같은 크기의 청크를 찾는다. 찾게되면, 청크는 두개의 청크로 나뉜다.
    • User chunk(사용자가 요청한 크기) - 사용자에게 반환
    • Remainder chunk(나머지 크기) - unsorted bin에 추가
  • 만약 largest chunk(이 binlist에서) 크기가 사용자가 요청한 크기보다 작다면, 비어있지 않은 다음 largest bin을 사용하여 사용자의 요청에 응답한다. 다음 largest bin code가 비어있지 않은 경우 다음 largest bin을 찾기 위해서 binmaps을 스캔한다. 만약 적절한 bin을 찾은 경우, 적절한 청크를 분리하여 사용자에게 반환된다. 만약 찾지 못한 경우에는 top chunk를 사용해서 사용자의 요청에 응답한다.
  • free(large chunk) - small chunk와 free 과정이 비슷하다.

Top Chunk

: Arena의 가장 꼭대기의 경계에 있는 chunk를 top chunk라고 한다. TOp chunk는 어떤 bin에도 속하지 않는다.

 Top chunk는 어떤 bins들 중에 해제된 블록이 하나도 없는 경우, 사용자의 요청에 응답하기 위해 사용된다.

 만약 top chunk의 크기가 사용자가 요구한 크기보다 큰 경우 top chunk는                                                         두개(User chunk, Remainder chunk)로 분리된다.

 이 경우 remainder chunk는 새로운 꼭대기가 된다. 만약 top chunk의 크기가 사용자가 요청한 경우보다 작은 경우,

 sbrk(main arena) 또는 mmap(thread arena) syscall을 사용하여 top chunk를 확장시킨다.

 

 

 

---

끝

힙 너무 어려운 것 같다.

살려주세요.

 

https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/

Understanding glibc malloc

https://tribal1012.tistory.com/78