page_alloc.c 137 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 *  linux/mm/page_alloc.c
 *
 *  Manages the free list, the system allocates free pages here.
 *  Note that kmalloc() lives in slab.c
 *
 *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
 *  Swap reorganised 29.12.95, Stephen Tweedie
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999
 *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
 *  Zone balancing, Kanoj Sarcar, SGI, Jan 2000
 *  Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002
 *          (lots of bits borrowed from Ingo Molnar & Andrew Morton)
 */

#include <linux/stddef.h>
#include <linux/mm.h>
#include <linux/swap.h>
#include <linux/interrupt.h>
#include <linux/pagemap.h>
22
#include <linux/jiffies.h>
Linus Torvalds's avatar
Linus Torvalds committed
23
24
#include <linux/bootmem.h>
#include <linux/compiler.h>
25
#include <linux/kernel.h>
26
#include <linux/kmemcheck.h>
Linus Torvalds's avatar
Linus Torvalds committed
27
28
29
30
31
#include <linux/module.h>
#include <linux/suspend.h>
#include <linux/pagevec.h>
#include <linux/blkdev.h>
#include <linux/slab.h>
32
#include <linux/oom.h>
Linus Torvalds's avatar
Linus Torvalds committed
33
34
35
36
37
#include <linux/notifier.h>
#include <linux/topology.h>
#include <linux/sysctl.h>
#include <linux/cpu.h>
#include <linux/cpuset.h>
38
#include <linux/memory_hotplug.h>
Linus Torvalds's avatar
Linus Torvalds committed
39
40
#include <linux/nodemask.h>
#include <linux/vmalloc.h>
41
#include <linux/mempolicy.h>
42
#include <linux/stop_machine.h>
43
44
#include <linux/sort.h>
#include <linux/pfn.h>
45
#include <linux/backing-dev.h>
46
#include <linux/fault-inject.h>
47
#include <linux/page-isolation.h>
48
#include <linux/page_cgroup.h>
49
#include <linux/debugobjects.h>
50
#include <linux/kmemleak.h>
Linus Torvalds's avatar
Linus Torvalds committed
51
52

#include <asm/tlbflush.h>
53
#include <asm/div64.h>
Linus Torvalds's avatar
Linus Torvalds committed
54
55
56
#include "internal.h"

/*
57
 * Array of node states.
Linus Torvalds's avatar
Linus Torvalds committed
58
 */
59
60
61
62
63
64
65
66
67
68
69
70
71
nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
	[N_POSSIBLE] = NODE_MASK_ALL,
	[N_ONLINE] = { { [0] = 1UL } },
#ifndef CONFIG_NUMA
	[N_NORMAL_MEMORY] = { { [0] = 1UL } },
#ifdef CONFIG_HIGHMEM
	[N_HIGH_MEMORY] = { { [0] = 1UL } },
#endif
	[N_CPU] = { { [0] = 1UL } },
#endif	/* NUMA */
};
EXPORT_SYMBOL(node_states);

72
unsigned long totalram_pages __read_mostly;
73
unsigned long totalreserve_pages __read_mostly;
74
unsigned long highest_memmap_pfn __read_mostly;
75
int percpu_pagelist_fraction;
76
gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
Linus Torvalds's avatar
Linus Torvalds committed
77

78
79
80
81
#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
int pageblock_order __read_mostly;
#endif

82
static void __free_pages_ok(struct page *page, unsigned int order);
83

Linus Torvalds's avatar
Linus Torvalds committed
84
85
86
87
88
89
90
/*
 * results with 256, 32 in the lowmem_reserve sysctl:
 *	1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
 *	1G machine -> (16M dma, 784M normal, 224M high)
 *	NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
 *	HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
 *	HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
91
92
93
 *
 * TBD: should special case ZONE_DMA32 machines here - in those we normally
 * don't need any ZONE_NORMAL reservation
Linus Torvalds's avatar
Linus Torvalds committed
94
 */
95
int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
96
#ifdef CONFIG_ZONE_DMA
97
	 256,
98
#endif
99
#ifdef CONFIG_ZONE_DMA32
100
	 256,
101
#endif
102
#ifdef CONFIG_HIGHMEM
Mel Gorman's avatar
Mel Gorman committed
103
	 32,
104
#endif
Mel Gorman's avatar
Mel Gorman committed
105
	 32,
106
};
Linus Torvalds's avatar
Linus Torvalds committed
107
108
109

EXPORT_SYMBOL(totalram_pages);

110
static char * const zone_names[MAX_NR_ZONES] = {
111
#ifdef CONFIG_ZONE_DMA
112
	 "DMA",
113
#endif
114
#ifdef CONFIG_ZONE_DMA32
115
	 "DMA32",
116
#endif
117
	 "Normal",
118
#ifdef CONFIG_HIGHMEM
Mel Gorman's avatar
Mel Gorman committed
119
	 "HighMem",
120
#endif
Mel Gorman's avatar
Mel Gorman committed
121
	 "Movable",
122
123
};

Linus Torvalds's avatar
Linus Torvalds committed
124
125
int min_free_kbytes = 1024;

