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