Malloc - glibc(ptmalloc2)

다양한 memory allocator

heap exploit을 구현하기 위해서는 메모리 관리를 위해 사용되는 Allocator에 대한 이해가 필요하다.

• dllmalloc - 일반적인 목적의 할당자
• ptmalloc2 - glibc
• jemalloc - FreeBSD와 Firefox
• tcmalloc - Google(Chrome)
• libumem - Solaris

ptmalloc2

• ptmalloc2는 리눅스 GLIBC에서 사용하는 메모리 할당자이다.
• 운영체제마다 메모리 할당자가 동작하는 방식은 각각 다르며, ptmalloc2는 리눅스 유저 모드에서 주로 사용하는 할당자이다.
• ptmalloc2는 glibc 2.23 버전과 glibc 2.26 ( Tcache )이후 버전 동작 방식이 조금 달라졌다.
• ptmalloc2는 dlmalloc 코드를 기반으로 하며 멀티 스레드에서 사용되도록 확장되었다.
• ptmalloc2는 사용하면 한 번에 두 개 이상의 메모리 영역을 활성화하여 멀티 스레드 어플리케이션을 효율적으로 처리 할 수 있다.
• 복수의 스레드가 동시에 malloc을 호출하면 각 스레드는 별도의 힙 세그먼트가 생성되고, 해당 힙을 유지 보수하는 데이터 구조도 분리되어 메모리에 할당된다.
• 따라서 서로 다른 스레드가 서로 간섭하지 않고 서로 다른 메모리 영역에 접근 할 수 있다.
• 이렇게 각각의 스레드의 유지를 위해 분배된 힙과 freelist data structures의 행동을 per thread arena라고 부른다.

Chunk

Malloc에 메모리 할당을 요청하면 넓은 메모리의 영역(“Heap”)을 다양한 크기의 덩어리(“Chunk”)로 나눈다.

• Chunk에는 Allocate Chunk, Free Chunk, Top Chunk, Last Remainder Chunk가 있다.
  • Allocate Chunk : malloc이나 calloc 함수 등 동적 메모리 할당 함수를 통해 할당된 청크를 말한다.
  • Free Chunk : free 함수 등 동적 메모리 해제 함수를 통해 해제된 청크를 말한다.
  • Top Chunk : 힙 메모리의 마지막에 위치해있는 청크를 말한다. Top Chunk의 마지막은 힙 메모리 영역의 끝이다. 메모리 할당 요청이 들어왔을 때, 사용할 적절한 Free Chunk가 없으면 Top Chunk를 쪼개어 사용한다.
  • Last Remainder Chunk : 작은 사이즈의 할당 요청이 들어왔을 때, Free Chunk가 쪼개지고 남은 청크를 말한다. Last Remainder Chunk는 연속된 작은 사이즈의 할당 요청이 들어왔을 때 비슷한 주소에 힙 청크가 할당되는 할당의 지역성을 유지시키기 위해 사용된다.
    • Allocator는 메모리를 할당할 때 Free chunks 중에서 사용가능한 chunk가 있는지 확인한다. 만약 요청한 크기와 일치하는 Chunk가 없고, 요청된 크기 보다 큰 Chunk가 있다면 해당 Chunk를 분할한다. 이때 분할되고 남은 Chunk가 “Last Remainder Chunk”이다.
• 각 청크에는 크기와 인접한 청크의 위치에 대한 메타 데이터를 가지고 있다.
  • 메타 데이터를 이용하여 해당 chunk가 사용중인지 또는 해제되었는지를 알 수 있다.
  • 그리고 이전 청크가 사용중인지 해제되었는지도 알 수 있다.

struct of malloc_chunk

