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

List

1.Malloc

Memory Allocator

  • Implementing heap exploits requires an understanding of Allocator, which is used for memory management.
    • There are various kinds of memory allocators: dlmalloc, ptmalloc2, jemalloc, tcmalloc, libumem, etc.
  • This book will explain ptmalloc2, the memory allocator of the GNU C Library.
    • ptmalloc2 is based on the dlmalloc code and extended for use in multithreading.
    • ptmalloc2 allows you to activate more than one memory area at a time to handle multithreaded applications efficiently.
    • When multiple threads call malloc at the same time, each thread creates a separate heap segment, and the data structures that maintain the heap are also separated and allocated for memory.
    • Thus, different threads can access different memory areas without interfering with each other.

Chunk

  • When you ask Malloc for memory allocation, it divides the large memory area ("heap") into chunks of various sizes ("chunk").

    • Chunk has In-use chunk, Free chunk, Top chunk, and Last Remainder chunk.

      • In-use chunk is the chunk that is in use allocated by the application.
      • Free chunk is the chunk returned by the application to the system.

      • Top chunk is the chunk at the top of Arena.

      • When Allocator allocates memory, it checks to see if there are available Free chunks.
        • If no chunk matches the requested size, but the larger chunk is available, it divides the chunk.
        • At this point, the remaining chunks are the "Last Remainder chunk."

    • The minimum size of the chunk is 4 * sizeof(void *) unless size_t is the same size as void *.

      • The minimum size may be larger if the platform's ABI requires additional sorting.

  • Each chunk has metadata about its size and the position of the adjacent chunk.

    • Available to know if the chunk is in use or free using metadata.
    • So is the previous chunk.

Struct of malloc_chunk

  • malloc() declares a malloc_chunk structure, mchunkptr, to manage each chunk.
    • malloc_chunk structure is the metadata described earlier.
/release/2.25/master/malloc/malloc.c
/* Forward declarations.  */
struct malloc_chunk;
typedef struct malloc_chunk* mchunkptr;
  • The structure malloc_chunk manages six informations.

    • When the old chunk becomes Free Chunk, the size of the old one is stored in "mchunk_prev_size".

    • Conversely, when the old chunk becomes an In-use chunk, user data of the old chunk may be placed.

    • Allocater saves the size of In-use chunk to "mchunk_size".

      • The last 3 bits of the field represent flag information.

  • Free chunks are stored in various lists by size and history. These lists are called "bins".

    • "fd(Forward pointer)" has a pointer of the next Free Chunk.

    • "bk(Backward pointer)" has a pointer of the previous Free Chunk.

    • Only pointers to large chunks are placed in fd_nextsize and bk_nextsize.
  • fd, bk, fd_nextsize, bk_nextsize are used only for free chunks.
/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;
};

  • The size of all chunks is a multiple of MALLOC_ALIGNMENT (2 * sizeof (size_t)).

    • In the case of 32bit, the size of the chunk is multiple of 8 because size_t is 4 bytes.
    • Thus, three LSBs (least significant bit) can be used as flags in the mchunk_size of the chunk.
  • The last 3 bits of the mchunk_size field is used as the flags.
  • These three flags are defined as follows:
    • PREV_INUSE [P] (0x1) flag is used only when an adjacent previous chunk is in use.
    • IS_MMAPPED [M] (0x2) flag is used if the chunk allocated from mmap().
    • NON_MAIN_ARENA [A] (0x4) flag is used when the chunk is allocated from a non-main arena.
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 is a chunk of memory that is being used by allocating memory from an allocator.
    • The size of the previous chunk is saved in mchunk_prev_size when the previous chunk is free.
    • The size of chunk is saved in mchunk_size. The last 3 bits of the field represent flag information.
