Hey there! This blog post will introduce you to the dynamic memory management performed by the ptmalloc2 algorithm, which is the implementation of malloc/realloc/free adapted to multiple threads/arenas by Wolfram Gloger, taking as basis the implementation of Doug Lea (previous dlmalloc algorithm). Note that we are focusing on the malloc implementation of UNIX-based systems (therefore, if you want to compile the examples provided here you need a UNIX-based system!). A detailed explanation of the ptmalloc2 algorithm can be read here.
Chunks
We call the memory requested by malloc as chunk. In fact, a chunk is a region of contiguous memory which may be returned by malloc() or has been passed to free(), considering the overhead.
A chunk is represented by the malloc_chunk structure, which is defined in 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;
};When the user asks for dynamic memory through the malloc() system call, it returns the pointer of the third field of the struct, instead of returning the pointer to the malloc_chunk structure.
We can watch this very easily with the following example code:
// gcc example1.c -o example1 -m32
#include <stdlib.h>
#include <stdio.h>
/* CODE TAKEN FROM malloc.c in glibc source code */
#define INTERNAL_SIZE_T size_t
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size;
INTERNAL_SIZE_T mchunk_size;
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
typedef struct malloc_chunk* mchunkptr;
#define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
/* END CODE COPIED */
void print_chunk(struct malloc_chunk* ptr){
if(ptr != NULL){
printf("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n");
printf("ptr: %p (user ptr: %p)\n", ptr, chunk2mem(ptr));
printf("chunk sizes: %d, %d\n", ptr -> mchunk_prev_size, ptr -> mchunk_size);
printf("chunk fd, bk: %p, %p\n", ptr -> fd, ptr -> bk);
printf("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n");
}else{
printf("ERROR: print_chunk: ptr is null\n");
}
}
int main(){
char *ptr;
int size = 16;
printf("[+] sizeof(size_t)=%lu\n", sizeof(size_t));
printf("[*] Allocating %d bytes ... \n", size);
ptr = (char *) malloc(size);
printf("[*] The address of ptr is %p\n", ptr);
print_chunk(mem2chunk(ptr));
return 0;
}Chunk size bits
Note that the macros chuck2mem and mem2chunk perform the pointer arithmetic needed to access to the chunk/user memory pointer. These macros are also contained in the malloc.c source code.
See that the code first allocates 16 bytes, then prints the value of the pointer returned by malloc(), and finally prints the values of the malloc_chunk structure.
We can now compile it and see its output (for the sake of simplicity, we have compiled it in 32 bits. You will likely obtain different memory addresses, don’t worry – they will even change during each program execution!):
$ gcc example1.c -o example1 -m32
$ ./example1
[+] sizeof(size_t)=4
[*] Allocating 16 bytes ...
[*] The address of ptr is 0x5826b5b0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x5826b5a8 (user ptr: 0x5826b5b0)
chunk sizes: 0, 33
chunk fd, bk: (nil), (nil)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+This output already tells us important stuff. Note that we have the pointer 0x5826b5b0 returned by malloc, and the chunk really starts 8 bytes earlier (at 0x5826b5a8). See also that the size is in fact 33 bytes, rather than just 16 bytes as we would have expected. In fact, this is not totally true, as the last three bits are used for bookkeeping. The last three bits of the mchunk_size field are the bits A | M | P, where the A bit means NON_MAIN_ARENA, M means IS_MMAPPED and P means PREV_INUSE.
The A bit is cleared for chunks on the initial, main arena. An arena is an internal malloc’s structure, shared among one or more threads, which contains references to one or more heaps, as well as linked lists of chunks within those heaps which are “free” (we will tell this soon). The allocation of memory performed by the threads assigned to each arena allocates memory from that arena’s free lists.
The M bit is set for chunks obtained through mmap(). These chunks are neither in an arena, not adjacent to a free chunk.
The P bit is 0 when the previous chunk (the one directly before it in memory, not the previous one in the linked list) is free (and then the previous field contains its size). The very first chunk allocated has this bit set. If this bit is 1, then we cannot determine the size of the previous chunk.
Now we can make a little improvement in our previous code to obtain the appropriate size of a memory chunk. Just add these lines to example1.c (also copied from the original malloc.c source code):
#define PREV_INUSE 0x1
#define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE)
#define IS_MMAPPED 0x2
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)
#define NON_MAIN_ARENA 0x4
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))
#define chunksize_nomask(p) ((p)->mchunk_size)And modify print_chunk as:
void print_chunk(struct malloc_chunk* ptr){
if(ptr != NULL){
printf("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n");
printf("ptr: %p (user ptr: %p)\n", ptr, chunk2mem(ptr));
printf("chunk sizes: %d, %d\n", ptr -> mchunk_prev_size, chunksize(ptr));
printf("chunk bits: A=%d, M=%d, P=%d\n", chunk_main_arena(ptr), chunk_is_mmapped(ptr), prev_inuse(ptr));
printf("chunk fd, bk: %p, %p\n", ptr -> fd, ptr -> bk);
printf("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n");
}else{
printf("ERROR: print_chunk: ptr is null\n");
}
}If we compile and execute it again:
$ gcc example1.c -o example1 -m32
$ ./example1
[+] sizeof(size_t)=4
[*] Allocating 16 bytes ...
[*] The address of ptr is 0x5738d5b0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x5738d5a8 (user ptr: 0x5738d5b0)
chunk sizes: 0, 32
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Hell yeah! Now the things are a pretty more clear. Let’s explain something else which is very relevant indeed. There are two types of chunks, allocated and free chunks.
Types of chunks
An allocated chunk looks like this (taken from the original malloc.c source code):
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|M|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_size() bytes) .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (size of chunk, but used for application data) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+When an allocated chunk is freed, it is stored in circular double-link lists. The lists are commonly referred to as bins. We will talk about them a little later on. A free chunk looks like this (taken also from the original malloc.c source code):
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |A|0|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Note that an allocated chunk contains the usable size for the user plus the overhead. Note also that the forward and back pointers to next chunk in list will contain user data in the case of an allocated chunk. In any event, to access to the nextchunk data in an allocated/free chunk, we need to consider the current size of a chunk.
We can define a couple of macros to navigate through previous/next chunks now as:
/* Ptr to next physical malloc_chunk. */
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))
/* Ptr to previous physical malloc_chunk. Only valid if !prev_inuse (P). */
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))
/* Size of the chunk below P. Only valid if !prev_inuse (P). */
#define prev_size(p) ((p)->mchunk_prev_size)And then modify print_chunk as follows:
void print_chunk(struct malloc_chunk* ptr){
if(ptr != NULL){
printf("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n");
printf("ptr: %p (user ptr: %p)\n", ptr, chunk2mem(ptr));
printf("chunk sizes: %d, %d\n", ptr -> mchunk_prev_size, chunksize(ptr));
printf("chunk bits: A=%d, M=%d, P=%d\n", chunk_main_arena(ptr), chunk_is_mmapped(ptr), prev_inuse(ptr));
printf("chunk fd, bk: %p, %p\n", ptr -> fd, ptr -> bk);
ptr = next_chunk(ptr);
printf("next chunk [%p] sizes (fd, bk): 0x%08x, 0x%08x\n", ptr, chunksize(ptr), prev_size(ptr));
if(!prev_inuse(ptr)){ // checks P to get previous chunk (only valid if P is cleared)
ptr = prev_chunk(ptr);
printf("prev chunk [%p] sizes (fd, bk): 0x%08x, 0x%08x\n", ptr, chunksize(ptr), prev_size(ptr));
}
printf("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\n");
}else{
printf("ERROR: print_chunk: ptr is null\n");
}
}If we compile and execute it now, we obtain an output similar to:
$ gcc example1.c -o example1 -m32
$ ./example1
[+] sizeof(size_t)=4
[*] Allocating 16 bytes ...
[*] The address of ptr is 0x580e55b0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x580e55a8 (user ptr: 0x580e55b0)
chunk sizes: 0, 32
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x580e55c8] sizes (fd, bk): 0x00021a38, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Well, let’s analyze this output now. The difference of 8 bytes between the user pointer address and the chunk pointer address is motivated by the two INTERNAL_SIZE_T fields prior the user pointer address, which are in fact 4 bytes long. Last, but not least, it is telling us that the next chunk is located at 0x580e55c8 and its size is equal to 0x00021a38. Don’t worry now about the meaning of this size, you will understand it later.
What kind of black magic is this? Well, it is nothing to be worried about. Let’s modify the main body of our example to allocate two more chunks of 8 bytes and print the chunks:
int main(){
char *ptr;
int size = 16;
printf("[+] sizeof(size_t)=%lu\n", sizeof(size_t));
printf("[*] Allocating %d bytes ... \n", size);
ptr = (char *) malloc(size);
printf("[*] The address of ptr is %p\n", ptr);
print_chunk(mem2chunk(ptr));
size = 8;
ptr = (char *) malloc(size);
printf("[*] The address of ptr of malloc(%d) is %p\n", size, ptr);
print_chunk(mem2chunk(ptr));
ptr = (char *) malloc(size);
printf("[*] The address of ptr of malloc(%d) is %p\n", size, ptr);
print_chunk(mem2chunk(ptr));
return 0;
}Now the output will be similar to:
$ gcc example1.c -o example1 -m32
$ ./example1
[+] sizeof(size_t)=4
[*] Allocating 16 bytes ...
[*] The address of ptr is 0x57fde5b0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x57fde5a8 (user ptr: 0x57fde5b0)
chunk sizes: 0, 32
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x57fde5c8] sizes (fd, bk): 0x00021a38, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] The address of ptr of malloc(8) is 0x57fde5d0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x57fde5c8 (user ptr: 0x57fde5d0)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x57fde5d8] sizes (fd, bk): 0x00021a28, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] The address of ptr of malloc(8) is 0x57fde5e0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x57fde5d8 (user ptr: 0x57fde5e0)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x57fde5e8] sizes (fd, bk): 0x00021a18, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Note that the subsequent allocated chunks begin in the address indicated as the next chunk when printing every chunk right after allocated it. If we make a little modification in the main body we can see how the data of the chunk structure have changed:
// replace the last three lines (prior return) of main's body with these ones
// ...
char *ptr2 = (char *) malloc(size);
printf("[*] The address of ptr of malloc(%d) is %p\n", size, ptr2);
print_chunk(mem2chunk(ptr2));
printf("[*] Printing again ptr %p ...\n", ptr);
print_chunk(mem2chunk(ptr));
// ...The new output is:
[+] sizeof(size_t)=4
[*] Allocating 16 bytes ...
[*] The address of ptr is 0x568805b0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x568805a8 (user ptr: 0x568805b0)
chunk sizes: 0, 32
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x568805c8] sizes (fd, bk): 0x00021a38, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] The address of ptr of malloc(8) is 0x568805d0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x568805c8 (user ptr: 0x568805d0)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x568805d8] sizes (fd, bk): 0x00021a28, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] The address of ptr of malloc(8) is 0x568805e0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x568805d8 (user ptr: 0x568805e0)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x568805e8] sizes (fd, bk): 0x00021a18, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Printing again ptr 0x568805d0 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x568805c8 (user ptr: 0x568805d0)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x568805d8] sizes (fd, bk): 0x00000010, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+As you see, the size of the next chunk pointed by the chunk at 0x568805c8 is 0x10, which is the expected value (the size of this chunk is 16 bytes, as you can also see in the previous output). Moreover, it is interesting also to see how the size of the next chunk is reduced after every call to malloc (we got first 0x00021a38, then 0x00021a28, and then 0x00021a18).
From allocated to free chunks
So far so good? We can now introduce the free() system call, which receives a memory pointer returned by malloc/realloc/etc. functions and “frees the allocated memory”. In this context, freeing the memory means to move from an allocated to a free chunk and to add the free chunk into a bin. Bins contain the free chunks in double-link ordered lists (but the first bin, which is the unsorted bin) and organized by chunk size. In fact, there are different types of bins: fast bins, small bins, large bins, and the unsorted bin. If you want to know more about the bins, I recommend you to read this link in detail.
Let us know prepare a new example to allocate and free a set of chunks:
int main(){
char *ptrs[4];
int size = 16;
ptrs[0] = (char *) malloc(size);
printf("[*] First malloc(%d), the address of ptr is %p\n", size, ptrs[0]);
// fill the memory with data, for illustrative purposes
for(int i = 0; i < size; i++)
ptrs[0][i] = 'A';
print_chunk(mem2chunk(ptrs[0]));
size = 8;
ptrs[1] = (char *) malloc(size);
printf("[*] Second malloc(%d), the address of ptr is %p\n", size, ptrs[1]);
print_chunk(mem2chunk(ptrs[1]));
ptrs[2] = (char *) malloc(size);
printf("[*] Third malloc(%d), the address of ptr is %p\n", size, ptrs[2]);
print_chunk(mem2chunk(ptrs[2]));
printf("[*] Freeing ptr %p ... \n", ptrs[0]);
free(ptrs[0]);
print_chunk(mem2chunk(ptrs[0]));
ptrs[0] = (char *) malloc(size);
printf("[*] Fourth malloc(%d), the address of ptr is %p\n", size, ptrs[0]);
print_chunk(mem2chunk(ptrs[0]));
size = 16;
ptrs[3] = (char *) malloc(size);
printf("[*] Fifth malloc(%d), the address of ptr is %p\n", size, ptrs[3]);
print_chunk(mem2chunk(ptrs[3]));
// Free the pointers
for(int i = 0; i < 4; i++){
printf("[*] Freeing ptr %p ... \n", ptrs[i]);
free(ptrs[i]);
}
// Printing chunk pointers
for(int i = 0; i < 4; i++){
printf("[*] Printing ptr %p ... \n", ptrs[i]);
print_chunk(mem2chunk(ptrs[i]));
}
return 0;
}As output, we will obtain something like this:
[*] First malloc(16), the address of ptr is 0x8c65008
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65000 (user ptr: 0x8c65008)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: 0x41414141, 0x41414141
next chunk [0x8c65018] sizes (fd, bk): 0x00020fe8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Second malloc(8), the address of ptr is 0x8c65020
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65018 (user ptr: 0x8c65020)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x8c65028] sizes (fd, bk): 0x00020fd8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Third malloc(8), the address of ptr is 0x8c65030
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65028 (user ptr: 0x8c65030)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x8c65038] sizes (fd, bk): 0x00020fc8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Freeing ptr 0x8c65008 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65000 (user ptr: 0x8c65008)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), 0x41414141
next chunk [0x8c65018] sizes (fd, bk): 0x00000010, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Fourth malloc(8), the address of ptr is 0x8c65040
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65038 (user ptr: 0x8c65040)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x8c65048] sizes (fd, bk): 0x00020fb8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Fifth malloc(16), the address of ptr is 0x8c65008
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65000 (user ptr: 0x8c65008)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), 0x41414141
next chunk [0x8c65018] sizes (fd, bk): 0x00000010, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Freeing ptr 0x8c65040 ...
[*] Freeing ptr 0x8c65020 ...
[*] Freeing ptr 0x8c65030 ...
[*] Freeing ptr 0x8c65008 ...
[*] Printing ptr 0x8c65040 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65038 (user ptr: 0x8c65040)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x8c65048] sizes (fd, bk): 0x00020fb8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Printing ptr 0x8c65020 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65018 (user ptr: 0x8c65020)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: 0x8c65038, (nil)
next chunk [0x8c65028] sizes (fd, bk): 0x00000010, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Printing ptr 0x8c65030 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65028 (user ptr: 0x8c65030)
chunk sizes: 0, 16
chunk bits: A=1, M=0, P=1
chunk fd, bk: 0x8c65018, (nil)
next chunk [0x8c65038] sizes (fd, bk): 0x00000010, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Printing ptr 0x8c65008 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8c65000 (user ptr: 0x8c65008)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), 0x41414141
next chunk [0x8c65018] sizes (fd, bk): 0x00000010, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Let us make a small picture on what is going on here to clarify it. Prior to the first call to free(), we have three chunks:
ptr[0]: @0x8c65000 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x18 | 101 +
user mem ->@0x8c65008 > + 0x41414141 +
+ 0x41414141 +
+ 0x41414141 +
+ 0x41414141 +
next chunk:@0x8c65018 > + 0x00020fe8 +
+ 0 +
+-+-+-+-+-+-+-+
(after the second call to malloc)
ptr[1]: @0x8c65018 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x10 | 101 +
user mem ->@0x8c65020 > + 0 +
+ 0 +
next chunk:@0x8c65028 > + 0x00020fd8 +
+ 0 +
+-+-+-+-+-+-+-+
(after the third call to malloc)
ptr[2]: @0x8c65028 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x10 | 101 +
user mem ->@0x8c65030 > + 0 +
+ 0 +
next chunk:@0x8c65038 > + 0x00020fb8 +
+ 0 +
+-+-+-+-+-+-+-+Recall that we have an overlapping between every chunk and the next chunk in the heap (see the pointer address values!). We then make a free() releasing the memory allocated in ptr[0]. Our heap now looks like:
ptr[0]: @0x8c65000 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x18 | 101 +
user mem ->@0x8c65008 > + 0x41414141 +
+ 0x41414141 +
+ 0x41414141 +
+ 0x41414141 +
next chunk:@0x8c65018 > + 0x10 +
+ 0 +
+-+-+-+-+-+-+-+
ptr[1]: @0x8c65018 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x10 | 101 +
user mem ->@0x8c65020 > + 0 +
+ 0 +
next chunk:@0x8c65028 > + 0x10 +
+ 0 +
+-+-+-+-+-+-+-+
ptr[2]: @0x8c65028 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x10 | 101 +
user mem ->@0x8c65030 > + 0 +
+ 0 +
next chunk:@0x8c65038 > + 0x00020fc8 +
+ 0 +
+-+-+-+-+-+-+-+The chunk at 0x8c65000 is now at the free chunk list, ready to be reused in case of needed. We have two more allocations, leaving our heap as:
ptr[3]: @0x8c65000 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x18 | 101 +
user mem ->@0x8c65008 > + 0 +
+ 0x41414141 +
+ 0x41414141 +
+ 0x41414141 +
next chunk:@0x8c65018 > + 0x10 +
+ 0 +
+-+-+-+-+-+-+-+
ptr[1]: @0x8c65018 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x10 | 101 +
user mem ->@0x8c65020 > + 0 +
+ 0 +
next chunk:@0x8c65028 > + 0x10 +
+ 0 +
+-+-+-+-+-+-+-+
ptr[2]: @0x8c65028 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x10 | 101 +
user mem ->@0x8c65030 > + 0 +
+ 0 +
next chunk:@0x8c65038 > + 0x10 +
+ 0 +
+-+-+-+-+-+-+-+
ptr[0]: @0x8c65038 > +-+-+-+-+-+-+-+
+ 0 +
+ 0x10 | 101 +
user mem ->@0x8c65040 > + 0 +
+ 0 +
next chunk:@0x8c65048 > + 0x00020fb8 +
+ 0 +
+-+-+-+-+-+-+-+We have used ptr[0] to store the fourth malloc. Note that a new chunk was assigned after this malloc. However, in the last malloc, as we have requested a (small) piece of memory and there is a free chunk that matches with the requested size in the bins, the previous freed chunk is reused. Note that when doing malloc(8) we did not get the free chunk, even its size is larger than 8. This is motivated because this chunk is in one of the 10 fast bins, which contains chunks with size 16, 24, 32, 40, 48, 56, 64, 72, 80 and 88.
One of the most interesting remarks here is also to notice the content of the last allocated chunk: the previous assignments of ‘A’ value to the first pointer is still there!
Accommodating user requests on-demand
And… what the heck is the value shown in the size field of the next chunk pointer of the last allocated chunk? That’s an easy one: it is the top chunk! The very first time that malloc() is invoked, we don’t have any space to give memory to the user. Therefore, a srbk() call is performed to ask to the system for memory space. Once the call is successful, this space forms the top chunk, which is divided to accommodate the user request, returning it to the user, and the reminder is set as the new top chunk.
This process is repeated every time the user requests for a new piece of memory, unless a free chunk exists (in any bin) that can fit into the user needs (this is a more complicated process, although I’m going to skip this explanation now for the sake of simplicity). When no free chunk can accommodate a user request, and the top chunk is not large enough, then a call to srbk() is performed to enlarge (and coalesce) the heap space. Once enlarged, the user request is served and the top chunk is updated appropriately.
Let’s try to provoke this effect. Consider this code:
int get_top_chunk_size(struct malloc_chunk *ptr){
ptr = next_chunk(ptr);
return chunksize(ptr);
}
int main(){
int size = 16;
char *ptr = (char *) malloc(size);
printf("[*] First malloc(%d), the address of ptr is %p\n", size, ptr);
// fill the memory with data, for illustrative purposes
for(int i = 0; i < size; i++)
ptr[i] = 'A';
print_chunk(mem2chunk(ptr));
int topchunk_value = get_top_chunk_size(mem2chunk(ptr));
printf("[*] top chunk size: %x\n", topchunk_value);
size = 1024;
char *ptr2;
for(int i = 0; i < topchunk_value; i += size){
printf("[*] Allocating %d bytes ... ", size);
ptr2 = (char *) malloc(size);
printf("ptr: %p; remaining size: %x\n", ptr2, get_top_chunk_size(mem2chunk(ptr2)));
}
print_chunk(mem2chunk(ptr2));
printf("[*] Printing again ptr %p ...\n", ptr);
print_chunk(mem2chunk(ptr));
return 0;
}And again, its execution will provide an output similar to:
[*] First malloc(16), the address of ptr is 0x8d9f008
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8d9f000 (user ptr: 0x8d9f008)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: 0x41414141, 0x41414141
next chunk [0x8d9f018] sizes (fd, bk): 0x00020fe8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] top chunk size: 20fe8
[*] Allocating 1024 bytes ... ptr: 0x8d9f020; remaining size: 20be0
[*] Allocating 1024 bytes ... ptr: 0x8d9f428; remaining size: 207d8
[*] Allocating 1024 bytes ... ptr: 0x8d9f830; remaining size: 203d0
[*] Allocating 1024 bytes ... ptr: 0x8d9fc38; remaining size: 1ffc8
[ ... redacted ... ]
[*] Allocating 1024 bytes ... ptr: 0x8dbf018; remaining size: be8
[*] Allocating 1024 bytes ... ptr: 0x8dbf420; remaining size: 7e0
[*] Allocating 1024 bytes ... ptr: 0x8dbf828; remaining size: 3d8
[*] Allocating 1024 bytes ... ptr: 0x8dbfc30; remaining size: 20fd0
[*] Allocating 1024 bytes ... ptr: 0x8dc0038; remaining size: 20bc8
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8dc0030 (user ptr: 0x8dc0038)
chunk sizes: 0, 1032
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x8dc0438] sizes (fd, bk): 0x00020bc8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Printing again ptr 0x8d9f008 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x8d9f000 (user ptr: 0x8d9f008)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: 0x41414141, 0x41414141
next chunk [0x8d9f018] sizes (fd, bk): 0x00000408, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Do you see something in this output trace? Exactly! Right almost at the end, the remaining size has increased after a new malloc(): as explained before, the heap grows to accomodate the user requests, if needed.
Mapped chunks
Finally, let us consider now the following code in which instead of small pieces we want a really big piece of the memory cake (we have done only little modifications in the main body):
// file example3.c
int main(){
int size = 16;
char *ptr = (char *) malloc(size);
printf("[*] First malloc(%d), the address of ptr is %p\n", size, ptr);
// fill the memory with data, for illustrative purposes
for(int i = 0; i < size; i++)
ptr[i] = 'A';
print_chunk(mem2chunk(ptr));
int topchunk_value = get_top_chunk_size(mem2chunk(ptr));
printf("[*] top chunk size: %x\n", topchunk_value);
size = topchunk_value + size;
printf("[*] Allocating now %d bytes ... \n", size);
char *ptr2 = (char *) malloc(size);
print_chunk(mem2chunk(ptr2));
size = 16;
ptr2 = (char *) malloc(size);
printf("[*] Allocating now %d bytes ... \n", size);
print_chunk(mem2chunk(ptr2));
return 0;
}If we compile and execute it, we obtain the following output:
$ gcc example3.c -o example3 -m32
death@debian-vm:~$ ./example2
[*] First malloc(16), the address of ptr is 0x94a9008
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x94a9000 (user ptr: 0x94a9008)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: 0x41414141, 0x41414141
next chunk [0x94a9018] sizes (fd, bk): 0x00020fe8, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] top chunk size: 20fe8
[*] Allocating now 135160 bytes ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0xf7539000 (user ptr: 0xf7539008)
chunk sizes: 0, 139264
chunk bits: A=1, M=2, P=0
chunk fd, bk: (nil), (nil)
next chunk [0xf755b000] sizes (fd, bk): 0x00000000, 0x00000040
prev chunk [0xf755afc0] sizes (fd, bk): 0x00000000, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[*] Allocating now 16 bytes ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ptr: 0x94a9018 (user ptr: 0x94a9020)
chunk sizes: 0, 24
chunk bits: A=1, M=0, P=1
chunk fd, bk: (nil), (nil)
next chunk [0x94a9030] sizes (fd, bk): 0x00020fd0, 0x00000000
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Note that in this case the large chunk is allocated in a different place! The second chunk has a size of 139264 and is mem mapped (see its status bits), unlike the third chunk which has only 24 bytes of size and is allocated in the same space than the first chunk, as you can infer by the memory addresses shown. Memory mapped chunks are neither in an arena, nor adjacent to a freed chunk, and are not part of the heap at all.
And that’s all, folks! After reading this, I hope you have a more clear concept on what is the heap and how the pieces of memory that you allocate/free in your program are handled. If you are hungry for more knowledge, I recommed you to read this link and this link. If you are more insterested in heap exploitation, you can read this link and (of course) the great Malloc Maleficarum and Malloc Des-Maleficarum.