• free 요청이 발생해 메모리 관리자가 메모리 해제를 수행하려면, 원래 할당했던 메모리의 크기를 정확하게 알고 있어야 한다.
• 메모리 관리자가 그러한 정보를 기억하는 일반적인 방식은 메모리를 할당할 때 할당된 메모리 블록 첫 부분에 그 블록의 크기를 써 두고, 할당 요청 코드에게는 그 크기를 쓴 부분 이후의 메모리 주소를 반환한다.
• 따라서 메모리를 요청할때 32bit인 경우, 헤더(8byte) + 요청한크기(8배수 align), 64bit인 경우, 헤더(16byte) + 요청한크기(16배수 align)이 할당된다.
• 이때 헤더는 prev_size, size로 되어있으며 prev_size는 메모리가 할당 되었을때 데이터 영역으로 사용되므로, align된 요청한 크기 + prev_size 크기 만큼 데이터를 저장할 수 있다.
• ex) malloc(32)를 한 경우 (32=0x20) 32는 16배수 이므로 헤더(16byte) + 요청한크기(32byte) = 48byte(0x30)이 할당된다. 여기서 헤더의 16byte중 prev_size의 8byte가 추가로 데이터 영역에 포함되므로 데이터 영역은 40byte가 된다. 즉, malloc(40)까지는 요청했을 경우 48byte(0x30)가 할당된다. 만약 malloc(41)을 했을 경우 48byte(0x30)을 초과하여 다시 16배수로 align을 해줘야 한다. 그러므로 헤더(16byte) + 요청한크기(41byte -> 48byte(가장 가까운 16배수) = 64byte(0x40)이 할당된다.
• malloc(32) ~ malloc(40) = 48byte(0x30)[chunk_size]이 할당된다.
• malloc(41) ~ malloc(48) ~ malloc(56) = 64byte(0x40)[chunk_size]이 할당된다.
• malloc(57) ~ malloc(64) ~ malloc(72) = 80byte(0x80)[chunk_size]이 할당된다.

malloc()은 각 Chunk를 관리하기 위해 malloc_chunk 구조체인 mchunkptr를 선언한다.

• malloc_chunk 구조체는 앞에서 설명한 메타데이터 이다.

구조체 malloc_chunk은 6개의 정보를 관리한다.

• prev_size : 이전 힙 청크가 해제되었을 경우 해제된 힙 청크의 크기를 저장한다. 해제되기 전까지는 이전 힙 청크의 데이터 영역으로 사용된다.
• size : 할당된 현재 힙 청크의 크기를 저장하고있으며, 3개의 비트 플래그가 존재한다.
  • Flags (3bit)
    • PREV_INUSE P : 해당 비트는 이전 힙 청크가 해제된 경우 설정 된다. 1은 이전 청크가 해제되지 않았을 경우이고, 0은 이전 청크가 해제되었을 때 나타내는 값이다.
    • IS_MMAPPED M : 해당 비트는 현재 청크가 mmap 시스템 콜을 사용하여 할당된 경우 설정된다.
    • NON_MAIN_ARENA N : 해당 비트는 현재 청크가 main_arena에서 관리하지 않을 경우에 설정된다.

Free chunk는 크기와 히스토리에 따라 다양한 목록에 저장되며, 이러한 목록들을 “bins”라고 한다.

• fd(Forward pointer) : fd 포인터가 위치한 주소가 실제로 데이터 영역의 시작 부분이며, 할당되었을 때에는 사용하지 않는다. 힙 청크가 해제되었을 때 동일한 bin에 존재하는 다음 Free 청크의 포인터를 가진다.
• bk(Backward pointer) : 동일한 bin에 존재하는 이전 Free 청크의 포인터를 가진다.
• fd_nextsize : large bin에서 사용하는 포인터로, 현재 힙 청크의 크기보다 작은 힙 청크의 주소를 가진다.
• bk_nextsize : large bin에서 사용하는 포인터로, 현재 힙 청크의 크기보다 큰 힙 청크의 주소를 가진다.

모든 청크의 크기는 MALLOC_ALIGNMENT(2 * sizeof(size_t))의 배수이다.

• 32bit의 경우 size_t의 크기가 4byte이기 때문에 chunk의 크기는 8의 배수가 된다.
• 64bit의 경우 size_t의 크기는 8byte이기 때문에 chunk의 크기는 16의 배수가 된다.
• 따라서 청크의 mchunk_size에서 3 LSB(least significant bit)를 플래그로 사용될 수 있다.

Allocate Chunk

Allocate Chunk는 할당자로 부터 메모리를 할당을 받아서 사용중인 메모리 덩어리 이다.

• 이전의 Chunk가 사용가능 할 때, 이전의 Chunk의 크기가 mchunk_prev_size에 저장된다.
• 해당 chunk의 크기가 mchunk_size에 저장되고, 필드의 맨 끝 3bit는 flag 정보를 나타낸다.
• malloc_chunk의 다른 필드(fd,bk)는 할당되어 있는 청크에서는 사용하지 않는다. 따라서 할당되어 있는 청크는 사용자 데이터가 저장되어 있다.
• 사용자가 요청한 크기는 malloc_chunk를 저장하고 메모리를 정렬하기 위해서는 약간의 공간이 여분으로 필요하기 때문에 사용할 수 있는 크기(청크 내부를 나타내는 크기)로 변환된다.

example

malloc()이 호출되기 전이다.

• 시스템은 Heap 공간이 필요한 경우에만 프로세스에 해당 공간을 맵핑한다.
• 기본적으로 맵핑되어 있지 않다.

malloc()이 호출된 후에 이 프로세스에 Heap 공간이 매핑되었다.

할당자로 부터 할당받은 첫번째 Heap의 포인터는 0x602010이다.

• 145(0x91)가 size(0x602008)에 저장되어 있다.
  • 할당자에 의해 할당되는 청크의 크기는 MALLOC_ALIGNMENT의 배수가 된다.
  • 이 시스템은 64bit이며, size_t의 크기가 8byte이기 때문에 할당되는 청크의 크기는 모두 16의 배수가 되어야한다.
  • 136(0x88)은 16의 배수가 아니며, 해당 수와 가장 가까운 16의 배수는 144이다.
  • 할당자는 이 크기로 청크를 할당한다.
• 그리고 해당 값에 PREV_INUSE P 플래그를 더한 값이 145(0x91)이다.
  • 해당 chunk가 프로세스에 매핑된 heap 공간의 최상위에 존재하기 때문에 해당 chunk 앞에 새로운 chunk를 할당할 수 없다.
  • 그래서 해당 청크에 PREV_INUSE P 플래그가 설정된다.
• 할당이 가능한 메모리의 크기가 (0x602098)에 저장된다. (Top Chunk 크기)

할당자로부터 할당받은 두번째 Heap의 포인터는 0x6020a0이다.

• 해당 청크의 크기는 97(0x61)이다.
• 애플리케이션이 요청한 크기는 80(0x50)이다. (16배수)
• 하지만 할당자는 청크를 관리하기 위해 필요한 헤더(prev_size,size)를 저장하기 위해 요청된 크기에 16을 더해서 메모리를 할당한다.
• 그리고 해당 청크 앞에 사용중인 청크가 있기 때문에 그 값에 PREV_INUSE P 플래그가 더해진다.

프로세스는 free()함수를 이용하여 첫번째 청크(0x602010)를 해제한다.

• 이로 인해 0x602010 ~ 0x602018 메모리에 fd, bk 값이 저장된다.
• 그리고 두번째 chunk의 prev_size에 해제된 chunk의 크기(0x90)가 저장되고, size에는 PREV_INUSE P 플래그 값이 빠진 값이 저장된다.

할당자로부터 할당받은 세번째 Heap의 포인터는 0x602010이다.

• 이 포인터는 처음 할당 된 포인터와 동일하다.
• malloc()은 메모리 효율성을 위해 free chunk를 관리한다.
  • 할당자는 메모리의 할당을 요청받으면 free chunk를 먼저 사용한다.
• 다시 할당받은 chunk는 이전에 저장된 데이터가 초기화 되지 않고 그대로 존재한다.
• 변경되는 값은 두번째 chunk의 size값이며, 0x60에서 0x61로 변경된다.
  • 두번째 chunk의 앞에 chunk가 할당되어 사용중이기 때문에 PREV_INUSE P 플래그 값이 추가되었다.

새로 할당받은 heap 메모리는 정상적으로 사용가능하다.

• 값을 입력하게 되면 이전에 저장되어 있던 값을 덮어쓰게 된다.

Free Chunk

Free chunk는 할당자에게 반환된 chunk 이다.

• Chunk의 크기에 따라 fd, bk, fd_nextsize, bk_nextsize의 값이 해당 chunk내에 저장된다.
  • Chunk의 크기가 최소의 크기 일 경우 fd_nextsize, bk_nextsize의 값을 저장할 수 없다.
  • 이 경우 Free chunk의 크기가 커지지 않는다.
    • 해당 chunk는 prev_size, size, fd, bk 값만을 메모리에 저장한다.
    • fd_nextsize, bk_nextsize는 오직 large bin에서만 사용된다.

example

할당자가 할당한 메모리는 다음과 같다.

• chunk의 크기가 128바이트인 메모리가 3개(0x602010, 0x6020c0, 0x602170) 할당되었다. (0x90)
• chunk의 크기가 8바이트인 메모리가 3개(0x6020a0, 0x602150, 0x602200) 할당되었다. (0x20)

heap1(0x602010)이 해제되면 해당 chunk에 bk,fd 값이 저장된다.

• 이전 청크의 크기(0x90)는 tmp2(0x6020a0)의 “prev_size”에 저장되며, “size”에는 PREV_INUSE [P] (0x1) 플래그의 값을 뺀 값(0x20)이 저장된다.

heap2(0x6020c0)가 해제되면 해당 chunk에 fd, bk값이 저장된다.

• fd(0x6020c0)에 저장되는 값은 해당 chunk 앞에 있는 Free chunk의 mchunkptr(0x602000)이다.
• 그리고 heap1의 bk(0x602018)에 heap2의 mchunkptr(0x6020b0)이 저장된다.

heap3(0x602170)가 해제되면 fd(0x602170)에 해당 chunk 앞에 있는 Free chunk의 mchunkptr(0x6020b0)이 저장된다.

• 그리고 heap2의 bk(0x6020c8)에 heap3의 mchunkptr(0x602160)이 저장된다.

Bin

해제된 힙 청크(Free Chunk)는 bin이라는 freelist 구조체를 통해 관리된다.

• freelist란 동적으로 메모리를 할당하고 해제할 때 메모리 관리의 효율을 높이기 위해 할당되지 않은 영역을 관리하는 연결 리스트이다.

• 영역을 해제할 때 해제하려는 영역을 freelist에 추가하고, 할당 요청이 들어왔을 때 freelist에 추가된 영역을 제거하고 해당 영역을 사용힌다.

• bins의 종류에는 Fast bin, Small bin, Large bin, Unsorted bin이 있다.

• fastbinsY - 이 배열은 fast bin을 수용한다.

• bins - 이 배열은 unsorted, small, large bin을 수용한다. 총 126개의 bin이 있다.

  • Bin 1 - Unsorted bin (1개)
  • Bin 2 ~ Bin 63 - Small bin (62개)
  • Bin 64 ~ Bin 126 - Large bin (63개)

fast bin

M_MXFAST(1)라는 매개변수를 사용해서 “fastbin”에 포함되는 청크의 범위를 설정한다.

• “fastbin”에 포함되는 chunk 크기의 범위는 0에서 80*sizeof(size_t)/4까지 이다.
• “fastbin”의 기본 범위는 0에서 64*sizeof(size_t)/4 이다. (mallopt() 함수로 확장 가능)
• 32비트 아키텍처에서 패스트빈의 상한은 64byte(644/4)이며, 64비트 아키텍처에서는 128byte(648/4)이다.
  • 해당 크기보다 작은 chunk들이 fastbin에 배치된다.
• 해당 크기는 매개변수 “value”를 이용하여 변경할 수 있다.
  • 매개변수를 최대로 설정하면 32비트 아키텍처에서는 최대 80byte(804/4), 64bit에서는 최대 160byte(808/4)의 상한을 설정 할 수 있다.
  • fast bin을 비활성화하려면 0으로 설정하면 된다.
• Fastbin은 LIFO(last in, first out)를 사용한다.
  • 마지막으로 해제 된 chunk가 먼저 재 할당된다.
• 해당 bin은 최대 10개의 bin 관리 할 수 있으며, 패스트빈의 상한 값보다 크기가 작은 chunk들을 관리한다.
  • 64bit 아키텍처의 경우 Fastbin에 포함되는 chunk의 크기는 32, 48, 64, 80, 96, 112, 128 이다.
  • 32bit 아키텍처의 경우 Fastbin에 포함되는 chunk의 크기는 16, 24, 32, 40, 48, 56, 64 이다.
• 해당 bin은 single-linked list로 구성된다.
  • 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 fd에 새로 해제된 chunk의 mchunkptr을 저장된다.
  • bk는 사용하지 않는다.
• 해당 bin에 포함되는 chunk들은 서로 인접해 있어도 병합하지 않는다.

example

마지막 free()를 호출한 다음의 코드에 Breakpoint를 설정하고 프로그램을 실행한다.

• main_arena의 정보는 gdb에 “p main_arena” 명령어를 입력하면 확인할 수 있다.
• 해제된 chunk들 중 fastbin에 포함되는 chunk들은 fastbinsY에 배치되어 있다.
• 배치된 chunk들의 크기는 0x20(32) ~ 0x80(128)이다.
• malloc(16) ~ malloc(112) -> 0x20(32) ~ 0x80(128)

fastbin에서 동일한 chunk들의 관리

해제된 chunk들 중 가장 나중에 free된 chunk가 fastbinsY에 배치된다.

• 이 chunk의 fd에는 두번째 free chunk의 mchunkptr이 저장되어 있다.
• 그리고 두번째 chunk의 fd에는 세번째 chunk의 mchunkptr이 저장되어 있다. (뒤로 갈수록 가장 먼저 free된 chunk)
• bk에는 어떠한 값도 배치되지 않는다.
• single-linked list 형태로 fastbin들이 연결된다.

malloc()에 크기가 16byte인 메모리의 할당을 요청하면, Allocater는 해당 크기과 동일한 free chunk가 있는지 fastbinsY에서 확인한다.

• 할당자는 fastbinsY에 동일한 크기의 chunk가 있다면 해당 chunk를 재할당한다.
• fastbinsY에는 두번째 free chunk가 배치되었고, 첫번째(가장 최근에 free된) free chunk가 반환되었다.
• 반환된 chunk에 값이 정상적으로 써진다.

small bin

• Small bin이 포함하는 chunk는 크기가 MIN_LARGE_SIZE 보다 작은 chunk들이다.
  • 32bit 시스템은 MALLOC_ALIGNMENT는 8이고, SIZE_SZ는 4이다.
    • MIN_LARGE_SIZE는 512((64 - 0) * 8)이다.
  • 64bit 시스템은 MALLOC_ALIGNMENT는 16이고,SIZE_SZ는 8이다.
    • MIN_LARGE_SIZE는 1024((64 * 0) * 16)이다.
  • 즉, 32bit 시스템에서 Small bin의 범위는 16504byte(64*8-8)이며 64bit에서는 321008byte이다.
• 해당 bin은 62개의 bin들을 관리하며, doubly-linked list로 구성된다.
  • 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 bk에 새로 해제된(나중에 해제된) chunk의 mchunkptr가 저장된다.
  • 새로 해제된 chunk의 fd에 마지막으로 해제된(먼저 해제된) 같은 크기의 chunk의 mchunkptr가 저장된다.
• Small bin은 FIFO(First In, First Out)을 사용한다.
  • 먼저 해제 된 청크가 먼저 재 할당된다.
• Small bin에 해당되는 chunk들은 서로 인접하게 배치될수 없다.
  • 해당 chunk가 서로 인접해 있을 경우 하나의 chunk로 병합된다.
• Small bin은 각 16바이트 크기를 가지는 청크 binlist를 가진다.
  • ex) 첫 번째 Small bin(Bin 2)은 32바이트 크기의 청크 binlist를 가지며, 두 번째 small bin(Bin 3)은 48바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.

