Excuse the ads! We need some help to keep our site up.

List

1.Malloc

Memory Allocator

힙 익스플로잇을 구현하기 위해서는 메모리 관리를 위해 사용되는 Allocator에 대한 이해가 필요합니다.
- dlmalloc, ptmalloc2, jemalloc, tcmalloc, libumem, 등 다양한 종류의 메모리 할당자가 있습니다.
이 책에서는 GNU C Library의 메모리 할당자인 ptmalloc2에 대해 설명하겠습니다.
- ptmalloc2는 dlmalloc 코드를 기반으로 하며 멀티 스레드에서 사용되도록 확장되었습니다.
- ptmalloc2는 사용하면 한 번에 두개 이상의 메모리 영역을 활성화하여 멀티 스레드 어플리케이션을 효율적으로 처리 할 수 있습니다.
- 복수의 스레드가 동시에 malloc을 호출하면 각 스레드는 별도의 힙 세그먼트가 생성되고, 해당 힙을 유지 보수하는 데이터 구조도 분리되어 메모리에 할당됩니다.
- 따라서 서로 다른 스레드가 서로 간섭하지 않고 서로 다른 메모리 영역에 접근 할 수 있다.

Chunk

Malloc에 메모리 할당을 요청하면 넓은 메모리의 영역("힙")을 다양한 크기의 덩어리("chunk")로 나눕니다.
- Chunk에는 사용 중인 덩어리, 해제된 덩어리, Top 덩어리, Last Remainder 덩어리가 있습니다.
  - In-use chunk는 애플리케이션에서 할당받아서 사용중인 덩어리입니다.
  - Free chunk는 응용프로그램에서 시스템에 반환한 덩어리입니다.
  - Top chunk는 Arena의 가장 상단에 있는 덩어리입니다.
  - Allocator는 메모리를 할당할 때 Free chunks 중에서 사용가능한 chunk가 있는지 확인합니다.
    - 만약 요청한 크기와 일치하는 chunk가 없고, 요청된 크기 보다 큰 chunk가 있다면 해당 덩어리를 분할합니다.
    - 이때 분할되고 남은 덩어리가 "Last Remainder chunk"입니다.
- size_t가 void*와 같은 크기가 아니라면 청크의 최소 크기는 4*sizeof(void*)입니다.
  - 플랫폼의 ABI에 추가 정렬이 필요한 경우 최소 크기가 더 클 수 있습니다.
각 청크에는 크기와 인접한 청크의 위치에 대한 메타 데이터를 가지고 있습니다.
- 메타 데이터를 이용하여 해당 chunk가 사용중인지 또는 해제되었는지를 알수 있습니다.
- 그리고 이전 청크가 사용중인지 해제되었는지도 알 수 있습니다.

Struct of malloc_chunk

malloc()은 각 chunk를 관리하기 위해 malloc_chunk 구조체인 mchunkptr를 선언합니다.
- malloc_chunk 구조체는 앞에서 설명한 메타데이터 입니다.

/release/2.25/master/malloc/malloc.c

/* Forward declarations.  */
struct malloc_chunk;
typedef struct malloc_chunk* mchunkptr;

구조체 malloc_chunk은 6개의 정보를 관리합니다.
- 이전 Chunk가 Free chunk가 되면, 이전 Chunk의 크기가 "mchunk_prev_size"에저장됩니다.
  - 반대로 이전 Chunk가 In-use chunk가 되면, 이전 Chunk의 사용자 데이터가 배치될수 있습니다.
- In-use chunk의 크기를 "mchunk_size" 에 저장합니다.
  - 그리고 필드의 맨 끝 3bit는 flag 정보를 나타냅니다.
Free chunk는 크기와 히스토리에 따라 다양한 목록에 저장되며,이러한 목록들을 "bins"라고 합니다.
- fd(Forward pointer)는 다음 Free Chunk의 포인터를 가집니다.
- bk(Backward pointer)는 이전 Free Chunk의 포인터를 가집니다.
- fd_nextsize, bk_nextsize는 크기가 큰 chunk의 포인터만 배치되었습니다.
fd,bk, fd_nextsize, bk_nextsize는 chunk가 Free chunk일 경우에만 사용됩니다.

/release/2.25/master/malloc/malloc.c

struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

모든 청크의 크기는 MALLOC_ALIGNMENT(2 * sizeof(size_t))의 배수입니다.
- 32bit의 경우 size_t의 크기가 4byte이기 때문에 chunk의 크기는 8의 배수가 됩니다.
- 따라서 청크의 mchunk_size에서 3 LSB(least significant bit)를 플래그로 사용될 수 있습니다.
mchunk_size 필드의 맨 끝 3bit는 플래그로 사용되며, 다음과 같이 정의됩니다
- PREV_INUSE [P](0x1) 플래그는 인접한 이전 청크가 사용중일 때 사용됩니다.
- IS_MMAPPED [M](0x2) 플래그는 해당 청크를 mmap()으로 부터 할당받았은 청크일 경우 사용됩니다.
- NON_MAIN_ARENA [A](0x4) 플래그는 해당 청크를 비 주요 경기장(non-main arena)으로부터 할당받은 경우 사용됩니다.

/release/2.25/master/malloc/malloc.c

/*
   --------------- Physical chunk operations ---------------
 */


/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1

/* extract inuse bit of previous chunk */
#define prev_inuse(p)       ((p)->size & PREV_INUSE)


/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
#define IS_MMAPPED 0x2

/* check for mmap()'ed chunk */
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)


/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
   from a non-main arena.  This is only set immediately before handing
   the chunk to the user, if necessary.  */
#define NON_MAIN_ARENA 0x4

/* check for chunk from non-main arena */
#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)

In-use chunk

In-use chunk는 할당자로 부터 메모리를 할당을 받아서 사용중인 메모리 덩어리입니다.
- 이전의 Chunk가 사용가능 할 때, 이전의 Chunk의 크기가 mchunk_prev_size에 저장됩니다.
- 해당 chunk의 크기가 mchunk_size에 저장되고, 필드의 맨 끝 3bit는 flag 정보를 나타냅니다.

in-use chunk

다음 코드를 이용하여 어플리케이션의 메모리에서 in-use chunk를 확인하겠습니다.
- malloc()에 크기가 128 byte와 80byte인 메모리 할당을 요청합니다.
- malloc()으로 부터 반환된 포인터를 heap1, heap2에 저장합니다.
- free()에 heap1이 가리키는 메모리의 해제를 요청합니다.
- 그리고 다시 malloc()에 크기가 128byte의 메모리의 할당을 요청합니다.
- 반환된 포인터는 heap3에 저장합니다.
- read()를 이용하여 heap3가 가리키는 메모리에 데이터를 입력합니다.

In-use.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
  
void main(){
    char *heap1 = malloc(136);
    char *heap2 = malloc(80);

    free(heap1);

    char *heap3 = malloc(136);
    read(STDIN_FILENO,heap3,136);
}

다음과 같이 breakpoints를 설정하여 메모리 변경을 확인합니다.

Breakpoints

lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gdb -q ./in-use
Reading symbols from ./in-use...(no debugging symbols found)...done.
(gdb) set disassembly-flavor intel 
(gdb) disassemble main 
Dump of assembler code for function main:
   0x00000000004005b6 <+0>:	push   rbp
   0x00000000004005b7 <+1>:	mov    rbp,rsp
   0x00000000004005ba <+4>:	sub    rsp,0x20
   0x00000000004005be <+8>:	mov    edi,0x88
   0x00000000004005c3 <+13>:	call   0x4004a0 <malloc@plt>
   0x00000000004005c8 <+18>:	mov    QWORD PTR [rbp-0x18],rax
   0x00000000004005cc <+22>:	mov    edi,0x50
   0x00000000004005d1 <+27>:	call   0x4004a0 <malloc@plt>
   0x00000000004005d6 <+32>:	mov    QWORD PTR [rbp-0x10],rax
   0x00000000004005da <+36>:	mov    rax,QWORD PTR [rbp-0x18]
   0x00000000004005de <+40>:	mov    rdi,rax
   0x00000000004005e1 <+43>:	call   0x400470 <free@plt>
   0x00000000004005e6 <+48>:	mov    edi,0x88
   0x00000000004005eb <+53>:	call   0x4004a0 <malloc@plt>
   0x00000000004005f0 <+58>:	mov    QWORD PTR [rbp-0x8],rax
   0x00000000004005f4 <+62>:	mov    rax,QWORD PTR [rbp-0x8]
   0x00000000004005f8 <+66>:	mov    edx,0x88
   0x00000000004005fd <+71>:	mov    rsi,rax
   0x0000000000400600 <+74>:	mov    edi,0x0
   0x0000000000400605 <+79>:	call   0x400480 <read@plt>
   0x000000000040060a <+84>:	nop
   0x000000000040060b <+85>:	leave  
   0x000000000040060c <+86>:	ret    
End of assembler dump.
(gdb) b *0x00000000004005c3
Breakpoint 1 at 0x4005c3
(gdb) b *0x00000000004005d6
Breakpoint 2 at 0x4005d6
(gdb) b *0x00000000004005e6
Breakpoint 3 at 0x4005e6
(gdb) b *0x00000000004005f0
Breakpoint 4 at 0x4005f0
(gdb) b *0x000000000040060a
Breakpoint 5 at 0x40060a
(gdb)

첫번째 Breakpoint에서는 malloc()이 호출되기 전입니다.
- 시스템은 Heap 공간이 필요한 경우에만 프로세스에 해당 공간을 맵핑합니다.
- 기본적으로 맵핑되어 있지 않습니다.
- malloc()이 호출된 후에 이 프로세스에 Heap 공간이 매핑되었습니다.

Before heap space is mapped to a process

(gdb) r
Starting program: /home/lazenca0x0/Book/Heap/1.Malloc/in-use 

Breakpoint 1, 0x00000000004005c3 in main ()
(gdb) x/i $rip
=> 0x4005c3 <main+13>:	call   0x4004a0 <malloc@plt>
(gdb) info proc map
process 7207
Mapped address spaces:

          Start Addr           End Addr       Size     Offset objfile
            0x400000           0x401000     0x1000        0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use
            0x600000           0x601000     0x1000        0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use
            0x601000           0x602000     0x1000     0x1000 /home/lazenca0x0/Book/Heap/1.Malloc/in-use
      0x7ffff7a0d000     0x7ffff7bcd000   0x1c0000        0x0 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7bcd000     0x7ffff7dcd000   0x200000   0x1c0000 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7dcd000     0x7ffff7dd1000     0x4000   0x1c0000 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7dd1000     0x7ffff7dd3000     0x2000   0x1c4000 /lib/x86_64-linux-gnu/libc-2.23.so
      0x7ffff7dd3000     0x7ffff7dd7000     0x4000        0x0 
      0x7ffff7dd7000     0x7ffff7dfd000    0x26000        0x0 /lib/x86_64-linux-gnu/ld-2.23.so
      0x7ffff7fde000     0x7ffff7fe1000     0x3000        0x0 
      0x7ffff7ff7000     0x7ffff7ffa000     0x3000        0x0 [vvar]
      0x7ffff7ffa000     0x7ffff7ffc000     0x2000        0x0 [vdso]
      0x7ffff7ffc000     0x7ffff7ffd000     0x1000    0x25000 /lib/x86_64-linux-gnu/ld-2.23.so
      0x7ffff7ffd000     0x7ffff7ffe000     0x1000    0x26000 /lib/x86_64-linux-gnu/ld-2.23.so
      0x7ffff7ffe000     0x7ffff7fff000     0x1000        0x0 
      0x7ffffffde000     0x7ffffffff000    0x21000        0x0 [stack]
  0xffffffffff600000 0xffffffffff601000     0x1000        0x0 [vsyscall]
(gdb)

After heap space is mapped to a process

(gdb) ni
0x00000000004005c8 in main ()
(gdb) info proc map
process 7207
Mapped address spaces:

          Start Addr           End Addr       Size     Offset objfile
            0x400000           0x401000     0x1000        0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use
            0x600000           0x601000     0x1000        0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use
            0x601000           0x602000     0x1000     0x1000 /home/lazenca0x0/Book/Heap/1.Malloc/in-use
            0x602000           0x623000    0x21000        0x0 [heap]
      0x7ffff7a0d000     0x7ffff7bcd000   0x1c0000        0x0 /lib/x86_64-linux-gnu/libc-2.23.so
...
      0x7ffffffde000     0x7ffffffff000    0x21000        0x0 [stack]
  0xffffffffff600000 0xffffffffff601000     0x1000        0x0 [vsyscall]
(gdb)

할당자로 부터 할당받은 첫번째 Heap의 포인터는 0x602010입니다.
- 145(0x91)가 size(0x602008)에 저장되어 있습니다.
  - 할당자에 의해 할당되는 청크의 크기는 MALLOC_ALIGNMENT의 배수가 됩니다.
  - 이 시스템은 64bit이며, size_t의 크기가 8byte이기 때문에 할당되는 청크의 크기는 모두 16의 배수가 되어야합니다.
  - 136(0x88)은 16의 배수가 아니며, 해당 수와 가장 가까운 16의 배수는 144입니다.
  - 할당자는 이 크기로 청크를 할당합니다.
- 그리고 해당 값에 PREV_INUSE [P](0x1) 플래그를 더한 값이 145(0x91)입니다.
  - 해당 chunk가 프로세스에 매핑된 heap 공간의 최상위에 존재하기 때문에 해당 chunk 앞에 새로운 chunk를 할당할 수습니다.
  - 그래서 해당 청크에 PREV_INUSE [P](0x1) 플래그가 설정됩니다.
- 할당이 가능한 메모리의 크기가 bk(0x602098)에 저장됩니다.

Allocation of the first heap

(gdb) i r rax
rax            0x602010	6299664
(gdb) x/32gx 0x602010 - 0x10
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x0000000000000000	0x0000000000000000
0x602020:	0x0000000000000000	0x0000000000000000
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000000000
0x602050:	0x0000000000000000	0x0000000000000000
0x602060:	0x0000000000000000	0x0000000000000000
0x602070:	0x0000000000000000	0x0000000000000000
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000000	0x0000000000020f71
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000000
0x6020c0:	0x0000000000000000	0x0000000000000000
0x6020d0:	0x0000000000000000	0x0000000000000000
0x6020e0:	0x0000000000000000	0x0000000000000000
0x6020f0:	0x0000000000000000	0x0000000000000000
(gdb)

할당자로부터 할당받은 두번째 Heap의 포인터는 0x6020a0입니다.
- 해당 청크의 크기는 97(0x61)입니다.
- 애플리케이션이 요청한 크기는 80(0x50)입니다.
- 하지만 할당자는 청크를 관리하기 위해 필요한 메타데이터(fd,bk)를 저장하기 위해 요청된 크기에 16을 더해서 메모리를 할당합니다.
- 그리고 해당 청크 앞에 사용중인 청크가 있기 때문에 그 값에 PREV_INUSE [P](0x1) 플래그가 더해집니다.

Allotted of the second heap

(gdb) c
Continuing.

Breakpoint 2, 0x00000000004005d6 in main ()
(gdb) i r rax
rax            0x6020a0	6299808
(gdb) x/32gx 0x602010 - 0x10
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x0000000000000000	0x0000000000000000
0x602020:	0x0000000000000000	0x0000000000000000
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000000000
0x602050:	0x0000000000000000	0x0000000000000000
0x602060:	0x0000000000000000	0x0000000000000000
0x602070:	0x0000000000000000	0x0000000000000000
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000000	0x0000000000000061
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000000
0x6020c0:	0x0000000000000000	0x0000000000000000
0x6020d0:	0x0000000000000000	0x0000000000000000
0x6020e0:	0x0000000000000000	0x0000000000000000
0x6020f0:	0x0000000000000000	0x0000000000020f11
(gdb)

