blob: 40db96a655d0c23ad7df245f6dd990b6555c8f4f [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>
22#include <linux/bootmem.h>
23#include <linux/compiler.h>
Randy Dunlap9f158332005-09-13 01:25:16 -070024#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070025#include <linux/module.h>
26#include <linux/suspend.h>
27#include <linux/pagevec.h>
28#include <linux/blkdev.h>
29#include <linux/slab.h>
30#include <linux/notifier.h>
31#include <linux/topology.h>
32#include <linux/sysctl.h>
33#include <linux/cpu.h>
34#include <linux/cpuset.h>
Dave Hansenbdc8cb92005-10-29 18:16:53 -070035#include <linux/memory_hotplug.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070036#include <linux/nodemask.h>
37#include <linux/vmalloc.h>
Christoph Lameter4be38e32006-01-06 00:11:17 -080038#include <linux/mempolicy.h>
Yasunori Goto68113782006-06-23 02:03:11 -070039#include <linux/stop_machine.h>
Mel Gormanc7132162006-09-27 01:49:43 -070040#include <linux/sort.h>
41#include <linux/pfn.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070042
43#include <asm/tlbflush.h>
Andrew Mortonac924c62006-05-15 09:43:59 -070044#include <asm/div64.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070045#include "internal.h"
46
47/*
48 * MCD - HACK: Find somewhere to initialize this EARLY, or make this
49 * initializer cleaner
50 */
Christoph Lameterc3d8c142005-09-06 15:16:33 -070051nodemask_t node_online_map __read_mostly = { { [0] = 1UL } };
Dean Nelson7223a932005-03-23 19:00:00 -070052EXPORT_SYMBOL(node_online_map);
Christoph Lameterc3d8c142005-09-06 15:16:33 -070053nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL;
Dean Nelson7223a932005-03-23 19:00:00 -070054EXPORT_SYMBOL(node_possible_map);
Ravikiran G Thirumalai6c231b72005-09-06 15:17:45 -070055unsigned long totalram_pages __read_mostly;
Hideo AOKIcb45b0e2006-04-10 22:52:59 -070056unsigned long totalreserve_pages __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070057long nr_swap_pages;
Rohit Seth8ad4b1f2006-01-08 01:00:40 -080058int percpu_pagelist_fraction;
Linus Torvalds1da177e2005-04-16 15:20:36 -070059
Hugh Dickinsd98c7a02006-02-14 13:52:59 -080060static void __free_pages_ok(struct page *page, unsigned int order);
David Howellsa226f6c2006-01-06 00:11:08 -080061
Linus Torvalds1da177e2005-04-16 15:20:36 -070062/*
63 * results with 256, 32 in the lowmem_reserve sysctl:
64 * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
65 * 1G machine -> (16M dma, 784M normal, 224M high)
66 * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
67 * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
68 * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
Andi Kleena2f1b422005-11-05 17:25:53 +010069 *
70 * TBD: should special case ZONE_DMA32 machines here - in those we normally
71 * don't need any ZONE_NORMAL reservation
Linus Torvalds1da177e2005-04-16 15:20:36 -070072 */
Christoph Lameter2f1b6242006-09-25 23:31:13 -070073int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
74 256,
Christoph Lameterfb0e7942006-09-25 23:31:13 -070075#ifdef CONFIG_ZONE_DMA32
Christoph Lameter2f1b6242006-09-25 23:31:13 -070076 256,
Christoph Lameterfb0e7942006-09-25 23:31:13 -070077#endif
Christoph Lametere53ef382006-09-25 23:31:14 -070078#ifdef CONFIG_HIGHMEM
Christoph Lameter2f1b6242006-09-25 23:31:13 -070079 32
Christoph Lametere53ef382006-09-25 23:31:14 -070080#endif
Christoph Lameter2f1b6242006-09-25 23:31:13 -070081};
Linus Torvalds1da177e2005-04-16 15:20:36 -070082
83EXPORT_SYMBOL(totalram_pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -070084
85/*
86 * Used by page_zone() to look up the address of the struct zone whose
87 * id is encoded in the upper bits of page->flags
88 */
Christoph Lameterc3d8c142005-09-06 15:16:33 -070089struct zone *zone_table[1 << ZONETABLE_SHIFT] __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070090EXPORT_SYMBOL(zone_table);
91
Christoph Lameter2f1b6242006-09-25 23:31:13 -070092static char *zone_names[MAX_NR_ZONES] = {
93 "DMA",
Christoph Lameterfb0e7942006-09-25 23:31:13 -070094#ifdef CONFIG_ZONE_DMA32
Christoph Lameter2f1b6242006-09-25 23:31:13 -070095 "DMA32",
Christoph Lameterfb0e7942006-09-25 23:31:13 -070096#endif
Christoph Lameter2f1b6242006-09-25 23:31:13 -070097 "Normal",
Christoph Lametere53ef382006-09-25 23:31:14 -070098#ifdef CONFIG_HIGHMEM
Christoph Lameter2f1b6242006-09-25 23:31:13 -070099 "HighMem"
Christoph Lametere53ef382006-09-25 23:31:14 -0700100#endif
Christoph Lameter2f1b6242006-09-25 23:31:13 -0700101};
102
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103int min_free_kbytes = 1024;
104
Yasunori Goto86356ab2006-06-23 02:03:09 -0700105unsigned long __meminitdata nr_kernel_pages;
106unsigned long __meminitdata nr_all_pages;
Mel Gorman0e0b8642006-09-27 01:49:56 -0700107static unsigned long __initdata dma_reserve;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108
Mel Gormanc7132162006-09-27 01:49:43 -0700109#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
110 /*
111 * MAX_ACTIVE_REGIONS determines the maxmimum number of distinct
112 * ranges of memory (RAM) that may be registered with add_active_range().
113 * Ranges passed to add_active_range() will be merged if possible
114 * so the number of times add_active_range() can be called is
115 * related to the number of nodes and the number of holes
116 */
117 #ifdef CONFIG_MAX_ACTIVE_REGIONS
118 /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
119 #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
120 #else
121 #if MAX_NUMNODES >= 32
122 /* If there can be many nodes, allow up to 50 holes per node */
123 #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
124 #else
125 /* By default, allow up to 256 distinct regions */
126 #define MAX_ACTIVE_REGIONS 256
127 #endif
128 #endif
129
130 struct node_active_region __initdata early_node_map[MAX_ACTIVE_REGIONS];
131 int __initdata nr_nodemap_entries;
132 unsigned long __initdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
133 unsigned long __initdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
Mel Gormanfb014392006-09-27 01:49:59 -0700134#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
135 unsigned long __initdata node_boundary_start_pfn[MAX_NUMNODES];
136 unsigned long __initdata node_boundary_end_pfn[MAX_NUMNODES];
137#endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
Mel Gormanc7132162006-09-27 01:49:43 -0700138#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
139
Nick Piggin13e74442006-01-06 00:10:58 -0800140#ifdef CONFIG_DEBUG_VM
Dave Hansenc6a57e12005-10-29 18:16:52 -0700141static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142{
Dave Hansenbdc8cb92005-10-29 18:16:53 -0700143 int ret = 0;
144 unsigned seq;
145 unsigned long pfn = page_to_pfn(page);
Dave Hansenc6a57e12005-10-29 18:16:52 -0700146
Dave Hansenbdc8cb92005-10-29 18:16:53 -0700147 do {
148 seq = zone_span_seqbegin(zone);
149 if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
150 ret = 1;
151 else if (pfn < zone->zone_start_pfn)
152 ret = 1;
153 } while (zone_span_seqretry(zone, seq));
154
155 return ret;
Dave Hansenc6a57e12005-10-29 18:16:52 -0700156}
157
158static int page_is_consistent(struct zone *zone, struct page *page)
159{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160#ifdef CONFIG_HOLES_IN_ZONE
161 if (!pfn_valid(page_to_pfn(page)))
Dave Hansenc6a57e12005-10-29 18:16:52 -0700162 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163#endif
164 if (zone != page_zone(page))
Dave Hansenc6a57e12005-10-29 18:16:52 -0700165 return 0;
166
167 return 1;
168}
169/*
170 * Temporary debugging check for pages not lying within a given zone.
171 */
172static int bad_range(struct zone *zone, struct page *page)
173{
174 if (page_outside_zone_boundaries(zone, page))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700175 return 1;
Dave Hansenc6a57e12005-10-29 18:16:52 -0700176 if (!page_is_consistent(zone, page))
177 return 1;
178
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179 return 0;
180}
Nick Piggin13e74442006-01-06 00:10:58 -0800181#else
182static inline int bad_range(struct zone *zone, struct page *page)
183{
184 return 0;
185}
186#endif
187
Nick Piggin224abf92006-01-06 00:11:11 -0800188static void bad_page(struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189{
Nick Piggin224abf92006-01-06 00:11:11 -0800190 printk(KERN_EMERG "Bad page state in process '%s'\n"
Hugh Dickins7365f3d2006-01-11 12:17:18 -0800191 KERN_EMERG "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n"
192 KERN_EMERG "Trying to fix it up, but a reboot is needed\n"
193 KERN_EMERG "Backtrace:\n",
Nick Piggin224abf92006-01-06 00:11:11 -0800194 current->comm, page, (int)(2*sizeof(unsigned long)),
195 (unsigned long)page->flags, page->mapping,
196 page_mapcount(page), page_count(page));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700197 dump_stack();
Hugh Dickins334795e2005-06-21 17:15:08 -0700198 page->flags &= ~(1 << PG_lru |
199 1 << PG_private |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700200 1 << PG_locked |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201 1 << PG_active |
202 1 << PG_dirty |
Hugh Dickins334795e2005-06-21 17:15:08 -0700203 1 << PG_reclaim |
204 1 << PG_slab |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205 1 << PG_swapcache |
Nick Piggin676165a2006-04-10 11:21:48 +1000206 1 << PG_writeback |
207 1 << PG_buddy );
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208 set_page_count(page, 0);
209 reset_page_mapcount(page);
210 page->mapping = NULL;
Randy Dunlap9f158332005-09-13 01:25:16 -0700211 add_taint(TAINT_BAD_PAGE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700212}
213
Linus Torvalds1da177e2005-04-16 15:20:36 -0700214/*
215 * Higher-order pages are called "compound pages". They are structured thusly:
216 *
217 * The first PAGE_SIZE page is called the "head page".
218 *
219 * The remaining PAGE_SIZE pages are called "tail pages".
220 *
221 * All pages have PG_compound set. All pages have their ->private pointing at
222 * the head page (even the head page has this).
223 *
Hugh Dickins41d78ba2006-02-14 13:52:58 -0800224 * The first tail page's ->lru.next holds the address of the compound page's
225 * put_page() function. Its ->lru.prev holds the order of allocation.
226 * This usage means that zero-order pages may not be compound.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227 */
Hugh Dickinsd98c7a02006-02-14 13:52:59 -0800228
229static void free_compound_page(struct page *page)
230{
231 __free_pages_ok(page, (unsigned long)page[1].lru.prev);
232}
233
Linus Torvalds1da177e2005-04-16 15:20:36 -0700234static void prep_compound_page(struct page *page, unsigned long order)
235{
236 int i;
237 int nr_pages = 1 << order;
238
Hugh Dickinsd98c7a02006-02-14 13:52:59 -0800239 page[1].lru.next = (void *)free_compound_page; /* set dtor */
Hugh Dickins41d78ba2006-02-14 13:52:58 -0800240 page[1].lru.prev = (void *)order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241 for (i = 0; i < nr_pages; i++) {
242 struct page *p = page + i;
243
Nick Piggin5e9dace2006-03-22 00:08:01 -0800244 __SetPageCompound(p);
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700245 set_page_private(p, (unsigned long)page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700246 }
247}
248
249static void destroy_compound_page(struct page *page, unsigned long order)
250{
251 int i;
252 int nr_pages = 1 << order;
253
Hugh Dickins41d78ba2006-02-14 13:52:58 -0800254 if (unlikely((unsigned long)page[1].lru.prev != order))
Nick Piggin224abf92006-01-06 00:11:11 -0800255 bad_page(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256
257 for (i = 0; i < nr_pages; i++) {
258 struct page *p = page + i;
259
Nick Piggin224abf92006-01-06 00:11:11 -0800260 if (unlikely(!PageCompound(p) |
261 (page_private(p) != (unsigned long)page)))
262 bad_page(page);
Nick Piggin5e9dace2006-03-22 00:08:01 -0800263 __ClearPageCompound(p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700264 }
265}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700266
Nick Piggin17cf4402006-03-22 00:08:41 -0800267static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
268{
269 int i;
270
Nick Piggin725d7042006-09-25 23:30:55 -0700271 VM_BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM);
Andrew Morton6626c5d2006-03-22 00:08:42 -0800272 /*
273 * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
274 * and __GFP_HIGHMEM from hard or soft interrupt context.
275 */
Nick Piggin725d7042006-09-25 23:30:55 -0700276 VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
Nick Piggin17cf4402006-03-22 00:08:41 -0800277 for (i = 0; i < (1 << order); i++)
278 clear_highpage(page + i);
279}
280
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281/*
282 * function for dealing with page's order in buddy system.
283 * zone->lock is already acquired when we use these.
284 * So, we don't need atomic page->flags operations here.
285 */
Andrew Morton6aa30012006-04-18 22:20:52 -0700286static inline unsigned long page_order(struct page *page)
287{
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700288 return page_private(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289}
290
Andrew Morton6aa30012006-04-18 22:20:52 -0700291static inline void set_page_order(struct page *page, int order)
292{
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700293 set_page_private(page, order);
Nick Piggin676165a2006-04-10 11:21:48 +1000294 __SetPageBuddy(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295}
296
297static inline void rmv_page_order(struct page *page)
298{
Nick Piggin676165a2006-04-10 11:21:48 +1000299 __ClearPageBuddy(page);
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700300 set_page_private(page, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301}
302
303/*
304 * Locate the struct page for both the matching buddy in our
305 * pair (buddy1) and the combined O(n+1) page they form (page).
306 *
307 * 1) Any buddy B1 will have an order O twin B2 which satisfies
308 * the following equation:
309 * B2 = B1 ^ (1 << O)
310 * For example, if the starting buddy (buddy2) is #8 its order
311 * 1 buddy is #10:
312 * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
313 *
314 * 2) Any buddy B will have an order O+1 parent P which
315 * satisfies the following equation:
316 * P = B & ~(1 << O)
317 *
Andreas Mohrd6e05ed2006-06-26 18:35:02 +0200318 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319 */
320static inline struct page *
321__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
322{
323 unsigned long buddy_idx = page_idx ^ (1 << order);
324
325 return page + (buddy_idx - page_idx);
326}
327
328static inline unsigned long
329__find_combined_index(unsigned long page_idx, unsigned int order)
330{
331 return (page_idx & ~(1 << order));
332}
333
334/*
335 * This function checks whether a page is free && is the buddy
336 * we can do coalesce a page and its buddy if
Nick Piggin13e74442006-01-06 00:10:58 -0800337 * (a) the buddy is not in a hole &&
Nick Piggin676165a2006-04-10 11:21:48 +1000338 * (b) the buddy is in the buddy system &&
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700339 * (c) a page and its buddy have the same order &&
340 * (d) a page and its buddy are in the same zone.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341 *
Nick Piggin676165a2006-04-10 11:21:48 +1000342 * For recording whether a page is in the buddy system, we use PG_buddy.
343 * Setting, clearing, and testing PG_buddy is serialized by zone->lock.
344 *
345 * For recording page's order, we use page_private(page).
Linus Torvalds1da177e2005-04-16 15:20:36 -0700346 */
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700347static inline int page_is_buddy(struct page *page, struct page *buddy,
348 int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700349{
Nick Piggin13e74442006-01-06 00:10:58 -0800350#ifdef CONFIG_HOLES_IN_ZONE
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700351 if (!pfn_valid(page_to_pfn(buddy)))
Nick Piggin13e74442006-01-06 00:10:58 -0800352 return 0;
353#endif
354
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700355 if (page_zone_id(page) != page_zone_id(buddy))
356 return 0;
357
358 if (PageBuddy(buddy) && page_order(buddy) == order) {
359 BUG_ON(page_count(buddy) != 0);
Andrew Morton6aa30012006-04-18 22:20:52 -0700360 return 1;
Nick Piggin676165a2006-04-10 11:21:48 +1000361 }
Andrew Morton6aa30012006-04-18 22:20:52 -0700362 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700363}
364
365/*
366 * Freeing function for a buddy system allocator.
367 *
368 * The concept of a buddy system is to maintain direct-mapped table
369 * (containing bit values) for memory blocks of various "orders".
370 * The bottom level table contains the map for the smallest allocatable
371 * units of memory (here, pages), and each level above it describes
372 * pairs of units from the levels below, hence, "buddies".
373 * At a high level, all that happens here is marking the table entry
374 * at the bottom level available, and propagating the changes upward
375 * as necessary, plus some accounting needed to play nicely with other
376 * parts of the VM system.
377 * At each level, we keep a list of pages, which are heads of continuous
Nick Piggin676165a2006-04-10 11:21:48 +1000378 * free pages of length of (1 << order) and marked with PG_buddy. Page's
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700379 * order is recorded in page_private(page) field.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700380 * So when we are allocating or freeing one, we can derive the state of the
381 * other. That is, if we allocate a small block, and both were
382 * free, the remainder of the region must be split into blocks.
383 * If a block is freed, and its buddy is also free, then this
384 * triggers coalescing into a block of larger size.
385 *
386 * -- wli
387 */
388
Nick Piggin48db57f2006-01-08 01:00:42 -0800389static inline void __free_one_page(struct page *page,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 struct zone *zone, unsigned int order)
391{
392 unsigned long page_idx;
393 int order_size = 1 << order;
394
Nick Piggin224abf92006-01-06 00:11:11 -0800395 if (unlikely(PageCompound(page)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 destroy_compound_page(page, order);
397
398 page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
399
Nick Piggin725d7042006-09-25 23:30:55 -0700400 VM_BUG_ON(page_idx & (order_size - 1));
401 VM_BUG_ON(bad_range(zone, page));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402
403 zone->free_pages += order_size;
404 while (order < MAX_ORDER-1) {
405 unsigned long combined_idx;
406 struct free_area *area;
407 struct page *buddy;
408
Linus Torvalds1da177e2005-04-16 15:20:36 -0700409 buddy = __page_find_buddy(page, page_idx, order);
Andy Whitcroftcb2b95e2006-06-23 02:03:01 -0700410 if (!page_is_buddy(page, buddy, order))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 break; /* Move the buddy up one level. */
Nick Piggin13e74442006-01-06 00:10:58 -0800412
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413 list_del(&buddy->lru);
414 area = zone->free_area + order;
415 area->nr_free--;
416 rmv_page_order(buddy);
Nick Piggin13e74442006-01-06 00:10:58 -0800417 combined_idx = __find_combined_index(page_idx, order);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700418 page = page + (combined_idx - page_idx);
419 page_idx = combined_idx;
420 order++;
421 }
422 set_page_order(page, order);
423 list_add(&page->lru, &zone->free_area[order].free_list);
424 zone->free_area[order].nr_free++;
425}
426
Nick Piggin224abf92006-01-06 00:11:11 -0800427static inline int free_pages_check(struct page *page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700428{
Nick Piggin92be2e32006-01-06 00:10:57 -0800429 if (unlikely(page_mapcount(page) |
430 (page->mapping != NULL) |
431 (page_count(page) != 0) |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700432 (page->flags & (
433 1 << PG_lru |
434 1 << PG_private |
435 1 << PG_locked |
436 1 << PG_active |
437 1 << PG_reclaim |
438 1 << PG_slab |
439 1 << PG_swapcache |
Nick Pigginb5810032005-10-29 18:16:12 -0700440 1 << PG_writeback |
Nick Piggin676165a2006-04-10 11:21:48 +1000441 1 << PG_reserved |
442 1 << PG_buddy ))))
Nick Piggin224abf92006-01-06 00:11:11 -0800443 bad_page(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700444 if (PageDirty(page))
Nick Piggin242e5462005-09-03 15:54:50 -0700445 __ClearPageDirty(page);
Hugh Dickins689bceb2005-11-21 21:32:20 -0800446 /*
447 * For now, we report if PG_reserved was found set, but do not
448 * clear it, and do not free the page. But we shall soon need
449 * to do more, for when the ZERO_PAGE count wraps negative.
450 */
451 return PageReserved(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700452}
453
454/*
455 * Frees a list of pages.
456 * Assumes all pages on list are in same zone, and of same order.
Renaud Lienhart207f36e2005-09-10 00:26:59 -0700457 * count is the number of pages to free.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700458 *
459 * If the zone was previously in an "all pages pinned" state then look to
460 * see if this freeing clears that state.
461 *
462 * And clear the zone's pages_scanned counter, to hold off the "all pages are
463 * pinned" detection logic.
464 */
Nick Piggin48db57f2006-01-08 01:00:42 -0800465static void free_pages_bulk(struct zone *zone, int count,
466 struct list_head *list, int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467{
Nick Pigginc54ad302006-01-06 00:10:56 -0800468 spin_lock(&zone->lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469 zone->all_unreclaimable = 0;
470 zone->pages_scanned = 0;
Nick Piggin48db57f2006-01-08 01:00:42 -0800471 while (count--) {
472 struct page *page;
473
Nick Piggin725d7042006-09-25 23:30:55 -0700474 VM_BUG_ON(list_empty(list));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475 page = list_entry(list->prev, struct page, lru);
Nick Piggin48db57f2006-01-08 01:00:42 -0800476 /* have to delete it as __free_one_page list manipulates */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 list_del(&page->lru);
Nick Piggin48db57f2006-01-08 01:00:42 -0800478 __free_one_page(page, zone, order);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479 }
Nick Pigginc54ad302006-01-06 00:10:56 -0800480 spin_unlock(&zone->lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481}
482
Nick Piggin48db57f2006-01-08 01:00:42 -0800483static void free_one_page(struct zone *zone, struct page *page, int order)
484{
Christoph Lameter006d22d2006-09-25 23:31:48 -0700485 spin_lock(&zone->lock);
486 zone->all_unreclaimable = 0;
487 zone->pages_scanned = 0;
488 __free_one_page(page, zone ,order);
489 spin_unlock(&zone->lock);
Nick Piggin48db57f2006-01-08 01:00:42 -0800490}
491
492static void __free_pages_ok(struct page *page, unsigned int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700493{
Nick Pigginc54ad302006-01-06 00:10:56 -0800494 unsigned long flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700495 int i;
Hugh Dickins689bceb2005-11-21 21:32:20 -0800496 int reserved = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700497
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498 for (i = 0 ; i < (1 << order) ; ++i)
Nick Piggin224abf92006-01-06 00:11:11 -0800499 reserved += free_pages_check(page + i);
Hugh Dickins689bceb2005-11-21 21:32:20 -0800500 if (reserved)
501 return;
502
Nick Piggin9858db52006-10-11 01:21:30 -0700503 if (!PageHighMem(page))
504 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
Nick Piggindafb1362006-10-11 01:21:30 -0700505 arch_free_page(page, order);
Nick Piggin48db57f2006-01-08 01:00:42 -0800506 kernel_map_pages(page, 1 << order, 0);
Nick Piggindafb1362006-10-11 01:21:30 -0700507
Nick Pigginc54ad302006-01-06 00:10:56 -0800508 local_irq_save(flags);
Christoph Lameterf8891e52006-06-30 01:55:45 -0700509 __count_vm_events(PGFREE, 1 << order);
Nick Piggin48db57f2006-01-08 01:00:42 -0800510 free_one_page(page_zone(page), page, order);
Nick Pigginc54ad302006-01-06 00:10:56 -0800511 local_irq_restore(flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512}
513
David Howellsa226f6c2006-01-06 00:11:08 -0800514/*
515 * permit the bootmem allocator to evade page validation on high-order frees
516 */
517void fastcall __init __free_pages_bootmem(struct page *page, unsigned int order)
518{
519 if (order == 0) {
520 __ClearPageReserved(page);
521 set_page_count(page, 0);
Nick Piggin7835e982006-03-22 00:08:40 -0800522 set_page_refcounted(page);
Nick Piggin545b1ea2006-03-22 00:08:07 -0800523 __free_page(page);
David Howellsa226f6c2006-01-06 00:11:08 -0800524 } else {
David Howellsa226f6c2006-01-06 00:11:08 -0800525 int loop;
526
Nick Piggin545b1ea2006-03-22 00:08:07 -0800527 prefetchw(page);
David Howellsa226f6c2006-01-06 00:11:08 -0800528 for (loop = 0; loop < BITS_PER_LONG; loop++) {
529 struct page *p = &page[loop];
530
Nick Piggin545b1ea2006-03-22 00:08:07 -0800531 if (loop + 1 < BITS_PER_LONG)
532 prefetchw(p + 1);
David Howellsa226f6c2006-01-06 00:11:08 -0800533 __ClearPageReserved(p);
534 set_page_count(p, 0);
535 }
536
Nick Piggin7835e982006-03-22 00:08:40 -0800537 set_page_refcounted(page);
Nick Piggin545b1ea2006-03-22 00:08:07 -0800538 __free_pages(page, order);
David Howellsa226f6c2006-01-06 00:11:08 -0800539 }
540}
541
Linus Torvalds1da177e2005-04-16 15:20:36 -0700542
543/*
544 * The order of subdivision here is critical for the IO subsystem.
545 * Please do not alter this order without good reasons and regression
546 * testing. Specifically, as large blocks of memory are subdivided,
547 * the order in which smaller blocks are delivered depends on the order
548 * they're subdivided in this function. This is the primary factor
549 * influencing the order in which pages are delivered to the IO
550 * subsystem according to empirical testing, and this is also justified
551 * by considering the behavior of a buddy system containing a single
552 * large block of memory acted on by a series of small allocations.
553 * This behavior is a critical factor in sglist merging's success.
554 *
555 * -- wli
556 */
Nick Piggin085cc7d2006-01-06 00:11:01 -0800557static inline void expand(struct zone *zone, struct page *page,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700558 int low, int high, struct free_area *area)
559{
560 unsigned long size = 1 << high;
561
562 while (high > low) {
563 area--;
564 high--;
565 size >>= 1;
Nick Piggin725d7042006-09-25 23:30:55 -0700566 VM_BUG_ON(bad_range(zone, &page[size]));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567 list_add(&page[size].lru, &area->free_list);
568 area->nr_free++;
569 set_page_order(&page[size], high);
570 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571}
572
Linus Torvalds1da177e2005-04-16 15:20:36 -0700573/*
574 * This page is about to be returned from the page allocator
575 */
Nick Piggin17cf4402006-03-22 00:08:41 -0800576static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577{
Nick Piggin92be2e32006-01-06 00:10:57 -0800578 if (unlikely(page_mapcount(page) |
579 (page->mapping != NULL) |
580 (page_count(page) != 0) |
Hugh Dickins334795e2005-06-21 17:15:08 -0700581 (page->flags & (
582 1 << PG_lru |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700583 1 << PG_private |
584 1 << PG_locked |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700585 1 << PG_active |
586 1 << PG_dirty |
587 1 << PG_reclaim |
Hugh Dickins334795e2005-06-21 17:15:08 -0700588 1 << PG_slab |
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589 1 << PG_swapcache |
Nick Pigginb5810032005-10-29 18:16:12 -0700590 1 << PG_writeback |
Nick Piggin676165a2006-04-10 11:21:48 +1000591 1 << PG_reserved |
592 1 << PG_buddy ))))
Nick Piggin224abf92006-01-06 00:11:11 -0800593 bad_page(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700594
Hugh Dickins689bceb2005-11-21 21:32:20 -0800595 /*
596 * For now, we report if PG_reserved was found set, but do not
597 * clear it, and do not allocate the page: as a safety net.
598 */
599 if (PageReserved(page))
600 return 1;
601
Linus Torvalds1da177e2005-04-16 15:20:36 -0700602 page->flags &= ~(1 << PG_uptodate | 1 << PG_error |
603 1 << PG_referenced | 1 << PG_arch_1 |
604 1 << PG_checked | 1 << PG_mappedtodisk);
Hugh Dickins4c21e2f2005-10-29 18:16:40 -0700605 set_page_private(page, 0);
Nick Piggin7835e982006-03-22 00:08:40 -0800606 set_page_refcounted(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700607 kernel_map_pages(page, 1 << order, 1);
Nick Piggin17cf4402006-03-22 00:08:41 -0800608
609 if (gfp_flags & __GFP_ZERO)
610 prep_zero_page(page, order, gfp_flags);
611
612 if (order && (gfp_flags & __GFP_COMP))
613 prep_compound_page(page, order);
614
Hugh Dickins689bceb2005-11-21 21:32:20 -0800615 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700616}
617
618/*
619 * Do the hard work of removing an element from the buddy allocator.
620 * Call me with the zone->lock already held.
621 */
622static struct page *__rmqueue(struct zone *zone, unsigned int order)
623{
624 struct free_area * area;
625 unsigned int current_order;
626 struct page *page;
627
628 for (current_order = order; current_order < MAX_ORDER; ++current_order) {
629 area = zone->free_area + current_order;
630 if (list_empty(&area->free_list))
631 continue;
632
633 page = list_entry(area->free_list.next, struct page, lru);
634 list_del(&page->lru);
635 rmv_page_order(page);
636 area->nr_free--;
637 zone->free_pages -= 1UL << order;
Nick Piggin085cc7d2006-01-06 00:11:01 -0800638 expand(zone, page, order, current_order, area);
639 return page;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640 }
641
642 return NULL;
643}
644
645/*
646 * Obtain a specified number of elements from the buddy allocator, all under
647 * a single hold of the lock, for efficiency. Add them to the supplied list.
648 * Returns the number of new pages which were placed at *list.
649 */
650static int rmqueue_bulk(struct zone *zone, unsigned int order,
651 unsigned long count, struct list_head *list)
652{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700654
Nick Pigginc54ad302006-01-06 00:10:56 -0800655 spin_lock(&zone->lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656 for (i = 0; i < count; ++i) {
Nick Piggin085cc7d2006-01-06 00:11:01 -0800657 struct page *page = __rmqueue(zone, order);
658 if (unlikely(page == NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700659 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700660 list_add_tail(&page->lru, list);
661 }
Nick Pigginc54ad302006-01-06 00:10:56 -0800662 spin_unlock(&zone->lock);
Nick Piggin085cc7d2006-01-06 00:11:01 -0800663 return i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700664}
665
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700666#ifdef CONFIG_NUMA
Christoph Lameter8fce4d82006-03-09 17:33:54 -0800667/*
668 * Called from the slab reaper to drain pagesets on a particular node that
Christoph Lameter39bbcb82006-09-25 23:31:49 -0700669 * belongs to the currently executing processor.
Christoph Lameter879336c2006-03-22 00:09:08 -0800670 * Note that this function must be called with the thread pinned to
671 * a single processor.
Christoph Lameter8fce4d82006-03-09 17:33:54 -0800672 */
673void drain_node_pages(int nodeid)
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700674{
Christoph Lameter2f6726e2006-09-25 23:31:18 -0700675 int i;
676 enum zone_type z;
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700677 unsigned long flags;
678
Christoph Lameter8fce4d82006-03-09 17:33:54 -0800679 for (z = 0; z < MAX_NR_ZONES; z++) {
680 struct zone *zone = NODE_DATA(nodeid)->node_zones + z;
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700681 struct per_cpu_pageset *pset;
682
Christoph Lameter39bbcb82006-09-25 23:31:49 -0700683 if (!populated_zone(zone))
684 continue;
685
Nick Piggin23316bc2006-01-08 01:00:41 -0800686 pset = zone_pcp(zone, smp_processor_id());
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700687 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
688 struct per_cpu_pages *pcp;
689
690 pcp = &pset->pcp[i];
Christoph Lameter879336c2006-03-22 00:09:08 -0800691 if (pcp->count) {
692 local_irq_save(flags);
693 free_pages_bulk(zone, pcp->count, &pcp->list, 0);
694 pcp->count = 0;
695 local_irq_restore(flags);
696 }
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700697 }
698 }
Christoph Lameter4ae7c032005-06-21 17:14:57 -0700699}
700#endif
701
Linus Torvalds1da177e2005-04-16 15:20:36 -0700702#if defined(CONFIG_PM) || defined(CONFIG_HOTPLUG_CPU)
703static void __drain_pages(unsigned int cpu)
704{
Nick Pigginc54ad302006-01-06 00:10:56 -0800705 unsigned long flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700706 struct zone *zone;
707 int i;
708
709 for_each_zone(zone) {
710 struct per_cpu_pageset *pset;
711
Christoph Lametere7c8d5c2005-06-21 17:14:47 -0700712 pset = zone_pcp(zone, cpu);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
714 struct per_cpu_pages *pcp;
715
716 pcp = &pset->pcp[i];
Nick Pigginc54ad302006-01-06 00:10:56 -0800717 local_irq_save(flags);
Nick Piggin48db57f2006-01-08 01:00:42 -0800718 free_pages_bulk(zone, pcp->count, &pcp->list, 0);
719 pcp->count = 0;
Nick Pigginc54ad302006-01-06 00:10:56 -0800720 local_irq_restore(flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700721 }
722 }
723}
724#endif /* CONFIG_PM || CONFIG_HOTPLUG_CPU */
725
726#ifdef CONFIG_PM
727
728void mark_free_pages(struct zone *zone)
729{
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700730 unsigned long pfn, max_zone_pfn;
731 unsigned long flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700732 int order;
733 struct list_head *curr;
734
735 if (!zone->spanned_pages)
736 return;
737
738 spin_lock_irqsave(&zone->lock, flags);
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700739
740 max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
741 for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
742 if (pfn_valid(pfn)) {
743 struct page *page = pfn_to_page(pfn);
744
745 if (!PageNosave(page))
746 ClearPageNosaveFree(page);
747 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700748
749 for (order = MAX_ORDER - 1; order >= 0; --order)
750 list_for_each(curr, &zone->free_area[order].free_list) {
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700751 unsigned long i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700752
Rafael J. Wysockif623f0d2006-09-25 23:32:49 -0700753 pfn = page_to_pfn(list_entry(curr, struct page, lru));
754 for (i = 0; i < (1UL << order); i++)
755 SetPageNosaveFree(pfn_to_page(pfn + i));
756 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757
Linus Torvalds1da177e2005-04-16 15:20:36 -0700758 spin_unlock_irqrestore(&zone->lock, flags);
759}
760
761/*
762 * Spill all of this CPU's per-cpu pages back into the buddy allocator.
763 */
764void drain_local_pages(void)
765{
766 unsigned long flags;
767
768 local_irq_save(flags);
769 __drain_pages(smp_processor_id());
770 local_irq_restore(flags);
771}
772#endif /* CONFIG_PM */
773
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774/*
775 * Free a 0-order page
776 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700777static void fastcall free_hot_cold_page(struct page *page, int cold)
778{
779 struct zone *zone = page_zone(page);
780 struct per_cpu_pages *pcp;
781 unsigned long flags;
782
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783 if (PageAnon(page))
784 page->mapping = NULL;
Nick Piggin224abf92006-01-06 00:11:11 -0800785 if (free_pages_check(page))
Hugh Dickins689bceb2005-11-21 21:32:20 -0800786 return;
787
Nick Piggin9858db52006-10-11 01:21:30 -0700788 if (!PageHighMem(page))
789 debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
Nick Piggindafb1362006-10-11 01:21:30 -0700790 arch_free_page(page, 0);
Hugh Dickins689bceb2005-11-21 21:32:20 -0800791 kernel_map_pages(page, 1, 0);
792
Christoph Lametere7c8d5c2005-06-21 17:14:47 -0700793 pcp = &zone_pcp(zone, get_cpu())->pcp[cold];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700794 local_irq_save(flags);
Christoph Lameterf8891e52006-06-30 01:55:45 -0700795 __count_vm_event(PGFREE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796 list_add(&page->lru, &pcp->list);
797 pcp->count++;
Nick Piggin48db57f2006-01-08 01:00:42 -0800798 if (pcp->count >= pcp->high) {
799 free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
800 pcp->count -= pcp->batch;
801 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700802 local_irq_restore(flags);
803 put_cpu();
804}
805
806void fastcall free_hot_page(struct page *page)
807{
808 free_hot_cold_page(page, 0);
809}
810
811void fastcall free_cold_page(struct page *page)
812{
813 free_hot_cold_page(page, 1);
814}
815
Nick Piggin8dfcc9b2006-03-22 00:08:05 -0800816/*
817 * split_page takes a non-compound higher-order page, and splits it into
818 * n (1<<order) sub-pages: page[0..n]
819 * Each sub-page must be freed individually.
820 *
821 * Note: this is probably too low level an operation for use in drivers.
822 * Please consult with lkml before using this in your driver.
823 */
824void split_page(struct page *page, unsigned int order)
825{
826 int i;
827
Nick Piggin725d7042006-09-25 23:30:55 -0700828 VM_BUG_ON(PageCompound(page));
829 VM_BUG_ON(!page_count(page));
Nick Piggin7835e982006-03-22 00:08:40 -0800830 for (i = 1; i < (1 << order); i++)
831 set_page_refcounted(page + i);
Nick Piggin8dfcc9b2006-03-22 00:08:05 -0800832}
Nick Piggin8dfcc9b2006-03-22 00:08:05 -0800833
Linus Torvalds1da177e2005-04-16 15:20:36 -0700834/*
835 * Really, prep_compound_page() should be called from __rmqueue_bulk(). But
836 * we cheat by calling it from here, in the order > 0 path. Saves a branch
837 * or two.
838 */
Nick Piggina74609f2006-01-06 00:11:20 -0800839static struct page *buffered_rmqueue(struct zonelist *zonelist,
840 struct zone *zone, int order, gfp_t gfp_flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700841{
842 unsigned long flags;
Hugh Dickins689bceb2005-11-21 21:32:20 -0800843 struct page *page;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844 int cold = !!(gfp_flags & __GFP_COLD);
Nick Piggina74609f2006-01-06 00:11:20 -0800845 int cpu;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846
Hugh Dickins689bceb2005-11-21 21:32:20 -0800847again:
Nick Piggina74609f2006-01-06 00:11:20 -0800848 cpu = get_cpu();
Nick Piggin48db57f2006-01-08 01:00:42 -0800849 if (likely(order == 0)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700850 struct per_cpu_pages *pcp;
851
Nick Piggina74609f2006-01-06 00:11:20 -0800852 pcp = &zone_pcp(zone, cpu)->pcp[cold];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853 local_irq_save(flags);
Nick Piggina74609f2006-01-06 00:11:20 -0800854 if (!pcp->count) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700855 pcp->count += rmqueue_bulk(zone, 0,
856 pcp->batch, &pcp->list);
Nick Piggina74609f2006-01-06 00:11:20 -0800857 if (unlikely(!pcp->count))
858 goto failed;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859 }
Nick Piggina74609f2006-01-06 00:11:20 -0800860 page = list_entry(pcp->list.next, struct page, lru);
861 list_del(&page->lru);
862 pcp->count--;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800863 } else {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700864 spin_lock_irqsave(&zone->lock, flags);
865 page = __rmqueue(zone, order);
Nick Piggina74609f2006-01-06 00:11:20 -0800866 spin_unlock(&zone->lock);
867 if (!page)
868 goto failed;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700869 }
870
Christoph Lameterf8891e52006-06-30 01:55:45 -0700871 __count_zone_vm_events(PGALLOC, zone, 1 << order);
Christoph Lameterca889e62006-06-30 01:55:44 -0700872 zone_statistics(zonelist, zone);
Nick Piggina74609f2006-01-06 00:11:20 -0800873 local_irq_restore(flags);
874 put_cpu();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875
Nick Piggin725d7042006-09-25 23:30:55 -0700876 VM_BUG_ON(bad_range(zone, page));
Nick Piggin17cf4402006-03-22 00:08:41 -0800877 if (prep_new_page(page, order, gfp_flags))
Nick Piggina74609f2006-01-06 00:11:20 -0800878 goto again;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700879 return page;
Nick Piggina74609f2006-01-06 00:11:20 -0800880
881failed:
882 local_irq_restore(flags);
883 put_cpu();
884 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700885}
886
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800887#define ALLOC_NO_WATERMARKS 0x01 /* don't check watermarks at all */
Nick Piggin31488902005-11-28 13:44:03 -0800888#define ALLOC_WMARK_MIN 0x02 /* use pages_min watermark */
889#define ALLOC_WMARK_LOW 0x04 /* use pages_low watermark */
890#define ALLOC_WMARK_HIGH 0x08 /* use pages_high watermark */
891#define ALLOC_HARDER 0x10 /* try to alloc harder */
892#define ALLOC_HIGH 0x20 /* __GFP_HIGH set */
893#define ALLOC_CPUSET 0x40 /* check for correct cpuset */
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800894
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895/*
896 * Return 1 if free pages are above 'mark'. This takes into account the order
897 * of the allocation.
898 */
899int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800900 int classzone_idx, int alloc_flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700901{
902 /* free_pages my go negative - that's OK */
Nick Piggine80ee882006-10-04 02:15:23 -0700903 unsigned long min = mark;
904 long free_pages = z->free_pages - (1 << order) + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905 int o;
906
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800907 if (alloc_flags & ALLOC_HIGH)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700908 min -= min / 2;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800909 if (alloc_flags & ALLOC_HARDER)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910 min -= min / 4;
911
912 if (free_pages <= min + z->lowmem_reserve[classzone_idx])
913 return 0;
914 for (o = 0; o < order; o++) {
915 /* At the next order, this order's pages become unavailable */
916 free_pages -= z->free_area[o].nr_free << o;
917
918 /* Require fewer higher order pages to be free */
919 min >>= 1;
920
921 if (free_pages <= min)
922 return 0;
923 }
924 return 1;
925}
926
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800927/*
928 * get_page_from_freeliest goes through the zonelist trying to allocate
929 * a page.
930 */
931static struct page *
932get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
933 struct zonelist *zonelist, int alloc_flags)
Martin Hicks753ee722005-06-21 17:14:41 -0700934{
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800935 struct zone **z = zonelist->zones;
936 struct page *page = NULL;
937 int classzone_idx = zone_idx(*z);
Christoph Lameter1192d522006-09-25 23:31:45 -0700938 struct zone *zone;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800939
940 /*
941 * Go through the zonelist once, looking for a zone with enough free.
942 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
943 */
944 do {
Christoph Lameter1192d522006-09-25 23:31:45 -0700945 zone = *z;
Christoph Lameter08e0f6a2006-09-27 01:50:06 -0700946 if (unlikely(NUMA_BUILD && (gfp_mask & __GFP_THISNODE) &&
Christoph Lameter1192d522006-09-25 23:31:45 -0700947 zone->zone_pgdat != zonelist->zones[0]->zone_pgdat))
Christoph Lameter9b819d22006-09-25 23:31:40 -0700948 break;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800949 if ((alloc_flags & ALLOC_CPUSET) &&
Christoph Lameter1192d522006-09-25 23:31:45 -0700950 !cpuset_zone_allowed(zone, gfp_mask))
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800951 continue;
952
953 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
Nick Piggin31488902005-11-28 13:44:03 -0800954 unsigned long mark;
955 if (alloc_flags & ALLOC_WMARK_MIN)
Christoph Lameter1192d522006-09-25 23:31:45 -0700956 mark = zone->pages_min;
Nick Piggin31488902005-11-28 13:44:03 -0800957 else if (alloc_flags & ALLOC_WMARK_LOW)
Christoph Lameter1192d522006-09-25 23:31:45 -0700958 mark = zone->pages_low;
Nick Piggin31488902005-11-28 13:44:03 -0800959 else
Christoph Lameter1192d522006-09-25 23:31:45 -0700960 mark = zone->pages_high;
961 if (!zone_watermark_ok(zone , order, mark,
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800962 classzone_idx, alloc_flags))
Christoph Lameter9eeff232006-01-18 17:42:31 -0800963 if (!zone_reclaim_mode ||
Christoph Lameter1192d522006-09-25 23:31:45 -0700964 !zone_reclaim(zone, gfp_mask, order))
Christoph Lameter9eeff232006-01-18 17:42:31 -0800965 continue;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800966 }
967
Christoph Lameter1192d522006-09-25 23:31:45 -0700968 page = buffered_rmqueue(zonelist, zone, order, gfp_mask);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800969 if (page) {
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800970 break;
971 }
972 } while (*(++z) != NULL);
973 return page;
Martin Hicks753ee722005-06-21 17:14:41 -0700974}
975
Linus Torvalds1da177e2005-04-16 15:20:36 -0700976/*
977 * This is the 'heart' of the zoned buddy allocator.
978 */
979struct page * fastcall
Al Virodd0fc662005-10-07 07:46:04 +0100980__alloc_pages(gfp_t gfp_mask, unsigned int order,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700981 struct zonelist *zonelist)
982{
Al Viro260b2362005-10-21 03:22:44 -0400983 const gfp_t wait = gfp_mask & __GFP_WAIT;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800984 struct zone **z;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985 struct page *page;
986 struct reclaim_state reclaim_state;
987 struct task_struct *p = current;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700988 int do_retry;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800989 int alloc_flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700990 int did_some_progress;
991
992 might_sleep_if(wait);
993
Jens Axboe6b1de912005-11-17 21:35:02 +0100994restart:
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800995 z = zonelist->zones; /* the list of zones suitable for gfp_mask */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700996
Rohit Seth7fb1d9f2005-11-13 16:06:43 -0800997 if (unlikely(*z == NULL)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700998 /* Should this ever happen?? */
999 return NULL;
1000 }
Jens Axboe6b1de912005-11-17 21:35:02 +01001001
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001002 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
Nick Piggin31488902005-11-28 13:44:03 -08001003 zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001004 if (page)
1005 goto got_pg;
1006
Jens Axboe6b1de912005-11-17 21:35:02 +01001007 do {
Chris Wright43b0bc02006-06-25 05:47:55 -07001008 wakeup_kswapd(*z, order);
Jens Axboe6b1de912005-11-17 21:35:02 +01001009 } while (*(++z));
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001010
Paul Jackson9bf22292005-09-06 15:18:12 -07001011 /*
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001012 * OK, we're below the kswapd watermark and have kicked background
1013 * reclaim. Now things get more complex, so set up alloc_flags according
1014 * to how we want to proceed.
1015 *
1016 * The caller may dip into page reserves a bit more if the caller
1017 * cannot run direct reclaim, or if the caller has realtime scheduling
Paul Jackson4eac9152006-01-11 12:17:19 -08001018 * policy or is asking for __GFP_HIGH memory. GFP_ATOMIC requests will
1019 * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
Paul Jackson9bf22292005-09-06 15:18:12 -07001020 */
Nick Piggin31488902005-11-28 13:44:03 -08001021 alloc_flags = ALLOC_WMARK_MIN;
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001022 if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
1023 alloc_flags |= ALLOC_HARDER;
1024 if (gfp_mask & __GFP_HIGH)
1025 alloc_flags |= ALLOC_HIGH;
Paul Jacksonbdd804f2006-05-20 15:00:09 -07001026 if (wait)
1027 alloc_flags |= ALLOC_CPUSET;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028
1029 /*
1030 * Go through the zonelist again. Let __GFP_HIGH and allocations
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001031 * coming from realtime tasks go deeper into reserves.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001032 *
1033 * This is the last chance, in general, before the goto nopage.
1034 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
Paul Jackson9bf22292005-09-06 15:18:12 -07001035 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001036 */
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001037 page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);
1038 if (page)
1039 goto got_pg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001040
1041 /* This allocation should allow future memory freeing. */
Nick Pigginb84a35b2005-05-01 08:58:36 -07001042
1043 if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
1044 && !in_interrupt()) {
1045 if (!(gfp_mask & __GFP_NOMEMALLOC)) {
Kirill Korotaev885036d2005-11-13 16:06:41 -08001046nofail_alloc:
Nick Pigginb84a35b2005-05-01 08:58:36 -07001047 /* go through the zonelist yet again, ignoring mins */
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001048 page = get_page_from_freelist(gfp_mask, order,
Paul Jackson47f3a862006-01-06 00:10:32 -08001049 zonelist, ALLOC_NO_WATERMARKS);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001050 if (page)
1051 goto got_pg;
Kirill Korotaev885036d2005-11-13 16:06:41 -08001052 if (gfp_mask & __GFP_NOFAIL) {
1053 blk_congestion_wait(WRITE, HZ/50);
1054 goto nofail_alloc;
1055 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001056 }
1057 goto nopage;
1058 }
1059
1060 /* Atomic allocations - we can't balance anything */
1061 if (!wait)
1062 goto nopage;
1063
1064rebalance:
1065 cond_resched();
1066
1067 /* We now go into synchronous reclaim */
Paul Jackson3e0d98b2006-01-08 01:01:49 -08001068 cpuset_memory_pressure_bump();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001069 p->flags |= PF_MEMALLOC;
1070 reclaim_state.reclaimed_slab = 0;
1071 p->reclaim_state = &reclaim_state;
1072
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001073 did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001074
1075 p->reclaim_state = NULL;
1076 p->flags &= ~PF_MEMALLOC;
1077
1078 cond_resched();
1079
1080 if (likely(did_some_progress)) {
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001081 page = get_page_from_freelist(gfp_mask, order,
1082 zonelist, alloc_flags);
1083 if (page)
1084 goto got_pg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001085 } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
1086 /*
1087 * Go through the zonelist yet one more time, keep
1088 * very high watermark here, this is only to catch
1089 * a parallel oom killing, we must fail if we're still
1090 * under heavy pressure.
1091 */
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001092 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
Nick Piggin31488902005-11-28 13:44:03 -08001093 zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
Rohit Seth7fb1d9f2005-11-13 16:06:43 -08001094 if (page)
1095 goto got_pg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001096
Christoph Lameter9b0f8b02006-02-20 18:27:52 -08001097 out_of_memory(zonelist, gfp_mask, order);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001098 goto restart;
1099 }
1100
1101 /*
1102 * Don't let big-order allocations loop unless the caller explicitly
1103 * requests that. Wait for some write requests to complete then retry.
1104 *
1105 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
1106 * <= 3, but that may not be true in other implementations.
1107 */
1108 do_retry = 0;
1109 if (!(gfp_mask & __GFP_NORETRY)) {
1110 if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
1111 do_retry = 1;
1112 if (gfp_mask & __GFP_NOFAIL)
1113 do_retry = 1;
1114 }
1115 if (do_retry) {
1116 blk_congestion_wait(WRITE, HZ/50);
1117 goto rebalance;
1118 }
1119
1120nopage:
1121 if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
1122 printk(KERN_WARNING "%s: page allocation failure."
1123 " order:%d, mode:0x%x\n",
1124 p->comm, order, gfp_mask);
1125 dump_stack();
Janet Morgan578c2fd2005-06-21 17:14:56 -07001126 show_mem();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001128got_pg:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001129 return page;
1130}
1131
1132EXPORT_SYMBOL(__alloc_pages);
1133
1134/*
1135 * Common helper functions.
1136 */
Al Virodd0fc662005-10-07 07:46:04 +01001137fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001138{
1139 struct page * page;
1140 page = alloc_pages(gfp_mask, order);
1141 if (!page)
1142 return 0;
1143 return (unsigned long) page_address(page);
1144}
1145
1146EXPORT_SYMBOL(__get_free_pages);
1147
Al Virodd0fc662005-10-07 07:46:04 +01001148fastcall unsigned long get_zeroed_page(gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001149{
1150 struct page * page;
1151
1152 /*
1153 * get_zeroed_page() returns a 32-bit address, which cannot represent
1154 * a highmem page
1155 */
Nick Piggin725d7042006-09-25 23:30:55 -07001156 VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001157
1158 page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
1159 if (page)
1160 return (unsigned long) page_address(page);
1161 return 0;
1162}
1163
1164EXPORT_SYMBOL(get_zeroed_page);
1165
1166void __pagevec_free(struct pagevec *pvec)
1167{
1168 int i = pagevec_count(pvec);
1169
1170 while (--i >= 0)
1171 free_hot_cold_page(pvec->pages[i], pvec->cold);
1172}
1173
1174fastcall void __free_pages(struct page *page, unsigned int order)
1175{
Nick Pigginb5810032005-10-29 18:16:12 -07001176 if (put_page_testzero(page)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001177 if (order == 0)
1178 free_hot_page(page);
1179 else
1180 __free_pages_ok(page, order);
1181 }
1182}
1183
1184EXPORT_SYMBOL(__free_pages);
1185
1186fastcall void free_pages(unsigned long addr, unsigned int order)
1187{
1188 if (addr != 0) {
Nick Piggin725d7042006-09-25 23:30:55 -07001189 VM_BUG_ON(!virt_addr_valid((void *)addr));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001190 __free_pages(virt_to_page((void *)addr), order);
1191 }
1192}
1193
1194EXPORT_SYMBOL(free_pages);
1195
1196/*
1197 * Total amount of free (allocatable) RAM:
1198 */
1199unsigned int nr_free_pages(void)
1200{
1201 unsigned int sum = 0;
1202 struct zone *zone;
1203
1204 for_each_zone(zone)
1205 sum += zone->free_pages;
1206
1207 return sum;
1208}
1209
1210EXPORT_SYMBOL(nr_free_pages);
1211
1212#ifdef CONFIG_NUMA
1213unsigned int nr_free_pages_pgdat(pg_data_t *pgdat)
1214{
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001215 unsigned int sum = 0;
1216 enum zone_type i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001217
1218 for (i = 0; i < MAX_NR_ZONES; i++)
1219 sum += pgdat->node_zones[i].free_pages;
1220
1221 return sum;
1222}
1223#endif
1224
1225static unsigned int nr_free_zone_pages(int offset)
1226{
Martin J. Blighe310fd42005-07-29 22:59:18 -07001227 /* Just pick one node, since fallback list is circular */
1228 pg_data_t *pgdat = NODE_DATA(numa_node_id());
Linus Torvalds1da177e2005-04-16 15:20:36 -07001229 unsigned int sum = 0;
1230
Martin J. Blighe310fd42005-07-29 22:59:18 -07001231 struct zonelist *zonelist = pgdat->node_zonelists + offset;
1232 struct zone **zonep = zonelist->zones;
1233 struct zone *zone;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001234
Martin J. Blighe310fd42005-07-29 22:59:18 -07001235 for (zone = *zonep++; zone; zone = *zonep++) {
1236 unsigned long size = zone->present_pages;
1237 unsigned long high = zone->pages_high;
1238 if (size > high)
1239 sum += size - high;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240 }
1241
1242 return sum;
1243}
1244
1245/*
1246 * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
1247 */
1248unsigned int nr_free_buffer_pages(void)
1249{
Al Viroaf4ca452005-10-21 02:55:38 -04001250 return nr_free_zone_pages(gfp_zone(GFP_USER));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001251}
1252
1253/*
1254 * Amount of free RAM allocatable within all zones
1255 */
1256unsigned int nr_free_pagecache_pages(void)
1257{
Al Viroaf4ca452005-10-21 02:55:38 -04001258 return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001259}
Christoph Lameter08e0f6a2006-09-27 01:50:06 -07001260
1261static inline void show_node(struct zone *zone)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001262{
Christoph Lameter08e0f6a2006-09-27 01:50:06 -07001263 if (NUMA_BUILD)
1264 printk("Node %ld ", zone_to_nid(zone));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001265}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001266
Linus Torvalds1da177e2005-04-16 15:20:36 -07001267void si_meminfo(struct sysinfo *val)
1268{
1269 val->totalram = totalram_pages;
1270 val->sharedram = 0;
1271 val->freeram = nr_free_pages();
1272 val->bufferram = nr_blockdev_pages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001273 val->totalhigh = totalhigh_pages;
1274 val->freehigh = nr_free_highpages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001275 val->mem_unit = PAGE_SIZE;
1276}
1277
1278EXPORT_SYMBOL(si_meminfo);
1279
1280#ifdef CONFIG_NUMA
1281void si_meminfo_node(struct sysinfo *val, int nid)
1282{
1283 pg_data_t *pgdat = NODE_DATA(nid);
1284
1285 val->totalram = pgdat->node_present_pages;
1286 val->freeram = nr_free_pages_pgdat(pgdat);
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07001287#ifdef CONFIG_HIGHMEM
Linus Torvalds1da177e2005-04-16 15:20:36 -07001288 val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
1289 val->freehigh = pgdat->node_zones[ZONE_HIGHMEM].free_pages;
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07001290#else
1291 val->totalhigh = 0;
1292 val->freehigh = 0;
1293#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294 val->mem_unit = PAGE_SIZE;
1295}
1296#endif
1297
1298#define K(x) ((x) << (PAGE_SHIFT-10))
1299
1300/*
1301 * Show free area list (used inside shift_scroll-lock stuff)
1302 * We also calculate the percentage fragmentation. We do this by counting the
1303 * memory on each free list with the exception of the first item on the list.
1304 */
1305void show_free_areas(void)
1306{
Jes Sorensenc7241912006-09-27 01:50:05 -07001307 int cpu;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001308 unsigned long active;
1309 unsigned long inactive;
1310 unsigned long free;
1311 struct zone *zone;
1312
1313 for_each_zone(zone) {
Jes Sorensenc7241912006-09-27 01:50:05 -07001314 if (!populated_zone(zone))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001315 continue;
Jes Sorensenc7241912006-09-27 01:50:05 -07001316
1317 show_node(zone);
1318 printk("%s per-cpu:\n", zone->name);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319
Dave Jones6b482c62005-11-10 15:45:56 -05001320 for_each_online_cpu(cpu) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001321 struct per_cpu_pageset *pageset;
1322
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001323 pageset = zone_pcp(zone, cpu);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001324
Jes Sorensenc7241912006-09-27 01:50:05 -07001325 printk("CPU %4d: Hot: hi:%5d, btch:%4d usd:%4d "
1326 "Cold: hi:%5d, btch:%4d usd:%4d\n",
1327 cpu, pageset->pcp[0].high,
1328 pageset->pcp[0].batch, pageset->pcp[0].count,
1329 pageset->pcp[1].high, pageset->pcp[1].batch,
1330 pageset->pcp[1].count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001331 }
1332 }
1333
Linus Torvalds1da177e2005-04-16 15:20:36 -07001334 get_zone_counts(&active, &inactive, &free);
1335
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336 printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu "
1337 "unstable:%lu free:%u slab:%lu mapped:%lu pagetables:%lu\n",
1338 active,
1339 inactive,
Christoph Lameterb1e7a8f2006-06-30 01:55:39 -07001340 global_page_state(NR_FILE_DIRTY),
Christoph Lameterce866b32006-06-30 01:55:40 -07001341 global_page_state(NR_WRITEBACK),
Christoph Lameterfd39fc82006-06-30 01:55:40 -07001342 global_page_state(NR_UNSTABLE_NFS),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001343 nr_free_pages(),
Christoph Lameter972d1a72006-09-25 23:31:51 -07001344 global_page_state(NR_SLAB_RECLAIMABLE) +
1345 global_page_state(NR_SLAB_UNRECLAIMABLE),
Christoph Lameter65ba55f2006-06-30 01:55:34 -07001346 global_page_state(NR_FILE_MAPPED),
Christoph Lameterdf849a12006-06-30 01:55:38 -07001347 global_page_state(NR_PAGETABLE));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001348
1349 for_each_zone(zone) {
1350 int i;
1351
Jes Sorensenc7241912006-09-27 01:50:05 -07001352 if (!populated_zone(zone))
1353 continue;
1354
Linus Torvalds1da177e2005-04-16 15:20:36 -07001355 show_node(zone);
1356 printk("%s"
1357 " free:%lukB"
1358 " min:%lukB"
1359 " low:%lukB"
1360 " high:%lukB"
1361 " active:%lukB"
1362 " inactive:%lukB"
1363 " present:%lukB"
1364 " pages_scanned:%lu"
1365 " all_unreclaimable? %s"
1366 "\n",
1367 zone->name,
1368 K(zone->free_pages),
1369 K(zone->pages_min),
1370 K(zone->pages_low),
1371 K(zone->pages_high),
1372 K(zone->nr_active),
1373 K(zone->nr_inactive),
1374 K(zone->present_pages),
1375 zone->pages_scanned,
1376 (zone->all_unreclaimable ? "yes" : "no")
1377 );
1378 printk("lowmem_reserve[]:");
1379 for (i = 0; i < MAX_NR_ZONES; i++)
1380 printk(" %lu", zone->lowmem_reserve[i]);
1381 printk("\n");
1382 }
1383
1384 for_each_zone(zone) {
Kirill Korotaev8f9de512006-06-23 02:03:50 -07001385 unsigned long nr[MAX_ORDER], flags, order, total = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386
Jes Sorensenc7241912006-09-27 01:50:05 -07001387 if (!populated_zone(zone))
1388 continue;
1389
Linus Torvalds1da177e2005-04-16 15:20:36 -07001390 show_node(zone);
1391 printk("%s: ", zone->name);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001392
1393 spin_lock_irqsave(&zone->lock, flags);
1394 for (order = 0; order < MAX_ORDER; order++) {
Kirill Korotaev8f9de512006-06-23 02:03:50 -07001395 nr[order] = zone->free_area[order].nr_free;
1396 total += nr[order] << order;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397 }
1398 spin_unlock_irqrestore(&zone->lock, flags);
Kirill Korotaev8f9de512006-06-23 02:03:50 -07001399 for (order = 0; order < MAX_ORDER; order++)
1400 printk("%lu*%lukB ", nr[order], K(1UL) << order);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 printk("= %lukB\n", K(total));
1402 }
1403
1404 show_swap_cache_info();
1405}
1406
1407/*
1408 * Builds allocation fallback zone lists.
Christoph Lameter1a932052006-01-06 00:11:16 -08001409 *
1410 * Add all populated zones of a node to the zonelist.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001411 */
Yasunori Goto86356ab2006-06-23 02:03:09 -07001412static int __meminit build_zonelists_node(pg_data_t *pgdat,
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001413 struct zonelist *zonelist, int nr_zones, enum zone_type zone_type)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001414{
Christoph Lameter1a932052006-01-06 00:11:16 -08001415 struct zone *zone;
1416
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07001417 BUG_ON(zone_type >= MAX_NR_ZONES);
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001418 zone_type++;
Christoph Lameter02a68a52006-01-06 00:11:18 -08001419
1420 do {
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001421 zone_type--;
Christoph Lameter070f8032006-01-06 00:11:19 -08001422 zone = pgdat->node_zones + zone_type;
Christoph Lameter1a932052006-01-06 00:11:16 -08001423 if (populated_zone(zone)) {
Christoph Lameter070f8032006-01-06 00:11:19 -08001424 zonelist->zones[nr_zones++] = zone;
1425 check_highest_zone(zone_type);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001426 }
Christoph Lameter02a68a52006-01-06 00:11:18 -08001427
Christoph Lameter2f6726e2006-09-25 23:31:18 -07001428 } while (zone_type);
Christoph Lameter070f8032006-01-06 00:11:19 -08001429 return nr_zones;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001430}
1431
1432#ifdef CONFIG_NUMA
1433#define MAX_NODE_LOAD (num_online_nodes())
Yasunori Goto86356ab2006-06-23 02:03:09 -07001434static int __meminitdata node_load[MAX_NUMNODES];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001435/**
Pavel Pisa4dc3b162005-05-01 08:59:25 -07001436 * 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 -07001437 * @node: node whose fallback list we're appending
1438 * @used_node_mask: nodemask_t of already used nodes
1439 *
1440 * We use a number of factors to determine which is the next node that should
1441 * appear on a given node's fallback list. The node should not have appeared
1442 * already in @node's fallback list, and it should be the next closest node
1443 * according to the distance array (which contains arbitrary distance values
1444 * from each node to each node in the system), and should also prefer nodes
1445 * with no CPUs, since presumably they'll have very little allocation pressure
1446 * on them otherwise.
1447 * It returns -1 if no node is found.
1448 */
Yasunori Goto86356ab2006-06-23 02:03:09 -07001449static int __meminit find_next_best_node(int node, nodemask_t *used_node_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450{
Linus Torvalds4cf808e2006-02-17 20:38:21 +01001451 int n, val;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001452 int min_val = INT_MAX;
1453 int best_node = -1;
1454
Linus Torvalds4cf808e2006-02-17 20:38:21 +01001455 /* Use the local node if we haven't already */
1456 if (!node_isset(node, *used_node_mask)) {
1457 node_set(node, *used_node_mask);
1458 return node;
1459 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001460
Linus Torvalds4cf808e2006-02-17 20:38:21 +01001461 for_each_online_node(n) {
1462 cpumask_t tmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001463
1464 /* Don't want a node to appear more than once */
1465 if (node_isset(n, *used_node_mask))
1466 continue;
1467
Linus Torvalds1da177e2005-04-16 15:20:36 -07001468 /* Use the distance array to find the distance */
1469 val = node_distance(node, n);
1470
Linus Torvalds4cf808e2006-02-17 20:38:21 +01001471 /* Penalize nodes under us ("prefer the next node") */
1472 val += (n < node);
1473
Linus Torvalds1da177e2005-04-16 15:20:36 -07001474 /* Give preference to headless and unused nodes */
1475 tmp = node_to_cpumask(n);
1476 if (!cpus_empty(tmp))
1477 val += PENALTY_FOR_NODE_WITH_CPUS;
1478
1479 /* Slight preference for less loaded node */
1480 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
1481 val += node_load[n];
1482
1483 if (val < min_val) {
1484 min_val = val;
1485 best_node = n;
1486 }
1487 }
1488
1489 if (best_node >= 0)
1490 node_set(best_node, *used_node_mask);
1491
1492 return best_node;
1493}
1494
Yasunori Goto86356ab2006-06-23 02:03:09 -07001495static void __meminit build_zonelists(pg_data_t *pgdat)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001496{
Christoph Lameter19655d32006-09-25 23:31:19 -07001497 int j, node, local_node;
1498 enum zone_type i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001499 int prev_node, load;
1500 struct zonelist *zonelist;
1501 nodemask_t used_mask;
1502
1503 /* initialize zonelists */
Christoph Lameter19655d32006-09-25 23:31:19 -07001504 for (i = 0; i < MAX_NR_ZONES; i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001505 zonelist = pgdat->node_zonelists + i;
1506 zonelist->zones[0] = NULL;
1507 }
1508
1509 /* NUMA-aware ordering of nodes */
1510 local_node = pgdat->node_id;
1511 load = num_online_nodes();
1512 prev_node = local_node;
1513 nodes_clear(used_mask);
1514 while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
Christoph Lameter9eeff232006-01-18 17:42:31 -08001515 int distance = node_distance(local_node, node);
1516
1517 /*
1518 * If another node is sufficiently far away then it is better
1519 * to reclaim pages in a zone before going off node.
1520 */
1521 if (distance > RECLAIM_DISTANCE)
1522 zone_reclaim_mode = 1;
1523
Linus Torvalds1da177e2005-04-16 15:20:36 -07001524 /*
1525 * We don't want to pressure a particular node.
1526 * So adding penalty to the first node in same
1527 * distance group to make it round-robin.
1528 */
Christoph Lameter9eeff232006-01-18 17:42:31 -08001529
1530 if (distance != node_distance(local_node, prev_node))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001531 node_load[node] += load;
1532 prev_node = node;
1533 load--;
Christoph Lameter19655d32006-09-25 23:31:19 -07001534 for (i = 0; i < MAX_NR_ZONES; i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001535 zonelist = pgdat->node_zonelists + i;
1536 for (j = 0; zonelist->zones[j] != NULL; j++);
1537
Christoph Lameter19655d32006-09-25 23:31:19 -07001538 j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001539 zonelist->zones[j] = NULL;
1540 }
1541 }
1542}
1543
1544#else /* CONFIG_NUMA */
1545
Yasunori Goto86356ab2006-06-23 02:03:09 -07001546static void __meminit build_zonelists(pg_data_t *pgdat)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001547{
Christoph Lameter19655d32006-09-25 23:31:19 -07001548 int node, local_node;
1549 enum zone_type i,j;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001550
1551 local_node = pgdat->node_id;
Christoph Lameter19655d32006-09-25 23:31:19 -07001552 for (i = 0; i < MAX_NR_ZONES; i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001553 struct zonelist *zonelist;
1554
1555 zonelist = pgdat->node_zonelists + i;
1556
Christoph Lameter19655d32006-09-25 23:31:19 -07001557 j = build_zonelists_node(pgdat, zonelist, 0, i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001558 /*
1559 * Now we build the zonelist so that it contains the zones
1560 * of all the other nodes.
1561 * We don't want to pressure a particular node, so when
1562 * building the zones for node N, we make sure that the
1563 * zones coming right after the local ones are those from
1564 * node N+1 (modulo N)
1565 */
1566 for (node = local_node + 1; node < MAX_NUMNODES; node++) {
1567 if (!node_online(node))
1568 continue;
Christoph Lameter19655d32006-09-25 23:31:19 -07001569 j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001570 }
1571 for (node = 0; node < local_node; node++) {
1572 if (!node_online(node))
1573 continue;
Christoph Lameter19655d32006-09-25 23:31:19 -07001574 j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001575 }
1576
1577 zonelist->zones[j] = NULL;
1578 }
1579}
1580
1581#endif /* CONFIG_NUMA */
1582
Yasunori Goto68113782006-06-23 02:03:11 -07001583/* return values int ....just for stop_machine_run() */
1584static int __meminit __build_all_zonelists(void *dummy)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001585{
Yasunori Goto68113782006-06-23 02:03:11 -07001586 int nid;
1587 for_each_online_node(nid)
1588 build_zonelists(NODE_DATA(nid));
1589 return 0;
1590}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001591
Yasunori Goto68113782006-06-23 02:03:11 -07001592void __meminit build_all_zonelists(void)
1593{
1594 if (system_state == SYSTEM_BOOTING) {
Randy Dunlap423b41d2006-09-27 01:50:12 -07001595 __build_all_zonelists(NULL);
Yasunori Goto68113782006-06-23 02:03:11 -07001596 cpuset_init_current_mems_allowed();
1597 } else {
1598 /* we have to stop all cpus to guaranntee there is no user
1599 of zonelist */
1600 stop_machine_run(__build_all_zonelists, NULL, NR_CPUS);
1601 /* cpuset refresh routine should be here */
1602 }
Andrew Mortonbd1e22b2006-06-23 02:03:47 -07001603 vm_total_pages = nr_free_pagecache_pages();
1604 printk("Built %i zonelists. Total pages: %ld\n",
1605 num_online_nodes(), vm_total_pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001606}
1607
1608/*
1609 * Helper functions to size the waitqueue hash table.
1610 * Essentially these want to choose hash table sizes sufficiently
1611 * large so that collisions trying to wait on pages are rare.
1612 * But in fact, the number of active page waitqueues on typical
1613 * systems is ridiculously low, less than 200. So this is even
1614 * conservative, even though it seems large.
1615 *
1616 * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
1617 * waitqueues, i.e. the size of the waitq table given the number of pages.
1618 */
1619#define PAGES_PER_WAITQUEUE 256
1620
Yasunori Gotocca448f2006-06-23 02:03:10 -07001621#ifndef CONFIG_MEMORY_HOTPLUG
Yasunori Goto02b694d2006-06-23 02:03:08 -07001622static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001623{
1624 unsigned long size = 1;
1625
1626 pages /= PAGES_PER_WAITQUEUE;
1627
1628 while (size < pages)
1629 size <<= 1;
1630
1631 /*
1632 * Once we have dozens or even hundreds of threads sleeping
1633 * on IO we've got bigger problems than wait queue collision.
1634 * Limit the size of the wait table to a reasonable size.
1635 */
1636 size = min(size, 4096UL);
1637
1638 return max(size, 4UL);
1639}
Yasunori Gotocca448f2006-06-23 02:03:10 -07001640#else
1641/*
1642 * A zone's size might be changed by hot-add, so it is not possible to determine
1643 * a suitable size for its wait_table. So we use the maximum size now.
1644 *
1645 * The max wait table size = 4096 x sizeof(wait_queue_head_t). ie:
1646 *
1647 * i386 (preemption config) : 4096 x 16 = 64Kbyte.
1648 * ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
1649 * ia64, x86-64 (preemption) : 4096 x 24 = 96Kbyte.
1650 *
1651 * The maximum entries are prepared when a zone's memory is (512K + 256) pages
1652 * or more by the traditional way. (See above). It equals:
1653 *
1654 * i386, x86-64, powerpc(4K page size) : = ( 2G + 1M)byte.
1655 * ia64(16K page size) : = ( 8G + 4M)byte.
1656 * powerpc (64K page size) : = (32G +16M)byte.
1657 */
1658static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
1659{
1660 return 4096UL;
1661}
1662#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001663
1664/*
1665 * This is an integer logarithm so that shifts can be used later
1666 * to extract the more random high bits from the multiplicative
1667 * hash function before the remainder is taken.
1668 */
1669static inline unsigned long wait_table_bits(unsigned long size)
1670{
1671 return ffz(~size);
1672}
1673
1674#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
1675
Linus Torvalds1da177e2005-04-16 15:20:36 -07001676/*
1677 * Initially all pages are reserved - free ones are freed
1678 * up by free_all_bootmem() once the early boot process is
1679 * done. Non-atomic initialization, single-pass.
1680 */
Matt Tolentinoc09b4242006-01-17 07:03:44 +01001681void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001682 unsigned long start_pfn)
1683{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001684 struct page *page;
Andy Whitcroft29751f62005-06-23 00:08:00 -07001685 unsigned long end_pfn = start_pfn + size;
1686 unsigned long pfn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001687
Greg Ungerercbe8dd42006-01-12 01:05:24 -08001688 for (pfn = start_pfn; pfn < end_pfn; pfn++) {
Andy Whitcroftd41dee32005-06-23 00:07:54 -07001689 if (!early_pfn_valid(pfn))
1690 continue;
1691 page = pfn_to_page(pfn);
1692 set_page_links(page, zone, nid, pfn);
Nick Piggin7835e982006-03-22 00:08:40 -08001693 init_page_count(page);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001694 reset_page_mapcount(page);
1695 SetPageReserved(page);
1696 INIT_LIST_HEAD(&page->lru);
1697#ifdef WANT_PAGE_VIRTUAL
1698 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
1699 if (!is_highmem_idx(zone))
Bob Picco3212c6b2005-06-27 14:36:28 -07001700 set_page_address(page, __va(pfn << PAGE_SHIFT));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001701#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001702 }
1703}
1704
1705void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone,
1706 unsigned long size)
1707{
1708 int order;
1709 for (order = 0; order < MAX_ORDER ; order++) {
1710 INIT_LIST_HEAD(&zone->free_area[order].free_list);
1711 zone->free_area[order].nr_free = 0;
1712 }
1713}
1714
Andy Whitcroftd41dee32005-06-23 00:07:54 -07001715#define ZONETABLE_INDEX(x, zone_nr) ((x << ZONES_SHIFT) | zone_nr)
Christoph Lameter2f1b6242006-09-25 23:31:13 -07001716void zonetable_add(struct zone *zone, int nid, enum zone_type zid,
1717 unsigned long pfn, unsigned long size)
Andy Whitcroftd41dee32005-06-23 00:07:54 -07001718{
1719 unsigned long snum = pfn_to_section_nr(pfn);
1720 unsigned long end = pfn_to_section_nr(pfn + size);
1721
1722 if (FLAGS_HAS_NODE)
1723 zone_table[ZONETABLE_INDEX(nid, zid)] = zone;
1724 else
1725 for (; snum <= end; snum++)
1726 zone_table[ZONETABLE_INDEX(snum, zid)] = zone;
1727}
1728
Linus Torvalds1da177e2005-04-16 15:20:36 -07001729#ifndef __HAVE_ARCH_MEMMAP_INIT
1730#define memmap_init(size, nid, zone, start_pfn) \
1731 memmap_init_zone((size), (nid), (zone), (start_pfn))
1732#endif
1733
Ashok Raj6292d9a2006-02-01 03:04:44 -08001734static int __cpuinit zone_batchsize(struct zone *zone)
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001735{
1736 int batch;
1737
1738 /*
1739 * The per-cpu-pages pools are set to around 1000th of the
Seth, Rohitba56e912005-10-29 18:15:47 -07001740 * size of the zone. But no more than 1/2 of a meg.
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001741 *
1742 * OK, so we don't know how big the cache is. So guess.
1743 */
1744 batch = zone->present_pages / 1024;
Seth, Rohitba56e912005-10-29 18:15:47 -07001745 if (batch * PAGE_SIZE > 512 * 1024)
1746 batch = (512 * 1024) / PAGE_SIZE;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001747 batch /= 4; /* We effectively *= 4 below */
1748 if (batch < 1)
1749 batch = 1;
1750
1751 /*
Nick Piggin0ceaacc2005-12-04 13:55:25 +11001752 * Clamp the batch to a 2^n - 1 value. Having a power
1753 * of 2 value was found to be more likely to have
1754 * suboptimal cache aliasing properties in some cases.
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001755 *
Nick Piggin0ceaacc2005-12-04 13:55:25 +11001756 * For example if 2 tasks are alternately allocating
1757 * batches of pages, one task can end up with a lot
1758 * of pages of one half of the possible page colors
1759 * and the other with pages of the other colors.
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001760 */
Nick Piggin0ceaacc2005-12-04 13:55:25 +11001761 batch = (1 << (fls(batch + batch/2)-1)) - 1;
Seth, Rohitba56e912005-10-29 18:15:47 -07001762
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001763 return batch;
1764}
1765
Christoph Lameter2caaad42005-06-21 17:15:00 -07001766inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
1767{
1768 struct per_cpu_pages *pcp;
1769
Magnus Damm1c6fe942005-10-26 01:58:59 -07001770 memset(p, 0, sizeof(*p));
1771
Christoph Lameter2caaad42005-06-21 17:15:00 -07001772 pcp = &p->pcp[0]; /* hot */
1773 pcp->count = 0;
Christoph Lameter2caaad42005-06-21 17:15:00 -07001774 pcp->high = 6 * batch;
1775 pcp->batch = max(1UL, 1 * batch);
1776 INIT_LIST_HEAD(&pcp->list);
1777
1778 pcp = &p->pcp[1]; /* cold*/
1779 pcp->count = 0;
Christoph Lameter2caaad42005-06-21 17:15:00 -07001780 pcp->high = 2 * batch;
Seth, Rohite46a5e22005-10-29 18:15:48 -07001781 pcp->batch = max(1UL, batch/2);
Christoph Lameter2caaad42005-06-21 17:15:00 -07001782 INIT_LIST_HEAD(&pcp->list);
1783}
1784
Rohit Seth8ad4b1f2006-01-08 01:00:40 -08001785/*
1786 * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
1787 * to the value high for the pageset p.
1788 */
1789
1790static void setup_pagelist_highmark(struct per_cpu_pageset *p,
1791 unsigned long high)
1792{
1793 struct per_cpu_pages *pcp;
1794
1795 pcp = &p->pcp[0]; /* hot list */
1796 pcp->high = high;
1797 pcp->batch = max(1UL, high/4);
1798 if ((high/4) > (PAGE_SHIFT * 8))
1799 pcp->batch = PAGE_SHIFT * 8;
1800}
1801
1802
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001803#ifdef CONFIG_NUMA
1804/*
Christoph Lameter2caaad42005-06-21 17:15:00 -07001805 * Boot pageset table. One per cpu which is going to be used for all
1806 * zones and all nodes. The parameters will be set in such a way
1807 * that an item put on a list will immediately be handed over to
1808 * the buddy list. This is safe since pageset manipulation is done
1809 * with interrupts disabled.
1810 *
1811 * Some NUMA counter updates may also be caught by the boot pagesets.
Christoph Lameterb7c84c62005-06-22 20:26:07 -07001812 *
1813 * The boot_pagesets must be kept even after bootup is complete for
1814 * unused processors and/or zones. They do play a role for bootstrapping
1815 * hotplugged processors.
1816 *
1817 * zoneinfo_show() and maybe other functions do
1818 * not check if the processor is online before following the pageset pointer.
1819 * Other parts of the kernel may not check if the zone is available.
Christoph Lameter2caaad42005-06-21 17:15:00 -07001820 */
Eric Dumazet88a2a4ac2006-02-04 23:27:36 -08001821static struct per_cpu_pageset boot_pageset[NR_CPUS];
Christoph Lameter2caaad42005-06-21 17:15:00 -07001822
1823/*
1824 * Dynamically allocate memory for the
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001825 * per cpu pageset array in struct zone.
1826 */
Ashok Raj6292d9a2006-02-01 03:04:44 -08001827static int __cpuinit process_zones(int cpu)
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001828{
1829 struct zone *zone, *dzone;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001830
1831 for_each_zone(zone) {
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001832
Christoph Lameter66a55032006-09-27 01:50:09 -07001833 if (!populated_zone(zone))
1834 continue;
1835
Nick Piggin23316bc2006-01-08 01:00:41 -08001836 zone_pcp(zone, cpu) = kmalloc_node(sizeof(struct per_cpu_pageset),
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001837 GFP_KERNEL, cpu_to_node(cpu));
Nick Piggin23316bc2006-01-08 01:00:41 -08001838 if (!zone_pcp(zone, cpu))
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001839 goto bad;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001840
Nick Piggin23316bc2006-01-08 01:00:41 -08001841 setup_pageset(zone_pcp(zone, cpu), zone_batchsize(zone));
Rohit Seth8ad4b1f2006-01-08 01:00:40 -08001842
1843 if (percpu_pagelist_fraction)
1844 setup_pagelist_highmark(zone_pcp(zone, cpu),
1845 (zone->present_pages / percpu_pagelist_fraction));
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001846 }
1847
1848 return 0;
1849bad:
1850 for_each_zone(dzone) {
1851 if (dzone == zone)
1852 break;
Nick Piggin23316bc2006-01-08 01:00:41 -08001853 kfree(zone_pcp(dzone, cpu));
1854 zone_pcp(dzone, cpu) = NULL;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001855 }
1856 return -ENOMEM;
1857}
1858
1859static inline void free_zone_pagesets(int cpu)
1860{
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001861 struct zone *zone;
1862
1863 for_each_zone(zone) {
1864 struct per_cpu_pageset *pset = zone_pcp(zone, cpu);
1865
David Rientjesf3ef9ea2006-09-25 16:24:57 -07001866 /* Free per_cpu_pageset if it is slab allocated */
1867 if (pset != &boot_pageset[cpu])
1868 kfree(pset);
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001869 zone_pcp(zone, cpu) = NULL;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001870 }
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001871}
1872
Chandra Seetharaman9c7b2162006-06-27 02:54:07 -07001873static int __cpuinit pageset_cpuup_callback(struct notifier_block *nfb,
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001874 unsigned long action,
1875 void *hcpu)
1876{
1877 int cpu = (long)hcpu;
1878 int ret = NOTIFY_OK;
1879
1880 switch (action) {
1881 case CPU_UP_PREPARE:
1882 if (process_zones(cpu))
1883 ret = NOTIFY_BAD;
1884 break;
Andi Kleenb0d41692005-11-05 17:25:53 +01001885 case CPU_UP_CANCELED:
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001886 case CPU_DEAD:
1887 free_zone_pagesets(cpu);
1888 break;
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001889 default:
1890 break;
1891 }
1892 return ret;
1893}
1894
Chandra Seetharaman74b85f32006-06-27 02:54:09 -07001895static struct notifier_block __cpuinitdata pageset_notifier =
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001896 { &pageset_cpuup_callback, NULL, 0 };
1897
Al Viro78d99552005-12-15 09:18:25 +00001898void __init setup_per_cpu_pageset(void)
Christoph Lametere7c8d5c2005-06-21 17:14:47 -07001899{
1900 int err;
1901
1902 /* Initialize per_cpu_pageset for cpu 0.
1903 * A cpuup callback will do this for every cpu
1904 * as it comes online
1905 */
1906 err = process_zones(smp_processor_id());
1907 BUG_ON(err);
1908 register_cpu_notifier(&pageset_notifier);
1909}
1910
1911#endif
1912
Matt Tolentinoc09b4242006-01-17 07:03:44 +01001913static __meminit
Yasunori Gotocca448f2006-06-23 02:03:10 -07001914int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
Dave Hansened8ece22005-10-29 18:16:50 -07001915{
1916 int i;
1917 struct pglist_data *pgdat = zone->zone_pgdat;
Yasunori Gotocca448f2006-06-23 02:03:10 -07001918 size_t alloc_size;
Dave Hansened8ece22005-10-29 18:16:50 -07001919
1920 /*
1921 * The per-page waitqueue mechanism uses hashed waitqueues
1922 * per zone.
1923 */
Yasunori Goto02b694d2006-06-23 02:03:08 -07001924 zone->wait_table_hash_nr_entries =
1925 wait_table_hash_nr_entries(zone_size_pages);
1926 zone->wait_table_bits =
1927 wait_table_bits(zone->wait_table_hash_nr_entries);
Yasunori Gotocca448f2006-06-23 02:03:10 -07001928 alloc_size = zone->wait_table_hash_nr_entries
1929 * sizeof(wait_queue_head_t);
1930
1931 if (system_state == SYSTEM_BOOTING) {
1932 zone->wait_table = (wait_queue_head_t *)
1933 alloc_bootmem_node(pgdat, alloc_size);
1934 } else {
1935 /*
1936 * This case means that a zone whose size was 0 gets new memory
1937 * via memory hot-add.
1938 * But it may be the case that a new node was hot-added. In
1939 * this case vmalloc() will not be able to use this new node's
1940 * memory - this wait_table must be initialized to use this new
1941 * node itself as well.
1942 * To use this new node's memory, further consideration will be
1943 * necessary.
1944 */
1945 zone->wait_table = (wait_queue_head_t *)vmalloc(alloc_size);
1946 }
1947 if (!zone->wait_table)
1948 return -ENOMEM;
Dave Hansened8ece22005-10-29 18:16:50 -07001949
Yasunori Goto02b694d2006-06-23 02:03:08 -07001950 for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
Dave Hansened8ece22005-10-29 18:16:50 -07001951 init_waitqueue_head(zone->wait_table + i);
Yasunori Gotocca448f2006-06-23 02:03:10 -07001952
1953 return 0;
Dave Hansened8ece22005-10-29 18:16:50 -07001954}
1955
Matt Tolentinoc09b4242006-01-17 07:03:44 +01001956static __meminit void zone_pcp_init(struct zone *zone)
Dave Hansened8ece22005-10-29 18:16:50 -07001957{
1958 int cpu;
1959 unsigned long batch = zone_batchsize(zone);
1960
1961 for (cpu = 0; cpu < NR_CPUS; cpu++) {
1962#ifdef CONFIG_NUMA
1963 /* Early boot. Slab allocator not functional yet */
Nick Piggin23316bc2006-01-08 01:00:41 -08001964 zone_pcp(zone, cpu) = &boot_pageset[cpu];
Dave Hansened8ece22005-10-29 18:16:50 -07001965 setup_pageset(&boot_pageset[cpu],0);
1966#else
1967 setup_pageset(zone_pcp(zone,cpu), batch);
1968#endif
1969 }
Anton Blanchardf5335c02006-03-25 03:06:49 -08001970 if (zone->present_pages)
1971 printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n",
1972 zone->name, zone->present_pages, batch);
Dave Hansened8ece22005-10-29 18:16:50 -07001973}
1974
Yasunori Goto718127c2006-06-23 02:03:10 -07001975__meminit int init_currently_empty_zone(struct zone *zone,
1976 unsigned long zone_start_pfn,
1977 unsigned long size)
Dave Hansened8ece22005-10-29 18:16:50 -07001978{
1979 struct pglist_data *pgdat = zone->zone_pgdat;
Yasunori Gotocca448f2006-06-23 02:03:10 -07001980 int ret;
1981 ret = zone_wait_table_init(zone, size);
1982 if (ret)
1983 return ret;
Dave Hansened8ece22005-10-29 18:16:50 -07001984 pgdat->nr_zones = zone_idx(zone) + 1;
1985
Dave Hansened8ece22005-10-29 18:16:50 -07001986 zone->zone_start_pfn = zone_start_pfn;
1987
1988 memmap_init(size, pgdat->node_id, zone_idx(zone), zone_start_pfn);
1989
1990 zone_init_free_lists(pgdat, zone, zone->spanned_pages);
Yasunori Goto718127c2006-06-23 02:03:10 -07001991
1992 return 0;
Dave Hansened8ece22005-10-29 18:16:50 -07001993}
1994
Mel Gormanc7132162006-09-27 01:49:43 -07001995#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
1996/*
1997 * Basic iterator support. Return the first range of PFNs for a node
1998 * Note: nid == MAX_NUMNODES returns first region regardless of node
1999 */
2000static int __init first_active_region_index_in_nid(int nid)
2001{
2002 int i;
2003
2004 for (i = 0; i < nr_nodemap_entries; i++)
2005 if (nid == MAX_NUMNODES || early_node_map[i].nid == nid)
2006 return i;
2007
2008 return -1;
2009}
2010
2011/*
2012 * Basic iterator support. Return the next active range of PFNs for a node
2013 * Note: nid == MAX_NUMNODES returns next region regardles of node
2014 */
2015static int __init next_active_region_index_in_nid(int index, int nid)
2016{
2017 for (index = index + 1; index < nr_nodemap_entries; index++)
2018 if (nid == MAX_NUMNODES || early_node_map[index].nid == nid)
2019 return index;
2020
2021 return -1;
2022}
2023
2024#ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
2025/*
2026 * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
2027 * Architectures may implement their own version but if add_active_range()
2028 * was used and there are no special requirements, this is a convenient
2029 * alternative
2030 */
2031int __init early_pfn_to_nid(unsigned long pfn)
2032{
2033 int i;
2034
2035 for (i = 0; i < nr_nodemap_entries; i++) {
2036 unsigned long start_pfn = early_node_map[i].start_pfn;
2037 unsigned long end_pfn = early_node_map[i].end_pfn;
2038
2039 if (start_pfn <= pfn && pfn < end_pfn)
2040 return early_node_map[i].nid;
2041 }
2042
2043 return 0;
2044}
2045#endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
2046
2047/* Basic iterator support to walk early_node_map[] */
2048#define for_each_active_range_index_in_nid(i, nid) \
2049 for (i = first_active_region_index_in_nid(nid); i != -1; \
2050 i = next_active_region_index_in_nid(i, nid))
2051
2052/**
2053 * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002054 * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
2055 * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
Mel Gormanc7132162006-09-27 01:49:43 -07002056 *
2057 * If an architecture guarantees that all ranges registered with
2058 * add_active_ranges() contain no holes and may be freed, this
2059 * this function may be used instead of calling free_bootmem() manually.
2060 */
2061void __init free_bootmem_with_active_regions(int nid,
2062 unsigned long max_low_pfn)
2063{
2064 int i;
2065
2066 for_each_active_range_index_in_nid(i, nid) {
2067 unsigned long size_pages = 0;
2068 unsigned long end_pfn = early_node_map[i].end_pfn;
2069
2070 if (early_node_map[i].start_pfn >= max_low_pfn)
2071 continue;
2072
2073 if (end_pfn > max_low_pfn)
2074 end_pfn = max_low_pfn;
2075
2076 size_pages = end_pfn - early_node_map[i].start_pfn;
2077 free_bootmem_node(NODE_DATA(early_node_map[i].nid),
2078 PFN_PHYS(early_node_map[i].start_pfn),
2079 size_pages << PAGE_SHIFT);
2080 }
2081}
2082
2083/**
2084 * sparse_memory_present_with_active_regions - Call memory_present for each active range
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002085 * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
Mel Gormanc7132162006-09-27 01:49:43 -07002086 *
2087 * If an architecture guarantees that all ranges registered with
2088 * add_active_ranges() contain no holes and may be freed, this
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002089 * function may be used instead of calling memory_present() manually.
Mel Gormanc7132162006-09-27 01:49:43 -07002090 */
2091void __init sparse_memory_present_with_active_regions(int nid)
2092{
2093 int i;
2094
2095 for_each_active_range_index_in_nid(i, nid)
2096 memory_present(early_node_map[i].nid,
2097 early_node_map[i].start_pfn,
2098 early_node_map[i].end_pfn);
2099}
2100
2101/**
Mel Gormanfb014392006-09-27 01:49:59 -07002102 * push_node_boundaries - Push node boundaries to at least the requested boundary
2103 * @nid: The nid of the node to push the boundary for
2104 * @start_pfn: The start pfn of the node
2105 * @end_pfn: The end pfn of the node
2106 *
2107 * In reserve-based hot-add, mem_map is allocated that is unused until hotadd
2108 * time. Specifically, on x86_64, SRAT will report ranges that can potentially
2109 * be hotplugged even though no physical memory exists. This function allows
2110 * an arch to push out the node boundaries so mem_map is allocated that can
2111 * be used later.
2112 */
2113#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
2114void __init push_node_boundaries(unsigned int nid,
2115 unsigned long start_pfn, unsigned long end_pfn)
2116{
2117 printk(KERN_DEBUG "Entering push_node_boundaries(%u, %lu, %lu)\n",
2118 nid, start_pfn, end_pfn);
2119
2120 /* Initialise the boundary for this node if necessary */
2121 if (node_boundary_end_pfn[nid] == 0)
2122 node_boundary_start_pfn[nid] = -1UL;
2123
2124 /* Update the boundaries */
2125 if (node_boundary_start_pfn[nid] > start_pfn)
2126 node_boundary_start_pfn[nid] = start_pfn;
2127 if (node_boundary_end_pfn[nid] < end_pfn)
2128 node_boundary_end_pfn[nid] = end_pfn;
2129}
2130
2131/* If necessary, push the node boundary out for reserve hotadd */
2132static void __init account_node_boundary(unsigned int nid,
2133 unsigned long *start_pfn, unsigned long *end_pfn)
2134{
2135 printk(KERN_DEBUG "Entering account_node_boundary(%u, %lu, %lu)\n",
2136 nid, *start_pfn, *end_pfn);
2137
2138 /* Return if boundary information has not been provided */
2139 if (node_boundary_end_pfn[nid] == 0)
2140 return;
2141
2142 /* Check the boundaries and update if necessary */
2143 if (node_boundary_start_pfn[nid] < *start_pfn)
2144 *start_pfn = node_boundary_start_pfn[nid];
2145 if (node_boundary_end_pfn[nid] > *end_pfn)
2146 *end_pfn = node_boundary_end_pfn[nid];
2147}
2148#else
2149void __init push_node_boundaries(unsigned int nid,
2150 unsigned long start_pfn, unsigned long end_pfn) {}
2151
2152static void __init account_node_boundary(unsigned int nid,
2153 unsigned long *start_pfn, unsigned long *end_pfn) {}
2154#endif
2155
2156
2157/**
Mel Gormanc7132162006-09-27 01:49:43 -07002158 * get_pfn_range_for_nid - Return the start and end page frames for a node
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002159 * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
2160 * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
2161 * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
Mel Gormanc7132162006-09-27 01:49:43 -07002162 *
2163 * It returns the start and end page frame of a node based on information
2164 * provided by an arch calling add_active_range(). If called for a node
2165 * with no available memory, a warning is printed and the start and end
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002166 * PFNs will be 0.
Mel Gormanc7132162006-09-27 01:49:43 -07002167 */
2168void __init get_pfn_range_for_nid(unsigned int nid,
2169 unsigned long *start_pfn, unsigned long *end_pfn)
2170{
2171 int i;
2172 *start_pfn = -1UL;
2173 *end_pfn = 0;
2174
2175 for_each_active_range_index_in_nid(i, nid) {
2176 *start_pfn = min(*start_pfn, early_node_map[i].start_pfn);
2177 *end_pfn = max(*end_pfn, early_node_map[i].end_pfn);
2178 }
2179
2180 if (*start_pfn == -1UL) {
2181 printk(KERN_WARNING "Node %u active with no memory\n", nid);
2182 *start_pfn = 0;
2183 }
Mel Gormanfb014392006-09-27 01:49:59 -07002184
2185 /* Push the node boundaries out if requested */
2186 account_node_boundary(nid, start_pfn, end_pfn);
Mel Gormanc7132162006-09-27 01:49:43 -07002187}
2188
2189/*
2190 * Return the number of pages a zone spans in a node, including holes
2191 * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
2192 */
2193unsigned long __init zone_spanned_pages_in_node(int nid,
2194 unsigned long zone_type,
2195 unsigned long *ignored)
2196{
2197 unsigned long node_start_pfn, node_end_pfn;
2198 unsigned long zone_start_pfn, zone_end_pfn;
2199
2200 /* Get the start and end of the node and zone */
2201 get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
2202 zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
2203 zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
2204
2205 /* Check that this node has pages within the zone's required range */
2206 if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
2207 return 0;
2208
2209 /* Move the zone boundaries inside the node if necessary */
2210 zone_end_pfn = min(zone_end_pfn, node_end_pfn);
2211 zone_start_pfn = max(zone_start_pfn, node_start_pfn);
2212
2213 /* Return the spanned pages */
2214 return zone_end_pfn - zone_start_pfn;
2215}
2216
2217/*
2218 * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002219 * then all holes in the requested range will be accounted for.
Mel Gormanc7132162006-09-27 01:49:43 -07002220 */
2221unsigned long __init __absent_pages_in_range(int nid,
2222 unsigned long range_start_pfn,
2223 unsigned long range_end_pfn)
2224{
2225 int i = 0;
2226 unsigned long prev_end_pfn = 0, hole_pages = 0;
2227 unsigned long start_pfn;
2228
2229 /* Find the end_pfn of the first active range of pfns in the node */
2230 i = first_active_region_index_in_nid(nid);
2231 if (i == -1)
2232 return 0;
2233
Mel Gorman9c7cd682006-09-27 01:49:58 -07002234 /* Account for ranges before physical memory on this node */
2235 if (early_node_map[i].start_pfn > range_start_pfn)
2236 hole_pages = early_node_map[i].start_pfn - range_start_pfn;
2237
Mel Gormanc7132162006-09-27 01:49:43 -07002238 prev_end_pfn = early_node_map[i].start_pfn;
2239
2240 /* Find all holes for the zone within the node */
2241 for (; i != -1; i = next_active_region_index_in_nid(i, nid)) {
2242
2243 /* No need to continue if prev_end_pfn is outside the zone */
2244 if (prev_end_pfn >= range_end_pfn)
2245 break;
2246
2247 /* Make sure the end of the zone is not within the hole */
2248 start_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
2249 prev_end_pfn = max(prev_end_pfn, range_start_pfn);
2250
2251 /* Update the hole size cound and move on */
2252 if (start_pfn > range_start_pfn) {
2253 BUG_ON(prev_end_pfn > start_pfn);
2254 hole_pages += start_pfn - prev_end_pfn;
2255 }
2256 prev_end_pfn = early_node_map[i].end_pfn;
2257 }
2258
Mel Gorman9c7cd682006-09-27 01:49:58 -07002259 /* Account for ranges past physical memory on this node */
2260 if (range_end_pfn > prev_end_pfn)
2261 hole_pages = range_end_pfn -
2262 max(range_start_pfn, prev_end_pfn);
2263
Mel Gormanc7132162006-09-27 01:49:43 -07002264 return hole_pages;
2265}
2266
2267/**
2268 * absent_pages_in_range - Return number of page frames in holes within a range
2269 * @start_pfn: The start PFN to start searching for holes
2270 * @end_pfn: The end PFN to stop searching for holes
2271 *
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002272 * It returns the number of pages frames in memory holes within a range.
Mel Gormanc7132162006-09-27 01:49:43 -07002273 */
2274unsigned long __init absent_pages_in_range(unsigned long start_pfn,
2275 unsigned long end_pfn)
2276{
2277 return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
2278}
2279
2280/* Return the number of page frames in holes in a zone on a node */
2281unsigned long __init zone_absent_pages_in_node(int nid,
2282 unsigned long zone_type,
2283 unsigned long *ignored)
2284{
Mel Gorman9c7cd682006-09-27 01:49:58 -07002285 unsigned long node_start_pfn, node_end_pfn;
2286 unsigned long zone_start_pfn, zone_end_pfn;
2287
2288 get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
2289 zone_start_pfn = max(arch_zone_lowest_possible_pfn[zone_type],
2290 node_start_pfn);
2291 zone_end_pfn = min(arch_zone_highest_possible_pfn[zone_type],
2292 node_end_pfn);
2293
2294 return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
Mel Gormanc7132162006-09-27 01:49:43 -07002295}
Mel Gorman0e0b8642006-09-27 01:49:56 -07002296
Mel Gormanc7132162006-09-27 01:49:43 -07002297#else
2298static inline unsigned long zone_spanned_pages_in_node(int nid,
2299 unsigned long zone_type,
2300 unsigned long *zones_size)
2301{
2302 return zones_size[zone_type];
2303}
2304
2305static inline unsigned long zone_absent_pages_in_node(int nid,
2306 unsigned long zone_type,
2307 unsigned long *zholes_size)
2308{
2309 if (!zholes_size)
2310 return 0;
2311
2312 return zholes_size[zone_type];
2313}
Mel Gorman0e0b8642006-09-27 01:49:56 -07002314
Mel Gormanc7132162006-09-27 01:49:43 -07002315#endif
2316
2317static void __init calculate_node_totalpages(struct pglist_data *pgdat,
2318 unsigned long *zones_size, unsigned long *zholes_size)
2319{
2320 unsigned long realtotalpages, totalpages = 0;
2321 enum zone_type i;
2322
2323 for (i = 0; i < MAX_NR_ZONES; i++)
2324 totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
2325 zones_size);
2326 pgdat->node_spanned_pages = totalpages;
2327
2328 realtotalpages = totalpages;
2329 for (i = 0; i < MAX_NR_ZONES; i++)
2330 realtotalpages -=
2331 zone_absent_pages_in_node(pgdat->node_id, i,
2332 zholes_size);
2333 pgdat->node_present_pages = realtotalpages;
2334 printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
2335 realtotalpages);
2336}
2337
Linus Torvalds1da177e2005-04-16 15:20:36 -07002338/*
2339 * Set up the zone data structures:
2340 * - mark all pages reserved
2341 * - mark all memory queues empty
2342 * - clear the memory bitmaps
2343 */
Yasunori Goto86356ab2006-06-23 02:03:09 -07002344static void __meminit free_area_init_core(struct pglist_data *pgdat,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002345 unsigned long *zones_size, unsigned long *zholes_size)
2346{
Christoph Lameter2f1b6242006-09-25 23:31:13 -07002347 enum zone_type j;
Dave Hansened8ece22005-10-29 18:16:50 -07002348 int nid = pgdat->node_id;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002349 unsigned long zone_start_pfn = pgdat->node_start_pfn;
Yasunori Goto718127c2006-06-23 02:03:10 -07002350 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002351
Dave Hansen208d54e2005-10-29 18:16:52 -07002352 pgdat_resize_init(pgdat);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002353 pgdat->nr_zones = 0;
2354 init_waitqueue_head(&pgdat->kswapd_wait);
2355 pgdat->kswapd_max_order = 0;
2356
2357 for (j = 0; j < MAX_NR_ZONES; j++) {
2358 struct zone *zone = pgdat->node_zones + j;
Mel Gorman0e0b8642006-09-27 01:49:56 -07002359 unsigned long size, realsize, memmap_pages;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002360
Mel Gormanc7132162006-09-27 01:49:43 -07002361 size = zone_spanned_pages_in_node(nid, j, zones_size);
2362 realsize = size - zone_absent_pages_in_node(nid, j,
2363 zholes_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002364
Mel Gorman0e0b8642006-09-27 01:49:56 -07002365 /*
2366 * Adjust realsize so that it accounts for how much memory
2367 * is used by this zone for memmap. This affects the watermark
2368 * and per-cpu initialisations
2369 */
2370 memmap_pages = (size * sizeof(struct page)) >> PAGE_SHIFT;
2371 if (realsize >= memmap_pages) {
2372 realsize -= memmap_pages;
2373 printk(KERN_DEBUG
2374 " %s zone: %lu pages used for memmap\n",
2375 zone_names[j], memmap_pages);
2376 } else
2377 printk(KERN_WARNING
2378 " %s zone: %lu pages exceeds realsize %lu\n",
2379 zone_names[j], memmap_pages, realsize);
2380
2381 /* Account for reserved DMA pages */
2382 if (j == ZONE_DMA && realsize > dma_reserve) {
2383 realsize -= dma_reserve;
2384 printk(KERN_DEBUG " DMA zone: %lu pages reserved\n",
2385 dma_reserve);
2386 }
2387
Christoph Lameter98d2b0e2006-09-25 23:31:12 -07002388 if (!is_highmem_idx(j))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002389 nr_kernel_pages += realsize;
2390 nr_all_pages += realsize;
2391
2392 zone->spanned_pages = size;
2393 zone->present_pages = realsize;
Christoph Lameter96146342006-07-03 00:24:13 -07002394#ifdef CONFIG_NUMA
Christoph Lameterd5f541e2006-09-27 01:50:08 -07002395 zone->node = nid;
Christoph Lameter8417bba2006-09-25 23:31:51 -07002396 zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
Christoph Lameter96146342006-07-03 00:24:13 -07002397 / 100;
Christoph Lameter0ff38492006-09-25 23:31:52 -07002398 zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
Christoph Lameter96146342006-07-03 00:24:13 -07002399#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07002400 zone->name = zone_names[j];
2401 spin_lock_init(&zone->lock);
2402 spin_lock_init(&zone->lru_lock);
Dave Hansenbdc8cb92005-10-29 18:16:53 -07002403 zone_seqlock_init(zone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002404 zone->zone_pgdat = pgdat;
2405 zone->free_pages = 0;
2406
2407 zone->temp_priority = zone->prev_priority = DEF_PRIORITY;
2408
Dave Hansened8ece22005-10-29 18:16:50 -07002409 zone_pcp_init(zone);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002410 INIT_LIST_HEAD(&zone->active_list);
2411 INIT_LIST_HEAD(&zone->inactive_list);
2412 zone->nr_scan_active = 0;
2413 zone->nr_scan_inactive = 0;
2414 zone->nr_active = 0;
2415 zone->nr_inactive = 0;
Christoph Lameter2244b952006-06-30 01:55:33 -07002416 zap_zone_vm_stats(zone);
Martin Hicks53e9a612005-09-03 15:54:51 -07002417 atomic_set(&zone->reclaim_in_progress, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002418 if (!size)
2419 continue;
2420
Andy Whitcroftd41dee32005-06-23 00:07:54 -07002421 zonetable_add(zone, nid, j, zone_start_pfn, size);
Yasunori Goto718127c2006-06-23 02:03:10 -07002422 ret = init_currently_empty_zone(zone, zone_start_pfn, size);
2423 BUG_ON(ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002424 zone_start_pfn += size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002425 }
2426}
2427
2428static void __init alloc_node_mem_map(struct pglist_data *pgdat)
2429{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002430 /* Skip empty nodes */
2431 if (!pgdat->node_spanned_pages)
2432 return;
2433
Andy Whitcroftd41dee32005-06-23 00:07:54 -07002434#ifdef CONFIG_FLAT_NODE_MEM_MAP
Linus Torvalds1da177e2005-04-16 15:20:36 -07002435 /* ia64 gets its own node_mem_map, before this, without bootmem */
2436 if (!pgdat->node_mem_map) {
Bob Piccoe984bb42006-05-20 15:00:31 -07002437 unsigned long size, start, end;
Andy Whitcroftd41dee32005-06-23 00:07:54 -07002438 struct page *map;
2439
Bob Piccoe984bb42006-05-20 15:00:31 -07002440 /*
2441 * The zone's endpoints aren't required to be MAX_ORDER
2442 * aligned but the node_mem_map endpoints must be in order
2443 * for the buddy allocator to function correctly.
2444 */
2445 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
2446 end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
2447 end = ALIGN(end, MAX_ORDER_NR_PAGES);
2448 size = (end - start) * sizeof(struct page);
Dave Hansen6f167ec2005-06-23 00:07:39 -07002449 map = alloc_remap(pgdat->node_id, size);
2450 if (!map)
2451 map = alloc_bootmem_node(pgdat, size);
Bob Piccoe984bb42006-05-20 15:00:31 -07002452 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002453 }
Andy Whitcroftd41dee32005-06-23 00:07:54 -07002454#ifdef CONFIG_FLATMEM
Linus Torvalds1da177e2005-04-16 15:20:36 -07002455 /*
2456 * With no DISCONTIG, the global mem_map is just set as node 0's
2457 */
Mel Gormanc7132162006-09-27 01:49:43 -07002458 if (pgdat == NODE_DATA(0)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002459 mem_map = NODE_DATA(0)->node_mem_map;
Mel Gormanc7132162006-09-27 01:49:43 -07002460#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
2461 if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
2462 mem_map -= pgdat->node_start_pfn;
2463#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
2464 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002465#endif
Andy Whitcroftd41dee32005-06-23 00:07:54 -07002466#endif /* CONFIG_FLAT_NODE_MEM_MAP */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002467}
2468
Yasunori Goto86356ab2006-06-23 02:03:09 -07002469void __meminit free_area_init_node(int nid, struct pglist_data *pgdat,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002470 unsigned long *zones_size, unsigned long node_start_pfn,
2471 unsigned long *zholes_size)
2472{
2473 pgdat->node_id = nid;
2474 pgdat->node_start_pfn = node_start_pfn;
Mel Gormanc7132162006-09-27 01:49:43 -07002475 calculate_node_totalpages(pgdat, zones_size, zholes_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002476
2477 alloc_node_mem_map(pgdat);
2478
2479 free_area_init_core(pgdat, zones_size, zholes_size);
2480}
2481
Mel Gormanc7132162006-09-27 01:49:43 -07002482#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
2483/**
2484 * add_active_range - Register a range of PFNs backed by physical memory
2485 * @nid: The node ID the range resides on
2486 * @start_pfn: The start PFN of the available physical memory
2487 * @end_pfn: The end PFN of the available physical memory
2488 *
2489 * These ranges are stored in an early_node_map[] and later used by
2490 * free_area_init_nodes() to calculate zone sizes and holes. If the
2491 * range spans a memory hole, it is up to the architecture to ensure
2492 * the memory is not freed by the bootmem allocator. If possible
2493 * the range being registered will be merged with existing ranges.
2494 */
2495void __init add_active_range(unsigned int nid, unsigned long start_pfn,
2496 unsigned long end_pfn)
2497{
2498 int i;
2499
2500 printk(KERN_DEBUG "Entering add_active_range(%d, %lu, %lu) "
2501 "%d entries of %d used\n",
2502 nid, start_pfn, end_pfn,
2503 nr_nodemap_entries, MAX_ACTIVE_REGIONS);
2504
2505 /* Merge with existing active regions if possible */
2506 for (i = 0; i < nr_nodemap_entries; i++) {
2507 if (early_node_map[i].nid != nid)
2508 continue;
2509
2510 /* Skip if an existing region covers this new one */
2511 if (start_pfn >= early_node_map[i].start_pfn &&
2512 end_pfn <= early_node_map[i].end_pfn)
2513 return;
2514
2515 /* Merge forward if suitable */
2516 if (start_pfn <= early_node_map[i].end_pfn &&
2517 end_pfn > early_node_map[i].end_pfn) {
2518 early_node_map[i].end_pfn = end_pfn;
2519 return;
2520 }
2521
2522 /* Merge backward if suitable */
2523 if (start_pfn < early_node_map[i].end_pfn &&
2524 end_pfn >= early_node_map[i].start_pfn) {
2525 early_node_map[i].start_pfn = start_pfn;
2526 return;
2527 }
2528 }
2529
2530 /* Check that early_node_map is large enough */
2531 if (i >= MAX_ACTIVE_REGIONS) {
2532 printk(KERN_CRIT "More than %d memory regions, truncating\n",
2533 MAX_ACTIVE_REGIONS);
2534 return;
2535 }
2536
2537 early_node_map[i].nid = nid;
2538 early_node_map[i].start_pfn = start_pfn;
2539 early_node_map[i].end_pfn = end_pfn;
2540 nr_nodemap_entries = i + 1;
2541}
2542
2543/**
2544 * shrink_active_range - Shrink an existing registered range of PFNs
2545 * @nid: The node id the range is on that should be shrunk
2546 * @old_end_pfn: The old end PFN of the range
2547 * @new_end_pfn: The new PFN of the range
2548 *
2549 * i386 with NUMA use alloc_remap() to store a node_mem_map on a local node.
2550 * The map is kept at the end physical page range that has already been
2551 * registered with add_active_range(). This function allows an arch to shrink
2552 * an existing registered range.
2553 */
2554void __init shrink_active_range(unsigned int nid, unsigned long old_end_pfn,
2555 unsigned long new_end_pfn)
2556{
2557 int i;
2558
2559 /* Find the old active region end and shrink */
2560 for_each_active_range_index_in_nid(i, nid)
2561 if (early_node_map[i].end_pfn == old_end_pfn) {
2562 early_node_map[i].end_pfn = new_end_pfn;
2563 break;
2564 }
2565}
2566
2567/**
2568 * remove_all_active_ranges - Remove all currently registered regions
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002569 *
Mel Gormanc7132162006-09-27 01:49:43 -07002570 * During discovery, it may be found that a table like SRAT is invalid
2571 * and an alternative discovery method must be used. This function removes
2572 * all currently registered regions.
2573 */
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002574void __init remove_all_active_ranges(void)
Mel Gormanc7132162006-09-27 01:49:43 -07002575{
2576 memset(early_node_map, 0, sizeof(early_node_map));
2577 nr_nodemap_entries = 0;
Mel Gormanfb014392006-09-27 01:49:59 -07002578#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
2579 memset(node_boundary_start_pfn, 0, sizeof(node_boundary_start_pfn));
2580 memset(node_boundary_end_pfn, 0, sizeof(node_boundary_end_pfn));
2581#endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
Mel Gormanc7132162006-09-27 01:49:43 -07002582}
2583
2584/* Compare two active node_active_regions */
2585static int __init cmp_node_active_region(const void *a, const void *b)
2586{
2587 struct node_active_region *arange = (struct node_active_region *)a;
2588 struct node_active_region *brange = (struct node_active_region *)b;
2589
2590 /* Done this way to avoid overflows */
2591 if (arange->start_pfn > brange->start_pfn)
2592 return 1;
2593 if (arange->start_pfn < brange->start_pfn)
2594 return -1;
2595
2596 return 0;
2597}
2598
2599/* sort the node_map by start_pfn */
2600static void __init sort_node_map(void)
2601{
2602 sort(early_node_map, (size_t)nr_nodemap_entries,
2603 sizeof(struct node_active_region),
2604 cmp_node_active_region, NULL);
2605}
2606
2607/* Find the lowest pfn for a node. This depends on a sorted early_node_map */
2608unsigned long __init find_min_pfn_for_node(unsigned long nid)
2609{
2610 int i;
2611
2612 /* Assuming a sorted map, the first range found has the starting pfn */
2613 for_each_active_range_index_in_nid(i, nid)
2614 return early_node_map[i].start_pfn;
2615
2616 printk(KERN_WARNING "Could not find start_pfn for node %lu\n", nid);
2617 return 0;
2618}
2619
2620/**
2621 * find_min_pfn_with_active_regions - Find the minimum PFN registered
2622 *
2623 * It returns the minimum PFN based on information provided via
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002624 * add_active_range().
Mel Gormanc7132162006-09-27 01:49:43 -07002625 */
2626unsigned long __init find_min_pfn_with_active_regions(void)
2627{
2628 return find_min_pfn_for_node(MAX_NUMNODES);
2629}
2630
2631/**
2632 * find_max_pfn_with_active_regions - Find the maximum PFN registered
2633 *
2634 * It returns the maximum PFN based on information provided via
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002635 * add_active_range().
Mel Gormanc7132162006-09-27 01:49:43 -07002636 */
2637unsigned long __init find_max_pfn_with_active_regions(void)
2638{
2639 int i;
2640 unsigned long max_pfn = 0;
2641
2642 for (i = 0; i < nr_nodemap_entries; i++)
2643 max_pfn = max(max_pfn, early_node_map[i].end_pfn);
2644
2645 return max_pfn;
2646}
2647
2648/**
2649 * free_area_init_nodes - Initialise all pg_data_t and zone data
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002650 * @max_zone_pfn: an array of max PFNs for each zone
Mel Gormanc7132162006-09-27 01:49:43 -07002651 *
2652 * This will call free_area_init_node() for each active node in the system.
2653 * Using the page ranges provided by add_active_range(), the size of each
2654 * zone in each node and their holes is calculated. If the maximum PFN
2655 * between two adjacent zones match, it is assumed that the zone is empty.
2656 * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
2657 * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
2658 * starts where the previous one ended. For example, ZONE_DMA32 starts
2659 * at arch_max_dma_pfn.
2660 */
2661void __init free_area_init_nodes(unsigned long *max_zone_pfn)
2662{
2663 unsigned long nid;
2664 enum zone_type i;
2665
2666 /* Record where the zone boundaries are */
2667 memset(arch_zone_lowest_possible_pfn, 0,
2668 sizeof(arch_zone_lowest_possible_pfn));
2669 memset(arch_zone_highest_possible_pfn, 0,
2670 sizeof(arch_zone_highest_possible_pfn));
2671 arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
2672 arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
2673 for (i = 1; i < MAX_NR_ZONES; i++) {
2674 arch_zone_lowest_possible_pfn[i] =
2675 arch_zone_highest_possible_pfn[i-1];
2676 arch_zone_highest_possible_pfn[i] =
2677 max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
2678 }
2679
2680 /* Regions in the early_node_map can be in any order */
2681 sort_node_map();
2682
2683 /* Print out the zone ranges */
2684 printk("Zone PFN ranges:\n");
2685 for (i = 0; i < MAX_NR_ZONES; i++)
2686 printk(" %-8s %8lu -> %8lu\n",
2687 zone_names[i],
2688 arch_zone_lowest_possible_pfn[i],
2689 arch_zone_highest_possible_pfn[i]);
2690
2691 /* Print out the early_node_map[] */
2692 printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
2693 for (i = 0; i < nr_nodemap_entries; i++)
2694 printk(" %3d: %8lu -> %8lu\n", early_node_map[i].nid,
2695 early_node_map[i].start_pfn,
2696 early_node_map[i].end_pfn);
2697
2698 /* Initialise every node */
2699 for_each_online_node(nid) {
2700 pg_data_t *pgdat = NODE_DATA(nid);
2701 free_area_init_node(nid, pgdat, NULL,
2702 find_min_pfn_for_node(nid), NULL);
2703 }
2704}
2705#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
2706
Mel Gorman0e0b8642006-09-27 01:49:56 -07002707/**
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002708 * set_dma_reserve - set the specified number of pages reserved in the first zone
2709 * @new_dma_reserve: The number of pages to mark reserved
Mel Gorman0e0b8642006-09-27 01:49:56 -07002710 *
2711 * The per-cpu batchsize and zone watermarks are determined by present_pages.
2712 * In the DMA zone, a significant percentage may be consumed by kernel image
2713 * and other unfreeable allocations which can skew the watermarks badly. This
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002714 * function may optionally be used to account for unfreeable pages in the
2715 * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
2716 * smaller per-cpu batchsize.
Mel Gorman0e0b8642006-09-27 01:49:56 -07002717 */
2718void __init set_dma_reserve(unsigned long new_dma_reserve)
2719{
2720 dma_reserve = new_dma_reserve;
2721}
2722
Dave Hansen93b75042005-06-23 00:07:47 -07002723#ifndef CONFIG_NEED_MULTIPLE_NODES
Linus Torvalds1da177e2005-04-16 15:20:36 -07002724static bootmem_data_t contig_bootmem_data;
2725struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };
2726
2727EXPORT_SYMBOL(contig_page_data);
Dave Hansen93b75042005-06-23 00:07:47 -07002728#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07002729
2730void __init free_area_init(unsigned long *zones_size)
2731{
Dave Hansen93b75042005-06-23 00:07:47 -07002732 free_area_init_node(0, NODE_DATA(0), zones_size,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002733 __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
2734}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002735
Linus Torvalds1da177e2005-04-16 15:20:36 -07002736#ifdef CONFIG_HOTPLUG_CPU
2737static int page_alloc_cpu_notify(struct notifier_block *self,
2738 unsigned long action, void *hcpu)
2739{
2740 int cpu = (unsigned long)hcpu;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002741
2742 if (action == CPU_DEAD) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002743 local_irq_disable();
2744 __drain_pages(cpu);
Christoph Lameterf8891e52006-06-30 01:55:45 -07002745 vm_events_fold_cpu(cpu);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002746 local_irq_enable();
Christoph Lameter2244b952006-06-30 01:55:33 -07002747 refresh_cpu_vm_stats(cpu);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002748 }
2749 return NOTIFY_OK;
2750}
2751#endif /* CONFIG_HOTPLUG_CPU */
2752
2753void __init page_alloc_init(void)
2754{
2755 hotcpu_notifier(page_alloc_cpu_notify, 0);
2756}
2757
2758/*
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07002759 * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio
2760 * or min_free_kbytes changes.
2761 */
2762static void calculate_totalreserve_pages(void)
2763{
2764 struct pglist_data *pgdat;
2765 unsigned long reserve_pages = 0;
Christoph Lameter2f6726e2006-09-25 23:31:18 -07002766 enum zone_type i, j;
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07002767
2768 for_each_online_pgdat(pgdat) {
2769 for (i = 0; i < MAX_NR_ZONES; i++) {
2770 struct zone *zone = pgdat->node_zones + i;
2771 unsigned long max = 0;
2772
2773 /* Find valid and maximum lowmem_reserve in the zone */
2774 for (j = i; j < MAX_NR_ZONES; j++) {
2775 if (zone->lowmem_reserve[j] > max)
2776 max = zone->lowmem_reserve[j];
2777 }
2778
2779 /* we treat pages_high as reserved pages. */
2780 max += zone->pages_high;
2781
2782 if (max > zone->present_pages)
2783 max = zone->present_pages;
2784 reserve_pages += max;
2785 }
2786 }
2787 totalreserve_pages = reserve_pages;
2788}
2789
2790/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07002791 * setup_per_zone_lowmem_reserve - called whenever
2792 * sysctl_lower_zone_reserve_ratio changes. Ensures that each zone
2793 * has a correct pages reserved value, so an adequate number of
2794 * pages are left in the zone after a successful __alloc_pages().
2795 */
2796static void setup_per_zone_lowmem_reserve(void)
2797{
2798 struct pglist_data *pgdat;
Christoph Lameter2f6726e2006-09-25 23:31:18 -07002799 enum zone_type j, idx;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002800
KAMEZAWA Hiroyukiec936fc2006-03-27 01:15:59 -08002801 for_each_online_pgdat(pgdat) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002802 for (j = 0; j < MAX_NR_ZONES; j++) {
2803 struct zone *zone = pgdat->node_zones + j;
2804 unsigned long present_pages = zone->present_pages;
2805
2806 zone->lowmem_reserve[j] = 0;
2807
Christoph Lameter2f6726e2006-09-25 23:31:18 -07002808 idx = j;
2809 while (idx) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002810 struct zone *lower_zone;
2811
Christoph Lameter2f6726e2006-09-25 23:31:18 -07002812 idx--;
2813
Linus Torvalds1da177e2005-04-16 15:20:36 -07002814 if (sysctl_lowmem_reserve_ratio[idx] < 1)
2815 sysctl_lowmem_reserve_ratio[idx] = 1;
2816
2817 lower_zone = pgdat->node_zones + idx;
2818 lower_zone->lowmem_reserve[j] = present_pages /
2819 sysctl_lowmem_reserve_ratio[idx];
2820 present_pages += lower_zone->present_pages;
2821 }
2822 }
2823 }
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07002824
2825 /* update totalreserve_pages */
2826 calculate_totalreserve_pages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002827}
2828
Randy Dunlap88ca3b92006-10-04 02:15:25 -07002829/**
2830 * setup_per_zone_pages_min - called when min_free_kbytes changes.
2831 *
2832 * Ensures that the pages_{min,low,high} values for each zone are set correctly
2833 * with respect to min_free_kbytes.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002834 */
Dave Hansen3947be12005-10-29 18:16:54 -07002835void setup_per_zone_pages_min(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002836{
2837 unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
2838 unsigned long lowmem_pages = 0;
2839 struct zone *zone;
2840 unsigned long flags;
2841
2842 /* Calculate total number of !ZONE_HIGHMEM pages */
2843 for_each_zone(zone) {
2844 if (!is_highmem(zone))
2845 lowmem_pages += zone->present_pages;
2846 }
2847
2848 for_each_zone(zone) {
Andrew Mortonac924c62006-05-15 09:43:59 -07002849 u64 tmp;
2850
Linus Torvalds1da177e2005-04-16 15:20:36 -07002851 spin_lock_irqsave(&zone->lru_lock, flags);
Andrew Mortonac924c62006-05-15 09:43:59 -07002852 tmp = (u64)pages_min * zone->present_pages;
2853 do_div(tmp, lowmem_pages);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002854 if (is_highmem(zone)) {
2855 /*
Nick Piggin669ed172005-11-13 16:06:45 -08002856 * __GFP_HIGH and PF_MEMALLOC allocations usually don't
2857 * need highmem pages, so cap pages_min to a small
2858 * value here.
2859 *
2860 * The (pages_high-pages_low) and (pages_low-pages_min)
2861 * deltas controls asynch page reclaim, and so should
2862 * not be capped for highmem.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002863 */
2864 int min_pages;
2865
2866 min_pages = zone->present_pages / 1024;
2867 if (min_pages < SWAP_CLUSTER_MAX)
2868 min_pages = SWAP_CLUSTER_MAX;
2869 if (min_pages > 128)
2870 min_pages = 128;
2871 zone->pages_min = min_pages;
2872 } else {
Nick Piggin669ed172005-11-13 16:06:45 -08002873 /*
2874 * If it's a lowmem zone, reserve a number of pages
Linus Torvalds1da177e2005-04-16 15:20:36 -07002875 * proportionate to the zone's size.
2876 */
Nick Piggin669ed172005-11-13 16:06:45 -08002877 zone->pages_min = tmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002878 }
2879
Andrew Mortonac924c62006-05-15 09:43:59 -07002880 zone->pages_low = zone->pages_min + (tmp >> 2);
2881 zone->pages_high = zone->pages_min + (tmp >> 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002882 spin_unlock_irqrestore(&zone->lru_lock, flags);
2883 }
Hideo AOKIcb45b0e2006-04-10 22:52:59 -07002884
2885 /* update totalreserve_pages */
2886 calculate_totalreserve_pages();
Linus Torvalds1da177e2005-04-16 15:20:36 -07002887}
2888
2889/*
2890 * Initialise min_free_kbytes.
2891 *
2892 * For small machines we want it small (128k min). For large machines
2893 * we want it large (64MB max). But it is not linear, because network
2894 * bandwidth does not increase linearly with machine size. We use
2895 *
2896 * min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
2897 * min_free_kbytes = sqrt(lowmem_kbytes * 16)
2898 *
2899 * which yields
2900 *
2901 * 16MB: 512k
2902 * 32MB: 724k
2903 * 64MB: 1024k
2904 * 128MB: 1448k
2905 * 256MB: 2048k
2906 * 512MB: 2896k
2907 * 1024MB: 4096k
2908 * 2048MB: 5792k
2909 * 4096MB: 8192k
2910 * 8192MB: 11584k
2911 * 16384MB: 16384k
2912 */
2913static int __init init_per_zone_pages_min(void)
2914{
2915 unsigned long lowmem_kbytes;
2916
2917 lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
2918
2919 min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
2920 if (min_free_kbytes < 128)
2921 min_free_kbytes = 128;
2922 if (min_free_kbytes > 65536)
2923 min_free_kbytes = 65536;
2924 setup_per_zone_pages_min();
2925 setup_per_zone_lowmem_reserve();
2926 return 0;
2927}
2928module_init(init_per_zone_pages_min)
2929
2930/*
2931 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
2932 * that we can call two helper functions whenever min_free_kbytes
2933 * changes.
2934 */
2935int min_free_kbytes_sysctl_handler(ctl_table *table, int write,
2936 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
2937{
2938 proc_dointvec(table, write, file, buffer, length, ppos);
2939 setup_per_zone_pages_min();
2940 return 0;
2941}
2942
Christoph Lameter96146342006-07-03 00:24:13 -07002943#ifdef CONFIG_NUMA
2944int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write,
2945 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
2946{
2947 struct zone *zone;
2948 int rc;
2949
2950 rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
2951 if (rc)
2952 return rc;
2953
2954 for_each_zone(zone)
Christoph Lameter8417bba2006-09-25 23:31:51 -07002955 zone->min_unmapped_pages = (zone->present_pages *
Christoph Lameter96146342006-07-03 00:24:13 -07002956 sysctl_min_unmapped_ratio) / 100;
2957 return 0;
2958}
Christoph Lameter0ff38492006-09-25 23:31:52 -07002959
2960int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write,
2961 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
2962{
2963 struct zone *zone;
2964 int rc;
2965
2966 rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
2967 if (rc)
2968 return rc;
2969
2970 for_each_zone(zone)
2971 zone->min_slab_pages = (zone->present_pages *
2972 sysctl_min_slab_ratio) / 100;
2973 return 0;
2974}
Christoph Lameter96146342006-07-03 00:24:13 -07002975#endif
2976
Linus Torvalds1da177e2005-04-16 15:20:36 -07002977/*
2978 * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
2979 * proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
2980 * whenever sysctl_lowmem_reserve_ratio changes.
2981 *
2982 * The reserve ratio obviously has absolutely no relation with the
2983 * pages_min watermarks. The lowmem reserve ratio can only make sense
2984 * if in function of the boot time zone sizes.
2985 */
2986int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
2987 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
2988{
2989 proc_dointvec_minmax(table, write, file, buffer, length, ppos);
2990 setup_per_zone_lowmem_reserve();
2991 return 0;
2992}
2993
Rohit Seth8ad4b1f2006-01-08 01:00:40 -08002994/*
2995 * percpu_pagelist_fraction - changes the pcp->high for each zone on each
2996 * cpu. It is the fraction of total pages in each zone that a hot per cpu pagelist
2997 * can have before it gets flushed back to buddy allocator.
2998 */
2999
3000int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write,
3001 struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
3002{
3003 struct zone *zone;
3004 unsigned int cpu;
3005 int ret;
3006
3007 ret = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
3008 if (!write || (ret == -EINVAL))
3009 return ret;
3010 for_each_zone(zone) {
3011 for_each_online_cpu(cpu) {
3012 unsigned long high;
3013 high = zone->present_pages / percpu_pagelist_fraction;
3014 setup_pagelist_highmark(zone_pcp(zone, cpu), high);
3015 }
3016 }
3017 return 0;
3018}
3019
David S. Millerf034b5d2006-08-24 03:08:07 -07003020int hashdist = HASHDIST_DEFAULT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003021
3022#ifdef CONFIG_NUMA
3023static int __init set_hashdist(char *str)
3024{
3025 if (!str)
3026 return 0;
3027 hashdist = simple_strtoul(str, &str, 0);
3028 return 1;
3029}
3030__setup("hashdist=", set_hashdist);
3031#endif
3032
3033/*
3034 * allocate a large system hash table from bootmem
3035 * - it is assumed that the hash table must contain an exact power-of-2
3036 * quantity of entries
3037 * - limit is the number of hash buckets, not the total allocation size
3038 */
3039void *__init alloc_large_system_hash(const char *tablename,
3040 unsigned long bucketsize,
3041 unsigned long numentries,
3042 int scale,
3043 int flags,
3044 unsigned int *_hash_shift,
3045 unsigned int *_hash_mask,
3046 unsigned long limit)
3047{
3048 unsigned long long max = limit;
3049 unsigned long log2qty, size;
3050 void *table = NULL;
3051
3052 /* allow the kernel cmdline to have a say */
3053 if (!numentries) {
3054 /* round applicable memory size up to nearest megabyte */
3055 numentries = (flags & HASH_HIGHMEM) ? nr_all_pages : nr_kernel_pages;
3056 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
3057 numentries >>= 20 - PAGE_SHIFT;
3058 numentries <<= 20 - PAGE_SHIFT;
3059
3060 /* limit to 1 bucket per 2^scale bytes of low memory */
3061 if (scale > PAGE_SHIFT)
3062 numentries >>= (scale - PAGE_SHIFT);
3063 else
3064 numentries <<= (PAGE_SHIFT - scale);
3065 }
John Hawkes6e692ed2006-03-25 03:08:02 -08003066 numentries = roundup_pow_of_two(numentries);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003067
3068 /* limit allocation size to 1/16 total memory by default */
3069 if (max == 0) {
3070 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
3071 do_div(max, bucketsize);
3072 }
3073
3074 if (numentries > max)
3075 numentries = max;
3076
3077 log2qty = long_log2(numentries);
3078
3079 do {
3080 size = bucketsize << log2qty;
3081 if (flags & HASH_EARLY)
3082 table = alloc_bootmem(size);
3083 else if (hashdist)
3084 table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
3085 else {
3086 unsigned long order;
3087 for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++)
3088 ;
3089 table = (void*) __get_free_pages(GFP_ATOMIC, order);
3090 }
3091 } while (!table && size > PAGE_SIZE && --log2qty);
3092
3093 if (!table)
3094 panic("Failed to allocate %s hash table\n", tablename);
3095
3096 printk("%s hash table entries: %d (order: %d, %lu bytes)\n",
3097 tablename,
3098 (1U << log2qty),
3099 long_log2(size) - PAGE_SHIFT,
3100 size);
3101
3102 if (_hash_shift)
3103 *_hash_shift = log2qty;
3104 if (_hash_mask)
3105 *_hash_mask = (1 << log2qty) - 1;
3106
3107 return table;
3108}
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08003109
3110#ifdef CONFIG_OUT_OF_LINE_PFN_TO_PAGE
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08003111struct page *pfn_to_page(unsigned long pfn)
3112{
Andy Whitcroft67de6482006-06-23 02:03:12 -07003113 return __pfn_to_page(pfn);
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08003114}
3115unsigned long page_to_pfn(struct page *page)
3116{
Andy Whitcroft67de6482006-06-23 02:03:12 -07003117 return __page_to_pfn(page);
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08003118}
KAMEZAWA Hiroyukia117e662006-03-27 01:15:25 -08003119EXPORT_SYMBOL(pfn_to_page);
3120EXPORT_SYMBOL(page_to_pfn);
3121#endif /* CONFIG_OUT_OF_LINE_PFN_TO_PAGE */