in-use chunk

  • Use the following code to check for in-use chunks in the application's memory.
    • Request to malloc() for memory allocations of size 128 and 80 bytes.
    • Store the pointer returned from malloc() in heap1 and heap2.
    • Request to free() to free the memory pointed by heap1.
    • Request to malloc() to allocate a memory of the size of 128 bytes again.
    • The returned pointer is stored in heap3.
    • Use the read() to enter data into the memory pointed by 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);
}

  • Set the breakpoints as follows to check the memory change.

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)
  • The first breakpoint is before malloc() is called.
    • The system maps the space to a process only if Heap space is needed.
    • The space is not mapped basically.
    • Heap space is mapped to this process after malloc() is called.
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)

  • The pointer of the first heap-allocated from the allocator is 0x602010.

    • 145(0x91) is stored at size(0x602008)
      • The size of the chunk allocated by the allocator is a multiple of MALLOC_ALIGNMENT.
      • The system is 64 bits, and the size of size_t is 8 bytes, so all chunks allocated must be multiples of 16.
      • 136(0x88) is not a multiple of 16, the nearest multiple of 16 is 144(0x90).
      • The allocator allocates chunks of this size.
    • The value (0x90) plus the PREV_INUSE [P](0x1) flag is 145(0x91).
      • Since the chunk is at the top of the heap space mapped to the process, it's available to allocate a new chunk before the chunk.
      • So the PREV_INUSE [P](0x1) flag is set in the chunk.

    • The amount of memory that can be allocated is stored in 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)

  • The pointer of the second heap-allocated from the allocator is 0x6020a0.

    • The chunk size is 97(0x61).
    • The size requested by the application is 80(0x50).
    • However, the allocator allocates memory by adding 16 to the requested size to store the metadata (fd, bk) needed to manage the chunks.
    • And since there is a chunk in use before the chunk, the value is added with the PREV_INUSE [P] (0x1) flag.
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)

  • Process frees the first chunk (0x602010) using free() function.

    • This causes fd, bk values ​​to be stored at 0x602010, 0x602018 memory.
    • The size of the free chunk(0x90) is stored in the second chunk's "prev_size", the value missing PREV_INUSE [P](0x1) flag is saved in 'size'.
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)

  • The third pointer of heap-allocated from the allocator is 0x602010.

    • This pointer is the same as the pointer that was first allocated.
    • malloc() manages free chunks for memory efficiency.
      • The allocator uses free chunks first when it is asked to allocate memory.
    • The reallocated chunks remain as they were before the previously saved data was not initialized.
    • The value that changes is the "size" of the second chunk, which changes from 0x60 to 0x61.
      • Since the chunk is in use previous the second chunk, the PREV_INUSE [P] (0x1) flag is added.
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)
  • The newly allocated heap memory is available to use.
    • If inputting value, the previous value is overwritten.
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 is the chunk returned to the allocator.
    • Depending on the chunk size, the values ​​of fd, bk, fd_nextsize, and bk_nextsize are stored in the chunk.
      • If the size of the chunk is the minimum, it's unavailable to save the values ​​of fd_nextsize, bk_nextsize.
      • In this case, the size of the free chunk does not grow.
        • The chunk stores only prev_size, size, fd, and bk values ​​in memory.
        • fd_nextsize and bk_nextsize are only used for large blocks.
free chunk

  • Check the change of free chunk using the following code.
    • Request malloc() for memory allocations of three 128-byte and three 8-byte.
    • Then free the 128 bytes of memory.
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);
}
  • Set the breakpoints as follows to check the change of the memory.
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)

  • The memory allocated by the allocator is as follows:

    • Allocated three memory chunks of 128 byte.(0x602010, 0x6020c0, 0x602170)
    • Allocated three memory chunks of 8 bytes.(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)

  • When heap1 (0x602010) is freed, the bk, fd value is stored in the chunk.

    • The size of the previous chunk (0x90) is stored in prev_size of tmp2(0x6020a0), the value (0x20) minus the value of the PREV_INUSE [P] (0x1) flag is stored in "size".
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)

  • When heap2(0x6020c0) is freed, fd and bk are stored in the chunk.

    • The value stored in fd(0x6020c0) is mchunkptr (0x602000) of the Free chunk in front of the chunk.

    • Then "mchunkptr"(0x6020b0) of "heap2" is stored in bk(0x602018) of heap1.

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)

  • When heap3(0x602170) is freed, fd(0x602170) stores the mchunkptr(0x6020b0) of the free chunk in front of the chunk.

    • Then "mchunkptr"(0x602160) of "heap3" is stored in bk(0x6020c8) of heap2.

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 chunks are stored in various lists by their size and history.

  • The lists are called "bins".

    • The allocator quickly finds and reallocates the appropriate chunks in bins to satisfy the allocation request.

    • Types of bins include Fast bins, Small bins, Large bins, and Unsorted bins.

Fast bin

  • Set the range of chunks contained in "fastbin" using a parameter called M_MXFAST(1).

    • The range of chunk size included in "fastbin" is 0 to 80 * sizeof (size_t) / 4.

    • The default range for "fastbin" is 0 to 64 * sizeof (size_t) / 4.

    • On 32-bit architectures, the upper limit for "fastbin" is 64 bytes (64 * 4/4) and on 64-bit architectures is 128 bytes (64 * 8/4).

      • Chunks smaller than that size are placed in fastbin.
    • The size can be changed using the parameter "value".
      • If setting the parameter to maximum, it's available to set an upper limit of up to 80 bytes (80 * 4/4) on 32-bit architectures and up to 160 bytes (80 * 8/4) on 64-bits.
      • Set 0 to disable fast bins.
