1 /*-
2 * Copyright (c) 2023, Netflix, Inc.
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7 #include "stand.h"
8 #include "seg.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 free(segs);
24 segs = malloc(sizeof(*segs) * segalloc);
25 if (segs == NULL)
26 panic("not enough memory to get memory map\n");
27 }
28
29 /*
30 * Make sure at least n items can be accessed in the segs array. Note the
31 * realloc here will invalidate cached pointers (potentially), so addresses
32 * into the segs array must be recomputed after this call.
33 */
34 void
need_avail(int n)35 need_avail(int n)
36 {
37 if (n <= segalloc)
38 return;
39
40 while (n > segalloc)
41 segalloc *= 2;
42 segs = realloc(segs, segalloc * sizeof(*segs));
43 if (segs == NULL)
44 panic("not enough memory to get memory map\n");
45 }
46
47 /*
48 * Always called for a new range, so always just append a range,
49 * unless it's continuous with the prior range.
50 */
51 void
add_avail(uint64_t start,uint64_t end,uint64_t type)52 add_avail(uint64_t start, uint64_t end, uint64_t type)
53 {
54 /*
55 * This range is contiguous with the previous range, and is
56 * the same type: we can collapse the two.
57 */
58 if (nr_seg >= 1 &&
59 segs[nr_seg - 1].end + 1 == start &&
60 segs[nr_seg - 1].type == type) {
61 segs[nr_seg - 1].end = end;
62 return;
63 }
64
65 /*
66 * Otherwise we need to add a new range at the end, but don't need to
67 * adjust the current end.
68 */
69 need_avail(nr_seg + 1);
70 segs[nr_seg].start = start;
71 segs[nr_seg].end = end;
72 segs[nr_seg].type = type;
73 nr_seg++;
74 }
75
76 /*
77 * All or part of a prior entry needs to be modified. Given the structure of the
78 * code, we know that it will always be modifying the last time and/or extending
79 * the one before it if its contiguous.
80 */
81 void
remove_avail(uint64_t start,uint64_t end,uint64_t type)82 remove_avail(uint64_t start, uint64_t end, uint64_t type)
83 {
84 struct memory_segments *s;
85
86 /*
87 * simple case: we are extending a previously removed item.
88 */
89 if (nr_seg >= 2) {
90 s = &segs[nr_seg - 2];
91 if (s->end + 1 == start &&
92 s->type == type) {
93 s->end = end;
94 /* Now adjust the ending element */
95 s++;
96 if (s->end == end) {
97 /* we've used up the 'free' space */
98 nr_seg--;
99 return;
100 }
101 /* Otherwise adjust the 'free' space */
102 s->start = end + 1;
103 return;
104 }
105 }
106
107 /*
108 * OK, we have four cases:
109 * (1) The new chunk is at the start of the free space, but didn't catch the above
110 * folding for whatever reason (different type, start of space). In this case,
111 * we allocate 1 additional item. The current end is copied to the new end. The
112 * current end is set to <start, end, type> and the new end's start is set to end + 1.
113 * (2) The new chunk is in the middle of the free space. In this case we allocate 2
114 * additional items. We copy the current end to the new end, set the new end's start
115 * to end + 1, the old end's end to start - 1 and the new item is <start, end, type>
116 * (3) The new chunk is at the end of the current end. In this case we allocate 1 more
117 * and adjust the current end's end to start - 1 and set the new end to <start, end, type>.
118 * (4) The new chunk is exactly the current end, except for type. In this case, we just adjust
119 * the type.
120 * We can assume we always have at least one chunk since that's created with new_avail() above
121 * necessarily before we are called to subset it.
122 */
123 s = &segs[nr_seg - 1];
124 if (s->start == start) {
125 if (s->end == end) { /* (4) */
126 s->type = type;
127 return;
128 }
129 /* chunk at start of old chunk -> (1) */
130 need_avail(nr_seg + 1);
131 s = &segs[nr_seg - 1]; /* Realloc may change pointers */
132 s[1] = s[0];
133 s->start = start;
134 s->end = end;
135 s->type = type;
136 s[1].start = end + 1;
137 nr_seg++;
138 return;
139 }
140 if (s->end == end) { /* At end of old chunk (3) */
141 need_avail(nr_seg + 1);
142 s = &segs[nr_seg - 1]; /* Realloc may change pointers */
143 s[1] = s[0];
144 s->end = start - 1;
145 s[1].start = start;
146 s[1].type = type;
147 nr_seg++;
148 return;
149 }
150 /* In the middle, need to split things up (2) */
151 need_avail(nr_seg + 2);
152 s = &segs[nr_seg - 1]; /* Realloc may change pointers */
153 s[2] = s[1] = s[0];
154 s->end = start - 1;
155 s[1].start = start;
156 s[1].end = end;
157 s[1].type = type;
158 s[2].start = end + 1;
159 nr_seg += 2;
160 }
161
162 void
print_avail(void)163 print_avail(void)
164 {
165 printf("Found %d RAM segments:\n", nr_seg);
166
167 for (int i = 0; i < nr_seg; i++) {
168 printf("%#jx-%#jx type %lu\n",
169 (uintmax_t)segs[i].start,
170 (uintmax_t)segs[i].end,
171 (u_long)segs[i].type);
172 }
173 }
174
175 uint64_t
first_avail(uint64_t align,uint64_t min_size,uint64_t memtype)176 first_avail(uint64_t align, uint64_t min_size, uint64_t memtype)
177 {
178 uint64_t s, len;
179
180 for (int i = 0; i < nr_seg; i++) {
181 if (segs[i].type != memtype) /* Not candidate */
182 continue;
183 s = roundup(segs[i].start, align);
184 if (s >= segs[i].end) /* roundup past end */
185 continue;
186 len = segs[i].end - s + 1;
187 if (len >= min_size) {
188 printf("Found a big enough hole at in seg %d at %#jx (%#jx-%#jx)\n",
189 i,
190 (uintmax_t)s,
191 (uintmax_t)segs[i].start,
192 (uintmax_t)segs[i].end);
193 return (s);
194 }
195 }
196
197 return (0);
198 }
199
200 enum types {
201 system_ram = SYSTEM_RAM,
202 firmware_reserved,
203 linux_code,
204 linux_data,
205 linux_bss,
206 unknown,
207 };
208
209 static struct kv
210 {
211 uint64_t type;
212 char * name;
213 int flags;
214 #define KV_KEEPER 1
215 } str2type_kv[] = {
216 { linux_code, "Kernel code", KV_KEEPER },
217 { linux_data, "Kernel data", KV_KEEPER },
218 { linux_bss, "Kernel bss", KV_KEEPER },
219 { firmware_reserved, "Reserved" },
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