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