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 #if DEBUG
  86     dprintf("Input memmap:\n");
  87     syslinux_dump_memmap(stdout, *list);
  88 #endif
  89
  90     /* Remove this to make len == 0 mean all of memory */
  91     if (len == 0)
  92         return 0;
  93
  94     /* Last byte -- to avoid rollover */
  95     last = start + len - 1;
  96
  97     mpp = list;
  98     oldtype = SMT_END;          /* Impossible value */
  99     while (mp = *mpp, start > mp->start && mp->type != SMT_END) {
 100         oldtype = mp->type;
 101         mpp = &mp->next;
 102     }
 103
 104     if (start < mp->start || mp->type == SMT_END) {
 105         if (type != oldtype) {
 106             /* Splice in a new start token */
 107             range = malloc(sizeof(*range));
 108             if (!range)
 109                 return -1;
 110
 111             range->start = start;
 112             range->type = type;
 113             *mpp = range;
 114             range->next = mp;
 115             mpp = &range->next;
 116         }
 117     } else {
 118         /* mp is exactly aligned with the start of our region */
 119         if (type != oldtype) {
 120             /* Reclaim this entry as our own boundary marker */
 121             oldtype = mp->type;
 122             mp->type = type;
 123             mpp = &mp->next;
 124         }
 125     }
 126
 127     while (mp = *mpp, last > mp->start - 1) {
 128         oldtype = mp->type;
 129         *mpp = mp->next;
 130         free(mp);
 131     }
 132
 133     if (last < mp->start - 1) {
 134         if (oldtype != type) {
 135             /* Need a new end token */
 136             range = malloc(sizeof(*range));
 137             if (!range)
 138                 return -1;
 139
 140             range->start = last + 1;
 141             range->type = oldtype;
 142             *mpp = range;
 143             range->next = mp;
 144         }
 145     } else {
 146         if (mp->type == type) {
 147             /* Merge this region with the following one */
 148             *mpp = mp->next;
 149             free(mp);
 150         }
 151     }
 152
 153 #if DEBUG
 154     dprintf("After adding (%#x,%#x,%d):\n", start, len, type);
 155     syslinux_dump_memmap(stdout, *list);
 156 #endif
 157
 158     return 0;
 159 }
 160
 161 /*
 162  * Verify what type a certain memory region is.  This function returns
 163  * SMT_ERROR if the memory region has multiple types.
 164  */
 165 enum syslinux_memmap_types syslinux_memmap_type(struct syslinux_memmap *list,
 166                                                 addr_t start, addr_t len)
 167 {
 168     addr_t last, llast;
 169
 170     last = start + len - 1;
 171
 172     while (list->type != SMT_END) {
 173         llast = list->next->start - 1;
 174         if (list->start <= start) {
 175             if (llast >= last)
 176                 return list->type;      /* Region has a well-defined type */
 177             else if (llast >= start)
 178                 return SMT_ERROR;       /* Crosses region boundary */
 179         }
 180         list = list->next;
 181     }
 182
 183     return SMT_ERROR;           /* Internal error? */
 184 }
 185
 186 /*
 187  * Find the largest zone of a specific type.  Returns -1 on failure.
 188  */
 189 int syslinux_memmap_largest(struct syslinux_memmap *list,
 190                             enum syslinux_memmap_types type,
 191                             addr_t * start, addr_t * len)
 192 {
 193     addr_t size, best_size = 0;
 194     struct syslinux_memmap *best = NULL;
 195
 196     while (list->type != SMT_END) {
 197         size = list->next->start - list->start;
 198
 199         if (list->type == type && size > best_size) {
 200             best = list;
 201             best_size = size;
 202         }
 203
 204         list = list->next;
 205     }
 206
 207     if (!best)
 208         return -1;
 209
 210     *start = best->start;
 211     *len = best_size;
 212
 213     return 0;
 214 }
 215
 216 /*
 217  * Find the first (lowest address) zone of a specific type and of
 218  * a certain minimum size, with an optional starting address.
 219  * The input values of start and len are used as minima.
 220  */
 221 int syslinux_memmap_find(struct syslinux_memmap *list,
 222                          enum syslinux_memmap_types type,
 223                          addr_t * start, addr_t * len, addr_t align)
 224 {
 225     addr_t min_start = *start;
 226     addr_t min_len = *len;
 227
 228     while (list->type != SMT_END) {
 229         if (list->type == type) {
 230             addr_t xstart, xlen;
 231             xstart = min_start > list->start ? min_start : list->start;
 232             xstart = ALIGN_UP(xstart, align);
 233
 234             if (xstart < list->next->start) {
 235                 xlen = list->next->start - xstart;
 236                 if (xlen >= min_len) {
 237                     *start = xstart;
 238                     *len = xlen;
 239                     return 0;
 240                 }
 241             }
 242         }
 243         list = list->next;
 244     }
 245
 246     return -1;                  /* Not found */
 247 }
 248
 249 /*
 250  * Free a zonelist.
 251  */
 252 void syslinux_free_memmap(struct syslinux_memmap *list)
 253 {
 254     struct syslinux_memmap *ml;
 255
 256     while (list) {
 257         ml = list;
 258         list = list->next;
 259         free(ml);
 260     }
 261 }
 262
 263 /*
 264  * Duplicate a zonelist.  Returns NULL on failure.
 265  */
 266 struct syslinux_memmap *syslinux_dup_memmap(struct syslinux_memmap *list)
 267 {
 268     struct syslinux_memmap *newlist = NULL, **nlp = &newlist;
 269     struct syslinux_memmap *ml;
 270
 271     while (list) {
 272         ml = malloc(sizeof(*ml));
 273         if (!ml) {
 274             syslinux_free_memmap(newlist);
 275             return NULL;
 276         }
 277         ml->start = list->start;
 278         ml->type = list->type;
 279         ml->next = NULL;
 280         *nlp = ml;
 281         nlp = &ml->next;
 282
 283         list = list->next;
 284     }
 285
 286     return newlist;
 287 }