CS F301 Project: Writing Malloc

By Andrew Mattson | December 13th, 2022

Here's the GitHub repository for the code I wrote.

Writing Malloc..?

Ever since entering into the computer science field, one of my biggest aspirations has been to learn how memory allocation works. In October of 2022, thanks to this project, I finally got that opportunity. Up to this point, my understanding of memory allocation was "Just call malloc!" Sounds like magic, right? Just ask this function for some bytes of memory and POOF, there's a pointer to the memory you wanted! Here's the thing: My field of study is called computer science, not computer magic. Thus, if this function isn't magic, it must be science!

Beginning my endeavor, I chose my project topic: Writing malloc. Minutes prior to approaching Professor Lawlor with the idea, I contemplated scrapping everything and finding a new idea. Writing malloc sounds so complicated! Upon discussing the topic, though, and sifting through some unfamiliar terminology, I was confident that my goal achievable. Given the class, CS F301, is called "Assembly Language Programming," I planned to use NASM assembly language to complete my project. What was left to do now but write malloc! Right..?

My Dilemma, and a Change of Plans

I started my research by looking for examples of malloc written in C++. My project would be exponentially easier if I could find a nicely written malloc in a high-level programming language, that I could then rewrite in assembly. Searching around, though, I found a common issue: Everyone who has written malloc is cheating! They all use other functions to write malloc, instead of doing it from scratch! I spent days searching for a good resource, and kept running across the same functions: HeapAlloc (for Windows), other versions of malloc (kmalloc, vmalloc), mmap, and brk. What was going on?

Finally, I found this (older) resource that helped me discover my fundamental misunderstanding about memory allocation. As it turns out, memory allocation on modern systems is under nearly complete control of the operating system. Without kernel level access, writing malloc from scratch (i.e., without the help of system functions) was impossible. Keep in mind, my project topic is "Writing Malloc," not, "Writing an Operating System."

Doing some further research, I uncovered that malloc is generally implemented as a wrapper around system functions like mmap or brk. So, despite my fears that I had to write an operating system, all I truly had to do was write a friendlier wrapper around mmap or brk. Thanks to that same resource, I understood these functions enough to get started.

Writing Malloc: brk

I first chose to write malloc using brk. The system function brk works by moving what is called the program's "break," which is its defined memory limit. If we simply move this break forward by a certain number of bytes, being sure to save the original break location, we can get a new chunk of useable memory! Here's how I implemented it (exactly how I described):

Note: I chose to focus specifically on malloc, not free, so this implementation is not complete (there is no deallocation).

Writing Malloc: mmap

My other malloc implementation used the system function mmap. Mmap works by allocating memory in "pages" of data, with each page being 4096 bytes. Although it might look more complex than the brk implementation, the mmap implementation is far simpler in my opinion. The first chunk of code simply rounds the requested number of bytes to the nearest page, since mmap gives us pages. Then, we make a syscall to mmap. All of those moves are simply giving mmap the parameters it wants, such as what address we want, what permissions the memory should have, etc. Then, finally, I ensure that mmap returned a valid address, and return a zero (nullptr) if not (like malloc does).

Note: Once again, I did not implement a free, as that was not my focus for this project.

Final Thoughts

Prior to completing this project, I had absolutely no idea how memory allocation worked. All I knew was the magic of malloc that I never questioned, until now. Having now worked with brk and mmap, I believe I am fully capable of using them effectively in future programing adventures. Furthermore, I discovered how immensely complex things get in comparison to what I made when implementing free (a future endeavor?).

I still have one burning question, though... How can I write malloc, entirely from scratch? I'm talking bare-bones; nothing but some hardware, a BIOS, and maybe a very stripped operating system. At that, what would it take to write my own operating system, including a functional malloc? Now that I understand how malloc works, I have my sights set on the very thing that forced me to use mmap and brk: Operating systems.

One final note: If you have anything to say about this project, or any other questions you wish to ask, please head over to this google form! I recieve an email instantly when you complete the form, and I will get back to you ASAP.

Page updated

Google Sites

Report abuse