bootmem.c 11.9 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1
2
3
4
5
6
7
8
9
10
11
/*
 *  linux/mm/bootmem.c
 *
 *  Copyright (C) 1999 Ingo Molnar
 *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
 *
 *  simple boot-time physical memory area allocator and
 *  free memory collector. It's used to deal with reserved
 *  system memory and memory holes as well.
 */
#include <linux/init.h>
12
#include <linux/pfn.h>
Linus Torvalds's avatar
Linus Torvalds committed
13
14
#include <linux/bootmem.h>
#include <linux/module.h>
15
16

#include <asm/bug.h>
Linus Torvalds's avatar
Linus Torvalds committed
17
#include <asm/io.h>
18

Linus Torvalds's avatar
Linus Torvalds committed
19
20
21
22
23
24
25
26
27
28
#include "internal.h"

/*
 * Access to this subsystem has to be serialized externally. (this is
 * true for the boot process anyway)
 */
unsigned long max_low_pfn;
unsigned long min_low_pfn;
unsigned long max_pfn;

29
EXPORT_UNUSED_SYMBOL(max_pfn);  /*  June 2006  */
Linus Torvalds's avatar
Linus Torvalds committed
30

31
static LIST_HEAD(bdata_list);
32
33
34
35
36
37
38
39
#ifdef CONFIG_CRASH_DUMP
/*
 * If we have booted due to a crash, max_pfn will be a very low value. We need
 * to know the amount of memory that the previous kernel used.
 */
unsigned long saved_max_pfn;
#endif

Linus Torvalds's avatar
Linus Torvalds committed
40
41
42
43
44
45
46
47
48
49
50
/* return the number of _pages_ that will be allocated for the boot bitmap */
unsigned long __init bootmem_bootmap_pages (unsigned long pages)
{
	unsigned long mapsize;

	mapsize = (pages+7)/8;
	mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK;
	mapsize >>= PAGE_SHIFT;

	return mapsize;
}
51
52
53
/*
 * link bdata in order
 */
54
static void __init link_bootmem(bootmem_data_t *bdata)
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
{
	bootmem_data_t *ent;
	if (list_empty(&bdata_list)) {
		list_add(&bdata->list, &bdata_list);
		return;
	}
	/* insert in order */
	list_for_each_entry(ent, &bdata_list, list) {
		if (bdata->node_boot_start < ent->node_boot_start) {
			list_add_tail(&bdata->list, &ent->list);
			return;
		}
	}
	list_add_tail(&bdata->list, &bdata_list);
	return;
}

72
73
74
75
76
77
78
79
80
81
82
83
/*
 * Given an initialised bdata, it returns the size of the boot bitmap
 */
static unsigned long __init get_mapsize(bootmem_data_t *bdata)
{
	unsigned long mapsize;
	unsigned long start = PFN_DOWN(bdata->node_boot_start);
	unsigned long end = bdata->node_low_pfn;

	mapsize = ((end - start) + 7) / 8;
	return ALIGN(mapsize, sizeof(long));
}
Linus Torvalds's avatar
Linus Torvalds committed
84
85
86
87
88
89
90
91

/*
 * Called once to set up the allocator itself.
 */
static unsigned long __init init_bootmem_core (pg_data_t *pgdat,
	unsigned long mapstart, unsigned long start, unsigned long end)
{
	bootmem_data_t *bdata = pgdat->bdata;
92
	unsigned long mapsize;
Linus Torvalds's avatar
Linus Torvalds committed
93

94
95
	bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart));
	bdata->node_boot_start = PFN_PHYS(start);
Linus Torvalds's avatar
Linus Torvalds committed
96
	bdata->node_low_pfn = end;
97
	link_bootmem(bdata);
Linus Torvalds's avatar
Linus Torvalds committed
98
99
100
101
102

	/*
	 * Initially all pages are reserved - setup_arch() has to
	 * register free RAM areas explicitly.
	 */
103
	mapsize = get_mapsize(bdata);
Linus Torvalds's avatar
Linus Torvalds committed
104
105
106
107
108
109
110
111
112
113
	memset(bdata->node_bootmem_map, 0xff, mapsize);

	return mapsize;
}

/*
 * Marks a particular physical memory range as unallocatable. Usable RAM
 * might be used for boot-time allocations - or it might get added
 * to the free page pool later on.
 */
114
115
static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr,
					unsigned long size)
Linus Torvalds's avatar
Linus Torvalds committed
116
{
117
	unsigned long sidx, eidx;
Linus Torvalds's avatar
Linus Torvalds committed
118
	unsigned long i;
119

Linus Torvalds's avatar
Linus Torvalds committed
120
121
122
123
124
	/*
	 * round up, partially reserved pages are considered
	 * fully reserved.
	 */
	BUG_ON(!size);
125
126
127
128
129
	BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn);
	BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn);

	sidx = PFN_DOWN(addr - bdata->node_boot_start);
	eidx = PFN_UP(addr + size - bdata->node_boot_start);