126
127
unsigned long __meminitdata nr_kernel_pages;
unsigned long __meminitdata nr_all_pages;
128
static unsigned long __meminitdata dma_reserve;
Linus Torvalds's avatar
Linus Torvalds committed
129

130
131
#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
  /*
Simon Arlott's avatar
Simon Arlott committed
132
   * MAX_ACTIVE_REGIONS determines the maximum number of distinct
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
   * ranges of memory (RAM) that may be registered with add_active_range().
   * Ranges passed to add_active_range() will be merged if possible
   * so the number of times add_active_range() can be called is
   * related to the number of nodes and the number of holes
   */
  #ifdef CONFIG_MAX_ACTIVE_REGIONS
    /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
    #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
  #else
    #if MAX_NUMNODES >= 32
      /* If there can be many nodes, allow up to 50 holes per node */
      #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
    #else
      /* By default, allow up to 256 distinct regions */
      #define MAX_ACTIVE_REGIONS 256
    #endif
  #endif

151
152
153
154
  static struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS];
  static int __meminitdata nr_nodemap_entries;
  static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
  static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
Adrian Bunk's avatar
Adrian Bunk committed
155
  static unsigned long __initdata required_kernelcore;
156
  static unsigned long __initdata required_movablecore;
Adrian Bunk's avatar
Adrian Bunk committed
157
  static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
Mel Gorman's avatar
Mel Gorman committed
158
159
160
161

  /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
  int movable_zone;
  EXPORT_SYMBOL(movable_zone);
162
163
#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */

Miklos Szeredi's avatar
Miklos Szeredi committed
164
165
#if MAX_NUMNODES > 1
int nr_node_ids __read_mostly = MAX_NUMNODES;
166
int nr_online_nodes __read_mostly = 1;
Miklos Szeredi's avatar
Miklos Szeredi committed
167
EXPORT_SYMBOL(nr_node_ids);
168
EXPORT_SYMBOL(nr_online_nodes);
Miklos Szeredi's avatar
Miklos Szeredi committed
169
170
#endif

171
172
int page_group_by_mobility_disabled __read_mostly;

173
174
static void set_pageblock_migratetype(struct page *page, int migratetype)
{
175
176
177
178

	if (unlikely(page_group_by_mobility_disabled))
		migratetype = MIGRATE_UNMOVABLE;

179
180
181
182
	set_pageblock_flags_group(page, (unsigned long)migratetype,
					PB_migrate, PB_migrate_end);
}

183
184
bool oom_killer_disabled __read_mostly;

Nick Piggin's avatar
Nick Piggin committed
185
#ifdef CONFIG_DEBUG_VM
186
static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
187
{
188
189
190
	int ret = 0;
	unsigned seq;
	unsigned long pfn = page_to_pfn(page);
191

192
193
194
195
196
197
198
199
200
	do {
		seq = zone_span_seqbegin(zone);
		if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
			ret = 1;
		else if (pfn < zone->zone_start_pfn)
			ret = 1;
	} while (zone_span_seqretry(zone, seq));

	return ret;
201
202
203
204
}

static int page_is_consistent(struct zone *zone, struct page *page)
{
205
	if (!pfn_valid_within(page_to_pfn(page)))
206
		return 0;
Linus Torvalds's avatar
Linus Torvalds committed
207
	if (zone != page_zone(page))
208
209
210
211
212
213
214
215
216
217
		return 0;

	return 1;
}
/*
 * Temporary debugging check for pages not lying within a given zone.
 */
static int bad_range(struct zone *zone, struct page *page)
{
	if (page_outside_zone_boundaries(zone, page))
Linus Torvalds's avatar
Linus Torvalds committed
218
		return 1;
219
220
221
	if (!page_is_consistent(zone, page))
		return 1;

Linus Torvalds's avatar
Linus Torvalds committed
222
223
	return 0;
}
Nick Piggin's avatar
Nick Piggin committed
224
225
226
227
228
229
230
#else
static inline int bad_range(struct zone *zone, struct page *page)
{
	return 0;
}
#endif

231
static void bad_page(struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
232
{
233
234
235
236
237
238
239
240
241
242
243
244
245
246
	static unsigned long resume;
	static unsigned long nr_shown;
	static unsigned long nr_unshown;

	/*
	 * Allow a burst of 60 reports, then keep quiet for that minute;
	 * or allow a steady drip of one report per second.
	 */
	if (nr_shown == 60) {
		if (time_before(jiffies, resume)) {
			nr_unshown++;
			goto out;
		}
		if (nr_unshown) {
247
248
			printk(KERN_ALERT
			      "BUG: Bad page state: %lu messages suppressed\n",
249
250
251
252
253
254
255
256
				nr_unshown);
			nr_unshown = 0;
		}
		nr_shown = 0;
	}
	if (nr_shown++ == 0)
		resume = jiffies + 60 * HZ;

257
	printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx\n",
258
		current->comm, page_to_pfn(page));
259
	printk(KERN_ALERT
260
261
262
263
		"page:%p flags:%p count:%d mapcount:%d mapping:%p index:%lx\n",
		page, (void *)page->flags, page_count(page),
		page_mapcount(page), page->mapping, page->index);

Linus Torvalds's avatar
Linus Torvalds committed
264
	dump_stack();
265
out:
266
267
	/* Leave bad fields for debug, except PageBuddy could make trouble */
	__ClearPageBuddy(page);
268
	add_taint(TAINT_BAD_PAGE);
Linus Torvalds's avatar
Linus Torvalds committed
269
270
271
272
273
274
275
276
277
278
279
280
}