/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 uses LIFO (last in, first out).

    • The last freed chunk is reallocated first.

  • The bin can manage up to 10 bins and manage chunks smaller than the upper limit of fastbin.
    • For 64-bit architectures, the size of chunk included in Fastbin are 32, 48, 64, 80, 96, and 112.
  • The bin consists of single-linked list.
    • If a chunk of the same size is freed, the mchunkptr of the newly freed chunk is stored in the fd of the last free chunk.
    • bk is not used.
  • The chunks contained in the bin are not merged even if they are adjacent to each other.

Small bin

  • The chunks included in the small bin are chunks smaller than MIN_LARGE_SIZE.

    • On 32-bit systems, MALLOC_ALIGNMENT is 8 and SIZE_SZ is 4.

      • MIN_LARGE_SIZE is 512 ((64-0) * 8).

    • On 64-bit systems, MALLOC_ALIGNMENT is 16 and SIZE_SZ is 8.

      • MIN_LARGE_SIZE is 1024 ((64 * 0) * 16).

    • On 32-bit systems, the small bin ranges from 16 to 504 bytes (64 * 8-8) and on 64bit, 32 to 1008 bytes.

  • The bin manages 64 bins and consists of doubly-linked list.
    • If a chunk of the same size is freed, mchunkptr of the newly freed chunk is stored in fd of the last freed chunk.
    • Bk of the newly freed chunk stores mchunkptr of the same sized chunk that was the last freed.

  • Small bin uses FIFOs (First In, First Out).

    • The chunks freed first are reallocated first.

  • The chunks of a small bin cannot be placed adjacent to each other.

    • If the chunks are adjacent to each other, they are merged into one 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)

  • The index of the bin can be checked using smallbin_index() function.

    • The function uses SMALLBIN_WIDTH to determine whether the system is 32-bit or 64-bit.
      • For 64bit, divide the chunk size by 16, then add SMALLBIN_CORRECTION to that value.
      • This value is the index of the chunk.
      • For 32bit, divide the chunk's size by 8.

    • For example, the index of a free chunk of 144 bytes on 64 bits is 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

  • The size of the chunk included in the Large bin are chunks that are the same as or larger than MIN_LARGE_SIZE.

    • For 64-bit architectures, if the size of the free chunk is larger than or equal to 1024, that chunk is placed in the Larger bin.
  • If the chunks in the Large bin are adjacent to each other, it merges into one.
  • Large bin uses 63 of bin and consists of the doubly-linked list like a small bin.

    • However, unlike a Small bin, Large bin stores chunks of various sizes in a single bin.

    • The bins are just sorted by size within the bin to increase allocation efficiency. 
/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.
 */

  • The indexes of chunks corresponding to the Large bin can be checked using the largebin_index_32 () and largebin_index_64 () functions.

    • The size of the free chunk is divided by the shift operation, and if the value satisfies the condition, the base index value is added to the index value of the chunk.
    • For example, in 64bit architecture, chunks with chunk sizes from 3072 ~ 3120 are stored in 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)

// 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) : largebin_index_32 (sz))

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

Unsorted bin

  • After splitting the chunks, the remaining chunks and all chunks returned are placed first in the Unsorted bin.
    • Because the bin has no limit on the chunk size, chunks of various sizes can be stored in that bin. 
    • However, chunks corresponding to the fast bin are not placed in unsorted bins.
    • The allocator will reallocate that chunk if it has the same chunk as the requested memory size in the Unsorted bin.
  • Unsorted Bin uses only one bin and uses the doubly-linked list and FIFO.
    • The process of allocating and freeing is faster because there is less time to find an appropriate bin using the bin.
  • Chunks retrieved by Allocator are either reallocated immediately or placed in the original bin.

Memory larger than 128 KB

  • The allocator requests mmap () to map new memory to allocate memory larger than 128KB in size and then allocates chunks from that memory.
    • These chunks do not belong in the bin.
    • The chunks are set with the IS_MMAPPED flag.
    • The chunks are freed by calling munmap().

