4 * Copyright (C) 1999 Ingo Molnar
5 * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
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.
11 #include <linux/init.h>
12 #include <linux/pfn.h>
13 #include <linux/bootmem.h>
14 #include <linux/module.h>
22 * Access to this subsystem has to be serialized externally. (this is
23 * true for the boot process anyway)
25 unsigned long max_low_pfn;
26 unsigned long min_low_pfn;
27 unsigned long max_pfn;
29 EXPORT_UNUSED_SYMBOL(max_pfn); /* June 2006 */
31 static LIST_HEAD(bdata_list);
32 #ifdef CONFIG_CRASH_DUMP
34 * If we have booted due to a crash, max_pfn will be a very low value. We need
35 * to know the amount of memory that the previous kernel used.
37 unsigned long saved_max_pfn;
40 /* return the number of _pages_ that will be allocated for the boot bitmap */
41 unsigned long __init bootmem_bootmap_pages(unsigned long pages)
43 unsigned long mapsize;
45 mapsize = (pages+7)/8;
46 mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK;
47 mapsize >>= PAGE_SHIFT;
55 static void __init link_bootmem(bootmem_data_t *bdata)
59 if (list_empty(&bdata_list)) {
60 list_add(&bdata->list, &bdata_list);
64 list_for_each_entry(ent, &bdata_list, list) {
65 if (bdata->node_boot_start < ent->node_boot_start) {
66 list_add_tail(&bdata->list, &ent->list);
70 list_add_tail(&bdata->list, &bdata_list);
74 * Given an initialised bdata, it returns the size of the boot bitmap
76 static unsigned long __init get_mapsize(bootmem_data_t *bdata)
78 unsigned long mapsize;
79 unsigned long start = PFN_DOWN(bdata->node_boot_start);
80 unsigned long end = bdata->node_low_pfn;
82 mapsize = ((end - start) + 7) / 8;
83 return ALIGN(mapsize, sizeof(long));
87 * Called once to set up the allocator itself.
89 static unsigned long __init init_bootmem_core(pg_data_t *pgdat,
90 unsigned long mapstart, unsigned long start, unsigned long end)
92 bootmem_data_t *bdata = pgdat->bdata;
93 unsigned long mapsize;
95 bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart));
96 bdata->node_boot_start = PFN_PHYS(start);
97 bdata->node_low_pfn = end;
101 * Initially all pages are reserved - setup_arch() has to
102 * register free RAM areas explicitly.
104 mapsize = get_mapsize(bdata);
105 memset(bdata->node_bootmem_map, 0xff, mapsize);
111 * Marks a particular physical memory range as unallocatable. Usable RAM
112 * might be used for boot-time allocations - or it might get added
113 * to the free page pool later on.
115 static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr,
118 unsigned long sidx, eidx;
122 * round up, partially reserved pages are considered
126 BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn);
127 BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn);
129 sidx = PFN_DOWN(addr - bdata->node_boot_start);
130 eidx = PFN_UP(addr + size - bdata->node_boot_start);
132 for (i = sidx; i < eidx; i++)
133 if (test_and_set_bit(i, bdata->node_bootmem_map)) {
134 #ifdef CONFIG_DEBUG_BOOTMEM
135 printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
140 static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr,
143 unsigned long sidx, eidx;
147 * round down end of usable mem, partially free pages are
148 * considered reserved.
151 BUG_ON(PFN_DOWN(addr + size) > bdata->node_low_pfn);
153 if (addr < bdata->last_success)
154 bdata->last_success = addr;
157 * Round up the beginning of the address.
159 sidx = PFN_UP(addr) - PFN_DOWN(bdata->node_boot_start);
160 eidx = PFN_DOWN(addr + size - bdata->node_boot_start);
162 for (i = sidx; i < eidx; i++) {
163 if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map)))
169 * We 'merge' subsequent allocations to save space. We might 'lose'
170 * some fraction of a page if allocations cannot be satisfied due to
171 * size constraints on boxes where there is physical RAM space
172 * fragmentation - in these cases (mostly large memory boxes) this
175 * On low memory boxes we get it right in 100% of the cases.
177 * alignment has to be a power of 2 value.
179 * NOTE: This function is _not_ reentrant.
182 __alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size,
183 unsigned long align, unsigned long goal, unsigned long limit)
185 unsigned long offset, remaining_size, areasize, preferred;
186 unsigned long i, start = 0, incr, eidx, end_pfn;
190 printk("__alloc_bootmem_core(): zero-sized request\n");
193 BUG_ON(align & (align-1));
195 if (limit && bdata->node_boot_start >= limit)
198 end_pfn = bdata->node_low_pfn;
199 limit = PFN_DOWN(limit);
200 if (limit && end_pfn > limit)
203 eidx = end_pfn - PFN_DOWN(bdata->node_boot_start);
205 if (align && (bdata->node_boot_start & (align - 1UL)) != 0)
206 offset = align - (bdata->node_boot_start & (align - 1UL));
207 offset = PFN_DOWN(offset);
210 * We try to allocate bootmem pages above 'goal'
211 * first, then we try to allocate lower pages.
213 if (goal && goal >= bdata->node_boot_start && PFN_DOWN(goal) < end_pfn) {
214 preferred = goal - bdata->node_boot_start;
216 if (bdata->last_success >= preferred)
217 if (!limit || (limit && limit > bdata->last_success))
218 preferred = bdata->last_success;
222 preferred = PFN_DOWN(ALIGN(preferred, align)) + offset;
223 areasize = (size + PAGE_SIZE-1) / PAGE_SIZE;
224 incr = align >> PAGE_SHIFT ? : 1;
227 for (i = preferred; i < eidx; i += incr) {
229 i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i);
233 if (test_bit(i, bdata->node_bootmem_map))
235 for (j = i + 1; j < i + areasize; ++j) {
238 if (test_bit(j, bdata->node_bootmem_map))
247 if (preferred > offset) {
254 bdata->last_success = PFN_PHYS(start);
255 BUG_ON(start >= eidx);
258 * Is the next page of the previous allocation-end the start
259 * of this allocation's buffer? If yes then we can 'merge'
260 * the previous partial page with this allocation.
262 if (align < PAGE_SIZE &&
263 bdata->last_offset && bdata->last_pos+1 == start) {
264 offset = ALIGN(bdata->last_offset, align);
265 BUG_ON(offset > PAGE_SIZE);
266 remaining_size = PAGE_SIZE - offset;
267 if (size < remaining_size) {
269 /* last_pos unchanged */
270 bdata->last_offset = offset + size;
271 ret = phys_to_virt(bdata->last_pos * PAGE_SIZE +
273 bdata->node_boot_start);
275 remaining_size = size - remaining_size;
276 areasize = (remaining_size + PAGE_SIZE-1) / PAGE_SIZE;
277 ret = phys_to_virt(bdata->last_pos * PAGE_SIZE +
279 bdata->node_boot_start);
280 bdata->last_pos = start + areasize - 1;
281 bdata->last_offset = remaining_size;
283 bdata->last_offset &= ~PAGE_MASK;
285 bdata->last_pos = start + areasize - 1;
286 bdata->last_offset = size & ~PAGE_MASK;
287 ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
291 * Reserve the area now:
293 for (i = start; i < start + areasize; i++)
294 if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map)))
296 memset(ret, 0, size);
300 static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat)
304 bootmem_data_t *bdata = pgdat->bdata;
305 unsigned long i, count, total = 0;
310 BUG_ON(!bdata->node_bootmem_map);
313 /* first extant page of the node */
314 pfn = PFN_DOWN(bdata->node_boot_start);
315 idx = bdata->node_low_pfn - pfn;
316 map = bdata->node_bootmem_map;
317 /* Check physaddr is O(LOG2(BITS_PER_LONG)) page aligned */
318 if (bdata->node_boot_start == 0 ||
319 ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG))
321 for (i = 0; i < idx; ) {
322 unsigned long v = ~map[i / BITS_PER_LONG];
324 if (gofast && v == ~0UL) {
327 page = pfn_to_page(pfn);
328 count += BITS_PER_LONG;
329 order = ffs(BITS_PER_LONG) - 1;
330 __free_pages_bootmem(page, order);
332 page += BITS_PER_LONG;
336 page = pfn_to_page(pfn);
337 for (m = 1; m && i < idx; m<<=1, page++, i++) {
340 __free_pages_bootmem(page, 0);
346 pfn += BITS_PER_LONG;
351 * Now free the allocator bitmap itself, it's not
354 page = virt_to_page(bdata->node_bootmem_map);
356 idx = (get_mapsize(bdata) + PAGE_SIZE-1) >> PAGE_SHIFT;
357 for (i = 0; i < idx; i++, page++) {
358 __free_pages_bootmem(page, 0);
362 bdata->node_bootmem_map = NULL;
367 unsigned long __init init_bootmem_node(pg_data_t *pgdat, unsigned long freepfn,
368 unsigned long startpfn, unsigned long endpfn)
370 return init_bootmem_core(pgdat, freepfn, startpfn, endpfn);
373 void __init reserve_bootmem_node(pg_data_t *pgdat, unsigned long physaddr,
376 reserve_bootmem_core(pgdat->bdata, physaddr, size);
379 void __init free_bootmem_node(pg_data_t *pgdat, unsigned long physaddr,
382 free_bootmem_core(pgdat->bdata, physaddr, size);
385 unsigned long __init free_all_bootmem_node(pg_data_t *pgdat)
387 return free_all_bootmem_core(pgdat);
390 unsigned long __init init_bootmem(unsigned long start, unsigned long pages)
394 return init_bootmem_core(NODE_DATA(0), start, 0, pages);
397 #ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE
398 void __init reserve_bootmem(unsigned long addr, unsigned long size)
400 reserve_bootmem_core(NODE_DATA(0)->bdata, addr, size);
402 #endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
404 void __init free_bootmem(unsigned long addr, unsigned long size)
406 free_bootmem_core(NODE_DATA(0)->bdata, addr, size);
409 unsigned long __init free_all_bootmem(void)
411 return free_all_bootmem_core(NODE_DATA(0));
414 void * __init __alloc_bootmem_nopanic(unsigned long size, unsigned long align,
417 bootmem_data_t *bdata;
420 list_for_each_entry(bdata, &bdata_list, list) {
421 ptr = __alloc_bootmem_core(bdata, size, align, goal, 0);
428 void * __init __alloc_bootmem(unsigned long size, unsigned long align,
431 void *mem = __alloc_bootmem_nopanic(size,align,goal);
436 * Whoops, we cannot satisfy the allocation request.
438 printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
439 panic("Out of memory");
444 void * __init __alloc_bootmem_node(pg_data_t *pgdat, unsigned long size,
445 unsigned long align, unsigned long goal)
449 ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal, 0);
453 return __alloc_bootmem(size, align, goal);
456 #define LOW32LIMIT 0xffffffff
458 void * __init __alloc_bootmem_low(unsigned long size, unsigned long align,
461 bootmem_data_t *bdata;
464 list_for_each_entry(bdata, &bdata_list, list) {
465 ptr = __alloc_bootmem_core(bdata, size, align, goal, LOW32LIMIT);
471 * Whoops, we cannot satisfy the allocation request.
473 printk(KERN_ALERT "low bootmem alloc of %lu bytes failed!\n", size);
474 panic("Out of low memory");
478 void * __init __alloc_bootmem_low_node(pg_data_t *pgdat, unsigned long size,
479 unsigned long align, unsigned long goal)
481 return __alloc_bootmem_core(pgdat->bdata, size, align, goal, LOW32LIMIT);