bin의 인덱스는 smallbin_index() 함수를 이용하여 확인 할 수 있다.

• 이함수는 SMALLBIN_WIDTH을 사용해서 해당 시스템이 32bit인지 64bit인지 확인한다.
  • 64bit의 경우 chunk 크기를 16으로, 32bit의 경우 chunk의 크기를 8로 나눈다음, 그 값에 SMALLBIN_CORRECTION를 더 한다.
  • 이 값이 해당 chunk에 대한 bin 인덱스 이다.
• 예를 들어 64bit에서 144byte의 free chunk의 bin의 인덱스는 9(144 >> 4 + 0)이다. bin 9
• free chunk의 인덱스는 ((144 >> 4 + 0) - 1) * 2 = 16(fd),17(bk) 이다.

example

사이즈가 128byte인 메모리 3개와 200byte 1개와 160byte 2개, 그리고 해당 메모리 사이에 16byte 메모리 할당을 요청한다.

• “small*”변수들이 가리키는 메모리들 사이에 16byte의 메모리 할당을 요청하지 않으면 Small bin에 해당하는 chunk들이 연속으로 배치되기 때문에 서로 병합된다.
• “small*”변수들이 가리키는 메모리들을 모두 해제한 후 200byte, 128byte의 메모리 할당을 요청한다.

