1#include <console/printf.h>
2#include <kassert.h>
3#include <math/align.h>
4#include <mem/alloc.h>
5#include <mem/bitmap.h>
6#include <mem/buddy.h>
7#include <mem/page.h>
8#include <mem/pmm.h>
9#include <stdbool.h>
10#include <stdint.h>
11#include <string.h>
12
13#include "internal.h"
14
15bool buddy_fa_empty(struct buddy_free_area *area) {
16 return area->head == NULL;
17}
18
19struct buddy_page *buddy_fa_get_head(struct buddy_free_area *area) {
20 return area->head;
21}
22
23struct buddy_page *buddy_fa_get_tail(struct buddy_free_area *area) {
24 return area->tail;
25}
26
27void buddy_fa_push_head(struct buddy_free_area *area, struct buddy_page *page) {
28 struct buddy_page *old_head = area->head;
29
30 buddy_page_set_prev(bp: page, NULL);
31 buddy_page_set_next(bp: page, next: old_head);
32
33 if (old_head)
34 buddy_page_set_prev(bp: old_head, prev: page);
35 else
36 area->tail = page;
37
38 area->head = page;
39 area->nr_free++;
40}
41
42void buddy_fa_push_tail(struct buddy_free_area *area, struct buddy_page *page) {
43 struct buddy_page *old_tail = area->tail;
44
45 buddy_page_set_next(bp: page, NULL);
46 buddy_page_set_prev(bp: page, prev: old_tail);
47
48 if (old_tail)
49 buddy_page_set_next(bp: old_tail, next: page);
50 else
51 area->head = page;
52
53 area->tail = page;
54 area->nr_free++;
55}
56
57struct buddy_page *buddy_fa_pop_head(struct buddy_free_area *area) {
58 struct buddy_page *page = area->head;
59 if (!page)
60 return NULL;
61
62 struct buddy_page *next = buddy_page_get_next(bp: page);
63 area->head = next;
64
65 if (next)
66 buddy_page_set_prev(bp: next, NULL);
67 else
68 area->tail = NULL;
69
70 buddy_page_set_next(bp: page, NULL);
71 area->nr_free--;
72 return page;
73}
74
75struct buddy_page *buddy_fa_pop_tail(struct buddy_free_area *area) {
76 struct buddy_page *page = area->tail;
77 if (!page)
78 return NULL;
79
80 struct buddy_page *prev = buddy_page_get_prev(bp: page);
81 area->tail = prev;
82
83 if (prev)
84 buddy_page_set_next(bp: prev, NULL);
85 else
86 area->head = NULL;
87
88 buddy_page_set_prev(bp: page, NULL);
89 area->nr_free--;
90 return page;
91}
92
93void buddy_fa_remove(struct buddy_free_area *area, struct buddy_page *page) {
94 struct buddy_page *prev = buddy_page_get_prev(bp: page);
95 struct buddy_page *next = buddy_page_get_next(bp: page);
96
97 if (prev)
98 buddy_page_set_next(bp: prev, next);
99 else
100 area->head = next;
101
102 if (next)
103 buddy_page_set_prev(bp: next, prev);
104 else
105 area->tail = prev;
106
107 buddy_page_set_next(bp: page, NULL);
108 buddy_page_set_prev(bp: page, NULL);
109 area->nr_free--;
110}
111
112void buddy_add_to_free_area(struct buddy_page *page,
113 struct buddy_free_area *area) {
114 buddy_page_assert_tag(page, tag: PAGE_TAG_BUDDY);
115 buddy_fa_push_tail(area, page);
116 buddy_page_set_free(bp: page, true);
117}
118
119struct buddy_page *buddy_remove_from_free_area(struct buddy_free_area *area) {
120 struct buddy_page *page = buddy_fa_pop_head(area);
121 if (!page)
122 return NULL;
123
124 buddy_page_set_free(bp: page, false);
125 return page;
126}
127
128paddr_t buddy_alloc_pages(struct buddy_free_area *free_area, size_t count) {
129 if (count == 0)
130 panic("Tried to allocate zero pages");
131
132 uint64_t order = 0, size = 1;
133 while (size < count) {
134 order++;
135 size <<= 1;
136 }
137
138 if (unlikely(order >= BUDDY_MAX_ORDER)) {
139 panic("Attempted to allocate too many pages (outside max order)");
140 return 0x0;
141 }
142
143 uint64_t current_order = order;
144 while (current_order < BUDDY_MAX_ORDER &&
145 free_area[current_order].nr_free == 0)
146 current_order++;
147
148 if (unlikely(current_order >= BUDDY_MAX_ORDER)) {
149 panic("Attempted to allocate too many pages (outside max order)");
150 return 0x0;
151 }
152
153 while (current_order > order) {
154 struct buddy_page *page =
155 buddy_remove_from_free_area(area: &free_area[current_order]);
156
157 if (!page)
158 return 0x0;
159
160 buddy_page_assert_tag(page, tag: PAGE_TAG_BUDDY);
161 uint64_t new_order = current_order - 1;
162 uint64_t buddy_pfn = buddy_page_get_pfn(bp: page) + (1ULL << new_order);
163
164 /* Send the other half away */
165 struct buddy_page *buddy = buddy_page_for_pfn(pfn: buddy_pfn);
166 buddy_page_tag(page: buddy);
167 buddy_page_set_next_pfn(bp: buddy, pfn: 0);
168 buddy_page_set_order(bp: page, order: new_order);
169 buddy_page_set_order(bp: buddy, order: new_order);
170
171 /* Put them in their new free areas */
172 buddy_add_to_free_area(page, area: &free_area[new_order]);
173 buddy_add_to_free_area(page: buddy, area: &free_area[new_order]);
174
175 current_order--;
176 }
177
178 struct buddy_page *page = buddy_remove_from_free_area(area: &free_area[order]);
179 if (!page)
180 return 0x0;
181
182 buddy_page_assert_tag(page, tag: PAGE_TAG_BUDDY);
183 buddy_page_untag(page);
184
185 return buddy_page_get_paddr(bp: page);
186}
187
188void buddy_free_pages(paddr_t addr, size_t count,
189 struct buddy_free_area *free_area, size_t total_pages) {
190 if (!addr || count == 0)
191 return;
192
193 uint64_t pfn = PAGE_TO_PFN(addr);
194 kassert(pfn < total_pages);
195
196 uint64_t order = 0, size = 1;
197 while (size < count) {
198 order++;
199 size <<= 1;
200 }
201
202 struct buddy_page *page = buddy_page_for_pfn(pfn);
203 buddy_page_assert_tag(page, tag: PAGE_TAG_NONE);
204 buddy_page_set_next_pfn(bp: page, pfn: 0);
205 buddy_page_set_order(bp: page, order);
206 buddy_page_tag(page);
207
208 while (order < BUDDY_MAX_ORDER - 1) {
209 uint64_t buddy_pfn = pfn ^ (1ULL << order);
210
211 if (buddy_pfn >= total_pages)
212 break;
213
214 struct buddy_page *buddy = buddy_page_for_pfn(pfn: buddy_pfn);
215
216 if (!buddy_page_is_free(bp: buddy) || buddy_page_get_order(bp: buddy) != order)
217 break;
218
219 buddy_page_tag(page: buddy);
220 buddy_fa_remove(area: &free_area[order], page: buddy);
221
222 pfn = (pfn < buddy_pfn) ? pfn : buddy_pfn;
223 page = buddy_page_for_pfn(pfn);
224 buddy_page_set_next_pfn(bp: page, pfn: 0);
225 buddy_page_set_order(bp: page, order: ++order);
226 buddy_page_tag(page);
227 }
228
229 buddy_add_to_free_area(page, area: &free_area[order]);
230}
231
232static struct spinlock buddy_lock = SPINLOCK_INIT;
233void buddy_free_pages_global(paddr_t addr, uint64_t count) {
234 enum irql irql = spin_lock(lock: &buddy_lock);
235 buddy_free_pages(addr, count, free_area: global.buddy_free_area, total_pages: global.last_pfn);
236 spin_unlock(lock: &buddy_lock, old: irql);
237}
238
239paddr_t buddy_alloc_pages_global(size_t count, enum alloc_flags f) {
240 (void) f;
241 enum irql irql = spin_lock(lock: &buddy_lock);
242 paddr_t ret = buddy_alloc_pages(free_area: global.buddy_free_area, count);
243 spin_unlock(lock: &buddy_lock, old: irql);
244 return ret;
245}
246