Memory Allocation

Skip to main content

One thing that all programs on your computer have in common is a need for<br>memory. Programs need to be loaded from your hard drive into memory before they<br>can be run. While running, the majority of what programs do is load values from<br>memory, do some computation on them, and then store the result back in memory.

In this post I'm going to introduce you to the basics of memory allocation.<br>Allocators exist because it's not enough to have memory available, you need to<br>use it effectively. We will visually explore how simple allocators work. We'll<br>see some of the problems that they try to solve, and some of the techniques used<br>to solve them. At the end of this post, you should know everything you need to<br>know to write your own allocator.

malloc and free

To understand the job of a memory allocator, it's essential to understand how<br>programs request and return memory. malloc and free are functions that were<br>first introduced in a recognisable form in UNIX v7 in 1979(!). Let's take a look<br>at a short C program demonstrating their use.

Woah, hold on. I've never written any C code before. Will I still be able<br>to follow along?

If you have beginner-level familiarity with another language, e.g. JavaScript,<br>Python, or C#, you should have no problem following along. You don't need to<br>understand every word, as long as you get the overall idea. This is the only<br>C code in the article, I promise.

#include

int main() {<br>void *ptr = malloc(4);<br>free(ptr);<br>return 0;<br>In the above program we ask for 4 bytes of memory by calling malloc(4), we<br>store the value returned in a variable called ptr, then we indicate that we're<br>done with the memory by calling free(ptr).

These two functions are how almost all programs manage the memory they use.<br>Even when you're not writing C, the code that is executing your Java, Python,<br>Ruby, JavaScript, and so on make use of malloc and free.

What is memory?

The smallest unit of memory that allocators work with is called a "byte." A byte<br>can store any number between 0 and 255. You can think of memory as being a long<br>sequence of bytes. We're going to represent this sequence as a grid of squares,<br>with each square representing a byte of memory.

In the C code from before, malloc(4) allocates 4 bytes of memory. We're going<br>to represent memory that has been allocated as darker squares.

Then free(ptr) tells the allocator we're done with that memory. It is returned<br>back to the pool of available memory.

Here's what 4 malloc calls followed by 4 free calls looks like. You'll<br>notice there's now a slider. Dragging the slider to the right advances time<br>forward, and dragging it left rewinds. You can also click anywhere on the grid<br>and then use the arrow keys on your keyboard, or you can use the left and right<br>buttons. The ticks along the slider represent calls to malloc and free.

Wait a sec... What is malloc actually returning as a value?<br>What does it mean to "give" memory to a program?

What malloc returns is called a "pointer" or a "memory address." It's a number<br>that identifies a byte in memory. We typically write addresses in a form called<br>"hexadecimal." Hexadecimal numbers are written with a 0x prefix to distinguish<br>them from decimal numbers. Move the slider below to see a comparison between<br>decimal numbers and hexadecimal numbers.

0x0

Here's our familiar grid of memory. Each byte is annotated with its address in<br>hexadecimal form. For space reasons, I've omitted the 0x prefix.

The examples we use in this article pretend that your computer only has a very<br>small amount of memory, but in real life you have billions of bytes to work<br>with. Real addresses are much larger than what we're using here, but the idea is<br>exactly the same. Memory addresses are numbers that refer to a specific byte in<br>memory.

The simplest malloc

The "hello world" of malloc implementations would hand out blocks of memory by<br>keeping track of where the previous block ended and starting the next block<br>right after. Below we represent where the next block should start with a grey<br>square.

You'll notice no memory is freed. If we're only keeping track of where the<br>next block should start, and we don't know where previous blocks start or end,<br>free doesn't have enough information to do anything. So it doesn't. This is<br>called a "memory leak" because, once allocated, the memory can never be used<br>again.

Believe it or not, this isn't a completely useless implementation. For programs<br>that use a known amount of memory, this can be a very efficient strategy. It's<br>extremely fast and extremely simple. As a general-purpose memory allocator,<br>though, we can't get away with having no free implementation.

The simplest general-purpose malloc

In order to free memory, we need to keep better track of memory. We can do<br>this by saving the address and size of all allocations, and the address and size<br>of blocks of free memory. We'll call these an "allocation list" and a "free<br>list" respectively.

We're representing free...