• free chunk들은 먼저 Unsorted bin에 배치되기 때문에 마지막에 해제된 chunk는 Unsorted bin에서 찾을 수 있다.
  • 해당 어플리케이션에서 마지막에 해제된 chunk는 0x602300이며, 크기는 176byte이다.
  • free()를 이용하여 해제할 메모리는 0x6023c0이며, 이 메모리는 마지막에 해제된 chunk과 인접해 있다.

• free()가 실행되면 두 chunk는 병합되어 하나의 chunk가 된다.
  • 해당 chunk(0x602300)의 크기가 352byte가 되었다.

• 크기가 144 (128 + 16) 바이트 인 청크의 인덱스는 16과 17이다.
• Unsorted bin에 있던 chunk가 재할당되면 list의 연결이 끊기기 때문에, Allocator는 연결이 끊긴 chunk들을 bins에 배치한다.
  • 크기가 128byte인 free chunk가 3개 있다.
  • 이 중에서 bins16에는 마지막에 해제된 chunk가, bins17에는 먼저 해제된 chunk가 배치된다.
• 할당자는 해당 chunk 앞,뒤에 있는 chunk의 mchunkptr를 fd와 bk에 배치한다.
  • 첫번째에 있는 chunk와 끝에 있는 chunk는 fd, bk에 “bins”의 주소를 배치한다.
  • 할당자는 free chunk에 배치된 “bins”의 주소를 하나의 chunk로 본다.
  • 그래서 할당자는 bins[idx]의 주소에서 16을 뺀 주소를 사용한다.
  • 이것은 doubly-linked list 형태이다.

