Introduction
One of the most important functions of an operating system is managing the memory. Some of the memory will be reserved for the operating system while the remaining memory will be rationed out to processes. Our memory management system should therefore keep track of every memory location and whether or not it is free. To keep things easy, we'll allocate memory in 4k pages which will play in nicely with the MMU when we need to deal with that later for virtual memory management.
Detecting memory
Unless you're using GRUB2, detecting memory isn't completely straightforward. Luckily, some smart individuals over at OSDev built an assembly function to help us detect memory and populate it into a static memory address. That link is over at https://wiki.osdev.org/Detecting_Memory_(x86)#Getting_an_E820_Memory_Map
If you're using GRUB2, life is a lot easier: https://wiki.osdev.org/Detecting_Memory_(x86)#Memory_Map_Via_GRUB
Populating the memory map
The above function populates a memory map at memory address 0x8004 and the size of the map at memory address 0x8000 as a 32bit integer. As the memory map is simply an array, we can map it in C with the following code. Note that I'm using a packed attribute to avoid C padding out the struct and misreading the data.
/* Number of regions in for the memory map table */
uint32_t* map_regions_count;
/* Represents an entry in the memory map table */
/* We still grab the high even though we're only a 32 bit system */
struct memory_map_entry_t {
uint32_t base_address_low;
uint32_t base_address_high;
uint32_t region_length_low;
uint32_t region_length_high;
uint32_t region_type;
uint32_t acpi_attribs;
} __attribute__((packed));
struct memory_map_entry_t* map_entry;
map_regions_count = (uint32_t*) 0x8000;
map_entry = (struct memory_map_entry_t*) 0x8004;
Figuring out which section to use
For my physical memory management, I want to grab the biggest section of continuous free memory I can to use for physically memory allocation. I'll then save the address and size so I can split them up into pages later. It's not the most robust method, but it's simple and it works.
/*
* We're grabbing the largest region of memory for memory operations
*/
main_memory_start = 0x00;
main_memory_length = 0x00;
#ifdef DEBUG_MSG_MEMORYMAP
printf("Base Address | Region Length | Type\n");
#endif
int i;
for(i=0; i < *map_regions_count; ++i)
{
/* Region 1 is free and we want to grab the largest region we can */
if(map_entry->region_type == 1
&& map_entry->region_length_low > main_memory_length)
{
main_memory_start = (uint32_t*)map_entry->base_address_low;
main_memory_length = map_entry->region_length_low;
}
printf("%x | %x | %d\n",
map_entry->base_address_low,
map_entry->region_length_low,
map_entry->region_type
);
/* Do some weird pointer stuff to get the next entry */
map_entry = (struct memory_map_entry_t*) ( BIOS_MEMORY_MAP_LOC + 0x18 * i );
}
Now that I have the block of memory I want to use, I'll immediately need to set aside space for our physical memory manager. This area will be used to track which blocks have been allocated and which blocks are free. Note that I automatically align everything to the 4k block size by dropping the last few bits. Again, this is to make life easier when I start implementing virtual memory.
#define PHYS_BLOCK_SIZE 4096
/* Immediately allocate storage for our physical memory manager */
mem_mgr_reserved_size = (main_memory_length / PHYS_BLOCK_SIZE);
/* Start of actual allocation is aligned by PHYS_BLOCK_SIZE bytes. Also add a bit of a buffer. */
uint32_t start_addr_alloc = (uint32_t)main_memory_start;
start_addr_alloc += mem_mgr_reserved_size + PHYS_BLOCK_SIZE;
start_addr_alloc &= ~(PHYS_BLOCK_SIZE - 1);
alloc_start = (uint32_t*)start_addr_alloc;
/* Print our memory info */
printf("Memory Start: %x, Memory Length: %x, Allocatable Start: %x, Number of blocks: %d \n",
main_memory_start, main_memory_length, alloc_start, mem_mgr_reserved_size);
printf("Memory: %d MB\n", main_memory_length / 1024 / 1024);
The physical memory manager layout
The beginning part of the memory is used to track the allocated and free blocks later on. A super simple diagram of the layout can be found below after calling the function alloc() twice.
Alloc and Free functions
There are plenty of excellent and efficient algorithms out there to deal with physical memory, but I'm going to take the easy method of simply running through the array and looking for a free entry. If we end back where we started without a hit, we know we've ran out of memory. Performance of this algorithm is O(n) which is fine for now since we don't plan on alloc and free-ing memory often.
/* Helper function to grab ptr from record */
uint32_t* entry_to_pmem(uint32_t entry)
{
if(entry > mem_mgr_reserved_size)
panic("entry_to_pmem: entry out of bounds!");
uint32_t working_ptr = PHYS_BLOCK_SIZE * entry;
working_ptr += (uint32_t) alloc_start;
return (uint32_t*) working_ptr;
}
uint32_t* pmem_alloc()
{
uint32_t record = curr_alloc_record;
++curr_alloc_record;
if(curr_alloc_record >= mem_mgr_reserved_size)
curr_alloc_record = 0;
/* If we loop all the way around, we're out of memory */
while(record != curr_alloc_record)
{
uint8_t* record_ptr = (uint8_t*)main_memory_start + record;
/* Allocate free page if available */
if(*record_ptr == 0x00)
{
*record_ptr = 0x1;
uint32_t* pmem_addr = entry_to_pmem(record);
#ifdef DEBUG_MSG_PMEM
printf("pmem: allocating record %d at record addr %x which points to %x\n", record, record_ptr, pmem_addr);
#endif
return pmem_addr;
}
/* Otherwise, incremement our records */
++curr_alloc_record;
if(curr_alloc_record >= mem_mgr_reserved_size)
curr_alloc_record = 0;
}
panic("out of memory!");
}
The section we reserved in the beginning simply maps a byte to a memory address. So the 1st page will map to the first byte in the reserved area, 2nd page maps to the second byte and so on. A value of 0x00 means it's free and a value of 0x01 means it's allocated. Very straightforward. Our free function is even simplier:
/* Helper function to grab record from ptr */
uint32_t pmem_to_entry(uint32_t* ptr)
{
if(alloc_start > ptr)
panic("pmem_to_entry: underflow error!");
if(main_memory_start + main_memory_length < ptr)
panic("pmem_to_entry: overflow error!");
uint32_t working_ptr = (uint32_t) ptr;
working_ptr -= (uint32_t) alloc_start;
working_ptr /= PHYS_BLOCK_SIZE;
return working_ptr;
}
int pmem_free(uint32_t* ptr)
{
uint32_t record = pmem_to_entry(ptr);
uint8_t* record_ptr = (uint8_t*)main_memory_start + record;
/* Memory is already free */
if(*record_ptr == 0x0)
return -1;
/* Mark record as free */
*record_ptr = 0x0;
#ifdef DEBUG_MSG_PMEM
printf("pmem: freeing record %d at record addr %x which points to %x\n", record, record_ptr, ptr);
#endif
return 0;
}
Testing it all
At this point, I really should be writing tests for my code. The following code runs through and allocates / frees memory constantly to make sure we don't have any weird behavior.
void pmem_tests(void)
{
/*
* Test allocations and frees
*/
printf("pmem: Testing memory allocations...");
int i = 0;
for(i = 0; i < mem_mgr_reserved_size * 2; i++)
{
uint32_t* mem_addr = pmem_alloc();
int res = pmem_free(mem_addr);
if(res != 0)
panic("error freeing memory!");
}
printf("Passed.\n");
}
And finally, a screenshot of the physical memory allocator tests in progress:
Conclusion
Thankfully, the physical memory allocator was fairly painless. The same may not be said about my next task: implementing the virtual memory allocator.