O(1) Page Allocation, Freeing and State Checking?
Posted: Fri May 10, 2013 2:26 pm
I've recently gotten back into OSDev and have been working on my kernel's page frame allocator. Originally I was going to simply use a bitmap, but I decided pretty quickly that it seemed like a bit of a kludge. The design I've come up with is a hybrid version of a stack and bitmap. The entries are stored in memory as an array and can be indexed as such, but each entry also includes a pointer to the next entry with free pages. When an entry runs out of free pages, it's popped from the stack.
This is the allocation function, it finds the first free bit in the entry at the top of stack. Almost O(1), as I'm not sure how GCC implements __builtin_ffsll on various different architectures, though even if it's not O(1) it has a maximum number of 64 iterations on x86-64 and 32 on x86 and ARM.
To free a page, the allocator unsets the bit and if needed place the entry back onto the stack. This is O(1).
To check the state of the page, the allocator can find the correct entry by indexing the entries as an array. Again, should be O(1)
AFAICT and unless there is something I am missing this page allocator should run in constant time, with the advantages of both a stack and bitmap, while using only twice the space of the latter.
What are the pros and cons of this approach compared to other allocators?
Code: Select all
struct entry {
struct entry *next;
uintptr_t bitmap;
};
Code: Select all
page_t alloc_page(void)
{
int bit = __builtin_ffsll(~head->bitmap) - 1;
head->bitmap |= (1 << i);
struct entry *tmp = head;
if (~head->bitmap == 0) {
head = head->next;
tmp->next = NULL;
}
return ((tmp - bitmap_base) * PAGES_PER_ENTRY + bit) * PAGE_SIZE;
}
Code: Select all
void free_page(page_t page)
{
struct entry *e = &bitmap_base[(page / PAGE_SIZE) / PAGES_PER_ENTRY];
int bit = (page / PAGE_SIZE) % PAGES_PER_ENTRY;
bool was_full = (~e->bitmap == 0);
e->bitmap &= ~(1 << bit);
/* Push back onto the stack if needed */
if (e->next == NULL && was_full) {
e->next = head;
head = entry;
}
}
Code: Select all
bool test_page(page_t page)
{
struct entry *e = &bitmap_base[(page / PAGE_SIZE) / PAGES_PER_ENTRY];
int bit = (page / PAGE_SIZE) % PAGES_PER_ENTRY;
return e->bitmap & (1 << bit);
}
What are the pros and cons of this approach compared to other allocators?