Greg Hartman | 76d05dc | 2016-11-23 15:51:27 -0800 | [diff] [blame] | 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 | } |