Page tree
Skip to end of metadata
Go to start of metadata

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.