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