I'm implementing a physical memory allocator using the buddy approach.
I'm not sure if my method is the most efficient / correct, i really doubt i understood buddy allocation.
so i'll be glad if you guys review my approach:
In general, i have an array of pointers whose size is MAX_ORDER + 1, where MAX_ORDER is the highest order
one can allocate(happens to be 10, i.e., 2^10 pages)
And this is what i do when initializing available memory regions(reported by GRUB):
Code: Select all
foreach (base_address, size) in available regions:
size = page_align(size) // page == 4096
order = log2(size / page_size)
vmm_address = map_to_vmm(base_address, size)
store_buddy_information(vmm_address)
add_to_list(order, base_address)
unmap_from_vmm(vmm_address, size)
allocating will be like:
Code: Select all
alloc(order):
if not_empty(buddy_lists[order]):
address = pop_element_from_list(buddy_lists[order]) // This will update the new list head and return the old HEAD's address
return address
order++
// Order's list is empty, we need to divide..
while order < MAX_ORDER - 1:
if not_empty(buddy_lists[order]):
address = pop_element_from_list(buddy_lists[order])
vmm_address = map_to_vmm(address, 2^order * PAGE_SIZE)
first_buddy = vmm_address
second_buddy = vmm_address + 2^order * PAGE_SIZE / 2
add_to_list(order - 1, physical_address(second_buddy))
return physical_address(first_buddy)
Not sure if this is clear enough.. this is highly pseudo.
