Physical Page Allocator

Definition of the problem

Essentially, this comes down to a data structure problem with a twist on the restrictions on coding a kernel. I have decided to represent each page on a stack, where each page element keeps track of at least the physical and virtual addresses of a page. Optionally, a page element will most likely hold some sort of flags variable to keep track of page usage information, but this is not required for an initial implementation.

The problem involves the allocation of physical page addresses or a structure that represents a page. So, either an address pointing to a free page or a structure that contains the physical address, virtual address, flags, etc. is returned. This functionality should co-exist utilizing the same data structure.

Given:

• Start of page addressable memory (starts at the end of kernel memory)


• End of memory (address of)


• Page size (given by the architecture)


• Size of my page structure (see previous post for code)

Kernel "rules":

Not so much about rules, but behavior exhibited by working in kernel code.

1. The allocation of the page structures cannot be done on the kernel's stack due to memory/stack size constraints. Thus, the space for all of the page structures must be taken from what is available from the page allocator.
   
   Of course, this leads to a circular dependency that you need to deal with in code, but it is possible (and not too difficult). One way around this is to simply pop the top n pages from the stack, where n is the number of pages required to store all of the page structures.
   
   A side effect of this circular dependency is that the physical page allocator cannot utilize kernel memory allocation routines due to the possibility of the page table scheme not completely initialized when it is used. This would require paging to be enabled!

Implementation Details

API:
    void init_page_table(unsigned long pt_start, int num_pages, unsigned long pt_size);
    page_t *pop_page();
    void push_page(page_t *page);
    unsigned long *alloc_page();
    int dealloc_page(unsigned long *page);

pop_page() and push_page() deal with page_t structures, while alloc_page() and dealloc_page() deal only with the physical address of a page. The distinction is subtle, but important to understand because their implementation reflects how the page table stack is modified.

To achieve the manipulation of both page_t structures or physical addresses, and to use them in any order without corrupting the stack I decided to use a doubly-linked list implementation of a stack. However, this stack is not normal because I don't have access to any memory management facilities (remember, I am still in the midst of setting everything up for memory management). A doubly-linked implementation would also ensure that the stack would not need to be used in any sort of order (i.e. pushing/popping along with allocation/de-allocation in the same logical order).

It is important to note that de-allocation or popping of a page does not actually free any memory to the system. It only gives the illusion that the page is no longer in the page table, but in fact the total page table stack needs to persist in kernel memory for the life of the kernel. Additionally, one cannot traverse this list at any given moment and find out what all the pages are being used for. Not all pages are guaranteed to be represented in this page table, but the space for all pages needs to exist.

pop_page() returns an entire page element, not just its physical page address, so it is similar to just removing that element from the list, which can be simulated by updating the next and prev pointers.

By removing elements you will effectively remove the ability to de-allocate a physical page address to a page structure that is currently in use, which acts as a protection mechanism since allocating an address on a page that has been popped off would be bad.

Allocating a physical address removes the address from the element (setting its value to 0, which is not a possible real value for a physical or virtual address), but the page structure stays linked on the beginning of the list. The head pointer is moved to the next available element, but an empty structure remains on the heads prev pointer. This will allow de-allocation of a pointer by following head's prev pointer to an empty and unused page structure so its physical address can be re-initialized by whatever address was passed in by the dealloc_page() function.

All four functions execute in constant time. However, the page struct will require two pointers for a doubly-linked list. This is expensive, but it allows me to work around any O(n) searches on push_page() or dealloc_page() functions.

The mixing of pop_page() and alloc_page() in any order will work well with this implementation.

Almost enabled paging... or so I thought

I added functions to my physical page allocator to allow the allocation and de-allocation of physical memory addresses, rather than just a page_t struct. This has introduced a new problem for de-allocation: de-allocation (adding a physical page back to the stack allocator) will require a search of the stack to find an open page_t struct. This causes time complexity is O(n). I could get around this by implementing a doubly-linked stack. Not sure how I will handle this.

However, I am having some problems right now enabling paging. All I need to do is set the cr0 and cr3 accordingly, but writing cr0 causes a crash.

I'm not sure what I am doing wrong. Make sure to check that the page directory is page-aligned (should add code to check for this all the time). A simple re-read of the Intel documentation along with the tutorials on osdev should fix this issue.

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.

First Post!

Never had a blog before, and I can say right away that this is *not* going to be a "What I had for breakfast" blog, it will have no info on who I am, etc.

This blog will be an online record of the steps I take (that I have been taking) in my experience of writing an OS kernel, along with everything/anything that I think is related to this.

I will use this blog as my virtual "notes" area, of which everyone will (obviously) be able to view. Info on this will most likely be added at irregular intervals; whenever I get something accomplished or when I am questioning certain design issues.