Arena

  • ptmalloc2 allows each thread to access different memory areas without interfering with each other.
    • These memory areas are called "Arena".
  • The application has an arena called the "main arena".
    • malloc() has a static variable pointing to this arena, and each arena has the next pointers to connect the additional arena.
  • Each Arena gets one or more heap memory.
    • main arena uses the initial heap of the program.
    • Additional Arena allocates memory for the heap through mmap, and adds more heaps to the heap list even if the previous heap is exhausted.
  • Arena manages chunks allocated from heap memory.
    • The chunks managed by Arena are those chunks that are in use or available to the application.
    • Chunks in use are not tracked in the arena.
    • Free chunks are sorted by size and history and stored in the arena.
    • The allocator can quickly find chunks that meet the allocation request in Arena.

struct malloc_state main_arena

  • There is a variable called "main_arena" in the malloc.c code.
    • This variable is the main arena mentioned earlier.
    • The variable uses a "struct malloc_state" structure.
/release/2.25/master/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
};
  • The structure of "malloc_state" is as follows:

  • mutex is used to control access to the arena.

    • Use mutex to prevent conflicts between threads.

    • Some operations, such as access to the fastbin, do not need to lock the Arena.

    • thred needs to lock Arena to do every other works.
/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;
};

  • The flags of main_area indicates the presence or absence of the information by two bits.

    • The first bit indicates if the arena has fastbin(fastchunk).
      • If fastbin (fastchunk) is in the arena, the value of the first bit is 0, otherwise, 1 is stored.
    • The second bit indicates whether the arena is contiguous.
      • 1 if the arenas are adjacent, 0 otherwise.
      • Non-main arena consists of the child heap and always NONCONTIGUOUS_BIT is set.
/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)

  • In fastbins, free chunk corresponding to fastbin is placed.

    • The index of chunk corresponding to fastbin can be checked using the fastbin_index() function.

    • This function uses the right shift to subtract 2 from the chunk size (sz) divided by 8 (32 bit) or 16 (64 bit).

    • For example, on a 64-bit architecture, a 32-byte chunk has an index of 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 chunk is placed top.
    • Top chunks are the chunks in the top area of Arena and are not included in the bin.
    • Top chunk is set with the PREV_INUSE flag.
    • If the size of the top chunk is larger than the size requested by the user, the top chunk is split into two.
      • The chunk of the size requested by the user, and the remainder chunks after the split.
    • The Remainder chunk becomes a new Top chunk.
  • The allocator increases the size of the top chunk or allocates a new heap according to the condition if the size of the top chunk is smaller than the size requested by the user.

    • The allocator maps a new heap area by calling mmap () if the size of the chunk requested is greater than DEFAULT_MMAP_THRESHOLD(131072).

/release/2.25/master/malloc/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));

  • The allocator increases the space in memory by calling sbrk () if there is not enough space in the arena to allocate memory.

    • In malloc.c, the sbrk() function is called using a macro named MORECORE.
/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 will place the remainder chunks after allocating chunks.

    • The allocator may split a free chunk larger than the requested size into the request size if no free chunks match the requested size.

  • In "bins" free chunks that contain unsorted bins, small bins, and large bins are placed.

    • The variable is an array variable and can place a total of (128 * 2-2) 254 chunk pointers.

    • When placing a free chunk in bins, the size of the array is 254 instead of 128 because it stores the fd, bk of the chunk.

      • bins [0], bins [1] are placed in the Unsorted bins.

  • binmap divides bins into 4 (BINMAPSIZE) regions to place information.

    • binmap[0] : 0 ~ 31, binmap[1] : 32 ~ 64, binmap[2] : 65 ~ 96, binmap[3] : 97 ~128

    • If a free chunk is placed in bins [], the binmap [] places the bits of that bin at the corresponding bin.

    • For example, the index of a free chunk with a size of 256 bytes is 65, and bit information is stored in binmap[2].

      • The allocator calculates the bit value to be stored using the idx2bit () function.

      • binmap[2]에는 2(1 << (index(65) & 31))가 배치됩니다.

    • Using the binmap [] array simplifies searching for large amounts of bins.

/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 is a pointer to the additional arena if there are multiple arenas.

Example

Fast bin

  • This example code uses malloc () to allocate chunks contained in fastbin and chunks(sizes 128, 144) out of fastbin's scope.
    • This allocated chunk is registered with fastbin using the free () function.
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);
}
  • Set the breakpoint in the code (0x40064c) after the last call to free () and run the program.
    • The main_arena information can be obtained by entering the "p main_arena" command in gdb.
    • Among the free chunks, the chunks included in fastbin are placed in fastbinsY.
    • The chunks placed are sized from 0x20 (32) to 0x70 (112).
    • The upper limit of fastbin, 128, does not place 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$
  • The following code request malloc() to allocate 16 bytes of memory four times and request free() to free them.
    • Use this code to see how fastbin manages the same chunks.
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);
}

  • Set break points at 0x4005bc and 0x4005c6.

    • Check how free chunks are managed at 0x4005bc.
    • Check the reuse of free chunks at 0x4005c6.