프로세스는 free()함수를 이용하여 첫번째 덩어리(0x602010)를 해제합니다.
- 이로 인해 0x602010 ~ 0x602018 메모리에 fd, bk 값이 저장됩니다.
- 그리고 두번째 chunk의 prev_size에 해제된 chunk의 크기(0x90)가 저장되고, size에는 PREV_INUSE [P](0x1) 플래그 값이 빠진 값이 저장됩니다.

Free the first heap.

(gdb) c
Continuing.

Breakpoint 3, 0x00000000004005e6 in main ()
(gdb) x/32gx 0x602010 - 0x10
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x00007ffff7dd1b78	0x00007ffff7dd1b78
0x602020:	0x0000000000000000	0x0000000000000000
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000000000
0x602050:	0x0000000000000000	0x0000000000000000
0x602060:	0x0000000000000000	0x0000000000000000
0x602070:	0x0000000000000000	0x0000000000000000
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000090	0x0000000000000060
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000000
0x6020c0:	0x0000000000000000	0x0000000000000000
0x6020d0:	0x0000000000000000	0x0000000000000000
0x6020e0:	0x0000000000000000	0x0000000000000000
0x6020f0:	0x0000000000000000	0x0000000000020f11
(gdb)

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

Free the third heap

(gdb) c
Continuing.

Breakpoint 4, 0x00000000004005f0 in main ()
(gdb) i r rax
rax            0x602010	6299664
(gdb) x/32gx 0x602010 - 0x10
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x00007ffff7dd1b78	0x00007ffff7dd1b78
0x602020:	0x0000000000000000	0x0000000000000000
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000000000
0x602050:	0x0000000000000000	0x0000000000000000
0x602060:	0x0000000000000000	0x0000000000000000
0x602070:	0x0000000000000000	0x0000000000000000
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000090	0x0000000000000061
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000000
0x6020c0:	0x0000000000000000	0x0000000000000000
0x6020d0:	0x0000000000000000	0x0000000000000000
0x6020e0:	0x0000000000000000	0x0000000000000000
0x6020f0:	0x0000000000000000	0x0000000000020f11
(gdb)

새로 할당받은 heap 메모리는 정상적으로 사용가능합니다.
- 값을 입력하게 되면 이전에 저장되어 있던 값을 덮어쓰게 됩니다.

Allocated a heap.

(gdb) c
Continuing.
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBB 

Breakpoint 5, 0x000000000040060a in main ()
(gdb) x/32gx 0x602010 - 0x10
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x4141414141414141	0x4141414141414141
0x602020:	0x4141414141414141	0x4141414141414141
0x602030:	0x4141414141414141	0x4141414141414141
0x602040:	0x4141414141414141	0x4141414141414141
0x602050:	0x4141414141414141	0x4141414141414141
0x602060:	0x4141414141414141	0x4141414141414141
0x602070:	0x4141414141414141	0x4141414141414141
0x602080:	0x4141414141414141	0x4141414141414141
0x602090:	0x0a42424242424242	0x0000000000000061
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000000
0x6020c0:	0x0000000000000000	0x0000000000000000
0x6020d0:	0x0000000000000000	0x0000000000000000
0x6020e0:	0x0000000000000000	0x0000000000000000
0x6020f0:	0x0000000000000000	0x0000000000020f11
(gdb)

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는 오직 큰 블록에서만 사용됩니다.

free chunk

다음 코드를 이용하여 free chunk의 변화를 확인하겠습니다.
- malloc()에 3개의 128byte, 3개의 8byte의 메모리 할당을 요청합니다.
- 그리고 크기가 128byte인 메모리들을 해제합니다.

free.c

#include <stdio.h>
#include <stdlib.h>
 
void main(){
        char *heap1 = malloc(128);
        char *tmp2 = malloc(8);
        char *heap2 = malloc(128);
        char *tmp3 = malloc(8);
        char *heap3 = malloc(128);
        char *tmp1 = malloc(8);
 
        free(heap1);
        free(heap2);
        free(heap3);
}

메모리의 변화를 확인하기 위해 다음과 같이 Breakpoint들을 설정합니다.

Breakpoints

lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gcc -o free free.c 
lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gdb -q ./free
Reading symbols from ./free...(no debugging symbols found)...done.
(gdb) disassemble main
Dump of assembler code for function main:
   0x0000000000400566 <+0>:	push   rbp
   0x0000000000400567 <+1>:	mov    rbp,rsp
   0x000000000040056a <+4>:	sub    rsp,0x30
   0x000000000040056e <+8>:	mov    edi,0x80
   0x0000000000400573 <+13>:	call   0x400450 <malloc@plt>
   0x0000000000400578 <+18>:	mov    QWORD PTR [rbp-0x30],rax
   0x000000000040057c <+22>:	mov    edi,0x8
   0x0000000000400581 <+27>:	call   0x400450 <malloc@plt>
   0x0000000000400586 <+32>:	mov    QWORD PTR [rbp-0x28],rax
   0x000000000040058a <+36>:	mov    edi,0x80
   0x000000000040058f <+41>:	call   0x400450 <malloc@plt>
   0x0000000000400594 <+46>:	mov    QWORD PTR [rbp-0x20],rax
   0x0000000000400598 <+50>:	mov    edi,0x8
   0x000000000040059d <+55>:	call   0x400450 <malloc@plt>
   0x00000000004005a2 <+60>:	mov    QWORD PTR [rbp-0x18],rax
   0x00000000004005a6 <+64>:	mov    edi,0x80
   0x00000000004005ab <+69>:	call   0x400450 <malloc@plt>
   0x00000000004005b0 <+74>:	mov    QWORD PTR [rbp-0x10],rax
   0x00000000004005b4 <+78>:	mov    edi,0x8
   0x00000000004005b9 <+83>:	call   0x400450 <malloc@plt>
   0x00000000004005be <+88>:	mov    QWORD PTR [rbp-0x8],rax
   0x00000000004005c2 <+92>:	mov    rax,QWORD PTR [rbp-0x30]
   0x00000000004005c6 <+96>:	mov    rdi,rax
   0x00000000004005c9 <+99>:	call   0x400430 <free@plt>
   0x00000000004005ce <+104>:	mov    rax,QWORD PTR [rbp-0x20]
   0x00000000004005d2 <+108>:	mov    rdi,rax
   0x00000000004005d5 <+111>:	call   0x400430 <free@plt>
   0x00000000004005da <+116>:	mov    rax,QWORD PTR [rbp-0x10]
   0x00000000004005de <+120>:	mov    rdi,rax
   0x00000000004005e1 <+123>:	call   0x400430 <free@plt>
   0x00000000004005e6 <+128>:	nop
   0x00000000004005e7 <+129>:	leave  
   0x00000000004005e8 <+130>:	ret    
End of assembler dump.
(gdb) b *0x00000000004005be
Breakpoint 1 at 0x4005be
(gdb) b *0x00000000004005ce
Breakpoint 2 at 0x4005ce
(gdb) b *0x00000000004005da
Breakpoint 3 at 0x4005da
(gdb) b *0x00000000004005e6
Breakpoint 4 at 0x4005e6
(gdb)

할당자가 할당한 메모리는 다음과 같습니다.
- chunk의 크기가 128바이트인 메모리가 3개(0x602010, 0x6020c0, 0x602170) 할당되었습니다.
- chunk의 크기가 8바이트인 메모리가 3개(0x6020a0, 0x602150, 0x602200) 할당되었습니다.

Allocated memory

(gdb) r
Starting program: /home/lazenca0x0/Book/Heap/1.Malloc/free 

