From thoughts to text

I read this article via Hacker News, where Senthilnathan explains why, if you want to allocate 13 bytes, it allocates more behind the scenes.

He writes that what you end up with, after running malloc, is this:

+----------------+
|     Header     |
+----------------+
|    Variable    |
|    padding     |
+----------------+
|  Back pointer  |
+----------------+
|  User memory   |  <- Pointer returned by malloc
+----------------+

But this, I have to point out, is his own implementation, which he shows in the article. Glibc uses a different implementation. I wrote a memory allocator back in 2014 which used yet a different layout.

In short; Senthil creates a header (basically the size of request), a variable padding (which is not properly explained), and a back pointer that points back to the header.

So when the memory is freed, free() can take the pointer (user memory), go one step back and use the back pointer to find the pointer to the original header that contains the size of the block, including the size of the padding, and free it properly.

Regarding the variable padding, Senthil write: “it needs to hand back a pointer that’s correctly aligned for whatever type the caller is about to store there.” and “depending on what alignment was requested.”

However, malloc doesn’t know the type that the caller is planning to store. It takes one argument, and that is the number of bytes requested. It does not ask for alignment.

Luckily he links to the code in Github, and it seems he has made his own allocator that does take alignment as an argument, which means that this is not an implementation of malloc at all.

My 2014 implementation of malloc

I made a memory allocator back in 2014 as part of a course.

The course went into topics such as CPU cache lines, memory allocation, and how to create payloads in machine code that could be used in buffer overflow attacks. Fun stuff.

My memory structure looked like this:

+----------------+
|  sizeAndTags   |
|   (header)     |
+----------------+
|      next      | <- Pointer returned by malloc
+----------------+
|      prev      |  next, prev and the boundary tag
+----------------+    is only used once the memory
|    space and   |          block is freed
|     padding    |
|       ...      |
+----------------+
|  boundary tag  |
|   (footer)     |
+----------------+

struct BlockInfo {
  size_t sizeAndTags;
  struct BlockInfo* next;
  struct BlockInfo* prev;
};

So with a request for n bytes, if the request is less than MIN_BLOCK_SIZE (BlockInfo + footer), I allocate MIN_BLOCK_SIZE, otherwise I make sure to round the request up to correct ALIGNMENT.

#define WORD_SIZE sizeof(void*)
#define MIN_BLOCK_SIZE (sizeof(BlockInfo) + WORD_SIZE)
#define ALIGNMENT 8

By rounding up, I do not need the “variable padding” Senthil uses, nor the back pointer.

The memory I give out is correctly aligned, always, and it is also big enough to contain the information needed once it is inserted into the free list.

If you request 13 bytes, the allocator will hand out 16 bytes. But the caller doesn’t know this, all it knows is that it has a pointer to memory that is at least 13 bytes, as requested.

Since I used 8 as ALIGNMENT, I am free to use the lower 3 bits of sizeAndTags for, well, tags. I used “TAG_USED” (this memory is in use) and “TAG_PRECENDING_USED” (the adjacent memory preceding this one is in use).

There is also a macro, SIZE, to get the correct size by masking out the 3 lower bits of sizeAndTags.

#define SIZE(x) ((x) & ~(ALIGNMENT - 1))

The boundary tag — in use when on the free list — is the size of the block (same as sizeAndTags), so you can go backwards and find the start of the memory block.

That’s why we have the TAG_PRECEDING_USED. If this is set to 0 on a block we are freeing, we can safely assume that the preceding block in memory has a valid boundary tag that we can use.

This also means we have to update this tag if the memory adjacent is allocated from the free list.

The boundary tag is used for coalescing. Merging two free adjacent memory blocks into one bigger memory block. Senthil explains this well in his article.

I remember spending a lot of time with pen and paper visualizing the memory layout and the pointer arithmetic.

When I worked on this, the structure of the memory block itself was not the interesting part. The exercise was to make an implementation that performed well. Both in speed and in memory utilization.

When and how long to search the free list for best fit, when to split a memory block from the free list, and whether to use the head or tail end of said split.

The course supplied test cases with various memory allocations. 9 tests in total. My results, that I submitted before the deadline, ended up like this:

Random, alternating big and small allocations, many small allocations, many free operations and back to big allocations to stress test coalescing and memory fragmentation.

It turns out that memory fragmentation is a real thing, and you have to take care to minimize its impact.