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