/*
 * Higher-order pages are called "compound pages".  They are structured thusly:
 *
 * The first PAGE_SIZE page is called the "head page".
 *
 * The remaining PAGE_SIZE pages are called "tail pages".
 *
 * All pages have PG_compound set.  All pages have their ->private pointing at
 * the head page (even the head page has this).
 *
281
282
283
 * The first tail page's ->lru.next holds the address of the compound page's
 * put_page() function.  Its ->lru.prev holds the order of allocation.
 * This usage means that zero-order pages may not be compound.
Linus Torvalds's avatar
Linus Torvalds committed
284
 */
285
286
287

static void free_compound_page(struct page *page)
{
288
	__free_pages_ok(page, compound_order(page));
289
290
}

291
void prep_compound_page(struct page *page, unsigned long order)
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
{
	int i;
	int nr_pages = 1 << order;

	set_compound_page_dtor(page, free_compound_page);
	set_compound_order(page, order);
	__SetPageHead(page);
	for (i = 1; i < nr_pages; i++) {
		struct page *p = page + i;

		__SetPageTail(p);
		p->first_page = page;
	}
}

307
static int destroy_compound_page(struct page *page, unsigned long order)
Linus Torvalds's avatar
Linus Torvalds committed
308
309
310
{
	int i;
	int nr_pages = 1 << order;
311
	int bad = 0;
Linus Torvalds's avatar
Linus Torvalds committed
312

313
314
	if (unlikely(compound_order(page) != order) ||
	    unlikely(!PageHead(page))) {
315
		bad_page(page);
316
317
		bad++;
	}
Linus Torvalds's avatar
Linus Torvalds committed
318

319
	__ClearPageHead(page);
320

321
322
	for (i = 1; i < nr_pages; i++) {
		struct page *p = page + i;
Linus Torvalds's avatar
Linus Torvalds committed
323

324
		if (unlikely(!PageTail(p) || (p->first_page != page))) {
325
			bad_page(page);
326
327
			bad++;
		}
328
		__ClearPageTail(p);
Linus Torvalds's avatar
Linus Torvalds committed
329
	}
330
331

	return bad;
Linus Torvalds's avatar
Linus Torvalds committed
332
333
}

Nick Piggin's avatar
Nick Piggin committed
334
335
336
337
static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
{
	int i;

338
339
340
341
	/*
	 * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
	 * and __GFP_HIGHMEM from hard or soft interrupt context.
	 */
Nick Piggin's avatar
Nick Piggin committed
342
	VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
Nick Piggin's avatar
Nick Piggin committed
343
344
345
346
	for (i = 0; i < (1 << order); i++)
		clear_highpage(page + i);
}

347
348
static inline void set_page_order(struct page *page, int order)
{
349
	set_page_private(page, order);
350
	__SetPageBuddy(page);
Linus Torvalds's avatar
Linus Torvalds committed
351
352
353
354
}

static inline void rmv_page_order(struct page *page)
{
355
	__ClearPageBuddy(page);
356
	set_page_private(page, 0);
Linus Torvalds's avatar
Linus Torvalds committed
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
}

/*
 * Locate the struct page for both the matching buddy in our
 * pair (buddy1) and the combined O(n+1) page they form (page).
 *
 * 1) Any buddy B1 will have an order O twin B2 which satisfies
 * the following equation:
 *     B2 = B1 ^ (1 << O)
 * For example, if the starting buddy (buddy2) is #8 its order
 * 1 buddy is #10:
 *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
 *
 * 2) Any buddy B will have an order O+1 parent P which
 * satisfies the following equation:
 *     P = B & ~(1 << O)
 *
Andreas Mohr's avatar
Andreas Mohr committed
374
 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
Linus Torvalds's avatar
Linus Torvalds committed
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 */
static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
	unsigned long buddy_idx = page_idx ^ (1 << order);

	return page + (buddy_idx - page_idx);
}

static inline unsigned long
__find_combined_index(unsigned long page_idx, unsigned int order)
{
	return (page_idx & ~(1 << order));
}

/*
 * This function checks whether a page is free && is the buddy
 * we can do coalesce a page and its buddy if
Nick Piggin's avatar
Nick Piggin committed
393
 * (a) the buddy is not in a hole &&
394
 * (b) the buddy is in the buddy system &&
395
396
 * (c) a page and its buddy have the same order &&
 * (d) a page and its buddy are in the same zone.
397
398
399
 *
 * For recording whether a page is in the buddy system, we use PG_buddy.
 * Setting, clearing, and testing PG_buddy is serialized by zone->lock.
Linus Torvalds's avatar
Linus Torvalds committed
400
 *
401
 * For recording page's order, we use page_private(page).
Linus Torvalds's avatar
Linus Torvalds committed
402
 */
