Low-level Memory Manager

I have finished what I think is a pretty good version of a low-level memory manager that deals with the physical memory. I chose the option of storing all physical pages in a page table that starts at the end of the kernel memory address space [1]. This method favors speed at the cost of space (i.e. my page allocater is fast 0(1), but it required an instance of the struct page_t below for *each* physical page on the system).

The amount of memory this page table takes up is proportional to the amount of memory that exists within the computer. The page_t struct below takes up 16 bytes of memory just for a page table entry. Assuming you figured out how many physical pages exist in your OS for allocation, take the number of pages multiplied by the sizeof the page_t struct. So, if you have a total of 7424 pages, and the page_t struct is a total of 16 bytes, then 7424 * 16 = 118,832 bytes (or 29.012 pages). Thus, the page table itself requires 30 pages to be allocated from the physical page allocator.

Now, the question is how the heck do you allocate pages from an allocator when you are still in the midst of writing the page allocator? The answer is: you don't! All you really need is the base address of where the page table needs to start. You should already know how large memory is (from your bootloader), and you will then know how many pages you have (total memory / PAGE_SIZE, where PAGE_SIZE = 4096 on most 32-machines). From this, you can perform some elegant pointer arithmetic to increment to the next element of your page table. See the articles linked below for good info on these issues.

typedef struct page_t {
    struct page_t *next;
    unsigned long phys_addr;
    unsigned long virt_addr;
    unsigned long flags;
} page_t;

Above is the struct that I use to represent my page table. One thing to realize that embedded within my page struct is a reference to the next item in the page table stack. This is an implementation detail that I did to get fast access to the next page along with adding pages back to the memory manager (pop() and push() respectively). It took me several re-writes to get something useful where allocation and deallocation wasn't O(n), and this is what I came up with. Essentially, my page_t is a low-level stack; the functions that manipulate the page table behave just like the functionality of a stack.

Next is using the physical page table that I have with the hardware MMU. This should be fun, no doubt.

Two great articles I found on this topic are:
http://osdev.berlios.de/memory1.html
http://osdev.berlios.de/memory2.html

[1] It was particularly difficult for me to find the *correct* memory location that my kernel ends. I was marking the end of kernel memory through a linker script, but there was actually some stuff in memory beyond that address. I only noticed this when I examined the memory map output of where things are actuall stored in my kernel (-Map option available by GNU ld). It turns out I was over-writing kernel read-only data in the initialization of my early physical memory manager, which of course lead to immediate kernel halts! I'm still working on a good way to do this, as the info I am getting from the linker script seems to be wrong. More on this later I'm sure.