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.
/* 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.
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.
/* --------------- 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.
- 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.
#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.
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.
(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)
(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).
- 145(0x91) is stored at size(0x602008)
(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.
(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'.
(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.
(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.
(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.
- Depending on the chunk size, the values of fd, bk, fd_nextsize, and bk_nextsize are stored in the 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.
#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.
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)
(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".
(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.
(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.
(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.
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) */
/* 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.
#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).
- The function uses SMALLBIN_WIDTH to determine whether the system is 32-bit or 64-bit.
#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.
/* 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
#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.
/* 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.
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.
- The first bit indicates if the arena has fastbin(fastchunk).
#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)
/* 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).
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.
/* 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.
/* 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.
#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.
#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.
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.
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.
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.
#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.
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.
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.
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].
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].
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.
#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.
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.
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)
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.
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
- Wolfram Gloger's http://www.malloc.de/en/index.html
- Doug Lea http://gee.cs.oswego.edu/dl/html/malloc.html
- https://sourceware.org/glibc/wiki/MallocInternals
- https://sourceware.org/git/?p=glibc.git;a=blob;f=malloc/malloc.c;h=5cbdaef86376039256c6fc8490e501f97c31c95e;hb=refs/heads/release/2.25/master
- https://stackoverflow.com/questions/20863330/how-where-is-sbrk-used-within-malloc-c
- https://www.blackhat.com/presentations/bh-usa-07/Ferguson/Whitepaper/bh-usa-07-ferguson-WP.pdf
- https://sensepost.com/blog/2017/painless-intro-to-the-linux-userland-heap/
Excuse the ads! We need some help to keep our site up.