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.
 160  */
 161 enum syslinux_memmap_types syslinux_memmap_type(struct syslinux_memmap *list,
 162                                                 addr_t start, addr_t len)
 163 {
 164     addr_t last, llast;
 165
 166     last = start + len - 1;
 167
 168     while (list->type != SMT_END) {
 169         llast = list->next->start - 1;
 170         if (list->start <= start) {
 171             if (llast >= last)
 172                 return list->type;      /* Region has a well-defined type */
 173             else if (llast >= start)
 174                 return SMT_ERROR;       /* Crosses region boundary */
 175         }
 176         list = list->next;
 177     }
 178
 179     return SMT_ERROR;           /* Internal error? */
 180 }
 181
 182 /*
 183  * Find the largest zone of a specific type.  Returns -1 on failure.
 184  */
 185 int syslinux_memmap_largest(struct syslinux_memmap *list,
 186                             enum syslinux_memmap_types type,
 187                             addr_t * start, addr_t * len)
 188 {
 189     addr_t size, best_size = 0;
 190     struct syslinux_memmap *best = NULL;
 191
 192     while (list->type != SMT_END) {
 193         size = list->next->start - list->start;
 194
 195         if (list->type == type && size > best_size) {
 196             best = list;
 197             best_size = size;
 198         }
 199
 200         list = list->next;
 201     }
 202
 203     if (!best)
 204         return -1;
 205
 206     *start = best->start;
 207     *len = best_size;
 208
 209     return 0;
 210 }
 211
 212 /*
 213  * Find the first (lowest address) zone of a specific type and of
 214  * a certain minimum size, with an optional starting address.
 215  * The input values of start and len are used as minima.
 216  */
 217 int syslinux_memmap_find(struct syslinux_memmap *list,
 218                          enum syslinux_memmap_types type,
 219                          addr_t * start, addr_t * len, addr_t align)
 220 {
 221     addr_t min_start = *start;
 222     addr_t min_len = *len;
 223
 224     while (list->type != SMT_END) {
 225         if (list->type == type) {
 226             addr_t xstart, xlen;
 227             xstart = min_start > list->start ? min_start : list->start;
 228             xstart = ALIGN_UP(xstart, align);
 229
 230             if (xstart < list->next->start) {
 231                 xlen = list->next->start - xstart;
 232                 if (xlen >= min_len) {
 233                     *start = xstart;
 234                     *len = xlen;
 235                     return 0;
 236                 }
 237             }
 238         }
 239         list = list->next;
 240     }
 241
 242     return -1;                  /* Not found */
 243 }
 244
 245 /*
 246  * Free a zonelist.
 247  */
 248 void syslinux_free_memmap(struct syslinux_memmap *list)
 249 {
 250     struct syslinux_memmap *ml;
 251
 252     while (list) {
 253         ml = list;
 254         list = list->next;
 255         free(ml);
 256     }
 257 }
 258
 259 /*
 260  * Duplicate a zonelist.  Returns NULL on failure.
 261  */
 262 struct syslinux_memmap *syslinux_dup_memmap(struct syslinux_memmap *list)
 263 {
 264     struct syslinux_memmap *newlist = NULL, **nlp = &newlist;
 265     struct syslinux_memmap *ml;
 266
 267     while (list) {
 268         ml = malloc(sizeof(*ml));
 269         if (!ml) {
 270             syslinux_free_memmap(newlist);
 271             return NULL;
 272         }
 273         ml->start = list->start;
 274         ml->type = list->type;
 275         ml->next = NULL;
 276         *nlp = ml;
 277         nlp = &ml->next;
 278
 279         list = list->next;
 280     }
 281
 282     return newlist;
 283 }