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