blob: 555d5d2731c6d963a66db15d9eb66aa03e9d6c8d [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Johannes Weiner57cfc292008-07-23 21:28:00 -07002 * bootmem - A boot-time physical memory allocator and configurator
Linus Torvalds1da177e2005-04-16 15:20:36 -07003 *
4 * Copyright (C) 1999 Ingo Molnar
Johannes Weiner57cfc292008-07-23 21:28:00 -07005 * 1999 Kanoj Sarcar, SGI
6 * 2008 Johannes Weiner
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 *
Johannes Weiner57cfc292008-07-23 21:28:00 -07008 * Access to this subsystem has to be serialized externally (which is true
9 * for the boot process anyway).
Linus Torvalds1da177e2005-04-16 15:20:36 -070010 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070011#include <linux/init.h>
Franck Bui-Huubbc7b922006-09-25 23:31:07 -070012#include <linux/pfn.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <linux/bootmem.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070014#include <linux/module.h>
Catalin Marinasec3a3542009-07-07 10:33:01 +010015#include <linux/kmemleak.h>
Franck Bui-Huue786e862006-09-25 23:31:06 -070016
17#include <asm/bug.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include <asm/io.h>
Heiko Carstensdfd54cb2006-09-25 23:31:33 -070019#include <asm/processor.h>
Franck Bui-Huue786e862006-09-25 23:31:06 -070020
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include "internal.h"
22
Linus Torvalds1da177e2005-04-16 15:20:36 -070023unsigned long max_low_pfn;
24unsigned long min_low_pfn;
25unsigned long max_pfn;
26
Vivek Goyal92aa63a2005-06-25 14:58:18 -070027#ifdef CONFIG_CRASH_DUMP
28/*
29 * If we have booted due to a crash, max_pfn will be a very low value. We need
30 * to know the amount of memory that the previous kernel used.
31 */
32unsigned long saved_max_pfn;
33#endif
34
Johannes Weinerb61bfa32008-07-23 21:26:55 -070035bootmem_data_t bootmem_node_data[MAX_NUMNODES] __initdata;
36
Johannes Weiner636cc402008-07-23 21:28:03 -070037static struct list_head bdata_list __initdata = LIST_HEAD_INIT(bdata_list);
38
Johannes Weiner2e5237d2008-07-23 21:28:02 -070039static int bootmem_debug;
40
41static int __init bootmem_debug_setup(char *buf)
42{
43 bootmem_debug = 1;
44 return 0;
45}
46early_param("bootmem_debug", bootmem_debug_setup);
47
48#define bdebug(fmt, args...) ({ \
49 if (unlikely(bootmem_debug)) \
50 printk(KERN_INFO \
51 "bootmem::%s " fmt, \
Harvey Harrison80a914d2008-10-15 22:01:25 -070052 __func__, ## args); \
Johannes Weiner2e5237d2008-07-23 21:28:02 -070053})
54
Johannes Weinerdf049a52008-07-23 21:28:02 -070055static unsigned long __init bootmap_bytes(unsigned long pages)
Johannes Weiner223e8dc2008-07-23 21:28:00 -070056{
Johannes Weinerdf049a52008-07-23 21:28:02 -070057 unsigned long bytes = (pages + 7) / 8;
Johannes Weiner223e8dc2008-07-23 21:28:00 -070058
Johannes Weinerdf049a52008-07-23 21:28:02 -070059 return ALIGN(bytes, sizeof(long));
Johannes Weiner223e8dc2008-07-23 21:28:00 -070060}
61
Johannes Weinera66fd7d2008-07-23 21:28:01 -070062/**
63 * bootmem_bootmap_pages - calculate bitmap size in pages
64 * @pages: number of pages the bitmap has to represent
65 */
Franck Bui-Huuf71bf0c2006-09-25 23:31:08 -070066unsigned long __init bootmem_bootmap_pages(unsigned long pages)
Linus Torvalds1da177e2005-04-16 15:20:36 -070067{
Johannes Weinerdf049a52008-07-23 21:28:02 -070068 unsigned long bytes = bootmap_bytes(pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -070069
Johannes Weinerdf049a52008-07-23 21:28:02 -070070 return PAGE_ALIGN(bytes) >> PAGE_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -070071}
Franck Bui-Huuf71bf0c2006-09-25 23:31:08 -070072
KAMEZAWA Hiroyuki679bc9f2006-03-27 01:15:58 -080073/*
74 * link bdata in order
75 */
Franck Bui-Huu69d49e62006-09-25 23:31:04 -070076static void __init link_bootmem(bootmem_data_t *bdata)
KAMEZAWA Hiroyuki679bc9f2006-03-27 01:15:58 -080077{
Johannes Weiner636cc402008-07-23 21:28:03 -070078 struct list_head *iter;
Franck Bui-Huuf71bf0c2006-09-25 23:31:08 -070079
Johannes Weiner636cc402008-07-23 21:28:03 -070080 list_for_each(iter, &bdata_list) {
81 bootmem_data_t *ent;
82
83 ent = list_entry(iter, bootmem_data_t, list);
Johannes Weiner3560e242008-07-23 21:28:09 -070084 if (bdata->node_min_pfn < ent->node_min_pfn)
Johannes Weiner636cc402008-07-23 21:28:03 -070085 break;
KAMEZAWA Hiroyuki679bc9f2006-03-27 01:15:58 -080086 }
Johannes Weiner636cc402008-07-23 21:28:03 -070087 list_add_tail(&bdata->list, iter);
KAMEZAWA Hiroyuki679bc9f2006-03-27 01:15:58 -080088}
89
Franck Bui-Huubbc7b922006-09-25 23:31:07 -070090/*
Linus Torvalds1da177e2005-04-16 15:20:36 -070091 * Called once to set up the allocator itself.
92 */
Johannes Weiner8ae04462008-07-23 21:26:59 -070093static unsigned long __init init_bootmem_core(bootmem_data_t *bdata,
Linus Torvalds1da177e2005-04-16 15:20:36 -070094 unsigned long mapstart, unsigned long start, unsigned long end)
95{
Franck Bui-Huubbc7b922006-09-25 23:31:07 -070096 unsigned long mapsize;
Linus Torvalds1da177e2005-04-16 15:20:36 -070097
Mel Gorman2dbb51c2008-07-23 21:26:52 -070098 mminit_validate_memmodel_limits(&start, &end);
Franck Bui-Huubbc7b922006-09-25 23:31:07 -070099 bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart));
Johannes Weiner3560e242008-07-23 21:28:09 -0700100 bdata->node_min_pfn = start;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700101 bdata->node_low_pfn = end;
KAMEZAWA Hiroyuki679bc9f2006-03-27 01:15:58 -0800102 link_bootmem(bdata);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103
104 /*
105 * Initially all pages are reserved - setup_arch() has to
106 * register free RAM areas explicitly.
107 */
Johannes Weinerdf049a52008-07-23 21:28:02 -0700108 mapsize = bootmap_bytes(end - start);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 memset(bdata->node_bootmem_map, 0xff, mapsize);
110
Johannes Weiner2e5237d2008-07-23 21:28:02 -0700111 bdebug("nid=%td start=%lx map=%lx end=%lx mapsize=%lx\n",
112 bdata - bootmem_node_data, start, mapstart, end, mapsize);
113
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114 return mapsize;
115}
116
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700117/**
118 * init_bootmem_node - register a node as boot memory
119 * @pgdat: node to register
120 * @freepfn: pfn where the bitmap for this node is to be placed
121 * @startpfn: first pfn on the node
122 * @endpfn: first pfn after the node
123 *
124 * Returns the number of bytes needed to hold the bitmap for this node.
125 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700126unsigned long __init init_bootmem_node(pg_data_t *pgdat, unsigned long freepfn,
127 unsigned long startpfn, unsigned long endpfn)
128{
129 return init_bootmem_core(pgdat->bdata, freepfn, startpfn, endpfn);
130}
131
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700132/**
133 * init_bootmem - register boot memory
134 * @start: pfn where the bitmap is to be placed
135 * @pages: number of available physical pages
136 *
137 * Returns the number of bytes needed to hold the bitmap.
138 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700139unsigned long __init init_bootmem(unsigned long start, unsigned long pages)
140{
141 max_low_pfn = pages;
142 min_low_pfn = start;
143 return init_bootmem_core(NODE_DATA(0)->bdata, start, 0, pages);
144}
145
146static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
147{
Johannes Weiner41546c12008-07-23 21:28:03 -0700148 int aligned;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700149 struct page *page;
Johannes Weiner41546c12008-07-23 21:28:03 -0700150 unsigned long start, end, pages, count = 0;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700151
Johannes Weiner41546c12008-07-23 21:28:03 -0700152 if (!bdata->node_bootmem_map)
153 return 0;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700154
Johannes Weiner3560e242008-07-23 21:28:09 -0700155 start = bdata->node_min_pfn;
Johannes Weiner41546c12008-07-23 21:28:03 -0700156 end = bdata->node_low_pfn;
157
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700158 /*
Johannes Weiner41546c12008-07-23 21:28:03 -0700159 * If the start is aligned to the machines wordsize, we might
160 * be able to free pages in bulks of that order.
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700161 */
Johannes Weiner41546c12008-07-23 21:28:03 -0700162 aligned = !(start & (BITS_PER_LONG - 1));
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700163
Johannes Weiner41546c12008-07-23 21:28:03 -0700164 bdebug("nid=%td start=%lx end=%lx aligned=%d\n",
165 bdata - bootmem_node_data, start, end, aligned);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700166
Johannes Weiner41546c12008-07-23 21:28:03 -0700167 while (start < end) {
168 unsigned long *map, idx, vec;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700169
Johannes Weiner41546c12008-07-23 21:28:03 -0700170 map = bdata->node_bootmem_map;
Johannes Weiner3560e242008-07-23 21:28:09 -0700171 idx = start - bdata->node_min_pfn;
Johannes Weiner41546c12008-07-23 21:28:03 -0700172 vec = ~map[idx / BITS_PER_LONG];
173
174 if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) {
175 int order = ilog2(BITS_PER_LONG);
176
177 __free_pages_bootmem(pfn_to_page(start), order);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700178 count += BITS_PER_LONG;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700179 } else {
Johannes Weiner41546c12008-07-23 21:28:03 -0700180 unsigned long off = 0;
181
182 while (vec && off < BITS_PER_LONG) {
183 if (vec & 1) {
184 page = pfn_to_page(start + off);
185 __free_pages_bootmem(page, 0);
186 count++;
187 }
188 vec >>= 1;
189 off++;
190 }
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700191 }
Johannes Weiner41546c12008-07-23 21:28:03 -0700192 start += BITS_PER_LONG;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700193 }
194
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700195 page = virt_to_page(bdata->node_bootmem_map);
Johannes Weiner3560e242008-07-23 21:28:09 -0700196 pages = bdata->node_low_pfn - bdata->node_min_pfn;
Johannes Weiner41546c12008-07-23 21:28:03 -0700197 pages = bootmem_bootmap_pages(pages);
198 count += pages;
199 while (pages--)
200 __free_pages_bootmem(page++, 0);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700201
Johannes Weiner2e5237d2008-07-23 21:28:02 -0700202 bdebug("nid=%td released=%lx\n", bdata - bootmem_node_data, count);
203
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700204 return count;
205}
206
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700207/**
208 * free_all_bootmem_node - release a node's free pages to the buddy allocator
209 * @pgdat: node to be released
210 *
211 * Returns the number of pages actually released.
212 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700213unsigned long __init free_all_bootmem_node(pg_data_t *pgdat)
214{
215 register_page_bootmem_info_node(pgdat);
216 return free_all_bootmem_core(pgdat->bdata);
217}
218
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700219/**
220 * free_all_bootmem - release free pages to the buddy allocator
221 *
222 * Returns the number of pages actually released.
223 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700224unsigned long __init free_all_bootmem(void)
225{
226 return free_all_bootmem_core(NODE_DATA(0)->bdata);
227}
228
Johannes Weinerd747fa42008-07-23 21:28:05 -0700229static void __init __free(bootmem_data_t *bdata,
230 unsigned long sidx, unsigned long eidx)
231{
232 unsigned long idx;
233
234 bdebug("nid=%td start=%lx end=%lx\n", bdata - bootmem_node_data,
Johannes Weiner3560e242008-07-23 21:28:09 -0700235 sidx + bdata->node_min_pfn,
236 eidx + bdata->node_min_pfn);
Johannes Weinerd747fa42008-07-23 21:28:05 -0700237
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700238 if (bdata->hint_idx > sidx)
239 bdata->hint_idx = sidx;
240
Johannes Weinerd747fa42008-07-23 21:28:05 -0700241 for (idx = sidx; idx < eidx; idx++)
242 if (!test_and_clear_bit(idx, bdata->node_bootmem_map))
243 BUG();
244}
245
246static int __init __reserve(bootmem_data_t *bdata, unsigned long sidx,
247 unsigned long eidx, int flags)
248{
249 unsigned long idx;
250 int exclusive = flags & BOOTMEM_EXCLUSIVE;
251
252 bdebug("nid=%td start=%lx end=%lx flags=%x\n",
253 bdata - bootmem_node_data,
Johannes Weiner3560e242008-07-23 21:28:09 -0700254 sidx + bdata->node_min_pfn,
255 eidx + bdata->node_min_pfn,
Johannes Weinerd747fa42008-07-23 21:28:05 -0700256 flags);
257
258 for (idx = sidx; idx < eidx; idx++)
259 if (test_and_set_bit(idx, bdata->node_bootmem_map)) {
260 if (exclusive) {
261 __free(bdata, sidx, idx);
262 return -EBUSY;
263 }
264 bdebug("silent double reserve of PFN %lx\n",
Johannes Weiner3560e242008-07-23 21:28:09 -0700265 idx + bdata->node_min_pfn);
Johannes Weinerd747fa42008-07-23 21:28:05 -0700266 }
267 return 0;
268}
269
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700270static int __init mark_bootmem_node(bootmem_data_t *bdata,
271 unsigned long start, unsigned long end,
272 int reserve, int flags)
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700273{
274 unsigned long sidx, eidx;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700275
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700276 bdebug("nid=%td start=%lx end=%lx reserve=%d flags=%x\n",
277 bdata - bootmem_node_data, start, end, reserve, flags);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700278
Johannes Weiner3560e242008-07-23 21:28:09 -0700279 BUG_ON(start < bdata->node_min_pfn);
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700280 BUG_ON(end > bdata->node_low_pfn);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700281
Johannes Weiner3560e242008-07-23 21:28:09 -0700282 sidx = start - bdata->node_min_pfn;
283 eidx = end - bdata->node_min_pfn;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700284
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700285 if (reserve)
286 return __reserve(bdata, sidx, eidx, flags);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700287 else
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700288 __free(bdata, sidx, eidx);
289 return 0;
290}
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700291
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700292static int __init mark_bootmem(unsigned long start, unsigned long end,
293 int reserve, int flags)
294{
295 unsigned long pos;
296 bootmem_data_t *bdata;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700297
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700298 pos = start;
299 list_for_each_entry(bdata, &bdata_list, list) {
300 int err;
301 unsigned long max;
302
Johannes Weiner3560e242008-07-23 21:28:09 -0700303 if (pos < bdata->node_min_pfn ||
304 pos >= bdata->node_low_pfn) {
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700305 BUG_ON(pos != start);
306 continue;
307 }
308
309 max = min(bdata->node_low_pfn, end);
310
311 err = mark_bootmem_node(bdata, pos, max, reserve, flags);
312 if (reserve && err) {
313 mark_bootmem(start, pos, 0, 0);
314 return err;
315 }
316
317 if (max == end)
318 return 0;
319 pos = bdata->node_low_pfn;
320 }
321 BUG();
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700322}
323
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700324/**
325 * free_bootmem_node - mark a page range as usable
326 * @pgdat: node the range resides on
327 * @physaddr: starting address of the range
328 * @size: size of the range in bytes
329 *
330 * Partial pages will be considered reserved and left as they are.
331 *
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700332 * The range must reside completely on the specified node.
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700333 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700334void __init free_bootmem_node(pg_data_t *pgdat, unsigned long physaddr,
335 unsigned long size)
336{
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700337 unsigned long start, end;
338
Catalin Marinasec3a3542009-07-07 10:33:01 +0100339 kmemleak_free_part(__va(physaddr), size);
340
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700341 start = PFN_UP(physaddr);
342 end = PFN_DOWN(physaddr + size);
343
344 mark_bootmem_node(pgdat->bdata, start, end, 0, 0);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700345}
346
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700347/**
348 * free_bootmem - mark a page range as usable
349 * @addr: starting address of the range
350 * @size: size of the range in bytes
351 *
352 * Partial pages will be considered reserved and left as they are.
353 *
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700354 * The range must be contiguous but may span node boundaries.
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700355 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700356void __init free_bootmem(unsigned long addr, unsigned long size)
357{
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700358 unsigned long start, end;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700359
Catalin Marinasec3a3542009-07-07 10:33:01 +0100360 kmemleak_free_part(__va(addr), size);
361
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700362 start = PFN_UP(addr);
363 end = PFN_DOWN(addr + size);
Yinghai Lua5645a62008-03-18 12:49:12 -0700364
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700365 mark_bootmem(start, end, 0, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366}
367
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700368/**
369 * reserve_bootmem_node - mark a page range as reserved
370 * @pgdat: node the range resides on
371 * @physaddr: starting address of the range
372 * @size: size of the range in bytes
373 * @flags: reservation flags (see linux/bootmem.h)
374 *
375 * Partial pages will be reserved.
376 *
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700377 * The range must reside completely on the specified node.
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700378 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700379int __init reserve_bootmem_node(pg_data_t *pgdat, unsigned long physaddr,
380 unsigned long size, int flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381{
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700382 unsigned long start, end;
Franck Bui-Huubbc7b922006-09-25 23:31:07 -0700383
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700384 start = PFN_DOWN(physaddr);
385 end = PFN_UP(physaddr + size);
386
387 return mark_bootmem_node(pgdat->bdata, start, end, 1, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388}
389
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700390/**
391 * reserve_bootmem - mark a page range as usable
392 * @addr: starting address of the range
393 * @size: size of the range in bytes
394 * @flags: reservation flags (see linux/bootmem.h)
395 *
396 * Partial pages will be reserved.
397 *
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700398 * The range must be contiguous but may span node boundaries.
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700399 */
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700400int __init reserve_bootmem(unsigned long addr, unsigned long size,
401 int flags)
402{
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700403 unsigned long start, end;
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700404
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700405 start = PFN_DOWN(addr);
406 end = PFN_UP(addr + size);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700407
Johannes Weinere2bf3ca2008-07-23 21:28:06 -0700408 return mark_bootmem(start, end, 1, flags);
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700409}
Johannes Weiner223e8dc2008-07-23 21:28:00 -0700410
Johannes Weiner481ebd02008-08-20 14:09:15 -0700411static unsigned long align_idx(struct bootmem_data *bdata, unsigned long idx,
412 unsigned long step)
413{
414 unsigned long base = bdata->node_min_pfn;
415
416 /*
417 * Align the index with respect to the node start so that the
418 * combination of both satisfies the requested alignment.
419 */
420
421 return ALIGN(base + idx, step) - base;
422}
423
424static unsigned long align_off(struct bootmem_data *bdata, unsigned long off,
425 unsigned long align)
426{
427 unsigned long base = PFN_PHYS(bdata->node_min_pfn);
428
429 /* Same as align_idx for byte offsets */
430
431 return ALIGN(base + off, align) - base;
432}
433
Tejun Heod0c4f572009-03-01 16:06:56 +0900434static void * __init alloc_bootmem_core(struct bootmem_data *bdata,
435 unsigned long size, unsigned long align,
436 unsigned long goal, unsigned long limit)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700437{
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700438 unsigned long fallback = 0;
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700439 unsigned long min, max, start, sidx, midx, step;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700440
Johannes Weiner594fe1a2009-01-06 14:40:32 -0800441 bdebug("nid=%td size=%lx [%lu pages] align=%lx goal=%lx limit=%lx\n",
442 bdata - bootmem_node_data, size, PAGE_ALIGN(size) >> PAGE_SHIFT,
443 align, goal, limit);
444
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700445 BUG_ON(!size);
446 BUG_ON(align & (align - 1));
447 BUG_ON(limit && goal + size > limit);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448
Christian Krafft7c309a62006-12-06 20:32:41 -0800449 if (!bdata->node_bootmem_map)
450 return NULL;
451
Johannes Weiner3560e242008-07-23 21:28:09 -0700452 min = bdata->node_min_pfn;
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700453 max = bdata->node_low_pfn;
Yinghai Lu9a2dc042008-03-18 12:44:48 -0700454
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700455 goal >>= PAGE_SHIFT;
456 limit >>= PAGE_SHIFT;
457
458 if (limit && max > limit)
459 max = limit;
460 if (max <= min)
Yinghai Lu9a2dc042008-03-18 12:44:48 -0700461 return NULL;
462
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700463 step = max(align >> PAGE_SHIFT, 1UL);
Yasunori Goto281dd252005-10-19 15:52:18 -0700464
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700465 if (goal && min < goal && goal < max)
466 start = ALIGN(goal, step);
467 else
468 start = ALIGN(min, step);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469
Johannes Weiner481ebd02008-08-20 14:09:15 -0700470 sidx = start - bdata->node_min_pfn;
Johannes Weiner3560e242008-07-23 21:28:09 -0700471 midx = max - bdata->node_min_pfn;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700472
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700473 if (bdata->hint_idx > sidx) {
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700474 /*
475 * Handle the valid case of sidx being zero and still
476 * catch the fallback below.
477 */
478 fallback = sidx + 1;
Johannes Weiner481ebd02008-08-20 14:09:15 -0700479 sidx = align_idx(bdata, bdata->hint_idx, step);
Yinghai Luad093152008-03-10 23:23:42 -0700480 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700482 while (1) {
483 int merge;
484 void *region;
485 unsigned long eidx, i, start_off, end_off;
486find_block:
487 sidx = find_next_zero_bit(bdata->node_bootmem_map, midx, sidx);
Johannes Weiner481ebd02008-08-20 14:09:15 -0700488 sidx = align_idx(bdata, sidx, step);
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700489 eidx = sidx + PFN_UP(size);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700491 if (sidx >= midx || eidx > midx)
Haren Myneni66d43e92005-12-12 00:37:39 -0800492 break;
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700493
494 for (i = sidx; i < eidx; i++)
495 if (test_bit(i, bdata->node_bootmem_map)) {
Johannes Weiner481ebd02008-08-20 14:09:15 -0700496 sidx = align_idx(bdata, i, step);
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700497 if (sidx == i)
498 sidx += step;
499 goto find_block;
500 }
501
Mikulas Patocka627240a2008-08-15 00:40:17 -0700502 if (bdata->last_end_off & (PAGE_SIZE - 1) &&
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700503 PFN_DOWN(bdata->last_end_off) + 1 == sidx)
Johannes Weiner481ebd02008-08-20 14:09:15 -0700504 start_off = align_off(bdata, bdata->last_end_off, align);
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700505 else
506 start_off = PFN_PHYS(sidx);
507
508 merge = PFN_DOWN(start_off) < sidx;
509 end_off = start_off + size;
510
511 bdata->last_end_off = end_off;
512 bdata->hint_idx = PFN_UP(end_off);
513
514 /*
515 * Reserve the area now:
516 */
Johannes Weinerd747fa42008-07-23 21:28:05 -0700517 if (__reserve(bdata, PFN_DOWN(start_off) + merge,
518 PFN_UP(end_off), BOOTMEM_EXCLUSIVE))
519 BUG();
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700520
Johannes Weiner3560e242008-07-23 21:28:09 -0700521 region = phys_to_virt(PFN_PHYS(bdata->node_min_pfn) +
522 start_off);
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700523 memset(region, 0, size);
Catalin Marinas008139d2009-08-27 14:29:17 +0100524 /*
525 * The min_count is set to 0 so that bootmem allocated blocks
526 * are never reported as leaks.
527 */
528 kmemleak_alloc(region, size, 0, 0);
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700529 return region;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700530 }
531
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700532 if (fallback) {
Johannes Weiner481ebd02008-08-20 14:09:15 -0700533 sidx = align_idx(bdata, fallback - 1, step);
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700534 fallback = 0;
535 goto find_block;
536 }
537
538 return NULL;
539}
540
Tejun Heod0c4f572009-03-01 16:06:56 +0900541static void * __init alloc_arch_preferred_bootmem(bootmem_data_t *bdata,
542 unsigned long size, unsigned long align,
543 unsigned long goal, unsigned long limit)
544{
Pekka Enberg441c7e02009-06-10 20:05:53 +0300545 if (WARN_ON_ONCE(slab_is_available()))
546 return kzalloc(size, GFP_NOWAIT);
547
Tejun Heod0c4f572009-03-01 16:06:56 +0900548#ifdef CONFIG_HAVE_ARCH_BOOTMEM
Joe Perches433f13a2009-06-18 16:48:58 -0700549 {
550 bootmem_data_t *p_bdata;
Tejun Heod0c4f572009-03-01 16:06:56 +0900551
Joe Perches433f13a2009-06-18 16:48:58 -0700552 p_bdata = bootmem_arch_preferred_node(bdata, size, align,
553 goal, limit);
554 if (p_bdata)
555 return alloc_bootmem_core(p_bdata, size, align,
556 goal, limit);
557 }
Tejun Heod0c4f572009-03-01 16:06:56 +0900558#endif
559 return NULL;
560}
561
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700562static void * __init ___alloc_bootmem_nopanic(unsigned long size,
563 unsigned long align,
564 unsigned long goal,
565 unsigned long limit)
566{
567 bootmem_data_t *bdata;
Tejun Heod0c4f572009-03-01 16:06:56 +0900568 void *region;
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700569
570restart:
Tejun Heod0c4f572009-03-01 16:06:56 +0900571 region = alloc_arch_preferred_bootmem(NULL, size, align, goal, limit);
572 if (region)
573 return region;
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700574
Tejun Heod0c4f572009-03-01 16:06:56 +0900575 list_for_each_entry(bdata, &bdata_list, list) {
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700576 if (goal && bdata->node_low_pfn <= PFN_DOWN(goal))
577 continue;
Johannes Weiner3560e242008-07-23 21:28:09 -0700578 if (limit && bdata->node_min_pfn >= PFN_DOWN(limit))
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700579 break;
580
581 region = alloc_bootmem_core(bdata, size, align, goal, limit);
582 if (region)
583 return region;
584 }
585
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700586 if (goal) {
587 goal = 0;
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700588 goto restart;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589 }
Johannes Weiner5f2809e2008-07-23 21:28:05 -0700590
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700592}
593
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700594/**
595 * __alloc_bootmem_nopanic - allocate boot memory without panicking
596 * @size: size of the request in bytes
597 * @align: alignment of the region
598 * @goal: preferred starting address of the region
599 *
600 * The goal is dropped if it can not be satisfied and the allocation will
601 * fall back to memory below @goal.
602 *
603 * Allocation may happen on any node in the system.
604 *
605 * Returns NULL on failure.
606 */
Franck Bui-Huubb0923a2006-09-25 23:31:05 -0700607void * __init __alloc_bootmem_nopanic(unsigned long size, unsigned long align,
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700608 unsigned long goal)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700609{
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700610 return ___alloc_bootmem_nopanic(size, align, goal, 0);
611}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700613static void * __init ___alloc_bootmem(unsigned long size, unsigned long align,
614 unsigned long goal, unsigned long limit)
615{
616 void *mem = ___alloc_bootmem_nopanic(size, align, goal, limit);
617
618 if (mem)
619 return mem;
620 /*
621 * Whoops, we cannot satisfy the allocation request.
622 */
623 printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
624 panic("Out of memory");
Andi Kleena8062232006-04-07 19:49:21 +0200625 return NULL;
626}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700628/**
629 * __alloc_bootmem - allocate boot memory
630 * @size: size of the request in bytes
631 * @align: alignment of the region
632 * @goal: preferred starting address of the region
633 *
634 * The goal is dropped if it can not be satisfied and the allocation will
635 * fall back to memory below @goal.
636 *
637 * Allocation may happen on any node in the system.
638 *
639 * The function panics if the request can not be satisfied.
640 */
Franck Bui-Huubb0923a2006-09-25 23:31:05 -0700641void * __init __alloc_bootmem(unsigned long size, unsigned long align,
642 unsigned long goal)
Andi Kleena8062232006-04-07 19:49:21 +0200643{
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700644 return ___alloc_bootmem(size, align, goal, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645}
646
Johannes Weiner4cc278b2008-07-23 21:28:08 -0700647static void * __init ___alloc_bootmem_node(bootmem_data_t *bdata,
648 unsigned long size, unsigned long align,
649 unsigned long goal, unsigned long limit)
650{
651 void *ptr;
652
Tejun Heod0c4f572009-03-01 16:06:56 +0900653 ptr = alloc_arch_preferred_bootmem(bdata, size, align, goal, limit);
654 if (ptr)
655 return ptr;
656
Johannes Weiner4cc278b2008-07-23 21:28:08 -0700657 ptr = alloc_bootmem_core(bdata, size, align, goal, limit);
658 if (ptr)
659 return ptr;
660
661 return ___alloc_bootmem(size, align, goal, limit);
662}
663
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700664/**
665 * __alloc_bootmem_node - allocate boot memory from a specific node
666 * @pgdat: node to allocate from
667 * @size: size of the request in bytes
668 * @align: alignment of the region
669 * @goal: preferred starting address of the region
670 *
671 * The goal is dropped if it can not be satisfied and the allocation will
672 * fall back to memory below @goal.
673 *
674 * Allocation may fall back to any node in the system if the specified node
675 * can not hold the requested memory.
676 *
677 * The function panics if the request can not be satisfied.
678 */
Franck Bui-Huubb0923a2006-09-25 23:31:05 -0700679void * __init __alloc_bootmem_node(pg_data_t *pgdat, unsigned long size,
680 unsigned long align, unsigned long goal)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681{
Pekka Enbergc91c4772009-06-11 08:10:28 +0300682 if (WARN_ON_ONCE(slab_is_available()))
683 return kzalloc_node(size, GFP_NOWAIT, pgdat->node_id);
684
Johannes Weiner4cc278b2008-07-23 21:28:08 -0700685 return ___alloc_bootmem_node(pgdat->bdata, size, align, goal, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700686}
687
Yasunori Gotoe70260a2008-04-28 02:13:32 -0700688#ifdef CONFIG_SPARSEMEM
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700689/**
690 * alloc_bootmem_section - allocate boot memory from a specific section
691 * @size: size of the request in bytes
692 * @section_nr: sparse map section to allocate from
693 *
694 * Return NULL on failure.
695 */
Yasunori Gotoe70260a2008-04-28 02:13:32 -0700696void * __init alloc_bootmem_section(unsigned long size,
697 unsigned long section_nr)
698{
Johannes Weiner75a56cf2008-07-23 21:28:09 -0700699 bootmem_data_t *bdata;
700 unsigned long pfn, goal, limit;
Yasunori Gotoe70260a2008-04-28 02:13:32 -0700701
702 pfn = section_nr_to_pfn(section_nr);
Johannes Weiner75a56cf2008-07-23 21:28:09 -0700703 goal = pfn << PAGE_SHIFT;
704 limit = section_nr_to_pfn(section_nr + 1) << PAGE_SHIFT;
705 bdata = &bootmem_node_data[early_pfn_to_nid(pfn)];
Yasunori Gotoe70260a2008-04-28 02:13:32 -0700706
Johannes Weiner75a56cf2008-07-23 21:28:09 -0700707 return alloc_bootmem_core(bdata, size, SMP_CACHE_BYTES, goal, limit);
Yasunori Gotoe70260a2008-04-28 02:13:32 -0700708}
709#endif
710
Andi Kleenb54bbf72008-07-23 21:27:45 -0700711void * __init __alloc_bootmem_node_nopanic(pg_data_t *pgdat, unsigned long size,
712 unsigned long align, unsigned long goal)
713{
714 void *ptr;
715
Pekka Enbergc91c4772009-06-11 08:10:28 +0300716 if (WARN_ON_ONCE(slab_is_available()))
717 return kzalloc_node(size, GFP_NOWAIT, pgdat->node_id);
718
Tejun Heod0c4f572009-03-01 16:06:56 +0900719 ptr = alloc_arch_preferred_bootmem(pgdat->bdata, size, align, goal, 0);
720 if (ptr)
721 return ptr;
722
Andi Kleenb54bbf72008-07-23 21:27:45 -0700723 ptr = alloc_bootmem_core(pgdat->bdata, size, align, goal, 0);
724 if (ptr)
725 return ptr;
726
727 return __alloc_bootmem_nopanic(size, align, goal);
728}
729
Heiko Carstensdfd54cb2006-09-25 23:31:33 -0700730#ifndef ARCH_LOW_ADDRESS_LIMIT
731#define ARCH_LOW_ADDRESS_LIMIT 0xffffffffUL
732#endif
Ravikiran G Thirumalai008857c2006-01-06 00:11:01 -0800733
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700734/**
735 * __alloc_bootmem_low - allocate low boot memory
736 * @size: size of the request in bytes
737 * @align: alignment of the region
738 * @goal: preferred starting address of the region
739 *
740 * The goal is dropped if it can not be satisfied and the allocation will
741 * fall back to memory below @goal.
742 *
743 * Allocation may happen on any node in the system.
744 *
745 * The function panics if the request can not be satisfied.
746 */
Franck Bui-Huubb0923a2006-09-25 23:31:05 -0700747void * __init __alloc_bootmem_low(unsigned long size, unsigned long align,
748 unsigned long goal)
Ravikiran G Thirumalai008857c2006-01-06 00:11:01 -0800749{
Johannes Weiner0f3caba2008-07-23 21:28:07 -0700750 return ___alloc_bootmem(size, align, goal, ARCH_LOW_ADDRESS_LIMIT);
Ravikiran G Thirumalai008857c2006-01-06 00:11:01 -0800751}
752
Johannes Weinera66fd7d2008-07-23 21:28:01 -0700753/**
754 * __alloc_bootmem_low_node - allocate low boot memory from a specific node
755 * @pgdat: node to allocate from
756 * @size: size of the request in bytes
757 * @align: alignment of the region
758 * @goal: preferred starting address of the region
759 *
760 * The goal is dropped if it can not be satisfied and the allocation will
761 * fall back to memory below @goal.
762 *
763 * Allocation may fall back to any node in the system if the specified node
764 * can not hold the requested memory.
765 *
766 * The function panics if the request can not be satisfied.
767 */
Ravikiran G Thirumalai008857c2006-01-06 00:11:01 -0800768void * __init __alloc_bootmem_low_node(pg_data_t *pgdat, unsigned long size,
769 unsigned long align, unsigned long goal)
770{
Pekka Enbergc91c4772009-06-11 08:10:28 +0300771 if (WARN_ON_ONCE(slab_is_available()))
772 return kzalloc_node(size, GFP_NOWAIT, pgdat->node_id);
773
Johannes Weiner4cc278b2008-07-23 21:28:08 -0700774 return ___alloc_bootmem_node(pgdat->bdata, size, align,
775 goal, ARCH_LOW_ADDRESS_LIMIT);
Ravikiran G Thirumalai008857c2006-01-06 00:11:01 -0800776}