stand/kboot/seg.c

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