com32/lib/syslinux/zonelist.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 2007-2009 H. Peter Anvin - All Rights Reserved
   4  *   Copyright 2009 Intel Corporation; author: H. Peter Anvin
   5  *
   6  *   Permission is hereby granted, free of charge, to any person
   7  *   obtaining a copy of this software and associated documentation
   8  *   files (the "Software"), to deal in the Software without
   9  *   restriction, including without limitation the rights to use,
  10  *   copy, modify, merge, publish, distribute, sublicense, and/or
  11  *   sell copies of the Software, and to permit persons to whom
  12  *   the Software is furnished to do so, subject to the following
  13  *   conditions:
  14  *
  15  *   The above copyright notice and this permission notice shall
  16  *   be included in all copies or substantial portions of the Software.
  17  *
  18  *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  20  *   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  *   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  22  *   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  23  *   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  24  *   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  25  *   OTHER DEALINGS IN THE SOFTWARE.
  26  *
  27  * ----------------------------------------------------------------------- */
  28
  29 /*
  30  * zonelist.c
  31  *
  32  * Deal with syslinux_memmap's, which are data structures designed to
  33  * hold memory maps.  A zonelist is a sorted linked list of memory
  34  * ranges, with the guarantee that no two adjacent blocks have the
  35  * same range type.  Additionally, all unspecified memory have a range
  36  * type of zero.
  37  */
  38
  39 #include <stdlib.h>
  40 #include <syslinux/align.h>
  41 #include <syslinux/movebits.h>
  42 #include <dprintf.h>
  43
  44 /*
  45  * Create an empty syslinux_memmap list.
  46  */
  47 struct syslinux_memmap *syslinux_init_memmap(void)
  48 {
  49     struct syslinux_memmap *sp, *ep;
  50
  51     sp = malloc(sizeof(*sp));
  52     if (!sp)
  53         return NULL;
  54
  55     ep = malloc(sizeof(*ep));
  56     if (!ep) {
  57         free(sp);
  58         return NULL;
  59     }
  60
  61     sp->start = 0;
  62     sp->type = SMT_UNDEFINED;
  63     sp->next = ep;
  64
  65     ep->start = 0;              /* Wrap around... */
  66     ep->type = SMT_END;         /* End of chain */
  67     ep->next = NULL;
  68
  69     return sp;
  70 }
  71
  72 /*
  73  * Add an item to a syslinux_memmap list, potentially overwriting
  74  * what is already there.
  75  */
  76 int syslinux_add_memmap(struct syslinux_memmap **list,
  77                         addr_t start, addr_t len,
  78                         enum syslinux_memmap_types type)
  79 {
  80     addr_t last;
  81     struct syslinux_memmap *mp, **mpp;
  82     struct syslinux_memmap *range;
  83     enum syslinux_memmap_types oldtype;
  84
  85     dprintf("Input memmap:\n");
  86     syslinux_dump_memmap(*list);
  87
  88     /* Remove this to make len == 0 mean all of memory */
  89     if (len == 0)
  90         return 0;
  91
  92     /* Last byte -- to avoid rollover */
  93     last = start + len - 1;
  94
  95     mpp = list;
  96     oldtype = SMT_END;          /* Impossible value */
  97     while (mp = *mpp, start > mp->start && mp->type != SMT_END) {
  98         oldtype = mp->type;
  99         mpp = &mp->next;
 100     }
 101
 102     if (start < mp->start || mp->type == SMT_END) {
 103         if (type != oldtype) {
 104             /* Splice in a new start token */
 105             range = malloc(sizeof(*range));
 106             if (!range)
 107                 return -1;
 108
 109             range->start = start;
 110             range->type = type;
 111             *mpp = range;
 112             range->next = mp;
 113             mpp = &range->next;
 114         }
 115     } else {
 116         /* mp is exactly aligned with the start of our region */
 117         if (type != oldtype) {
 118             /* Reclaim this entry as our own boundary marker */
 119             oldtype = mp->type;
 120             mp->type = type;
 121             mpp = &mp->next;
 122         }
 123     }
 124
 125     while (mp = *mpp, last > mp->start - 1) {
 126         oldtype = mp->type;
 127         *mpp = mp->next;
 128         free(mp);
 129     }
 130
 131     if (last < mp->start - 1) {
 132         if (oldtype != type) {
 133             /* Need a new end token */
 134             range = malloc(sizeof(*range));
 135             if (!range)
 136                 return -1;
 137
 138             range->start = last + 1;
 139             range->type = oldtype;
 140             *mpp = range;
 141             range->next = mp;
 142         }
 143     } else {
 144         if (mp->type == type) {
 145             /* Merge this region with the following one */
 146             *mpp = mp->next;
 147             free(mp);
 148         }
 149     }
 150
 151     dprintf("After adding (%#x,%#x,%d):\n", start, len, type);
 152     syslinux_dump_memmap(*list);
 153
 154     return 0;
 155 }
 156
 157 /*
 158  * Verify what type a certain memory region is.  This function returns
 159  * SMT_ERROR if the memory region has multiple types, except that
 160  * SMT_FREE can be demoted to SMT_TERMINAL.
 161  */
 162 enum syslinux_memmap_types syslinux_memmap_type(struct syslinux_memmap *list,
 163                                                 addr_t start, addr_t len)
 164 {
 165     addr_t last, llast;
 166
 167     last = start + len - 1;
 168
 169     while (list->type != SMT_END) {
 170         llast = list->next->start - 1;
 171         if (list->start <= start) {
 172             if (llast >= last) {
 173                 return list->type;      /* Region has a well-defined type */
 174             } else if (llast >= start) {
 175                 /* Crosses region boundary */
 176                 while (valid_terminal_type(list->type)) {
 177                     list = list->next;
 178                     llast = list->next->start - 1;
 179                     if (llast >= last)
 180                         return SMT_TERMINAL;
 181                 }
 182                 return SMT_ERROR;
 183             }
 184         }
 185         list = list->next;
 186     }
 187
 188     return SMT_ERROR;           /* Internal error? */
 189 }
 190
 191 /*
 192  * Find the largest zone of a specific type.  Returns -1 on failure.
 193  */
 194 int syslinux_memmap_largest(struct syslinux_memmap *list,
 195                             enum syslinux_memmap_types type,
 196                             addr_t * start, addr_t * len)
 197 {
 198     addr_t size, best_size = 0;
 199     struct syslinux_memmap *best = NULL;
 200
 201     while (list->type != SMT_END) {
 202         size = list->next->start - list->start;
 203
 204         if (list->type == type && size > best_size) {
 205             best = list;
 206             best_size = size;
 207         }
 208
 209         list = list->next;
 210     }
 211
 212     if (!best)
 213         return -1;
 214
 215     *start = best->start;
 216     *len = best_size;
 217
 218     return 0;
 219 }
 220
 221 /*
 222  * Find the highest zone of a specific type that satisfies the
 223  * constraints.
 224  *
 225  * 'start' is updated with the highest address on success. 'start' can
 226  * be used to set a minimum address to begin searching from.
 227  *
 228  * Returns -1 on failure.
 229  */
 230 int syslinux_memmap_highest(const struct syslinux_memmap *list,
 231                             enum syslinux_memmap_types type,
 232                             addr_t *start, addr_t len,
 233                             addr_t ceiling, addr_t align)
 234 {
 235     addr_t size, best;
 236
 237     for (best = 0; list->type != SMT_END; list = list->next) {
 238         size = list->next->start - list->start;
 239
 240         if (list->type != type)
 241             continue;
 242
 243         if (list->start + size <= *start)
 244             continue;
 245
 246         if (list->start + len >= ceiling)
 247             continue;
 248
 249         if (list->start + size < ceiling)
 250             best = ALIGN_DOWN(list->start + size - len, align);
 251         else
 252             best = ALIGN_DOWN(ceiling - len, align);
 253
 254         if (best < *start)
 255             best = 0;
 256     }
 257
 258     if (!best)
 259         return -1;
 260
 261     *start = best;
 262
 263     return 0;
 264 }
 265
 266 /*
 267  * Find the first (lowest address) zone of a specific type and of
 268  * a certain minimum size, with an optional starting address.
 269  * The input values of start and len are used as minima.
 270  */
 271 int syslinux_memmap_find_type(struct syslinux_memmap *list,
 272                               enum syslinux_memmap_types type,
 273                               addr_t * start, addr_t * len, addr_t align)
 274 {
 275     addr_t min_start = *start;
 276     addr_t min_len = *len;
 277
 278     while (list->type != SMT_END) {
 279         if (list->type == type) {
 280             addr_t xstart, xlen;
 281             xstart = min_start > list->start ? min_start : list->start;
 282             xstart = ALIGN_UP(xstart, align);
 283
 284             if (xstart < list->next->start) {
 285                 xlen = list->next->start - xstart;
 286                 if (xlen >= min_len) {
 287                     *start = xstart;
 288                     *len = xlen;
 289                     return 0;
 290                 }
 291             }
 292         }
 293         list = list->next;
 294     }
 295
 296     return -1;                  /* Not found */
 297 }
 298
 299 /*
 300  * Free a zonelist.
 301  */
 302 void syslinux_free_memmap(struct syslinux_memmap *list)
 303 {
 304     struct syslinux_memmap *ml;
 305
 306     while (list) {
 307         ml = list;
 308         list = list->next;
 309         free(ml);
 310     }
 311 }
 312
 313 /*
 314  * Duplicate a zonelist.  Returns NULL on failure.
 315  */
 316 struct syslinux_memmap *syslinux_dup_memmap(struct syslinux_memmap *list)
 317 {
 318     struct syslinux_memmap *newlist = NULL, **nlp = &newlist;
 319     struct syslinux_memmap *ml;
 320
 321     while (list) {
 322         ml = malloc(sizeof(*ml));
 323         if (!ml) {
 324             syslinux_free_memmap(newlist);
 325             return NULL;
 326         }
 327         ml->start = list->start;
 328         ml->type = list->type;
 329         ml->next = NULL;
 330         *nlp = ml;
 331         nlp = &ml->next;
 332
 333         list = list->next;
 334     }
 335
 336     return newlist;
 337 }
 338
 339 /*
 340  * Find a memory region, given a set of heuristics and update 'base' if
 341  * successful.
 342  */
 343 int syslinux_memmap_find(struct syslinux_memmap *mmap,
 344                          addr_t *base, size_t size,
 345                          bool relocate, size_t align,
 346                          addr_t start_min, addr_t start_max,
 347                          addr_t end_min, addr_t end_max)
 348 {
 349     const struct syslinux_memmap *mp;
 350     enum syslinux_memmap_types type;
 351     bool ok;
 352
 353     if (!size)
 354         return 0;
 355
 356     type = syslinux_memmap_type(mmap, *base, size);
 357
 358     /* This assumes SMT_TERMINAL is OK if we can get the exact address */
 359     if (valid_terminal_type(type))
 360         return 0;
 361
 362     if (!relocate) {
 363         dprintf("Cannot relocate\n");
 364         return -1;
 365     }
 366
 367     ok = false;
 368     for (mp = mmap; mp && mp->type != SMT_END; mp = mp->next) {
 369         addr_t start, end;
 370         start = mp->start;
 371         end = mp->next->start;
 372
 373         if (mp->type != SMT_FREE)
 374             continue;
 375
 376         /* min */
 377         if (end <= end_min)
 378             continue;   /* Only relocate upwards */
 379
 380         if (start < start_min)
 381             start = start_min;
 382
 383         /* max */
 384         if (end > end_max)
 385             end = end_max;
 386
 387         start = ALIGN_UP(start, align);
 388         if (start > start_max || start >= end)
 389             continue;
 390
 391         if (end - start >= size) {
 392             *base = start;
 393             ok = true;
 394             break;
 395         }
 396     }
 397
 398     if (!ok)
 399         return -1;
 400
 401     return 0;
 402 }