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 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 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 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 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 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 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 * 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 * 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 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 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 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