403
404
static inline int page_is_buddy(struct page *page, struct page *buddy,
								int order)
Linus Torvalds's avatar
Linus Torvalds committed
405
{
406
	if (!pfn_valid_within(page_to_pfn(buddy)))
Nick Piggin's avatar
Nick Piggin committed
407
408
		return 0;

409
410
411
412
	if (page_zone_id(page) != page_zone_id(buddy))
		return 0;

	if (PageBuddy(buddy) && page_order(buddy) == order) {
413
		VM_BUG_ON(page_count(buddy) != 0);
414
		return 1;
415
	}
416
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
}

/*
 * Freeing function for a buddy system allocator.
 *
 * The concept of a buddy system is to maintain direct-mapped table
 * (containing bit values) for memory blocks of various "orders".
 * The bottom level table contains the map for the smallest allocatable
 * units of memory (here, pages), and each level above it describes
 * pairs of units from the levels below, hence, "buddies".
 * At a high level, all that happens here is marking the table entry
 * at the bottom level available, and propagating the changes upward
 * as necessary, plus some accounting needed to play nicely with other
 * parts of the VM system.
 * At each level, we keep a list of pages, which are heads of continuous
432
 * free pages of length of (1 << order) and marked with PG_buddy. Page's
433
 * order is recorded in page_private(page) field.
Linus Torvalds's avatar
Linus Torvalds committed
434
435
436
437
438
439
440
441
442
 * So when we are allocating or freeing one, we can derive the state of the
 * other.  That is, if we allocate a small block, and both were   
 * free, the remainder of the region must be split into blocks.   
 * If a block is freed, and its buddy is also free, then this
 * triggers coalescing into a block of larger size.            
 *
 * -- wli
 */

Nick Piggin's avatar
Nick Piggin committed
443
static inline void __free_one_page(struct page *page,
444
445
		struct zone *zone, unsigned int order,
		int migratetype)
Linus Torvalds's avatar
Linus Torvalds committed
446
447
448
{
	unsigned long page_idx;

449
	if (unlikely(PageCompound(page)))
450
451
		if (unlikely(destroy_compound_page(page, order)))
			return;
Linus Torvalds's avatar
Linus Torvalds committed
452

453
454
	VM_BUG_ON(migratetype == -1);

Linus Torvalds's avatar
Linus Torvalds committed
455
456
	page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

457
	VM_BUG_ON(page_idx & ((1 << order) - 1));
Nick Piggin's avatar
Nick Piggin committed
458
	VM_BUG_ON(bad_range(zone, page));
Linus Torvalds's avatar
Linus Torvalds committed
459
460
461
462
463
464

	while (order < MAX_ORDER-1) {
		unsigned long combined_idx;
		struct page *buddy;

		buddy = __page_find_buddy(page, page_idx, order);
465
		if (!page_is_buddy(page, buddy, order))
466
			break;
Nick Piggin's avatar
Nick Piggin committed
467

468
		/* Our buddy is free, merge with it and move up one order. */
Linus Torvalds's avatar
Linus Torvalds committed
469
		list_del(&buddy->lru);
470
		zone->free_area[order].nr_free--;
Linus Torvalds's avatar
Linus Torvalds committed
471
		rmv_page_order(buddy);
Nick Piggin's avatar
Nick Piggin committed
472
		combined_idx = __find_combined_index(page_idx, order);
Linus Torvalds's avatar
Linus Torvalds committed
473
474
475
476
477
		page = page + (combined_idx - page_idx);
		page_idx = combined_idx;
		order++;
	}
	set_page_order(page, order);
478
479
	list_add(&page->lru,
		&zone->free_area[order].free_list[migratetype]);
Linus Torvalds's avatar
Linus Torvalds committed
480
481
482
	zone->free_area[order].nr_free++;
}

483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
#ifdef CONFIG_HAVE_MLOCKED_PAGE_BIT
/*
 * free_page_mlock() -- clean up attempts to free and mlocked() page.
 * Page should not be on lru, so no need to fix that up.
 * free_pages_check() will verify...
 */
static inline void free_page_mlock(struct page *page)
{
	__dec_zone_page_state(page, NR_MLOCK);
	__count_vm_event(UNEVICTABLE_MLOCKFREED);
}
#else
static void free_page_mlock(struct page *page) { }
#endif

