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 }