1 /*-
2 * Copyright (c) 2023, Netflix, Inc.
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7 #include "stand.h"
8 #include "kboot.h"
9
10 #include <sys/param.h>
11
12 static struct memory_segments *segs;
13 static int nr_seg = 0;
14 static int segalloc = 0;
15
16 void
init_avail(void)17 init_avail(void)
18 {
19 if (segs)
20 free(segs);
21 nr_seg = 0;
22 segalloc = 16;
23 segs = malloc(sizeof(*segs) * segalloc);
24 if (segs == NULL)
25 panic("not enough memory to get memory map\n");
26 }
27
28 /*
29 * Make sure at least n items can be accessed in the segs array. Note the
30 * realloc here will invalidate cached pointers (potentially), so addresses
31 * into the segs array must be recomputed after this call.
32 */
33 void
need_avail(int n)34 need_avail(int n)
35 {
36 if (n <= segalloc)
37 return;
38
39 while (n > segalloc)
40 segalloc *= 2;
41 segs = realloc(segs, segalloc * sizeof(*segs));
42 if (segs == NULL)
43 panic("not enough memory to get memory map\n");
44 }
45
46 /*
47 * Always called for a new range, so always just append a range,
48 * unless it's continuous with the prior range.
49 */
50 void
add_avail(uint64_t start,uint64_t end,uint64_t type)51 add_avail(uint64_t start, uint64_t end, uint64_t type)
52 {
53 /*
54 * This range is contiguous with the previous range, and is
55 * the same type: we can collapse the two.
56 */
57 if (nr_seg >= 1 &&
58 segs[nr_seg - 1].end + 1 == start &&
59 segs[nr_seg - 1].type == type) {
60 segs[nr_seg - 1].end = end;
61 return;
62 }
63
64 /*
65 * Otherwise we need to add a new range at the end, but don't need to
66 * adjust the current end.
67 */
68 need_avail(nr_seg + 1);
69 segs[nr_seg].start = start;
70 segs[nr_seg].end = end;
71 segs[nr_seg].type = type;
72 nr_seg++;
73 }
74
75 /*
76 * All or part of a prior entry needs to be modified. Given the structure of the
77 * code, we know that it will always be modifying the last time and/or extending
78 * the one before it if its contiguous.
79 */
80 void
remove_avail(uint64_t start,uint64_t end,uint64_t type)81 remove_avail(uint64_t start, uint64_t end, uint64_t type)
82 {
83 struct memory_segments *s;
84
85 /*
86 * simple case: we are extending a previously removed item.
87 */
88 if (nr_seg >= 2) {
89 s = &segs[nr_seg - 2];
90 if (s->end + 1 == start &&
91 s->type == type) {
92 s->end = end;
93 /* Now adjust the ending element */
94 s++;
95 if (s->end == end) {
96 /* we've used up the 'free' space */
97 nr_seg--;
98 return;
99 }
100 /* Otherwise adjust the 'free' space */
101 s->start = end + 1;
102 return;
103 }
104 }
105
106 /*
107 * OK, we have four cases:
108 * (1) The new chunk is at the start of the free space, but didn't catch the above
109 * folding for whatever reason (different type, start of space). In this case,
110 * we allocate 1 additional item. The current end is copied to the new end. The
111 * current end is set to <start, end, type> and the new end's start is set to end + 1.
112 * (2) The new chunk is in the middle of the free space. In this case we allocate 2
113 * additional items. We copy the current end to the new end, set the new end's start
114 * to end + 1, the old end's end to start - 1 and the new item is <start, end, type>
115 * (3) The new chunk is at the end of the current end. In this case we allocate 1 more
116 * and adjust the current end's end to start - 1 and set the new end to <start, end, type>.
117 * (4) The new chunk is exactly the current end, except for type. In this case, we just adjust
118 * the type.
119 * We can assume we always have at least one chunk since that's created with new_avail() above
120 * necessarily before we are called to subset it.
121 */
122 s = &segs[nr_seg - 1];
123 if (s->start == start) {
124 if (s->end == end) { /* (4) */
125 s->type = type;
126 return;
127 }
128 /* chunk at start of old chunk -> (1) */
129 need_avail(nr_seg + 1);
130 s = &segs[nr_seg - 1]; /* Realloc may change pointers */
131 s[1] = s[0];
132 s->start = start;
133 s->end = end;
134 s->type = type;
135 s[1].start = end + 1;
136 nr_seg++;
137 return;
138 }
139 if (s->end == end) { /* At end of old chunk (3) */
140 need_avail(nr_seg + 1);
141 s = &segs[nr_seg - 1]; /* Realloc may change pointers */
142 s[1] = s[0];
143 s->end = start - 1;
144 s[1].start = start;
145 s[1].type = type;
146 nr_seg++;
147 return;
148 }
149 /* In the middle, need to split things up (2) */
150 need_avail(nr_seg + 2);
151 s = &segs[nr_seg - 1]; /* Realloc may change pointers */
152 s[2] = s[1] = s[0];
153 s->end = start - 1;
154 s[1].start = start;
155 s[1].end = end;
156 s[1].type = type;
157 s[2].start = end + 1;
158 nr_seg += 2;
159 }
160
161 void
print_avail(void)162 print_avail(void)
163 {
164 printf("Found %d RAM segments:\n", nr_seg);
165
166 for (int i = 0; i < nr_seg; i++) {
167 printf("%#jx-%#jx type %lu\n",
168 (uintmax_t)segs[i].start,
169 (uintmax_t)segs[i].end,
170 (u_long)segs[i].type);
171 }
172 }
173
174 uint64_t
first_avail(uint64_t align,uint64_t min_size,uint64_t memtype)175 first_avail(uint64_t align, uint64_t min_size, uint64_t memtype)
176 {
177 uint64_t s, len;
178
179 for (int i = 0; i < nr_seg; i++) {
180 if (segs[i].type != memtype) /* Not candidate */
181 continue;
182 s = roundup(segs[i].start, align);
183 if (s >= segs[i].end) /* roundup past end */
184 continue;
185 len = segs[i].end - s + 1;
186 if (len >= min_size) {
187 printf("Found a big enough hole at in seg %d at %#jx (%#jx-%#jx)\n",
188 i,
189 (uintmax_t)s,
190 (uintmax_t)segs[i].start,
191 (uintmax_t)segs[i].end);
192 return (s);
193 }
194 }
195
196 return (0);
197 }
198
199 enum types {
200 system_ram = SYSTEM_RAM,
201 firmware_reserved,
202 linux_code,
203 linux_data,
204 linux_bss,
205 unknown,
206 };
207
208 static struct kv
209 {
210 uint64_t type;
211 char * name;
212 int flags;
213 #define KV_KEEPER 1
214 } str2type_kv[] = {
215 { linux_code, "Kernel code", KV_KEEPER },
216 { linux_data, "Kernel data", KV_KEEPER },
217 { linux_bss, "Kernel bss", KV_KEEPER },
218 { firmware_reserved, "reserved" },
219 { 0, NULL },
220 };
221
222 static const char *
parse_line(const char * line,uint64_t * startp,uint64_t * endp)223 parse_line(const char *line, uint64_t *startp, uint64_t *endp)
224 {
225 const char *walker;
226 char *next;
227 uint64_t start, end;
228
229 /*
230 * Each line is a range followed by a description of the form:
231 * <hex-number><dash><hex-number><space><colon><space><string>
232 * Bail if we have any parsing errors.
233 */
234 walker = line;
235 start = strtoull(walker, &next, 16);
236 if (start == ULLONG_MAX || walker == next)
237 return (NULL);
238 walker = next;
239 if (*walker != '-')
240 return (NULL);
241 walker++;
242 end = strtoull(walker, &next, 16);
243 if (end == ULLONG_MAX || walker == next)
244 return (NULL);
245 walker = next;
246 /* Now eat the ' : ' in front of the string we want to return */
247 if (strncmp(walker, " : ", 3) != 0)
248 return (NULL);
249 *startp = start;
250 *endp = end;
251 return (walker + 3);
252 }
253
254 static struct kv *
kvlookup(const char * str,struct kv * kvs,size_t nkv)255 kvlookup(const char *str, struct kv *kvs, size_t nkv)
256 {
257 for (int i = 0; i < nkv; i++)
258 if (strcmp(kvs[i].name, str) == 0)
259 return (&kvs[i]);
260
261 return (NULL);
262 }
263
264 /* Trim trailing whitespace */
265 static void
chop(char * line)266 chop(char *line)
267 {
268 char *ep = line + strlen(line) - 1;
269
270 while (ep >= line && isspace(*ep))
271 *ep-- = '\0';
272 }
273
274 #define SYSTEM_RAM_STR "System RAM"
275 #define RESERVED "reserved"
276
277 bool
populate_avail_from_iomem(void)278 populate_avail_from_iomem(void)
279 {
280 int fd;
281 char buf[128];
282 const char *str;
283 uint64_t start, end;
284 struct kv *kv;
285
286 fd = open("host:/proc/iomem", O_RDONLY);
287 if (fd == -1) {
288 printf("Can't get memory map\n");
289 init_avail();
290 // Hack: 32G of RAM starting at 4G
291 add_avail(4ull << 30, 36ull << 30, system_ram);
292 return false;
293 }
294
295 if (fgetstr(buf, sizeof(buf), fd) < 0)
296 goto out; /* Nothing to do ???? */
297 init_avail();
298 chop(buf);
299 while (true) {
300 /*
301 * Look for top level items we understand. Skip anything that's
302 * a continuation, since we don't care here. If we care, we'll
303 * consume them all when we recognize that top level item.
304 */
305 if (buf[0] == ' ') /* Continuation lines? Ignore */
306 goto next_line;
307 str = parse_line(buf, &start, &end);
308 if (str == NULL) /* Malformed -> ignore */
309 goto next_line;
310 /*
311 * All we care about is System RAM
312 */
313 if (strncmp(str, SYSTEM_RAM_STR, sizeof(SYSTEM_RAM_STR) - 1) == 0)
314 add_avail(start, end, system_ram);
315 else if (strncmp(str, RESERVED, sizeof(RESERVED) - 1) == 0)
316 add_avail(start, end, firmware_reserved);
317 else
318 goto next_line; /* Ignore hardware */
319 while (fgetstr(buf, sizeof(buf), fd) >= 0 && buf[0] == ' ') {
320 chop(buf);
321 str = parse_line(buf, &start, &end);
322 if (str == NULL)
323 break;
324 kv = kvlookup(str, str2type_kv, nitems(str2type_kv));
325 if (kv == NULL) /* failsafe for new types: igonre */
326 remove_avail(start, end, unknown);
327 else if ((kv->flags & KV_KEEPER) == 0)
328 remove_avail(start, end, kv->type);
329 /* Else no need to adjust since it's a keeper */
330 }
331
332 /*
333 * if buf[0] == ' ' then we know that the fgetstr failed and we
334 * should break. Otherwise fgetstr succeeded and we have a
335 * buffer we need to examine for being a top level item.
336 */
337 if (buf[0] == ' ')
338 break;
339 chop(buf);
340 continue; /* buf has next top level line to parse */
341 next_line:
342 if (fgetstr(buf, sizeof(buf), fd) < 0)
343 break;
344 }
345
346 out:
347 close(fd);
348 return true;
349 }
350
351 /*
352 * Return the amount of space available in the segment that @start@ lives in,
353 * from @start@ to the end of the segment.
354 */
355 uint64_t
space_avail(uint64_t start)356 space_avail(uint64_t start)
357 {
358 for (int i = 0; i < nr_seg; i++) {
359 if (start >= segs[i].start && start <= segs[i].end)
360 return segs[i].end - start;
361 }
362
363 /*
364 * Properly used, we should never get here. Unsure if this should be a
365 * panic or not.
366 */
367 return 0;
368 }
369