498
static inline int free_pages_check(struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
499
{
Nick Piggin's avatar
Nick Piggin committed
500
501
	if (unlikely(page_mapcount(page) |
		(page->mapping != NULL)  |
502
		(atomic_read(&page->_count) != 0) |
503
		(page->flags & PAGE_FLAGS_CHECK_AT_FREE))) {
504
		bad_page(page);
505
		return 1;
506
	}
507
508
509
	if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
		page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
510
511
512
513
514
}

/*
 * Frees a list of pages. 
 * Assumes all pages on list are in same zone, and of same order.
515
 * count is the number of pages to free.
Linus Torvalds's avatar
Linus Torvalds committed
516
517
518
519
520
521
522
 *
 * If the zone was previously in an "all pages pinned" state then look to
 * see if this freeing clears that state.
 *
 * And clear the zone's pages_scanned counter, to hold off the "all pages are
 * pinned" detection logic.
 */
Nick Piggin's avatar
Nick Piggin committed
523
524
static void free_pages_bulk(struct zone *zone, int count,
					struct list_head *list, int order)
Linus Torvalds's avatar
Linus Torvalds committed
525
{
Nick Piggin's avatar
Nick Piggin committed
526
	spin_lock(&zone->lock);
527
	zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
Linus Torvalds's avatar
Linus Torvalds committed
528
	zone->pages_scanned = 0;
529
530

	__mod_zone_page_state(zone, NR_FREE_PAGES, count << order);
Nick Piggin's avatar
Nick Piggin committed
531
532
533
	while (count--) {
		struct page *page;

Nick Piggin's avatar
Nick Piggin committed
534
		VM_BUG_ON(list_empty(list));
Linus Torvalds's avatar
Linus Torvalds committed
535
		page = list_entry(list->prev, struct page, lru);
Nick Piggin's avatar
Nick Piggin committed
536
		/* have to delete it as __free_one_page list manipulates */
Linus Torvalds's avatar
Linus Torvalds committed
537
		list_del(&page->lru);
538
		__free_one_page(page, zone, order, page_private(page));
Linus Torvalds's avatar
Linus Torvalds committed
539
	}
Nick Piggin's avatar
Nick Piggin committed
540
	spin_unlock(&zone->lock);
Linus Torvalds's avatar
Linus Torvalds committed
541
542
}

543
544
static void free_one_page(struct zone *zone, struct page *page, int order,
				int migratetype)
Linus Torvalds's avatar
Linus Torvalds committed
545
{
546
	spin_lock(&zone->lock);
547
	zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
548
	zone->pages_scanned = 0;
549
550

	__mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
551
	__free_one_page(page, zone, order, migratetype);
552
	spin_unlock(&zone->lock);
Nick Piggin's avatar
Nick Piggin committed
553
554
555
556
557
}

static void __free_pages_ok(struct page *page, unsigned int order)
{
	unsigned long flags;
Linus Torvalds's avatar
Linus Torvalds committed
558
	int i;
559
	int bad = 0;
560
	int wasMlocked = TestClearPageMlocked(page);
Linus Torvalds's avatar
Linus Torvalds committed
561

562
563
	kmemcheck_free_shadow(page, order);

Linus Torvalds's avatar
Linus Torvalds committed
564
	for (i = 0 ; i < (1 << order) ; ++i)
565
566
		bad += free_pages_check(page + i);
	if (bad)
567
568
		return;

569
	if (!PageHighMem(page)) {
Nick Piggin's avatar
Nick Piggin committed
570
		debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
571
572
573
		debug_check_no_obj_freed(page_address(page),
					   PAGE_SIZE << order);
	}
Nick Piggin's avatar
Nick Piggin committed
574
	arch_free_page(page, order);
Nick Piggin's avatar
Nick Piggin committed
575
	kernel_map_pages(page, 1 << order, 0);
Nick Piggin's avatar
Nick Piggin committed
576

Nick Piggin's avatar
Nick Piggin committed
577
	local_irq_save(flags);
578
	if (unlikely(wasMlocked))
579
		free_page_mlock(page);
580
	__count_vm_events(PGFREE, 1 << order);
581
582
	free_one_page(page_zone(page), page, order,
					get_pageblock_migratetype(page));
Nick Piggin's avatar
Nick Piggin committed
583
	local_irq_restore(flags);
Linus Torvalds's avatar
Linus Torvalds committed
584
585
}

586
587
588
/*
 * permit the bootmem allocator to evade page validation on high-order frees
 */
589
void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
590
591
592
593
{
	if (order == 0) {
		__ClearPageReserved(page);
		set_page_count(page, 0);
594
		set_page_refcounted(page);
Nick Piggin's avatar
Nick Piggin committed
595
		__free_page(page);
596
597
598
	} else {
		int loop;

Nick Piggin's avatar
Nick Piggin committed
599
		prefetchw(page);
600
601
602
		for (loop = 0; loop < BITS_PER_LONG; loop++) {
			struct page *p = &page[loop];

Nick Piggin's avatar
Nick Piggin committed
603
604
			if (loop + 1 < BITS_PER_LONG)
				prefetchw(p + 1);
605
606
607
608
			__ClearPageReserved(p);
			set_page_count(p, 0);
		}

609
		set_page_refcounted(page);
Nick Piggin's avatar
Nick Piggin committed
610
		__free_pages(page, order);
611
612
613
	}
}

Linus Torvalds's avatar
Linus Torvalds committed
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628

/*
 * The order of subdivision here is critical for the IO subsystem.
 * Please do not alter this order without good reasons and regression
 * testing. Specifically, as large blocks of memory are subdivided,
 * the order in which smaller blocks are delivered depends on the order
 * they're subdivided in this function. This is the primary factor
 * influencing the order in which pages are delivered to the IO
 * subsystem according to empirical testing, and this is also justified
 * by considering the behavior of a buddy system containing a single
 * large block of memory acted on by a series of small allocations.
 * This behavior is a critical factor in sglist merging's success.
 *
 * -- wli
 */
Nick Piggin's avatar
Nick Piggin committed
629
static inline void expand(struct zone *zone, struct page *page,
630
631
	int low, int high, struct free_area *area,
	int migratetype)
Linus Torvalds's avatar
Linus Torvalds committed
632
633
634
635
636
637
638
{
	unsigned long size = 1 << high;

	while (high > low) {
		area--;
		high--;
		size >>= 1;
Nick Piggin's avatar
Nick Piggin committed
639
		VM_BUG_ON(bad_range(zone, &page[size]));
640
		list_add(&page[size].lru, &area->free_list[migratetype]);
Linus Torvalds's avatar
Linus Torvalds committed
641
642
643
644
645
646
647
648
		area->nr_free++;
		set_page_order(&page[size], high);
	}
}

/*
 * This page is about to be returned from the page allocator
 */
Nick Piggin's avatar
Nick Piggin committed
649
static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
Linus Torvalds's avatar
Linus Torvalds committed
650
{
Nick Piggin's avatar
Nick Piggin committed
651
652
	if (unlikely(page_mapcount(page) |
		(page->mapping != NULL)  |
653
		(atomic_read(&page->_count) != 0)  |
654
		(page->flags & PAGE_FLAGS_CHECK_AT_PREP))) {
655
		bad_page(page);
656
		return 1;
657
	}
658

659
	set_page_private(page, 0);
660
	set_page_refcounted(page);
Nick Piggin's avatar
Nick Piggin committed
661
662

	arch_alloc_page(page, order);
Linus Torvalds's avatar
Linus Torvalds committed
663
	kernel_map_pages(page, 1 << order, 1);
Nick Piggin's avatar
Nick Piggin committed
664
665
666
667
668
669
670

	if (gfp_flags & __GFP_ZERO)
		prep_zero_page(page, order, gfp_flags);

	if (order && (gfp_flags & __GFP_COMP))
		prep_compound_page(page, order);

671
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
672
673
}

674
675
676
677
/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
678
679
static inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
						int migratetype)
{
	unsigned int current_order;
	struct free_area * area;
	struct page *page;

	/* Find a page of the appropriate size in the preferred list */
	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
		area = &(zone->free_area[current_order]);
		if (list_empty(&area->free_list[migratetype]))
			continue;

		page = list_entry(area->free_list[migratetype].next,
							struct page, lru);
		list_del(&page->lru);
		rmv_page_order(page);
		area->nr_free--;
		expand(zone, page, order, current_order, area, migratetype);
		return page;
	}

	return NULL;
}


