In my previous post I tried to give a high level overview of how I learned everything I know about programming.
In this post I am going to dive into a specific example. The general way I have always approached things is by taking them apart and putting them back together. Along the way I bounce between theory and practice. That means I will do some research to see what other people have discovered before, learn the concepts and theories, and then I will go back to the code and figure out how to apply them. In this post we’re going to learn how to implement malloc and free.
I started using C back in the early 90s. You may have picked it up yourself at some point. I learned about the stack and the heap. When you initialize a variable in a scope it takes memory from the stack. When you want to initialize a value on the heap you need to use malloc. I had learned that the stack grows, “from the top” of the program’s memory. The heap, “grows from the bottom.”
Why is that? I had never really needed to know. Such facts were enough for all of the programs and work I’ve done. And so I decided I wanted to find out.
Use What You Know
Forgive me if I’m wrong about this but I think there’s a generation or two of folks who were brought up in an era where Google was the tool people were taught to use when they wanted to know something. If you wanted to learn how to implement malloc or how to implement a compiler you would start with a query. And then you look for the answer.
When StackOverflow began to reign supreme on the Internet, for programmers, this was often the first and final destination. Copy and paste the answer. Move on.
That’s not how I work.
Like when I was a kid, I take things apart. I try to figure out how they work by putting them back together. Fortunately for us, we’re using computers and writing code. It’s hard to break anything. My poor family had piles of broken Speak-And-Spells and radios to deal with in the wake of my quest to learn. These days I have hundreds of little snippets and unfinished programs.
For figuring out how to implement malloc let’s just take the type signature and figure out how to implement our own using what we know.
Taking Stock
So I already know that when I execute a program on my operating system it creates a process. On my Linux system that program is a binary file in the ELF format. The OS allocates a page of virtual memory, maps my program into that memory, sets up the program counter to point at the main entry point, and probably does some other bits of bookkeeping. Then things go.
I also know the type signatures of the malloc and free functions I normally use from the standard C library:
void* malloc(size_t);
void free(void*);