tags:
  - Cpp

Malloc in glibc (ENG)

What Does `malloc()` Do?

In simple terms, malloc() is an abstraction built on system calls like mmap() and brk(). This means you don’t need to worry about the underlying system details. This is what high-level languages have provided such conveniences for us since the 1970s.

If you are familiar with how systems allocate memory, you would know that a page (typically 4KB) is the smallest unit that an operating system can process for memory allocation. However, in C, C++, or other high-level languages, you actually can allocate as little as a single byte(in reality, this might round up to 32 bytes). Then there's must be something happened under the hood.

For those who aren’t familiar with these system calls or OS memory management, you are encouraged to learn more about mmap() and brk() from here and here. If you’re entirely new to memory management, feel free to explore my OS series, [Chapter 11](11. Memory Management).

Let's Spill The Beans

At first, let's look at how malloc is originally declared in <stdlib.h>:

#include <stdlib.h>
void* malloc(size_t size);
/*
Parameters:
    1. size: The number of bytes to allocate. This specifies the size of the process memory block to be allocated.
   
Return value: 
    - On success: Returns a pointer to the beginning of the allocated memory block. The memory is uninitialized.
    - On failure: Returns NULL, and errno is set to indicate the error.
*/

malloc accepts only one parameter, which specifies the number of bytes to allocate. If the memory chunk allocation succeeds, the function returns a pointer to the beginning of the allocated memory chunk. If the allocation fails, it returns NULL, and then errno is set.

Pretty easy, right? But this is only scratching the surface—we want to dig deeper and uncover the inner workings of malloc. In this section, we’ll use the following example to see what’s happening beneath the surface:

#include <stdio.h>
#include <stdlib.h>
struct linked_chunk{
	int chunk_value;
	struct linked_chunk* next_chunk;
};

int main(){
	struct linked_chunk *chunk1;
    printf("Size of struct linked_chunk is %ld bytes.\n", sizeof(struct linked_chunk));
	chunk1 = malloc(sizeof(struct linked_chunk));
	chunk1 -> chunk_value = 100;
	printf("The address of first chunk is: %p\n", chunk1);
	block1 -> next_block = malloc(sizeof(struct linked_block));
	printf("The address of second chunk is: %p\n", chunk1 -> next_chunk);
	chunk1 -> next_chunk -> chunk_value = 200;
	chunk1 -> next_chunk -> next_chunk = NULL;
    free(chunk1 -> next_chunk);
    free(chunk1);
	return 0;
}

Using this example, we have just allocated memory chunk with malloc. Let's analyze this with the image under below:

Outputs:

du@DVM:~/cpp$ setarch $(uname -m) -R ./proc
Size of struct linked_chunk is 16 bytes.
The address of first chunk is: 0x5555555596b0
The address of second chunk is: 0x5555555596d0

Notice anything unusual? Our structure is a 16-byte struct, yet there is a 0x10-byte gap (16 bytes) between allocations. Why is that? Because there’s metadata behind the scenes. As said, the OS only allows processes to allocate memory in multiples of the system's page size. However, with malloc metadata, your compiler does a remarkable fine-grained job for you. For example, it allocates a 32-byte memory chunk, and we are going to explore how that happens.

Use your GNU debugger, and you will uncover what’s happening in that gap at 0x5555555596c0, which is a total of 16 bytes (system-specific). Within this space, we encounter 0x21, and it is reasonable to deduce that this is where our metadata resides. So, what does 0x21 signify?

(gdb) print chunk1
$1 = (struct linked_block *) 0x5555555596b0
(gdb) x/20x 0x5555555596b0
0x5555555596b0: 0x00000064      0x00000000      0x555596d0      0x00005555
0x5555555596c0: 0x00000000      0x00000000      0x00000021      0x00000000
0x5555555596d0: 0x000000c8      0x00000000      0x00000000      0x00000000
0x5555555596e0: 0x00000000      0x00000000      0x00020921      0x00000000
0x5555555596f0: 0x00000000      0x00000000      0x00000000      0x00000000

To be straightforward, the metadata includes how many bytes are allocated and whether that memory chunk is occupied. For example, 0x20 in 0x21 denote the allocated memory size, while 0x1 indicates that this allocated memory is occupied. To free the chunk, simply set the occupied bit to 0x0, and it's all done. Quite straightforward no? (That explained why you only allocate 1 byte but actually allocated 32 bytes of memory)

Understanding that, let's now delve into how malloc manages heap memory. Using gdb, we can observe that our heap spans from 0x555555559000 to 0x55555557a000, totaling 0x21000 bytes in size.

Mapped address spaces:

Start Addr           End Addr       Size     Offset  Perms  objfile
0x555555559000     0x55555557a000  0x21000    0x0     rw-p   [heap]

0x555555559000: 0x00000000      0x00000000      0x00000291      0x00000000
0x555555559290: 0x00000000      0x00000000      0x00000411      0x00000000
0x5555555596a0: 0x00000000      0x00000000      0x00000021      0x00000000
0x5555555596c0: 0x00000000      0x00000000      0x00000021      0x00000000
0x5555555596e0: 0x00000000      0x00000000      0x00020921      0x00000000

Bit by bit, we can observe how malloc manages heap memory. In total, we have 0x21000 bytes of heap memory (0x290 + 0x410 + 0x20 + 0x20 + 0x20920 = 0x21000). Visually, it looks like this:

Also in memory mapping segment, you can find this metadata behind the dynamic allocated memory.

Malloc in glibc (ENG)

What Does malloc() Do?

Let's Spill The Beans

What Does `malloc()` Do?