어플리케이션이 Small bin에 배치된 chunk와 동일한 크기의 메모리 할당을 요청하면, 할당자는 먼저 해제되었던 chunk(0x6020c0)를 재할당한다.

• 그리고 해당 chunk(0x6020c0) 뒤에 있던 chunk(0x602000)가 bins[17]에 배치된다.

example2

• 크기가 272byte인 chunk의 인덱스는 (272/16 -1) * 2 = 32(fd), 33(bk)이다.
• bins[32],bins[33]은 bins17으로 하나의 주소를 사용한다. (bins[30],bins[31] = bins16으로 하나의 주소 사용)
• 맨처음에 해제된 chunk의 mchunkptr는 bins[33]에 배치된다.
• 맨마지막에 해제된 chunk의 mchunkptr는 bins[32]에 배치된다.

large bin

• Large bin이 포함하는 chunk의 크기가 MIN_LARGE_SIZE와 같거나 큰 chunk들이다.
  • 64bit 아키텍처의 경우 free chunk의 크기가 1024와 같거나 크면 해당 chunk는 Larger bin에 배치된다.
• Large bin이 포함하는 chunk들은 서로 인접해 있을 경우 하나의 chunk로 병합된다.
• Large bin은 63개의 bin을 사용하며, small bin과 같이 doubly-linked list로 구성된다.
  • 그러나 Large bin은 Small Bin과 다르게 하나의 bin에 다양한 크기의 chunk들을 보관한다.
  • 해당 bin들은 bin내에서 크기 별로 정렬되어 할당의 효율성을 높인다.

