ArcanOS pre-FOOL: Boot Summary and Heap Allocator

Last night, I did a push to the code repository for ArcanOS which represents the last of the work needed for its first heap allocator.  I inherited the majority of my bootloader code (please see the project website for my acknowledgements), so I decided that my first milestone for ArcanOS wouldn’t be “it boots and can run C code.”  That’s an amazing luxury, I might add.  The x86 boot process is rather arcane, as is learning how to read from a hard drive.  In short, the bootloader has to do a few things.  First, it has to set up a stack.  Then, it has to enable the A20 line so you can access some real memory.  Then, it has to set up some sort of segmentation as a prelude to switching to protected mode (so that 32-bit code can be used, among other things).  After all of that, being in 32-bit mode and armed with a stack, it can run the rest of itself in fairly standard gcc C, and you can thus more easily do the final task– loading and dispatching a bigger binary to do more meaningful work.

ArcanOS currently has no file system, so the kernel is just stuffed on the sector after the boot sector.  The kernel is an ELF binary, and the headers for ELF give the necessary information about where to load the kernel and how to jump to it.  The entry point to the kernel is actually in assembly because the first thing the kernel does is re-do memory segmentation so that the kernel loads into the higher memory addresses.  The boot loader actually loads the kernel at roughly 1MB, but the kernel is linked to be loaded at address 0xf0000000 + 1MB, so the first thing that’s done is that a new descriptor table is loaded to map all the low memory to high addresses.  This actually moves the video memory buffers up into the higher addresses as well, which is why the ArcanOS “console driver” must offset its writes by KERNBASE.

I’m going to skip over my experiences writing the “console driver” for now.  Suffice it to say, when you are implementing your own kernel, you quickly realize how little you have to work with.  I was once told that, ultimately, there are only two debugging tools — cleverness and printf( ).  I actually repeat that to rookies on my team, because, generally speaking, it’s true.  Well, guess what?  On day 1 of your kernel, you don’t have printf( ), and you have to go make one for yourself.  That starts with a functional screen console of some kind, and some bits of library code, such as itoa( ), that you’ve likely taken for granted your whole life.  So, a fairly considerable amount of time went into just getting some basic screen printing for debugging purposes.  I have no doubt that the “console driver” is, ultimately, throw-away code in favor of a far more robust console system, but necessity dictates.

The other thing I wanted to go ahead and get out of the way was a kernel heap allocator.  If there’s another function we all take for granted, it’s malloc( ).  There is no malloc( ) in your kernel if you don’t write it yourself.  This itself was an interesting journey, because the first challenge is finding a place to start the heap.  Placing the heap wrong might mean overwriting the kernel or running into memory dedicated to hardware I/O.  Fortunately, there isn’t much hardware to dodge once you’re above the 1MB offset, so the question is how to find where the kernel ends.  The way I’ve solved this is by extending the linker script called “kernel.ld”.  The PROVIDE( ) function in linker script language is particularly useful, and it lets you store information gathered in the linking process into C variables which you declare “extern”.  You can see the code which “receives” this information in kern/init.c.

What about the allocator itself?  Well, I decided that determining the amount of RAM on the target platform was a fish too big to fry right away.  RAM detection requires that I either give up my boot loader in favor of GRUB or that I add RAM detection into my boot loader before I go into protected mode (since it requires BIOS calls).  Both are non-trivial, and I also don’t plan on doing any massive allocations any time soon.  Given this, the heap just naively assumes it’s got 1MB of space in which to work.  I’ll correct this in future releases.

The allocation algorithm is incredibly simple.  The allocator will check to see if it’s got a free chunk that’s already the right size and will return that if it’s available.  Otherwise, the last member of the free list is always the “frontier” of never-before-allocated space, and it will carve off a new hunk from it.  The algorithm for freeing space it so simply move the chunk from the “allocated list” into the “free list” for future use.  There’s no provision for coalescing chunks together in the free list or anything like that, and I have some reasons for not doing this.  The first reason is because, frankly, I expect that I will rewrite this heap allocator when I have RAM detection and other goodies of this nature available to me.  The other major reason is because this allocation scheme is, in reality, enough to keep development moving along for now.  ArcanOS currently just services itself, and its allocation needs are small, and the 1MB space is likely to be plenty for a while.  Moreover, I expect most of my allocation needs will be a handful of objects of regular size.  If I were allocating lots of things of different sizes, this would eat into memory pretty badly, but if I’m just allocating structs of the same type over and over again, this system works pretty well.  Finally, a more complex algorithm means more chances for bugs…at a time when my available debugging options aren’t huge.  It’s unwise to invite extra bugs for functionality you don’t need when you expect you’re going to rewrite it anyway.

A crummy malloc( ) is, by the way, WAY better than no malloc( ) at all.

And now, armed with console out and a heap allocator, it’s time for me to attack the last feature for the FOOL milestone — writing ISRs and turning on interrupts.