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