High Level Understanding Of Malloc

Memory Layout Of A Process

Before diving into what Malloc is, it’s important to paint the picture of how your program, or any process executing on your machine (for most standard operating systems), is laid out in memory. As seen in the graphic above, the memory layout consists of four main parts. The Text and Data represent the executable machine instructions and initialized global and static variables respectively. Unlike the Stack and Heap, these portions do not expand at runtime. The Stack and Heap represent portions of the memory layout that are far more complicated than the Text and Data portions. The Stack is used to establish variables’ lifetimes. Meaning, any local variables, function parameters, return addresses, etc. are placed into stack frames and help a process establish their lifetime within a program. Alternatively, the Heap represents dynamically allocated memory within a program, meaning memory that can outlast a single stack frame.

What The Hell is Virtual Memory?

Surprisingly, virtual memory is not your elders getting scammed into downloading RAM off of a shady website. Instead, virtual memory has to do with the concept of virtualization. In operating systems virtualization is how an operating system provides the illusion of isolation for processes when interacting with hardware. More specifically, have you ever wondered how your computer is able to keep open 15 Chrome tabs, Discord, and Zoom? Well, ignoring multicore CPUs, this has to do with virtualizing your CPU! Virtualizing your CPU means that despite only having one CPU, your operating system provides the illusion that each process has “its own CPU”. With that being said, your operating system does a similar process with your RAM. Your RAM has one physical address space, however your operating system translates this physical address space into a contiguous virtual address space, or virtual memory for each process.

So What Is Malloc Then…

Malloc, and its corresponding function free, are simply C functions that abstract virtual memory management from the programmer. For example, if you call malloc with a certain amount of bytes, you do not have to worry about whether your current heap size is of size to accommodate that request, as malloc handles that for you. Additionally, when you ultimately (hopefully) free this pointer, malloc will free this block of memory and mark it as reusable, allowing you to reuse heap memory you previously allocated.

Diving Into The Mechanics Of Malloc (Basic Implementation)

Initially Calling Malloc

The first time you call Malloc, your heap will be of a predetermined size by your operating system. So, if your memory request exceeds this initial amount malloc will call sbrk. Sbrk is a system call that will expand the upper bound of your heap memory. If this system call is successful, then Malloc will return a void pointer to you at the start of a heap address of the size of your request.

So What About When You Free This Memory?

When you call free on this memory pointer, I remember thinking how does free know how long the passed-in pointer is? There is no easy, inherent way to know the size of a block of data given only a pointer, so Malloc and Free work together by utilizing Malloc headers and the free list.

What Is This Malloc Header And Free List You Are Talking About?

Jumping back to when you initially call malloc, there is a sneaky step I originally left out and is unbeknownst to an unsuspecting user. When Malloc hands you a void pointer to your memory, the memory immediately preceding your void pointer is a Malloc header. As shown in the graphic above, the Malloc header includes important information, such as the size of the preceding block of memory, overwrite protection checks, and helps map out your virtual address space. This allows free to “jump back” in memory the size of the malloc header and read important metadata.

So, now that you understand what a malloc header is and how it helps map out the virtual address space, what is a free list? Well, when you free that block of memory, that malloc header is placed as a node in a linked list (at least in this simple implementation) in ascending order based on the virtual memory address they point to. This allows the free list to coalesce blocks. Meaning, if there are free blocks adjacent in memory to one another these merge to form a large block, preventing fragmentation of memory. These free blocks are then utilized by malloc in future calls as potential addresses of memory that can be used. If the size of the request can fit within a free node on a free list, that memory is used and potentially split based on the size of the request.

What I Learned From Implementing This

Amongst the core concepts of CS I learned from this, what I particularly was taken aback by was just how much is truly abstracted from programmers. The OS truly provides these “sandboxes” your processes/programs live in in which you do not have to worry about much. Even further, I primarily code in Python as an MLE.. which takes care of heap allocation and garbage collection for you. The true abstraction that occurs in these languages and operating systems is very impressive and hides a lot of knowledge from you. However, while languages like Python abstract these things from you, knowing how these processes work under the hood is still very helpful. This knowledge can help you write more performant code, in addition to understanding errors and “weird” occurrences in your code that you would otherwise be blind to.

If you are interested in seeing my implementation of malloc, please see here.

https://github.com/AndrewJMart/A-lloc