(32bit)

• 32개의 bin은 각 64바이트 크기를 가지는 청크의 binlist를 가진다.

  • ie) 첫 번째 large bin(Bin 65)은 512바이트 ~ 568바이트 크기의 청크 binlist를 가지고,
  • 두 번째 large bin(Bin 66)은 576바이트 ~ 632바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.

• 16개의 bin은 각 512바이트 크기를 가지는 청크의 binlist를 가진다.

• 8개의 bin은 각 4,096바이트 크기를 가지는 청크의 binlist를 가진다.

• 4개의 bin은 각 32,768바이트 크기를 가지는 청크의 binlist를 가진다.

• 2개의 bin은 각 262,144바이트 크기를 가지는 청크의 binlist를 가진다.

• 1개의 bin은 남은 크기를 가지는 청크를 가진다.

• small bin과 달리, large bin 내부의 청크는 동일한 크기를 가지고 있지 않다. 따라서, 내림차순으로 저장된다.

  • 가장 큰 청크는 binlist의 가장 앞쪽에 저장되고, 가장 작은 청크는 binlist의 가장 뒷쪽에 저장된다.
  • fd로 갈 수록 크기가 작고, bk로 갈 수록 크기가 크다.

• fd_nextsize(나보다 작은 크기)와 bk_nextsize(나보다 큰 크기)를 사용하여 크기 순으로 정렬, 동일한 크기의 chunk 끼리는 연결되지 않는다.

Large bin에 해당하는 chunk들의 인덱스는 largebin_index_32(), largebin_index_64() 함수를 이용하여 확인할 수 있다.

• free chunk의 크기를 쉬프트 연산을 이용하여 나누고, 그 값이 조건에 만족하는 값이라면 기본 인덱스 값을 더한 값이 해당 chunk의 인덱스 값이 된다.
• ex)64bit 아키텍처에서 chunk의 크기가 3072 ~ 3120인 chunk들은 bin[96]에 보관된다. 48 + (3072 >> 6) = 96

example

1024, 1040, 1056 byte인 메모리 3개, 200byte 1개, 1120byte 2개, 그리고 해당 메모리 사이에 16byte 메모리 할당을 요청한다.

• “large*” 변수가 가리키는 메모리들 사이에 16byte의 메모리 할당을 요청하지 않으면 Large bin에 해당하는 chunk들이 연속으로 배치되기 때문에 서로 병합된다.
• “large*” 변수가 가리키는 메모리들을 모두 해제한 후 200byte, 1040byte의 메모리 할당을 요청한다.

• 마지막으로 해제된 chunk는 0x602db0이며, 크기는 1136byte이다.
  • free()를 이용하여 해제할 메모리는 0x603230이며, 이 메모리는 마지막에 해제된 chunk과 인접해 있다.

• free()가 실행되면 두 chunk는 병합되어 하나의 chunk가 된다
  • 해당 chunk(0x602db0)의 크기가 2272byte가 되었다.

크기가 1040(1024 + 16)byte 인 chunk의 인덱스는 126 및 127이다.

• Large bin은 Small bin과 동일하게 doubly-linked list 로 chunk들을 연결한다.

할당자는 Large bin에 해당하는 chunk가 “bins”에 배치될때 해당 인덱스에 해당하는 chunk들을 크기 별로 정렬한다.

• Chunk가 Unsorted bin에 있을 때는 해제된 순서대로 연결되어 있다.
  • 0x602870 (size : 0x430) <–> 0x602000 (size : 0x410) <–> 0x602430 (size : 0x420)
• 하지만 Chunk가 “bins”에 배치되면 chunk의 크기순으로 정렬된다.
  • 0x602870 (size : 0x430) <–> 0x602430 (size : 0x420) <–> 0x602000 (size : 0x410)

Large bin에 배치된 chunk와 동일한 크기의 메모리 할당을 요청하면, 할당자는 요청한 크기와 동일한 chunk(0x602440)를 재할당한다.

unsorted bin

• 청크를 분할한 후에 남은 chunk와 반환된 모든 청크는 Unsorted bin에 먼저 배치된다.
  • 해당 bin은 Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 청크가 해당 Bin에 저장될 수 있다.
  • 그러나 Fast bin에 해당하는 chunk는 Unsorted bin에 배치 되지 않는다.
  • 할당자는 Unsorted bin에 요청받은 메모리의 크기와 같은 chunk가 있다면 해당 chunk를 재할당한다.
• Unsorted Bin은 1개의 bin만 사용하며, doubly-linked list와 FIFO를 사용한다.
  • 해당 bin을 이용해 적절한 bin을 찾는 시간이 덜 걸리므로 할당과 해제의 처리가 빠르다.
• Allocator에 의해 검색된 Chunk는 바로 재할당 되거나 아니면 원래의 Bin에 배치된다.
  • unsorted bin의 모든 chunk는 재할당을 위한 1번의 기회가 주어진다.
  • 재할당에 실패한 경우, 크기에 따라 small bin이나 large bin에 재배치된다.