Breakpoint 1, 0x00000000004005be in main ()
(gdb) x/70gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x0000000000000000	0x0000000000000000
0x602020:	0x0000000000000000	0x0000000000000000
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000000000
0x602050:	0x0000000000000000	0x0000000000000000
0x602060:	0x0000000000000000	0x0000000000000000
0x602070:	0x0000000000000000	0x0000000000000000
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000000	0x0000000000000021
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000091
0x6020c0:	0x0000000000000000	0x0000000000000000
0x6020d0:	0x0000000000000000	0x0000000000000000
0x6020e0:	0x0000000000000000	0x0000000000000000
0x6020f0:	0x0000000000000000	0x0000000000000000
0x602100:	0x0000000000000000	0x0000000000000000
0x602110:	0x0000000000000000	0x0000000000000000
0x602120:	0x0000000000000000	0x0000000000000000
0x602130:	0x0000000000000000	0x0000000000000000
0x602140:	0x0000000000000000	0x0000000000000021
0x602150:	0x0000000000000000	0x0000000000000000
0x602160:	0x0000000000000000	0x0000000000000091
0x602170:	0x0000000000000000	0x0000000000000000
0x602180:	0x0000000000000000	0x0000000000000000
0x602190:	0x0000000000000000	0x0000000000000000
0x6021a0:	0x0000000000000000	0x0000000000000000
0x6021b0:	0x0000000000000000	0x0000000000000000
0x6021c0:	0x0000000000000000	0x0000000000000000
0x6021d0:	0x0000000000000000	0x0000000000000000
0x6021e0:	0x0000000000000000	0x0000000000000000
0x6021f0:	0x0000000000000000	0x0000000000000021
0x602200:	0x0000000000000000	0x0000000000000000
0x602210:	0x0000000000000000	0x0000000000020df1
0x602220:	0x0000000000000000	0x0000000000000000
(gdb)

heap1(0x602010)이 해제되면 해당 chunk에 bk,fd 값이 저장됩니다.
- 이전 청크의 크기(0x90)는 tmp2(0x6020a0)의 "prev_size"에 저장되며, "size"에는 PREV_INUSE [P] (0x1) 플래그의 값을 뺀 값(0x20)이 저장됩니다.

First free chunk

(gdb) c
Continuing.

Breakpoint 2, 0x00000000004005ce in main ()
(gdb) x/70gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x00007ffff7dd1b78	0x00007ffff7dd1b78
0x602020:	0x0000000000000000	0x0000000000000000
...
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000090	0x0000000000000020
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000091
0x6020c0:	0x0000000000000000	0x0000000000000000
0x6020d0:	0x0000000000000000	0x0000000000000000
...
0x602130:	0x0000000000000000	0x0000000000000000
0x602140:	0x0000000000000000	0x0000000000000021
0x602150:	0x0000000000000000	0x0000000000000000
0x602160:	0x0000000000000000	0x0000000000000091
0x602170:	0x0000000000000000	0x0000000000000000
0x602180:	0x0000000000000000	0x0000000000000000
...
0x6021e0:	0x0000000000000000	0x0000000000000000
0x6021f0:	0x0000000000000000	0x0000000000000021
0x602200:	0x0000000000000000	0x0000000000000000
0x602210:	0x0000000000000000	0x0000000000020df1
0x602220:	0x0000000000000000	0x0000000000000000
(gdb)

heap2(0x6020c0)가 해제되면 해당 chunk에 fd, bk값이 저장됩니다.
- fd(0x6020c0)에 저장되는 값은 해당 chunk 앞에 있는 Free chunk의 mchunkptr(0x602000)입니다.
- 그리고 heap1의 bk(0x602018)에 heap2의 mchunkptr(0x6020b0)이 저장됩니다.

Second free chunk

(gdb) c
Continuing.

Breakpoint 3, 0x00000000004005da in main ()
(gdb) x/70gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x00007ffff7dd1b78	0x00000000006020b0
0x602020:	0x0000000000000000	0x0000000000000000
...
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000090	0x0000000000000020
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000091
0x6020c0:	0x0000000000602000	0x00007ffff7dd1b78
0x6020d0:	0x0000000000000000	0x0000000000000000
...
0x602130:	0x0000000000000000	0x0000000000000000
0x602140:	0x0000000000000090	0x0000000000000020
0x602150:	0x0000000000000000	0x0000000000000000
0x602160:	0x0000000000000000	0x0000000000000091
0x602170:	0x0000000000000000	0x0000000000000000
0x602180:	0x0000000000000000	0x0000000000000000
...
0x6021e0:	0x0000000000000000	0x0000000000000000
0x6021f0:	0x0000000000000000	0x0000000000000021
0x602200:	0x0000000000000000	0x0000000000000000
0x602210:	0x0000000000000000	0x0000000000020df1
0x602220:	0x0000000000000000	0x0000000000000000
(gdb)

heap3(0x602170)가 해제되면 fd(0x602170)에 해당 chunk 앞에 있는 Free chunk의 mchunkptr(0x6020b0)이 저장합니다.
- 그리고 heap2의 bk(0x6020c8)에 heap3의 mchunkptr(0x602160)이 저장됩니다.

Third free chunk

(gdb) c
Continuing.

Breakpoint 4, 0x00000000004005e6 in main ()
(gdb) x/70gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x00007ffff7dd1b78	0x00000000006020b0
0x602020:	0x0000000000000000	0x0000000000000000
...
0x602080:	0x0000000000000000	0x0000000000000000
0x602090:	0x0000000000000090	0x0000000000000020
0x6020a0:	0x0000000000000000	0x0000000000000000
0x6020b0:	0x0000000000000000	0x0000000000000091
0x6020c0:	0x0000000000602000	0x0000000000602160
0x6020d0:	0x0000000000000000	0x0000000000000000
...
0x602130:	0x0000000000000000	0x0000000000000000
0x602140:	0x0000000000000090	0x0000000000000020
0x602150:	0x0000000000000000	0x0000000000000000
0x602160:	0x0000000000000000	0x0000000000000091
0x602170:	0x00000000006020b0	0x00007ffff7dd1b78
0x602180:	0x0000000000000000	0x0000000000000000
...
0x6021e0:	0x0000000000000000	0x0000000000000000
0x6021f0:	0x0000000000000090	0x0000000000000020
0x602200:	0x0000000000000000	0x0000000000000000
0x602210:	0x0000000000000000	0x0000000000020df1
0x602220:	0x0000000000000000	0x0000000000000000
(gdb)

Bin

Free chunk는 크기와 히스토리에 따라 다양한 목록에 저장됩니다.
이러한 목록을 "bins"라고 합니다.
- 할당자는 할당 요청을 충족시키기 위해 적합한 청크를 bins에서 신속하게 찾아서 재할당합니다.
- bins의 종류에는 Fast bin, Small bin, Large bin, Unsorted bin이 있습니다.

Fast bin

M_MXFAST(1)라는 매개변수를 사용해서 "fastbin"에 포함되는 청크의 범위를 설정합니다.
- "fastbin"에 포함되는 chunk 크기의 범위는 0에서 80*sizeof(size_t)/4까지 입니다.
- "fastbin"의 기본 범위는 0에서 64*sizeof(size_t)/4 입니다.
- 32비트 아키텍처에서 패스트빈의 상한은 64byte(64*4/4)이며, 64비트 아키텍처에서는 128byte(64*8/4)입니다.
  - 해당 크기보다 작은 chunk들이 fastbin에 배치됩니다.
- 해당 크기는 매개변수 "value"를 이용하여 변경할 수 있습니다.
  - 매개변수를 최대로 설정하면 32비트 아키텍처에서는 최대 80byte(80*4/4), 64bit에서는 최대 160byte(80*8/4)의 상한을 설정 할 수 있습니다.
  - fast bin을 비활성화하려면 0으로 설정하면 됩니다.

