bootmem.c revision 9a2dc04cf070ee98e014a172695782ff42015fc4
1/* 2 * linux/mm/bootmem.c 3 * 4 * Copyright (C) 1999 Ingo Molnar 5 * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999 6 * 7 * simple boot-time physical memory area allocator and 8 * free memory collector. It's used to deal with reserved 9 * system memory and memory holes as well. 10 */ 11#include <linux/init.h> 12#include <linux/pfn.h> 13#include <linux/bootmem.h> 14#include <linux/module.h> 15 16#include <asm/bug.h> 17#include <asm/io.h> 18#include <asm/processor.h> 19 20#include "internal.h" 21 22/* 23 * Access to this subsystem has to be serialized externally. (this is 24 * true for the boot process anyway) 25 */ 26unsigned long max_low_pfn; 27unsigned long min_low_pfn; 28unsigned long max_pfn; 29 30static LIST_HEAD(bdata_list); 31#ifdef CONFIG_CRASH_DUMP 32/* 33 * If we have booted due to a crash, max_pfn will be a very low value. We need 34 * to know the amount of memory that the previous kernel used. 35 */ 36unsigned long saved_max_pfn; 37#endif 38 39/* return the number of _pages_ that will be allocated for the boot bitmap */ 40unsigned long __init bootmem_bootmap_pages(unsigned long pages) 41{ 42 unsigned long mapsize; 43 44 mapsize = (pages+7)/8; 45 mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK; 46 mapsize >>= PAGE_SHIFT; 47 48 return mapsize; 49} 50 51/* 52 * link bdata in order 53 */ 54static void __init link_bootmem(bootmem_data_t *bdata) 55{ 56 bootmem_data_t *ent; 57 58 if (list_empty(&bdata_list)) { 59 list_add(&bdata->list, &bdata_list); 60 return; 61 } 62 /* insert in order */ 63 list_for_each_entry(ent, &bdata_list, list) { 64 if (bdata->node_boot_start < ent->node_boot_start) { 65 list_add_tail(&bdata->list, &ent->list); 66 return; 67 } 68 } 69 list_add_tail(&bdata->list, &bdata_list); 70} 71 72/* 73 * Given an initialised bdata, it returns the size of the boot bitmap 74 */ 75static unsigned long __init get_mapsize(bootmem_data_t *bdata) 76{ 77 unsigned long mapsize; 78 unsigned long start = PFN_DOWN(bdata->node_boot_start); 79 unsigned long end = bdata->node_low_pfn; 80 81 mapsize = ((end - start) + 7) / 8; 82 return ALIGN(mapsize, sizeof(long)); 83} 84 85/* 86 * Called once to set up the allocator itself. 87 */ 88static unsigned long __init init_bootmem_core(pg_data_t *pgdat, 89 unsigned long mapstart, unsigned long start, unsigned long end) 90{ 91 bootmem_data_t *bdata = pgdat->bdata; 92 unsigned long mapsize; 93 94 bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart)); 95 bdata->node_boot_start = PFN_PHYS(start); 96 bdata->node_low_pfn = end; 97 link_bootmem(bdata); 98 99 /* 100 * Initially all pages are reserved - setup_arch() has to 101 * register free RAM areas explicitly. 102 */ 103 mapsize = get_mapsize(bdata); 104 memset(bdata->node_bootmem_map, 0xff, mapsize); 105 106 return mapsize; 107} 108 109/* 110 * Marks a particular physical memory range as unallocatable. Usable RAM 111 * might be used for boot-time allocations - or it might get added 112 * to the free page pool later on. 113 */ 114static int __init reserve_bootmem_core(bootmem_data_t *bdata, 115 unsigned long addr, unsigned long size, int flags) 116{ 117 unsigned long sidx, eidx; 118 unsigned long i; 119 int ret; 120 121 /* 122 * round up, partially reserved pages are considered 123 * fully reserved. 124 */ 125 BUG_ON(!size); 126 BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn); 127 BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn); 128 BUG_ON(addr < bdata->node_boot_start); 129 130 sidx = PFN_DOWN(addr - bdata->node_boot_start); 131 eidx = PFN_UP(addr + size - bdata->node_boot_start); 132 133 for (i = sidx; i < eidx; i++) 134 if (test_and_set_bit(i, bdata->node_bootmem_map)) { 135#ifdef CONFIG_DEBUG_BOOTMEM 136 printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE); 137#endif 138 if (flags & BOOTMEM_EXCLUSIVE) { 139 ret = -EBUSY; 140 goto err; 141 } 142 } 143 144 return 0; 145 146err: 147 /* unreserve memory we accidentally reserved */ 148 for (i--; i >= sidx; i--) 149 clear_bit(i, bdata->node_bootmem_map); 150 151 return ret; 152} 153 154static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr, 155 unsigned long size) 156{ 157 unsigned long sidx, eidx; 158 unsigned long i; 159 160 BUG_ON(!size); 161 162 /* out range */ 163 if (addr + size < bdata->node_boot_start || 164 PFN_DOWN(addr) > bdata->node_low_pfn) 165 return; 166 /* 167 * round down end of usable mem, partially free pages are 168 * considered reserved. 169 */ 170 171 if (addr >= bdata->node_boot_start && addr < bdata->last_success) 172 bdata->last_success = addr; 173 174 /* 175 * Round up to index to the range. 176 */ 177 if (PFN_UP(addr) > PFN_DOWN(bdata->node_boot_start)) 178 sidx = PFN_UP(addr) - PFN_DOWN(bdata->node_boot_start); 179 else 180 sidx = 0; 181 182 eidx = PFN_DOWN(addr + size - bdata->node_boot_start); 183 if (eidx > bdata->node_low_pfn - PFN_DOWN(bdata->node_boot_start)) 184 eidx = bdata->node_low_pfn - PFN_DOWN(bdata->node_boot_start); 185 186 for (i = sidx; i < eidx; i++) { 187 if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map))) 188 BUG(); 189 } 190} 191 192/* 193 * We 'merge' subsequent allocations to save space. We might 'lose' 194 * some fraction of a page if allocations cannot be satisfied due to 195 * size constraints on boxes where there is physical RAM space 196 * fragmentation - in these cases (mostly large memory boxes) this 197 * is not a problem. 198 * 199 * On low memory boxes we get it right in 100% of the cases. 200 * 201 * alignment has to be a power of 2 value. 202 * 203 * NOTE: This function is _not_ reentrant. 204 */ 205void * __init 206__alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size, 207 unsigned long align, unsigned long goal, unsigned long limit) 208{ 209 unsigned long areasize, preferred; 210 unsigned long i, start = 0, incr, eidx, end_pfn; 211 void *ret; 212 unsigned long node_boot_start; 213 void *node_bootmem_map; 214 215 if (!size) { 216 printk("__alloc_bootmem_core(): zero-sized request\n"); 217 BUG(); 218 } 219 BUG_ON(align & (align-1)); 220 221 /* on nodes without memory - bootmem_map is NULL */ 222 if (!bdata->node_bootmem_map) 223 return NULL; 224 225 /* bdata->node_boot_start is supposed to be (12+6)bits alignment on x86_64 ? */ 226 node_boot_start = bdata->node_boot_start; 227 node_bootmem_map = bdata->node_bootmem_map; 228 if (align) { 229 node_boot_start = ALIGN(bdata->node_boot_start, align); 230 if (node_boot_start > bdata->node_boot_start) 231 node_bootmem_map = (unsigned long *)bdata->node_bootmem_map + 232 PFN_DOWN(node_boot_start - bdata->node_boot_start)/BITS_PER_LONG; 233 } 234 235 if (limit && node_boot_start >= limit) 236 return NULL; 237 238 end_pfn = bdata->node_low_pfn; 239 limit = PFN_DOWN(limit); 240 if (limit && end_pfn > limit) 241 end_pfn = limit; 242 243 eidx = end_pfn - PFN_DOWN(node_boot_start); 244 245 /* 246 * We try to allocate bootmem pages above 'goal' 247 * first, then we try to allocate lower pages. 248 */ 249 preferred = 0; 250 if (goal && PFN_DOWN(goal) < end_pfn) { 251 if (goal > node_boot_start) 252 preferred = goal - node_boot_start; 253 254 if (bdata->last_success > node_boot_start && 255 bdata->last_success - node_boot_start >= preferred) 256 if (!limit || (limit && limit > bdata->last_success)) 257 preferred = bdata->last_success - node_boot_start; 258 } 259 260 preferred = PFN_DOWN(ALIGN(preferred, align)); 261 areasize = (size + PAGE_SIZE-1) / PAGE_SIZE; 262 incr = align >> PAGE_SHIFT ? : 1; 263 264restart_scan: 265 for (i = preferred; i < eidx;) { 266 unsigned long j; 267 268 i = find_next_zero_bit(node_bootmem_map, eidx, i); 269 i = ALIGN(i, incr); 270 if (i >= eidx) 271 break; 272 if (test_bit(i, node_bootmem_map)) { 273 i += incr; 274 continue; 275 } 276 for (j = i + 1; j < i + areasize; ++j) { 277 if (j >= eidx) 278 goto fail_block; 279 if (test_bit(j, node_bootmem_map)) 280 goto fail_block; 281 } 282 start = i; 283 goto found; 284 fail_block: 285 i = ALIGN(j, incr); 286 if (i == j) 287 i += incr; 288 } 289 290 if (preferred > 0) { 291 preferred = 0; 292 goto restart_scan; 293 } 294 return NULL; 295 296found: 297 bdata->last_success = PFN_PHYS(start) + node_boot_start; 298 BUG_ON(start >= eidx); 299 300 /* 301 * Is the next page of the previous allocation-end the start 302 * of this allocation's buffer? If yes then we can 'merge' 303 * the previous partial page with this allocation. 304 */ 305 if (align < PAGE_SIZE && 306 bdata->last_offset && bdata->last_pos+1 == start) { 307 unsigned long offset, remaining_size; 308 offset = ALIGN(bdata->last_offset, align); 309 BUG_ON(offset > PAGE_SIZE); 310 remaining_size = PAGE_SIZE - offset; 311 if (size < remaining_size) { 312 areasize = 0; 313 /* last_pos unchanged */ 314 bdata->last_offset = offset + size; 315 ret = phys_to_virt(bdata->last_pos * PAGE_SIZE + 316 offset + node_boot_start); 317 } else { 318 remaining_size = size - remaining_size; 319 areasize = (remaining_size + PAGE_SIZE-1) / PAGE_SIZE; 320 ret = phys_to_virt(bdata->last_pos * PAGE_SIZE + 321 offset + node_boot_start); 322 bdata->last_pos = start + areasize - 1; 323 bdata->last_offset = remaining_size; 324 } 325 bdata->last_offset &= ~PAGE_MASK; 326 } else { 327 bdata->last_pos = start + areasize - 1; 328 bdata->last_offset = size & ~PAGE_MASK; 329 ret = phys_to_virt(start * PAGE_SIZE + node_boot_start); 330 } 331 332 /* 333 * Reserve the area now: 334 */ 335 for (i = start; i < start + areasize; i++) 336 if (unlikely(test_and_set_bit(i, node_bootmem_map))) 337 BUG(); 338 memset(ret, 0, size); 339 return ret; 340} 341 342static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat) 343{ 344 struct page *page; 345 unsigned long pfn; 346 bootmem_data_t *bdata = pgdat->bdata; 347 unsigned long i, count, total = 0; 348 unsigned long idx; 349 unsigned long *map; 350 int gofast = 0; 351 352 BUG_ON(!bdata->node_bootmem_map); 353 354 count = 0; 355 /* first extant page of the node */ 356 pfn = PFN_DOWN(bdata->node_boot_start); 357 idx = bdata->node_low_pfn - pfn; 358 map = bdata->node_bootmem_map; 359 /* Check physaddr is O(LOG2(BITS_PER_LONG)) page aligned */ 360 if (bdata->node_boot_start == 0 || 361 ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG)) 362 gofast = 1; 363 for (i = 0; i < idx; ) { 364 unsigned long v = ~map[i / BITS_PER_LONG]; 365 366 if (gofast && v == ~0UL) { 367 int order; 368 369 page = pfn_to_page(pfn); 370 count += BITS_PER_LONG; 371 order = ffs(BITS_PER_LONG) - 1; 372 __free_pages_bootmem(page, order); 373 i += BITS_PER_LONG; 374 page += BITS_PER_LONG; 375 } else if (v) { 376 unsigned long m; 377 378 page = pfn_to_page(pfn); 379 for (m = 1; m && i < idx; m<<=1, page++, i++) { 380 if (v & m) { 381 count++; 382 __free_pages_bootmem(page, 0); 383 } 384 } 385 } else { 386 i += BITS_PER_LONG; 387 } 388 pfn += BITS_PER_LONG; 389 } 390 total += count; 391 392 /* 393 * Now free the allocator bitmap itself, it's not 394 * needed anymore: 395 */ 396 page = virt_to_page(bdata->node_bootmem_map); 397 count = 0; 398 idx = (get_mapsize(bdata) + PAGE_SIZE-1) >> PAGE_SHIFT; 399 for (i = 0; i < idx; i++, page++) { 400 __free_pages_bootmem(page, 0); 401 count++; 402 } 403 total += count; 404 bdata->node_bootmem_map = NULL; 405 406 return total; 407} 408 409unsigned long __init init_bootmem_node(pg_data_t *pgdat, unsigned long freepfn, 410 unsigned long startpfn, unsigned long endpfn) 411{ 412 return init_bootmem_core(pgdat, freepfn, startpfn, endpfn); 413} 414 415void __init reserve_bootmem_node(pg_data_t *pgdat, unsigned long physaddr, 416 unsigned long size, int flags) 417{ 418 reserve_bootmem_core(pgdat->bdata, physaddr, size, flags); 419} 420 421void __init free_bootmem_node(pg_data_t *pgdat, unsigned long physaddr, 422 unsigned long size) 423{ 424 free_bootmem_core(pgdat->bdata, physaddr, size); 425} 426 427unsigned long __init free_all_bootmem_node(pg_data_t *pgdat) 428{ 429 return free_all_bootmem_core(pgdat); 430} 431 432unsigned long __init init_bootmem(unsigned long start, unsigned long pages) 433{ 434 max_low_pfn = pages; 435 min_low_pfn = start; 436 return init_bootmem_core(NODE_DATA(0), start, 0, pages); 437} 438 439#ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE 440int __init reserve_bootmem(unsigned long addr, unsigned long size, 441 int flags) 442{ 443 return reserve_bootmem_core(NODE_DATA(0)->bdata, addr, size, flags); 444} 445#endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */ 446 447void __init free_bootmem(unsigned long addr, unsigned long size) 448{ 449 bootmem_data_t *bdata; 450 list_for_each_entry(bdata, &bdata_list, list) 451 free_bootmem_core(bdata, addr, size); 452} 453 454unsigned long __init free_all_bootmem(void) 455{ 456 return free_all_bootmem_core(NODE_DATA(0)); 457} 458 459void * __init __alloc_bootmem_nopanic(unsigned long size, unsigned long align, 460 unsigned long goal) 461{ 462 bootmem_data_t *bdata; 463 void *ptr; 464 465 list_for_each_entry(bdata, &bdata_list, list) { 466 ptr = __alloc_bootmem_core(bdata, size, align, goal, 0); 467 if (ptr) 468 return ptr; 469 } 470 return NULL; 471} 472 473void * __init __alloc_bootmem(unsigned long size, unsigned long align, 474 unsigned long goal) 475{ 476 void *mem = __alloc_bootmem_nopanic(size,align,goal); 477 478 if (mem) 479 return mem; 480 /* 481 * Whoops, we cannot satisfy the allocation request. 482 */ 483 printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size); 484 panic("Out of memory"); 485 return NULL; 486} 487 488 489void * __init __alloc_bootmem_node(pg_data_t *pgdat, unsigned long size, 490 unsigned long align, unsigned long goal) 491{ 492 void *ptr; 493 494 ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal, 0); 495 if (ptr) 496 return ptr; 497 498 return __alloc_bootmem(size, align, goal); 499} 500 501#ifndef ARCH_LOW_ADDRESS_LIMIT 502#define ARCH_LOW_ADDRESS_LIMIT 0xffffffffUL 503#endif 504 505void * __init __alloc_bootmem_low(unsigned long size, unsigned long align, 506 unsigned long goal) 507{ 508 bootmem_data_t *bdata; 509 void *ptr; 510 511 list_for_each_entry(bdata, &bdata_list, list) { 512 ptr = __alloc_bootmem_core(bdata, size, align, goal, 513 ARCH_LOW_ADDRESS_LIMIT); 514 if (ptr) 515 return ptr; 516 } 517 518 /* 519 * Whoops, we cannot satisfy the allocation request. 520 */ 521 printk(KERN_ALERT "low bootmem alloc of %lu bytes failed!\n", size); 522 panic("Out of low memory"); 523 return NULL; 524} 525 526void * __init __alloc_bootmem_low_node(pg_data_t *pgdat, unsigned long size, 527 unsigned long align, unsigned long goal) 528{ 529 return __alloc_bootmem_core(pgdat->bdata, size, align, goal, 530 ARCH_LOW_ADDRESS_LIMIT); 531} 532