705
706
707
708
709
/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 */
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
710
711
712
713
	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
	[MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
714
715
};

716
717
/*
 * Move the free pages in a range to the free lists of the requested type.
718
 * Note that start_page and end_pages are not aligned on a pageblock
719
720
 * boundary. If alignment is required, use move_freepages_block()
 */
Adrian Bunk's avatar
Adrian Bunk committed
721
722
723
static int move_freepages(struct zone *zone,
			  struct page *start_page, struct page *end_page,
			  int migratetype)
724
725
726
{
	struct page *page;
	unsigned long order;
727
	int pages_moved = 0;
728
729
730
731
732
733
734

#ifndef CONFIG_HOLES_IN_ZONE
	/*
	 * page_zone is not safe to call in this context when
	 * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
	 * anyway as we check zone boundaries in move_freepages_block().
	 * Remove at a later date when no bug reports exist related to
Mel Gorman's avatar
Mel Gorman committed
735
	 * grouping pages by mobility
736
737
738
739
740
	 */
	BUG_ON(page_zone(start_page) != page_zone(end_page));
#endif

	for (page = start_page; page <= end_page;) {
741
742
743
		/* Make sure we are not inadvertently changing nodes */
		VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));

744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
		if (!pfn_valid_within(page_to_pfn(page))) {
			page++;
			continue;
		}

		if (!PageBuddy(page)) {
			page++;
			continue;
		}

		order = page_order(page);
		list_del(&page->lru);
		list_add(&page->lru,
			&zone->free_area[order].free_list[migratetype]);
		page += 1 << order;
759
		pages_moved += 1 << order;
760
761
	}

762
	return pages_moved;
763
764
}

Adrian Bunk's avatar
Adrian Bunk committed
765
766
static int move_freepages_block(struct zone *zone, struct page *page,
				int migratetype)
767
768
769
770
771
{
	unsigned long start_pfn, end_pfn;
	struct page *start_page, *end_page;

	start_pfn = page_to_pfn(page);
772
	start_pfn = start_pfn & ~(pageblock_nr_pages-1);
773
	start_page = pfn_to_page(start_pfn);
774
775
	end_page = start_page + pageblock_nr_pages - 1;
	end_pfn = start_pfn + pageblock_nr_pages - 1;
776
777
778
779
780
781
782
783
784
785

	/* Do not cross zone boundaries */
	if (start_pfn < zone->zone_start_pfn)
		start_page = page;
	if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
		return 0;

	return move_freepages(zone, start_page, end_page, migratetype);
}