/release/2.25/master/malloc/malloc.c

  Symbol            param #   default    allowed param values
  M_MXFAST          1         64         0-80  (0 disables fastbins)
  M_TRIM_THRESHOLD -1         128*1024   any   (-1U disables trimming)
  M_TOP_PAD        -2         0          any
  M_MMAP_THRESHOLD -3         128*1024   any   (or 0 if no MMAP support)
  M_MMAP_MAX       -4         65536      any   (0 disables use of mmap)
*/

/release/2.25/master/malloc/malloc.c

/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST            1
#endif

#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)
#endif

Fastbin은 LIFO(last in, first out)를 사용합니다.
- 마지막으로 해제 된 chunk가 먼저 재 할당됩니다.
해당 bin은 최대 10개의 bin 관리 할 수 있으며, 패스트빈의 상한 값보다 크기가 작은 chunk들을 관리합니다.
- 64bit 아키텍처의 경우 Fastbin에 포함되는 chunk의 크기는 32, 48, 64, 80, 96, 112 입니다.
해당 bin은 single-linked list로 구성됩니다.
- 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 fd에 새로 해제된 chunk의 mchunkptr을 저장됩니다.
- bk는 사용하지 않습니다.
해당 bin에 포함되는 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의 범위는 16~504byte(64*8-8)이며 64bit에서는 32~1008byte입니다.
해당 bin은 64개의 bin들을 관리하며, doubly-linked list로 구성됩니다.
- 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 fd에 새로 해제된 chunk의 mchunkptr가 저장됩니다.
- 새로 해제된 chunk의 bk에 마지막으로 해제된 같은 크기의 chunk의 mchunkptr가 저장됩니다.
Small bin은 FIFO(First In, First Out)을 사용합니다.
- 먼저 해제 된 청크가 먼저 재 할당됩니다.
Small bin에 해당되는 chunk들은 서로 인접하게 배치될수 없습니다.
- 해당 chunk가 서로 인접해 있을 경우 하나의 chunk로 병합됩니다.

/release/2.25/master/malloc/malloc.c

#define NBINS             128
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

bin의 인덱스는 smallbin_index() 함수를 이용하여 확인 할 수 있습니다.
- 이함수는 SMALLBIN_WIDTH을 사용해서 해당 시스템이 32bit인지 64bit인지 확인합니다.
  - 64bit의 경우 chunk 크기를 16으로 나눈다음, 그 값에 SMALLBIN_CORRECTION를 더 합니다.
  - 이 값이 해당 chunk의 인덱스 입니다.
  - 32bit의 경우 chunk의 크기를 8로 나눕니다.
- 예를 들어 64bit에서 144byte의 free chunk의 인덱스는 9(504 >> 3 + 0)입니다.

/release/2.25/master/malloc/malloc.c

#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
   + SMALLBIN_CORRECTION)

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내에서 크기 별로 정렬되어 할당의 효율성을 높입니다.

/release/2.25/master/malloc/malloc.c

/*
   Indexing

    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
    8 bytes apart. Larger bins are approximately logarithmically spaced:

    64 bins of size       8
    32 bins of size      64
    16 bins of size     512
     8 bins of size    4096
     4 bins of size   32768
     2 bins of size  262144
     1 bin  of size what's left

    There is actually a little bit of slop in the numbers in bin_index
    for the sake of speed. This makes no difference elsewhere.

    The bins top out around 1MB because we expect to service large
    requests via mmap.

    Bin 0 does not exist.  Bin 1 is the unordered list; if that would be
    a valid chunk size the small bins are bumped up one.
 */

Large bin에 해당하는 chunk들의 인덱스는 largebin_index_32(), largebin_index_64() 함수를 이용하여 확인할 수 있습니다.
- free chunk의 크기를 쉬프트 연산을 이용하여 나누고, 그 값이 조건에 만족하는 값이라면 기본 인덱스 값을 더한 값이 해당 chunk의 인덱스 값이 됩니다.
- 예를 들어 64bit 아키텍처에서 chunk의 크기가 3072 ~ 3120인 chunk들은 bin[96]에 보관됩니다. 48 + (3072 >> 6) = 96

/release/2.25/master/malloc/malloc.c

#define largebin_index_32(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

