1#include <log.h>
2#include <mem/address_range.h>
3#include <mem/page.h>
4#include <string.h>
5
6LOG_SITE_DECLARE_DEFAULT(address_range);
7LOG_HANDLE_DECLARE_DEFAULT(address_range);
8
9#define ar_log(lvl, fmt, ...) \
10 log(LOG_SITE(address_range), LOG_HANDLE(address_range), lvl, fmt, \
11 ##__VA_ARGS__)
12
13#define ar_err(fmt, ...) ar_log(LOG_ERROR, fmt, ##__VA_ARGS__)
14#define ar_warn(fmt, ...) ar_log(LOG_WARN, fmt, ##__VA_ARGS__)
15#define ar_info(fmt, ...) ar_log(LOG_INFO, fmt, ##__VA_ARGS__)
16#define ar_debug(fmt, ...) ar_log(LOG_DEBUG, fmt, ##__VA_ARGS__)
17#define ar_trace(fmt, ...) ar_log(LOG_TRACE, fmt, ##__VA_ARGS__)
18
19static struct rbt ar_tree;
20
21static void print_bytes(uint64_t bytes) {
22 const uint64_t kib = 1024ULL;
23 const uint64_t mib = 1024ULL * kib;
24 const uint64_t gib = 1024ULL * mib;
25 const uint64_t tib = 1024ULL * gib;
26 const uint64_t pib = 1024ULL * tib;
27 const uint64_t eib = 1024ULL * pib;
28
29 if (bytes == 0) {
30 printf(format: "0 bytes\n");
31 return;
32 }
33
34 uint64_t v;
35
36 v = bytes / eib;
37 if (v)
38 printf(format: "%llu eib", v);
39 bytes %= eib;
40
41 v = bytes / pib;
42 if (v)
43 printf(format: "%llu pib", v);
44 bytes %= pib;
45
46 v = bytes / tib;
47 if (v)
48 printf(format: "%llu tib", v);
49 bytes %= tib;
50
51 v = bytes / gib;
52 if (v)
53 printf(format: "%llu gib", v);
54 bytes %= gib;
55
56 v = bytes / mib;
57 if (v)
58 printf(format: "%llu mib", v);
59 bytes %= mib;
60
61 v = bytes / kib;
62 if (v)
63 printf(format: "%llu kib", v);
64 bytes %= kib;
65
66 if (bytes) {
67 printf(format: "%llu bytes ", bytes);
68 }
69
70 printf(format: "\n");
71}
72
73static inline size_t ar_end(struct address_range *ar) {
74 return ar->base + ar->size;
75}
76
77static size_t ar_get_data(struct rbt_node *rn) {
78 return container_of(rn, struct address_range, rbt_node_internal)->base;
79}
80
81static int32_t ar_cmp(const struct rbt_node *a, const struct rbt_node *b) {
82 vaddr_t l = ar_get_data(rn: (void *) a);
83 vaddr_t r = ar_get_data(rn: (void *) b);
84 return (l > r) - (l < r);
85}
86
87static bool address_ranges_overlap(struct address_range *a,
88 struct address_range *b) {
89 return a->base < ar_end(ar: b) && b->base < ar_end(ar: a);
90}
91
92static void add_static_address_range(struct address_range *ar) {
93 struct rbt_node *prev = rbt_find_predecessor(tree: &ar_tree, data: ar->base);
94 struct rbt_node *next = rbt_find_successor(tree: &ar_tree, data: ar->base);
95
96 if (prev) {
97 struct address_range *p =
98 rbt_entry(prev, struct address_range, rbt_node_internal);
99
100 if (address_ranges_overlap(a: p, b: ar))
101 panic("Address range '%s' overlaps '%s'", ar->name, p->name);
102 }
103
104 if (next) {
105 struct address_range *n =
106 rbt_entry(next, struct address_range, rbt_node_internal);
107
108 if (address_ranges_overlap(a: ar, b: n))
109 panic("Address range '%s' overlaps '%s'", ar->name, n->name);
110 }
111
112 rbt_insert(tree: &ar_tree, new_node: &ar->rbt_node_internal);
113}
114
115static bool gap_fits(vaddr_t need_align, size_t need_size, vaddr_t gap_base,
116 vaddr_t gap_end, vaddr_t *out_base) {
117 vaddr_t aligned = ALIGN_UP(gap_base, need_align);
118 vaddr_t end = aligned + need_size;
119 if (aligned < gap_end && end <= gap_end) {
120 *out_base = aligned;
121 return true;
122 }
123 return false;
124}
125
126static void add_dynamic_address_range(struct address_range *ar) {
127 kassert(ar->base == 0);
128 vaddr_t need_align = ar->align;
129 size_t need_size = ar->size;
130
131 struct rbt_node *node = rbt_min(tree: &ar_tree);
132 vaddr_t gap_base = ADDRESS_RANGE_KERNEL_START;
133
134 while (node) {
135 struct address_range *gap_ar =
136 rbt_entry(node, struct address_range, rbt_node_internal);
137
138 vaddr_t chosen;
139 if (gap_fits(need_align, need_size, gap_base, gap_end: gap_ar->base, out_base: &chosen)) {
140 ar->base = chosen;
141 rbt_insert(tree: &ar_tree, new_node: &ar->rbt_node_internal);
142 return;
143 }
144
145 gap_base = ar_end(ar: gap_ar);
146 node = rbt_next(node);
147 }
148
149 vaddr_t chosen;
150 if (gap_fits(need_align, need_size, gap_base, ADDRESS_RANGE_KERNEL_END,
151 out_base: &chosen)) {
152 ar->base = chosen;
153 rbt_insert(tree: &ar_tree, new_node: &ar->rbt_node_internal);
154 return;
155 }
156
157 panic("No suitable gap for dynamic address range");
158}
159
160/* The idea behind this is as follows:
161 *
162 * We have a linker section full of struct address_range. For each
163 * of these, we either
164 *
165 * 1. Add it to the address range tree, if it already has a base and size.
166 * a. Validate that it doesn't cross over any existing range
167 *
168 * 2. Find a spot to allocate it, and provide it with that base and size
169 */
170void address_ranges_init() {
171 rbt_init(t: &ar_tree, get_data: ar_get_data, compare: ar_cmp);
172
173 for (struct address_range *ar = __skernel_address_ranges;
174 ar < __ekernel_address_ranges; ar++) {
175 if (!(ar->flags & ADDRESS_RANGE_DYNAMIC))
176 add_static_address_range(ar);
177 }
178
179 for (struct address_range *ar = __skernel_address_ranges;
180 ar < __ekernel_address_ranges; ar++) {
181 if (ar->flags & ADDRESS_RANGE_DYNAMIC)
182 add_dynamic_address_range(ar);
183 }
184
185 address_ranges_print();
186}
187
188static void format_size(char *buf, size_t bufsz, size_t bytes) {
189 if (bytes >= (1ULL << 30)) {
190 size_t whole = bytes >> 30;
191 size_t frac = ((bytes & ((1ULL << 30) - 1)) * 100) >> 30;
192 if (frac == 0) {
193 snprintf(buffer: buf, buffer_len: bufsz, format: "%zu GiB", whole);
194 } else {
195 snprintf(buffer: buf, buffer_len: bufsz, format: "%zu.%02zu GiB", whole, frac);
196 }
197 } else if (bytes >= (1ULL << 20)) {
198 size_t whole = bytes >> 20;
199 size_t frac = ((bytes & ((1ULL << 20) - 1)) * 100) >> 20;
200 if (frac == 0) {
201 snprintf(buffer: buf, buffer_len: bufsz, format: "%zu MiB", whole);
202 } else {
203 snprintf(buffer: buf, buffer_len: bufsz, format: "%zu.%02zu MiB", whole, frac);
204 }
205 } else if (bytes >= (1ULL << 10)) {
206 size_t whole = bytes >> 10;
207 size_t frac = ((bytes & ((1ULL << 10) - 1)) * 100) >> 10;
208 if (frac == 0) {
209 snprintf(buffer: buf, buffer_len: bufsz, format: "%zu KiB", whole);
210 } else {
211 snprintf(buffer: buf, buffer_len: bufsz, format: "%zu.%02zu KiB", whole, frac);
212 }
213 } else {
214 snprintf(buffer: buf, buffer_len: bufsz, format: "%zu B", bytes);
215 }
216}
217
218#define AR_COL_ADDR 18
219#define AR_LINE "─────────────────────────"
220#define AR_SEP_TOP "0x%llx ┬───┬─────────────────────────"
221#define AR_SEP_BOTTOM "0x%llx ┴───┴─────────────────────────"
222
223static void ar_print_gap(vaddr_t gap_size, vaddr_t end) {
224 char gapbuf[32];
225 format_size(buf: gapbuf, bufsz: sizeof(gapbuf), bytes: gap_size);
226 printf(format: "0x%016llx ┼───┼" AR_LINE "\n", end);
227 printf(format: " │ O │\n");
228 printf(format: " │ O │ gap: %-13s\n", gapbuf);
229 printf(format: " │ O │\n");
230}
231
232void address_ranges_print() {
233 size_t count = __ekernel_address_ranges - __skernel_address_ranges;
234 ar_info("%zu address ranges:", count);
235
236 struct address_range *ranges[count];
237 size_t i = 0;
238 struct rbt_node *rn;
239 rbt_for_each(rn, &ar_tree) {
240 ranges[i++] = container_of(rn, struct address_range, rbt_node_internal);
241 }
242
243 for (size_t a = 0; a < i; a++) {
244 for (size_t b = a + 1; b < i; b++) {
245 if (ranges[b]->base > ranges[a]->base) {
246 struct address_range *tmp = ranges[a];
247 ranges[a] = ranges[b];
248 ranges[b] = tmp;
249 }
250 }
251 }
252
253 printf(format: "\n");
254 printf(format: "%-*s %s\n", AR_COL_ADDR, " address", "region");
255
256 if (i > 0) {
257 vaddr_t top_end = ranges[0]->base + ranges[0]->size;
258 if ((vaddr_t) ADDRESS_RANGE_KERNEL_END > top_end)
259 ar_print_gap(gap_size: (vaddr_t) ADDRESS_RANGE_KERNEL_END - top_end,
260 ADDRESS_RANGE_KERNEL_END);
261 }
262
263 for (size_t k = 0; k < i; k++) {
264 struct address_range *ar = ranges[k];
265 vaddr_t end = ar->base + ar->size;
266 char szbuf[32];
267 format_size(buf: szbuf, bufsz: sizeof(szbuf), bytes: ar->size);
268
269 size_t name_len = strlen(str: ar->name);
270
271 printf(format: "0x%016llx ┼───┼" AR_LINE "\n", end);
272 printf(format: "%-*s │ X │ %s: %-*s\n", AR_COL_ADDR, "", ar->name,
273 AR_COL_ADDR - name_len - 2, szbuf);
274
275 if (k + 1 < i) {
276 vaddr_t next_end = ranges[k + 1]->base + ranges[k + 1]->size;
277 if (ar->base > next_end)
278 ar_print_gap(gap_size: ar->base - next_end, end: ar->base);
279 }
280 }
281
282 if (i > 0) {
283 vaddr_t bot_base = ranges[i - 1]->base;
284 if (bot_base > (vaddr_t) ADDRESS_RANGE_KERNEL_START)
285 ar_print_gap(gap_size: bot_base - (vaddr_t) ADDRESS_RANGE_KERNEL_START,
286 end: bot_base);
287 }
288
289 printf(AR_SEP_BOTTOM "\n\n", ADDRESS_RANGE_KERNEL_START);
290}
291
292struct address_range *address_range_for_addr(vaddr_t vaddr) {
293 for (struct address_range *ar = __skernel_address_ranges;
294 ar < __ekernel_address_ranges; ar++) {
295 if (vaddr >= ar->base && vaddr <= ar_end(ar))
296 return ar;
297 }
298
299 return NULL;
300}
301