1#include <console/printf.h>
2#include <math/align.h>
3#include <mem/alloc.h>
4#include <mem/bitmap.h>
5#include <mem/buddy.h>
6#include <mem/hhdm.h>
7#include <mem/pmm.h>
8#include <stdbool.h>
9#include <stdint.h>
10#include <string.h>
11
12#include "internal.h"
13
14static bool pfn_usable_from_memmap(uint64_t pfn) {
15 uint64_t addr = pfn * PAGE_SIZE;
16
17 for (uint64_t i = 0; i < memmap->entry_count; i++) {
18 struct limine_memmap_entry *entry = memmap->entries[i];
19 if (entry->type != LIMINE_MEMMAP_USABLE)
20 continue;
21
22 uint64_t start = ALIGN_DOWN(entry->base, PAGE_SIZE);
23 uint64_t end = ALIGN_UP(entry->base + entry->length, PAGE_SIZE);
24
25 if (addr >= start && addr < end)
26 return true;
27 }
28
29 return false;
30}
31
32static bool is_block_free(uint64_t pfn, uint64_t order) {
33 uint64_t pages = 1ULL << order;
34
35 for (uint64_t i = 0; i < pages; i++) {
36 uint64_t cur_pfn = pfn + i;
37 if (cur_pfn < BOOT_BITMAP_SIZE * 8) {
38 if (test_bit(index: cur_pfn))
39 return false;
40 } else {
41 if (!pfn_usable_from_memmap(pfn: cur_pfn))
42 return false;
43 }
44 }
45
46 return true;
47}
48
49static inline int order_base_2(uint64_t x) {
50 return 64 - __builtin_clzll(x) - 1;
51}
52
53void buddy_add_entry(struct page *page_array, struct limine_memmap_entry *entry,
54 struct buddy_free_area *farea) {
55 if (entry->type != LIMINE_MEMMAP_USABLE)
56 return;
57
58 uint64_t start = ALIGN_UP(entry->base, PAGE_SIZE);
59 uint64_t end = ALIGN_DOWN(entry->base + entry->length, PAGE_SIZE);
60 if (start >= end)
61 return;
62
63 uint64_t region_start = start / PAGE_SIZE;
64 uint64_t region_size = (end - start) / PAGE_SIZE;
65
66 while (region_size > 0) {
67 int order = MIN(order_base_2(region_size), BUDDY_MAX_ORDER - 1);
68 size_t block_size = 1ULL << order;
69
70 while ((region_start & (block_size - 1)) != 0 && order > 0) {
71 order--;
72 block_size = 1ULL << order;
73 }
74
75 if (block_size > region_size)
76 block_size = region_size;
77
78 if (is_block_free(pfn: region_start, order)) {
79 struct buddy_page *page = buddy_page_for_pfn(pfn: region_start);
80
81 buddy_page_tag(page);
82 buddy_page_set_order(bp: page, order);
83 buddy_page_set_free(bp: page, true);
84 buddy_page_set_next_pfn(bp: page, pfn: 0);
85
86 buddy_add_to_free_area(page, area: &farea[order]);
87 }
88
89 region_start += block_size;
90 region_size -= block_size;
91 }
92}
93
94static void mid_init_buddy(size_t pages_needed) {
95 bool found = false;
96
97 for (uint64_t i = 0; i < memmap->entry_count && !found; i++) {
98 struct limine_memmap_entry *entry = memmap->entries[i];
99 if (entry->type != LIMINE_MEMMAP_USABLE)
100 continue;
101
102 uint64_t start = ALIGN_UP(entry->base, PAGE_SIZE);
103 uint64_t end = ALIGN_DOWN(entry->base + entry->length, PAGE_SIZE);
104 uint64_t run_len = end > start ? (end - start) / PAGE_SIZE : 0;
105
106 if (run_len >= pages_needed) {
107 global.page_array = hhdm_paddr_to_ptr(p: start);
108 memset(global.page_array, 0, pages_needed * PAGE_SIZE);
109
110 for (uint64_t j = 0; j < pages_needed; j++)
111 set_bit((start / PAGE_SIZE) + j);
112
113 entry->base = start + pages_needed * PAGE_SIZE;
114 entry->length = end - entry->base;
115
116 found = true;
117 break;
118 }
119 }
120
121 if (!global.page_array)
122 panic("Failed to allocate buddy metadata");
123}
124
125void buddy_init(void) {
126 size_t pages_needed =
127 (sizeof(struct page) * global.last_pfn + PAGE_SIZE - 1) / PAGE_SIZE;
128
129 mid_init_buddy(pages_needed);
130
131 for (int i = 0; i < BUDDY_MAX_ORDER; i++) {
132 global.buddy_free_area[i].head = NULL;
133 global.buddy_free_area[i].tail = NULL;
134 global.buddy_free_area[i].nr_free = 0;
135 }
136
137 for (uint64_t i = 0; i < memmap->entry_count; i++)
138 buddy_add_entry(page_array: global.page_array, entry: memmap->entries[i],
139 farea: global.buddy_free_area);
140}
141