Breakpoints
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$
  • The first chunk released is placed in fastbinsY.
    • This chunk's fd has the mchunkptr of the second free chunk.
    • The second chunk's fd has the third chunk's mchunkptr.
    • No value is placed in the bk.
    • Fastbins are linked in a single-linked list.
Chunk management of fast bins
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$
  • When you ask malloc () to allocate 16 bytes of memory, Allocater checks fastbinsY for a free chunk equal to that size.
    • The allocator reallocates chunks if fastbinsY has chunks of the same size.
    • fastbinsY has a second free chunk deployed, and the first free chunk is returned.
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

  • This example code asks for three bytes of 128-byte memory, one 200 byte, two 160 bytes, and a 16-byte memory allocation between the memory memories.
    • If you do not request 16 bytes of memory allocation between the memories pointed to by the "small *" variables, the chunks corresponding to the small bins are contiguously placed and merged together.

    • After freeing all the memory pointed to by the "small *" variables, request 200byte or 128byte memory allocation.

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);
}

  • Notice the change in the adjacent small chunk at 0x40064b.

    • Check the small bin registered in bins area at 0x40065a.

    • Then check the reallocate of the small bin at 0x400668.
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 chunks are placed first in the Unsorted bin, so the last chunk freed can be found in the Unsorted bin.
    • The chunk last released in this application is 0x602300 and 176 bytes in size.
    • The memory to be freed using the free() is 0x6023c0, which is adjacent to the chunk that was freed last.

  • When free () is executed, the two chunks are merged into one chunk.

    • The chunk (0x602300) is now 352 bytes in size.

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$
  • The indexes for chunks of size 144(128 + 16) bytes are 16 and 17.
    • The chunks corresponding to the small bin are still placed in the Unsorted bin.
  • Because the list is disconnected when the chunks in the unsorted bins are reallocated, the Allocator places the disconnected chunks in the bins.
    • There are three free chunks that are 128 bytes in size.
    • Of these, bins [16] will have the last released chunk, and bins [17] will have the first released chunk.
  • The allocator places the chunk's mchunkptr before and after the chunk in fd and bk.
    • The chunk at the first and the chunk at the end put the addresses of "bins" in fd, bk.
    • Allocator sees the addresses of "bins" placed on free chunks as one chunk.
    • So the allocator uses the address of bins [idx] minus 16.
    • This is a 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$
  • When an application requests memory allocation of the same size as a chunk placed in the small bin, the allocator will reallocate the chunk (0x6020c0) that was released first.
    • And the chunk(0x602000) that followed that chunk(0x6020c0) is placed in 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$
  • If the allocator has three free chunks of 272 bytes in size, mchunkptr of the chunk freed last is placed in bins[32].
  •  mchunkptr of the chunk freed first is placed in bins[33].
Small bins

Large bin

  • This example code requests three 1024, 1040, 1056 byte memories, one 200byte, two 1120bytes, and a 16byte memory allocation between them.
    • If not request 16 bytes of memory allocation between the memory pointed to by the "large *" variable, the chunks corresponding to the large bins are contiguously placed and merged together.

    • After freeing all the memory pointed to by the "large *" variable, request 200byte or 1040byte memory allocation.

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);
}

  • Notice the change in the adjacent large chunk at 0x40064b.

    • Check the Large chunk placed on bins[] at 0x40065a.

    • Check the reuse of the large chunk at 0x400668.
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$
  • The chunk freed last is 0x602db0 and is 1136 bytes in size.
    • The memory to be freed using free () is 0x603230, which is adjacent to the chunk that was freed last.

  • When free () is executed, two chunks are merged into one chunk.

    • The chunk (0x602db0) is now 2272 bytes in size.

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$

  • The indexes for chunks of size 1040 (1024 + 16) bytes are 126 and 127.

    • Large bins link chunks to a doubly-linked list just like small bins.

  • The allocator sorts chunk corresponding to the index by size when chunks corresponding to large bins are placed in "bins".

    • When Chunks are in the Unsorted bin, they are connected in the order they were freed.

      • 0x602870 (size : 0x430) <--> 0x602000 (size : 0x410) <--> 0x602430 (size : 0x420)

    • However, when Chunks are placed in "bins", they are sorted by chunk size.

      • 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$
  • When an application requests memory allocation of the same size as a chunk placed in a large bin, the allocator reallocates the chunk (0x602440) equal to the requested size.
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.