#define largebin_index_32_big(sz)                                            \
  (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

#define largebin_index(sz) \
  (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
   : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
   : largebin_index_32 (sz))

#define bin_index(sz) \
  ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

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에 배치 됩니다.

128KB 이상의 큰 메모리

할당자는 크기가 128KB보다 큰 메모리를 할당하기 위해 mmap()에 새로운 메모리를 매핑을 요청한 후 해당 메모리에서 Chunk를 할당합니다.
- 해당 Chunk들은 Bin에 속하지 않습니다.
- 해당 Chunk들은 IS_MMAPPED 플래그가 설정됩니다.
- 해당 chunk들은 munmap()을 호출하여 해제합니다.

Arena

ptmalloc2는 각 스레드가 서로 간섭하지 않고, 서로 다른 메모리 영역에 액세스 할 수 있게 합니다.
- 이러한 메모리 영역을 "Arena"라고합니다.
응용 프로그램에는 "주요 경기장"이라는 경기장이 있습니다.
- malloc()에는 이 경기장을 가리키는 정적 변수가 있으며 각 경기장에는 추가 경기장을 연결하는 다음 포인터가 있습니다.
각 Arena는 하나 이상의 힙 메모리를 얻습니다.
- main arena는 프로그램의 초기 힙을 사용합니다 (.bss 등 직후 시작).
- 추가 Arena는 mmap를 통해 힙에 메모리를 할당하고, 이전 힙이 소모되면 더 많은 힙을 힙목록에 추가합니다.
Arena는 heap 메모리에서 할당된 chunk들을 관리합니다.
- Arena에서 관리되는 chunk들은 응용 프로그램에서 사용 중이거나 사용이 가능한 chunk들 입니다.
- 사용중인 청크는 Arena에서 추적되지 않습니다.
- Free chunk는 크기와 히스토리에 따라 분류되어 arena에 저장됩니다.
- 할당자는 arena에서 할당 요청을 충족하는 chunk를 신속하게 찾을 수 있습니다.

struct malloc_state main_arena

malloc.c 코드내에 "main_arena"라는 변수가 존재합니다.
- 이 변수가 앞에서 언급한 main arena입니다.
- 해당 변수는 "struct malloc_state" 구조체를 사용합니다.

glibc-2_5/malloc/malloc.c

/* There are several instances of this struct ("arenas") in this
   malloc.  If you are adapting this malloc in a way that does NOT use
   a static or mmapped malloc_state, you MUST explicitly zero-fill it
   before using. This malloc relies on the property that malloc_state
   is initialized to all zeroes (as is true of C statics).  */

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

"malloc_state"의 구조는 다음과 같습니다.
mutex는 해당 arena에 대한 액세스를 제어하는 데 사용됩니다.
- mutex를 이용하여 여러 스레드간에 arena 사용 충돌이 발생하것을 방지합니다.
- 패스트 빈에 대한 액세스와 같은 일부 작업은 경기장을 잠글 필요가 없습니다.
- 이 외에 다른 모든 작업을 하려면 스레드가 Arena를 잠글 필요가 있습니다.

/release/2.25/master/malloc/malloc.c

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

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가 설정됩니다.

/release/2.25/master/malloc/malloc.c

#define FASTCHUNKS_BIT        (1U)

#define have_fastchunks(M)     (((M)->flags & FASTCHUNKS_BIT) == 0)
#define clear_fastchunks(M)    catomic_or (&(M)->flags, FASTCHUNKS_BIT)
#define set_fastchunks(M)      catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)

/*
   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
   regions.  Otherwise, contiguity is exploited in merging together,
   when possible, results from consecutive MORECORE calls.

   The initial value comes from MORECORE_CONTIGUOUS, but is
   changed dynamically if mmap is ever used as an sbrk substitute.
 */

#define NONCONTIGUOUS_BIT     (2U)

#define contiguous(M)          (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M)       (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M)   ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M)      ((M)->flags &= ~NONCONTIGUOUS_BIT)

fastbins에 fastbin에 해당하는 free chunk가 배치됩니다.
- fastbin에 해당하는 chunk의 인덱스는 fastbin_index()함수를 이용하여 확인할 수 있습니다.
- 해당 함수는 우측 시프트를 이용하여 chunk의 크기(sz)를 8(32bit) 또는 16(64bit)으로 나눈 값에 2를 뺍니다.
- 예를 들어 64bit 아키텍처에서 크기가 32byte인 chunk의 인덱스는 0((32 >> 4) - 2)입니다.

/release/2.25/master/malloc/malloc.c

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 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 영역을 매핑합니다.

malloc.c

  if (av == NULL
      || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
	  && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
      char *mm;           /* return value from mmap call*/

    try_mmap:
      /*
         Round up size to nearest page.  For mmapped chunks, the overhead
         is one SIZE_SZ unit larger than for normal chunks, because there
         is no following chunk whose prev_size field could be used.

         See the front_misalign handling below, for glibc there is no
         need for further alignments unless we have have high alignment.
       */
      if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
        size = ALIGN_UP (nb + SIZE_SZ, pagesize);
      else
        size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
      tried_mmap = true;

      /* Don't try if size wraps around 0 */
      if ((unsigned long) (size) > (unsigned long) (nb))
        {
          mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));

할당자는 메모리를 할당하기에 arena의 공간이 부족할 경우 sbrk()를 호출하여 메모리의 공간을 증가시킵니다.
- malloc.c에서는 MORECORE라는 매크로를 이용하여 sbrk() 함수를 호출합니다.

/release/2.25/master/malloc/malloc.c

      /*
         Don't try to call MORECORE if argument is so big as to appear
         negative. Note that since mmap takes size_t arg, it may succeed
         below even if we cannot call MORECORE.
       */

      if (size > 0)
        {
          brk = (char *) (MORECORE (size));
          LIBC_PROBE (memory_sbrk_more, 2, brk, size);
        }

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[] 배열을 사용하면 많은양의 빈 검색이 간소화됩니다.

/release/2.25/master/malloc/malloc.c

/* Conservatively use 32 bits per map word, even if on 64bit system */
#define BINMAPSHIFT      5
#define BITSPERMAP       (1U << BINMAPSHIFT)
#define BINMAPSIZE       (NBINS / BITSPERMAP)

#define idx2block(i)     ((i) >> BINMAPSHIFT)
#define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT)-1))))

#define mark_bin(m,i)    ((m)->binmap[idx2block(i)] |=  idx2bit(i))
#define unmark_bin(m,i)  ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
#define get_binmap(m,i)  ((m)->binmap[idx2block(i)] &   idx2bit(i))

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

Example

Fast bin

이 예제 코드는 malloc()을 이용하여 fastbin에 포함되는 chunk들을 할당받고, fastbin의 범위를 벋어나는 chunk(크기가 128, 144)도 할당받습니다.
- 이렇게 할당받은 청크는 free()함수를 이용하여 fastbin에 등록 되도록합니다.

fast.c

#include <stdio.h>
#include <stdlib.h>
 
void main(){

    char *fast1 = malloc(16);
    char *fast2 = malloc(32);
    char *fast3 = malloc(48);
    char *fast4 = malloc(64);
    char *fast5 = malloc(80);
    char *fast6 = malloc(96);
    char *fast7 = malloc(128);
    char *fast8 = malloc(144);

    free(fast1);
    free(fast2);
    free(fast3);
    free(fast4);
    free(fast5);
    free(fast6);
    free(fast7);
}

마지막 free()를 호출한 다음의 코드(0x40064c)에 Breakpoint를 설정하고 프로그램을 실행합니다.
- main_arena의 정보는 gdb에 "p main_arena" 명령어를 입력하면 확인할 수 있습니다.
- 해제된 chunk들 중 fastbin에 포함되는 chunk들은 fastbinsY에 배치되어 있습니다.
- 배치된 chunk들의 크기는 0x20(32) ~ 0x70(112)입니다.
- fastbin의 상한 값인 128은 fastbinsY 배치되지 않습니다.

lazenca0x0@ubuntu:~/Book/malloc$ gdb -q ./fast
Reading symbols from ./fast...(no debugging symbols found)...done.
gdb-peda$ disassemble main
Dump of assembler code for function main:
   0x0000000000400566 <+0>:	push   rbp
   0x0000000000400567 <+1>:	mov    rbp,rsp
   0x000000000040056a <+4>:	sub    rsp,0x50
   0x000000000040056e <+8>:	mov    edi,0x10
...
   0x0000000000400647 <+225>:	call   0x400430 <free@plt>
   0x000000000040064c <+230>:	nop
   0x000000000040064d <+231>:	leave  
   0x000000000040064e <+232>:	ret    
End of assembler dump.
gdb-peda$ b *0x000000000040064c
Breakpoint 1 at 0x40064c
gdb-peda$ r
Starting program: /home/lazenca0x0/Book/malloc/fast

Breakpoint 1, 0x000000000040064c in main ()
gdb-peda$ p main_arena 
$1 = {
  mutex = 0x0, 
  flags = 0x0, 
  fastbinsY = {0x602000, 0x602020, 0x602050, 0x602090, 0x6020e0, 0x602140, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x602390, 
...
  binmap = {0x0, 0x0, 0x0, 0x0}, 
  next = 0x7ffff7dd1b20 <main_arena>, 
  next_free = 0x0, 
  attached_threads = 0x1, 
  system_mem = 0x21000, 
  max_system_mem = 0x21000
}
gdb-peda$ x/2gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000021
gdb-peda$ x/2gx 0x602140
0x602140:	0x0000000000000000	0x0000000000000071
gdb-peda$

다음 코드는 malloc()에 크기가 16byte인 메모리의 할당을 4번 요청하고, free()에 그 메모리들의 해제를 요청합니다.
- 이 코드를 이용하여 fastbin에서 동일한 chunk들의 어떻게 관리하는지 확인합니다.

fast2.c

#include <stdio.h>
#include <stdlib.h>
 
void main(){

    char *fast1 = malloc(16);
    char *fast2 = malloc(16);
    char *fast3 = malloc(16);
    char *fast4 = malloc(16);

    free(fast2);
    free(fast1);
    free(fast3);
    free(fast4);
}

0x4005bc, 0x4005c6에 break point를 설정합니다.
- 0x4005bc - free chunk들이 어떻게 관리되는지 확인합니다.
- 0x4005c6 - free chunk의 재사용을 확인합니다.
다음과 같이 해제된 chunk들중 첫번째 free chunk가 fastbinsY에 배치됩니다.
- 이 chunk의 fd에는 두번째 free chunk의 mchunkptr이 저장되어 있습니다.
- 그리고 두번째 chunk의 fd에는 세번째 chunk의 mchunkptr이 저장되어 있습니다.
- bk에는 어떠한 값도 배치되지 않습니다.
- single-linked list 형태로 fastbin들이 연결됩니다.

Chunk management of fast bins

lazenca0x0@ubuntu:~/Book/malloc$ gdb -q ./fast2
Reading symbols from ./fast2...(no debugging symbols found)...done.
gdb-peda$ disassemble main
Dump of assembler code for function main:
   0x0000000000400566 <+0>:	push   rbp
   0x0000000000400567 <+1>:	mov    rbp,rsp
   0x000000000040056a <+4>:	sub    rsp,0x20
...
   0x00000000004005b7 <+81>:	call   0x400430 <free@plt>
   0x00000000004005bc <+86>:	mov    edi,0x10
   0x00000000004005c1 <+91>:	call   0x400450 <malloc@plt>
   0x00000000004005c6 <+96>:	mov    QWORD PTR [rbp-0x8],rax
   0x00000000004005ca <+100>:	nop
   0x00000000004005cb <+101>:	leave  
   0x00000000004005cc <+102>:	ret    
End of assembler dump.
gdb-peda$ b *0x00000000004005bc
Breakpoint 1 at 0x4005bc
gdb-peda$ b *0x00000000004005c6
Breakpoint 2 at 0x4005c6
gdb-peda$ r
Starting program: /home/lazenca0x0/Book/malloc/fast2 

Breakpoint 1, 0x00000000004005bc in main ()
gdb-peda$ p main_arena.fastbinsY 
$1 = {0x602040, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}
gdb-peda$ x/4gx 0x602040
0x602040:	0x0000000000000000	0x0000000000000021
0x602050:	0x0000000000602000	0x0000000000000000
gdb-peda$ x/4gx 0x0000000000602000
0x602000:	0x0000000000000000	0x0000000000000021
0x602010:	0x0000000000602020	0x0000000000000000
gdb-peda$ x/4gx 0x0000000000602020
0x602020:	0x0000000000000000	0x0000000000000021
0x602030:	0x0000000000000000	0x0000000000000000
gdb-peda$

malloc()에 크기가 16byte인 메모리의 할당을 요청하면, Allocater는 해당 크기과 동일한 free chunk가 있는지 fastbinsY에서 확인합니다.
- 할당자는 fastbinsY에 동일한 크기의 chunk가 있다면 해당 chunk를 재할당합니다.
- fastbinsY에는 두번째 free chunk가 배치되었고, 첫번째 free chunk가 반환되었습니다.

Realloc

gdb-peda$ c
Continuing.

Breakpoint 2, 0x00000000004005c6 in main ()
gdb-peda$ p main_arena.fastbinsY 
$2 = {0x602000, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}
gdb-peda$ x/4gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000021
0x602010:	0x0000000000602020	0x0000000000000000
gdb-peda$ x/4gx 0x0000000000602020
0x602020:	0x0000000000000000	0x0000000000000021
0x602030:	0x0000000000000000	0x0000000000000000
gdb-peda$ i r rax
rax            0x602050	0x602050
gdb-peda$

Small bin

이 예제 코드는 사이즈가 128byte인 메모리 3개와 200byte 1개와 160byte 2개, 그리고 해당 메모리 사이에 16byte 메모리 할당을 요청합니다.
- "small*"변수들이 가리키는 메모리들 사이에 16byte의 메모리 할당을 요청하지 않으면 Small bin에 해당하는 chunk들이 연속으로 배치되기 때문에 서로 병합됩니다.
- "small*"변수들이 가리키는 메모리들을 모두 해제한 후 200byte, 128byte의 메모리 할당을 요청합니다.

small.c

#include <stdio.h>
#include <stdlib.h>
 
void main(){

    char *small1 = malloc(128);
    char *tmp1  = malloc(16);
    char *small2 = malloc(128);
    char *tmp2  = malloc(16);
    char *small3 = malloc(128);
    char *tmp3  = malloc(16);

    char *small4 = malloc(200);
    char *tmp4  = malloc(16);

    char *small5 = malloc(160);
    char *small6= malloc(160);
    char *tmp9  = malloc(16);

    free(small2);
    free(small1);
    free(small3);

    free(small4);

    free(small5);
    free(small6);

    char *small7 = malloc(200);
    char *small8 = malloc(128);
}

0x40064b에서 인접한 small chunk의 변화를 확인합니다.
- 0x40065a에서 bins영역에 등록된 small bin을 확인합니다.
- 그리고 0x400668에서 Small bin의 재사용을 확인합니다.

Breakpoints

lazenca0x0@ubuntu:~/Book/malloc$ gcc -o small small.c 
lazenca0x0@ubuntu:~/Book/malloc$ gdb -q ./small
Reading symbols from ./small...(no debugging symbols found)...done.
gdb-peda$ disassemble main
Dump of assembler code for function main:
   0x0000000000400566 <+0>:	push   rbp
   0x0000000000400567 <+1>:	mov    rbp,rsp
   0x000000000040056a <+4>:	sub    rsp,0x70
...
   0x000000000040064b <+229>:	call   0x400430 <free@plt>
   0x0000000000400650 <+234>:	mov    edi,0xc8
   0x0000000000400655 <+239>:	call   0x400450 <malloc@plt>
   0x000000000040065a <+244>:	mov    QWORD PTR [rbp-0x10],rax
   0x000000000040065e <+248>:	mov    edi,0x80
   0x0000000000400663 <+253>:	call   0x400450 <malloc@plt>
   0x0000000000400668 <+258>:	mov    QWORD PTR [rbp-0x8],rax
   0x000000000040066c <+262>:	nop
   0x000000000040066d <+263>:	leave  
   0x000000000040066e <+264>:	ret    
End of assembler dump.
gdb-peda$ b *0x000000000040064b
Breakpoint 1 at 0x40064b
gdb-peda$ b *0x000000000040065a
Breakpoint 2 at 0x40065a
gdb-peda$ b *0x0000000000400668
Breakpoint 3 at 0x400668
gdb-peda$

free chunk들은 먼저 Unsorted bin에 배치되기 때문에 마지막에 해제된 chunk는 Unsorted bin에서 찾을 수 있습니다.
- 해당 어플리케이션에서 마지막에 해제된 chunk는 0x602300이며, 크기는 176byte입니다.
- free()를 이용하여 해제할 메모리는 0x6023c0이며, 이 메모리는 마지막에 해제된 chunk과 인접해 있습니다.
free()가 실행되면 두 chunk는 병합되어 하나의 chunk가 됩니다.
- 해당 chunk(0x602300)의 크기가 352byte가 되었습니다.

Coalesce of adjacent chunks

gdb-peda$ r
Starting program: /home/lazenca0x0/Book/malloc/small 

Breakpoint 1, 0x000000000040064b in main ()
gdb-peda$ p main_arena.bins[0]
$2 = (mchunkptr) 0x602300
gdb-peda$ p main_arena.bins[1]
$3 = (mchunkptr) 0x6020b0
gdb-peda$ p main_arena.bins[0].size
$4 = 0xb1
gdb-peda$ p/d main_arena.bins[0].size - 1
$5 = 176
gdb-peda$ x/i $rip
=> 0x40064b <main+229>:	call   0x400430 <free@plt>
gdb-peda$ i r rdi
rdi            0x6023c0	0x6023c0
gdb-peda$ ni

0x0000000000400650 in main ()
gdb-peda$ p main_arena.bins[0]
$6 = (mchunkptr) 0x602300
gdb-peda$ p/d main_arena.bins[0].size - 1
$7 = 352
gdb-peda$

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

Chunk management of small bin

gdb-peda$ p/d ((0x90 >> 4) - 1) * 2
$8 = 16
gdb-peda$ p main_arena.bins[16]
$9 = (mchunkptr) 0x7ffff7dd1bf8 <main_arena+216>
gdb-peda$ p main_arena.bins[17]
$10 = (mchunkptr) 0x7ffff7dd1bf8 <main_arena+216>
gdb-peda$ c
Continuing.

Breakpoint 2, 0x000000000040065a in main ()
gdb-peda$ p main_arena.bins[16]
$11 = (mchunkptr) 0x602160
gdb-peda$ p main_arena.bins[17]
$12 = (mchunkptr) 0x6020b0
gdb-peda$ x/4gx 0x602160
0x602160:	0x0000000000000000	0x0000000000000091
0x602170:	0x0000000000602000	0x00007ffff7dd1bf8
gdb-peda$ x/4gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000091
0x602010:	0x00000000006020b0	0x0000000000602160
gdb-peda$ x/4gx 0x00000000006020b0
0x6020b0:	0x0000000000000000	0x0000000000000091
0x6020c0:	0x00007ffff7dd1bf8	0x0000000000602000
gdb-peda$

어플리케이션이 Small bin에 배치된 chunk와 동일한 크기의 메모리 할당을 요청하면, 할당자는 먼저 해제되었던 chunk(0x6020c0)를 재할당합니다.
- 그리고 해당 chunk(0x6020c0) 뒤에 있던 chunk(0x602000)가 bins[17]에 배치됩니다.

Realloc

gdb-peda$ c
Continuing.

Breakpoint 3, 0x0000000000400668 in main ()
gdb-peda$ p main_arena.bins[16]
$13 = (mchunkptr) 0x602160
gdb-peda$ p main_arena.bins[17]
$14 = (mchunkptr) 0x602000
gdb-peda$ i r rax
rax            0x6020c0	0x6020c0
gdb-peda$

할당자가 크기가 272byte인 free chunk를 3개 가지고 있으면 마지막으로 해제된 chunk의 mchunkptr은 bins[32]에 배치합니다.
- 맨처음에 해제된 chunk의 mchunkptr는 bins[33]에 배치됩니다.

Small bins

Large bin

이 예제에서는 1024, 1040, 1056 byte인 메모리 3개, 200byte 1개, 1120byte 2개, 그리고 해당 메모리 사이에 16byte 메모리 할당을 요청합니다.
- "large*" 변수가 가리키는 메모리들 사이에 16byte의 메모리 할당을 요청하지 않으면 Large bin에 해당하는 chunk들이 연속으로 배치되기 때문에 서로 병합됩니다.
- "large*" 변수가 가리키는 메모리들을 모두 해제한 후 200byte, 1040byte의 메모리 할당을 요청합니다.

large.c

#include <stdio.h>
#include <stdlib.h>
  
void main(){
 
    char *large1 = malloc(1024);
    char *tmp1  = malloc(16);
    char *large2 = malloc(1040);
    char *tmp2  = malloc(16);
    char *large3 = malloc(1056);
    char *tmp3  = malloc(16);
 
    char *large4 = malloc(200);
    char *tmp4  = malloc(16);
 
    char *large5 = malloc(1120);
    char *large6= malloc(1120);
    char *tmp9  = malloc(16);
 
    free(large2);
    free(large1);
    free(large3);
 
    free(large4);
 
    free(large5);
    free(large6);
 
    char *large7 = malloc(200);
    char *large8 = malloc(1040);
}

0x40064b에서 인접한 Large chunk의 변화를 확인합니다.
- 0x40065a에서 bins[]에 배치된 Large chunk을 확인합니다.
- 그리고 0x400668에서 Large chunk의 재사용을 확인합니다.

Breakpoints

lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gcc -o large large.c 
lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gdb -q ./large
Reading symbols from ./large...(no debugging symbols found)...done.
gdb-peda$ disassemble main
Dump of assembler code for function main:
   0x0000000000400566 <+0>:	push   rbp
   0x0000000000400567 <+1>:	mov    rbp,rsp
   0x000000000040056a <+4>:	sub    rsp,0x70
...
   0x000000000040064b <+229>:	call   0x400430 <free@plt>
   0x0000000000400650 <+234>:	mov    edi,0xc8
   0x0000000000400655 <+239>:	call   0x400450 <malloc@plt>
   0x000000000040065a <+244>:	mov    QWORD PTR [rbp-0x10],rax
   0x000000000040065e <+248>:	mov    edi,0x410
   0x0000000000400663 <+253>:	call   0x400450 <malloc@plt>
   0x0000000000400668 <+258>:	mov    QWORD PTR [rbp-0x8],rax
   0x000000000040066c <+262>:	nop
   0x000000000040066d <+263>:	leave  
   0x000000000040066e <+264>:	ret    
End of assembler dump.
gdb-peda$ b *0x000000000040064b
Breakpoint 1 at 0x40064b
gdb-peda$ b *0x000000000040065a
Breakpoint 2 at 0x40065a
gdb-peda$ b *0x0000000000400668
Breakpoint 3 at 0x400668
gdb-peda$

마지막으로 해제된 chunk는 0x602db0이며, 크기는 1136byte입니다.
- free()를 이용하여 해제할 메모리는 0x603230이며, 이 메모리는 마지막에 해제된 chunk과 인접해 있습니다.
free()가 실행되면 두 chunk는 병합되어 하나의 chunk가 됩니다
- 해당 chunk(0x602db0)의 크기가 2272byte가 되었습니다.

Coalesce of adjacent chunks

gdb-peda$ r
Starting program: /home/lazenca0x0/Book/Heap/1.Malloc/large 

Breakpoint 1, 0x000000000040064b in main ()
gdb-peda$ p main_arena.bins[0]
$1 = (mchunkptr) 0x602db0
gdb-peda$ p main_arena.bins[1]
$2 = (mchunkptr) 0x602430
gdb-peda$ p main_arena.bins[0].size
$3 = 0x471
gdb-peda$ p/d main_arena.bins[0].size - 1
$4 = 1136
gdb-peda$ x/i $rip
=> 0x40064b <main+229>:	call   0x400430 <free@plt>
gdb-peda$ i r rdi
rdi            0x603230	0x603230
gdb-peda$ ni

0x0000000000400650 in main ()
gdb-peda$ p main_arena.bins[0]
$6 = (mchunkptr) 0x602db0
gdb-peda$ p main_arena.bins[0].size
$7 = 0x8e1
gdb-peda$ p/d main_arena.bins[0].size - 1
$9 = 2272
gdb-peda$

크기가 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)

Chunk management of small bin

gdb-peda$ p main_arena.bins[1]
$19 = (mchunkptr) 0x602430
gdb-peda$ x/4gx 0x602430
0x602430:	0x0000000000000000	0x0000000000000421
0x602440:	0x00007ffff7dd1b78	0x0000000000602000
gdb-peda$ x/4gx 0x0000000000602000
0x602000:	0x0000000000000000	0x0000000000000411
0x602010:	0x0000000000602430	0x0000000000602870
gdb-peda$ x/4gx 0x0000000000602870
0x602870:	0x0000000000000000	0x0000000000000431
0x602880:	0x0000000000602000	0x0000000000602cc0
gdb-peda$ p/d ((1040 >> 6) + 48 - 1) * 2
$12 = 126
gdb-peda$ p main_arena.bins[126]
$13 = (mchunkptr) 0x7ffff7dd1f68 <main_arena+1096>
gdb-peda$ p main_arena.bins[127]
$14 = (mchunkptr) 0x7ffff7dd1f68 <main_arena+1096>
gdb-peda$ c
Continuing.

Breakpoint 2, 0x000000000040065a in main ()
gdb-peda$ p main_arena.bins[126]
$15 = (mchunkptr) 0x602870
gdb-peda$ p main_arena.bins[127]
$16 = (mchunkptr) 0x602000
gdb-peda$ x/4gx 0x602870
0x602870:	0x0000000000000000	0x0000000000000431
0x602880:	0x0000000000602430	0x00007ffff7dd1f68
gdb-peda$ x/4gx0x0000000000602430
0x602430:	0x0000000000000000	0x0000000000000421
0x602440:	0x0000000000602000	0x0000000000602870
gdb-peda$ x/4gx 0x0000000000602000
0x602000:	0x0000000000000000	0x0000000000000411
0x602010:	0x00007ffff7dd1f68	0x0000000000602430
gdb-peda$

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

Realloc

gdb-peda$ c
Continuing.

Breakpoint 3, 0x0000000000400668 in main ()
gdb-peda$ p main_arena.bins[126]
$17 = (mchunkptr) 0x602870
gdb-peda$ p main_arena.bins[127]
$18 = (mchunkptr) 0x602000
gdb-peda$ i r rax
rax            0x602440	0x602440
gdb-peda$

Reference

Excuse the ads! We need some help to keep our site up.

Page tree

01.Malloc - glibc(ptmalloc2)[Korean]

List

1.Malloc

Memory Allocator

Chunk

Struct of malloc_chunk

In-use chunk

Free chunk

Bin

Fast bin

Small bin

Large bin

Unsorted bin

128KB 이상의 큰 메모리

Arena

struct malloc_state main_arena

Example

Fast bin

Small bin

Large bin

Reference