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
12static struct memory_segments *segs;
13static int nr_seg = 0;
14static int segalloc = 0;
15
16void
17init_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 */
33void
34need_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 */
50void
51add_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 */
80void
81remove_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
161void
162print_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
174uint64_t
175first_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
199enum types {
200	system_ram = SYSTEM_RAM,
201	firmware_reserved,
202	linux_code,
203	linux_data,
204	linux_bss,
205	unknown,
206};
207
208static 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
222static const char *
223parse_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
254static struct kv *
255kvlookup(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 */
265static void
266chop(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
277bool
278populate_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 */
341next_line:
342		if (fgetstr(buf, sizeof(buf), fd) < 0)
343			break;
344	}
345
346out:
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 */
355uint64_t
356space_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