fastbinsY & bins

Arena

• ptmalloc2는 각 스레드가 서로 간섭하지 않고, 서로 다른 메모리 영역에 액세스 할 수 있게 한다.
  • 이러한 메모리 영역을 “Arena”라고한다.
  • Main을 포함한 모든 각 Threads에 대한 힙 영역이라고 할 수 있다.
  • 모든 Threads가 각자의 Arena를 가지진 못 하고 32bit와 64bit System과 시스템의 Core 갯수에 따라 Arena의 갯수에 제한이 있다.
  • 제한을 넘어 Arena가 필요한 경우는 기존에 사용하던 Arena를 재사용한다.
• 응용 프로그램에는 “main arena”이라는 arena가 있다.
  • malloc()에는 이 arena를 가리키는 정적 변수가 있으며 각 arena에는 추가 arena를 연결하는 다음 포인터가 있다.
• 각 Arena는 하나 이상의 힙 메모리를 얻는다.
  • main arena는 프로그램의 초기 힙을 사용한다 (.bss 등 직후 시작)
  • main arena는 힙 공간이 부족하면 확장하여 사용하기 때문에 추가로 힙을 할당 할 필요가 없다.
  • 추가 Arena는 mmap를 통해 힙에 메모리를 할당하고, 이전 힙이 소모되면 더 많은 힙을 힙목록에 추가한다.
• Arena는 heap 메모리에서 할당된 chunk들을 관리한다.
  • Arena에서 관리되는 chunk들은 응용 프로그램에서 사용 중이거나 사용이 가능한 chunk들 이다.
  • 사용중인 청크는 Arena에서 추적되지 않는다.
  • Free chunk는 크기와 히스토리에 따라 분류되어 arena에 저장된다.
  • 할당자는 arena에서 할당 요청을 충족하는 chunk를 신속하게 찾을 수 있다.
• Arena의 개수는 현재 시스템의 core의 수에 기반된다.
  • For 32 bit systems: Number of arena = 2 * number of cores.
  • For 64 bit systems: Number of arena = 8 * number of cores.

malloc.c 코드내에 “main_arena”라는 변수가 존재한다.

• 이 변수가 앞에서 언급한 main arena이다.
• 해당 변수는 “struct malloc_state” 구조체를 사용한다.

구조체 정리

struct malloc_info (Heap_Header)

• Arena는 각 Threads에 대한 힙 영역이기 때문에 힙 영역의 공간이 부족하면 새로운 영역에 추가로 할당받아 여러 개의 힙 영역을 가질 수 있다(Main Thread 제외).
• 이런 힙 영역은 어떤 Arena가 관리하고 있는지, 힙 영역의 크기가 어느정도인지, 이전에 사용하던 heap 영역의 정보가 어디에 있는지를 저장할 필요가 있다.
• 이런 정보를 저장하기 위한 구조체가 malloc_info 구조체이며, 힙에 대한 정보를 저장하기 때문에 Heap_Header라고도 할 수 있다(Main Thread는 확장을 해서 쓰기 때문에 제외)

struct malloc_state (Arena Header)

• 위의 Heap_Header에서는 단순히 힙 영역에 대한 정보만을 저장하였기 때문에, 힙 영역에서도 어떤 부분을 사용하면 되는지에 대해 Arena는 이를 관리하기 때문에 알고 있을 필요가 있다.
• malloc_state 구조체는 각 Arena에 하나씩 주어지고, 해제된 Chunk를 관리하는 연결리스트 bin과 최상위 Chunk인 top chunk와 같은 Arena에 대한 정보를 저장한다.
• 단일 스레드 arena는 여러 개의 힙을 가질 수 있지만, 이러한 모든 힙에 대해서는 오직 하나의 arena header만이 존재한다.
• “malloc_state”의 구조는 다음과 같다.
• mutex는 해당 arena에 대한 액세스를 제어하는 데 사용된다.
  • mutex를 이용하여 여러 스레드간에 arena 사용 충돌이 발생하것을 방지한다.
  • 패스트 빈에 대한 액세스와 같은 일부 작업은 arena를 잠글 필요가 없다.
  • 이 외에 다른 모든 작업을 하려면 스레드가 arena를 잠글 필요가 있다.

main_arena의 flags는 2개의 bit로 정보들의 유무를 나타낸다.

• 첫번째bit는 해당 Arena가 fastbin(fastchunk)를 가지고 있는지 나타낸다.
  • fastbin(fastchunk)이 arena에 있다면 첫번째 bit의 값은 0이, 없다면 1이 보관 된다.
• 두번째bit는 해당 Arena가 인접한지를 나타낸다.
  • 해당 arena가 인접한 arena라면 1이, 아니라면 0이 표시된다.
  • Non-main arena는 하위 힙으로 구성되며 항상 NONCONTIGUOUS_BIT가 설정된다.