Linus Torvalds's avatar
Linus Torvalds committed
130
131
132
133
134
135
136
137
138

	for (i = sidx; i < eidx; i++)
		if (test_and_set_bit(i, bdata->node_bootmem_map)) {
#ifdef CONFIG_DEBUG_BOOTMEM
			printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
#endif
		}
}

139
140
static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr,
				     unsigned long size)
Linus Torvalds's avatar
Linus Torvalds committed
141
{
142
	unsigned long sidx, eidx;
Linus Torvalds's avatar
Linus Torvalds committed
143
	unsigned long i;
144

Linus Torvalds's avatar
Linus Torvalds committed
145
146
147
148
149
	/*
	 * round down end of usable mem, partially free pages are
	 * considered reserved.
	 */
	BUG_ON(!size);
150
	BUG_ON(PFN_DOWN(addr + size) > bdata->node_low_pfn);
Linus Torvalds's avatar
Linus Torvalds committed
151
152
153
154
155
156
157

	if (addr < bdata->last_success)
		bdata->last_success = addr;

	/*
	 * Round up the beginning of the address.
	 */
158
159
	sidx = PFN_UP(addr) - PFN_DOWN(bdata->node_boot_start);
	eidx = PFN_DOWN(addr + size - bdata->node_boot_start);
Linus Torvalds's avatar
Linus Torvalds committed
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

	for (i = sidx; i < eidx; i++) {
		if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map)))
			BUG();
	}
}

/*
 * We 'merge' subsequent allocations to save space. We might 'lose'
 * some fraction of a page if allocations cannot be satisfied due to
 * size constraints on boxes where there is physical RAM space
 * fragmentation - in these cases (mostly large memory boxes) this
 * is not a problem.
 *
 * On low memory boxes we get it right in 100% of the cases.
 *
 * alignment has to be a power of 2 value.
 *
 * NOTE:  This function is _not_ reentrant.
 */
180
void * __init
Linus Torvalds's avatar
Linus Torvalds committed
181
__alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size,
182
	      unsigned long align, unsigned long goal, unsigned long limit)
Linus Torvalds's avatar
Linus Torvalds committed
183
184
{
	unsigned long offset, remaining_size, areasize, preferred;
185
	unsigned long i, start = 0, incr, eidx, end_pfn;
Linus Torvalds's avatar
Linus Torvalds committed
186
187
188
189
190
191
192
193
	void *ret;

	if(!size) {
		printk("__alloc_bootmem_core(): zero-sized request\n");
		BUG();
	}
	BUG_ON(align & (align-1));

194
195
196
	if (limit && bdata->node_boot_start >= limit)
		return NULL;

197
198
	end_pfn = bdata->node_low_pfn;
	limit = PFN_DOWN(limit);
199
200
201
	if (limit && end_pfn > limit)
		end_pfn = limit;

202
	eidx = end_pfn - PFN_DOWN(bdata->node_boot_start);
Linus Torvalds's avatar
Linus Torvalds committed
203
	offset = 0;
204
205
206
	if (align && (bdata->node_boot_start & (align - 1UL)) != 0)
		offset = align - (bdata->node_boot_start & (align - 1UL));
	offset = PFN_DOWN(offset);
Linus Torvalds's avatar
Linus Torvalds committed
207
208
209
210
211

	/*
	 * We try to allocate bootmem pages above 'goal'
	 * first, then we try to allocate lower pages.
	 */
212
	if (goal && goal >= bdata->node_boot_start && PFN_DOWN(goal) < end_pfn) {
Linus Torvalds's avatar
Linus Torvalds committed
213
214
215
		preferred = goal - bdata->node_boot_start;

		if (bdata->last_success >= preferred)
216
217
			if (!limit || (limit && limit > bdata->last_success))
				preferred = bdata->last_success;
Linus Torvalds's avatar
Linus Torvalds committed
218
219
220
	} else
		preferred = 0;

221
222
	preferred = PFN_DOWN(ALIGN(preferred, align)) + offset;
	areasize = (size + PAGE_SIZE-1) / PAGE_SIZE;
Linus Torvalds's avatar
Linus Torvalds committed
223
224
225
226
227
228
229
	incr = align >> PAGE_SHIFT ? : 1;

restart_scan:
	for (i = preferred; i < eidx; i += incr) {
		unsigned long j;
		i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i);
		i = ALIGN(i, incr);
230
231
		if (i >= eidx)
			break;
Linus Torvalds's avatar
Linus Torvalds committed
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
		if (test_bit(i, bdata->node_bootmem_map))
			continue;
		for (j = i + 1; j < i + areasize; ++j) {
			if (j >= eidx)
				goto fail_block;
			if (test_bit (j, bdata->node_bootmem_map))
				goto fail_block;
		}
		start = i;
		goto found;
	fail_block:
		i = ALIGN(j, incr);
	}

	if (preferred > offset) {
		preferred = offset;
		goto restart_scan;
	}
	return NULL;

