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 } 403
