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#if !defined(CONFIG_HWSIM) || defined(CONFIG_HWSIM_ZMEM) 105 memset(bdata->node_bootmem_map, 0xff, mapsize); 106#endif 107 108 return mapsize; 109} 110 111/* 112 * Marks a particular physical memory range as unallocatable. Usable RAM 113 * might be used for boot-time allocations - or it might get added 114 * to the free page pool later on. 115 */ 116static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr, 117 unsigned long size) 118{ 119 unsigned long sidx, eidx; 120 unsigned long i; 121 122 /* 123 * round up, partially reserved pages are considered 124 * fully reserved. 125 */ 126 BUG_ON(!size); 127 BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn); 128 BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn); 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 } 139} 140 141static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr, 142 unsigned long size) 143{ 144 unsigned long sidx, eidx; 145 unsigned long i; 146 147 /* 148 * round down end of usable mem, partially free pages are 149 * considered reserved. 150 */ 151 BUG_ON(!size); 152 BUG_ON(PFN_DOWN(addr + size) > bdata->node_low_pfn); 153 154 if (addr < bdata->last_success) 155 bdata->last_success = addr; 156 157 /* 158 * Round up the beginning of the address. 159 */ 160 sidx = PFN_UP(addr) - PFN_DOWN(bdata->node_boot_start); 161 eidx = PFN_DOWN(addr + size - bdata->node_boot_start); 162 163 for (i = sidx; i < eidx; i++) { 164 if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map))) 165 BUG(); 166 } 167} 168 169/* 170 * We 'merge' subsequent allocations to save space. We might 'lose' 171 * some fraction of a page if allocations cannot be satisfied due to 172 * size constraints on boxes where there is physical RAM space 173 * fragmentation - in these cases (mostly large memory boxes) this 174 * is not a problem. 175 * 176 * On low memory boxes we get it right in 100% of the cases. 177 * 178 * alignment has to be a power of 2 value. 179 * 180 * NOTE: This function is _not_ reentrant. 181 */ 182void * __init 183__alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size, 184 unsigned long align, unsigned long goal, unsigned long limit) 185{ 186 unsigned long offset, remaining_size, areasize, preferred; 187 unsigned long i, start = 0, incr, eidx, end_pfn; 188 void *ret; 189 190 if (!size) { 191 printk("__alloc_bootmem_core(): zero-sized request\n"); 192 BUG(); 193 } 194 BUG_ON(align & (align-1)); 195 196 if (limit && bdata->node_boot_start >= limit) 197 return NULL; 198 199 /* on nodes without memory - bootmem_map is NULL */ 200 if (!bdata->node_bootmem_map) 201 return NULL; 202 203 end_pfn = bdata->node_low_pfn; 204 limit = PFN_DOWN(limit); 205 if (limit && end_pfn > limit) 206 end_pfn = limit; 207 208 eidx = end_pfn - PFN_DOWN(bdata->node_boot_start); 209 offset = 0; 210 if (align && (bdata->node_boot_start & (align - 1UL)) != 0) 211 offset = align - (bdata->node_boot_start & (align - 1UL)); 212 offset = PFN_DOWN(offset); 213 214 /* 215 * We try to allocate bootmem pages above 'goal' 216 * first, then we try to allocate lower pages. 217 */ 218 if (goal && goal >= bdata->node_boot_start && PFN_DOWN(goal) < end_pfn) { 219 preferred = goal - bdata->node_boot_start; 220 221 if (bdata->last_success >= preferred) 222 if (!limit || (limit && limit > bdata->last_success)) 223 preferred = bdata->last_success; 224 } else 225 preferred = 0; 226 227 preferred = PFN_DOWN(ALIGN(preferred, align)) + offset; 228 areasize = (size + PAGE_SIZE-1) / PAGE_SIZE; 229 incr = align >> PAGE_SHIFT ? : 1; 230 231restart_scan: 232 for (i = preferred; i < eidx; i += incr) { 233 unsigned long j; 234 i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i); 235 i = ALIGN(i, incr); 236 if (i >= eidx) 237 break; 238 if (test_bit(i, bdata->node_bootmem_map)) 239 continue; 240 for (j = i + 1; j < i + areasize; ++j) { 241 if (j >= eidx) 242 goto fail_block; 243 if (test_bit(j, bdata->node_bootmem_map)) 244 goto fail_block; 245 } 246 start = i; 247 goto found; 248 fail_block: 249 i = ALIGN(j, incr); 250 } 251 252 if (preferred > offset) { 253 preferred = offset; 254 goto restart_scan; 255 } 256 return NULL; 257 258found: 259 bdata->last_success = PFN_PHYS(start); 260 BUG_ON(start >= eidx); 261 262 /* 263 * Is the next page of the previous allocation-end the start 264 * of this allocation's buffer? If yes then we can 'merge' 265 * the previous partial page with this allocation. 266 */ 267 if (align < PAGE_SIZE && 268 bdata->last_offset && bdata->last_pos+1 == start) { 269 offset = ALIGN(bdata->last_offset, align); 270 BUG_ON(offset > PAGE_SIZE); 271 remaining_size = PAGE_SIZE - offset; 272 if (size < remaining_size) { 273 areasize = 0; 274 /* last_pos unchanged */ 275 bdata->last_offset = offset + size; 276 ret = phys_to_virt(bdata->last_pos * PAGE_SIZE + 277 offset + 278 bdata->node_boot_start); 279 } else { 280 remaining_size = size - remaining_size; 281 areasize = (remaining_size + PAGE_SIZE-1) / PAGE_SIZE; 282 ret = phys_to_virt(bdata->last_pos * PAGE_SIZE + 283 offset + 284 bdata->node_boot_start); 285 bdata->last_pos = start + areasize - 1; 286 bdata->last_offset = remaining_size; 287 } 288 bdata->last_offset &= ~PAGE_MASK; 289 } else { 290 bdata->last_pos = start + areasize - 1; 291 bdata->last_offset = size & ~PAGE_MASK; 292 ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start); 293 } 294 295 /* 296 * Reserve the area now: 297 */ 298 for (i = start; i < start + areasize; i++) 299 if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map))) 300 BUG(); 301#ifndef CONFIG_HWSIM 302 memset(ret, 0, size); 303#endif 304 return ret; 305} 306 307static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat) 308{ 309 struct page *page; 310 unsigned long pfn; 311 bootmem_data_t *bdata = pgdat->bdata; 312 unsigned long i, count, total = 0; 313 unsigned long idx; 314 unsigned long *map; 315 int gofast = 0; 316 317 BUG_ON(!bdata->node_bootmem_map); 318 319 count = 0; 320 /* first extant page of the node */ 321 pfn = PFN_DOWN(bdata->node_boot_start); 322 idx = bdata->node_low_pfn - pfn; 323 map = bdata->node_bootmem_map; 324 /* Check physaddr is O(LOG2(BITS_PER_LONG)) page aligned */ 325 if (bdata->node_boot_start == 0 || 326 ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG)) 327 gofast = 1; 328 for (i = 0; i < idx; ) { 329 unsigned long v = ~map[i / BITS_PER_LONG]; 330 331 if (gofast && v == ~0UL) { 332 int order; 333 334 page = pfn_to_page(pfn); 335 count += BITS_PER_LONG; 336 order = ffs(BITS_PER_LONG) - 1; 337 __free_pages_bootmem(page, order); 338 i += BITS_PER_LONG; 339 page += BITS_PER_LONG; 340 } else if (v) { 341 unsigned long m; 342 343 page = pfn_to_page(pfn); 344 for (m = 1; m && i < idx; m<<=1, page++, i++) { 345 if (v & m) { 346 count++; 347 __free_pages_bootmem(page, 0); 348 } 349 } 350 } else { 351 i += BITS_PER_LONG; 352 } 353 pfn += BITS_PER_LONG; 354 } 355 total += count; 356 357 /* 358 * Now free the allocator bitmap itself, it's not 359 * needed anymore: 360 */ 361 page = virt_to_page(bdata->node_bootmem_map); 362 count = 0; 363 idx = (get_mapsize(bdata) + PAGE_SIZE-1) >> PAGE_SHIFT; 364 for (i = 0; i < idx; i++, page++) { 365 __free_pages_bootmem(page, 0); 366 count++; 367 } 368 total += count; 369 bdata->node_bootmem_map = NULL; 370 371 return total; 372} 373 374unsigned long __init init_bootmem_node(pg_data_t *pgdat, unsigned long freepfn, 375 unsigned long startpfn, unsigned long endpfn) 376{ 377 return init_bootmem_core(pgdat, freepfn, startpfn, endpfn); 378} 379 380void __init reserve_bootmem_node(pg_data_t *pgdat, unsigned long physaddr, 381 unsigned long size) 382{ 383 reserve_bootmem_core(pgdat->bdata, physaddr, size); 384} 385 386void __init free_bootmem_node(pg_data_t *pgdat, unsigned long physaddr, 387 unsigned long size) 388{ 389 free_bootmem_core(pgdat->bdata, physaddr, size); 390} 391 392unsigned long __init free_all_bootmem_node(pg_data_t *pgdat) 393{ 394 return free_all_bootmem_core(pgdat); 395} 396 397unsigned long __init init_bootmem(unsigned long start, unsigned long pages) 398{ 399 max_low_pfn = pages; 400 min_low_pfn = start; 401 return init_bootmem_core(NODE_DATA(0), start, 0, pages); 402} 403 404#ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE 405void __init reserve_bootmem(unsigned long addr, unsigned long size) 406{ 407 reserve_bootmem_core(NODE_DATA(0)->bdata, addr, size); 408} 409#endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */ 410 411void __init free_bootmem(unsigned long addr, unsigned long size) 412{ 413 free_bootmem_core(NODE_DATA(0)->bdata, addr, size); 414} 415 416unsigned long __init free_all_bootmem(void) 417{ 418 return free_all_bootmem_core(NODE_DATA(0)); 419} 420 421void * __init __alloc_bootmem_nopanic(unsigned long size, unsigned long align, 422 unsigned long goal) 423{ 424 bootmem_data_t *bdata; 425 void *ptr; 426 427 list_for_each_entry(bdata, &bdata_list, list) { 428 ptr = __alloc_bootmem_core(bdata, size, align, goal, 0); 429 if (ptr) 430 return ptr; 431 } 432 return NULL; 433} 434 435void * __init __alloc_bootmem(unsigned long size, unsigned long align, 436 unsigned long goal) 437{ 438 void *mem = __alloc_bootmem_nopanic(size,align,goal); 439 440 if (mem) 441 return mem; 442 /* 443 * Whoops, we cannot satisfy the allocation request. 444 */ 445 printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size); 446 panic("Out of memory"); 447 return NULL; 448} 449 450 451void * __init __alloc_bootmem_node(pg_data_t *pgdat, unsigned long size, 452 unsigned long align, unsigned long goal) 453{ 454 void *ptr; 455 456 ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal, 0); 457 if (ptr) 458 return ptr; 459 460 return __alloc_bootmem(size, align, goal); 461} 462 463#ifndef ARCH_LOW_ADDRESS_LIMIT 464#define ARCH_LOW_ADDRESS_LIMIT 0xffffffffUL 465#endif 466 467void * __init __alloc_bootmem_low(unsigned long size, unsigned long align, 468 unsigned long goal) 469{ 470 bootmem_data_t *bdata; 471 void *ptr; 472 473 list_for_each_entry(bdata, &bdata_list, list) { 474 ptr = __alloc_bootmem_core(bdata, size, align, goal, 475 ARCH_LOW_ADDRESS_LIMIT); 476 if (ptr) 477 return ptr; 478 } 479 480 /* 481 * Whoops, we cannot satisfy the allocation request. 482 */ 483 printk(KERN_ALERT "low bootmem alloc of %lu bytes failed!\n", size); 484 panic("Out of low memory"); 485 return NULL; 486} 487 488void * __init __alloc_bootmem_low_node(pg_data_t *pgdat, unsigned long size, 489 unsigned long align, unsigned long goal) 490{ 491 return __alloc_bootmem_core(pgdat->bdata, size, align, goal, 492 ARCH_LOW_ADDRESS_LIMIT); 493} 494