fastbins에 fastbin에 해당하는 free chunk가 배치된다.

• fastbin에 해당하는 chunk의 인덱스는 fastbin_index()함수를 이용하여 확인할 수 있다.
• 해당 함수는 우측 시프트를 이용하여 chunk의 크기(sz)를 8(32bit) 또는 16(64bit)으로 나눈 값에 2를 뺀다.
• ex)64bit 아키텍처에서 크기가 32byte인 chunk의 인덱스는 0((32 >> 4) - 2)이다.

top에는 Top chunk가 배치된다.

• Top chunk는 Arena의 가장 상위 영역에 있는 Chunk이며, bin에 포함되지 않는다.
• Top chunk는 PREV_INUSE 플래그가 설정된다.
• Top chunk는 요청한 힙을 할당할 수 있는 충분한 청크가 bin에 없는 경우에 사용된다.
• Top chunk의 크기가 사용자가 요청한 크기보다 큰 경우 top chunk는 2개로 분리된다.
  • (사용자가 요청한 크기의 청크와 분할되고 남은 크기의 나머지 청크(Remainder chunk))
• Remainder chunk는 새로운 Top chunk가 된다.
• 할당자는 Top chunk의 크기가 사용자가 요청한 크기보다 작은 경우 조건에 따라 Top chunk의 크기를 증가시키거나, 새로운 Heap영역을 할당한다.
  • 할당자는 요청받은 chunk의 크기가 DEFAULT_MMAP_THRESHOLD(131072)보다 큰경우 mmap()을 호출하여 새로운 Heap 영역을 매핑한다.

할당자는 메모리를 할당하기에 arena의 공간이 부족할 경우 sbrk()를 호출하여 메모리의 공간을 증가시킨다.

• malloc.c에서는 MORECORE라는 매크로를 이용하여 sbrk() 함수를 호출한다.

last_remainder에는 chunk를 할당 한 후에 남은 chunk가 배치된다.

• 할당자는 요청한 크기와 일치하는 free chunk가 없으면, 요청한 크기보다 큰 free chunk를 요청 크기로 분할하는 경우가 있다.

“bins”에 Unsorted bin, Small bin, Large bin가 포함하는 free chunk가 배치된다.

• 이 변수는 배열 변수이며 총(128 * 2 - 2)254개의 chunk 포인터를 배치할 수 있다.
• free chunk를 bins에 배치할 때 chunk의 fd, bk 정보를 저장하기 때문 배열의 크기가 128이 아닌 254이다.
  • bins[0], bins[1]은 Unsorted bin들이 배치된다.

binmap은 bins를 4(BINMAPSIZE)개의 영역으로 나누어서 정보를 배치한다.

• binmap[0] : 0 ~ 31, binmap[1] : 32 ~ 64, binmap[2] : 65 ~ 96, binmap[3] : 97 ~128
  • bins[]에 free chunk가 배치되면, binmap[]에는 그 bin이 해당하는 위치에 해당 bin의 bit가 배치된다.
• 예를 들어 크기가 256byte인 free chunk의 인덱스는 65이며, binmap[2]에 bit정보가 저장된다.
  • 할당자는 idx2bit() 함수를 이용하여 저장할 bit값을 계산한다.
  • binmap[2]에는 2(1 << (index(65) & 31))가 배치된다.
• binmap[] 배열을 사용하면 많은양의 빈 검색이 간소화된다.

next는 여러 arena가 있는 경우에 추가 arena을 연결하는 포인터다.

struct malloc_chunk (Chunk Header)

• 힙 영역은 사용자에 의해 할당되거나, 해제되거나 하면 Chunk라는 단위로 관리된다.
• malloc_chunk는 현재 chunk의 크기와 바로 인접한 이전 chunk의 크기를 저장하고, 해제된 chunk는 bin에 의해 연결리스트로 관리되기 때문에 이중 연결리스트를 위한 포인터 주소를 저장한다.
• 마지막으로 있는 2개의 chunk 포인터는 large bin을 위해서만 사용된다. large bin은 다른 bin과 다르게 연결리스트에 크기를 대략적으로 관리하기 때문에 연결리스트 내부에서 크기 순으로 추가적인 연결리스트를 가진다.

※

• Main arena는 여러 개의 힙과 heap_info 구조체를 가질 수 없다. main arena의 공간이 부족한 경우, sbrk 힙 영역은 메모리가 매핑된 영역까지 확장(인접한 영역)된다.
• thread arena와 달리, main arena의 arena header는 sbrk 힙 영역의 일부가 아니다. main arena는 전역 변수이며, libc.so의 데이터 영역에서 찾을 수 있다.

Reference

• https://www.lazenca.net/pages/viewpage.action?pageId=1147929
• https://tribal1012.tistory.com/141
• https://tribal1012.tistory.com/78
• https://dreamhack.io/
• http://studyfoss.egloos.com/5206220