tl;dr

I implemented malloc in C. it was pretty fun. Here is the repo.

What is Malloc?

Those of you familiar with C will surely have heard of and used malloc before, but for those who haven’t: malloc is C’s standard memory allocation function. Memory is a tricky thing in C. Created before the days of dynamic typing and seamless memory allocation, C is not a language for the faint of heart. Initializing a variable wrong, allocating the wrong amount of memory, pointing to the wrong segment of memory, or something as simple as passing an integer instead of a pointer to an integer to a function could lead you down a rabbit hole from whence some never return. Aside from that, C is pretty cool. It is a vast and powerful language, and most importantly it makes you feel like a real hackerman instead of some phony who only codes in convenient languages.

Implementation

To implement malloc, I made use of a data structure called a free list (you can read more about it here. It is a very nifty data structure that helps a ton when you’re dynamically allocating memory. The memory allocator uses a page structure to assign memory, meaning that it assigns memory in fixed-sized chunks called pages. Why fixed-size nodes? I hear you say. Well, not using fixed-sized chunks can lead to a lot of wasted space in memory and fragmentation. Why? Because allocating chunks of dynamic sizes might mean that we end up with odd-sized spaces between the chunks that don’t fit anything. Thus, we waste memory. By allocating memory in fixed sized chunks, we ensure that there is no space between chunks that ends up wasted. Sure, we might have to allocate more memory than needed in some cases. Say, for example, that a process requests 300 bytes of memory, but our chunks are 200 bytes. This would mean we would have to give the process 400 bytes of memory, since we only have 200-byte sized chunks. Turns out this is still better than letting our memory fragment, because we waste less space in the long run and don’t have to spend resources on rearraging memory.

Closing Thoughts

I highly recommend implementing malloc to anyone trying to further their understanding of how operating systems allocate memory and how C’s memory manipulation works. You will get your hands dirty with a lot of pointer manipulation and fun referencing and derefencing stuff, but it’s not too bad once you get it down. So, yeah. Cool little project that helped me understand memory better and also made me way more comfortable playing around with C. Link to the repo for this project.