786
/* Remove an element from the buddy allocator from the fallback list */
787
788
static inline struct page *
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
789
790
791
792
793
794
795
796
797
798
799
800
{
	struct free_area * area;
	int current_order;
	struct page *page;
	int migratetype, i;

	/* Find the largest possible block of pages in the other list */
	for (current_order = MAX_ORDER-1; current_order >= order;
						--current_order) {
		for (i = 0; i < MIGRATE_TYPES - 1; i++) {
			migratetype = fallbacks[start_migratetype][i];

801
802
803
			/* MIGRATE_RESERVE handled later if necessary */
			if (migratetype == MIGRATE_RESERVE)
				continue;
804

805
806
807
808
809
810
811
812
813
			area = &(zone->free_area[current_order]);
			if (list_empty(&area->free_list[migratetype]))
				continue;

			page = list_entry(area->free_list[migratetype].next,
					struct page, lru);
			area->nr_free--;

			/*
814
			 * If breaking a large block of pages, move all free
815
816
817
			 * pages to the preferred allocation list. If falling
			 * back for a reclaimable kernel allocation, be more
			 * agressive about taking ownership of free pages
818
			 */
819
			if (unlikely(current_order >= (pageblock_order >> 1)) ||
820
821
					start_migratetype == MIGRATE_RECLAIMABLE ||
					page_group_by_mobility_disabled) {
822
823
824
825
826
				unsigned long pages;
				pages = move_freepages_block(zone, page,
								start_migratetype);

				/* Claim the whole block if over half of it is free */
827
828
				if (pages >= (1 << (pageblock_order-1)) ||
						page_group_by_mobility_disabled)
829
830
831
					set_pageblock_migratetype(page,
								start_migratetype);

832
				migratetype = start_migratetype;
833
			}
834
835
836
837
838

			/* Remove the page from the freelists */
			list_del(&page->lru);
			rmv_page_order(page);

839
			if (current_order == pageblock_order)
840
841
842
843
844
845
846
847
				set_pageblock_migratetype(page,
							start_migratetype);

			expand(zone, page, order, current_order, area, migratetype);
			return page;
		}
	}

848
	return NULL;
849
850
}

851
/*
Linus Torvalds's avatar
Linus Torvalds committed
852
853
854
 * Do the hard work of removing an element from the buddy allocator.
 * Call me with the zone->lock already held.
 */
855
856
static struct page *__rmqueue(struct zone *zone, unsigned int order,
						int migratetype)
Linus Torvalds's avatar
Linus Torvalds committed
857
858
859
{
	struct page *page;

860
retry_reserve:
861
	page = __rmqueue_smallest(zone, order, migratetype);
862

863
	if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
864
		page = __rmqueue_fallback(zone, order, migratetype);
865

866
867
868
869
870
871
872
873
874
875
876
		/*
		 * Use MIGRATE_RESERVE rather than fail an allocation. goto
		 * is used because __rmqueue_smallest is an inline function
		 * and we want just one call site
		 */
		if (!page) {
			migratetype = MIGRATE_RESERVE;
			goto retry_reserve;
		}
	}

877
	return page;
Linus Torvalds's avatar
Linus Torvalds committed
878
879
880
881
882
883
884
885
}

/* 
 * Obtain a specified number of elements from the buddy allocator, all under
 * a single hold of the lock, for efficiency.  Add them to the supplied list.
 * Returns the number of new pages which were placed at *list.
 */
static int rmqueue_bulk(struct zone *zone, unsigned int order, 
886
			unsigned long count, struct list_head *list,
887
			int migratetype, int cold)
Linus Torvalds's avatar
Linus Torvalds committed
888
889
890
{
	int i;
	
Nick Piggin's avatar
Nick Piggin committed
891
	spin_lock(&zone->lock);
Linus Torvalds's avatar
Linus Torvalds committed
892
	for (i = 0; i < count; ++i) {
893
		struct page *page = __rmqueue(zone, order, migratetype);
Nick Piggin's avatar
Nick Piggin committed
894
		if (unlikely(page == NULL))
Linus Torvalds's avatar
Linus Torvalds committed
895
			break;
896
897
898
899
900
901
902
903
904
905

		/*
		 * Split buddy pages returned by expand() are received here
		 * in physical page order. The page is added to the callers and
		 * list and the list head then moves forward. From the callers
		 * perspective, the linked list is ordered by page number in
		 * some conditions. This is useful for IO devices that can
		 * merge IO requests if the physical pages are ordered
		 * properly.
		 */
906
907
908
909
		if (likely(cold == 0))
			list_add(&page->lru, list);
		else
			list_add_tail(&page->lru, list);
910
		set_page_private(page, migratetype);
911
		list = &page->lru;
Linus Torvalds's avatar
Linus Torvalds committed
912
	}
913
	__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
Nick Piggin's avatar
Nick Piggin committed
914
	spin_unlock(&zone->lock);
Nick Piggin's avatar
Nick Piggin committed
915
	return i;
Linus Torvalds's avatar
Linus Torvalds committed
916
917
}

918
#ifdef CONFIG_NUMA
919
/*
920
921
922
923
 * Called from the vmstat counter updater to drain pagesets of this
 * currently executing processor on remote nodes after they have
 * expired.
 *
924
925
 * Note that this function must be called with the thread pinned to
 * a single processor.
926
 */
