blob: d0a240fbb8bfc34f5304ee896af7964442230d4d [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * linux/mm/page_alloc.c
3 *
4 * Manages the free list, the system allocates free pages here.
5 * Note that kmalloc() lives in slab.c
6 *
7 * Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
8 * Swap reorganised 29.12.95, Stephen Tweedie
9 * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
10 * Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999
11 * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
12 * Zone balancing, Kanoj Sarcar, SGI, Jan 2000
13 * Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002
14 * (lots of bits borrowed from Ingo Molnar & Andrew Morton)
15 */
16
Linus Torvalds1da177e2005-04-16 15:20:36 -070017#include <linux/stddef.h>
18#include <linux/mm.h>
19#include <linux/swap.h>
20#include <linux/interrupt.h>
21#include <linux/pagemap.h>
KOSAKI Motohiro10ed2732008-03-04 14:28:32 -080022#include <linux/jiffies.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070023#include <linux/bootmem.h>
24#include <linux/compiler.h>
Randy Dunlap9f158332005-09-13 01:25:16 -070025#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070026#include <linux/module.h>
27#include <linux/suspend.h>
28#include <linux/pagevec.h>
29#include <linux/blkdev.h>
30#include <linux/slab.h>
David Rientjes5a3135c2007-10-16 23:25:53 -070031#include <linux/oom.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070032#include <linux/notifier.h>
33#include <linux/topology.h>
34#include <linux/sysctl.h>
35#include <linux/cpu.h>
36#include <linux/cpuset.h>
Dave Hansenbdc8cb92005-10-29 18:16:53 -070037#include <linux/memory_hotplug.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070038#include <linux/nodemask.h>
39#include <linux/vmalloc.h>
Christoph Lameter4be38e32006-01-06 00:11:17 -080040#include <linux/mempolicy.h>
Yasunori Goto68113782006-06-23 02:03:11 -070041#include <linux/stop_machine.h>
Mel Gormanc7132162006-09-27 01:49:43 -070042#include <linux/sort.h>
43#include <linux/pfn.h>
Andrew Morton3fcfab12006-10-19 23:28:16 -070044#include <linux/backing-dev.h>
Akinobu Mita933e3122006-12-08 02:39:45 -080045#include <linux/fault-inject.h>
KAMEZAWA Hiroyukia5d76b52007-10-16 01:26:11 -070046#include <linux/page-isolation.h>
KAMEZAWA Hiroyuki52d4b9a2008-10-18 20:28:16 -070047#include <linux/page_cgroup.h>
Thomas Gleixner3ac7fe52008-04-30 00:55:01 -070048#include <linux/debugobjects.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070049
50#include <asm/tlbflush.h>
Andrew Mortonac924c62006-05-15 09:43:59 -070051#include <asm/div64.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070052#include "internal.h"
53
54/*
Christoph Lameter13808912007-10-16 01:25:27 -070055 * Array of node states.
Linus Torvalds1da177e2005-04-16 15:20:36 -070056 */
Christoph Lameter13808912007-10-16 01:25:27 -070057nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
58 [N_POSSIBLE] = NODE_MASK_ALL,
59 [N_ONLINE] = { { [0] = 1UL } },
60#ifndef CONFIG_NUMA
61 [N_NORMAL_MEMORY] = { { [0] = 1UL } },
62#ifdef CONFIG_HIGHMEM
63 [N_HIGH_MEMORY] = { { [0] = 1UL } },
64#endif
65 [N_CPU] = { { [0] = 1UL } },
66#endif /* NUMA */
67};
68EXPORT_SYMBOL(node_states);
69
Ravikiran G Thirumalai6c231b72005-09-06 15:17:45 -070070unsigned long totalram_pages __read_mostly;
Hideo AOKIcb45b0e2006-04-10 22:52:59 -070071unsigned long totalreserve_pages __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070072long nr_swap_pages;
Rohit Seth8ad4b1f2006-01-08 01:00:40 -080073int percpu_pagelist_fraction;
Linus Torvalds1da177e2005-04-16 15:20:36 -070074
Mel Gormand9c23402007-10-16 01:26:01 -070075#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
76int pageblock_order __read_mostly;
77#endif
78
Hugh Dickinsd98c7a02006-02-14 13:52:59 -080079static void __free_pages_ok(struct page *page, unsigned int order);
David Howellsa226f6c2006-01-06 00:11:08 -080080
Linus Torvalds1da177e2005-04-16 15:20:36 -070081/*
82 * results with 256, 32 in the lowmem_reserve sysctl:
83 * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
84 * 1G machine -> (16M dma, 784M normal, 224M high)
85 * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
86 * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
87 * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
Andi Kleena2f1b422005-11-05 17:25:53 +010088 *
89 * TBD: should special case ZONE_DMA32 machines here - in those we normally
90 * don't need any ZONE_NORMAL reservation
Linus Torvalds1da177e2005-04-16 15:20:36 -070091 */
Christoph Lameter2f1b6242006-09-25 23:31:13 -070092int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
Christoph Lameter4b51d662007-02-10 01:43:10 -080093#ifdef CONFIG_ZONE_DMA
Christoph Lameter2f1b6242006-09-25 23:31:13 -070094 256,
Christoph Lameter4b51d662007-02-10 01:43:10 -080095#endif
Christoph Lameterfb0e7942006-09-25 23:31:13 -070096#ifdef CONFIG_ZONE_DMA32
Christoph Lameter2f1b6242006-09-25 23:31:13 -070097 256,
Christoph Lameterfb0e7942006-09-25 23:31:13 -070098#endif
Christoph Lametere53ef382006-09-25 23:31:14 -070099#ifdef CONFIG_HIGHMEM
Mel Gorman2a1e2742007-07-17 04:03:12 -0700100 32,
Christoph Lametere53ef382006-09-25 23:31:14 -0700101#endif
Mel Gorman2a1e2742007-07-17 04:03:12 -0700102 32,
Christoph Lameter2f1b6242006-09-25 23:31:13 -0700103};
Linus Torvalds1da177e2005-04-16 15:20:36 -0700104
105EXPORT_SYMBOL(totalram_pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700106
Helge Deller15ad7cd2006-12-06 20:40:36 -0800107static char * const zone_names[MAX_NR_ZONES] = {
Christoph Lameter4b51d662007-02-10 01:43:10 -0800108#ifdef CONFIG_ZONE_DMA
Christoph Lameter2f1b6242006-09-25 23:31:13 -0700109 "DMA",
Christoph Lameter4b51d662007-02-10 01:43:10 -0800110#endif
Christoph Lameterfb0e7942006-09-25 23:31:13 -0700111#ifdef CONFIG_ZONE_DMA32
Christoph Lameter2f1b6242006-09-25 23:31:13 -0700112 "DMA32",
Christoph Lameterfb0e7942006-09-25 23:31:13 -0700113#endif
Christoph Lameter2f1b6242006-09-25 23:31:13 -0700114 "Normal",
Christoph Lametere53ef382006-09-25 23:31:14 -0700115#ifdef CONFIG_HIGHMEM
Mel Gorman2a1e2742007-07-17 04:03:12 -0700116 "HighMem",
Christoph Lametere53ef382006-09-25 23:31:14 -0700117#endif
Mel Gorman2a1e2742007-07-17 04:03:12 -0700118 "Movable",
Christoph Lameter2f1b6242006-09-25 23:31:13 -0700119};
120
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121int min_free_kbytes = 1024;
122
Yasunori Goto86356ab2006-06-23 02:03:09 -0700123unsigned long __meminitdata nr_kernel_pages;
124unsigned long __meminitdata nr_all_pages;
Yasunori Gotoa3142c82007-05-08 00:23:07 -0700125static unsigned long __meminitdata dma_reserve;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126
Mel Gormanc7132162006-09-27 01:49:43 -0700127#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
128 /*
Simon Arlott183ff222007-10-20 01:27:18 +0200129 * MAX_ACTIVE_REGIONS determines the maximum number of distinct
Mel Gormanc7132162006-09-27 01:49:43 -0700130 * ranges of memory (RAM) that may be registered with add_active_range().
131 * Ranges passed to add_active_range() will be merged if possible
132 * so the number of times add_active_range() can be called is
133 * related to the number of nodes and the number of holes
134 */
135 #ifdef CONFIG_MAX_ACTIVE_REGIONS
136 /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
137 #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
138 #else
139 #if MAX_NUMNODES >= 32
140 /* If there can be many nodes, allow up to 50 holes per node */
141 #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
142 #else
143 /* By default, allow up to 256 distinct regions */
144 #define MAX_ACTIVE_REGIONS 256
145 #endif
146 #endif
147
Jan Beulich98011f52007-07-15 23:38:17 -0700148 static struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS];
149 static int __meminitdata nr_nodemap_entries;
150 static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
151 static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
Mel Gormanfb014392006-09-27 01:49:59 -0700152#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
Jan Beulich98011f52007-07-15 23:38:17 -0700153 static unsigned long __meminitdata node_boundary_start_pfn[MAX_NUMNODES];
154 static unsigned long __meminitdata node_boundary_end_pfn[MAX_NUMNODES];
Mel Gormanfb014392006-09-27 01:49:59 -0700155#endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
Adrian Bunkb69a7282008-07-23 21:28:12 -0700156 static unsigned long __initdata required_kernelcore;
Adrian Bunk484f51f2007-10-16 01:26:03 -0700157 static unsigned long __initdata required_movablecore;
Adrian Bunkb69a7282008-07-23 21:28:12 -0700158 static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
Mel Gorman2a1e2742007-07-17 04:03:12 -0700159
160 /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
161 int movable_zone;
162 EXPORT_SYMBOL(movable_zone);
Mel Gormanc7132162006-09-27 01:49:43 -0700163#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
164
Miklos Szeredi418508c2007-05-23 13:57:55 -0700165#if MAX_NUMNODES > 1
166int nr_node_ids __read_mostly = MAX_NUMNODES;
167EXPORT_SYMBOL(nr_node_ids);
168#endif
169
Mel Gorman9ef9acb2007-10-16 01:25:54 -0700170int page_group_by_mobility_disabled __read_mostly;
171
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700172static void set_pageblock_migratetype(struct page *page, int migratetype)
173{
174 set_pageblock_flags_group(page, (unsigned long)migratetype,
175 PB_migrate, PB_migrate_end);
176}
177
Nick Piggin13e74442006-01-06 00:10:58 -0800178#ifdef CONFIG_DEBUG_VM
Dave Hansenc6a57e12005-10-29 18:16:52 -0700179static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180{
Dave Hansenbdc8cb92005-10-29 18:16:53 -0700181 int ret = 0;
182 unsigned seq;
183 unsigned long pfn = page_to_pfn(page);
Dave Hansenc6a57e12005-10-29 18:16:52 -0700184
Dave Hansenbdc8cb92005-10-29 18:16:53 -0700185 do {
186 seq = zone_span_seqbegin(zone);
187 if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
188 ret = 1;
189 else if (pfn < zone->zone_start_pfn)
190 ret = 1;
191 } while (zone_span_seqretry(zone, seq));
192
193 return ret;
Dave Hansenc6a57e12005-10-29 18:16:52 -0700194}
195
196static int page_is_consistent(struct zone *zone, struct page *page)
197{
Andy Whitcroft14e07292007-05-06 14:49:14 -0700198 if (!pfn_valid_within(page_to_pfn(page)))
Dave Hansenc6a57e12005-10-29 18:16:52 -0700199 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700200 if (zone != page_zone(page))
Dave Hansenc6a57e12005-10-29 18:16:52 -0700201 return 0;
202
203 return 1;
204}
205/*
206 * Temporary debugging check for pages not lying within a given zone.
207 */
208static int bad_range(struct zone *zone, struct page *page)
209{
210 if (page_outside_zone_boundaries(zone, page))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211 return 1;
Dave Hansenc6a57e12005-10-29 18:16:52 -0700212 if (!page_is_consistent(zone, page))
213 return 1;
214
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 return 0;
216}
Nick Piggin13e74442006-01-06 00:10:58 -0800217#else
218static inline int bad_range(struct zone *zone, struct page *page)
219{
220 return 0;
221}
222#endif
223
Nick Piggin224abf92006-01-06 00:11:11 -0800224static void bad_page(struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700225{
Hugh Dickins9442ec9d2008-03-04 14:29:07 -0800226 printk(KERN_EMERG "Bad page state in process '%s'\n" KERN_EMERG
227 "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n",
Nick Piggin224abf92006-01-06 00:11:11 -0800228 current->comm, page, (int)(2*sizeof(unsigned long)),
229 (unsigned long)page->flags, page->mapping,
230 page_mapcount(page), page_count(page));
KAMEZAWA Hiroyuki52d4b9a2008-10-18 20:28:16 -0700231
Hugh Dickins9442ec9d2008-03-04 14:29:07 -0800232 printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n"
233 KERN_EMERG "Backtrace:\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700234 dump_stack();
Russ Andersondfa7e202008-06-09 11:18:45 -0500235 page->flags &= ~PAGE_FLAGS_CLEAR_WHEN_BAD;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236 set_page_count(page, 0);
237 reset_page_mapcount(page);
238 page->mapping = NULL;
Randy Dunlap9f158332005-09-13 01:25:16 -0700239 add_taint(TAINT_BAD_PAGE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240}
241
Linus Torvalds1da177e2005-04-16 15:20:36 -0700242/*
243 * Higher-order pages are called "compound pages". They are structured thusly:
244 *
245 * The first PAGE_SIZE page is called the "head page".
246 *
247 * The remaining PAGE_SIZE pages are called "tail pages".
248 *
249 * All pages have PG_compound set. All pages have their ->private pointing at
250 * the head page (even the head page has this).
251 *
Hugh Dickins41d78ba2006-02-14 13:52:58 -0800252 * The first tail page's ->lru.next holds the address of the compound page's
253 * put_page() function. Its ->lru.prev holds the order of allocation.
254 * This usage means that zero-order pages may not be compound.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255 */
Hugh Dickinsd98c7a02006-02-14 13:52:59 -0800256
257static void free_compound_page(struct page *page)
258{
Christoph Lameterd85f3382007-05-06 14:49:39 -0700259 __free_pages_ok(page, compound_order(page));
Hugh Dickinsd98c7a02006-02-14 13:52:59 -0800260}
261
Andi Kleen01ad1c02008-07-23 21:27:46 -0700262void prep_compound_page(struct page *page, unsigned long order)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263{
264 int i;
265 int nr_pages = 1 << order;
Andy Whitcroft6babc322008-10-02 14:50:18 -0700266 struct page *p = page + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700267
Andy Whitcroft33f2ef82006-12-06 20:33:32 -0800268 set_compound_page_dtor(page, free_compound_page);
Christoph Lameterd85f3382007-05-06 14:49:39 -0700269 set_compound_order(page, order);
Christoph Lameter6d777952007-05-06 14:49:40 -0700270 __SetPageHead(page);
Andy Whitcroft6babc322008-10-02 14:50:18 -0700271 for (i = 1; i < nr_pages; i++, p++) {
272 if (unlikely((i & (MAX_ORDER_NR_PAGES - 1)) == 0))
273 p = pfn_to_page(page_to_pfn(page) + i);
Christoph Lameterd85f3382007-05-06 14:49:39 -0700274 __SetPageTail(p);
Christoph Lameterd85f3382007-05-06 14:49:39 -0700275 p->first_page = page;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276 }
277}
278
279static void destroy_compound_page(struct page *page, unsigned long order)
280{
281 int i;
282 int nr_pages = 1 << order;
Andy Whitcroft6babc322008-10-02 14:50:18 -0700283 struct page *p = page + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700284
Christoph Lameterd85f3382007-05-06 14:49:39 -0700285 if (unlikely(compound_order(page) != order))
Nick Piggin224abf92006-01-06 00:11:11 -0800286 bad_page(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700287
Christoph Lameter6d777952007-05-06 14:49:40 -0700288 if (unlikely(!PageHead(page)))
Christoph Lameterd85f3382007-05-06 14:49:39 -0700289 bad_page(page);
Christoph Lameter6d777952007-05-06 14:49:40 -0700290 __ClearPageHead(page);
Andy Whitcroft6babc322008-10-02 14:50:18 -0700291 for (i = 1; i < nr_pages; i++, p++) {
292 if (unlikely((i & (MAX_ORDER_NR_PAGES - 1)) == 0))
293 p = pfn_to_page(page_to_pfn(page) + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294
Christoph Lameter6d777952007-05-06 14:49:40 -0700295 if (unlikely(!PageTail(p) |
Christoph Lameterd85f3382007-05-06 14:49:39 -0700296 (p->first_page != page)))
Nick Piggin224abf92006-01-06 00:11:11 -0800297 bad_page(page);
Christoph Lameterd85f3382007-05-06 14:49:39 -0700298 __ClearPageTail(p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700299 }
300}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301
Nick Piggin17cf4402006-03-22 00:08:41 -0800302static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
303{
304 int i;
305
Andrew Morton6626c5d2006-03-22 00:08:42 -0800306 /*
307 * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
308 * and __GFP_HIGHMEM from hard or soft interrupt context.
309 */
Nick Piggin725d7042006-09-25 23:30:55 -0700310 VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
Nick Piggin17cf4402006-03-22 00:08:41 -0800311 for (i = 0; i < (1 << order); i++)
312 clear_highpage(page + i);
313}
314
Andrew Morton6aa30012006-04-18 22:20:52 -0700315static inline void set_page_order(struct page *page, int order)
316{
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700317 set_page_private(page, order);
Nick Piggin676165a2006-04-10 11:21:48 +1000318 __SetPageBuddy(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319}
320
321static inline void rmv_page_order(struct page *page)
322{
Nick Piggin676165a2006-04-10 11:21:48 +1000323 __ClearPageBuddy(page);
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700324 set_page_private(page, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700325}
326
327/*
328 * Locate the struct page for both the matching buddy in our
329 * pair (buddy1) and the combined O(n+1) page they form (page).
330 *
331 * 1) Any buddy B1 will have an order O twin B2 which satisfies
332 * the following equation:
333 * B2 = B1 ^ (1 << O)
334 * For example, if the starting buddy (buddy2) is #8 its order
335 * 1 buddy is #10:
336 * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
337 *
338 * 2) Any buddy B will have an order O+1 parent P which
339 * satisfies the following equation:
340 * P = B & ~(1 << O)
341 *
Andreas Mohrd6e05ed2006-06-26 18:35:02 +0200342 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
Linus Torvalds1da177e2005-04-16 15:20:36 -0700343 */
344static inline struct page *
345__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
346{
347 unsigned long buddy_idx = page_idx ^ (1 << order);
348
349 return page + (buddy_idx - page_idx);
350}
351
352static inline unsigned long
353__find_combined_index(unsigned long page_idx, unsigned int order)
354{
355 return (page_idx & ~(1 << order));
356}
357
358/*
359 * This function checks whether a page is free && is the buddy
360 * we can do coalesce a page and its buddy if
Nick Piggin13e74442006-01-06 00:10:58 -0800361 * (a) the buddy is not in a hole &&
Nick Piggin676165a2006-04-10 11:21:48 +1000362 * (b) the buddy is in the buddy system &&
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700363 * (c) a page and its buddy have the same order &&
364 * (d) a page and its buddy are in the same zone.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700365 *
Nick Piggin676165a2006-04-10 11:21:48 +1000366 * For recording whether a page is in the buddy system, we use PG_buddy.
367 * Setting, clearing, and testing PG_buddy is serialized by zone->lock.
368 *
369 * For recording page's order, we use page_private(page).
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370 */
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700371static inline int page_is_buddy(struct page *page, struct page *buddy,
372 int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700373{
Andy Whitcroft14e07292007-05-06 14:49:14 -0700374 if (!pfn_valid_within(page_to_pfn(buddy)))
Nick Piggin13e74442006-01-06 00:10:58 -0800375 return 0;
Nick Piggin13e74442006-01-06 00:10:58 -0800376
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700377 if (page_zone_id(page) != page_zone_id(buddy))
378 return 0;
379
380 if (PageBuddy(buddy) && page_order(buddy) == order) {
381 BUG_ON(page_count(buddy) != 0);
Andrew Morton6aa30012006-04-18 22:20:52 -0700382 return 1;
Nick Piggin676165a2006-04-10 11:21:48 +1000383 }
Andrew Morton6aa30012006-04-18 22:20:52 -0700384 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385}
386
387/*
388 * Freeing function for a buddy system allocator.
389 *
390 * The concept of a buddy system is to maintain direct-mapped table
391 * (containing bit values) for memory blocks of various "orders".
392 * The bottom level table contains the map for the smallest allocatable
393 * units of memory (here, pages), and each level above it describes
394 * pairs of units from the levels below, hence, "buddies".
395 * At a high level, all that happens here is marking the table entry
396 * at the bottom level available, and propagating the changes upward
397 * as necessary, plus some accounting needed to play nicely with other
398 * parts of the VM system.
399 * At each level, we keep a list of pages, which are heads of continuous
Nick Piggin676165a2006-04-10 11:21:48 +1000400 * free pages of length of (1 << order) and marked with PG_buddy. Page's
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700401 * order is recorded in page_private(page) field.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402 * So when we are allocating or freeing one, we can derive the state of the
403 * other. That is, if we allocate a small block, and both were
404 * free, the remainder of the region must be split into blocks.
405 * If a block is freed, and its buddy is also free, then this
406 * triggers coalescing into a block of larger size.
407 *
408 * -- wli
409 */
410
Nick Piggin48db57f2006-01-08 01:00:42 -0800411static inline void __free_one_page(struct page *page,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700412 struct zone *zone, unsigned int order)
413{
414 unsigned long page_idx;
415 int order_size = 1 << order;
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700416 int migratetype = get_pageblock_migratetype(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417
Nick Piggin224abf92006-01-06 00:11:11 -0800418 if (unlikely(PageCompound(page)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419 destroy_compound_page(page, order);
420
421 page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
422
Nick Piggin725d7042006-09-25 23:30:55 -0700423 VM_BUG_ON(page_idx & (order_size - 1));
424 VM_BUG_ON(bad_range(zone, page));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425
Christoph Lameterd23ad422007-02-10 01:43:02 -0800426 __mod_zone_page_state(zone, NR_FREE_PAGES, order_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427 while (order < MAX_ORDER-1) {
428 unsigned long combined_idx;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700429 struct page *buddy;
430
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431 buddy = __page_find_buddy(page, page_idx, order);
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700432 if (!page_is_buddy(page, buddy, order))
Andy Whitcroft3c82d0c2008-07-23 21:27:11 -0700433 break;
Nick Piggin13e74442006-01-06 00:10:58 -0800434
Andy Whitcroft3c82d0c2008-07-23 21:27:11 -0700435 /* Our buddy is free, merge with it and move up one order. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436 list_del(&buddy->lru);
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700437 zone->free_area[order].nr_free--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 rmv_page_order(buddy);
Nick Piggin13e74442006-01-06 00:10:58 -0800439 combined_idx = __find_combined_index(page_idx, order);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700440 page = page + (combined_idx - page_idx);
441 page_idx = combined_idx;
442 order++;
443 }
444 set_page_order(page, order);
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700445 list_add(&page->lru,
446 &zone->free_area[order].free_list[migratetype]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700447 zone->free_area[order].nr_free++;
448}
449
Nick Piggin224abf92006-01-06 00:11:11 -0800450static inline int free_pages_check(struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700451{
Lee Schermerhorn985737c2008-10-18 20:26:53 -0700452 free_page_mlock(page);
Nick Piggin92be2e32006-01-06 00:10:57 -0800453 if (unlikely(page_mapcount(page) |
454 (page->mapping != NULL) |
455 (page_count(page) != 0) |
Russ Andersondfa7e202008-06-09 11:18:45 -0500456 (page->flags & PAGE_FLAGS_CHECK_AT_FREE)))
Nick Piggin224abf92006-01-06 00:11:11 -0800457 bad_page(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700458 if (PageDirty(page))
Nick Piggin242e5462005-09-03 15:54:50 -0700459 __ClearPageDirty(page);
Rik van Rielb2e18532008-10-18 20:26:30 -0700460 if (PageSwapBacked(page))
461 __ClearPageSwapBacked(page);
Hugh Dickins689bceb2005-11-21 21:32:20 -0800462 /*
463 * For now, we report if PG_reserved was found set, but do not
464 * clear it, and do not free the page. But we shall soon need
465 * to do more, for when the ZERO_PAGE count wraps negative.
466 */
467 return PageReserved(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468}
469
470/*
471 * Frees a list of pages.
472 * Assumes all pages on list are in same zone, and of same order.
Renaud Lienhart207f36e2005-09-10 00:26:59 -0700473 * count is the number of pages to free.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700474 *
475 * If the zone was previously in an "all pages pinned" state then look to
476 * see if this freeing clears that state.
477 *
478 * And clear the zone's pages_scanned counter, to hold off the "all pages are
479 * pinned" detection logic.
480 */
Nick Piggin48db57f2006-01-08 01:00:42 -0800481static void free_pages_bulk(struct zone *zone, int count,
482 struct list_head *list, int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483{
Nick Pigginc54ad302006-01-06 00:10:56 -0800484 spin_lock(&zone->lock);
David Rientjese815af92007-10-16 23:25:54 -0700485 zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700486 zone->pages_scanned = 0;
Nick Piggin48db57f2006-01-08 01:00:42 -0800487 while (count--) {
488 struct page *page;
489
Nick Piggin725d7042006-09-25 23:30:55 -0700490 VM_BUG_ON(list_empty(list));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700491 page = list_entry(list->prev, struct page, lru);
Nick Piggin48db57f2006-01-08 01:00:42 -0800492 /* have to delete it as __free_one_page list manipulates */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700493 list_del(&page->lru);
Nick Piggin48db57f2006-01-08 01:00:42 -0800494 __free_one_page(page, zone, order);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700495 }
Nick Pigginc54ad302006-01-06 00:10:56 -0800496 spin_unlock(&zone->lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700497}
498
Nick Piggin48db57f2006-01-08 01:00:42 -0800499static void free_one_page(struct zone *zone, struct page *page, int order)
500{
Christoph Lameter006d22d2006-09-25 23:31:48 -0700501 spin_lock(&zone->lock);
David Rientjese815af92007-10-16 23:25:54 -0700502 zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
Christoph Lameter006d22d2006-09-25 23:31:48 -0700503 zone->pages_scanned = 0;
Paul Jackson0798e512006-12-06 20:31:38 -0800504 __free_one_page(page, zone, order);
Christoph Lameter006d22d2006-09-25 23:31:48 -0700505 spin_unlock(&zone->lock);
Nick Piggin48db57f2006-01-08 01:00:42 -0800506}
507
508static void __free_pages_ok(struct page *page, unsigned int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700509{
Nick Pigginc54ad302006-01-06 00:10:56 -0800510 unsigned long flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700511 int i;
Hugh Dickins689bceb2005-11-21 21:32:20 -0800512 int reserved = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514 for (i = 0 ; i < (1 << order) ; ++i)
Nick Piggin224abf92006-01-06 00:11:11 -0800515 reserved += free_pages_check(page + i);
Hugh Dickins689bceb2005-11-21 21:32:20 -0800516 if (reserved)
517 return;
518
Thomas Gleixner3ac7fe52008-04-30 00:55:01 -0700519 if (!PageHighMem(page)) {
Nick Piggin9858db52006-10-11 01:21:30 -0700520 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
Thomas Gleixner3ac7fe52008-04-30 00:55:01 -0700521 debug_check_no_obj_freed(page_address(page),
522 PAGE_SIZE << order);
523 }
Nick Piggindafb1362006-10-11 01:21:30 -0700524 arch_free_page(page, order);
Nick Piggin48db57f2006-01-08 01:00:42 -0800525 kernel_map_pages(page, 1 << order, 0);
Nick Piggindafb1362006-10-11 01:21:30 -0700526
Nick Pigginc54ad302006-01-06 00:10:56 -0800527 local_irq_save(flags);
Christoph Lameterf8891e52006-06-30 01:55:45 -0700528 __count_vm_events(PGFREE, 1 << order);
Nick Piggin48db57f2006-01-08 01:00:42 -0800529 free_one_page(page_zone(page), page, order);
Nick Pigginc54ad302006-01-06 00:10:56 -0800530 local_irq_restore(flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531}
532
David Howellsa226f6c2006-01-06 00:11:08 -0800533/*
534 * permit the bootmem allocator to evade page validation on high-order frees
535 */
Yasunori Gotoaf370fb2008-07-23 21:28:17 -0700536void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
David Howellsa226f6c2006-01-06 00:11:08 -0800537{
538 if (order == 0) {
539 __ClearPageReserved(page);
540 set_page_count(page, 0);
Nick Piggin7835e982006-03-22 00:08:40 -0800541 set_page_refcounted(page);
Nick Piggin545b1ea2006-03-22 00:08:07 -0800542 __free_page(page);
David Howellsa226f6c2006-01-06 00:11:08 -0800543 } else {
David Howellsa226f6c2006-01-06 00:11:08 -0800544 int loop;
545
Nick Piggin545b1ea2006-03-22 00:08:07 -0800546 prefetchw(page);
David Howellsa226f6c2006-01-06 00:11:08 -0800547 for (loop = 0; loop < BITS_PER_LONG; loop++) {
548 struct page *p = &page[loop];
549
Nick Piggin545b1ea2006-03-22 00:08:07 -0800550 if (loop + 1 < BITS_PER_LONG)
551 prefetchw(p + 1);
David Howellsa226f6c2006-01-06 00:11:08 -0800552 __ClearPageReserved(p);
553 set_page_count(p, 0);
554 }
555
Nick Piggin7835e982006-03-22 00:08:40 -0800556 set_page_refcounted(page);
Nick Piggin545b1ea2006-03-22 00:08:07 -0800557 __free_pages(page, order);
David Howellsa226f6c2006-01-06 00:11:08 -0800558 }
559}
560
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561
562/*
563 * The order of subdivision here is critical for the IO subsystem.
564 * Please do not alter this order without good reasons and regression
565 * testing. Specifically, as large blocks of memory are subdivided,
566 * the order in which smaller blocks are delivered depends on the order
567 * they're subdivided in this function. This is the primary factor
568 * influencing the order in which pages are delivered to the IO
569 * subsystem according to empirical testing, and this is also justified
570 * by considering the behavior of a buddy system containing a single
571 * large block of memory acted on by a series of small allocations.
572 * This behavior is a critical factor in sglist merging's success.
573 *
574 * -- wli
575 */
Nick Piggin085cc7d2006-01-06 00:11:01 -0800576static inline void expand(struct zone *zone, struct page *page,
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700577 int low, int high, struct free_area *area,
578 int migratetype)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579{
580 unsigned long size = 1 << high;
581
582 while (high > low) {
583 area--;
584 high--;
585 size >>= 1;
Nick Piggin725d7042006-09-25 23:30:55 -0700586 VM_BUG_ON(bad_range(zone, &page[size]));
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700587 list_add(&page[size].lru, &area->free_list[migratetype]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700588 area->nr_free++;
589 set_page_order(&page[size], high);
590 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591}
592
Linus Torvalds1da177e2005-04-16 15:20:36 -0700593/*
594 * This page is about to be returned from the page allocator
595 */
Nick Piggin17cf4402006-03-22 00:08:41 -0800596static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597{
Nick Piggin92be2e32006-01-06 00:10:57 -0800598 if (unlikely(page_mapcount(page) |
599 (page->mapping != NULL) |
600 (page_count(page) != 0) |
Russ Andersondfa7e202008-06-09 11:18:45 -0500601 (page->flags & PAGE_FLAGS_CHECK_AT_PREP)))
Nick Piggin224abf92006-01-06 00:11:11 -0800602 bad_page(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700603
Hugh Dickins689bceb2005-11-21 21:32:20 -0800604 /*
605 * For now, we report if PG_reserved was found set, but do not
606 * clear it, and do not allocate the page: as a safety net.
607 */
608 if (PageReserved(page))
609 return 1;
610
Christoph Lameter0a128b22008-04-28 02:12:52 -0700611 page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 1 << PG_reclaim |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612 1 << PG_referenced | 1 << PG_arch_1 |
Nick Pigginb291f002008-10-18 20:26:44 -0700613 1 << PG_owner_priv_1 | 1 << PG_mappedtodisk
614#ifdef CONFIG_UNEVICTABLE_LRU
615 | 1 << PG_mlocked
616#endif
617 );
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700618 set_page_private(page, 0);
Nick Piggin7835e982006-03-22 00:08:40 -0800619 set_page_refcounted(page);
Nick Piggincc102502006-12-06 20:32:00 -0800620
621 arch_alloc_page(page, order);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700622 kernel_map_pages(page, 1 << order, 1);
Nick Piggin17cf4402006-03-22 00:08:41 -0800623
624 if (gfp_flags & __GFP_ZERO)
625 prep_zero_page(page, order, gfp_flags);
626
627 if (order && (gfp_flags & __GFP_COMP))
628 prep_compound_page(page, order);
629
Hugh Dickins689bceb2005-11-21 21:32:20 -0800630 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700631}
632
Mel Gorman56fd56b2007-10-16 01:25:58 -0700633/*
634 * Go through the free lists for the given migratetype and remove
635 * the smallest available page from the freelists
636 */
637static struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
638 int migratetype)
639{
640 unsigned int current_order;
641 struct free_area * area;
642 struct page *page;
643
644 /* Find a page of the appropriate size in the preferred list */
645 for (current_order = order; current_order < MAX_ORDER; ++current_order) {
646 area = &(zone->free_area[current_order]);
647 if (list_empty(&area->free_list[migratetype]))
648 continue;
649
650 page = list_entry(area->free_list[migratetype].next,
651 struct page, lru);
652 list_del(&page->lru);
653 rmv_page_order(page);
654 area->nr_free--;
655 __mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
656 expand(zone, page, order, current_order, area, migratetype);
657 return page;
658 }
659
660 return NULL;
661}
662
663
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700664/*
665 * This array describes the order lists are fallen back to when
666 * the free lists for the desirable migrate type are depleted
667 */
668static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
Mel Gorman64c5e132007-10-16 01:25:59 -0700669 [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
670 [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
671 [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
672 [MIGRATE_RESERVE] = { MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE }, /* Never used */
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700673};
674
Mel Gormanc361be52007-10-16 01:25:51 -0700675/*
676 * Move the free pages in a range to the free lists of the requested type.
Mel Gormand9c23402007-10-16 01:26:01 -0700677 * Note that start_page and end_pages are not aligned on a pageblock
Mel Gormanc361be52007-10-16 01:25:51 -0700678 * boundary. If alignment is required, use move_freepages_block()
679 */
Adrian Bunkb69a7282008-07-23 21:28:12 -0700680static int move_freepages(struct zone *zone,
681 struct page *start_page, struct page *end_page,
682 int migratetype)
Mel Gormanc361be52007-10-16 01:25:51 -0700683{
684 struct page *page;
685 unsigned long order;
Mel Gormand1003132007-10-16 01:26:00 -0700686 int pages_moved = 0;
Mel Gormanc361be52007-10-16 01:25:51 -0700687
688#ifndef CONFIG_HOLES_IN_ZONE
689 /*
690 * page_zone is not safe to call in this context when
691 * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
692 * anyway as we check zone boundaries in move_freepages_block().
693 * Remove at a later date when no bug reports exist related to
Mel Gormanac0e5b72007-10-16 01:25:58 -0700694 * grouping pages by mobility
Mel Gormanc361be52007-10-16 01:25:51 -0700695 */
696 BUG_ON(page_zone(start_page) != page_zone(end_page));
697#endif
698
699 for (page = start_page; page <= end_page;) {
Adam Litke344c7902008-09-02 14:35:38 -0700700 /* Make sure we are not inadvertently changing nodes */
701 VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));
702
Mel Gormanc361be52007-10-16 01:25:51 -0700703 if (!pfn_valid_within(page_to_pfn(page))) {
704 page++;
705 continue;
706 }
707
708 if (!PageBuddy(page)) {
709 page++;
710 continue;
711 }
712
713 order = page_order(page);
714 list_del(&page->lru);
715 list_add(&page->lru,
716 &zone->free_area[order].free_list[migratetype]);
717 page += 1 << order;
Mel Gormand1003132007-10-16 01:26:00 -0700718 pages_moved += 1 << order;
Mel Gormanc361be52007-10-16 01:25:51 -0700719 }
720
Mel Gormand1003132007-10-16 01:26:00 -0700721 return pages_moved;
Mel Gormanc361be52007-10-16 01:25:51 -0700722}
723
Adrian Bunkb69a7282008-07-23 21:28:12 -0700724static int move_freepages_block(struct zone *zone, struct page *page,
725 int migratetype)
Mel Gormanc361be52007-10-16 01:25:51 -0700726{
727 unsigned long start_pfn, end_pfn;
728 struct page *start_page, *end_page;
729
730 start_pfn = page_to_pfn(page);
Mel Gormand9c23402007-10-16 01:26:01 -0700731 start_pfn = start_pfn & ~(pageblock_nr_pages-1);
Mel Gormanc361be52007-10-16 01:25:51 -0700732 start_page = pfn_to_page(start_pfn);
Mel Gormand9c23402007-10-16 01:26:01 -0700733 end_page = start_page + pageblock_nr_pages - 1;
734 end_pfn = start_pfn + pageblock_nr_pages - 1;
Mel Gormanc361be52007-10-16 01:25:51 -0700735
736 /* Do not cross zone boundaries */
737 if (start_pfn < zone->zone_start_pfn)
738 start_page = page;
739 if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
740 return 0;
741
742 return move_freepages(zone, start_page, end_page, migratetype);
743}
744
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700745/* Remove an element from the buddy allocator from the fallback list */
746static struct page *__rmqueue_fallback(struct zone *zone, int order,
747 int start_migratetype)
748{
749 struct free_area * area;
750 int current_order;
751 struct page *page;
752 int migratetype, i;
753
754 /* Find the largest possible block of pages in the other list */
755 for (current_order = MAX_ORDER-1; current_order >= order;
756 --current_order) {
757 for (i = 0; i < MIGRATE_TYPES - 1; i++) {
758 migratetype = fallbacks[start_migratetype][i];
759
Mel Gorman56fd56b2007-10-16 01:25:58 -0700760 /* MIGRATE_RESERVE handled later if necessary */
761 if (migratetype == MIGRATE_RESERVE)
762 continue;
Mel Gormane0104872007-10-16 01:25:53 -0700763
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700764 area = &(zone->free_area[current_order]);
765 if (list_empty(&area->free_list[migratetype]))
766 continue;
767
768 page = list_entry(area->free_list[migratetype].next,
769 struct page, lru);
770 area->nr_free--;
771
772 /*
Mel Gormanc361be52007-10-16 01:25:51 -0700773 * If breaking a large block of pages, move all free
Mel Gorman46dafbc2007-10-16 01:25:55 -0700774 * pages to the preferred allocation list. If falling
775 * back for a reclaimable kernel allocation, be more
776 * agressive about taking ownership of free pages
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700777 */
Mel Gormand9c23402007-10-16 01:26:01 -0700778 if (unlikely(current_order >= (pageblock_order >> 1)) ||
Mel Gorman46dafbc2007-10-16 01:25:55 -0700779 start_migratetype == MIGRATE_RECLAIMABLE) {
780 unsigned long pages;
781 pages = move_freepages_block(zone, page,
782 start_migratetype);
783
784 /* Claim the whole block if over half of it is free */
Mel Gormand9c23402007-10-16 01:26:01 -0700785 if (pages >= (1 << (pageblock_order-1)))
Mel Gorman46dafbc2007-10-16 01:25:55 -0700786 set_pageblock_migratetype(page,
787 start_migratetype);
788
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700789 migratetype = start_migratetype;
Mel Gormanc361be52007-10-16 01:25:51 -0700790 }
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700791
792 /* Remove the page from the freelists */
793 list_del(&page->lru);
794 rmv_page_order(page);
795 __mod_zone_page_state(zone, NR_FREE_PAGES,
796 -(1UL << order));
797
Mel Gormand9c23402007-10-16 01:26:01 -0700798 if (current_order == pageblock_order)
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700799 set_pageblock_migratetype(page,
800 start_migratetype);
801
802 expand(zone, page, order, current_order, area, migratetype);
803 return page;
804 }
805 }
806
Mel Gorman56fd56b2007-10-16 01:25:58 -0700807 /* Use MIGRATE_RESERVE rather than fail an allocation */
808 return __rmqueue_smallest(zone, order, MIGRATE_RESERVE);
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700809}
810
Mel Gorman56fd56b2007-10-16 01:25:58 -0700811/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700812 * Do the hard work of removing an element from the buddy allocator.
813 * Call me with the zone->lock already held.
814 */
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700815static struct page *__rmqueue(struct zone *zone, unsigned int order,
816 int migratetype)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700817{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700818 struct page *page;
819
Mel Gorman56fd56b2007-10-16 01:25:58 -0700820 page = __rmqueue_smallest(zone, order, migratetype);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700821
Mel Gorman56fd56b2007-10-16 01:25:58 -0700822 if (unlikely(!page))
823 page = __rmqueue_fallback(zone, order, migratetype);
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700824
825 return page;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700826}
827
828/*
829 * Obtain a specified number of elements from the buddy allocator, all under
830 * a single hold of the lock, for efficiency. Add them to the supplied list.
831 * Returns the number of new pages which were placed at *list.
832 */
833static int rmqueue_bulk(struct zone *zone, unsigned int order,
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700834 unsigned long count, struct list_head *list,
835 int migratetype)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700837 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838
Nick Pigginc54ad302006-01-06 00:10:56 -0800839 spin_lock(&zone->lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700840 for (i = 0; i < count; ++i) {
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700841 struct page *page = __rmqueue(zone, order, migratetype);
Nick Piggin085cc7d2006-01-06 00:11:01 -0800842 if (unlikely(page == NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700843 break;
Mel Gorman81eabcb2007-12-17 16:20:05 -0800844
845 /*
846 * Split buddy pages returned by expand() are received here
847 * in physical page order. The page is added to the callers and
848 * list and the list head then moves forward. From the callers
849 * perspective, the linked list is ordered by page number in
850 * some conditions. This is useful for IO devices that can
851 * merge IO requests if the physical pages are ordered
852 * properly.
853 */
Mel Gorman535131e2007-10-16 01:25:49 -0700854 list_add(&page->lru, list);
855 set_page_private(page, migratetype);
Mel Gorman81eabcb2007-12-17 16:20:05 -0800856 list = &page->lru;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700857 }
Nick Pigginc54ad302006-01-06 00:10:56 -0800858 spin_unlock(&zone->lock);
Nick Piggin085cc7d2006-01-06 00:11:01 -0800859 return i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860}
861
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700862#ifdef CONFIG_NUMA
Christoph Lameter8fce4d82006-03-09 17:33:54 -0800863/*
Christoph Lameter4037d452007-05-09 02:35:14 -0700864 * Called from the vmstat counter updater to drain pagesets of this
865 * currently executing processor on remote nodes after they have
866 * expired.
867 *
Christoph Lameter879336c2006-03-22 00:09:08 -0800868 * Note that this function must be called with the thread pinned to
869 * a single processor.
Christoph Lameter8fce4d82006-03-09 17:33:54 -0800870 */
Christoph Lameter4037d452007-05-09 02:35:14 -0700871void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700872{
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700873 unsigned long flags;
Christoph Lameter4037d452007-05-09 02:35:14 -0700874 int to_drain;
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700875
Christoph Lameter4037d452007-05-09 02:35:14 -0700876 local_irq_save(flags);
877 if (pcp->count >= pcp->batch)
878 to_drain = pcp->batch;
879 else
880 to_drain = pcp->count;
881 free_pages_bulk(zone, to_drain, &pcp->list, 0);
882 pcp->count -= to_drain;
883 local_irq_restore(flags);
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700884}
885#endif
886
Christoph Lameter9f8f2172008-02-04 22:29:11 -0800887/*
888 * Drain pages of the indicated processor.
889 *
890 * The processor must either be the current processor and the
891 * thread pinned to the current processor or a processor that
892 * is not online.
893 */
894static void drain_pages(unsigned int cpu)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895{
Nick Pigginc54ad302006-01-06 00:10:56 -0800896 unsigned long flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700897 struct zone *zone;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898
899 for_each_zone(zone) {
900 struct per_cpu_pageset *pset;
Christoph Lameter3dfa5722008-02-04 22:29:19 -0800901 struct per_cpu_pages *pcp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902
Christoph Lameterf2e12bb2007-01-05 16:37:02 -0800903 if (!populated_zone(zone))
904 continue;
905
Christoph Lametere7c8d5c2005-06-21 17:14:47 -0700906 pset = zone_pcp(zone, cpu);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700907
Christoph Lameter3dfa5722008-02-04 22:29:19 -0800908 pcp = &pset->pcp;
909 local_irq_save(flags);
910 free_pages_bulk(zone, pcp->count, &pcp->list, 0);
911 pcp->count = 0;
912 local_irq_restore(flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913 }
914}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700915
Christoph Lameter9f8f2172008-02-04 22:29:11 -0800916/*
917 * Spill all of this CPU's per-cpu pages back into the buddy allocator.
918 */
919void drain_local_pages(void *arg)
920{
921 drain_pages(smp_processor_id());
922}
923
924/*
925 * Spill all the per-cpu pages from all CPUs back into the buddy allocator
926 */
927void drain_all_pages(void)
928{
Jens Axboe15c8b6c2008-05-09 09:39:44 +0200929 on_each_cpu(drain_local_pages, NULL, 1);
Christoph Lameter9f8f2172008-02-04 22:29:11 -0800930}
931
Rafael J. Wysocki296699d2007-07-29 23:27:18 +0200932#ifdef CONFIG_HIBERNATION
Linus Torvalds1da177e2005-04-16 15:20:36 -0700933
934void mark_free_pages(struct zone *zone)
935{
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700936 unsigned long pfn, max_zone_pfn;
937 unsigned long flags;
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700938 int order, t;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939 struct list_head *curr;
940
941 if (!zone->spanned_pages)
942 return;
943
944 spin_lock_irqsave(&zone->lock, flags);
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700945
946 max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
947 for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
948 if (pfn_valid(pfn)) {
949 struct page *page = pfn_to_page(pfn);
950
Rafael J. Wysocki7be98232007-05-06 14:50:42 -0700951 if (!swsusp_page_is_forbidden(page))
952 swsusp_unset_page_free(page);
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700953 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700955 for_each_migratetype_order(order, t) {
956 list_for_each(curr, &zone->free_area[order].free_list[t]) {
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700957 unsigned long i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700958
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700959 pfn = page_to_pfn(list_entry(curr, struct page, lru));
960 for (i = 0; i < (1UL << order); i++)
Rafael J. Wysocki7be98232007-05-06 14:50:42 -0700961 swsusp_set_page_free(pfn_to_page(pfn + i));
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700962 }
Mel Gormanb2a0ac82007-10-16 01:25:48 -0700963 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700964 spin_unlock_irqrestore(&zone->lock, flags);
965}
Mel Gormane2c55dc2007-10-16 01:25:50 -0700966#endif /* CONFIG_PM */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967
968/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700969 * Free a 0-order page
970 */
Harvey Harrison920c7a52008-02-04 22:29:26 -0800971static void free_hot_cold_page(struct page *page, int cold)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700972{
973 struct zone *zone = page_zone(page);
974 struct per_cpu_pages *pcp;
975 unsigned long flags;
976
Linus Torvalds1da177e2005-04-16 15:20:36 -0700977 if (PageAnon(page))
978 page->mapping = NULL;
Nick Piggin224abf92006-01-06 00:11:11 -0800979 if (free_pages_check(page))
Hugh Dickins689bceb2005-11-21 21:32:20 -0800980 return;
981
Thomas Gleixner3ac7fe52008-04-30 00:55:01 -0700982 if (!PageHighMem(page)) {
Nick Piggin9858db52006-10-11 01:21:30 -0700983 debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
Thomas Gleixner3ac7fe52008-04-30 00:55:01 -0700984 debug_check_no_obj_freed(page_address(page), PAGE_SIZE);
985 }
Nick Piggindafb1362006-10-11 01:21:30 -0700986 arch_free_page(page, 0);
Hugh Dickins689bceb2005-11-21 21:32:20 -0800987 kernel_map_pages(page, 1, 0);
988
Christoph Lameter3dfa5722008-02-04 22:29:19 -0800989 pcp = &zone_pcp(zone, get_cpu())->pcp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700990 local_irq_save(flags);
Christoph Lameterf8891e52006-06-30 01:55:45 -0700991 __count_vm_event(PGFREE);
Christoph Lameter3dfa5722008-02-04 22:29:19 -0800992 if (cold)
993 list_add_tail(&page->lru, &pcp->list);
994 else
995 list_add(&page->lru, &pcp->list);
Mel Gorman535131e2007-10-16 01:25:49 -0700996 set_page_private(page, get_pageblock_migratetype(page));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700997 pcp->count++;
Nick Piggin48db57f2006-01-08 01:00:42 -0800998 if (pcp->count >= pcp->high) {
999 free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
1000 pcp->count -= pcp->batch;
1001 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001002 local_irq_restore(flags);
1003 put_cpu();
1004}
1005
Harvey Harrison920c7a52008-02-04 22:29:26 -08001006void free_hot_page(struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001007{
1008 free_hot_cold_page(page, 0);
1009}
1010
Harvey Harrison920c7a52008-02-04 22:29:26 -08001011void free_cold_page(struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001012{
1013 free_hot_cold_page(page, 1);
1014}
1015
Nick Piggin8dfcc9b2006-03-22 00:08:05 -08001016/*
1017 * split_page takes a non-compound higher-order page, and splits it into
1018 * n (1<<order) sub-pages: page[0..n]
1019 * Each sub-page must be freed individually.
1020 *
1021 * Note: this is probably too low level an operation for use in drivers.
1022 * Please consult with lkml before using this in your driver.
1023 */
1024void split_page(struct page *page, unsigned int order)
1025{
1026 int i;
1027
Nick Piggin725d7042006-09-25 23:30:55 -07001028 VM_BUG_ON(PageCompound(page));
1029 VM_BUG_ON(!page_count(page));
Nick Piggin7835e982006-03-22 00:08:40 -08001030 for (i = 1; i < (1 << order); i++)
1031 set_page_refcounted(page + i);
Nick Piggin8dfcc9b2006-03-22 00:08:05 -08001032}
Nick Piggin8dfcc9b2006-03-22 00:08:05 -08001033
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034/*
1035 * Really, prep_compound_page() should be called from __rmqueue_bulk(). But
1036 * we cheat by calling it from here, in the order > 0 path. Saves a branch
1037 * or two.
1038 */
Mel Gorman18ea7e72008-04-28 02:12:14 -07001039static struct page *buffered_rmqueue(struct zone *preferred_zone,
Nick Piggina74609f2006-01-06 00:11:20 -08001040 struct zone *zone, int order, gfp_t gfp_flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001041{
1042 unsigned long flags;
Hugh Dickins689bceb2005-11-21 21:32:20 -08001043 struct page *page;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044 int cold = !!(gfp_flags & __GFP_COLD);
Nick Piggina74609f2006-01-06 00:11:20 -08001045 int cpu;
Mel Gorman64c5e132007-10-16 01:25:59 -07001046 int migratetype = allocflags_to_migratetype(gfp_flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001047
Hugh Dickins689bceb2005-11-21 21:32:20 -08001048again:
Nick Piggina74609f2006-01-06 00:11:20 -08001049 cpu = get_cpu();
Nick Piggin48db57f2006-01-08 01:00:42 -08001050 if (likely(order == 0)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051 struct per_cpu_pages *pcp;
1052
Christoph Lameter3dfa5722008-02-04 22:29:19 -08001053 pcp = &zone_pcp(zone, cpu)->pcp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001054 local_irq_save(flags);
Nick Piggina74609f2006-01-06 00:11:20 -08001055 if (!pcp->count) {
nkalmala941c7102006-11-02 22:07:04 -08001056 pcp->count = rmqueue_bulk(zone, 0,
Mel Gormanb2a0ac82007-10-16 01:25:48 -07001057 pcp->batch, &pcp->list, migratetype);
Nick Piggina74609f2006-01-06 00:11:20 -08001058 if (unlikely(!pcp->count))
1059 goto failed;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001060 }
Mel Gorman535131e2007-10-16 01:25:49 -07001061
Mel Gormanb92a6ed2007-10-16 01:25:50 -07001062 /* Find a page of the appropriate migrate type */
Christoph Lameter3dfa5722008-02-04 22:29:19 -08001063 if (cold) {
1064 list_for_each_entry_reverse(page, &pcp->list, lru)
1065 if (page_private(page) == migratetype)
1066 break;
1067 } else {
1068 list_for_each_entry(page, &pcp->list, lru)
1069 if (page_private(page) == migratetype)
1070 break;
1071 }
Mel Gormanb92a6ed2007-10-16 01:25:50 -07001072
1073 /* Allocate more to the pcp list if necessary */
1074 if (unlikely(&page->lru == &pcp->list)) {
Mel Gorman535131e2007-10-16 01:25:49 -07001075 pcp->count += rmqueue_bulk(zone, 0,
1076 pcp->batch, &pcp->list, migratetype);
1077 page = list_entry(pcp->list.next, struct page, lru);
Mel Gorman535131e2007-10-16 01:25:49 -07001078 }
Mel Gormanb92a6ed2007-10-16 01:25:50 -07001079
1080 list_del(&page->lru);
1081 pcp->count--;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001082 } else {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001083 spin_lock_irqsave(&zone->lock, flags);
Mel Gormanb2a0ac82007-10-16 01:25:48 -07001084 page = __rmqueue(zone, order, migratetype);
Nick Piggina74609f2006-01-06 00:11:20 -08001085 spin_unlock(&zone->lock);
1086 if (!page)
1087 goto failed;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001088 }
1089
Christoph Lameterf8891e52006-06-30 01:55:45 -07001090 __count_zone_vm_events(PGALLOC, zone, 1 << order);
Mel Gorman18ea7e72008-04-28 02:12:14 -07001091 zone_statistics(preferred_zone, zone);
Nick Piggina74609f2006-01-06 00:11:20 -08001092 local_irq_restore(flags);
1093 put_cpu();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001094
Nick Piggin725d7042006-09-25 23:30:55 -07001095 VM_BUG_ON(bad_range(zone, page));
Nick Piggin17cf4402006-03-22 00:08:41 -08001096 if (prep_new_page(page, order, gfp_flags))
Nick Piggina74609f2006-01-06 00:11:20 -08001097 goto again;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001098 return page;
Nick Piggina74609f2006-01-06 00:11:20 -08001099
1100failed:
1101 local_irq_restore(flags);
1102 put_cpu();
1103 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001104}
1105
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001106#define ALLOC_NO_WATERMARKS 0x01 /* don't check watermarks at all */
Nick Piggin31488902005-11-28 13:44:03 -08001107#define ALLOC_WMARK_MIN 0x02 /* use pages_min watermark */
1108#define ALLOC_WMARK_LOW 0x04 /* use pages_low watermark */
1109#define ALLOC_WMARK_HIGH 0x08 /* use pages_high watermark */
1110#define ALLOC_HARDER 0x10 /* try to alloc harder */
1111#define ALLOC_HIGH 0x20 /* __GFP_HIGH set */
1112#define ALLOC_CPUSET 0x40 /* check for correct cpuset */
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001113
Akinobu Mita933e3122006-12-08 02:39:45 -08001114#ifdef CONFIG_FAIL_PAGE_ALLOC
1115
1116static struct fail_page_alloc_attr {
1117 struct fault_attr attr;
1118
1119 u32 ignore_gfp_highmem;
1120 u32 ignore_gfp_wait;
Akinobu Mita54114992007-07-15 23:40:23 -07001121 u32 min_order;
Akinobu Mita933e3122006-12-08 02:39:45 -08001122
1123#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1124
1125 struct dentry *ignore_gfp_highmem_file;
1126 struct dentry *ignore_gfp_wait_file;
Akinobu Mita54114992007-07-15 23:40:23 -07001127 struct dentry *min_order_file;
Akinobu Mita933e3122006-12-08 02:39:45 -08001128
1129#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1130
1131} fail_page_alloc = {
1132 .attr = FAULT_ATTR_INITIALIZER,
Don Mullis6b1b60f2006-12-08 02:39:53 -08001133 .ignore_gfp_wait = 1,
1134 .ignore_gfp_highmem = 1,
Akinobu Mita54114992007-07-15 23:40:23 -07001135 .min_order = 1,
Akinobu Mita933e3122006-12-08 02:39:45 -08001136};
1137
1138static int __init setup_fail_page_alloc(char *str)
1139{
1140 return setup_fault_attr(&fail_page_alloc.attr, str);
1141}
1142__setup("fail_page_alloc=", setup_fail_page_alloc);
1143
1144static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1145{
Akinobu Mita54114992007-07-15 23:40:23 -07001146 if (order < fail_page_alloc.min_order)
1147 return 0;
Akinobu Mita933e3122006-12-08 02:39:45 -08001148 if (gfp_mask & __GFP_NOFAIL)
1149 return 0;
1150 if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
1151 return 0;
1152 if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
1153 return 0;
1154
1155 return should_fail(&fail_page_alloc.attr, 1 << order);
1156}
1157
1158#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1159
1160static int __init fail_page_alloc_debugfs(void)
1161{
1162 mode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
1163 struct dentry *dir;
1164 int err;
1165
1166 err = init_fault_attr_dentries(&fail_page_alloc.attr,
1167 "fail_page_alloc");
1168 if (err)
1169 return err;
1170 dir = fail_page_alloc.attr.dentries.dir;
1171
1172 fail_page_alloc.ignore_gfp_wait_file =
1173 debugfs_create_bool("ignore-gfp-wait", mode, dir,
1174 &fail_page_alloc.ignore_gfp_wait);
1175
1176 fail_page_alloc.ignore_gfp_highmem_file =
1177 debugfs_create_bool("ignore-gfp-highmem", mode, dir,
1178 &fail_page_alloc.ignore_gfp_highmem);
Akinobu Mita54114992007-07-15 23:40:23 -07001179 fail_page_alloc.min_order_file =
1180 debugfs_create_u32("min-order", mode, dir,
1181 &fail_page_alloc.min_order);
Akinobu Mita933e3122006-12-08 02:39:45 -08001182
1183 if (!fail_page_alloc.ignore_gfp_wait_file ||
Akinobu Mita54114992007-07-15 23:40:23 -07001184 !fail_page_alloc.ignore_gfp_highmem_file ||
1185 !fail_page_alloc.min_order_file) {
Akinobu Mita933e3122006-12-08 02:39:45 -08001186 err = -ENOMEM;
1187 debugfs_remove(fail_page_alloc.ignore_gfp_wait_file);
1188 debugfs_remove(fail_page_alloc.ignore_gfp_highmem_file);
Akinobu Mita54114992007-07-15 23:40:23 -07001189 debugfs_remove(fail_page_alloc.min_order_file);
Akinobu Mita933e3122006-12-08 02:39:45 -08001190 cleanup_fault_attr_dentries(&fail_page_alloc.attr);
1191 }
1192
1193 return err;
1194}
1195
1196late_initcall(fail_page_alloc_debugfs);
1197
1198#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1199
1200#else /* CONFIG_FAIL_PAGE_ALLOC */
1201
1202static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1203{
1204 return 0;
1205}
1206
1207#endif /* CONFIG_FAIL_PAGE_ALLOC */
1208
Linus Torvalds1da177e2005-04-16 15:20:36 -07001209/*
1210 * Return 1 if free pages are above 'mark'. This takes into account the order
1211 * of the allocation.
1212 */
1213int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001214 int classzone_idx, int alloc_flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215{
1216 /* free_pages my go negative - that's OK */
Christoph Lameterd23ad422007-02-10 01:43:02 -08001217 long min = mark;
1218 long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001219 int o;
1220
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001221 if (alloc_flags & ALLOC_HIGH)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222 min -= min / 2;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001223 if (alloc_flags & ALLOC_HARDER)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001224 min -= min / 4;
1225
1226 if (free_pages <= min + z->lowmem_reserve[classzone_idx])
1227 return 0;
1228 for (o = 0; o < order; o++) {
1229 /* At the next order, this order's pages become unavailable */
1230 free_pages -= z->free_area[o].nr_free << o;
1231
1232 /* Require fewer higher order pages to be free */
1233 min >>= 1;
1234
1235 if (free_pages <= min)
1236 return 0;
1237 }
1238 return 1;
1239}
1240
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001241#ifdef CONFIG_NUMA
1242/*
1243 * zlc_setup - Setup for "zonelist cache". Uses cached zone data to
1244 * skip over zones that are not allowed by the cpuset, or that have
1245 * been recently (in last second) found to be nearly full. See further
1246 * comments in mmzone.h. Reduces cache footprint of zonelist scans
Simon Arlott183ff222007-10-20 01:27:18 +02001247 * that have to skip over a lot of full or unallowed zones.
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001248 *
1249 * If the zonelist cache is present in the passed in zonelist, then
1250 * returns a pointer to the allowed node mask (either the current
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07001251 * tasks mems_allowed, or node_states[N_HIGH_MEMORY].)
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001252 *
1253 * If the zonelist cache is not available for this zonelist, does
1254 * nothing and returns NULL.
1255 *
1256 * If the fullzones BITMAP in the zonelist cache is stale (more than
1257 * a second since last zap'd) then we zap it out (clear its bits.)
1258 *
1259 * We hold off even calling zlc_setup, until after we've checked the
1260 * first zone in the zonelist, on the theory that most allocations will
1261 * be satisfied from that first zone, so best to examine that zone as
1262 * quickly as we can.
1263 */
1264static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1265{
1266 struct zonelist_cache *zlc; /* cached zonelist speedup info */
1267 nodemask_t *allowednodes; /* zonelist_cache approximation */
1268
1269 zlc = zonelist->zlcache_ptr;
1270 if (!zlc)
1271 return NULL;
1272
S.Caglar Onurf05111f2008-04-28 02:12:38 -07001273 if (time_after(jiffies, zlc->last_full_zap + HZ)) {
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001274 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1275 zlc->last_full_zap = jiffies;
1276 }
1277
1278 allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
1279 &cpuset_current_mems_allowed :
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07001280 &node_states[N_HIGH_MEMORY];
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001281 return allowednodes;
1282}
1283
1284/*
1285 * Given 'z' scanning a zonelist, run a couple of quick checks to see
1286 * if it is worth looking at further for free memory:
1287 * 1) Check that the zone isn't thought to be full (doesn't have its
1288 * bit set in the zonelist_cache fullzones BITMAP).
1289 * 2) Check that the zones node (obtained from the zonelist_cache
1290 * z_to_n[] mapping) is allowed in the passed in allowednodes mask.
1291 * Return true (non-zero) if zone is worth looking at further, or
1292 * else return false (zero) if it is not.
1293 *
1294 * This check -ignores- the distinction between various watermarks,
1295 * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ... If a zone is
1296 * found to be full for any variation of these watermarks, it will
1297 * be considered full for up to one second by all requests, unless
1298 * we are so low on memory on all allowed nodes that we are forced
1299 * into the second scan of the zonelist.
1300 *
1301 * In the second scan we ignore this zonelist cache and exactly
1302 * apply the watermarks to all zones, even it is slower to do so.
1303 * We are low on memory in the second scan, and should leave no stone
1304 * unturned looking for a free page.
1305 */
Mel Gormandd1a2392008-04-28 02:12:17 -07001306static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001307 nodemask_t *allowednodes)
1308{
1309 struct zonelist_cache *zlc; /* cached zonelist speedup info */
1310 int i; /* index of *z in zonelist zones */
1311 int n; /* node that zone *z is on */
1312
1313 zlc = zonelist->zlcache_ptr;
1314 if (!zlc)
1315 return 1;
1316
Mel Gormandd1a2392008-04-28 02:12:17 -07001317 i = z - zonelist->_zonerefs;
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001318 n = zlc->z_to_n[i];
1319
1320 /* This zone is worth trying if it is allowed but not full */
1321 return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
1322}
1323
1324/*
1325 * Given 'z' scanning a zonelist, set the corresponding bit in
1326 * zlc->fullzones, so that subsequent attempts to allocate a page
1327 * from that zone don't waste time re-examining it.
1328 */
Mel Gormandd1a2392008-04-28 02:12:17 -07001329static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001330{
1331 struct zonelist_cache *zlc; /* cached zonelist speedup info */
1332 int i; /* index of *z in zonelist zones */
1333
1334 zlc = zonelist->zlcache_ptr;
1335 if (!zlc)
1336 return;
1337
Mel Gormandd1a2392008-04-28 02:12:17 -07001338 i = z - zonelist->_zonerefs;
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001339
1340 set_bit(i, zlc->fullzones);
1341}
1342
1343#else /* CONFIG_NUMA */
1344
1345static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1346{
1347 return NULL;
1348}
1349
Mel Gormandd1a2392008-04-28 02:12:17 -07001350static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001351 nodemask_t *allowednodes)
1352{
1353 return 1;
1354}
1355
Mel Gormandd1a2392008-04-28 02:12:17 -07001356static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001357{
1358}
1359#endif /* CONFIG_NUMA */
1360
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001361/*
Paul Jackson0798e512006-12-06 20:31:38 -08001362 * get_page_from_freelist goes through the zonelist trying to allocate
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001363 * a page.
1364 */
1365static struct page *
Mel Gorman19770b32008-04-28 02:12:18 -07001366get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
Mel Gorman54a6eb52008-04-28 02:12:16 -07001367 struct zonelist *zonelist, int high_zoneidx, int alloc_flags)
Martin Hicks753ee722005-06-21 17:14:41 -07001368{
Mel Gormandd1a2392008-04-28 02:12:17 -07001369 struct zoneref *z;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001370 struct page *page = NULL;
Mel Gorman54a6eb52008-04-28 02:12:16 -07001371 int classzone_idx;
Mel Gorman18ea7e72008-04-28 02:12:14 -07001372 struct zone *zone, *preferred_zone;
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001373 nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
1374 int zlc_active = 0; /* set if using zonelist_cache */
1375 int did_zlc_setup = 0; /* just call zlc_setup() one time */
Mel Gorman54a6eb52008-04-28 02:12:16 -07001376
Mel Gorman19770b32008-04-28 02:12:18 -07001377 (void)first_zones_zonelist(zonelist, high_zoneidx, nodemask,
1378 &preferred_zone);
Andy Whitcroft7eb54822008-05-23 13:04:50 -07001379 if (!preferred_zone)
1380 return NULL;
1381
Mel Gorman19770b32008-04-28 02:12:18 -07001382 classzone_idx = zone_idx(preferred_zone);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001383
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001384zonelist_scan:
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001385 /*
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001386 * Scan zonelist, looking for a zone with enough free.
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001387 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1388 */
Mel Gorman19770b32008-04-28 02:12:18 -07001389 for_each_zone_zonelist_nodemask(zone, z, zonelist,
1390 high_zoneidx, nodemask) {
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001391 if (NUMA_BUILD && zlc_active &&
1392 !zlc_zone_worth_trying(zonelist, z, allowednodes))
1393 continue;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001394 if ((alloc_flags & ALLOC_CPUSET) &&
Paul Jackson02a0e532006-12-13 00:34:25 -08001395 !cpuset_zone_allowed_softwall(zone, gfp_mask))
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001396 goto try_next_zone;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001397
1398 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
Nick Piggin31488902005-11-28 13:44:03 -08001399 unsigned long mark;
1400 if (alloc_flags & ALLOC_WMARK_MIN)
Christoph Lameter1192d522006-09-25 23:31:45 -07001401 mark = zone->pages_min;
Nick Piggin31488902005-11-28 13:44:03 -08001402 else if (alloc_flags & ALLOC_WMARK_LOW)
Christoph Lameter1192d522006-09-25 23:31:45 -07001403 mark = zone->pages_low;
Nick Piggin31488902005-11-28 13:44:03 -08001404 else
Christoph Lameter1192d522006-09-25 23:31:45 -07001405 mark = zone->pages_high;
Paul Jackson0798e512006-12-06 20:31:38 -08001406 if (!zone_watermark_ok(zone, order, mark,
1407 classzone_idx, alloc_flags)) {
Christoph Lameter9eeff232006-01-18 17:42:31 -08001408 if (!zone_reclaim_mode ||
Christoph Lameter1192d522006-09-25 23:31:45 -07001409 !zone_reclaim(zone, gfp_mask, order))
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001410 goto this_zone_full;
Paul Jackson0798e512006-12-06 20:31:38 -08001411 }
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001412 }
1413
Mel Gorman18ea7e72008-04-28 02:12:14 -07001414 page = buffered_rmqueue(preferred_zone, zone, order, gfp_mask);
Paul Jackson0798e512006-12-06 20:31:38 -08001415 if (page)
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001416 break;
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001417this_zone_full:
1418 if (NUMA_BUILD)
1419 zlc_mark_zone_full(zonelist, z);
1420try_next_zone:
1421 if (NUMA_BUILD && !did_zlc_setup) {
1422 /* we do zlc_setup after the first zone is tried */
1423 allowednodes = zlc_setup(zonelist, alloc_flags);
1424 zlc_active = 1;
1425 did_zlc_setup = 1;
1426 }
Mel Gorman54a6eb52008-04-28 02:12:16 -07001427 }
Paul Jackson9276b1bc2006-12-06 20:31:48 -08001428
1429 if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
1430 /* Disable zlc cache for second zonelist scan */
1431 zlc_active = 0;
1432 goto zonelist_scan;
1433 }
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001434 return page;
Martin Hicks753ee722005-06-21 17:14:41 -07001435}
1436
Linus Torvalds1da177e2005-04-16 15:20:36 -07001437/*
1438 * This is the 'heart' of the zoned buddy allocator.
1439 */
KOSAKI Motohiroe4048e52008-07-23 21:27:01 -07001440struct page *
Mel Gorman19770b32008-04-28 02:12:18 -07001441__alloc_pages_internal(gfp_t gfp_mask, unsigned int order,
1442 struct zonelist *zonelist, nodemask_t *nodemask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001443{
Al Viro260b2362005-10-21 03:22:44 -04001444 const gfp_t wait = gfp_mask & __GFP_WAIT;
Mel Gorman54a6eb52008-04-28 02:12:16 -07001445 enum zone_type high_zoneidx = gfp_zone(gfp_mask);
Mel Gormandd1a2392008-04-28 02:12:17 -07001446 struct zoneref *z;
1447 struct zone *zone;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001448 struct page *page;
1449 struct reclaim_state reclaim_state;
1450 struct task_struct *p = current;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001451 int do_retry;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001452 int alloc_flags;
Nishanth Aravamudana41f24e2008-04-29 00:58:25 -07001453 unsigned long did_some_progress;
1454 unsigned long pages_reclaimed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001455
1456 might_sleep_if(wait);
1457
Akinobu Mita933e3122006-12-08 02:39:45 -08001458 if (should_fail_alloc_page(gfp_mask, order))
1459 return NULL;
1460
Jens Axboe6b1de912005-11-17 21:35:02 +01001461restart:
Mel Gormandd1a2392008-04-28 02:12:17 -07001462 z = zonelist->_zonerefs; /* the list of zones suitable for gfp_mask */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001463
Mel Gormandd1a2392008-04-28 02:12:17 -07001464 if (unlikely(!z->zone)) {
Christoph Lameter523b9452007-10-16 01:25:37 -07001465 /*
1466 * Happens if we have an empty zonelist as a result of
1467 * GFP_THISNODE being used on a memoryless node
1468 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001469 return NULL;
1470 }
Jens Axboe6b1de912005-11-17 21:35:02 +01001471
Mel Gorman19770b32008-04-28 02:12:18 -07001472 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
Mel Gorman54a6eb52008-04-28 02:12:16 -07001473 zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001474 if (page)
1475 goto got_pg;
1476
Christoph Lameter952f3b52006-12-06 20:33:26 -08001477 /*
1478 * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
1479 * __GFP_NOWARN set) should not cause reclaim since the subsystem
1480 * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
1481 * using a larger set of nodes after it has established that the
1482 * allowed per node queues are empty and that nodes are
1483 * over allocated.
1484 */
1485 if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
1486 goto nopage;
1487
Mel Gormandd1a2392008-04-28 02:12:17 -07001488 for_each_zone_zonelist(zone, z, zonelist, high_zoneidx)
1489 wakeup_kswapd(zone, order);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001490
Paul Jackson9bf22292005-09-06 15:18:12 -07001491 /*
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001492 * OK, we're below the kswapd watermark and have kicked background
1493 * reclaim. Now things get more complex, so set up alloc_flags according
1494 * to how we want to proceed.
1495 *
1496 * The caller may dip into page reserves a bit more if the caller
1497 * cannot run direct reclaim, or if the caller has realtime scheduling
Paul Jackson4eac9152006-01-11 12:17:19 -08001498 * policy or is asking for __GFP_HIGH memory. GFP_ATOMIC requests will
1499 * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
Paul Jackson9bf22292005-09-06 15:18:12 -07001500 */
Nick Piggin31488902005-11-28 13:44:03 -08001501 alloc_flags = ALLOC_WMARK_MIN;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001502 if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
1503 alloc_flags |= ALLOC_HARDER;
1504 if (gfp_mask & __GFP_HIGH)
1505 alloc_flags |= ALLOC_HIGH;
Paul Jacksonbdd804f2006-05-20 15:00:09 -07001506 if (wait)
1507 alloc_flags |= ALLOC_CPUSET;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001508
1509 /*
1510 * Go through the zonelist again. Let __GFP_HIGH and allocations
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001511 * coming from realtime tasks go deeper into reserves.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001512 *
1513 * This is the last chance, in general, before the goto nopage.
1514 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
Paul Jackson9bf22292005-09-06 15:18:12 -07001515 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001516 */
Mel Gorman19770b32008-04-28 02:12:18 -07001517 page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
Mel Gorman54a6eb52008-04-28 02:12:16 -07001518 high_zoneidx, alloc_flags);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001519 if (page)
1520 goto got_pg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001521
1522 /* This allocation should allow future memory freeing. */
Nick Pigginb84a35b2005-05-01 08:58:36 -07001523
Kirill Korotaevb43a57b2006-12-06 20:32:27 -08001524rebalance:
Nick Pigginb84a35b2005-05-01 08:58:36 -07001525 if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
1526 && !in_interrupt()) {
1527 if (!(gfp_mask & __GFP_NOMEMALLOC)) {
Kirill Korotaev885036d2005-11-13 16:06:41 -08001528nofail_alloc:
Nick Pigginb84a35b2005-05-01 08:58:36 -07001529 /* go through the zonelist yet again, ignoring mins */
Mel Gorman19770b32008-04-28 02:12:18 -07001530 page = get_page_from_freelist(gfp_mask, nodemask, order,
Mel Gorman54a6eb52008-04-28 02:12:16 -07001531 zonelist, high_zoneidx, ALLOC_NO_WATERMARKS);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001532 if (page)
1533 goto got_pg;
Kirill Korotaev885036d2005-11-13 16:06:41 -08001534 if (gfp_mask & __GFP_NOFAIL) {
Andrew Morton3fcfab12006-10-19 23:28:16 -07001535 congestion_wait(WRITE, HZ/50);
Kirill Korotaev885036d2005-11-13 16:06:41 -08001536 goto nofail_alloc;
1537 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001538 }
1539 goto nopage;
1540 }
1541
1542 /* Atomic allocations - we can't balance anything */
1543 if (!wait)
1544 goto nopage;
1545
Linus Torvalds1da177e2005-04-16 15:20:36 -07001546 cond_resched();
1547
1548 /* We now go into synchronous reclaim */
Paul Jackson3e0d98b2006-01-08 01:01:49 -08001549 cpuset_memory_pressure_bump();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001550 p->flags |= PF_MEMALLOC;
1551 reclaim_state.reclaimed_slab = 0;
1552 p->reclaim_state = &reclaim_state;
1553
Mel Gormandac1d272008-04-28 02:12:12 -07001554 did_some_progress = try_to_free_pages(zonelist, order, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001555
1556 p->reclaim_state = NULL;
1557 p->flags &= ~PF_MEMALLOC;
1558
1559 cond_resched();
1560
Mel Gormane2c55dc2007-10-16 01:25:50 -07001561 if (order != 0)
Christoph Lameter9f8f2172008-02-04 22:29:11 -08001562 drain_all_pages();
Mel Gormane2c55dc2007-10-16 01:25:50 -07001563
Linus Torvalds1da177e2005-04-16 15:20:36 -07001564 if (likely(did_some_progress)) {
Mel Gorman19770b32008-04-28 02:12:18 -07001565 page = get_page_from_freelist(gfp_mask, nodemask, order,
Mel Gorman54a6eb52008-04-28 02:12:16 -07001566 zonelist, high_zoneidx, alloc_flags);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001567 if (page)
1568 goto got_pg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001569 } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
Mel Gormandd1a2392008-04-28 02:12:17 -07001570 if (!try_set_zone_oom(zonelist, gfp_mask)) {
David Rientjesff0ceb92007-10-16 23:25:56 -07001571 schedule_timeout_uninterruptible(1);
1572 goto restart;
1573 }
1574
Linus Torvalds1da177e2005-04-16 15:20:36 -07001575 /*
1576 * Go through the zonelist yet one more time, keep
1577 * very high watermark here, this is only to catch
1578 * a parallel oom killing, we must fail if we're still
1579 * under heavy pressure.
1580 */
Mel Gorman19770b32008-04-28 02:12:18 -07001581 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask,
1582 order, zonelist, high_zoneidx,
1583 ALLOC_WMARK_HIGH|ALLOC_CPUSET);
David Rientjesff0ceb92007-10-16 23:25:56 -07001584 if (page) {
Mel Gormandd1a2392008-04-28 02:12:17 -07001585 clear_zonelist_oom(zonelist, gfp_mask);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001586 goto got_pg;
David Rientjesff0ceb92007-10-16 23:25:56 -07001587 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001588
Mel Gormana8bbf722007-07-31 00:37:30 -07001589 /* The OOM killer will not help higher order allocs so fail */
David Rientjesff0ceb92007-10-16 23:25:56 -07001590 if (order > PAGE_ALLOC_COSTLY_ORDER) {
Mel Gormandd1a2392008-04-28 02:12:17 -07001591 clear_zonelist_oom(zonelist, gfp_mask);
Mel Gormana8bbf722007-07-31 00:37:30 -07001592 goto nopage;
David Rientjesff0ceb92007-10-16 23:25:56 -07001593 }
Mel Gormana8bbf722007-07-31 00:37:30 -07001594
Christoph Lameter9b0f8b02006-02-20 18:27:52 -08001595 out_of_memory(zonelist, gfp_mask, order);
Mel Gormandd1a2392008-04-28 02:12:17 -07001596 clear_zonelist_oom(zonelist, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001597 goto restart;
1598 }
1599
1600 /*
1601 * Don't let big-order allocations loop unless the caller explicitly
1602 * requests that. Wait for some write requests to complete then retry.
1603 *
Nishanth Aravamudana41f24e2008-04-29 00:58:25 -07001604 * In this implementation, order <= PAGE_ALLOC_COSTLY_ORDER
1605 * means __GFP_NOFAIL, but that may not be true in other
Nishanth Aravamudanab857d02008-04-29 00:58:23 -07001606 * implementations.
Nishanth Aravamudana41f24e2008-04-29 00:58:25 -07001607 *
1608 * For order > PAGE_ALLOC_COSTLY_ORDER, if __GFP_REPEAT is
1609 * specified, then we retry until we no longer reclaim any pages
1610 * (above), or we've reclaimed an order of pages at least as
1611 * large as the allocation's order. In both cases, if the
1612 * allocation still fails, we stop retrying.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001613 */
Nishanth Aravamudana41f24e2008-04-29 00:58:25 -07001614 pages_reclaimed += did_some_progress;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001615 do_retry = 0;
1616 if (!(gfp_mask & __GFP_NORETRY)) {
Nishanth Aravamudana41f24e2008-04-29 00:58:25 -07001617 if (order <= PAGE_ALLOC_COSTLY_ORDER) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001618 do_retry = 1;
Nishanth Aravamudana41f24e2008-04-29 00:58:25 -07001619 } else {
1620 if (gfp_mask & __GFP_REPEAT &&
1621 pages_reclaimed < (1 << order))
1622 do_retry = 1;
1623 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001624 if (gfp_mask & __GFP_NOFAIL)
1625 do_retry = 1;
1626 }
1627 if (do_retry) {
Andrew Morton3fcfab12006-10-19 23:28:16 -07001628 congestion_wait(WRITE, HZ/50);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001629 goto rebalance;
1630 }
1631
1632nopage:
1633 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
1634 printk(KERN_WARNING "%s: page allocation failure."
1635 " order:%d, mode:0x%x\n",
1636 p->comm, order, gfp_mask);
1637 dump_stack();
Janet Morgan578c2fd2005-06-21 17:14:56 -07001638 show_mem();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001639 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001640got_pg:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001641 return page;
1642}
KOSAKI Motohiroe4048e52008-07-23 21:27:01 -07001643EXPORT_SYMBOL(__alloc_pages_internal);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001644
1645/*
1646 * Common helper functions.
1647 */
Harvey Harrison920c7a52008-02-04 22:29:26 -08001648unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001649{
1650 struct page * page;
1651 page = alloc_pages(gfp_mask, order);
1652 if (!page)
1653 return 0;
1654 return (unsigned long) page_address(page);
1655}
1656
1657EXPORT_SYMBOL(__get_free_pages);
1658
Harvey Harrison920c7a52008-02-04 22:29:26 -08001659unsigned long get_zeroed_page(gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001660{
1661 struct page * page;
1662
1663 /*
1664 * get_zeroed_page() returns a 32-bit address, which cannot represent
1665 * a highmem page
1666 */
Nick Piggin725d7042006-09-25 23:30:55 -07001667 VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001668
1669 page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
1670 if (page)
1671 return (unsigned long) page_address(page);
1672 return 0;
1673}
1674
1675EXPORT_SYMBOL(get_zeroed_page);
1676
1677void __pagevec_free(struct pagevec *pvec)
1678{
1679 int i = pagevec_count(pvec);
1680
1681 while (--i >= 0)
1682 free_hot_cold_page(pvec->pages[i], pvec->cold);
1683}
1684
Harvey Harrison920c7a52008-02-04 22:29:26 -08001685void __free_pages(struct page *page, unsigned int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001686{
Nick Pigginb5810032005-10-29 18:16:12 -07001687 if (put_page_testzero(page)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001688 if (order == 0)
1689 free_hot_page(page);
1690 else
1691 __free_pages_ok(page, order);
1692 }
1693}
1694
1695EXPORT_SYMBOL(__free_pages);
1696
Harvey Harrison920c7a52008-02-04 22:29:26 -08001697void free_pages(unsigned long addr, unsigned int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001698{
1699 if (addr != 0) {
Nick Piggin725d7042006-09-25 23:30:55 -07001700 VM_BUG_ON(!virt_addr_valid((void *)addr));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001701 __free_pages(virt_to_page((void *)addr), order);
1702 }
1703}
1704
1705EXPORT_SYMBOL(free_pages);
1706
Timur Tabi2be0ffe2008-07-23 21:28:11 -07001707/**
1708 * alloc_pages_exact - allocate an exact number physically-contiguous pages.
1709 * @size: the number of bytes to allocate
1710 * @gfp_mask: GFP flags for the allocation
1711 *
1712 * This function is similar to alloc_pages(), except that it allocates the
1713 * minimum number of pages to satisfy the request. alloc_pages() can only
1714 * allocate memory in power-of-two pages.
1715 *
1716 * This function is also limited by MAX_ORDER.
1717 *
1718 * Memory allocated by this function must be released by free_pages_exact().
1719 */
1720void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
1721{
1722 unsigned int order = get_order(size);
1723 unsigned long addr;
1724
1725 addr = __get_free_pages(gfp_mask, order);
1726 if (addr) {
1727 unsigned long alloc_end = addr + (PAGE_SIZE << order);
1728 unsigned long used = addr + PAGE_ALIGN(size);
1729
1730 split_page(virt_to_page(addr), order);
1731 while (used < alloc_end) {
1732 free_page(used);
1733 used += PAGE_SIZE;
1734 }
1735 }
1736
1737 return (void *)addr;
1738}
1739EXPORT_SYMBOL(alloc_pages_exact);
1740
1741/**
1742 * free_pages_exact - release memory allocated via alloc_pages_exact()
1743 * @virt: the value returned by alloc_pages_exact.
1744 * @size: size of allocation, same value as passed to alloc_pages_exact().
1745 *
1746 * Release the memory allocated by a previous call to alloc_pages_exact.
1747 */
1748void free_pages_exact(void *virt, size_t size)
1749{
1750 unsigned long addr = (unsigned long)virt;
1751 unsigned long end = addr + PAGE_ALIGN(size);
1752
1753 while (addr < end) {
1754 free_page(addr);
1755 addr += PAGE_SIZE;
1756 }
1757}
1758EXPORT_SYMBOL(free_pages_exact);
1759
Linus Torvalds1da177e2005-04-16 15:20:36 -07001760static unsigned int nr_free_zone_pages(int offset)
1761{
Mel Gormandd1a2392008-04-28 02:12:17 -07001762 struct zoneref *z;
Mel Gorman54a6eb52008-04-28 02:12:16 -07001763 struct zone *zone;
1764
Martin J. Blighe310fd42005-07-29 22:59:18 -07001765 /* Just pick one node, since fallback list is circular */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001766 unsigned int sum = 0;
1767
Mel Gorman0e884602008-04-28 02:12:14 -07001768 struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001769
Mel Gorman54a6eb52008-04-28 02:12:16 -07001770 for_each_zone_zonelist(zone, z, zonelist, offset) {
Martin J. Blighe310fd42005-07-29 22:59:18 -07001771 unsigned long size = zone->present_pages;
1772 unsigned long high = zone->pages_high;
1773 if (size > high)
1774 sum += size - high;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001775 }
1776
1777 return sum;
1778}
1779
1780/*
1781 * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
1782 */
1783unsigned int nr_free_buffer_pages(void)
1784{
Al Viroaf4ca452005-10-21 02:55:38 -04001785 return nr_free_zone_pages(gfp_zone(GFP_USER));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001786}
Meelap Shahc2f1a552007-07-17 04:04:39 -07001787EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001788
1789/*
1790 * Amount of free RAM allocatable within all zones
1791 */
1792unsigned int nr_free_pagecache_pages(void)
1793{
Mel Gorman2a1e2742007-07-17 04:03:12 -07001794 return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001795}
Christoph Lameter08e0f6a2006-09-27 01:50:06 -07001796
1797static inline void show_node(struct zone *zone)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001798{
Christoph Lameter08e0f6a2006-09-27 01:50:06 -07001799 if (NUMA_BUILD)
Andy Whitcroft25ba77c2006-12-06 20:33:03 -08001800 printk("Node %d ", zone_to_nid(zone));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001801}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001802
Linus Torvalds1da177e2005-04-16 15:20:36 -07001803void si_meminfo(struct sysinfo *val)
1804{
1805 val->totalram = totalram_pages;
1806 val->sharedram = 0;
Christoph Lameterd23ad422007-02-10 01:43:02 -08001807 val->freeram = global_page_state(NR_FREE_PAGES);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001808 val->bufferram = nr_blockdev_pages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001809 val->totalhigh = totalhigh_pages;
1810 val->freehigh = nr_free_highpages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001811 val->mem_unit = PAGE_SIZE;
1812}
1813
1814EXPORT_SYMBOL(si_meminfo);
1815
1816#ifdef CONFIG_NUMA
1817void si_meminfo_node(struct sysinfo *val, int nid)
1818{
1819 pg_data_t *pgdat = NODE_DATA(nid);
1820
1821 val->totalram = pgdat->node_present_pages;
Christoph Lameterd23ad422007-02-10 01:43:02 -08001822 val->freeram = node_page_state(nid, NR_FREE_PAGES);
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07001823#ifdef CONFIG_HIGHMEM
Linus Torvalds1da177e2005-04-16 15:20:36 -07001824 val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
Christoph Lameterd23ad422007-02-10 01:43:02 -08001825 val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
1826 NR_FREE_PAGES);
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07001827#else
1828 val->totalhigh = 0;
1829 val->freehigh = 0;
1830#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001831 val->mem_unit = PAGE_SIZE;
1832}
1833#endif
1834
1835#define K(x) ((x) << (PAGE_SHIFT-10))
1836
1837/*
1838 * Show free area list (used inside shift_scroll-lock stuff)
1839 * We also calculate the percentage fragmentation. We do this by counting the
1840 * memory on each free list with the exception of the first item on the list.
1841 */
1842void show_free_areas(void)
1843{
Jes Sorensenc7241912006-09-27 01:50:05 -07001844 int cpu;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001845 struct zone *zone;
1846
1847 for_each_zone(zone) {
Jes Sorensenc7241912006-09-27 01:50:05 -07001848 if (!populated_zone(zone))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001849 continue;
Jes Sorensenc7241912006-09-27 01:50:05 -07001850
1851 show_node(zone);
1852 printk("%s per-cpu:\n", zone->name);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001853
Dave Jones6b482c62005-11-10 15:45:56 -05001854 for_each_online_cpu(cpu) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001855 struct per_cpu_pageset *pageset;
1856
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001857 pageset = zone_pcp(zone, cpu);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001858
Christoph Lameter3dfa5722008-02-04 22:29:19 -08001859 printk("CPU %4d: hi:%5d, btch:%4d usd:%4d\n",
1860 cpu, pageset->pcp.high,
1861 pageset->pcp.batch, pageset->pcp.count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001862 }
1863 }
1864
Lee Schermerhorn7b854122008-10-18 20:26:40 -07001865 printk("Active_anon:%lu active_file:%lu inactive_anon:%lu\n"
1866 " inactive_file:%lu"
1867//TODO: check/adjust line lengths
1868#ifdef CONFIG_UNEVICTABLE_LRU
1869 " unevictable:%lu"
1870#endif
1871 " dirty:%lu writeback:%lu unstable:%lu\n"
Christoph Lameterd23ad422007-02-10 01:43:02 -08001872 " free:%lu slab:%lu mapped:%lu pagetables:%lu bounce:%lu\n",
Rik van Riel4f98a2f2008-10-18 20:26:32 -07001873 global_page_state(NR_ACTIVE_ANON),
1874 global_page_state(NR_ACTIVE_FILE),
1875 global_page_state(NR_INACTIVE_ANON),
1876 global_page_state(NR_INACTIVE_FILE),
Lee Schermerhorn7b854122008-10-18 20:26:40 -07001877#ifdef CONFIG_UNEVICTABLE_LRU
1878 global_page_state(NR_UNEVICTABLE),
1879#endif
Christoph Lameterb1e7a8f2006-06-30 01:55:39 -07001880 global_page_state(NR_FILE_DIRTY),
Christoph Lameterce866b32006-06-30 01:55:40 -07001881 global_page_state(NR_WRITEBACK),
Christoph Lameterfd39fc82006-06-30 01:55:40 -07001882 global_page_state(NR_UNSTABLE_NFS),
Christoph Lameterd23ad422007-02-10 01:43:02 -08001883 global_page_state(NR_FREE_PAGES),
Christoph Lameter972d1a72006-09-25 23:31:51 -07001884 global_page_state(NR_SLAB_RECLAIMABLE) +
1885 global_page_state(NR_SLAB_UNRECLAIMABLE),
Christoph Lameter65ba55f2006-06-30 01:55:34 -07001886 global_page_state(NR_FILE_MAPPED),
Andrew Mortona25700a2007-02-08 14:20:40 -08001887 global_page_state(NR_PAGETABLE),
1888 global_page_state(NR_BOUNCE));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001889
1890 for_each_zone(zone) {
1891 int i;
1892
Jes Sorensenc7241912006-09-27 01:50:05 -07001893 if (!populated_zone(zone))
1894 continue;
1895
Linus Torvalds1da177e2005-04-16 15:20:36 -07001896 show_node(zone);
1897 printk("%s"
1898 " free:%lukB"
1899 " min:%lukB"
1900 " low:%lukB"
1901 " high:%lukB"
Rik van Riel4f98a2f2008-10-18 20:26:32 -07001902 " active_anon:%lukB"
1903 " inactive_anon:%lukB"
1904 " active_file:%lukB"
1905 " inactive_file:%lukB"
Lee Schermerhorn7b854122008-10-18 20:26:40 -07001906#ifdef CONFIG_UNEVICTABLE_LRU
1907 " unevictable:%lukB"
1908#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001909 " present:%lukB"
1910 " pages_scanned:%lu"
1911 " all_unreclaimable? %s"
1912 "\n",
1913 zone->name,
Christoph Lameterd23ad422007-02-10 01:43:02 -08001914 K(zone_page_state(zone, NR_FREE_PAGES)),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001915 K(zone->pages_min),
1916 K(zone->pages_low),
1917 K(zone->pages_high),
Rik van Riel4f98a2f2008-10-18 20:26:32 -07001918 K(zone_page_state(zone, NR_ACTIVE_ANON)),
1919 K(zone_page_state(zone, NR_INACTIVE_ANON)),
1920 K(zone_page_state(zone, NR_ACTIVE_FILE)),
1921 K(zone_page_state(zone, NR_INACTIVE_FILE)),
Lee Schermerhorn7b854122008-10-18 20:26:40 -07001922#ifdef CONFIG_UNEVICTABLE_LRU
1923 K(zone_page_state(zone, NR_UNEVICTABLE)),
1924#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001925 K(zone->present_pages),
1926 zone->pages_scanned,
David Rientjese815af92007-10-16 23:25:54 -07001927 (zone_is_all_unreclaimable(zone) ? "yes" : "no")
Linus Torvalds1da177e2005-04-16 15:20:36 -07001928 );
1929 printk("lowmem_reserve[]:");
1930 for (i = 0; i < MAX_NR_ZONES; i++)
1931 printk(" %lu", zone->lowmem_reserve[i]);
1932 printk("\n");
1933 }
1934
1935 for_each_zone(zone) {
Kirill Korotaev8f9de512006-06-23 02:03:50 -07001936 unsigned long nr[MAX_ORDER], flags, order, total = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001937
Jes Sorensenc7241912006-09-27 01:50:05 -07001938 if (!populated_zone(zone))
1939 continue;
1940
Linus Torvalds1da177e2005-04-16 15:20:36 -07001941 show_node(zone);
1942 printk("%s: ", zone->name);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001943
1944 spin_lock_irqsave(&zone->lock, flags);
1945 for (order = 0; order < MAX_ORDER; order++) {
Kirill Korotaev8f9de512006-06-23 02:03:50 -07001946 nr[order] = zone->free_area[order].nr_free;
1947 total += nr[order] << order;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001948 }
1949 spin_unlock_irqrestore(&zone->lock, flags);
Kirill Korotaev8f9de512006-06-23 02:03:50 -07001950 for (order = 0; order < MAX_ORDER; order++)
1951 printk("%lu*%lukB ", nr[order], K(1UL) << order);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001952 printk("= %lukB\n", K(total));
1953 }
1954
Larry Woodmane6f36022008-02-04 22:29:30 -08001955 printk("%ld total pagecache pages\n", global_page_state(NR_FILE_PAGES));
1956
Linus Torvalds1da177e2005-04-16 15:20:36 -07001957 show_swap_cache_info();
1958}
1959
Mel Gorman19770b32008-04-28 02:12:18 -07001960static void zoneref_set_zone(struct zone *zone, struct zoneref *zoneref)
1961{
1962 zoneref->zone = zone;
1963 zoneref->zone_idx = zone_idx(zone);
1964}
1965
Linus Torvalds1da177e2005-04-16 15:20:36 -07001966/*
1967 * Builds allocation fallback zone lists.
Christoph Lameter1a932052006-01-06 00:11:16 -08001968 *
1969 * Add all populated zones of a node to the zonelist.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001970 */
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07001971static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
1972 int nr_zones, enum zone_type zone_type)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001973{
Christoph Lameter1a932052006-01-06 00:11:16 -08001974 struct zone *zone;
1975
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07001976 BUG_ON(zone_type >= MAX_NR_ZONES);
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001977 zone_type++;
Christoph Lameter02a68a52006-01-06 00:11:18 -08001978
1979 do {
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001980 zone_type--;
Christoph Lameter070f8032006-01-06 00:11:19 -08001981 zone = pgdat->node_zones + zone_type;
Christoph Lameter1a932052006-01-06 00:11:16 -08001982 if (populated_zone(zone)) {
Mel Gormandd1a2392008-04-28 02:12:17 -07001983 zoneref_set_zone(zone,
1984 &zonelist->_zonerefs[nr_zones++]);
Christoph Lameter070f8032006-01-06 00:11:19 -08001985 check_highest_zone(zone_type);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001986 }
Christoph Lameter02a68a52006-01-06 00:11:18 -08001987
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001988 } while (zone_type);
Christoph Lameter070f8032006-01-06 00:11:19 -08001989 return nr_zones;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001990}
1991
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07001992
1993/*
1994 * zonelist_order:
1995 * 0 = automatic detection of better ordering.
1996 * 1 = order by ([node] distance, -zonetype)
1997 * 2 = order by (-zonetype, [node] distance)
1998 *
1999 * If not NUMA, ZONELIST_ORDER_ZONE and ZONELIST_ORDER_NODE will create
2000 * the same zonelist. So only NUMA can configure this param.
2001 */
2002#define ZONELIST_ORDER_DEFAULT 0
2003#define ZONELIST_ORDER_NODE 1
2004#define ZONELIST_ORDER_ZONE 2
2005
2006/* zonelist order in the kernel.
2007 * set_zonelist_order() will set this to NODE or ZONE.
2008 */
2009static int current_zonelist_order = ZONELIST_ORDER_DEFAULT;
2010static char zonelist_order_name[3][8] = {"Default", "Node", "Zone"};
2011
2012
Linus Torvalds1da177e2005-04-16 15:20:36 -07002013#ifdef CONFIG_NUMA
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002014/* The value user specified ....changed by config */
2015static int user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2016/* string for sysctl */
2017#define NUMA_ZONELIST_ORDER_LEN 16
2018char numa_zonelist_order[16] = "default";
2019
2020/*
2021 * interface for configure zonelist ordering.
2022 * command line option "numa_zonelist_order"
2023 * = "[dD]efault - default, automatic configuration.
2024 * = "[nN]ode - order by node locality, then by zone within node
2025 * = "[zZ]one - order by zone, then by locality within zone
2026 */
2027
2028static int __parse_numa_zonelist_order(char *s)
2029{
2030 if (*s == 'd' || *s == 'D') {
2031 user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2032 } else if (*s == 'n' || *s == 'N') {
2033 user_zonelist_order = ZONELIST_ORDER_NODE;
2034 } else if (*s == 'z' || *s == 'Z') {
2035 user_zonelist_order = ZONELIST_ORDER_ZONE;
2036 } else {
2037 printk(KERN_WARNING
2038 "Ignoring invalid numa_zonelist_order value: "
2039 "%s\n", s);
2040 return -EINVAL;
2041 }
2042 return 0;
2043}
2044
2045static __init int setup_numa_zonelist_order(char *s)
2046{
2047 if (s)
2048 return __parse_numa_zonelist_order(s);
2049 return 0;
2050}
2051early_param("numa_zonelist_order", setup_numa_zonelist_order);
2052
2053/*
2054 * sysctl handler for numa_zonelist_order
2055 */
2056int numa_zonelist_order_handler(ctl_table *table, int write,
2057 struct file *file, void __user *buffer, size_t *length,
2058 loff_t *ppos)
2059{
2060 char saved_string[NUMA_ZONELIST_ORDER_LEN];
2061 int ret;
2062
2063 if (write)
2064 strncpy(saved_string, (char*)table->data,
2065 NUMA_ZONELIST_ORDER_LEN);
2066 ret = proc_dostring(table, write, file, buffer, length, ppos);
2067 if (ret)
2068 return ret;
2069 if (write) {
2070 int oldval = user_zonelist_order;
2071 if (__parse_numa_zonelist_order((char*)table->data)) {
2072 /*
2073 * bogus value. restore saved string
2074 */
2075 strncpy((char*)table->data, saved_string,
2076 NUMA_ZONELIST_ORDER_LEN);
2077 user_zonelist_order = oldval;
2078 } else if (oldval != user_zonelist_order)
2079 build_all_zonelists();
2080 }
2081 return 0;
2082}
2083
2084
Linus Torvalds1da177e2005-04-16 15:20:36 -07002085#define MAX_NODE_LOAD (num_online_nodes())
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002086static int node_load[MAX_NUMNODES];
2087
Linus Torvalds1da177e2005-04-16 15:20:36 -07002088/**
Pavel Pisa4dc3b162005-05-01 08:59:25 -07002089 * find_next_best_node - find the next node that should appear in a given node's fallback list
Linus Torvalds1da177e2005-04-16 15:20:36 -07002090 * @node: node whose fallback list we're appending
2091 * @used_node_mask: nodemask_t of already used nodes
2092 *
2093 * We use a number of factors to determine which is the next node that should
2094 * appear on a given node's fallback list. The node should not have appeared
2095 * already in @node's fallback list, and it should be the next closest node
2096 * according to the distance array (which contains arbitrary distance values
2097 * from each node to each node in the system), and should also prefer nodes
2098 * with no CPUs, since presumably they'll have very little allocation pressure
2099 * on them otherwise.
2100 * It returns -1 if no node is found.
2101 */
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002102static int find_next_best_node(int node, nodemask_t *used_node_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002103{
Linus Torvalds4cf808e2006-02-17 20:38:21 +01002104 int n, val;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002105 int min_val = INT_MAX;
2106 int best_node = -1;
Mike Travisc5f59f02008-04-04 18:11:10 -07002107 node_to_cpumask_ptr(tmp, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002108
Linus Torvalds4cf808e2006-02-17 20:38:21 +01002109 /* Use the local node if we haven't already */
2110 if (!node_isset(node, *used_node_mask)) {
2111 node_set(node, *used_node_mask);
2112 return node;
2113 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002114
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07002115 for_each_node_state(n, N_HIGH_MEMORY) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002116
2117 /* Don't want a node to appear more than once */
2118 if (node_isset(n, *used_node_mask))
2119 continue;
2120
Linus Torvalds1da177e2005-04-16 15:20:36 -07002121 /* Use the distance array to find the distance */
2122 val = node_distance(node, n);
2123
Linus Torvalds4cf808e2006-02-17 20:38:21 +01002124 /* Penalize nodes under us ("prefer the next node") */
2125 val += (n < node);
2126
Linus Torvalds1da177e2005-04-16 15:20:36 -07002127 /* Give preference to headless and unused nodes */
Mike Travisc5f59f02008-04-04 18:11:10 -07002128 node_to_cpumask_ptr_next(tmp, n);
2129 if (!cpus_empty(*tmp))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002130 val += PENALTY_FOR_NODE_WITH_CPUS;
2131
2132 /* Slight preference for less loaded node */
2133 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
2134 val += node_load[n];
2135
2136 if (val < min_val) {
2137 min_val = val;
2138 best_node = n;
2139 }
2140 }
2141
2142 if (best_node >= 0)
2143 node_set(best_node, *used_node_mask);
2144
2145 return best_node;
2146}
2147
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002148
2149/*
2150 * Build zonelists ordered by node and zones within node.
2151 * This results in maximum locality--normal zone overflows into local
2152 * DMA zone, if any--but risks exhausting DMA zone.
2153 */
2154static void build_zonelists_in_node_order(pg_data_t *pgdat, int node)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002155{
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002156 int j;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002157 struct zonelist *zonelist;
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002158
Mel Gorman54a6eb52008-04-28 02:12:16 -07002159 zonelist = &pgdat->node_zonelists[0];
Mel Gormandd1a2392008-04-28 02:12:17 -07002160 for (j = 0; zonelist->_zonerefs[j].zone != NULL; j++)
Mel Gorman54a6eb52008-04-28 02:12:16 -07002161 ;
2162 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2163 MAX_NR_ZONES - 1);
Mel Gormandd1a2392008-04-28 02:12:17 -07002164 zonelist->_zonerefs[j].zone = NULL;
2165 zonelist->_zonerefs[j].zone_idx = 0;
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002166}
2167
2168/*
Christoph Lameter523b9452007-10-16 01:25:37 -07002169 * Build gfp_thisnode zonelists
2170 */
2171static void build_thisnode_zonelists(pg_data_t *pgdat)
2172{
Christoph Lameter523b9452007-10-16 01:25:37 -07002173 int j;
2174 struct zonelist *zonelist;
2175
Mel Gorman54a6eb52008-04-28 02:12:16 -07002176 zonelist = &pgdat->node_zonelists[1];
2177 j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
Mel Gormandd1a2392008-04-28 02:12:17 -07002178 zonelist->_zonerefs[j].zone = NULL;
2179 zonelist->_zonerefs[j].zone_idx = 0;
Christoph Lameter523b9452007-10-16 01:25:37 -07002180}
2181
2182/*
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002183 * Build zonelists ordered by zone and nodes within zones.
2184 * This results in conserving DMA zone[s] until all Normal memory is
2185 * exhausted, but results in overflowing to remote node while memory
2186 * may still exist in local DMA zone.
2187 */
2188static int node_order[MAX_NUMNODES];
2189
2190static void build_zonelists_in_zone_order(pg_data_t *pgdat, int nr_nodes)
2191{
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002192 int pos, j, node;
2193 int zone_type; /* needs to be signed */
2194 struct zone *z;
2195 struct zonelist *zonelist;
2196
Mel Gorman54a6eb52008-04-28 02:12:16 -07002197 zonelist = &pgdat->node_zonelists[0];
2198 pos = 0;
2199 for (zone_type = MAX_NR_ZONES - 1; zone_type >= 0; zone_type--) {
2200 for (j = 0; j < nr_nodes; j++) {
2201 node = node_order[j];
2202 z = &NODE_DATA(node)->node_zones[zone_type];
2203 if (populated_zone(z)) {
Mel Gormandd1a2392008-04-28 02:12:17 -07002204 zoneref_set_zone(z,
2205 &zonelist->_zonerefs[pos++]);
Mel Gorman54a6eb52008-04-28 02:12:16 -07002206 check_highest_zone(zone_type);
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002207 }
2208 }
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002209 }
Mel Gormandd1a2392008-04-28 02:12:17 -07002210 zonelist->_zonerefs[pos].zone = NULL;
2211 zonelist->_zonerefs[pos].zone_idx = 0;
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002212}
2213
2214static int default_zonelist_order(void)
2215{
2216 int nid, zone_type;
2217 unsigned long low_kmem_size,total_size;
2218 struct zone *z;
2219 int average_size;
2220 /*
2221 * ZONE_DMA and ZONE_DMA32 can be very small area in the sytem.
2222 * If they are really small and used heavily, the system can fall
2223 * into OOM very easily.
2224 * This function detect ZONE_DMA/DMA32 size and confgigures zone order.
2225 */
2226 /* Is there ZONE_NORMAL ? (ex. ppc has only DMA zone..) */
2227 low_kmem_size = 0;
2228 total_size = 0;
2229 for_each_online_node(nid) {
2230 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
2231 z = &NODE_DATA(nid)->node_zones[zone_type];
2232 if (populated_zone(z)) {
2233 if (zone_type < ZONE_NORMAL)
2234 low_kmem_size += z->present_pages;
2235 total_size += z->present_pages;
2236 }
2237 }
2238 }
2239 if (!low_kmem_size || /* there are no DMA area. */
2240 low_kmem_size > total_size/2) /* DMA/DMA32 is big. */
2241 return ZONELIST_ORDER_NODE;
2242 /*
2243 * look into each node's config.
2244 * If there is a node whose DMA/DMA32 memory is very big area on
2245 * local memory, NODE_ORDER may be suitable.
2246 */
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07002247 average_size = total_size /
2248 (nodes_weight(node_states[N_HIGH_MEMORY]) + 1);
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002249 for_each_online_node(nid) {
2250 low_kmem_size = 0;
2251 total_size = 0;
2252 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
2253 z = &NODE_DATA(nid)->node_zones[zone_type];
2254 if (populated_zone(z)) {
2255 if (zone_type < ZONE_NORMAL)
2256 low_kmem_size += z->present_pages;
2257 total_size += z->present_pages;
2258 }
2259 }
2260 if (low_kmem_size &&
2261 total_size > average_size && /* ignore small node */
2262 low_kmem_size > total_size * 70/100)
2263 return ZONELIST_ORDER_NODE;
2264 }
2265 return ZONELIST_ORDER_ZONE;
2266}
2267
2268static void set_zonelist_order(void)
2269{
2270 if (user_zonelist_order == ZONELIST_ORDER_DEFAULT)
2271 current_zonelist_order = default_zonelist_order();
2272 else
2273 current_zonelist_order = user_zonelist_order;
2274}
2275
2276static void build_zonelists(pg_data_t *pgdat)
2277{
2278 int j, node, load;
2279 enum zone_type i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002280 nodemask_t used_mask;
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002281 int local_node, prev_node;
2282 struct zonelist *zonelist;
2283 int order = current_zonelist_order;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002284
2285 /* initialize zonelists */
Christoph Lameter523b9452007-10-16 01:25:37 -07002286 for (i = 0; i < MAX_ZONELISTS; i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002287 zonelist = pgdat->node_zonelists + i;
Mel Gormandd1a2392008-04-28 02:12:17 -07002288 zonelist->_zonerefs[0].zone = NULL;
2289 zonelist->_zonerefs[0].zone_idx = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002290 }
2291
2292 /* NUMA-aware ordering of nodes */
2293 local_node = pgdat->node_id;
2294 load = num_online_nodes();
2295 prev_node = local_node;
2296 nodes_clear(used_mask);
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002297
2298 memset(node_load, 0, sizeof(node_load));
2299 memset(node_order, 0, sizeof(node_order));
2300 j = 0;
2301
Linus Torvalds1da177e2005-04-16 15:20:36 -07002302 while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
Christoph Lameter9eeff232006-01-18 17:42:31 -08002303 int distance = node_distance(local_node, node);
2304
2305 /*
2306 * If another node is sufficiently far away then it is better
2307 * to reclaim pages in a zone before going off node.
2308 */
2309 if (distance > RECLAIM_DISTANCE)
2310 zone_reclaim_mode = 1;
2311
Linus Torvalds1da177e2005-04-16 15:20:36 -07002312 /*
2313 * We don't want to pressure a particular node.
2314 * So adding penalty to the first node in same
2315 * distance group to make it round-robin.
2316 */
Christoph Lameter9eeff232006-01-18 17:42:31 -08002317 if (distance != node_distance(local_node, prev_node))
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002318 node_load[node] = load;
2319
Linus Torvalds1da177e2005-04-16 15:20:36 -07002320 prev_node = node;
2321 load--;
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002322 if (order == ZONELIST_ORDER_NODE)
2323 build_zonelists_in_node_order(pgdat, node);
2324 else
2325 node_order[j++] = node; /* remember order */
2326 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002327
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002328 if (order == ZONELIST_ORDER_ZONE) {
2329 /* calculate node order -- i.e., DMA last! */
2330 build_zonelists_in_zone_order(pgdat, j);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002331 }
Christoph Lameter523b9452007-10-16 01:25:37 -07002332
2333 build_thisnode_zonelists(pgdat);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002334}
2335
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002336/* Construct the zonelist performance cache - see further mmzone.h */
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002337static void build_zonelist_cache(pg_data_t *pgdat)
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002338{
Mel Gorman54a6eb52008-04-28 02:12:16 -07002339 struct zonelist *zonelist;
2340 struct zonelist_cache *zlc;
Mel Gormandd1a2392008-04-28 02:12:17 -07002341 struct zoneref *z;
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002342
Mel Gorman54a6eb52008-04-28 02:12:16 -07002343 zonelist = &pgdat->node_zonelists[0];
2344 zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
2345 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
Mel Gormandd1a2392008-04-28 02:12:17 -07002346 for (z = zonelist->_zonerefs; z->zone; z++)
2347 zlc->z_to_n[z - zonelist->_zonerefs] = zonelist_node_idx(z);
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002348}
2349
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002350
Linus Torvalds1da177e2005-04-16 15:20:36 -07002351#else /* CONFIG_NUMA */
2352
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002353static void set_zonelist_order(void)
2354{
2355 current_zonelist_order = ZONELIST_ORDER_ZONE;
2356}
2357
2358static void build_zonelists(pg_data_t *pgdat)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002359{
Christoph Lameter19655d32006-09-25 23:31:19 -07002360 int node, local_node;
Mel Gorman54a6eb52008-04-28 02:12:16 -07002361 enum zone_type j;
2362 struct zonelist *zonelist;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002363
2364 local_node = pgdat->node_id;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002365
Mel Gorman54a6eb52008-04-28 02:12:16 -07002366 zonelist = &pgdat->node_zonelists[0];
2367 j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002368
Mel Gorman54a6eb52008-04-28 02:12:16 -07002369 /*
2370 * Now we build the zonelist so that it contains the zones
2371 * of all the other nodes.
2372 * We don't want to pressure a particular node, so when
2373 * building the zones for node N, we make sure that the
2374 * zones coming right after the local ones are those from
2375 * node N+1 (modulo N)
2376 */
2377 for (node = local_node + 1; node < MAX_NUMNODES; node++) {
2378 if (!node_online(node))
2379 continue;
2380 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2381 MAX_NR_ZONES - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002382 }
Mel Gorman54a6eb52008-04-28 02:12:16 -07002383 for (node = 0; node < local_node; node++) {
2384 if (!node_online(node))
2385 continue;
2386 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2387 MAX_NR_ZONES - 1);
2388 }
2389
Mel Gormandd1a2392008-04-28 02:12:17 -07002390 zonelist->_zonerefs[j].zone = NULL;
2391 zonelist->_zonerefs[j].zone_idx = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002392}
2393
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002394/* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002395static void build_zonelist_cache(pg_data_t *pgdat)
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002396{
Mel Gorman54a6eb52008-04-28 02:12:16 -07002397 pgdat->node_zonelists[0].zlcache_ptr = NULL;
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002398}
2399
Linus Torvalds1da177e2005-04-16 15:20:36 -07002400#endif /* CONFIG_NUMA */
2401
Rusty Russell9b1a4d32008-07-28 12:16:30 -05002402/* return values int ....just for stop_machine() */
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002403static int __build_all_zonelists(void *dummy)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002404{
Yasunori Goto68113782006-06-23 02:03:11 -07002405 int nid;
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002406
2407 for_each_online_node(nid) {
Christoph Lameter7ea15302007-10-16 01:25:29 -07002408 pg_data_t *pgdat = NODE_DATA(nid);
2409
2410 build_zonelists(pgdat);
2411 build_zonelist_cache(pgdat);
Paul Jackson9276b1bc2006-12-06 20:31:48 -08002412 }
Yasunori Goto68113782006-06-23 02:03:11 -07002413 return 0;
2414}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002415
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002416void build_all_zonelists(void)
Yasunori Goto68113782006-06-23 02:03:11 -07002417{
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002418 set_zonelist_order();
2419
Yasunori Goto68113782006-06-23 02:03:11 -07002420 if (system_state == SYSTEM_BOOTING) {
Randy Dunlap423b41d2006-09-27 01:50:12 -07002421 __build_all_zonelists(NULL);
Mel Gorman68ad8df2008-07-23 21:26:52 -07002422 mminit_verify_zonelist();
Yasunori Goto68113782006-06-23 02:03:11 -07002423 cpuset_init_current_mems_allowed();
2424 } else {
Simon Arlott183ff222007-10-20 01:27:18 +02002425 /* we have to stop all cpus to guarantee there is no user
Yasunori Goto68113782006-06-23 02:03:11 -07002426 of zonelist */
Rusty Russell9b1a4d32008-07-28 12:16:30 -05002427 stop_machine(__build_all_zonelists, NULL, NULL);
Yasunori Goto68113782006-06-23 02:03:11 -07002428 /* cpuset refresh routine should be here */
2429 }
Andrew Mortonbd1e22b2006-06-23 02:03:47 -07002430 vm_total_pages = nr_free_pagecache_pages();
Mel Gorman9ef9acb2007-10-16 01:25:54 -07002431 /*
2432 * Disable grouping by mobility if the number of pages in the
2433 * system is too low to allow the mechanism to work. It would be
2434 * more accurate, but expensive to check per-zone. This check is
2435 * made on memory-hotadd so a system can start with mobility
2436 * disabled and enable it later
2437 */
Mel Gormand9c23402007-10-16 01:26:01 -07002438 if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
Mel Gorman9ef9acb2007-10-16 01:25:54 -07002439 page_group_by_mobility_disabled = 1;
2440 else
2441 page_group_by_mobility_disabled = 0;
2442
2443 printk("Built %i zonelists in %s order, mobility grouping %s. "
2444 "Total pages: %ld\n",
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002445 num_online_nodes(),
2446 zonelist_order_name[current_zonelist_order],
Mel Gorman9ef9acb2007-10-16 01:25:54 -07002447 page_group_by_mobility_disabled ? "off" : "on",
KAMEZAWA Hiroyukif0c0b2b2007-07-15 23:38:01 -07002448 vm_total_pages);
2449#ifdef CONFIG_NUMA
2450 printk("Policy zone: %s\n", zone_names[policy_zone]);
2451#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07002452}
2453
2454/*
2455 * Helper functions to size the waitqueue hash table.
2456 * Essentially these want to choose hash table sizes sufficiently
2457 * large so that collisions trying to wait on pages are rare.
2458 * But in fact, the number of active page waitqueues on typical
2459 * systems is ridiculously low, less than 200. So this is even
2460 * conservative, even though it seems large.
2461 *
2462 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
2463 * waitqueues, i.e. the size of the waitq table given the number of pages.
2464 */
2465#define PAGES_PER_WAITQUEUE 256
2466
Yasunori Gotocca448f2006-06-23 02:03:10 -07002467#ifndef CONFIG_MEMORY_HOTPLUG
Yasunori Goto02b694d2006-06-23 02:03:08 -07002468static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002469{
2470 unsigned long size = 1;
2471
2472 pages /= PAGES_PER_WAITQUEUE;
2473
2474 while (size < pages)
2475 size <<= 1;
2476
2477 /*
2478 * Once we have dozens or even hundreds of threads sleeping
2479 * on IO we've got bigger problems than wait queue collision.
2480 * Limit the size of the wait table to a reasonable size.
2481 */
2482 size = min(size, 4096UL);
2483
2484 return max(size, 4UL);
2485}
Yasunori Gotocca448f2006-06-23 02:03:10 -07002486#else
2487/*
2488 * A zone's size might be changed by hot-add, so it is not possible to determine
2489 * a suitable size for its wait_table. So we use the maximum size now.
2490 *
2491 * The max wait table size = 4096 x sizeof(wait_queue_head_t). ie:
2492 *
2493 * i386 (preemption config) : 4096 x 16 = 64Kbyte.
2494 * ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
2495 * ia64, x86-64 (preemption) : 4096 x 24 = 96Kbyte.
2496 *
2497 * The maximum entries are prepared when a zone's memory is (512K + 256) pages
2498 * or more by the traditional way. (See above). It equals:
2499 *
2500 * i386, x86-64, powerpc(4K page size) : = ( 2G + 1M)byte.
2501 * ia64(16K page size) : = ( 8G + 4M)byte.
2502 * powerpc (64K page size) : = (32G +16M)byte.
2503 */
2504static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
2505{
2506 return 4096UL;
2507}
2508#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07002509
2510/*
2511 * This is an integer logarithm so that shifts can be used later
2512 * to extract the more random high bits from the multiplicative
2513 * hash function before the remainder is taken.
2514 */
2515static inline unsigned long wait_table_bits(unsigned long size)
2516{
2517 return ffz(~size);
2518}
2519
2520#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
2521
Mel Gorman56fd56b2007-10-16 01:25:58 -07002522/*
Mel Gormand9c23402007-10-16 01:26:01 -07002523 * Mark a number of pageblocks as MIGRATE_RESERVE. The number
Mel Gorman56fd56b2007-10-16 01:25:58 -07002524 * of blocks reserved is based on zone->pages_min. The memory within the
2525 * reserve will tend to store contiguous free pages. Setting min_free_kbytes
2526 * higher will lead to a bigger reserve which will get freed as contiguous
2527 * blocks as reclaim kicks in
2528 */
2529static void setup_zone_migrate_reserve(struct zone *zone)
2530{
2531 unsigned long start_pfn, pfn, end_pfn;
2532 struct page *page;
2533 unsigned long reserve, block_migratetype;
2534
2535 /* Get the start pfn, end pfn and the number of blocks to reserve */
2536 start_pfn = zone->zone_start_pfn;
2537 end_pfn = start_pfn + zone->spanned_pages;
Mel Gormand9c23402007-10-16 01:26:01 -07002538 reserve = roundup(zone->pages_min, pageblock_nr_pages) >>
2539 pageblock_order;
Mel Gorman56fd56b2007-10-16 01:25:58 -07002540
Mel Gormand9c23402007-10-16 01:26:01 -07002541 for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
Mel Gorman56fd56b2007-10-16 01:25:58 -07002542 if (!pfn_valid(pfn))
2543 continue;
2544 page = pfn_to_page(pfn);
2545
Adam Litke344c7902008-09-02 14:35:38 -07002546 /* Watch out for overlapping nodes */
2547 if (page_to_nid(page) != zone_to_nid(zone))
2548 continue;
2549
Mel Gorman56fd56b2007-10-16 01:25:58 -07002550 /* Blocks with reserved pages will never free, skip them. */
2551 if (PageReserved(page))
2552 continue;
2553
2554 block_migratetype = get_pageblock_migratetype(page);
2555
2556 /* If this block is reserved, account for it */
2557 if (reserve > 0 && block_migratetype == MIGRATE_RESERVE) {
2558 reserve--;
2559 continue;
2560 }
2561
2562 /* Suitable for reserving if this block is movable */
2563 if (reserve > 0 && block_migratetype == MIGRATE_MOVABLE) {
2564 set_pageblock_migratetype(page, MIGRATE_RESERVE);
2565 move_freepages_block(zone, page, MIGRATE_RESERVE);
2566 reserve--;
2567 continue;
2568 }
2569
2570 /*
2571 * If the reserve is met and this is a previous reserved block,
2572 * take it back
2573 */
2574 if (block_migratetype == MIGRATE_RESERVE) {
2575 set_pageblock_migratetype(page, MIGRATE_MOVABLE);
2576 move_freepages_block(zone, page, MIGRATE_MOVABLE);
2577 }
2578 }
2579}
Mel Gormanac0e5b72007-10-16 01:25:58 -07002580
Linus Torvalds1da177e2005-04-16 15:20:36 -07002581/*
2582 * Initially all pages are reserved - free ones are freed
2583 * up by free_all_bootmem() once the early boot process is
2584 * done. Non-atomic initialization, single-pass.
2585 */
Matt Tolentinoc09b4242006-01-17 07:03:44 +01002586void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
Dave Hansena2f3aa02007-01-10 23:15:30 -08002587 unsigned long start_pfn, enum memmap_context context)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002588{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002589 struct page *page;
Andy Whitcroft29751f62005-06-23 00:08:00 -07002590 unsigned long end_pfn = start_pfn + size;
2591 unsigned long pfn;
KAMEZAWA Hiroyuki86051ca2008-04-29 00:58:21 -07002592 struct zone *z;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002593
KAMEZAWA Hiroyuki86051ca2008-04-29 00:58:21 -07002594 z = &NODE_DATA(nid)->node_zones[zone];
Greg Ungerercbe8dd42006-01-12 01:05:24 -08002595 for (pfn = start_pfn; pfn < end_pfn; pfn++) {
Dave Hansena2f3aa02007-01-10 23:15:30 -08002596 /*
2597 * There can be holes in boot-time mem_map[]s
2598 * handed to this function. They do not
2599 * exist on hotplugged memory.
2600 */
2601 if (context == MEMMAP_EARLY) {
2602 if (!early_pfn_valid(pfn))
2603 continue;
2604 if (!early_pfn_in_nid(pfn, nid))
2605 continue;
2606 }
Andy Whitcroftd41dee32005-06-23 00:07:54 -07002607 page = pfn_to_page(pfn);
2608 set_page_links(page, zone, nid, pfn);
Mel Gorman708614e2008-07-23 21:26:51 -07002609 mminit_verify_page_links(page, zone, nid, pfn);
Nick Piggin7835e982006-03-22 00:08:40 -08002610 init_page_count(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002611 reset_page_mapcount(page);
2612 SetPageReserved(page);
Mel Gormanb2a0ac82007-10-16 01:25:48 -07002613 /*
2614 * Mark the block movable so that blocks are reserved for
2615 * movable at startup. This will force kernel allocations
2616 * to reserve their blocks rather than leaking throughout
2617 * the address space during boot when many long-lived
Mel Gorman56fd56b2007-10-16 01:25:58 -07002618 * kernel allocations are made. Later some blocks near
2619 * the start are marked MIGRATE_RESERVE by
2620 * setup_zone_migrate_reserve()
KAMEZAWA Hiroyuki86051ca2008-04-29 00:58:21 -07002621 *
2622 * bitmap is created for zone's valid pfn range. but memmap
2623 * can be created for invalid pages (for alignment)
2624 * check here not to call set_pageblock_migratetype() against
2625 * pfn out of zone.
Mel Gormanb2a0ac82007-10-16 01:25:48 -07002626 */
KAMEZAWA Hiroyuki86051ca2008-04-29 00:58:21 -07002627 if ((z->zone_start_pfn <= pfn)
2628 && (pfn < z->zone_start_pfn + z->spanned_pages)
2629 && !(pfn & (pageblock_nr_pages - 1)))
Mel Gorman56fd56b2007-10-16 01:25:58 -07002630 set_pageblock_migratetype(page, MIGRATE_MOVABLE);
Mel Gormanb2a0ac82007-10-16 01:25:48 -07002631
Linus Torvalds1da177e2005-04-16 15:20:36 -07002632 INIT_LIST_HEAD(&page->lru);
2633#ifdef WANT_PAGE_VIRTUAL
2634 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
2635 if (!is_highmem_idx(zone))
Bob Picco3212c6b2005-06-27 14:36:28 -07002636 set_page_address(page, __va(pfn << PAGE_SHIFT));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002637#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07002638 }
2639}
2640
Andi Kleen1e548de2008-02-04 22:29:26 -08002641static void __meminit zone_init_free_lists(struct zone *zone)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002642{
Mel Gormanb2a0ac82007-10-16 01:25:48 -07002643 int order, t;
2644 for_each_migratetype_order(order, t) {
2645 INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002646 zone->free_area[order].nr_free = 0;
2647 }
2648}
2649
2650#ifndef __HAVE_ARCH_MEMMAP_INIT
2651#define memmap_init(size, nid, zone, start_pfn) \
Dave Hansena2f3aa02007-01-10 23:15:30 -08002652 memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002653#endif
2654
Sam Ravnborg1d6f4e62008-01-17 15:21:12 -08002655static int zone_batchsize(struct zone *zone)
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002656{
2657 int batch;
2658
2659 /*
2660 * The per-cpu-pages pools are set to around 1000th of the
Seth, Rohitba56e912005-10-29 18:15:47 -07002661 * size of the zone. But no more than 1/2 of a meg.
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002662 *
2663 * OK, so we don't know how big the cache is. So guess.
2664 */
2665 batch = zone->present_pages / 1024;
Seth, Rohitba56e912005-10-29 18:15:47 -07002666 if (batch * PAGE_SIZE > 512 * 1024)
2667 batch = (512 * 1024) / PAGE_SIZE;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002668 batch /= 4; /* We effectively *= 4 below */
2669 if (batch < 1)
2670 batch = 1;
2671
2672 /*
Nick Piggin0ceaacc2005-12-04 13:55:25 +11002673 * Clamp the batch to a 2^n - 1 value. Having a power
2674 * of 2 value was found to be more likely to have
2675 * suboptimal cache aliasing properties in some cases.
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002676 *
Nick Piggin0ceaacc2005-12-04 13:55:25 +11002677 * For example if 2 tasks are alternately allocating
2678 * batches of pages, one task can end up with a lot
2679 * of pages of one half of the possible page colors
2680 * and the other with pages of the other colors.
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002681 */
Nick Piggin0ceaacc2005-12-04 13:55:25 +11002682 batch = (1 << (fls(batch + batch/2)-1)) - 1;
Seth, Rohitba56e912005-10-29 18:15:47 -07002683
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002684 return batch;
2685}
2686
Adrian Bunkb69a7282008-07-23 21:28:12 -07002687static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
Christoph Lameter2caaad42005-06-21 17:15:00 -07002688{
2689 struct per_cpu_pages *pcp;
2690
Magnus Damm1c6fe942005-10-26 01:58:59 -07002691 memset(p, 0, sizeof(*p));
2692
Christoph Lameter3dfa5722008-02-04 22:29:19 -08002693 pcp = &p->pcp;
Christoph Lameter2caaad42005-06-21 17:15:00 -07002694 pcp->count = 0;
Christoph Lameter2caaad42005-06-21 17:15:00 -07002695 pcp->high = 6 * batch;
2696 pcp->batch = max(1UL, 1 * batch);
2697 INIT_LIST_HEAD(&pcp->list);
Christoph Lameter2caaad42005-06-21 17:15:00 -07002698}
2699
Rohit Seth8ad4b1f2006-01-08 01:00:40 -08002700/*
2701 * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
2702 * to the value high for the pageset p.
2703 */
2704
2705static void setup_pagelist_highmark(struct per_cpu_pageset *p,
2706 unsigned long high)
2707{
2708 struct per_cpu_pages *pcp;
2709
Christoph Lameter3dfa5722008-02-04 22:29:19 -08002710 pcp = &p->pcp;
Rohit Seth8ad4b1f2006-01-08 01:00:40 -08002711 pcp->high = high;
2712 pcp->batch = max(1UL, high/4);
2713 if ((high/4) > (PAGE_SHIFT * 8))
2714 pcp->batch = PAGE_SHIFT * 8;
2715}
2716
2717
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002718#ifdef CONFIG_NUMA
2719/*
Christoph Lameter2caaad42005-06-21 17:15:00 -07002720 * Boot pageset table. One per cpu which is going to be used for all
2721 * zones and all nodes. The parameters will be set in such a way
2722 * that an item put on a list will immediately be handed over to
2723 * the buddy list. This is safe since pageset manipulation is done
2724 * with interrupts disabled.
2725 *
2726 * Some NUMA counter updates may also be caught by the boot pagesets.
Christoph Lameterb7c84c62005-06-22 20:26:07 -07002727 *
2728 * The boot_pagesets must be kept even after bootup is complete for
2729 * unused processors and/or zones. They do play a role for bootstrapping
2730 * hotplugged processors.
2731 *
2732 * zoneinfo_show() and maybe other functions do
2733 * not check if the processor is online before following the pageset pointer.
2734 * Other parts of the kernel may not check if the zone is available.
Christoph Lameter2caaad42005-06-21 17:15:00 -07002735 */
Eric Dumazet88a2a4ac2006-02-04 23:27:36 -08002736static struct per_cpu_pageset boot_pageset[NR_CPUS];
Christoph Lameter2caaad42005-06-21 17:15:00 -07002737
2738/*
2739 * Dynamically allocate memory for the
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002740 * per cpu pageset array in struct zone.
2741 */
Ashok Raj6292d9a2006-02-01 03:04:44 -08002742static int __cpuinit process_zones(int cpu)
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002743{
2744 struct zone *zone, *dzone;
Christoph Lameter37c07082007-10-16 01:25:36 -07002745 int node = cpu_to_node(cpu);
2746
2747 node_set_state(node, N_CPU); /* this node has a cpu */
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002748
2749 for_each_zone(zone) {
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002750
Christoph Lameter66a55032006-09-27 01:50:09 -07002751 if (!populated_zone(zone))
2752 continue;
2753
Nick Piggin23316bc2006-01-08 01:00:41 -08002754 zone_pcp(zone, cpu) = kmalloc_node(sizeof(struct per_cpu_pageset),
Christoph Lameter37c07082007-10-16 01:25:36 -07002755 GFP_KERNEL, node);
Nick Piggin23316bc2006-01-08 01:00:41 -08002756 if (!zone_pcp(zone, cpu))
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002757 goto bad;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002758
Nick Piggin23316bc2006-01-08 01:00:41 -08002759 setup_pageset(zone_pcp(zone, cpu), zone_batchsize(zone));
Rohit Seth8ad4b1f2006-01-08 01:00:40 -08002760
2761 if (percpu_pagelist_fraction)
2762 setup_pagelist_highmark(zone_pcp(zone, cpu),
2763 (zone->present_pages / percpu_pagelist_fraction));
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002764 }
2765
2766 return 0;
2767bad:
2768 for_each_zone(dzone) {
Andrew Morton64191682007-08-30 23:56:17 -07002769 if (!populated_zone(dzone))
2770 continue;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002771 if (dzone == zone)
2772 break;
Nick Piggin23316bc2006-01-08 01:00:41 -08002773 kfree(zone_pcp(dzone, cpu));
2774 zone_pcp(dzone, cpu) = NULL;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002775 }
2776 return -ENOMEM;
2777}
2778
2779static inline void free_zone_pagesets(int cpu)
2780{
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002781 struct zone *zone;
2782
2783 for_each_zone(zone) {
2784 struct per_cpu_pageset *pset = zone_pcp(zone, cpu);
2785
David Rientjesf3ef9ea2006-09-25 16:24:57 -07002786 /* Free per_cpu_pageset if it is slab allocated */
2787 if (pset != &boot_pageset[cpu])
2788 kfree(pset);
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002789 zone_pcp(zone, cpu) = NULL;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002790 }
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002791}
2792
Chandra Seetharaman9c7b2162006-06-27 02:54:07 -07002793static int __cpuinit pageset_cpuup_callback(struct notifier_block *nfb,
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002794 unsigned long action,
2795 void *hcpu)
2796{
2797 int cpu = (long)hcpu;
2798 int ret = NOTIFY_OK;
2799
2800 switch (action) {
Andy Whitcroftce421c72006-12-06 20:33:08 -08002801 case CPU_UP_PREPARE:
Rafael J. Wysocki8bb78442007-05-09 02:35:10 -07002802 case CPU_UP_PREPARE_FROZEN:
Andy Whitcroftce421c72006-12-06 20:33:08 -08002803 if (process_zones(cpu))
2804 ret = NOTIFY_BAD;
2805 break;
2806 case CPU_UP_CANCELED:
Rafael J. Wysocki8bb78442007-05-09 02:35:10 -07002807 case CPU_UP_CANCELED_FROZEN:
Andy Whitcroftce421c72006-12-06 20:33:08 -08002808 case CPU_DEAD:
Rafael J. Wysocki8bb78442007-05-09 02:35:10 -07002809 case CPU_DEAD_FROZEN:
Andy Whitcroftce421c72006-12-06 20:33:08 -08002810 free_zone_pagesets(cpu);
2811 break;
2812 default:
2813 break;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002814 }
2815 return ret;
2816}
2817
Chandra Seetharaman74b85f32006-06-27 02:54:09 -07002818static struct notifier_block __cpuinitdata pageset_notifier =
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002819 { &pageset_cpuup_callback, NULL, 0 };
2820
Al Viro78d99552005-12-15 09:18:25 +00002821void __init setup_per_cpu_pageset(void)
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07002822{
2823 int err;
2824
2825 /* Initialize per_cpu_pageset for cpu 0.
2826 * A cpuup callback will do this for every cpu
2827 * as it comes online
2828 */
2829 err = process_zones(smp_processor_id());
2830 BUG_ON(err);
2831 register_cpu_notifier(&pageset_notifier);
2832}
2833
2834#endif
2835
Sam Ravnborg577a32f2007-05-17 23:29:25 +02002836static noinline __init_refok
Yasunori Gotocca448f2006-06-23 02:03:10 -07002837int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
Dave Hansened8ece22005-10-29 18:16:50 -07002838{
2839 int i;
2840 struct pglist_data *pgdat = zone->zone_pgdat;
Yasunori Gotocca448f2006-06-23 02:03:10 -07002841 size_t alloc_size;
Dave Hansened8ece22005-10-29 18:16:50 -07002842
2843 /*
2844 * The per-page waitqueue mechanism uses hashed waitqueues
2845 * per zone.
2846 */
Yasunori Goto02b694d2006-06-23 02:03:08 -07002847 zone->wait_table_hash_nr_entries =
2848 wait_table_hash_nr_entries(zone_size_pages);
2849 zone->wait_table_bits =
2850 wait_table_bits(zone->wait_table_hash_nr_entries);
Yasunori Gotocca448f2006-06-23 02:03:10 -07002851 alloc_size = zone->wait_table_hash_nr_entries
2852 * sizeof(wait_queue_head_t);
2853
Heiko Carstenscd94b9d2008-05-23 13:04:52 -07002854 if (!slab_is_available()) {
Yasunori Gotocca448f2006-06-23 02:03:10 -07002855 zone->wait_table = (wait_queue_head_t *)
2856 alloc_bootmem_node(pgdat, alloc_size);
2857 } else {
2858 /*
2859 * This case means that a zone whose size was 0 gets new memory
2860 * via memory hot-add.
2861 * But it may be the case that a new node was hot-added. In
2862 * this case vmalloc() will not be able to use this new node's
2863 * memory - this wait_table must be initialized to use this new
2864 * node itself as well.
2865 * To use this new node's memory, further consideration will be
2866 * necessary.
2867 */
Jesper Juhl8691f3a2007-10-16 01:24:49 -07002868 zone->wait_table = vmalloc(alloc_size);
Yasunori Gotocca448f2006-06-23 02:03:10 -07002869 }
2870 if (!zone->wait_table)
2871 return -ENOMEM;
Dave Hansened8ece22005-10-29 18:16:50 -07002872
Yasunori Goto02b694d2006-06-23 02:03:08 -07002873 for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
Dave Hansened8ece22005-10-29 18:16:50 -07002874 init_waitqueue_head(zone->wait_table + i);
Yasunori Gotocca448f2006-06-23 02:03:10 -07002875
2876 return 0;
Dave Hansened8ece22005-10-29 18:16:50 -07002877}
2878
Matt Tolentinoc09b4242006-01-17 07:03:44 +01002879static __meminit void zone_pcp_init(struct zone *zone)
Dave Hansened8ece22005-10-29 18:16:50 -07002880{
2881 int cpu;
2882 unsigned long batch = zone_batchsize(zone);
2883
2884 for (cpu = 0; cpu < NR_CPUS; cpu++) {
2885#ifdef CONFIG_NUMA
2886 /* Early boot. Slab allocator not functional yet */
Nick Piggin23316bc2006-01-08 01:00:41 -08002887 zone_pcp(zone, cpu) = &boot_pageset[cpu];
Dave Hansened8ece22005-10-29 18:16:50 -07002888 setup_pageset(&boot_pageset[cpu],0);
2889#else
2890 setup_pageset(zone_pcp(zone,cpu), batch);
2891#endif
2892 }
Anton Blanchardf5335c02006-03-25 03:06:49 -08002893 if (zone->present_pages)
2894 printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n",
2895 zone->name, zone->present_pages, batch);
Dave Hansened8ece22005-10-29 18:16:50 -07002896}
2897
Yasunori Goto718127c2006-06-23 02:03:10 -07002898__meminit int init_currently_empty_zone(struct zone *zone,
2899 unsigned long zone_start_pfn,
Dave Hansena2f3aa02007-01-10 23:15:30 -08002900 unsigned long size,
2901 enum memmap_context context)
Dave Hansened8ece22005-10-29 18:16:50 -07002902{
2903 struct pglist_data *pgdat = zone->zone_pgdat;
Yasunori Gotocca448f2006-06-23 02:03:10 -07002904 int ret;
2905 ret = zone_wait_table_init(zone, size);
2906 if (ret)
2907 return ret;
Dave Hansened8ece22005-10-29 18:16:50 -07002908 pgdat->nr_zones = zone_idx(zone) + 1;
2909
Dave Hansened8ece22005-10-29 18:16:50 -07002910 zone->zone_start_pfn = zone_start_pfn;
2911
Mel Gorman708614e2008-07-23 21:26:51 -07002912 mminit_dprintk(MMINIT_TRACE, "memmap_init",
2913 "Initialising map node %d zone %lu pfns %lu -> %lu\n",
2914 pgdat->node_id,
2915 (unsigned long)zone_idx(zone),
2916 zone_start_pfn, (zone_start_pfn + size));
2917
Andi Kleen1e548de2008-02-04 22:29:26 -08002918 zone_init_free_lists(zone);
Yasunori Goto718127c2006-06-23 02:03:10 -07002919
2920 return 0;
Dave Hansened8ece22005-10-29 18:16:50 -07002921}
2922
Mel Gormanc7132162006-09-27 01:49:43 -07002923#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
2924/*
2925 * Basic iterator support. Return the first range of PFNs for a node
2926 * Note: nid == MAX_NUMNODES returns first region regardless of node
2927 */
Yasunori Gotoa3142c82007-05-08 00:23:07 -07002928static int __meminit first_active_region_index_in_nid(int nid)
Mel Gormanc7132162006-09-27 01:49:43 -07002929{
2930 int i;
2931
2932 for (i = 0; i < nr_nodemap_entries; i++)
2933 if (nid == MAX_NUMNODES || early_node_map[i].nid == nid)
2934 return i;
2935
2936 return -1;
2937}
2938
2939/*
2940 * Basic iterator support. Return the next active range of PFNs for a node
Simon Arlott183ff222007-10-20 01:27:18 +02002941 * Note: nid == MAX_NUMNODES returns next region regardless of node
Mel Gormanc7132162006-09-27 01:49:43 -07002942 */
Yasunori Gotoa3142c82007-05-08 00:23:07 -07002943static int __meminit next_active_region_index_in_nid(int index, int nid)
Mel Gormanc7132162006-09-27 01:49:43 -07002944{
2945 for (index = index + 1; index < nr_nodemap_entries; index++)
2946 if (nid == MAX_NUMNODES || early_node_map[index].nid == nid)
2947 return index;
2948
2949 return -1;
2950}
2951
2952#ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
2953/*
2954 * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
2955 * Architectures may implement their own version but if add_active_range()
2956 * was used and there are no special requirements, this is a convenient
2957 * alternative
2958 */
Stephen Rothwell6f076f52007-05-10 03:15:27 -07002959int __meminit early_pfn_to_nid(unsigned long pfn)
Mel Gormanc7132162006-09-27 01:49:43 -07002960{
2961 int i;
2962
2963 for (i = 0; i < nr_nodemap_entries; i++) {
2964 unsigned long start_pfn = early_node_map[i].start_pfn;
2965 unsigned long end_pfn = early_node_map[i].end_pfn;
2966
2967 if (start_pfn <= pfn && pfn < end_pfn)
2968 return early_node_map[i].nid;
2969 }
2970
2971 return 0;
2972}
2973#endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
2974
2975/* Basic iterator support to walk early_node_map[] */
2976#define for_each_active_range_index_in_nid(i, nid) \
2977 for (i = first_active_region_index_in_nid(nid); i != -1; \
2978 i = next_active_region_index_in_nid(i, nid))
2979
2980/**
2981 * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002982 * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
2983 * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
Mel Gormanc7132162006-09-27 01:49:43 -07002984 *
2985 * If an architecture guarantees that all ranges registered with
2986 * add_active_ranges() contain no holes and may be freed, this
2987 * this function may be used instead of calling free_bootmem() manually.
2988 */
2989void __init free_bootmem_with_active_regions(int nid,
2990 unsigned long max_low_pfn)
2991{
2992 int i;
2993
2994 for_each_active_range_index_in_nid(i, nid) {
2995 unsigned long size_pages = 0;
2996 unsigned long end_pfn = early_node_map[i].end_pfn;
2997
2998 if (early_node_map[i].start_pfn >= max_low_pfn)
2999 continue;
3000
3001 if (end_pfn > max_low_pfn)
3002 end_pfn = max_low_pfn;
3003
3004 size_pages = end_pfn - early_node_map[i].start_pfn;
3005 free_bootmem_node(NODE_DATA(early_node_map[i].nid),
3006 PFN_PHYS(early_node_map[i].start_pfn),
3007 size_pages << PAGE_SHIFT);
3008 }
3009}
3010
Yinghai Lub5bc6c02008-06-14 18:32:52 -07003011void __init work_with_active_regions(int nid, work_fn_t work_fn, void *data)
3012{
3013 int i;
Yinghai Lud52d53b2008-06-16 20:10:55 -07003014 int ret;
Yinghai Lub5bc6c02008-06-14 18:32:52 -07003015
Yinghai Lud52d53b2008-06-16 20:10:55 -07003016 for_each_active_range_index_in_nid(i, nid) {
3017 ret = work_fn(early_node_map[i].start_pfn,
3018 early_node_map[i].end_pfn, data);
3019 if (ret)
3020 break;
3021 }
Yinghai Lub5bc6c02008-06-14 18:32:52 -07003022}
Mel Gormanc7132162006-09-27 01:49:43 -07003023/**
3024 * sparse_memory_present_with_active_regions - Call memory_present for each active range
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003025 * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
Mel Gormanc7132162006-09-27 01:49:43 -07003026 *
3027 * If an architecture guarantees that all ranges registered with
3028 * add_active_ranges() contain no holes and may be freed, this
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003029 * function may be used instead of calling memory_present() manually.
Mel Gormanc7132162006-09-27 01:49:43 -07003030 */
3031void __init sparse_memory_present_with_active_regions(int nid)
3032{
3033 int i;
3034
3035 for_each_active_range_index_in_nid(i, nid)
3036 memory_present(early_node_map[i].nid,
3037 early_node_map[i].start_pfn,
3038 early_node_map[i].end_pfn);
3039}
3040
3041/**
Mel Gormanfb014392006-09-27 01:49:59 -07003042 * push_node_boundaries - Push node boundaries to at least the requested boundary
3043 * @nid: The nid of the node to push the boundary for
3044 * @start_pfn: The start pfn of the node
3045 * @end_pfn: The end pfn of the node
3046 *
3047 * In reserve-based hot-add, mem_map is allocated that is unused until hotadd
3048 * time. Specifically, on x86_64, SRAT will report ranges that can potentially
3049 * be hotplugged even though no physical memory exists. This function allows
3050 * an arch to push out the node boundaries so mem_map is allocated that can
3051 * be used later.
3052 */
3053#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
3054void __init push_node_boundaries(unsigned int nid,
3055 unsigned long start_pfn, unsigned long end_pfn)
3056{
Mel Gorman6b74ab92008-07-23 21:26:49 -07003057 mminit_dprintk(MMINIT_TRACE, "zoneboundary",
3058 "Entering push_node_boundaries(%u, %lu, %lu)\n",
Mel Gormanfb014392006-09-27 01:49:59 -07003059 nid, start_pfn, end_pfn);
3060
3061 /* Initialise the boundary for this node if necessary */
3062 if (node_boundary_end_pfn[nid] == 0)
3063 node_boundary_start_pfn[nid] = -1UL;
3064
3065 /* Update the boundaries */
3066 if (node_boundary_start_pfn[nid] > start_pfn)
3067 node_boundary_start_pfn[nid] = start_pfn;
3068 if (node_boundary_end_pfn[nid] < end_pfn)
3069 node_boundary_end_pfn[nid] = end_pfn;
3070}
3071
3072/* If necessary, push the node boundary out for reserve hotadd */
Jan Beulich98011f52007-07-15 23:38:17 -07003073static void __meminit account_node_boundary(unsigned int nid,
Mel Gormanfb014392006-09-27 01:49:59 -07003074 unsigned long *start_pfn, unsigned long *end_pfn)
3075{
Mel Gorman6b74ab92008-07-23 21:26:49 -07003076 mminit_dprintk(MMINIT_TRACE, "zoneboundary",
3077 "Entering account_node_boundary(%u, %lu, %lu)\n",
Mel Gormanfb014392006-09-27 01:49:59 -07003078 nid, *start_pfn, *end_pfn);
3079
3080 /* Return if boundary information has not been provided */
3081 if (node_boundary_end_pfn[nid] == 0)
3082 return;
3083
3084 /* Check the boundaries and update if necessary */
3085 if (node_boundary_start_pfn[nid] < *start_pfn)
3086 *start_pfn = node_boundary_start_pfn[nid];
3087 if (node_boundary_end_pfn[nid] > *end_pfn)
3088 *end_pfn = node_boundary_end_pfn[nid];
3089}
3090#else
3091void __init push_node_boundaries(unsigned int nid,
3092 unsigned long start_pfn, unsigned long end_pfn) {}
3093
Jan Beulich98011f52007-07-15 23:38:17 -07003094static void __meminit account_node_boundary(unsigned int nid,
Mel Gormanfb014392006-09-27 01:49:59 -07003095 unsigned long *start_pfn, unsigned long *end_pfn) {}
3096#endif
3097
3098
3099/**
Mel Gormanc7132162006-09-27 01:49:43 -07003100 * get_pfn_range_for_nid - Return the start and end page frames for a node
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003101 * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
3102 * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
3103 * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
Mel Gormanc7132162006-09-27 01:49:43 -07003104 *
3105 * It returns the start and end page frame of a node based on information
3106 * provided by an arch calling add_active_range(). If called for a node
3107 * with no available memory, a warning is printed and the start and end
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003108 * PFNs will be 0.
Mel Gormanc7132162006-09-27 01:49:43 -07003109 */
Yasunori Gotoa3142c82007-05-08 00:23:07 -07003110void __meminit get_pfn_range_for_nid(unsigned int nid,
Mel Gormanc7132162006-09-27 01:49:43 -07003111 unsigned long *start_pfn, unsigned long *end_pfn)
3112{
3113 int i;
3114 *start_pfn = -1UL;
3115 *end_pfn = 0;
3116
3117 for_each_active_range_index_in_nid(i, nid) {
3118 *start_pfn = min(*start_pfn, early_node_map[i].start_pfn);
3119 *end_pfn = max(*end_pfn, early_node_map[i].end_pfn);
3120 }
3121
Christoph Lameter633c0662007-10-16 01:25:37 -07003122 if (*start_pfn == -1UL)
Mel Gormanc7132162006-09-27 01:49:43 -07003123 *start_pfn = 0;
Mel Gormanfb014392006-09-27 01:49:59 -07003124
3125 /* Push the node boundaries out if requested */
3126 account_node_boundary(nid, start_pfn, end_pfn);
Mel Gormanc7132162006-09-27 01:49:43 -07003127}
3128
3129/*
Mel Gorman2a1e2742007-07-17 04:03:12 -07003130 * This finds a zone that can be used for ZONE_MOVABLE pages. The
3131 * assumption is made that zones within a node are ordered in monotonic
3132 * increasing memory addresses so that the "highest" populated zone is used
3133 */
Adrian Bunkb69a7282008-07-23 21:28:12 -07003134static void __init find_usable_zone_for_movable(void)
Mel Gorman2a1e2742007-07-17 04:03:12 -07003135{
3136 int zone_index;
3137 for (zone_index = MAX_NR_ZONES - 1; zone_index >= 0; zone_index--) {
3138 if (zone_index == ZONE_MOVABLE)
3139 continue;
3140
3141 if (arch_zone_highest_possible_pfn[zone_index] >
3142 arch_zone_lowest_possible_pfn[zone_index])
3143 break;
3144 }
3145
3146 VM_BUG_ON(zone_index == -1);
3147 movable_zone = zone_index;
3148}
3149
3150/*
3151 * The zone ranges provided by the architecture do not include ZONE_MOVABLE
3152 * because it is sized independant of architecture. Unlike the other zones,
3153 * the starting point for ZONE_MOVABLE is not fixed. It may be different
3154 * in each node depending on the size of each node and how evenly kernelcore
3155 * is distributed. This helper function adjusts the zone ranges
3156 * provided by the architecture for a given node by using the end of the
3157 * highest usable zone for ZONE_MOVABLE. This preserves the assumption that
3158 * zones within a node are in order of monotonic increases memory addresses
3159 */
Adrian Bunkb69a7282008-07-23 21:28:12 -07003160static void __meminit adjust_zone_range_for_zone_movable(int nid,
Mel Gorman2a1e2742007-07-17 04:03:12 -07003161 unsigned long zone_type,
3162 unsigned long node_start_pfn,
3163 unsigned long node_end_pfn,
3164 unsigned long *zone_start_pfn,
3165 unsigned long *zone_end_pfn)
3166{
3167 /* Only adjust if ZONE_MOVABLE is on this node */
3168 if (zone_movable_pfn[nid]) {
3169 /* Size ZONE_MOVABLE */
3170 if (zone_type == ZONE_MOVABLE) {
3171 *zone_start_pfn = zone_movable_pfn[nid];
3172 *zone_end_pfn = min(node_end_pfn,
3173 arch_zone_highest_possible_pfn[movable_zone]);
3174
3175 /* Adjust for ZONE_MOVABLE starting within this range */
3176 } else if (*zone_start_pfn < zone_movable_pfn[nid] &&
3177 *zone_end_pfn > zone_movable_pfn[nid]) {
3178 *zone_end_pfn = zone_movable_pfn[nid];
3179
3180 /* Check if this whole range is within ZONE_MOVABLE */
3181 } else if (*zone_start_pfn >= zone_movable_pfn[nid])
3182 *zone_start_pfn = *zone_end_pfn;
3183 }
3184}
3185
3186/*
Mel Gormanc7132162006-09-27 01:49:43 -07003187 * Return the number of pages a zone spans in a node, including holes
3188 * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
3189 */
Paul Mundt6ea6e682007-07-15 23:38:20 -07003190static unsigned long __meminit zone_spanned_pages_in_node(int nid,
Mel Gormanc7132162006-09-27 01:49:43 -07003191 unsigned long zone_type,
3192 unsigned long *ignored)
3193{
3194 unsigned long node_start_pfn, node_end_pfn;
3195 unsigned long zone_start_pfn, zone_end_pfn;
3196
3197 /* Get the start and end of the node and zone */
3198 get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
3199 zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
3200 zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
Mel Gorman2a1e2742007-07-17 04:03:12 -07003201 adjust_zone_range_for_zone_movable(nid, zone_type,
3202 node_start_pfn, node_end_pfn,
3203 &zone_start_pfn, &zone_end_pfn);
Mel Gormanc7132162006-09-27 01:49:43 -07003204
3205 /* Check that this node has pages within the zone's required range */
3206 if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
3207 return 0;
3208
3209 /* Move the zone boundaries inside the node if necessary */
3210 zone_end_pfn = min(zone_end_pfn, node_end_pfn);
3211 zone_start_pfn = max(zone_start_pfn, node_start_pfn);
3212
3213 /* Return the spanned pages */
3214 return zone_end_pfn - zone_start_pfn;
3215}
3216
3217/*
3218 * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003219 * then all holes in the requested range will be accounted for.
Mel Gormanc7132162006-09-27 01:49:43 -07003220 */
Adrian Bunkb69a7282008-07-23 21:28:12 -07003221static unsigned long __meminit __absent_pages_in_range(int nid,
Mel Gormanc7132162006-09-27 01:49:43 -07003222 unsigned long range_start_pfn,
3223 unsigned long range_end_pfn)
3224{
3225 int i = 0;
3226 unsigned long prev_end_pfn = 0, hole_pages = 0;
3227 unsigned long start_pfn;
3228
3229 /* Find the end_pfn of the first active range of pfns in the node */
3230 i = first_active_region_index_in_nid(nid);
3231 if (i == -1)
3232 return 0;
3233
Mel Gormanb5445f92007-07-26 10:41:18 -07003234 prev_end_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
3235
Mel Gorman9c7cd682006-09-27 01:49:58 -07003236 /* Account for ranges before physical memory on this node */
3237 if (early_node_map[i].start_pfn > range_start_pfn)
Mel Gormanb5445f92007-07-26 10:41:18 -07003238 hole_pages = prev_end_pfn - range_start_pfn;
Mel Gormanc7132162006-09-27 01:49:43 -07003239
3240 /* Find all holes for the zone within the node */
3241 for (; i != -1; i = next_active_region_index_in_nid(i, nid)) {
3242
3243 /* No need to continue if prev_end_pfn is outside the zone */
3244 if (prev_end_pfn >= range_end_pfn)
3245 break;
3246
3247 /* Make sure the end of the zone is not within the hole */
3248 start_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
3249 prev_end_pfn = max(prev_end_pfn, range_start_pfn);
3250
3251 /* Update the hole size cound and move on */
3252 if (start_pfn > range_start_pfn) {
3253 BUG_ON(prev_end_pfn > start_pfn);
3254 hole_pages += start_pfn - prev_end_pfn;
3255 }
3256 prev_end_pfn = early_node_map[i].end_pfn;
3257 }
3258
Mel Gorman9c7cd682006-09-27 01:49:58 -07003259 /* Account for ranges past physical memory on this node */
3260 if (range_end_pfn > prev_end_pfn)
Mel Gorman0c6cb972006-10-28 10:38:59 -07003261 hole_pages += range_end_pfn -
Mel Gorman9c7cd682006-09-27 01:49:58 -07003262 max(range_start_pfn, prev_end_pfn);
3263
Mel Gormanc7132162006-09-27 01:49:43 -07003264 return hole_pages;
3265}
3266
3267/**
3268 * absent_pages_in_range - Return number of page frames in holes within a range
3269 * @start_pfn: The start PFN to start searching for holes
3270 * @end_pfn: The end PFN to stop searching for holes
3271 *
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003272 * It returns the number of pages frames in memory holes within a range.
Mel Gormanc7132162006-09-27 01:49:43 -07003273 */
3274unsigned long __init absent_pages_in_range(unsigned long start_pfn,
3275 unsigned long end_pfn)
3276{
3277 return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
3278}
3279
3280/* Return the number of page frames in holes in a zone on a node */
Paul Mundt6ea6e682007-07-15 23:38:20 -07003281static unsigned long __meminit zone_absent_pages_in_node(int nid,
Mel Gormanc7132162006-09-27 01:49:43 -07003282 unsigned long zone_type,
3283 unsigned long *ignored)
3284{
Mel Gorman9c7cd682006-09-27 01:49:58 -07003285 unsigned long node_start_pfn, node_end_pfn;
3286 unsigned long zone_start_pfn, zone_end_pfn;
3287
3288 get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
3289 zone_start_pfn = max(arch_zone_lowest_possible_pfn[zone_type],
3290 node_start_pfn);
3291 zone_end_pfn = min(arch_zone_highest_possible_pfn[zone_type],
3292 node_end_pfn);
3293
Mel Gorman2a1e2742007-07-17 04:03:12 -07003294 adjust_zone_range_for_zone_movable(nid, zone_type,
3295 node_start_pfn, node_end_pfn,
3296 &zone_start_pfn, &zone_end_pfn);
Mel Gorman9c7cd682006-09-27 01:49:58 -07003297 return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
Mel Gormanc7132162006-09-27 01:49:43 -07003298}
Mel Gorman0e0b8642006-09-27 01:49:56 -07003299
Mel Gormanc7132162006-09-27 01:49:43 -07003300#else
Paul Mundt6ea6e682007-07-15 23:38:20 -07003301static inline unsigned long __meminit zone_spanned_pages_in_node(int nid,
Mel Gormanc7132162006-09-27 01:49:43 -07003302 unsigned long zone_type,
3303 unsigned long *zones_size)
3304{
3305 return zones_size[zone_type];
3306}
3307
Paul Mundt6ea6e682007-07-15 23:38:20 -07003308static inline unsigned long __meminit zone_absent_pages_in_node(int nid,
Mel Gormanc7132162006-09-27 01:49:43 -07003309 unsigned long zone_type,
3310 unsigned long *zholes_size)
3311{
3312 if (!zholes_size)
3313 return 0;
3314
3315 return zholes_size[zone_type];
3316}
Mel Gorman0e0b8642006-09-27 01:49:56 -07003317
Mel Gormanc7132162006-09-27 01:49:43 -07003318#endif
3319
Yasunori Gotoa3142c82007-05-08 00:23:07 -07003320static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,
Mel Gormanc7132162006-09-27 01:49:43 -07003321 unsigned long *zones_size, unsigned long *zholes_size)
3322{
3323 unsigned long realtotalpages, totalpages = 0;
3324 enum zone_type i;
3325
3326 for (i = 0; i < MAX_NR_ZONES; i++)
3327 totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
3328 zones_size);
3329 pgdat->node_spanned_pages = totalpages;
3330
3331 realtotalpages = totalpages;
3332 for (i = 0; i < MAX_NR_ZONES; i++)
3333 realtotalpages -=
3334 zone_absent_pages_in_node(pgdat->node_id, i,
3335 zholes_size);
3336 pgdat->node_present_pages = realtotalpages;
3337 printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
3338 realtotalpages);
3339}
3340
Mel Gorman835c1342007-10-16 01:25:47 -07003341#ifndef CONFIG_SPARSEMEM
3342/*
3343 * Calculate the size of the zone->blockflags rounded to an unsigned long
Mel Gormand9c23402007-10-16 01:26:01 -07003344 * Start by making sure zonesize is a multiple of pageblock_order by rounding
3345 * up. Then use 1 NR_PAGEBLOCK_BITS worth of bits per pageblock, finally
Mel Gorman835c1342007-10-16 01:25:47 -07003346 * round what is now in bits to nearest long in bits, then return it in
3347 * bytes.
3348 */
3349static unsigned long __init usemap_size(unsigned long zonesize)
3350{
3351 unsigned long usemapsize;
3352
Mel Gormand9c23402007-10-16 01:26:01 -07003353 usemapsize = roundup(zonesize, pageblock_nr_pages);
3354 usemapsize = usemapsize >> pageblock_order;
Mel Gorman835c1342007-10-16 01:25:47 -07003355 usemapsize *= NR_PAGEBLOCK_BITS;
3356 usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));
3357
3358 return usemapsize / 8;
3359}
3360
3361static void __init setup_usemap(struct pglist_data *pgdat,
3362 struct zone *zone, unsigned long zonesize)
3363{
3364 unsigned long usemapsize = usemap_size(zonesize);
3365 zone->pageblock_flags = NULL;
3366 if (usemapsize) {
3367 zone->pageblock_flags = alloc_bootmem_node(pgdat, usemapsize);
3368 memset(zone->pageblock_flags, 0, usemapsize);
3369 }
3370}
3371#else
3372static void inline setup_usemap(struct pglist_data *pgdat,
3373 struct zone *zone, unsigned long zonesize) {}
3374#endif /* CONFIG_SPARSEMEM */
3375
Mel Gormand9c23402007-10-16 01:26:01 -07003376#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
Mel Gormanba72cb82007-11-28 16:21:13 -08003377
3378/* Return a sensible default order for the pageblock size. */
3379static inline int pageblock_default_order(void)
3380{
3381 if (HPAGE_SHIFT > PAGE_SHIFT)
3382 return HUGETLB_PAGE_ORDER;
3383
3384 return MAX_ORDER-1;
3385}
3386
Mel Gormand9c23402007-10-16 01:26:01 -07003387/* Initialise the number of pages represented by NR_PAGEBLOCK_BITS */
3388static inline void __init set_pageblock_order(unsigned int order)
3389{
3390 /* Check that pageblock_nr_pages has not already been setup */
3391 if (pageblock_order)
3392 return;
3393
3394 /*
3395 * Assume the largest contiguous order of interest is a huge page.
3396 * This value may be variable depending on boot parameters on IA64
3397 */
3398 pageblock_order = order;
3399}
3400#else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
3401
Mel Gormanba72cb82007-11-28 16:21:13 -08003402/*
3403 * When CONFIG_HUGETLB_PAGE_SIZE_VARIABLE is not set, set_pageblock_order()
3404 * and pageblock_default_order() are unused as pageblock_order is set
3405 * at compile-time. See include/linux/pageblock-flags.h for the values of
3406 * pageblock_order based on the kernel config
3407 */
3408static inline int pageblock_default_order(unsigned int order)
3409{
3410 return MAX_ORDER-1;
3411}
Mel Gormand9c23402007-10-16 01:26:01 -07003412#define set_pageblock_order(x) do {} while (0)
3413
3414#endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
3415
Linus Torvalds1da177e2005-04-16 15:20:36 -07003416/*
3417 * Set up the zone data structures:
3418 * - mark all pages reserved
3419 * - mark all memory queues empty
3420 * - clear the memory bitmaps
3421 */
Alexander van Heukelumb5a0e012008-02-23 15:24:06 -08003422static void __paginginit free_area_init_core(struct pglist_data *pgdat,
Linus Torvalds1da177e2005-04-16 15:20:36 -07003423 unsigned long *zones_size, unsigned long *zholes_size)
3424{
Christoph Lameter2f1b6242006-09-25 23:31:13 -07003425 enum zone_type j;
Dave Hansened8ece22005-10-29 18:16:50 -07003426 int nid = pgdat->node_id;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003427 unsigned long zone_start_pfn = pgdat->node_start_pfn;
Yasunori Goto718127c2006-06-23 02:03:10 -07003428 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003429
Dave Hansen208d54e2005-10-29 18:16:52 -07003430 pgdat_resize_init(pgdat);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003431 pgdat->nr_zones = 0;
3432 init_waitqueue_head(&pgdat->kswapd_wait);
3433 pgdat->kswapd_max_order = 0;
KAMEZAWA Hiroyuki52d4b9a2008-10-18 20:28:16 -07003434 pgdat_page_cgroup_init(pgdat);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003435
3436 for (j = 0; j < MAX_NR_ZONES; j++) {
3437 struct zone *zone = pgdat->node_zones + j;
Mel Gorman0e0b8642006-09-27 01:49:56 -07003438 unsigned long size, realsize, memmap_pages;
Christoph Lameterb69408e2008-10-18 20:26:14 -07003439 enum lru_list l;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003440
Mel Gormanc7132162006-09-27 01:49:43 -07003441 size = zone_spanned_pages_in_node(nid, j, zones_size);
3442 realsize = size - zone_absent_pages_in_node(nid, j,
3443 zholes_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003444
Mel Gorman0e0b8642006-09-27 01:49:56 -07003445 /*
3446 * Adjust realsize so that it accounts for how much memory
3447 * is used by this zone for memmap. This affects the watermark
3448 * and per-cpu initialisations
3449 */
Johannes Weinerf7232152008-05-23 13:04:21 -07003450 memmap_pages =
3451 PAGE_ALIGN(size * sizeof(struct page)) >> PAGE_SHIFT;
Mel Gorman0e0b8642006-09-27 01:49:56 -07003452 if (realsize >= memmap_pages) {
3453 realsize -= memmap_pages;
Yinghai Lud903ef92008-10-18 20:27:06 -07003454 printk(KERN_DEBUG
3455 " %s zone: %lu pages used for memmap\n",
Mel Gorman0e0b8642006-09-27 01:49:56 -07003456 zone_names[j], memmap_pages);
3457 } else
3458 printk(KERN_WARNING
3459 " %s zone: %lu pages exceeds realsize %lu\n",
3460 zone_names[j], memmap_pages, realsize);
3461
Christoph Lameter62672762007-02-10 01:43:07 -08003462 /* Account for reserved pages */
3463 if (j == 0 && realsize > dma_reserve) {
Mel Gorman0e0b8642006-09-27 01:49:56 -07003464 realsize -= dma_reserve;
Yinghai Lud903ef92008-10-18 20:27:06 -07003465 printk(KERN_DEBUG " %s zone: %lu pages reserved\n",
Christoph Lameter62672762007-02-10 01:43:07 -08003466 zone_names[0], dma_reserve);
Mel Gorman0e0b8642006-09-27 01:49:56 -07003467 }
3468
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07003469 if (!is_highmem_idx(j))
Linus Torvalds1da177e2005-04-16 15:20:36 -07003470 nr_kernel_pages += realsize;
3471 nr_all_pages += realsize;
3472
3473 zone->spanned_pages = size;
3474 zone->present_pages = realsize;
Christoph Lameter96146342006-07-03 00:24:13 -07003475#ifdef CONFIG_NUMA
Christoph Lameterd5f541e2006-09-27 01:50:08 -07003476 zone->node = nid;
Christoph Lameter8417bba2006-09-25 23:31:51 -07003477 zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
Christoph Lameter96146342006-07-03 00:24:13 -07003478 / 100;
Christoph Lameter0ff38492006-09-25 23:31:52 -07003479 zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
Christoph Lameter96146342006-07-03 00:24:13 -07003480#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07003481 zone->name = zone_names[j];
3482 spin_lock_init(&zone->lock);
3483 spin_lock_init(&zone->lru_lock);
Dave Hansenbdc8cb92005-10-29 18:16:53 -07003484 zone_seqlock_init(zone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003485 zone->zone_pgdat = pgdat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003486
Martin Bligh3bb1a852006-10-28 10:38:24 -07003487 zone->prev_priority = DEF_PRIORITY;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003488
Dave Hansened8ece22005-10-29 18:16:50 -07003489 zone_pcp_init(zone);
Christoph Lameterb69408e2008-10-18 20:26:14 -07003490 for_each_lru(l) {
3491 INIT_LIST_HEAD(&zone->lru[l].list);
3492 zone->lru[l].nr_scan = 0;
3493 }
Rik van Riel4f98a2f2008-10-18 20:26:32 -07003494 zone->recent_rotated[0] = 0;
3495 zone->recent_rotated[1] = 0;
3496 zone->recent_scanned[0] = 0;
3497 zone->recent_scanned[1] = 0;
Christoph Lameter2244b952006-06-30 01:55:33 -07003498 zap_zone_vm_stats(zone);
David Rientjese815af92007-10-16 23:25:54 -07003499 zone->flags = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003500 if (!size)
3501 continue;
3502
Mel Gormanba72cb82007-11-28 16:21:13 -08003503 set_pageblock_order(pageblock_default_order());
Mel Gorman835c1342007-10-16 01:25:47 -07003504 setup_usemap(pgdat, zone, size);
Dave Hansena2f3aa02007-01-10 23:15:30 -08003505 ret = init_currently_empty_zone(zone, zone_start_pfn,
3506 size, MEMMAP_EARLY);
Yasunori Goto718127c2006-06-23 02:03:10 -07003507 BUG_ON(ret);
Heiko Carstens76cdd582008-05-14 16:05:52 -07003508 memmap_init(size, nid, j, zone_start_pfn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003509 zone_start_pfn += size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003510 }
3511}
3512
Sam Ravnborg577a32f2007-05-17 23:29:25 +02003513static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003514{
Linus Torvalds1da177e2005-04-16 15:20:36 -07003515 /* Skip empty nodes */
3516 if (!pgdat->node_spanned_pages)
3517 return;
3518
Andy Whitcroftd41dee32005-06-23 00:07:54 -07003519#ifdef CONFIG_FLAT_NODE_MEM_MAP
Linus Torvalds1da177e2005-04-16 15:20:36 -07003520 /* ia64 gets its own node_mem_map, before this, without bootmem */
3521 if (!pgdat->node_mem_map) {
Bob Piccoe984bb42006-05-20 15:00:31 -07003522 unsigned long size, start, end;
Andy Whitcroftd41dee32005-06-23 00:07:54 -07003523 struct page *map;
3524
Bob Piccoe984bb42006-05-20 15:00:31 -07003525 /*
3526 * The zone's endpoints aren't required to be MAX_ORDER
3527 * aligned but the node_mem_map endpoints must be in order
3528 * for the buddy allocator to function correctly.
3529 */
3530 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
3531 end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
3532 end = ALIGN(end, MAX_ORDER_NR_PAGES);
3533 size = (end - start) * sizeof(struct page);
Dave Hansen6f167ec2005-06-23 00:07:39 -07003534 map = alloc_remap(pgdat->node_id, size);
3535 if (!map)
3536 map = alloc_bootmem_node(pgdat, size);
Bob Piccoe984bb42006-05-20 15:00:31 -07003537 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003538 }
Roman Zippel12d810c2007-05-31 00:40:54 -07003539#ifndef CONFIG_NEED_MULTIPLE_NODES
Linus Torvalds1da177e2005-04-16 15:20:36 -07003540 /*
3541 * With no DISCONTIG, the global mem_map is just set as node 0's
3542 */
Mel Gormanc7132162006-09-27 01:49:43 -07003543 if (pgdat == NODE_DATA(0)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07003544 mem_map = NODE_DATA(0)->node_mem_map;
Mel Gormanc7132162006-09-27 01:49:43 -07003545#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
3546 if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
Thomas Bogendoerfer467bc462008-01-08 15:33:11 -08003547 mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);
Mel Gormanc7132162006-09-27 01:49:43 -07003548#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
3549 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07003550#endif
Andy Whitcroftd41dee32005-06-23 00:07:54 -07003551#endif /* CONFIG_FLAT_NODE_MEM_MAP */
Linus Torvalds1da177e2005-04-16 15:20:36 -07003552}
3553
Johannes Weiner9109fb72008-07-23 21:27:20 -07003554void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
3555 unsigned long node_start_pfn, unsigned long *zholes_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003556{
Johannes Weiner9109fb72008-07-23 21:27:20 -07003557 pg_data_t *pgdat = NODE_DATA(nid);
3558
Linus Torvalds1da177e2005-04-16 15:20:36 -07003559 pgdat->node_id = nid;
3560 pgdat->node_start_pfn = node_start_pfn;
Mel Gormanc7132162006-09-27 01:49:43 -07003561 calculate_node_totalpages(pgdat, zones_size, zholes_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003562
3563 alloc_node_mem_map(pgdat);
Yinghai Lue8c27ac2008-06-01 13:15:22 -07003564#ifdef CONFIG_FLAT_NODE_MEM_MAP
3565 printk(KERN_DEBUG "free_area_init_node: node %d, pgdat %08lx, node_mem_map %08lx\n",
3566 nid, (unsigned long)pgdat,
3567 (unsigned long)pgdat->node_mem_map);
3568#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07003569
3570 free_area_init_core(pgdat, zones_size, zholes_size);
3571}
3572
Mel Gormanc7132162006-09-27 01:49:43 -07003573#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
Miklos Szeredi418508c2007-05-23 13:57:55 -07003574
3575#if MAX_NUMNODES > 1
3576/*
3577 * Figure out the number of possible node ids.
3578 */
3579static void __init setup_nr_node_ids(void)
3580{
3581 unsigned int node;
3582 unsigned int highest = 0;
3583
3584 for_each_node_mask(node, node_possible_map)
3585 highest = node;
3586 nr_node_ids = highest + 1;
3587}
3588#else
3589static inline void setup_nr_node_ids(void)
3590{
3591}
3592#endif
3593
Mel Gormanc7132162006-09-27 01:49:43 -07003594/**
3595 * add_active_range - Register a range of PFNs backed by physical memory
3596 * @nid: The node ID the range resides on
3597 * @start_pfn: The start PFN of the available physical memory
3598 * @end_pfn: The end PFN of the available physical memory
3599 *
3600 * These ranges are stored in an early_node_map[] and later used by
3601 * free_area_init_nodes() to calculate zone sizes and holes. If the
3602 * range spans a memory hole, it is up to the architecture to ensure
3603 * the memory is not freed by the bootmem allocator. If possible
3604 * the range being registered will be merged with existing ranges.
3605 */
3606void __init add_active_range(unsigned int nid, unsigned long start_pfn,
3607 unsigned long end_pfn)
3608{
3609 int i;
3610
Mel Gorman6b74ab92008-07-23 21:26:49 -07003611 mminit_dprintk(MMINIT_TRACE, "memory_register",
3612 "Entering add_active_range(%d, %#lx, %#lx) "
3613 "%d entries of %d used\n",
3614 nid, start_pfn, end_pfn,
3615 nr_nodemap_entries, MAX_ACTIVE_REGIONS);
Mel Gormanc7132162006-09-27 01:49:43 -07003616
Mel Gorman2dbb51c2008-07-23 21:26:52 -07003617 mminit_validate_memmodel_limits(&start_pfn, &end_pfn);
3618
Mel Gormanc7132162006-09-27 01:49:43 -07003619 /* Merge with existing active regions if possible */
3620 for (i = 0; i < nr_nodemap_entries; i++) {
3621 if (early_node_map[i].nid != nid)
3622 continue;
3623
3624 /* Skip if an existing region covers this new one */
3625 if (start_pfn >= early_node_map[i].start_pfn &&
3626 end_pfn <= early_node_map[i].end_pfn)
3627 return;
3628
3629 /* Merge forward if suitable */
3630 if (start_pfn <= early_node_map[i].end_pfn &&
3631 end_pfn > early_node_map[i].end_pfn) {
3632 early_node_map[i].end_pfn = end_pfn;
3633 return;
3634 }
3635
3636 /* Merge backward if suitable */
3637 if (start_pfn < early_node_map[i].end_pfn &&
3638 end_pfn >= early_node_map[i].start_pfn) {
3639 early_node_map[i].start_pfn = start_pfn;
3640 return;
3641 }
3642 }
3643
3644 /* Check that early_node_map is large enough */
3645 if (i >= MAX_ACTIVE_REGIONS) {
3646 printk(KERN_CRIT "More than %d memory regions, truncating\n",
3647 MAX_ACTIVE_REGIONS);
3648 return;
3649 }
3650
3651 early_node_map[i].nid = nid;
3652 early_node_map[i].start_pfn = start_pfn;
3653 early_node_map[i].end_pfn = end_pfn;
3654 nr_nodemap_entries = i + 1;
3655}
3656
3657/**
Yinghai Lucc1050b2008-06-13 19:08:52 -07003658 * remove_active_range - Shrink an existing registered range of PFNs
Mel Gormanc7132162006-09-27 01:49:43 -07003659 * @nid: The node id the range is on that should be shrunk
Yinghai Lucc1050b2008-06-13 19:08:52 -07003660 * @start_pfn: The new PFN of the range
3661 * @end_pfn: The new PFN of the range
Mel Gormanc7132162006-09-27 01:49:43 -07003662 *
3663 * i386 with NUMA use alloc_remap() to store a node_mem_map on a local node.
Yinghai Lucc1a9d82008-06-08 19:39:16 -07003664 * The map is kept near the end physical page range that has already been
3665 * registered. This function allows an arch to shrink an existing registered
3666 * range.
Mel Gormanc7132162006-09-27 01:49:43 -07003667 */
Yinghai Lucc1050b2008-06-13 19:08:52 -07003668void __init remove_active_range(unsigned int nid, unsigned long start_pfn,
3669 unsigned long end_pfn)
Mel Gormanc7132162006-09-27 01:49:43 -07003670{
Yinghai Lucc1a9d82008-06-08 19:39:16 -07003671 int i, j;
3672 int removed = 0;
Mel Gormanc7132162006-09-27 01:49:43 -07003673
Yinghai Lucc1050b2008-06-13 19:08:52 -07003674 printk(KERN_DEBUG "remove_active_range (%d, %lu, %lu)\n",
3675 nid, start_pfn, end_pfn);
3676
Mel Gormanc7132162006-09-27 01:49:43 -07003677 /* Find the old active region end and shrink */
Yinghai Lucc1a9d82008-06-08 19:39:16 -07003678 for_each_active_range_index_in_nid(i, nid) {
Yinghai Lucc1050b2008-06-13 19:08:52 -07003679 if (early_node_map[i].start_pfn >= start_pfn &&
3680 early_node_map[i].end_pfn <= end_pfn) {
Yinghai Lucc1a9d82008-06-08 19:39:16 -07003681 /* clear it */
Yinghai Lucc1050b2008-06-13 19:08:52 -07003682 early_node_map[i].start_pfn = 0;
Yinghai Lucc1a9d82008-06-08 19:39:16 -07003683 early_node_map[i].end_pfn = 0;
3684 removed = 1;
3685 continue;
Mel Gormanc7132162006-09-27 01:49:43 -07003686 }
Yinghai Lucc1050b2008-06-13 19:08:52 -07003687 if (early_node_map[i].start_pfn < start_pfn &&
3688 early_node_map[i].end_pfn > start_pfn) {
3689 unsigned long temp_end_pfn = early_node_map[i].end_pfn;
3690 early_node_map[i].end_pfn = start_pfn;
3691 if (temp_end_pfn > end_pfn)
3692 add_active_range(nid, end_pfn, temp_end_pfn);
3693 continue;
3694 }
3695 if (early_node_map[i].start_pfn >= start_pfn &&
3696 early_node_map[i].end_pfn > end_pfn &&
3697 early_node_map[i].start_pfn < end_pfn) {
3698 early_node_map[i].start_pfn = end_pfn;
Yinghai Lucc1a9d82008-06-08 19:39:16 -07003699 continue;
3700 }
3701 }
3702
3703 if (!removed)
3704 return;
3705
3706 /* remove the blank ones */
3707 for (i = nr_nodemap_entries - 1; i > 0; i--) {
3708 if (early_node_map[i].nid != nid)
3709 continue;
3710 if (early_node_map[i].end_pfn)
3711 continue;
3712 /* we found it, get rid of it */
3713 for (j = i; j < nr_nodemap_entries - 1; j++)
3714 memcpy(&early_node_map[j], &early_node_map[j+1],
3715 sizeof(early_node_map[j]));
3716 j = nr_nodemap_entries - 1;
3717 memset(&early_node_map[j], 0, sizeof(early_node_map[j]));
3718 nr_nodemap_entries--;
3719 }
Mel Gormanc7132162006-09-27 01:49:43 -07003720}
3721
3722/**
3723 * remove_all_active_ranges - Remove all currently registered regions
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003724 *
Mel Gormanc7132162006-09-27 01:49:43 -07003725 * During discovery, it may be found that a table like SRAT is invalid
3726 * and an alternative discovery method must be used. This function removes
3727 * all currently registered regions.
3728 */
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003729void __init remove_all_active_ranges(void)
Mel Gormanc7132162006-09-27 01:49:43 -07003730{
3731 memset(early_node_map, 0, sizeof(early_node_map));
3732 nr_nodemap_entries = 0;
Mel Gormanfb014392006-09-27 01:49:59 -07003733#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
3734 memset(node_boundary_start_pfn, 0, sizeof(node_boundary_start_pfn));
3735 memset(node_boundary_end_pfn, 0, sizeof(node_boundary_end_pfn));
3736#endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
Mel Gormanc7132162006-09-27 01:49:43 -07003737}
3738
3739/* Compare two active node_active_regions */
3740static int __init cmp_node_active_region(const void *a, const void *b)
3741{
3742 struct node_active_region *arange = (struct node_active_region *)a;
3743 struct node_active_region *brange = (struct node_active_region *)b;
3744
3745 /* Done this way to avoid overflows */
3746 if (arange->start_pfn > brange->start_pfn)
3747 return 1;
3748 if (arange->start_pfn < brange->start_pfn)
3749 return -1;
3750
3751 return 0;
3752}
3753
3754/* sort the node_map by start_pfn */
3755static void __init sort_node_map(void)
3756{
3757 sort(early_node_map, (size_t)nr_nodemap_entries,
3758 sizeof(struct node_active_region),
3759 cmp_node_active_region, NULL);
3760}
3761
Mel Gormana6af2bc2007-02-10 01:42:57 -08003762/* Find the lowest pfn for a node */
Adrian Bunkb69a7282008-07-23 21:28:12 -07003763static unsigned long __init find_min_pfn_for_node(int nid)
Mel Gormanc7132162006-09-27 01:49:43 -07003764{
3765 int i;
Mel Gormana6af2bc2007-02-10 01:42:57 -08003766 unsigned long min_pfn = ULONG_MAX;
Mel Gorman1abbfb42006-11-23 12:01:41 +00003767
Mel Gormanc7132162006-09-27 01:49:43 -07003768 /* Assuming a sorted map, the first range found has the starting pfn */
3769 for_each_active_range_index_in_nid(i, nid)
Mel Gormana6af2bc2007-02-10 01:42:57 -08003770 min_pfn = min(min_pfn, early_node_map[i].start_pfn);
Mel Gormanc7132162006-09-27 01:49:43 -07003771
Mel Gormana6af2bc2007-02-10 01:42:57 -08003772 if (min_pfn == ULONG_MAX) {
3773 printk(KERN_WARNING
Paul Jackson2bc0d262008-06-22 07:22:17 -07003774 "Could not find start_pfn for node %d\n", nid);
Mel Gormana6af2bc2007-02-10 01:42:57 -08003775 return 0;
3776 }
3777
3778 return min_pfn;
Mel Gormanc7132162006-09-27 01:49:43 -07003779}
3780
3781/**
3782 * find_min_pfn_with_active_regions - Find the minimum PFN registered
3783 *
3784 * It returns the minimum PFN based on information provided via
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003785 * add_active_range().
Mel Gormanc7132162006-09-27 01:49:43 -07003786 */
3787unsigned long __init find_min_pfn_with_active_regions(void)
3788{
3789 return find_min_pfn_for_node(MAX_NUMNODES);
3790}
3791
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07003792/*
3793 * early_calculate_totalpages()
3794 * Sum pages in active regions for movable zone.
3795 * Populate N_HIGH_MEMORY for calculating usable_nodes.
3796 */
Adrian Bunk484f51f2007-10-16 01:26:03 -07003797static unsigned long __init early_calculate_totalpages(void)
Mel Gorman7e63efe2007-07-17 04:03:15 -07003798{
3799 int i;
3800 unsigned long totalpages = 0;
3801
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07003802 for (i = 0; i < nr_nodemap_entries; i++) {
3803 unsigned long pages = early_node_map[i].end_pfn -
Mel Gorman7e63efe2007-07-17 04:03:15 -07003804 early_node_map[i].start_pfn;
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07003805 totalpages += pages;
3806 if (pages)
3807 node_set_state(early_node_map[i].nid, N_HIGH_MEMORY);
3808 }
3809 return totalpages;
Mel Gorman7e63efe2007-07-17 04:03:15 -07003810}
3811
Mel Gorman2a1e2742007-07-17 04:03:12 -07003812/*
3813 * Find the PFN the Movable zone begins in each node. Kernel memory
3814 * is spread evenly between nodes as long as the nodes have enough
3815 * memory. When they don't, some nodes will have more kernelcore than
3816 * others
3817 */
Adrian Bunkb69a7282008-07-23 21:28:12 -07003818static void __init find_zone_movable_pfns_for_nodes(unsigned long *movable_pfn)
Mel Gorman2a1e2742007-07-17 04:03:12 -07003819{
3820 int i, nid;
3821 unsigned long usable_startpfn;
3822 unsigned long kernelcore_node, kernelcore_remaining;
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07003823 unsigned long totalpages = early_calculate_totalpages();
3824 int usable_nodes = nodes_weight(node_states[N_HIGH_MEMORY]);
Mel Gorman2a1e2742007-07-17 04:03:12 -07003825
Mel Gorman7e63efe2007-07-17 04:03:15 -07003826 /*
3827 * If movablecore was specified, calculate what size of
3828 * kernelcore that corresponds so that memory usable for
3829 * any allocation type is evenly spread. If both kernelcore
3830 * and movablecore are specified, then the value of kernelcore
3831 * will be used for required_kernelcore if it's greater than
3832 * what movablecore would have allowed.
3833 */
3834 if (required_movablecore) {
Mel Gorman7e63efe2007-07-17 04:03:15 -07003835 unsigned long corepages;
3836
3837 /*
3838 * Round-up so that ZONE_MOVABLE is at least as large as what
3839 * was requested by the user
3840 */
3841 required_movablecore =
3842 roundup(required_movablecore, MAX_ORDER_NR_PAGES);
3843 corepages = totalpages - required_movablecore;
3844
3845 required_kernelcore = max(required_kernelcore, corepages);
3846 }
3847
Mel Gorman2a1e2742007-07-17 04:03:12 -07003848 /* If kernelcore was not specified, there is no ZONE_MOVABLE */
3849 if (!required_kernelcore)
3850 return;
3851
3852 /* usable_startpfn is the lowest possible pfn ZONE_MOVABLE can be at */
3853 find_usable_zone_for_movable();
3854 usable_startpfn = arch_zone_lowest_possible_pfn[movable_zone];
3855
3856restart:
3857 /* Spread kernelcore memory as evenly as possible throughout nodes */
3858 kernelcore_node = required_kernelcore / usable_nodes;
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07003859 for_each_node_state(nid, N_HIGH_MEMORY) {
Mel Gorman2a1e2742007-07-17 04:03:12 -07003860 /*
3861 * Recalculate kernelcore_node if the division per node
3862 * now exceeds what is necessary to satisfy the requested
3863 * amount of memory for the kernel
3864 */
3865 if (required_kernelcore < kernelcore_node)
3866 kernelcore_node = required_kernelcore / usable_nodes;
3867
3868 /*
3869 * As the map is walked, we track how much memory is usable
3870 * by the kernel using kernelcore_remaining. When it is
3871 * 0, the rest of the node is usable by ZONE_MOVABLE
3872 */
3873 kernelcore_remaining = kernelcore_node;
3874
3875 /* Go through each range of PFNs within this node */
3876 for_each_active_range_index_in_nid(i, nid) {
3877 unsigned long start_pfn, end_pfn;
3878 unsigned long size_pages;
3879
3880 start_pfn = max(early_node_map[i].start_pfn,
3881 zone_movable_pfn[nid]);
3882 end_pfn = early_node_map[i].end_pfn;
3883 if (start_pfn >= end_pfn)
3884 continue;
3885
3886 /* Account for what is only usable for kernelcore */
3887 if (start_pfn < usable_startpfn) {
3888 unsigned long kernel_pages;
3889 kernel_pages = min(end_pfn, usable_startpfn)
3890 - start_pfn;
3891
3892 kernelcore_remaining -= min(kernel_pages,
3893 kernelcore_remaining);
3894 required_kernelcore -= min(kernel_pages,
3895 required_kernelcore);
3896
3897 /* Continue if range is now fully accounted */
3898 if (end_pfn <= usable_startpfn) {
3899
3900 /*
3901 * Push zone_movable_pfn to the end so
3902 * that if we have to rebalance
3903 * kernelcore across nodes, we will
3904 * not double account here
3905 */
3906 zone_movable_pfn[nid] = end_pfn;
3907 continue;
3908 }
3909 start_pfn = usable_startpfn;
3910 }
3911
3912 /*
3913 * The usable PFN range for ZONE_MOVABLE is from
3914 * start_pfn->end_pfn. Calculate size_pages as the
3915 * number of pages used as kernelcore
3916 */
3917 size_pages = end_pfn - start_pfn;
3918 if (size_pages > kernelcore_remaining)
3919 size_pages = kernelcore_remaining;
3920 zone_movable_pfn[nid] = start_pfn + size_pages;
3921
3922 /*
3923 * Some kernelcore has been met, update counts and
3924 * break if the kernelcore for this node has been
3925 * satisified
3926 */
3927 required_kernelcore -= min(required_kernelcore,
3928 size_pages);
3929 kernelcore_remaining -= size_pages;
3930 if (!kernelcore_remaining)
3931 break;
3932 }
3933 }
3934
3935 /*
3936 * If there is still required_kernelcore, we do another pass with one
3937 * less node in the count. This will push zone_movable_pfn[nid] further
3938 * along on the nodes that still have memory until kernelcore is
3939 * satisified
3940 */
3941 usable_nodes--;
3942 if (usable_nodes && required_kernelcore > usable_nodes)
3943 goto restart;
3944
3945 /* Align start of ZONE_MOVABLE on all nids to MAX_ORDER_NR_PAGES */
3946 for (nid = 0; nid < MAX_NUMNODES; nid++)
3947 zone_movable_pfn[nid] =
3948 roundup(zone_movable_pfn[nid], MAX_ORDER_NR_PAGES);
3949}
3950
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07003951/* Any regular memory on that node ? */
3952static void check_for_regular_memory(pg_data_t *pgdat)
3953{
3954#ifdef CONFIG_HIGHMEM
3955 enum zone_type zone_type;
3956
3957 for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {
3958 struct zone *zone = &pgdat->node_zones[zone_type];
3959 if (zone->present_pages)
3960 node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);
3961 }
3962#endif
3963}
3964
Mel Gormanc7132162006-09-27 01:49:43 -07003965/**
3966 * free_area_init_nodes - Initialise all pg_data_t and zone data
Randy Dunlap88ca3b92006-10-04 02:15:25 -07003967 * @max_zone_pfn: an array of max PFNs for each zone
Mel Gormanc7132162006-09-27 01:49:43 -07003968 *
3969 * This will call free_area_init_node() for each active node in the system.
3970 * Using the page ranges provided by add_active_range(), the size of each
3971 * zone in each node and their holes is calculated. If the maximum PFN
3972 * between two adjacent zones match, it is assumed that the zone is empty.
3973 * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
3974 * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
3975 * starts where the previous one ended. For example, ZONE_DMA32 starts
3976 * at arch_max_dma_pfn.
3977 */
3978void __init free_area_init_nodes(unsigned long *max_zone_pfn)
3979{
3980 unsigned long nid;
Andrew Mortondb991002008-10-15 22:01:07 -07003981 int i;
Mel Gormanc7132162006-09-27 01:49:43 -07003982
Mel Gormana6af2bc2007-02-10 01:42:57 -08003983 /* Sort early_node_map as initialisation assumes it is sorted */
3984 sort_node_map();
3985
Mel Gormanc7132162006-09-27 01:49:43 -07003986 /* Record where the zone boundaries are */
3987 memset(arch_zone_lowest_possible_pfn, 0,
3988 sizeof(arch_zone_lowest_possible_pfn));
3989 memset(arch_zone_highest_possible_pfn, 0,
3990 sizeof(arch_zone_highest_possible_pfn));
3991 arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
3992 arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
3993 for (i = 1; i < MAX_NR_ZONES; i++) {
Mel Gorman2a1e2742007-07-17 04:03:12 -07003994 if (i == ZONE_MOVABLE)
3995 continue;
Mel Gormanc7132162006-09-27 01:49:43 -07003996 arch_zone_lowest_possible_pfn[i] =
3997 arch_zone_highest_possible_pfn[i-1];
3998 arch_zone_highest_possible_pfn[i] =
3999 max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
4000 }
Mel Gorman2a1e2742007-07-17 04:03:12 -07004001 arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
4002 arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;
4003
4004 /* Find the PFNs that ZONE_MOVABLE begins at in each node */
4005 memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
4006 find_zone_movable_pfns_for_nodes(zone_movable_pfn);
Mel Gormanc7132162006-09-27 01:49:43 -07004007
Mel Gormanc7132162006-09-27 01:49:43 -07004008 /* Print out the zone ranges */
4009 printk("Zone PFN ranges:\n");
Mel Gorman2a1e2742007-07-17 04:03:12 -07004010 for (i = 0; i < MAX_NR_ZONES; i++) {
4011 if (i == ZONE_MOVABLE)
4012 continue;
Paul Jackson5dab8ec2008-06-25 05:44:40 -07004013 printk(" %-8s %0#10lx -> %0#10lx\n",
Mel Gormanc7132162006-09-27 01:49:43 -07004014 zone_names[i],
4015 arch_zone_lowest_possible_pfn[i],
4016 arch_zone_highest_possible_pfn[i]);
Mel Gorman2a1e2742007-07-17 04:03:12 -07004017 }
4018
4019 /* Print out the PFNs ZONE_MOVABLE begins at in each node */
4020 printk("Movable zone start PFN for each node\n");
4021 for (i = 0; i < MAX_NUMNODES; i++) {
4022 if (zone_movable_pfn[i])
4023 printk(" Node %d: %lu\n", i, zone_movable_pfn[i]);
4024 }
Mel Gormanc7132162006-09-27 01:49:43 -07004025
4026 /* Print out the early_node_map[] */
4027 printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
4028 for (i = 0; i < nr_nodemap_entries; i++)
Paul Jackson5dab8ec2008-06-25 05:44:40 -07004029 printk(" %3d: %0#10lx -> %0#10lx\n", early_node_map[i].nid,
Mel Gormanc7132162006-09-27 01:49:43 -07004030 early_node_map[i].start_pfn,
4031 early_node_map[i].end_pfn);
4032
4033 /* Initialise every node */
Mel Gorman708614e2008-07-23 21:26:51 -07004034 mminit_verify_pageflags_layout();
Christoph Lameter8ef82862007-02-20 13:57:52 -08004035 setup_nr_node_ids();
Mel Gormanc7132162006-09-27 01:49:43 -07004036 for_each_online_node(nid) {
4037 pg_data_t *pgdat = NODE_DATA(nid);
Johannes Weiner9109fb72008-07-23 21:27:20 -07004038 free_area_init_node(nid, NULL,
Mel Gormanc7132162006-09-27 01:49:43 -07004039 find_min_pfn_for_node(nid), NULL);
Lee Schermerhorn37b07e42007-10-16 01:25:39 -07004040
4041 /* Any memory on that node */
4042 if (pgdat->node_present_pages)
4043 node_set_state(nid, N_HIGH_MEMORY);
4044 check_for_regular_memory(pgdat);
Mel Gormanc7132162006-09-27 01:49:43 -07004045 }
4046}
Mel Gorman2a1e2742007-07-17 04:03:12 -07004047
Mel Gorman7e63efe2007-07-17 04:03:15 -07004048static int __init cmdline_parse_core(char *p, unsigned long *core)
Mel Gorman2a1e2742007-07-17 04:03:12 -07004049{
4050 unsigned long long coremem;
4051 if (!p)
4052 return -EINVAL;
4053
4054 coremem = memparse(p, &p);
Mel Gorman7e63efe2007-07-17 04:03:15 -07004055 *core = coremem >> PAGE_SHIFT;
Mel Gorman2a1e2742007-07-17 04:03:12 -07004056
Mel Gorman7e63efe2007-07-17 04:03:15 -07004057 /* Paranoid check that UL is enough for the coremem value */
Mel Gorman2a1e2742007-07-17 04:03:12 -07004058 WARN_ON((coremem >> PAGE_SHIFT) > ULONG_MAX);
4059
4060 return 0;
4061}
Mel Gormaned7ed362007-07-17 04:03:14 -07004062
Mel Gorman7e63efe2007-07-17 04:03:15 -07004063/*
4064 * kernelcore=size sets the amount of memory for use for allocations that
4065 * cannot be reclaimed or migrated.
4066 */
4067static int __init cmdline_parse_kernelcore(char *p)
4068{
4069 return cmdline_parse_core(p, &required_kernelcore);
4070}
4071
4072/*
4073 * movablecore=size sets the amount of memory for use for allocations that
4074 * can be reclaimed or migrated.
4075 */
4076static int __init cmdline_parse_movablecore(char *p)
4077{
4078 return cmdline_parse_core(p, &required_movablecore);
4079}
4080
Mel Gormaned7ed362007-07-17 04:03:14 -07004081early_param("kernelcore", cmdline_parse_kernelcore);
Mel Gorman7e63efe2007-07-17 04:03:15 -07004082early_param("movablecore", cmdline_parse_movablecore);
Mel Gormaned7ed362007-07-17 04:03:14 -07004083
Mel Gormanc7132162006-09-27 01:49:43 -07004084#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
4085
Mel Gorman0e0b8642006-09-27 01:49:56 -07004086/**
Randy Dunlap88ca3b92006-10-04 02:15:25 -07004087 * set_dma_reserve - set the specified number of pages reserved in the first zone
4088 * @new_dma_reserve: The number of pages to mark reserved
Mel Gorman0e0b8642006-09-27 01:49:56 -07004089 *
4090 * The per-cpu batchsize and zone watermarks are determined by present_pages.
4091 * In the DMA zone, a significant percentage may be consumed by kernel image
4092 * and other unfreeable allocations which can skew the watermarks badly. This
Randy Dunlap88ca3b92006-10-04 02:15:25 -07004093 * function may optionally be used to account for unfreeable pages in the
4094 * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
4095 * smaller per-cpu batchsize.
Mel Gorman0e0b8642006-09-27 01:49:56 -07004096 */
4097void __init set_dma_reserve(unsigned long new_dma_reserve)
4098{
4099 dma_reserve = new_dma_reserve;
4100}
4101
Dave Hansen93b75042005-06-23 00:07:47 -07004102#ifndef CONFIG_NEED_MULTIPLE_NODES
Marcin Slusarz52765582008-09-02 14:35:41 -07004103struct pglist_data __refdata contig_page_data = { .bdata = &bootmem_node_data[0] };
Linus Torvalds1da177e2005-04-16 15:20:36 -07004104EXPORT_SYMBOL(contig_page_data);
Dave Hansen93b75042005-06-23 00:07:47 -07004105#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07004106
4107void __init free_area_init(unsigned long *zones_size)
4108{
Johannes Weiner9109fb72008-07-23 21:27:20 -07004109 free_area_init_node(0, zones_size,
Linus Torvalds1da177e2005-04-16 15:20:36 -07004110 __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
4111}
Linus Torvalds1da177e2005-04-16 15:20:36 -07004112
Linus Torvalds1da177e2005-04-16 15:20:36 -07004113static int page_alloc_cpu_notify(struct notifier_block *self,
4114 unsigned long action, void *hcpu)
4115{
4116 int cpu = (unsigned long)hcpu;
Linus Torvalds1da177e2005-04-16 15:20:36 -07004117
Rafael J. Wysocki8bb78442007-05-09 02:35:10 -07004118 if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
Christoph Lameter9f8f2172008-02-04 22:29:11 -08004119 drain_pages(cpu);
4120
4121 /*
4122 * Spill the event counters of the dead processor
4123 * into the current processors event counters.
4124 * This artificially elevates the count of the current
4125 * processor.
4126 */
Christoph Lameterf8891e52006-06-30 01:55:45 -07004127 vm_events_fold_cpu(cpu);
Christoph Lameter9f8f2172008-02-04 22:29:11 -08004128
4129 /*
4130 * Zero the differential counters of the dead processor
4131 * so that the vm statistics are consistent.
4132 *
4133 * This is only okay since the processor is dead and cannot
4134 * race with what we are doing.
4135 */
Christoph Lameter2244b952006-06-30 01:55:33 -07004136 refresh_cpu_vm_stats(cpu);
Linus Torvalds1da177e2005-04-16 15:20:36 -07004137 }
4138 return NOTIFY_OK;
4139}
Linus Torvalds1da177e2005-04-16 15:20:36 -07004140
4141void __init page_alloc_init(void)
4142{
4143 hotcpu_notifier(page_alloc_cpu_notify, 0);
4144}
4145
4146/*
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07004147 * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio
4148 * or min_free_kbytes changes.
4149 */
4150static void calculate_totalreserve_pages(void)
4151{
4152 struct pglist_data *pgdat;
4153 unsigned long reserve_pages = 0;
Christoph Lameter2f6726e2006-09-25 23:31:18 -07004154 enum zone_type i, j;
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07004155
4156 for_each_online_pgdat(pgdat) {
4157 for (i = 0; i < MAX_NR_ZONES; i++) {
4158 struct zone *zone = pgdat->node_zones + i;
4159 unsigned long max = 0;
4160
4161 /* Find valid and maximum lowmem_reserve in the zone */
4162 for (j = i; j < MAX_NR_ZONES; j++) {
4163 if (zone->lowmem_reserve[j] > max)
4164 max = zone->lowmem_reserve[j];
4165 }
4166
4167 /* we treat pages_high as reserved pages. */
4168 max += zone->pages_high;
4169
4170 if (max > zone->present_pages)
4171 max = zone->present_pages;
4172 reserve_pages += max;
4173 }
4174 }
4175 totalreserve_pages = reserve_pages;
4176}
4177
4178/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07004179 * setup_per_zone_lowmem_reserve - called whenever
4180 * sysctl_lower_zone_reserve_ratio changes. Ensures that each zone
4181 * has a correct pages reserved value, so an adequate number of
4182 * pages are left in the zone after a successful __alloc_pages().
4183 */
4184static void setup_per_zone_lowmem_reserve(void)
4185{
4186 struct pglist_data *pgdat;
Christoph Lameter2f6726e2006-09-25 23:31:18 -07004187 enum zone_type j, idx;
Linus Torvalds1da177e2005-04-16 15:20:36 -07004188
KAMEZAWA Hiroyukiec936fc2006-03-27 01:15:59 -08004189 for_each_online_pgdat(pgdat) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07004190 for (j = 0; j < MAX_NR_ZONES; j++) {
4191 struct zone *zone = pgdat->node_zones + j;
4192 unsigned long present_pages = zone->present_pages;
4193
4194 zone->lowmem_reserve[j] = 0;
4195
Christoph Lameter2f6726e2006-09-25 23:31:18 -07004196 idx = j;
4197 while (idx) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07004198 struct zone *lower_zone;
4199
Christoph Lameter2f6726e2006-09-25 23:31:18 -07004200 idx--;
4201
Linus Torvalds1da177e2005-04-16 15:20:36 -07004202 if (sysctl_lowmem_reserve_ratio[idx] < 1)
4203 sysctl_lowmem_reserve_ratio[idx] = 1;
4204
4205 lower_zone = pgdat->node_zones + idx;
4206 lower_zone->lowmem_reserve[j] = present_pages /
4207 sysctl_lowmem_reserve_ratio[idx];
4208 present_pages += lower_zone->present_pages;
4209 }
4210 }
4211 }
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07004212
4213 /* update totalreserve_pages */
4214 calculate_totalreserve_pages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07004215}
4216
Randy Dunlap88ca3b92006-10-04 02:15:25 -07004217/**
4218 * setup_per_zone_pages_min - called when min_free_kbytes changes.
4219 *
4220 * Ensures that the pages_{min,low,high} values for each zone are set correctly
4221 * with respect to min_free_kbytes.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004222 */
Dave Hansen3947be12005-10-29 18:16:54 -07004223void setup_per_zone_pages_min(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07004224{
4225 unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
4226 unsigned long lowmem_pages = 0;
4227 struct zone *zone;
4228 unsigned long flags;
4229
4230 /* Calculate total number of !ZONE_HIGHMEM pages */
4231 for_each_zone(zone) {
4232 if (!is_highmem(zone))
4233 lowmem_pages += zone->present_pages;
4234 }
4235
4236 for_each_zone(zone) {
Andrew Mortonac924c62006-05-15 09:43:59 -07004237 u64 tmp;
4238
Gerald Schaefer1125b4e2008-10-18 20:27:11 -07004239 spin_lock_irqsave(&zone->lock, flags);
Andrew Mortonac924c62006-05-15 09:43:59 -07004240 tmp = (u64)pages_min * zone->present_pages;
4241 do_div(tmp, lowmem_pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -07004242 if (is_highmem(zone)) {
4243 /*
Nick Piggin669ed172005-11-13 16:06:45 -08004244 * __GFP_HIGH and PF_MEMALLOC allocations usually don't
4245 * need highmem pages, so cap pages_min to a small
4246 * value here.
4247 *
4248 * The (pages_high-pages_low) and (pages_low-pages_min)
4249 * deltas controls asynch page reclaim, and so should
4250 * not be capped for highmem.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004251 */
4252 int min_pages;
4253
4254 min_pages = zone->present_pages / 1024;
4255 if (min_pages < SWAP_CLUSTER_MAX)
4256 min_pages = SWAP_CLUSTER_MAX;
4257 if (min_pages > 128)
4258 min_pages = 128;
4259 zone->pages_min = min_pages;
4260 } else {
Nick Piggin669ed172005-11-13 16:06:45 -08004261 /*
4262 * If it's a lowmem zone, reserve a number of pages
Linus Torvalds1da177e2005-04-16 15:20:36 -07004263 * proportionate to the zone's size.
4264 */
Nick Piggin669ed172005-11-13 16:06:45 -08004265 zone->pages_min = tmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07004266 }
4267
Andrew Mortonac924c62006-05-15 09:43:59 -07004268 zone->pages_low = zone->pages_min + (tmp >> 2);
4269 zone->pages_high = zone->pages_min + (tmp >> 1);
Mel Gorman56fd56b2007-10-16 01:25:58 -07004270 setup_zone_migrate_reserve(zone);
Gerald Schaefer1125b4e2008-10-18 20:27:11 -07004271 spin_unlock_irqrestore(&zone->lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07004272 }
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07004273
4274 /* update totalreserve_pages */
4275 calculate_totalreserve_pages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07004276}
4277
Rik van Riel556adec2008-10-18 20:26:34 -07004278/**
4279 * setup_per_zone_inactive_ratio - called when min_free_kbytes changes.
4280 *
4281 * The inactive anon list should be small enough that the VM never has to
4282 * do too much work, but large enough that each inactive page has a chance
4283 * to be referenced again before it is swapped out.
4284 *
4285 * The inactive_anon ratio is the target ratio of ACTIVE_ANON to
4286 * INACTIVE_ANON pages on this zone's LRU, maintained by the
4287 * pageout code. A zone->inactive_ratio of 3 means 3:1 or 25% of
4288 * the anonymous pages are kept on the inactive list.
4289 *
4290 * total target max
4291 * memory ratio inactive anon
4292 * -------------------------------------
4293 * 10MB 1 5MB
4294 * 100MB 1 50MB
4295 * 1GB 3 250MB
4296 * 10GB 10 0.9GB
4297 * 100GB 31 3GB
4298 * 1TB 101 10GB
4299 * 10TB 320 32GB
4300 */
4301void setup_per_zone_inactive_ratio(void)
4302{
4303 struct zone *zone;
4304
4305 for_each_zone(zone) {
4306 unsigned int gb, ratio;
4307
4308 /* Zone size in gigabytes */
4309 gb = zone->present_pages >> (30 - PAGE_SHIFT);
4310 ratio = int_sqrt(10 * gb);
4311 if (!ratio)
4312 ratio = 1;
4313
4314 zone->inactive_ratio = ratio;
4315 }
4316}
4317
Linus Torvalds1da177e2005-04-16 15:20:36 -07004318/*
4319 * Initialise min_free_kbytes.
4320 *
4321 * For small machines we want it small (128k min). For large machines
4322 * we want it large (64MB max). But it is not linear, because network
4323 * bandwidth does not increase linearly with machine size. We use
4324 *
4325 * min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
4326 * min_free_kbytes = sqrt(lowmem_kbytes * 16)
4327 *
4328 * which yields
4329 *
4330 * 16MB: 512k
4331 * 32MB: 724k
4332 * 64MB: 1024k
4333 * 128MB: 1448k
4334 * 256MB: 2048k
4335 * 512MB: 2896k
4336 * 1024MB: 4096k
4337 * 2048MB: 5792k
4338 * 4096MB: 8192k
4339 * 8192MB: 11584k
4340 * 16384MB: 16384k
4341 */
4342static int __init init_per_zone_pages_min(void)
4343{
4344 unsigned long lowmem_kbytes;
4345
4346 lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
4347
4348 min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
4349 if (min_free_kbytes < 128)
4350 min_free_kbytes = 128;
4351 if (min_free_kbytes > 65536)
4352 min_free_kbytes = 65536;
4353 setup_per_zone_pages_min();
4354 setup_per_zone_lowmem_reserve();
Rik van Riel556adec2008-10-18 20:26:34 -07004355 setup_per_zone_inactive_ratio();
Linus Torvalds1da177e2005-04-16 15:20:36 -07004356 return 0;
4357}
4358module_init(init_per_zone_pages_min)
4359
4360/*
4361 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
4362 * that we can call two helper functions whenever min_free_kbytes
4363 * changes.
4364 */
4365int min_free_kbytes_sysctl_handler(ctl_table *table, int write,
4366 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4367{
4368 proc_dointvec(table, write, file, buffer, length, ppos);
Mel Gorman3b1d92c2007-05-06 14:49:30 -07004369 if (write)
4370 setup_per_zone_pages_min();
Linus Torvalds1da177e2005-04-16 15:20:36 -07004371 return 0;
4372}
4373
Christoph Lameter96146342006-07-03 00:24:13 -07004374#ifdef CONFIG_NUMA
4375int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write,
4376 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4377{
4378 struct zone *zone;
4379 int rc;
4380
4381 rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4382 if (rc)
4383 return rc;
4384
4385 for_each_zone(zone)
Christoph Lameter8417bba2006-09-25 23:31:51 -07004386 zone->min_unmapped_pages = (zone->present_pages *
Christoph Lameter96146342006-07-03 00:24:13 -07004387 sysctl_min_unmapped_ratio) / 100;
4388 return 0;
4389}
Christoph Lameter0ff38492006-09-25 23:31:52 -07004390
4391int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write,
4392 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4393{
4394 struct zone *zone;
4395 int rc;
4396
4397 rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4398 if (rc)
4399 return rc;
4400
4401 for_each_zone(zone)
4402 zone->min_slab_pages = (zone->present_pages *
4403 sysctl_min_slab_ratio) / 100;
4404 return 0;
4405}
Christoph Lameter96146342006-07-03 00:24:13 -07004406#endif
4407
Linus Torvalds1da177e2005-04-16 15:20:36 -07004408/*
4409 * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
4410 * proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
4411 * whenever sysctl_lowmem_reserve_ratio changes.
4412 *
4413 * The reserve ratio obviously has absolutely no relation with the
4414 * pages_min watermarks. The lowmem reserve ratio can only make sense
4415 * if in function of the boot time zone sizes.
4416 */
4417int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
4418 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4419{
4420 proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4421 setup_per_zone_lowmem_reserve();
4422 return 0;
4423}
4424
Rohit Seth8ad4b1f2006-01-08 01:00:40 -08004425/*
4426 * percpu_pagelist_fraction - changes the pcp->high for each zone on each
4427 * cpu. It is the fraction of total pages in each zone that a hot per cpu pagelist
4428 * can have before it gets flushed back to buddy allocator.
4429 */
4430
4431int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write,
4432 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
4433{
4434 struct zone *zone;
4435 unsigned int cpu;
4436 int ret;
4437
4438 ret = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
4439 if (!write || (ret == -EINVAL))
4440 return ret;
4441 for_each_zone(zone) {
4442 for_each_online_cpu(cpu) {
4443 unsigned long high;
4444 high = zone->present_pages / percpu_pagelist_fraction;
4445 setup_pagelist_highmark(zone_pcp(zone, cpu), high);
4446 }
4447 }
4448 return 0;
4449}
4450
David S. Millerf034b5d2006-08-24 03:08:07 -07004451int hashdist = HASHDIST_DEFAULT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07004452
4453#ifdef CONFIG_NUMA
4454static int __init set_hashdist(char *str)
4455{
4456 if (!str)
4457 return 0;
4458 hashdist = simple_strtoul(str, &str, 0);
4459 return 1;
4460}
4461__setup("hashdist=", set_hashdist);
4462#endif
4463
4464/*
4465 * allocate a large system hash table from bootmem
4466 * - it is assumed that the hash table must contain an exact power-of-2
4467 * quantity of entries
4468 * - limit is the number of hash buckets, not the total allocation size
4469 */
4470void *__init alloc_large_system_hash(const char *tablename,
4471 unsigned long bucketsize,
4472 unsigned long numentries,
4473 int scale,
4474 int flags,
4475 unsigned int *_hash_shift,
4476 unsigned int *_hash_mask,
4477 unsigned long limit)
4478{
4479 unsigned long long max = limit;
4480 unsigned long log2qty, size;
4481 void *table = NULL;
4482
4483 /* allow the kernel cmdline to have a say */
4484 if (!numentries) {
4485 /* round applicable memory size up to nearest megabyte */
Andrew Morton04903662006-12-06 20:37:33 -08004486 numentries = nr_kernel_pages;
Linus Torvalds1da177e2005-04-16 15:20:36 -07004487 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
4488 numentries >>= 20 - PAGE_SHIFT;
4489 numentries <<= 20 - PAGE_SHIFT;
4490
4491 /* limit to 1 bucket per 2^scale bytes of low memory */
4492 if (scale > PAGE_SHIFT)
4493 numentries >>= (scale - PAGE_SHIFT);
4494 else
4495 numentries <<= (PAGE_SHIFT - scale);
Paul Mundt9ab37b82007-01-05 16:36:30 -08004496
4497 /* Make sure we've got at least a 0-order allocation.. */
4498 if (unlikely((numentries * bucketsize) < PAGE_SIZE))
4499 numentries = PAGE_SIZE / bucketsize;
Linus Torvalds1da177e2005-04-16 15:20:36 -07004500 }
John Hawkes6e692ed2006-03-25 03:08:02 -08004501 numentries = roundup_pow_of_two(numentries);
Linus Torvalds1da177e2005-04-16 15:20:36 -07004502
4503 /* limit allocation size to 1/16 total memory by default */
4504 if (max == 0) {
4505 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
4506 do_div(max, bucketsize);
4507 }
4508
4509 if (numentries > max)
4510 numentries = max;
4511
David Howellsf0d1b0b2006-12-08 02:37:49 -08004512 log2qty = ilog2(numentries);
Linus Torvalds1da177e2005-04-16 15:20:36 -07004513
4514 do {
4515 size = bucketsize << log2qty;
4516 if (flags & HASH_EARLY)
Jan Beulich74768ed2008-08-12 15:08:39 -07004517 table = alloc_bootmem_nopanic(size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07004518 else if (hashdist)
4519 table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
4520 else {
Pavel Machek2309f9e2008-04-28 02:13:35 -07004521 unsigned long order = get_order(size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07004522 table = (void*) __get_free_pages(GFP_ATOMIC, order);
Eric Dumazet1037b832007-07-15 23:38:05 -07004523 /*
4524 * If bucketsize is not a power-of-two, we may free
4525 * some pages at the end of hash table.
4526 */
4527 if (table) {
4528 unsigned long alloc_end = (unsigned long)table +
4529 (PAGE_SIZE << order);
4530 unsigned long used = (unsigned long)table +
4531 PAGE_ALIGN(size);
4532 split_page(virt_to_page(table), order);
4533 while (used < alloc_end) {
4534 free_page(used);
4535 used += PAGE_SIZE;
4536 }
4537 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07004538 }
4539 } while (!table && size > PAGE_SIZE && --log2qty);
4540
4541 if (!table)
4542 panic("Failed to allocate %s hash table\n", tablename);
4543
Dan Alonib49ad482007-07-15 23:38:23 -07004544 printk(KERN_INFO "%s hash table entries: %d (order: %d, %lu bytes)\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -07004545 tablename,
4546 (1U << log2qty),
David Howellsf0d1b0b2006-12-08 02:37:49 -08004547 ilog2(size) - PAGE_SHIFT,
Linus Torvalds1da177e2005-04-16 15:20:36 -07004548 size);
4549
4550 if (_hash_shift)
4551 *_hash_shift = log2qty;
4552 if (_hash_mask)
4553 *_hash_mask = (1 << log2qty) - 1;
4554
4555 return table;
4556}
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08004557
4558#ifdef CONFIG_OUT_OF_LINE_PFN_TO_PAGE
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08004559struct page *pfn_to_page(unsigned long pfn)
4560{
Andy Whitcroft67de6482006-06-23 02:03:12 -07004561 return __pfn_to_page(pfn);
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08004562}
4563unsigned long page_to_pfn(struct page *page)
4564{
Andy Whitcroft67de6482006-06-23 02:03:12 -07004565 return __page_to_pfn(page);
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08004566}
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08004567EXPORT_SYMBOL(pfn_to_page);
4568EXPORT_SYMBOL(page_to_pfn);
4569#endif /* CONFIG_OUT_OF_LINE_PFN_TO_PAGE */
Andrew Morton6220ec72006-10-19 23:29:05 -07004570
Mel Gorman835c1342007-10-16 01:25:47 -07004571/* Return a pointer to the bitmap storing bits affecting a block of pages */
4572static inline unsigned long *get_pageblock_bitmap(struct zone *zone,
4573 unsigned long pfn)
4574{
4575#ifdef CONFIG_SPARSEMEM
4576 return __pfn_to_section(pfn)->pageblock_flags;
4577#else
4578 return zone->pageblock_flags;
4579#endif /* CONFIG_SPARSEMEM */
4580}
Andrew Morton6220ec72006-10-19 23:29:05 -07004581
Mel Gorman835c1342007-10-16 01:25:47 -07004582static inline int pfn_to_bitidx(struct zone *zone, unsigned long pfn)
4583{
4584#ifdef CONFIG_SPARSEMEM
4585 pfn &= (PAGES_PER_SECTION-1);
Mel Gormand9c23402007-10-16 01:26:01 -07004586 return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
Mel Gorman835c1342007-10-16 01:25:47 -07004587#else
4588 pfn = pfn - zone->zone_start_pfn;
Mel Gormand9c23402007-10-16 01:26:01 -07004589 return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
Mel Gorman835c1342007-10-16 01:25:47 -07004590#endif /* CONFIG_SPARSEMEM */
4591}
4592
4593/**
Mel Gormand9c23402007-10-16 01:26:01 -07004594 * get_pageblock_flags_group - Return the requested group of flags for the pageblock_nr_pages block of pages
Mel Gorman835c1342007-10-16 01:25:47 -07004595 * @page: The page within the block of interest
4596 * @start_bitidx: The first bit of interest to retrieve
4597 * @end_bitidx: The last bit of interest
4598 * returns pageblock_bits flags
4599 */
4600unsigned long get_pageblock_flags_group(struct page *page,
4601 int start_bitidx, int end_bitidx)
4602{
4603 struct zone *zone;
4604 unsigned long *bitmap;
4605 unsigned long pfn, bitidx;
4606 unsigned long flags = 0;
4607 unsigned long value = 1;
4608
4609 zone = page_zone(page);
4610 pfn = page_to_pfn(page);
4611 bitmap = get_pageblock_bitmap(zone, pfn);
4612 bitidx = pfn_to_bitidx(zone, pfn);
4613
4614 for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
4615 if (test_bit(bitidx + start_bitidx, bitmap))
4616 flags |= value;
4617
4618 return flags;
4619}
4620
4621/**
Mel Gormand9c23402007-10-16 01:26:01 -07004622 * set_pageblock_flags_group - Set the requested group of flags for a pageblock_nr_pages block of pages
Mel Gorman835c1342007-10-16 01:25:47 -07004623 * @page: The page within the block of interest
4624 * @start_bitidx: The first bit of interest
4625 * @end_bitidx: The last bit of interest
4626 * @flags: The flags to set
4627 */
4628void set_pageblock_flags_group(struct page *page, unsigned long flags,
4629 int start_bitidx, int end_bitidx)
4630{
4631 struct zone *zone;
4632 unsigned long *bitmap;
4633 unsigned long pfn, bitidx;
4634 unsigned long value = 1;
4635
4636 zone = page_zone(page);
4637 pfn = page_to_pfn(page);
4638 bitmap = get_pageblock_bitmap(zone, pfn);
4639 bitidx = pfn_to_bitidx(zone, pfn);
KAMEZAWA Hiroyuki86051ca2008-04-29 00:58:21 -07004640 VM_BUG_ON(pfn < zone->zone_start_pfn);
4641 VM_BUG_ON(pfn >= zone->zone_start_pfn + zone->spanned_pages);
Mel Gorman835c1342007-10-16 01:25:47 -07004642
4643 for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
4644 if (flags & value)
4645 __set_bit(bitidx + start_bitidx, bitmap);
4646 else
4647 __clear_bit(bitidx + start_bitidx, bitmap);
4648}
KAMEZAWA Hiroyukia5d76b52007-10-16 01:26:11 -07004649
4650/*
4651 * This is designed as sub function...plz see page_isolation.c also.
4652 * set/clear page block's type to be ISOLATE.
4653 * page allocater never alloc memory from ISOLATE block.
4654 */
4655
4656int set_migratetype_isolate(struct page *page)
4657{
4658 struct zone *zone;
4659 unsigned long flags;
4660 int ret = -EBUSY;
4661
4662 zone = page_zone(page);
4663 spin_lock_irqsave(&zone->lock, flags);
4664 /*
4665 * In future, more migrate types will be able to be isolation target.
4666 */
4667 if (get_pageblock_migratetype(page) != MIGRATE_MOVABLE)
4668 goto out;
4669 set_pageblock_migratetype(page, MIGRATE_ISOLATE);
4670 move_freepages_block(zone, page, MIGRATE_ISOLATE);
4671 ret = 0;
4672out:
4673 spin_unlock_irqrestore(&zone->lock, flags);
4674 if (!ret)
Christoph Lameter9f8f2172008-02-04 22:29:11 -08004675 drain_all_pages();
KAMEZAWA Hiroyukia5d76b52007-10-16 01:26:11 -07004676 return ret;
4677}
4678
4679void unset_migratetype_isolate(struct page *page)
4680{
4681 struct zone *zone;
4682 unsigned long flags;
4683 zone = page_zone(page);
4684 spin_lock_irqsave(&zone->lock, flags);
4685 if (get_pageblock_migratetype(page) != MIGRATE_ISOLATE)
4686 goto out;
4687 set_pageblock_migratetype(page, MIGRATE_MOVABLE);
4688 move_freepages_block(zone, page, MIGRATE_MOVABLE);
4689out:
4690 spin_unlock_irqrestore(&zone->lock, flags);
4691}
KAMEZAWA Hiroyuki0c0e6192007-10-16 01:26:12 -07004692
4693#ifdef CONFIG_MEMORY_HOTREMOVE
4694/*
4695 * All pages in the range must be isolated before calling this.
4696 */
4697void
4698__offline_isolated_pages(unsigned long start_pfn, unsigned long end_pfn)
4699{
4700 struct page *page;
4701 struct zone *zone;
4702 int order, i;
4703 unsigned long pfn;
4704 unsigned long flags;
4705 /* find the first valid pfn */
4706 for (pfn = start_pfn; pfn < end_pfn; pfn++)
4707 if (pfn_valid(pfn))
4708 break;
4709 if (pfn == end_pfn)
4710 return;
4711 zone = page_zone(pfn_to_page(pfn));
4712 spin_lock_irqsave(&zone->lock, flags);
4713 pfn = start_pfn;
4714 while (pfn < end_pfn) {
4715 if (!pfn_valid(pfn)) {
4716 pfn++;
4717 continue;
4718 }
4719 page = pfn_to_page(pfn);
4720 BUG_ON(page_count(page));
4721 BUG_ON(!PageBuddy(page));
4722 order = page_order(page);
4723#ifdef CONFIG_DEBUG_VM
4724 printk(KERN_INFO "remove from free list %lx %d %lx\n",
4725 pfn, 1 << order, end_pfn);
4726#endif
4727 list_del(&page->lru);
4728 rmv_page_order(page);
4729 zone->free_area[order].nr_free--;
4730 __mod_zone_page_state(zone, NR_FREE_PAGES,
4731 - (1UL << order));
4732 for (i = 0; i < (1 << order); i++)
4733 SetPageReserved((page+i));
4734 pfn += (1 << order);
4735 }
4736 spin_unlock_irqrestore(&zone->lock, flags);
4737}
4738#endif