If you are an OSDev and have trouble understanding how to implement a Memory Management Stack, you came to the right place. In this post I will try to explain how to create an interface for managing the physical memory and offer a relevant implementation.
First let’s define some state variables that will help us determine some important aspects about the physical memory.
mem_size - Size of the available memory, in KBused_blocks - Number of used blocks of size BLOCK_SIZEmax_blocks - Maximum number of used blocks of size BLOCK_SIZEpmmap - Physical Memory Map, bitmap that contains the state of each memory block (used/unused)pmmap_size - Size of bitmap (number of dwords occupied by pmmap)
This tutorial only covers a configuration where BLOCK_SIZE is 4096 bytes, aka 4KB pages. I think it may work with other configurations, but there are some adjustments to be done.
Now let’s jump into writing the routines that will handle the initialization of the Physical Memory Manager (PMM), allocate blocks and free them.
Note that in this tutorial, blocks and pages have the same meaning.
Great, our first routine will be called pmm_init and will set the state variables and the content of the bitmap.
That weird math in KB_TO_BLOCKS is done because we receive the size in KB and we must convert it in blocks. To do that we transform size in B by multiplying by 1024 and get the number of blocks by dividing by BLOCKS_SIZE. Pretty straight forward, right?
Note that BLOCKS_PER_DWORD is 32 because each bit has the responsibility to point to a block of memory. Now you may ask yourself to which block does a bit in pmmap points? Well it points to index * BLOCK_SIZE, where index is the index of the desired bit in pmmap.
As you can see, the bitmap is an array of uint32_t’s but not quite. Instead we should treat it as an array of bits, pmmap_size being the size of uint32_t’s in this array. Next I will explain the if at line 9 with the following example: suppose we have 33 blocks, if we were to consider only the division at line 8 then we would end with just only an uint32_t in pmmap_size, now that we consider that there may be some remaining bits, we end up with two uint32_t’s. The second uint32_t can now keep the 33rd bit.
In the end, we set all memory as used by default. Later we will develop a way to make available only some regions of memory.
We should also talk about the arguments this routine receives.
What is the size of the memory we initialize? If you use GRUB to load your kernel, it will provide a pointer to a multiboot_info structure that must contain the following fields: mem_lower and mem_upper. mem_lower represents the available memory that can be found in conventional memory in KB (aka first 640KB of memory) and mem_upper represents the available memory that can be found in extended memory (aka available memory starting from 1MB).
Our bitmap must map all memory starting from 0 KB up to the limit of available extended memory. Which means that size = 1024 + mem_upper (KB). 1024 KB is just 1MB. Of course that you could also skip the memory between 640KB and 1MB but then it gets a little bit more complicated.
Where does the bitmap lay in memory? The answer is: the end of the kernel. This way, it is the safer and most accessible place for the bitmap because it is a variable sized bitmap and we have no memory allocator that can do magic for us.
Ok, now we will write some routines that will initialize and deinitialize memory regions. The first important thing we must ask ourselves before starting writing them is.. why do we need them in the first place? Well, we need a way to tell which memory can be accessible for allocating and which not, this is exactly what our following routines do.
As you can see, we receive a base and a size. Using them we calculate how many blocks we need to initialize and what is the starting point of initialization. Then we start setting bits in pmmap and decrement the number of used blocks.
We must align the base because remember that we need to work with blocks of 4KB, not with random addresses. The manager only takes care of blocks, they are its “atomic” unit.
There is a reason why we set the first block as set (line 13). First this ensures that allocs cannot be 0 and that we can have a reference to NULL whenever we need it. Now that I think about it, it is set a little bit to often, it may be better to move it in pmm_init, right?
This routine operates after the same principle, there is not much to explain about pmm_deinit_region.
For me it wasn’t obvious from the first time why these routines work and I recommend you to draw some blocks on a sheet of paper and try to “init” some regions.
Also please notice that we use a bitmap interface. I will not cover it in this article, instead I will provide a link to its implementation because it is very simple to understand and to implement, trust me.
One more step
Very coool. Before we write our routines for allocating and freeing blocks of memory, we need to init and deinit some memory regions. For me, this was the most interesting part of writing a PMM.
Back again to GRUB. It will also provide some information about the mapping of memory. We will loop through each region and check if it is an available memory region, if so, init it. Here is a multiboot header file that you can check if you want to get an idea about how the structure provided by GRUB looks.
The reasons why some memory regions may be unavailable may be:
- BIOS reserved some memory for itself
- There may be memory holes
- Video RAM
Note: before calling this routine, we should make sure that there is indeed info about memory in the GRUB structure. To do that we need to check a specific bit in flags field (see the multiboot header file).
This routine is a little bit more complicated, so let’s try to explain what it does.
First, there are two symbols exported: _kernel_start and _kernel_end, they are usually exported from a linker script and we use them to compute the size of our kernel. Please note that we use their addresses because we are not in their content. Also an explicit conversion to size_t is needed because by default it will do pointer arithmetic and that is not what we want.
Next we compute the size of our bitmap that is placed at the end of the kernel. The reason we align the size of the bitmap is because we want to deinit all the pages where bitmap may be placed.
You may wonder why kernel_size is not aligned. Well I already did it in the linker script and there is no need to do that.
In the end, we use our previously written routine to deinit the kernel region and the bitmap region.
Splendid! Now let’s write the core routines of this manager: pmm_alloc_block and pmm_free_block.
See how everything is starting to make sense. To allocate a physical memory block we first check that there are still available blocks and request the first free memory block using bitmap_first_unset. Now that I think about it, the second if statement could be deleted because if the first if failed there is no way the second could fail too.
Next we mark the memory block as used and return a pointer to the actual physical memory location. It is that simple!!
Now we free allocated blocks. It is just a matter of finding the index of the memory block and marking it as available for further uses. That confusing cast from line 6 is done because our physical addresses are expressed as unsigned 32 bit integers.
As you can see, the routines rely heavily on the bitmap interface. Its operations have the following complexities:
- set/unset - O(1)
- first_unset - O(n)
That O(n) is a very bad thing because the kernel will request very often memory blocks and it will lower the performance of your system if you are developing on a slow computer.
Another solution is to implement your PMM using a stack which has better running times, but for a beginner it is better to see the bitmap implementation first, as they can move to a stack later if they are unsatisfied with the system’s performance.
Thanks for having patience to read this article and I hope you will develop a fantastic Physical Memory Manager that will fit perfectly in your Operating System. See you next time!