found:
253
	bdata->last_success = PFN_PHYS(start);
Linus Torvalds's avatar
Linus Torvalds committed
254
255
256
257
258
259
260
261
262
	BUG_ON(start >= eidx);

	/*
	 * Is the next page of the previous allocation-end the start
	 * of this allocation's buffer? If yes then we can 'merge'
	 * the previous partial page with this allocation.
	 */
	if (align < PAGE_SIZE &&
	    bdata->last_offset && bdata->last_pos+1 == start) {
263
		offset = ALIGN(bdata->last_offset, align);
Linus Torvalds's avatar
Linus Torvalds committed
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
		BUG_ON(offset > PAGE_SIZE);
		remaining_size = PAGE_SIZE-offset;
		if (size < remaining_size) {
			areasize = 0;
			/* last_pos unchanged */
			bdata->last_offset = offset+size;
			ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
						bdata->node_boot_start);
		} else {
			remaining_size = size - remaining_size;
			areasize = (remaining_size+PAGE_SIZE-1)/PAGE_SIZE;
			ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
						bdata->node_boot_start);
			bdata->last_pos = start+areasize-1;
			bdata->last_offset = remaining_size;
		}
		bdata->last_offset &= ~PAGE_MASK;
	} else {
		bdata->last_pos = start + areasize - 1;
		bdata->last_offset = size & ~PAGE_MASK;
		ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
	}

	/*
	 * Reserve the area now:
	 */
	for (i = start; i < start+areasize; i++)
		if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map)))
			BUG();
	memset(ret, 0, size);
	return ret;
}

static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat)
{
	struct page *page;
300
	unsigned long pfn;
Linus Torvalds's avatar
Linus Torvalds committed
301
302
303
304
305
306
307
308
309
310
	bootmem_data_t *bdata = pgdat->bdata;
	unsigned long i, count, total = 0;
	unsigned long idx;
	unsigned long *map; 
	int gofast = 0;

	BUG_ON(!bdata->node_bootmem_map);

	count = 0;
	/* first extant page of the node */
311
312
	pfn = PFN_DOWN(bdata->node_boot_start);
	idx = bdata->node_low_pfn - pfn;
Linus Torvalds's avatar
Linus Torvalds committed
313
314
315
316
317
318
319
	map = bdata->node_bootmem_map;
	/* Check physaddr is O(LOG2(BITS_PER_LONG)) page aligned */
	if (bdata->node_boot_start == 0 ||
	    ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG))
		gofast = 1;
	for (i = 0; i < idx; ) {
		unsigned long v = ~map[i / BITS_PER_LONG];
320

Linus Torvalds's avatar
Linus Torvalds committed
321
		if (gofast && v == ~0UL) {
322
			int order;
Linus Torvalds's avatar
Linus Torvalds committed
323

324
			page = pfn_to_page(pfn);
Linus Torvalds's avatar
Linus Torvalds committed
325
326
			count += BITS_PER_LONG;
			order = ffs(BITS_PER_LONG) - 1;
327
			__free_pages_bootmem(page, order);
Linus Torvalds's avatar
Linus Torvalds committed
328
329
330
331
			i += BITS_PER_LONG;
			page += BITS_PER_LONG;
		} else if (v) {
			unsigned long m;
332
333

			page = pfn_to_page(pfn);
Linus Torvalds's avatar
Linus Torvalds committed
334
335
336
			for (m = 1; m && i < idx; m<<=1, page++, i++) {
				if (v & m) {
					count++;
337
					__free_pages_bootmem(page, 0);
Linus Torvalds's avatar
Linus Torvalds committed
338
339
340
341
342
				}
			}
		} else {
			i+=BITS_PER_LONG;
		}
343
		pfn += BITS_PER_LONG;
Linus Torvalds's avatar
Linus Torvalds committed
344
345
346
347
348
349
350
351
352
	}
	total += count;

	/*
	 * Now free the allocator bitmap itself, it's not
	 * needed anymore:
	 */
	page = virt_to_page(bdata->node_bootmem_map);
	count = 0;
