xref: /freebsd/stand/kboot/kboot/seg.c (revision 091c255b5b279fddf445a42dd7d0bad0e7c213fd)
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