927
void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
928
929
{
	unsigned long flags;
930
	int to_drain;
931

932
933
934
935
936
937
938
939
	local_irq_save(flags);
	if (pcp->count >= pcp->batch)
		to_drain = pcp->batch;
	else
		to_drain = pcp->count;
	free_pages_bulk(zone, to_drain, &pcp->list, 0);
	pcp->count -= to_drain;
	local_irq_restore(flags);
940
941
942
}
#endif

943
944
945
946
947
948
949
950
/*
 * Drain pages of the indicated processor.
 *
 * The processor must either be the current processor and the
 * thread pinned to the current processor or a processor that
 * is not online.
 */
static void drain_pages(unsigned int cpu)
Linus Torvalds's avatar
Linus Torvalds committed
951
{
Nick Piggin's avatar
Nick Piggin committed
952
	unsigned long flags;
Linus Torvalds's avatar
Linus Torvalds committed
953
954
	struct zone *zone;

955
	for_each_populated_zone(zone) {
Linus Torvalds's avatar
Linus Torvalds committed
956
		struct per_cpu_pageset *pset;
957
		struct per_cpu_pages *pcp;
Linus Torvalds's avatar
Linus Torvalds committed
958

959
		pset = zone_pcp(zone, cpu);
960
961
962
963
964
965

		pcp = &pset->pcp;
		local_irq_save(flags);
		free_pages_bulk(zone, pcp->count, &pcp->list, 0);
		pcp->count = 0;
		local_irq_restore(flags);
Linus Torvalds's avatar
Linus Torvalds committed
966
967
968
	}
}

969
970
971
972
973
974
975
976
977
978
979
980
981
/*
 * Spill all of this CPU's per-cpu pages back into the buddy allocator.
 */
void drain_local_pages(void *arg)
{
	drain_pages(smp_processor_id());
}

/*
 * Spill all the per-cpu pages from all CPUs back into the buddy allocator
 */
void drain_all_pages(void)
{
982
	on_each_cpu(drain_local_pages, NULL, 1);
983
984
}

985
#ifdef CONFIG_HIBERNATION
Linus Torvalds's avatar
Linus Torvalds committed
986
987
988

void mark_free_pages(struct zone *zone)
{
989
990
	unsigned long pfn, max_zone_pfn;
	unsigned long flags;
991
	int order, t;
Linus Torvalds's avatar
Linus Torvalds committed
992
993
994
995
996
997
	struct list_head *curr;

	if (!zone->spanned_pages)
		return;

	spin_lock_irqsave(&zone->lock, flags);
998
999
1000
1001
1002
1003

	max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
	for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
		if (pfn_valid(pfn)) {
			struct page *page = pfn_to_page(pfn);

1004
1005
			if (!swsusp_page_is_forbidden(page))
				swsusp_unset_page_free(page);
1006
		}
Linus Torvalds's avatar
Linus Torvalds committed
1007

1008
1009
	for_each_migratetype_order(order, t) {
		list_for_each(curr, &zone->free_area[order].free_list[t]) {
1010
			unsigned long i;
Linus Torvalds's avatar
Linus Torvalds committed
1011

1012
1013
			pfn = page_to_pfn(list_entry(curr, struct page, lru));
			for (i = 0; i < (1UL << order); i++)
1014
				swsusp_set_page_free(pfn_to_page(pfn + i));
1015
		}
1016
	}
Linus Torvalds's avatar
Linus Torvalds committed
1017
1018
	spin_unlock_irqrestore(&zone->lock, flags);
}
1019
#endif /* CONFIG_PM */
Linus Torvalds's avatar
Linus Torvalds committed
1020
1021
1022
1023

/*
 * Free a 0-order page
 */
Harvey Harrison's avatar
Harvey Harrison committed
1024
static void free_hot_cold_page(struct page *page, int cold)
Linus Torvalds's avatar
Linus Torvalds committed
1025
1026
1027
1028
{
	struct zone *zone = page_zone(page);
	struct per_cpu_pages *pcp;
	unsigned long flags;
1029
	int wasMlocked = TestClearPageMlocked(page);
Linus Torvalds's avatar
Linus Torvalds committed
1030

1031
1032
	kmemcheck_free_shadow(page, 0);

Linus Torvalds's avatar
Linus Torvalds committed
1033
1034
	if (PageAnon(page))
		page->mapping = NULL;
1035
	if (free_pages_check(page))
1036
1037
		return;

1038
	if (!PageHighMem(page)) {
Nick Piggin's avatar
Nick Piggin committed
1039
		debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
1040
1041
		debug_check_no_obj_freed(page_address(page), PAGE_SIZE);
	}
Nick Piggin's avatar
Nick Piggin committed
1042
	arch_free_page(page, 0);
1043
1044
	kernel_map_pages(page, 1, 0);

1045
	pcp = &zone_pcp(zone, get_cpu())->pcp;
1046
	set_page_private(page, get_pageblock_migratetype(page));
Linus Torvalds's avatar
Linus Torvalds committed
1047
	local_irq_save(flags);
1048
	if (unlikely(wasMlocked))