353
354
	idx = (get_mapsize(bdata) + PAGE_SIZE-1) >> PAGE_SHIFT;
	for (i = 0; i < idx; i++, page++) {
355
		__free_pages_bootmem(page, 0);
356
		count++;
Linus Torvalds's avatar
Linus Torvalds committed
357
358
359
360
361
362
363
	}
	total += count;
	bdata->node_bootmem_map = NULL;

	return total;
}

364
365
unsigned long __init init_bootmem_node (pg_data_t *pgdat, unsigned long freepfn,
				unsigned long startpfn, unsigned long endpfn)
Linus Torvalds's avatar
Linus Torvalds committed
366
367
368
369
{
	return(init_bootmem_core(pgdat, freepfn, startpfn, endpfn));
}

370
371
void __init reserve_bootmem_node (pg_data_t *pgdat, unsigned long physaddr,
				  unsigned long size)
Linus Torvalds's avatar
Linus Torvalds committed
372
373
374
375
{
	reserve_bootmem_core(pgdat->bdata, physaddr, size);
}

376
377
void __init free_bootmem_node (pg_data_t *pgdat, unsigned long physaddr,
			       unsigned long size)
Linus Torvalds's avatar
Linus Torvalds committed
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
{
	free_bootmem_core(pgdat->bdata, physaddr, size);
}

unsigned long __init free_all_bootmem_node (pg_data_t *pgdat)
{
	return(free_all_bootmem_core(pgdat));
}

unsigned long __init init_bootmem (unsigned long start, unsigned long pages)
{
	max_low_pfn = pages;
	min_low_pfn = start;
	return(init_bootmem_core(NODE_DATA(0), start, 0, pages));
}

#ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE
void __init reserve_bootmem (unsigned long addr, unsigned long size)
{
	reserve_bootmem_core(NODE_DATA(0)->bdata, addr, size);
}
#endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */

void __init free_bootmem (unsigned long addr, unsigned long size)
{
	free_bootmem_core(NODE_DATA(0)->bdata, addr, size);
}

unsigned long __init free_all_bootmem (void)
{
	return(free_all_bootmem_core(NODE_DATA(0)));
}

411
412
void * __init __alloc_bootmem_nopanic(unsigned long size, unsigned long align,
				      unsigned long goal)
Linus Torvalds's avatar
Linus Torvalds committed
413
{
414
	bootmem_data_t *bdata;
Linus Torvalds's avatar
Linus Torvalds committed
415
416
	void *ptr;

417
418
	list_for_each_entry(bdata, &bdata_list, list)
		if ((ptr = __alloc_bootmem_core(bdata, size, align, goal, 0)))
Linus Torvalds's avatar
Linus Torvalds committed
419
			return(ptr);
420
421
	return NULL;
}
Linus Torvalds's avatar
Linus Torvalds committed
422

423
424
void * __init __alloc_bootmem(unsigned long size, unsigned long align,
			      unsigned long goal)
425
426
427
428
{
	void *mem = __alloc_bootmem_nopanic(size,align,goal);
	if (mem)
		return mem;
Linus Torvalds's avatar
Linus Torvalds committed
429
430
431
432
433
434
435
436
	/*
	 * Whoops, we cannot satisfy the allocation request.
	 */
	printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
	panic("Out of memory");
	return NULL;
}

437

438
439
void * __init __alloc_bootmem_node(pg_data_t *pgdat, unsigned long size,
				   unsigned long align, unsigned long goal)
Linus Torvalds's avatar
Linus Torvalds committed
440
441
442
{
	void *ptr;

443
	ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal, 0);
Linus Torvalds's avatar
Linus Torvalds committed
444
445
446
	if (ptr)
		return (ptr);

447
	return __alloc_bootmem(size, align, goal);
Linus Torvalds's avatar
Linus Torvalds committed
448
449
}

450
451
#define LOW32LIMIT 0xffffffff

452
453
void * __init __alloc_bootmem_low(unsigned long size, unsigned long align,
				  unsigned long goal)
454
{
455
	bootmem_data_t *bdata;
456
457
	void *ptr;

458
459
	list_for_each_entry(bdata, &bdata_list, list)
		if ((ptr = __alloc_bootmem_core(bdata, size,
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
						 align, goal, LOW32LIMIT)))
			return(ptr);

	/*
	 * Whoops, we cannot satisfy the allocation request.
	 */
	printk(KERN_ALERT "low bootmem alloc of %lu bytes failed!\n", size);
	panic("Out of low memory");
	return NULL;
}

void * __init __alloc_bootmem_low_node(pg_data_t *pgdat, unsigned long size,
				       unsigned long align, unsigned long goal)
{
	return __alloc_bootmem_core(pgdat->bdata, size, align, goal, LOW32LIMIT);
}