ArcanOS PRE-MAGUS: frame allocator rudiments

It’s been entirely too long coming, but as of ArcanOS commit e1a75edd4b0a, the rudiments of the frame allocator are available.  Those who’ve followed the project will note that the memory manager was disabled and still hasn’t come back, but this will be coming along very soon.  Really, “memory manager” was a misnomer anyway, as the real goal was to have a basic malloc( )function.  Being able to summon up a pointer to an arbitrary chunk of memory could be considered “handy” for early development.  So, the original allocator is what I’ve been calling a “scratch pad allocator.”  Basically, it just assumes there’s a spare megabyte of RAM located just beyond the kernel’s load location and it uses this area for serving memory requests.  This actually was a pretty neat thing to have on hand in the early days of ArcanOS, before we were using paging and when it was more important to me to have a robust kernel debug log than it was to do anything else.  Of course, this had to be retired when ArcanOS switched over to paging, because the 1MB “scratch pad” shouldn’t be assumed to be mapped in.  No…the malloc( )function should necessarily rely on the paging system.

There are some distinct phases to go through in making a mechanism for allocating out the available RAM:

  1. Identify the physical addresses of all the RAM in system.
  2. Create a tracking system to know what RAM is free and which is used.
  3. Create a mechanism for mapping unused RAM into the address space of the process requesting it.

Step (1) was nicely done for us already by GRUB and the map is passed in as part of the multiboot info struct when GRUB dispatches to the kernel’s entry point.  To know where all the free RAM is in the system, you need only parse the struct.  Of course, to make use of the information in the struct, it’s handy to also tackle step (2), so that you have somewhere to record this information about available memory.  Since I think it’s probably the most minimal data structure possible (and, therefore, the easiest to read, learn, and explain…and thus in line with a goal of ArcanOS), I have opted for the ever-humble bitmap.  ArcanOS has an intentional design decision to target a very generic 32-bit x86 architecture and thus limits its address space to 4GB.  This is broken down into page-size chunks and each one gets a bit in the bitmap.  A 1 in the bitmap denotes free RAM, otherwise it should not be touched.

I set up the bitmap in memmgr.c in multiple passes.  In the first pass, I set the bitmap so that all the page frames are invalidated:

void frame_allocator_init(multiboot_info_t* mbi, uint32_t kernel_base, uint32_t kernel_end) {
	int i;
	int frames_allocated = 0;
	for(i=0; i<(PHYS_MEM_MAP_SIZE); i++) {
		phys_mem_map[i] = 0;

Next, I iterate through the memory map given by GRUB and mark all the full and available 4KB frames as being available:

   multiboot_memory_map_t* mmap;
   for (mmap = (multiboot_memory_map_t *) (mbi->mmap_addr);
		(unsigned long) mmap < (mbi->mmap_addr) + mbi->mmap_length;
		mmap = (multiboot_memory_map_t *) ((unsigned long) mmap
								 + mmap->size + sizeof (mmap->size)))
	 //_kern_print(" size = 0x%x, base_addr = 0x%x%x,"
		//	 " length = 0x%x%x, type = 0x%x\n",
			// (unsigned) mmap->size,
		//	 mmap->addr_high,
	//		 mmap->addr_low,
		//	 mmap->len_high,
	//		 mmap->len_low,
		//	 (unsigned) mmap->type);
	if (mmap->type == MULTIBOOT_MEMORY_AVAILABLE) {
		 //Kindly note here that we will *NOT* be making use of the "high"
		 //fields here.  The memory manager is current capped at 4GB, so
		 //we will deal only with the lower 32-bits of addresses.
		 //The goal here is to flip on the bits for available RAM.  After
		 //that, we will flip OFF the bits for the areas where the kernel
		 //was loaded and where the initial page tables sit.
		 //The frame allocator is very happy to fail to mark partial
		 //frames as "not available."  This is a good, safe starting point
		 //as it means that the only physical memory allocated out will
		 //"really be there."
		 uint32_t base = mmap->addr_low;
		 uint32_t len = mmap->len_low;
	     //First, advance up to the next page frame boundary.
		 if ((base % PAGE_SIZE) != 0) {
			 base = base + (PAGE_SIZE - (base % PAGE_SIZE));
			 len = len - (PAGE_SIZE - (base % PAGE_SIZE));
	     //As long as there is another frame to allocate, allocate it.
		 while (!(len<PAGE_SIZE)) {
			 mark_frame(base, FRAME_STATUS_FREE);
			 base += PAGE_SIZE;
			 len -= PAGE_SIZE;

And then finally I make sure that the space taken up by the kernel and the initial page directory and page tables is marked as unavailable.  This is important to remember to do…the space you’ve used before turning on your memory manager is, by definition, not available to use.  Otherwise, you’ll accidentally write over your page tables and other stuff you’ve so laboriously set up:

   //Now, time to make sure the page directory and any existing page
   //tables are never again re-allocated.
   uint32_t* page_entry = (uint32_t*)INITIAL_PDE;
   for (i=0; i<1024; i++) {
		uint32_t pde_entry = page_entry[i];
		pde_entry &= 0xFFFFF000; //Page table address is in the upper 20 bits
		if (pde_entry != 0) {
			_kern_print("Located existing page at 0x%x and will mark it as used\n", pde_entry);
			mark_frame(pde_entry, FRAME_STATUS_USED);
   //Finally, mark off the area where the kernel is loaded
   kernel_base &= 0xFFFFF000; //Find the nearest page (rounding down)
   while(kernel_base < kernel_end) {
	   mark_frame(kernel_base, FRAME_STATUS_USED);
	   kernel_base += PAGE_SIZE;

And, presto.  It’s a bitmap of memory.  The process of feeding free frames of memory back into the allocator is now a process of finding a 1 in the bitmap, calculating its physical address, and then updating the page directory and tables appropriately.  When I write that code, I’ll break it down on here.  I want to add that there are some obvious drawbacks to the use of a bitmap in this fashion.  The first is that the bitmap is going to be pretty sparse, meaning that space is dedicating to bits that will never actually be used.  The bitmap is also very minimal in what it can do– it’s a map of available RAM, but if a frame is marked as 0, there’s no way to tell why.  I also suspect that the process of returning frames to available RAM is not going to be as simple as it could be, and I further suspect that requesting large data extents (such as 4KB for making a new page table) may not go in a perfectly optimal fashion.  All of these, however, are hits I’m willing to take in exchange for the fact that it’s a simple, easy to code, and easy to explain data structure.  This shows how to take the information in a GRUB multiboot info struct and use it to build a map of the available page frames in memory, and being able to show this in a single blog post isn’t so bad.

So, the next step is to get the allocator allocating, which is to say the next step is to take frames out of the bitmap and map their physical addresses to available addresses in the kernel’s address space.