Memory management is one of the, if not most, important parts of an OS. It needs to efficiently allocate and deallocate chunks of memory and it needs to do it now. The things to keep in mind when writing a memory allocator is to minimise the time taken to allocate or deallocate a memory block and at the same time, minimise fragmentation that may (will!) be caused after multiple cycles of allocations and deallocations.
For those who don't know, Jazz is a toy OS that I'm writing and it is in need of a memory allocator for some time now.
There are multiple open source pluggable memory allocators which are available but I wanted to write one myself. I have been able to enable paging for it, which I'm not very confident of right now, but I'm willing to move on and write a memory allocator anyway. I'll come back and fix anything if worse comes to worst.
There are multiple algorithms to choose from for the memory allocation, but to begin small, we'll choose the First Fit algorithm which is the easiest to implement using a linked list. We'll use a doubly linked list because it makes removing a node easier.
Admittedly, it's not the best algorithm to implement but it gets the job done and we can easily swap out this for something more sophisticated like Buddy Allocation later if we keep our interface clean.
The algorithm is fairly simple:
The memory allocator depends on a page allocator to be available. A page allocator should allocate a page of a fixed size which the memory allocator will break into smaller chunks.
We keep the interface similar to the unix system calls:
malloc returns a block for the given size.
free frees the block.
To keep a list of free memory, we need to create a linked list. This can easily be done by using the block itself as a node in the list. Allocating a new block is as simple as:
To find a block in the free blocks list, we create a helper function like so:
Up till now, we've created a list of free blocks, and a way to find the first free block which can fit the given size. Next, we need to implement
You would have noticed that
free does not take the size of the block. How do we know the size of the block when we want to free it?
Going with the second approach, we keep a small amount of data in the block just before the address that we return. To do this, we allocate a block of (requested size + metadata size). The metadata can store the information about the block size.
free is called with this block, it can check the metadata just before the address of the block to find the size and return the block back to the free memory list.
It's fairly straight-forward to implement these methods, so I'm leaving this up to you to try out if you want. If not, check out the implementation in Jazz.
This was the simplest algorithm that you can use to implement a memory allocator. But this algorithm lacks a few things like:
There are better algorithms to handle these shortcomings like buddy allocation. It has shortcomings of its own, but even then it performs better than first fit. This is left as an improvement for now.