Merge master.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6
[linux-2.6] / mm / page_alloc.c
1 /*
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
17 #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>
24 #include <linux/kernel.h>
25 #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>
35 #include <linux/memory_hotplug.h>
36 #include <linux/nodemask.h>
37 #include <linux/vmalloc.h>
38 #include <linux/mempolicy.h>
39 #include <linux/stop_machine.h>
40 #include <linux/sort.h>
41 #include <linux/pfn.h>
42 #include <linux/backing-dev.h>
43 #include <linux/fault-inject.h>
44
45 #include <asm/tlbflush.h>
46 #include <asm/div64.h>
47 #include "internal.h"
48
49 /*
50  * MCD - HACK: Find somewhere to initialize this EARLY, or make this
51  * initializer cleaner
52  */
53 nodemask_t node_online_map __read_mostly = { { [0] = 1UL } };
54 EXPORT_SYMBOL(node_online_map);
55 nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL;
56 EXPORT_SYMBOL(node_possible_map);
57 unsigned long totalram_pages __read_mostly;
58 unsigned long totalreserve_pages __read_mostly;
59 long nr_swap_pages;
60 int percpu_pagelist_fraction;
61
62 static void __free_pages_ok(struct page *page, unsigned int order);
63
64 /*
65  * results with 256, 32 in the lowmem_reserve sysctl:
66  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
67  *      1G machine -> (16M dma, 784M normal, 224M high)
68  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
69  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
70  *      HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
71  *
72  * TBD: should special case ZONE_DMA32 machines here - in those we normally
73  * don't need any ZONE_NORMAL reservation
74  */
75 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
76 #ifdef CONFIG_ZONE_DMA
77          256,
78 #endif
79 #ifdef CONFIG_ZONE_DMA32
80          256,
81 #endif
82 #ifdef CONFIG_HIGHMEM
83          32,
84 #endif
85          32,
86 };
87
88 EXPORT_SYMBOL(totalram_pages);
89
90 static char * const zone_names[MAX_NR_ZONES] = {
91 #ifdef CONFIG_ZONE_DMA
92          "DMA",
93 #endif
94 #ifdef CONFIG_ZONE_DMA32
95          "DMA32",
96 #endif
97          "Normal",
98 #ifdef CONFIG_HIGHMEM
99          "HighMem",
100 #endif
101          "Movable",
102 };
103
104 int min_free_kbytes = 1024;
105
106 unsigned long __meminitdata nr_kernel_pages;
107 unsigned long __meminitdata nr_all_pages;
108 static unsigned long __meminitdata dma_reserve;
109
110 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
111   /*
112    * MAX_ACTIVE_REGIONS determines the maxmimum number of distinct
113    * ranges of memory (RAM) that may be registered with add_active_range().
114    * Ranges passed to add_active_range() will be merged if possible
115    * so the number of times add_active_range() can be called is
116    * related to the number of nodes and the number of holes
117    */
118   #ifdef CONFIG_MAX_ACTIVE_REGIONS
119     /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
120     #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
121   #else
122     #if MAX_NUMNODES >= 32
123       /* If there can be many nodes, allow up to 50 holes per node */
124       #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
125     #else
126       /* By default, allow up to 256 distinct regions */
127       #define MAX_ACTIVE_REGIONS 256
128     #endif
129   #endif
130
131   static struct node_active_region __meminitdata early_node_map[MAX_ACTIVE_REGIONS];
132   static int __meminitdata nr_nodemap_entries;
133   static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
134   static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
135 #ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
136   static unsigned long __meminitdata node_boundary_start_pfn[MAX_NUMNODES];
137   static unsigned long __meminitdata node_boundary_end_pfn[MAX_NUMNODES];
138 #endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
139   unsigned long __initdata required_kernelcore;
140   unsigned long __initdata required_movablecore;
141   unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
142
143   /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
144   int movable_zone;
145   EXPORT_SYMBOL(movable_zone);
146 #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
147
148 #if MAX_NUMNODES > 1
149 int nr_node_ids __read_mostly = MAX_NUMNODES;
150 EXPORT_SYMBOL(nr_node_ids);
151 #endif
152
153 #ifdef CONFIG_DEBUG_VM
154 static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
155 {
156         int ret = 0;
157         unsigned seq;
158         unsigned long pfn = page_to_pfn(page);
159
160         do {
161                 seq = zone_span_seqbegin(zone);
162                 if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
163                         ret = 1;
164                 else if (pfn < zone->zone_start_pfn)
165                         ret = 1;
166         } while (zone_span_seqretry(zone, seq));
167
168         return ret;
169 }
170
171 static int page_is_consistent(struct zone *zone, struct page *page)
172 {
173         if (!pfn_valid_within(page_to_pfn(page)))
174                 return 0;
175         if (zone != page_zone(page))
176                 return 0;
177
178         return 1;
179 }
180 /*
181  * Temporary debugging check for pages not lying within a given zone.
182  */
183 static int bad_range(struct zone *zone, struct page *page)
184 {
185         if (page_outside_zone_boundaries(zone, page))
186                 return 1;
187         if (!page_is_consistent(zone, page))
188                 return 1;
189
190         return 0;
191 }
192 #else
193 static inline int bad_range(struct zone *zone, struct page *page)
194 {
195         return 0;
196 }
197 #endif
198
199 static void bad_page(struct page *page)
200 {
201         printk(KERN_EMERG "Bad page state in process '%s'\n"
202                 KERN_EMERG "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n"
203                 KERN_EMERG "Trying to fix it up, but a reboot is needed\n"
204                 KERN_EMERG "Backtrace:\n",
205                 current->comm, page, (int)(2*sizeof(unsigned long)),
206                 (unsigned long)page->flags, page->mapping,
207                 page_mapcount(page), page_count(page));
208         dump_stack();
209         page->flags &= ~(1 << PG_lru    |
210                         1 << PG_private |
211                         1 << PG_locked  |
212                         1 << PG_active  |
213                         1 << PG_dirty   |
214                         1 << PG_reclaim |
215                         1 << PG_slab    |
216                         1 << PG_swapcache |
217                         1 << PG_writeback |
218                         1 << PG_buddy );
219         set_page_count(page, 0);
220         reset_page_mapcount(page);
221         page->mapping = NULL;
222         add_taint(TAINT_BAD_PAGE);
223 }
224
225 /*
226  * Higher-order pages are called "compound pages".  They are structured thusly:
227  *
228  * The first PAGE_SIZE page is called the "head page".
229  *
230  * The remaining PAGE_SIZE pages are called "tail pages".
231  *
232  * All pages have PG_compound set.  All pages have their ->private pointing at
233  * the head page (even the head page has this).
234  *
235  * The first tail page's ->lru.next holds the address of the compound page's
236  * put_page() function.  Its ->lru.prev holds the order of allocation.
237  * This usage means that zero-order pages may not be compound.
238  */
239
240 static void free_compound_page(struct page *page)
241 {
242         __free_pages_ok(page, compound_order(page));
243 }
244
245 static void prep_compound_page(struct page *page, unsigned long order)
246 {
247         int i;
248         int nr_pages = 1 << order;
249
250         set_compound_page_dtor(page, free_compound_page);
251         set_compound_order(page, order);
252         __SetPageHead(page);
253         for (i = 1; i < nr_pages; i++) {
254                 struct page *p = page + i;
255
256                 __SetPageTail(p);
257                 p->first_page = page;
258         }
259 }
260
261 static void destroy_compound_page(struct page *page, unsigned long order)
262 {
263         int i;
264         int nr_pages = 1 << order;
265
266         if (unlikely(compound_order(page) != order))
267                 bad_page(page);
268
269         if (unlikely(!PageHead(page)))
270                         bad_page(page);
271         __ClearPageHead(page);
272         for (i = 1; i < nr_pages; i++) {
273                 struct page *p = page + i;
274
275                 if (unlikely(!PageTail(p) |
276                                 (p->first_page != page)))
277                         bad_page(page);
278                 __ClearPageTail(p);
279         }
280 }
281
282 static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
283 {
284         int i;
285
286         VM_BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM);
287         /*
288          * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
289          * and __GFP_HIGHMEM from hard or soft interrupt context.
290          */
291         VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
292         for (i = 0; i < (1 << order); i++)
293                 clear_highpage(page + i);
294 }
295
296 /*
297  * function for dealing with page's order in buddy system.
298  * zone->lock is already acquired when we use these.
299  * So, we don't need atomic page->flags operations here.
300  */
301 static inline unsigned long page_order(struct page *page)
302 {
303         return page_private(page);
304 }
305
306 static inline void set_page_order(struct page *page, int order)
307 {
308         set_page_private(page, order);
309         __SetPageBuddy(page);
310 }
311
312 static inline void rmv_page_order(struct page *page)
313 {
314         __ClearPageBuddy(page);
315         set_page_private(page, 0);
316 }
317
318 /*
319  * Locate the struct page for both the matching buddy in our
320  * pair (buddy1) and the combined O(n+1) page they form (page).
321  *
322  * 1) Any buddy B1 will have an order O twin B2 which satisfies
323  * the following equation:
324  *     B2 = B1 ^ (1 << O)
325  * For example, if the starting buddy (buddy2) is #8 its order
326  * 1 buddy is #10:
327  *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
328  *
329  * 2) Any buddy B will have an order O+1 parent P which
330  * satisfies the following equation:
331  *     P = B & ~(1 << O)
332  *
333  * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
334  */
335 static inline struct page *
336 __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
337 {
338         unsigned long buddy_idx = page_idx ^ (1 << order);
339
340         return page + (buddy_idx - page_idx);
341 }
342
343 static inline unsigned long
344 __find_combined_index(unsigned long page_idx, unsigned int order)
345 {
346         return (page_idx & ~(1 << order));
347 }
348
349 /*
350  * This function checks whether a page is free && is the buddy
351  * we can do coalesce a page and its buddy if
352  * (a) the buddy is not in a hole &&
353  * (b) the buddy is in the buddy system &&
354  * (c) a page and its buddy have the same order &&
355  * (d) a page and its buddy are in the same zone.
356  *
357  * For recording whether a page is in the buddy system, we use PG_buddy.
358  * Setting, clearing, and testing PG_buddy is serialized by zone->lock.
359  *
360  * For recording page's order, we use page_private(page).
361  */
362 static inline int page_is_buddy(struct page *page, struct page *buddy,
363                                                                 int order)
364 {
365         if (!pfn_valid_within(page_to_pfn(buddy)))
366                 return 0;
367
368         if (page_zone_id(page) != page_zone_id(buddy))
369                 return 0;
370
371         if (PageBuddy(buddy) && page_order(buddy) == order) {
372                 BUG_ON(page_count(buddy) != 0);
373                 return 1;
374         }
375         return 0;
376 }
377
378 /*
379  * Freeing function for a buddy system allocator.
380  *
381  * The concept of a buddy system is to maintain direct-mapped table
382  * (containing bit values) for memory blocks of various "orders".
383  * The bottom level table contains the map for the smallest allocatable
384  * units of memory (here, pages), and each level above it describes
385  * pairs of units from the levels below, hence, "buddies".
386  * At a high level, all that happens here is marking the table entry
387  * at the bottom level available, and propagating the changes upward
388  * as necessary, plus some accounting needed to play nicely with other
389  * parts of the VM system.
390  * At each level, we keep a list of pages, which are heads of continuous
391  * free pages of length of (1 << order) and marked with PG_buddy. Page's
392  * order is recorded in page_private(page) field.
393  * So when we are allocating or freeing one, we can derive the state of the
394  * other.  That is, if we allocate a small block, and both were   
395  * free, the remainder of the region must be split into blocks.   
396  * If a block is freed, and its buddy is also free, then this
397  * triggers coalescing into a block of larger size.            
398  *
399  * -- wli
400  */
401
402 static inline void __free_one_page(struct page *page,
403                 struct zone *zone, unsigned int order)
404 {
405         unsigned long page_idx;
406         int order_size = 1 << order;
407
408         if (unlikely(PageCompound(page)))
409                 destroy_compound_page(page, order);
410
411         page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
412
413         VM_BUG_ON(page_idx & (order_size - 1));
414         VM_BUG_ON(bad_range(zone, page));
415
416         __mod_zone_page_state(zone, NR_FREE_PAGES, order_size);
417         while (order < MAX_ORDER-1) {
418                 unsigned long combined_idx;
419                 struct free_area *area;
420                 struct page *buddy;
421
422                 buddy = __page_find_buddy(page, page_idx, order);
423                 if (!page_is_buddy(page, buddy, order))
424                         break;          /* Move the buddy up one level. */
425
426                 list_del(&buddy->lru);
427                 area = zone->free_area + order;
428                 area->nr_free--;
429                 rmv_page_order(buddy);
430                 combined_idx = __find_combined_index(page_idx, order);
431                 page = page + (combined_idx - page_idx);
432                 page_idx = combined_idx;
433                 order++;
434         }
435         set_page_order(page, order);
436         list_add(&page->lru, &zone->free_area[order].free_list);
437         zone->free_area[order].nr_free++;
438 }
439
440 static inline int free_pages_check(struct page *page)
441 {
442         if (unlikely(page_mapcount(page) |
443                 (page->mapping != NULL)  |
444                 (page_count(page) != 0)  |
445                 (page->flags & (
446                         1 << PG_lru     |
447                         1 << PG_private |
448                         1 << PG_locked  |
449                         1 << PG_active  |
450                         1 << PG_slab    |
451                         1 << PG_swapcache |
452                         1 << PG_writeback |
453                         1 << PG_reserved |
454                         1 << PG_buddy ))))
455                 bad_page(page);
456         if (PageDirty(page))
457                 __ClearPageDirty(page);
458         /*
459          * For now, we report if PG_reserved was found set, but do not
460          * clear it, and do not free the page.  But we shall soon need
461          * to do more, for when the ZERO_PAGE count wraps negative.
462          */
463         return PageReserved(page);
464 }
465
466 /*
467  * Frees a list of pages. 
468  * Assumes all pages on list are in same zone, and of same order.
469  * count is the number of pages to free.
470  *
471  * If the zone was previously in an "all pages pinned" state then look to
472  * see if this freeing clears that state.
473  *
474  * And clear the zone's pages_scanned counter, to hold off the "all pages are
475  * pinned" detection logic.
476  */
477 static void free_pages_bulk(struct zone *zone, int count,
478                                         struct list_head *list, int order)
479 {
480         spin_lock(&zone->lock);
481         zone->all_unreclaimable = 0;
482         zone->pages_scanned = 0;
483         while (count--) {
484                 struct page *page;
485
486                 VM_BUG_ON(list_empty(list));
487                 page = list_entry(list->prev, struct page, lru);
488                 /* have to delete it as __free_one_page list manipulates */
489                 list_del(&page->lru);
490                 __free_one_page(page, zone, order);
491         }
492         spin_unlock(&zone->lock);
493 }
494
495 static void free_one_page(struct zone *zone, struct page *page, int order)
496 {
497         spin_lock(&zone->lock);
498         zone->all_unreclaimable = 0;
499         zone->pages_scanned = 0;
500         __free_one_page(page, zone, order);
501         spin_unlock(&zone->lock);
502 }
503
504 static void __free_pages_ok(struct page *page, unsigned int order)
505 {
506         unsigned long flags;
507         int i;
508         int reserved = 0;
509
510         for (i = 0 ; i < (1 << order) ; ++i)
511                 reserved += free_pages_check(page + i);
512         if (reserved)
513                 return;
514
515         if (!PageHighMem(page))
516                 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
517         arch_free_page(page, order);
518         kernel_map_pages(page, 1 << order, 0);
519
520         local_irq_save(flags);
521         __count_vm_events(PGFREE, 1 << order);
522         free_one_page(page_zone(page), page, order);
523         local_irq_restore(flags);
524 }
525
526 /*
527  * permit the bootmem allocator to evade page validation on high-order frees
528  */
529 void fastcall __init __free_pages_bootmem(struct page *page, unsigned int order)
530 {
531         if (order == 0) {
532                 __ClearPageReserved(page);
533                 set_page_count(page, 0);
534                 set_page_refcounted(page);
535                 __free_page(page);
536         } else {
537                 int loop;
538
539                 prefetchw(page);
540                 for (loop = 0; loop < BITS_PER_LONG; loop++) {
541                         struct page *p = &page[loop];
542
543                         if (loop + 1 < BITS_PER_LONG)
544                                 prefetchw(p + 1);
545                         __ClearPageReserved(p);
546                         set_page_count(p, 0);
547                 }
548
549                 set_page_refcounted(page);
550                 __free_pages(page, order);
551         }
552 }
553
554
555 /*
556  * The order of subdivision here is critical for the IO subsystem.
557  * Please do not alter this order without good reasons and regression
558  * testing. Specifically, as large blocks of memory are subdivided,
559  * the order in which smaller blocks are delivered depends on the order
560  * they're subdivided in this function. This is the primary factor
561  * influencing the order in which pages are delivered to the IO
562  * subsystem according to empirical testing, and this is also justified
563  * by considering the behavior of a buddy system containing a single
564  * large block of memory acted on by a series of small allocations.
565  * This behavior is a critical factor in sglist merging's success.
566  *
567  * -- wli
568  */
569 static inline void expand(struct zone *zone, struct page *page,
570         int low, int high, struct free_area *area)
571 {
572         unsigned long size = 1 << high;
573
574         while (high > low) {
575                 area--;
576                 high--;
577                 size >>= 1;
578                 VM_BUG_ON(bad_range(zone, &page[size]));
579                 list_add(&page[size].lru, &area->free_list);
580                 area->nr_free++;
581                 set_page_order(&page[size], high);
582         }
583 }
584
585 /*
586  * This page is about to be returned from the page allocator
587  */
588 static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
589 {
590         if (unlikely(page_mapcount(page) |
591                 (page->mapping != NULL)  |
592                 (page_count(page) != 0)  |
593                 (page->flags & (
594                         1 << PG_lru     |
595                         1 << PG_private |
596                         1 << PG_locked  |
597                         1 << PG_active  |
598                         1 << PG_dirty   |
599                         1 << PG_slab    |
600                         1 << PG_swapcache |
601                         1 << PG_writeback |
602                         1 << PG_reserved |
603                         1 << PG_buddy ))))
604                 bad_page(page);
605
606         /*
607          * For now, we report if PG_reserved was found set, but do not
608          * clear it, and do not allocate the page: as a safety net.
609          */
610         if (PageReserved(page))
611                 return 1;
612
613         page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 1 << PG_readahead |
614                         1 << PG_referenced | 1 << PG_arch_1 |
615                         1 << PG_owner_priv_1 | 1 << PG_mappedtodisk);
616         set_page_private(page, 0);
617         set_page_refcounted(page);
618
619         arch_alloc_page(page, order);
620         kernel_map_pages(page, 1 << order, 1);
621
622         if (gfp_flags & __GFP_ZERO)
623                 prep_zero_page(page, order, gfp_flags);
624
625         if (order && (gfp_flags & __GFP_COMP))
626                 prep_compound_page(page, order);
627
628         return 0;
629 }
630
631 /* 
632  * Do the hard work of removing an element from the buddy allocator.
633  * Call me with the zone->lock already held.
634  */
635 static struct page *__rmqueue(struct zone *zone, unsigned int order)
636 {
637         struct free_area * area;
638         unsigned int current_order;
639         struct page *page;
640
641         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
642                 area = zone->free_area + current_order;
643                 if (list_empty(&area->free_list))
644                         continue;
645
646                 page = list_entry(area->free_list.next, struct page, lru);
647                 list_del(&page->lru);
648                 rmv_page_order(page);
649                 area->nr_free--;
650                 __mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
651                 expand(zone, page, order, current_order, area);
652                 return page;
653         }
654
655         return NULL;
656 }
657
658 /* 
659  * Obtain a specified number of elements from the buddy allocator, all under
660  * a single hold of the lock, for efficiency.  Add them to the supplied list.
661  * Returns the number of new pages which were placed at *list.
662  */
663 static int rmqueue_bulk(struct zone *zone, unsigned int order, 
664                         unsigned long count, struct list_head *list)
665 {
666         int i;
667         
668         spin_lock(&zone->lock);
669         for (i = 0; i < count; ++i) {
670                 struct page *page = __rmqueue(zone, order);
671                 if (unlikely(page == NULL))
672                         break;
673                 list_add_tail(&page->lru, list);
674         }
675         spin_unlock(&zone->lock);
676         return i;
677 }
678
679 #ifdef CONFIG_NUMA
680 /*
681  * Called from the vmstat counter updater to drain pagesets of this
682  * currently executing processor on remote nodes after they have
683  * expired.
684  *
685  * Note that this function must be called with the thread pinned to
686  * a single processor.
687  */
688 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
689 {
690         unsigned long flags;
691         int to_drain;
692
693         local_irq_save(flags);
694         if (pcp->count >= pcp->batch)
695                 to_drain = pcp->batch;
696         else
697                 to_drain = pcp->count;
698         free_pages_bulk(zone, to_drain, &pcp->list, 0);
699         pcp->count -= to_drain;
700         local_irq_restore(flags);
701 }
702 #endif
703
704 static void __drain_pages(unsigned int cpu)
705 {
706         unsigned long flags;
707         struct zone *zone;
708         int i;
709
710         for_each_zone(zone) {
711                 struct per_cpu_pageset *pset;
712
713                 if (!populated_zone(zone))
714                         continue;
715
716                 pset = zone_pcp(zone, cpu);
717                 for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
718                         struct per_cpu_pages *pcp;
719
720                         pcp = &pset->pcp[i];
721                         local_irq_save(flags);
722                         free_pages_bulk(zone, pcp->count, &pcp->list, 0);
723                         pcp->count = 0;
724                         local_irq_restore(flags);
725                 }
726         }
727 }
728
729 #ifdef CONFIG_PM
730
731 void mark_free_pages(struct zone *zone)
732 {
733         unsigned long pfn, max_zone_pfn;
734         unsigned long flags;
735         int order;
736         struct list_head *curr;
737
738         if (!zone->spanned_pages)
739                 return;
740
741         spin_lock_irqsave(&zone->lock, flags);
742
743         max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
744         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
745                 if (pfn_valid(pfn)) {
746                         struct page *page = pfn_to_page(pfn);
747
748                         if (!swsusp_page_is_forbidden(page))
749                                 swsusp_unset_page_free(page);
750                 }
751
752         for (order = MAX_ORDER - 1; order >= 0; --order)
753                 list_for_each(curr, &zone->free_area[order].free_list) {
754                         unsigned long i;
755
756                         pfn = page_to_pfn(list_entry(curr, struct page, lru));
757                         for (i = 0; i < (1UL << order); i++)
758                                 swsusp_set_page_free(pfn_to_page(pfn + i));
759                 }
760
761         spin_unlock_irqrestore(&zone->lock, flags);
762 }
763
764 /*
765  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
766  */
767 void drain_local_pages(void)
768 {
769         unsigned long flags;
770
771         local_irq_save(flags);  
772         __drain_pages(smp_processor_id());
773         local_irq_restore(flags);       
774 }
775 #endif /* CONFIG_PM */
776
777 /*
778  * Free a 0-order page
779  */
780 static void fastcall free_hot_cold_page(struct page *page, int cold)
781 {
782         struct zone *zone = page_zone(page);
783         struct per_cpu_pages *pcp;
784         unsigned long flags;
785
786         if (PageAnon(page))
787                 page->mapping = NULL;
788         if (free_pages_check(page))
789                 return;
790
791         if (!PageHighMem(page))
792                 debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
793         arch_free_page(page, 0);
794         kernel_map_pages(page, 1, 0);
795
796         pcp = &zone_pcp(zone, get_cpu())->pcp[cold];
797         local_irq_save(flags);
798         __count_vm_event(PGFREE);
799         list_add(&page->lru, &pcp->list);
800         pcp->count++;
801         if (pcp->count >= pcp->high) {
802                 free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
803                 pcp->count -= pcp->batch;
804         }
805         local_irq_restore(flags);
806         put_cpu();
807 }
808
809 void fastcall free_hot_page(struct page *page)
810 {
811         free_hot_cold_page(page, 0);
812 }
813         
814 void fastcall free_cold_page(struct page *page)
815 {
816         free_hot_cold_page(page, 1);
817 }
818
819 /*
820  * split_page takes a non-compound higher-order page, and splits it into
821  * n (1<<order) sub-pages: page[0..n]
822  * Each sub-page must be freed individually.
823  *
824  * Note: this is probably too low level an operation for use in drivers.
825  * Please consult with lkml before using this in your driver.
826  */
827 void split_page(struct page *page, unsigned int order)
828 {
829         int i;
830
831         VM_BUG_ON(PageCompound(page));
832         VM_BUG_ON(!page_count(page));
833         for (i = 1; i < (1 << order); i++)
834                 set_page_refcounted(page + i);
835 }
836
837 /*
838  * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
839  * we cheat by calling it from here, in the order > 0 path.  Saves a branch
840  * or two.
841  */
842 static struct page *buffered_rmqueue(struct zonelist *zonelist,
843                         struct zone *zone, int order, gfp_t gfp_flags)
844 {
845         unsigned long flags;
846         struct page *page;
847         int cold = !!(gfp_flags & __GFP_COLD);
848         int cpu;
849
850 again:
851         cpu  = get_cpu();
852         if (likely(order == 0)) {
853                 struct per_cpu_pages *pcp;
854
855                 pcp = &zone_pcp(zone, cpu)->pcp[cold];
856                 local_irq_save(flags);
857                 if (!pcp->count) {
858                         pcp->count = rmqueue_bulk(zone, 0,
859                                                 pcp->batch, &pcp->list);
860                         if (unlikely(!pcp->count))
861                                 goto failed;
862                 }
863                 page = list_entry(pcp->list.next, struct page, lru);
864                 list_del(&page->lru);
865                 pcp->count--;
866         } else {
867                 spin_lock_irqsave(&zone->lock, flags);
868                 page = __rmqueue(zone, order);
869                 spin_unlock(&zone->lock);
870                 if (!page)
871                         goto failed;
872         }
873
874         __count_zone_vm_events(PGALLOC, zone, 1 << order);
875         zone_statistics(zonelist, zone);
876         local_irq_restore(flags);
877         put_cpu();
878
879         VM_BUG_ON(bad_range(zone, page));
880         if (prep_new_page(page, order, gfp_flags))
881                 goto again;
882         return page;
883
884 failed:
885         local_irq_restore(flags);
886         put_cpu();
887         return NULL;
888 }
889
890 #define ALLOC_NO_WATERMARKS     0x01 /* don't check watermarks at all */
891 #define ALLOC_WMARK_MIN         0x02 /* use pages_min watermark */
892 #define ALLOC_WMARK_LOW         0x04 /* use pages_low watermark */
893 #define ALLOC_WMARK_HIGH        0x08 /* use pages_high watermark */
894 #define ALLOC_HARDER            0x10 /* try to alloc harder */
895 #define ALLOC_HIGH              0x20 /* __GFP_HIGH set */
896 #define ALLOC_CPUSET            0x40 /* check for correct cpuset */
897
898 #ifdef CONFIG_FAIL_PAGE_ALLOC
899
900 static struct fail_page_alloc_attr {
901         struct fault_attr attr;
902
903         u32 ignore_gfp_highmem;
904         u32 ignore_gfp_wait;
905         u32 min_order;
906
907 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
908
909         struct dentry *ignore_gfp_highmem_file;
910         struct dentry *ignore_gfp_wait_file;
911         struct dentry *min_order_file;
912
913 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
914
915 } fail_page_alloc = {
916         .attr = FAULT_ATTR_INITIALIZER,
917         .ignore_gfp_wait = 1,
918         .ignore_gfp_highmem = 1,
919         .min_order = 1,
920 };
921
922 static int __init setup_fail_page_alloc(char *str)
923 {
924         return setup_fault_attr(&fail_page_alloc.attr, str);
925 }
926 __setup("fail_page_alloc=", setup_fail_page_alloc);
927
928 static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
929 {
930         if (order < fail_page_alloc.min_order)
931                 return 0;
932         if (gfp_mask & __GFP_NOFAIL)
933                 return 0;
934         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
935                 return 0;
936         if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
937                 return 0;
938
939         return should_fail(&fail_page_alloc.attr, 1 << order);
940 }
941
942 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
943
944 static int __init fail_page_alloc_debugfs(void)
945 {
946         mode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
947         struct dentry *dir;
948         int err;
949
950         err = init_fault_attr_dentries(&fail_page_alloc.attr,
951                                        "fail_page_alloc");
952         if (err)
953                 return err;
954         dir = fail_page_alloc.attr.dentries.dir;
955
956         fail_page_alloc.ignore_gfp_wait_file =
957                 debugfs_create_bool("ignore-gfp-wait", mode, dir,
958                                       &fail_page_alloc.ignore_gfp_wait);
959
960         fail_page_alloc.ignore_gfp_highmem_file =
961                 debugfs_create_bool("ignore-gfp-highmem", mode, dir,
962                                       &fail_page_alloc.ignore_gfp_highmem);
963         fail_page_alloc.min_order_file =
964                 debugfs_create_u32("min-order", mode, dir,
965                                    &fail_page_alloc.min_order);
966
967         if (!fail_page_alloc.ignore_gfp_wait_file ||
968             !fail_page_alloc.ignore_gfp_highmem_file ||
969             !fail_page_alloc.min_order_file) {
970                 err = -ENOMEM;
971                 debugfs_remove(fail_page_alloc.ignore_gfp_wait_file);
972                 debugfs_remove(fail_page_alloc.ignore_gfp_highmem_file);
973                 debugfs_remove(fail_page_alloc.min_order_file);
974                 cleanup_fault_attr_dentries(&fail_page_alloc.attr);
975         }
976
977         return err;
978 }
979
980 late_initcall(fail_page_alloc_debugfs);
981
982 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
983
984 #else /* CONFIG_FAIL_PAGE_ALLOC */
985
986 static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
987 {
988         return 0;
989 }
990
991 #endif /* CONFIG_FAIL_PAGE_ALLOC */
992
993 /*
994  * Return 1 if free pages are above 'mark'. This takes into account the order
995  * of the allocation.
996  */
997 int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
998                       int classzone_idx, int alloc_flags)
999 {
1000         /* free_pages my go negative - that's OK */
1001         long min = mark;
1002         long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;
1003         int o;
1004
1005         if (alloc_flags & ALLOC_HIGH)
1006                 min -= min / 2;
1007         if (alloc_flags & ALLOC_HARDER)
1008                 min -= min / 4;
1009
1010         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
1011                 return 0;
1012         for (o = 0; o < order; o++) {
1013                 /* At the next order, this order's pages become unavailable */
1014                 free_pages -= z->free_area[o].nr_free << o;
1015
1016                 /* Require fewer higher order pages to be free */
1017                 min >>= 1;
1018
1019                 if (free_pages <= min)
1020                         return 0;
1021         }
1022         return 1;
1023 }
1024
1025 #ifdef CONFIG_NUMA
1026 /*
1027  * zlc_setup - Setup for "zonelist cache".  Uses cached zone data to
1028  * skip over zones that are not allowed by the cpuset, or that have
1029  * been recently (in last second) found to be nearly full.  See further
1030  * comments in mmzone.h.  Reduces cache footprint of zonelist scans
1031  * that have to skip over alot of full or unallowed zones.
1032  *
1033  * If the zonelist cache is present in the passed in zonelist, then
1034  * returns a pointer to the allowed node mask (either the current
1035  * tasks mems_allowed, or node_online_map.)
1036  *
1037  * If the zonelist cache is not available for this zonelist, does
1038  * nothing and returns NULL.
1039  *
1040  * If the fullzones BITMAP in the zonelist cache is stale (more than
1041  * a second since last zap'd) then we zap it out (clear its bits.)
1042  *
1043  * We hold off even calling zlc_setup, until after we've checked the
1044  * first zone in the zonelist, on the theory that most allocations will
1045  * be satisfied from that first zone, so best to examine that zone as
1046  * quickly as we can.
1047  */
1048 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1049 {
1050         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1051         nodemask_t *allowednodes;       /* zonelist_cache approximation */
1052
1053         zlc = zonelist->zlcache_ptr;
1054         if (!zlc)
1055                 return NULL;
1056
1057         if (jiffies - zlc->last_full_zap > 1 * HZ) {
1058                 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1059                 zlc->last_full_zap = jiffies;
1060         }
1061
1062         allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
1063                                         &cpuset_current_mems_allowed :
1064                                         &node_online_map;
1065         return allowednodes;
1066 }
1067
1068 /*
1069  * Given 'z' scanning a zonelist, run a couple of quick checks to see
1070  * if it is worth looking at further for free memory:
1071  *  1) Check that the zone isn't thought to be full (doesn't have its
1072  *     bit set in the zonelist_cache fullzones BITMAP).
1073  *  2) Check that the zones node (obtained from the zonelist_cache
1074  *     z_to_n[] mapping) is allowed in the passed in allowednodes mask.
1075  * Return true (non-zero) if zone is worth looking at further, or
1076  * else return false (zero) if it is not.
1077  *
1078  * This check -ignores- the distinction between various watermarks,
1079  * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ...  If a zone is
1080  * found to be full for any variation of these watermarks, it will
1081  * be considered full for up to one second by all requests, unless
1082  * we are so low on memory on all allowed nodes that we are forced
1083  * into the second scan of the zonelist.
1084  *
1085  * In the second scan we ignore this zonelist cache and exactly
1086  * apply the watermarks to all zones, even it is slower to do so.
1087  * We are low on memory in the second scan, and should leave no stone
1088  * unturned looking for a free page.
1089  */
1090 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zone **z,
1091                                                 nodemask_t *allowednodes)
1092 {
1093         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1094         int i;                          /* index of *z in zonelist zones */
1095         int n;                          /* node that zone *z is on */
1096
1097         zlc = zonelist->zlcache_ptr;
1098         if (!zlc)
1099                 return 1;
1100
1101         i = z - zonelist->zones;
1102         n = zlc->z_to_n[i];
1103
1104         /* This zone is worth trying if it is allowed but not full */
1105         return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
1106 }
1107
1108 /*
1109  * Given 'z' scanning a zonelist, set the corresponding bit in
1110  * zlc->fullzones, so that subsequent attempts to allocate a page
1111  * from that zone don't waste time re-examining it.
1112  */
1113 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zone **z)
1114 {
1115         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1116         int i;                          /* index of *z in zonelist zones */
1117
1118         zlc = zonelist->zlcache_ptr;
1119         if (!zlc)
1120                 return;
1121
1122         i = z - zonelist->zones;
1123
1124         set_bit(i, zlc->fullzones);
1125 }
1126
1127 #else   /* CONFIG_NUMA */
1128
1129 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1130 {
1131         return NULL;
1132 }
1133
1134 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zone **z,
1135                                 nodemask_t *allowednodes)
1136 {
1137         return 1;
1138 }
1139
1140 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zone **z)
1141 {
1142 }
1143 #endif  /* CONFIG_NUMA */
1144
1145 /*
1146  * get_page_from_freelist goes through the zonelist trying to allocate
1147  * a page.
1148  */
1149 static struct page *
1150 get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
1151                 struct zonelist *zonelist, int alloc_flags)
1152 {
1153         struct zone **z;
1154         struct page *page = NULL;
1155         int classzone_idx = zone_idx(zonelist->zones[0]);
1156         struct zone *zone;
1157         nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
1158         int zlc_active = 0;             /* set if using zonelist_cache */
1159         int did_zlc_setup = 0;          /* just call zlc_setup() one time */
1160
1161 zonelist_scan:
1162         /*
1163          * Scan zonelist, looking for a zone with enough free.
1164          * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1165          */
1166         z = zonelist->zones;
1167
1168         do {
1169                 if (NUMA_BUILD && zlc_active &&
1170                         !zlc_zone_worth_trying(zonelist, z, allowednodes))
1171                                 continue;
1172                 zone = *z;
1173                 if (unlikely(NUMA_BUILD && (gfp_mask & __GFP_THISNODE) &&
1174                         zone->zone_pgdat != zonelist->zones[0]->zone_pgdat))
1175                                 break;
1176                 if ((alloc_flags & ALLOC_CPUSET) &&
1177                         !cpuset_zone_allowed_softwall(zone, gfp_mask))
1178                                 goto try_next_zone;
1179
1180                 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
1181                         unsigned long mark;
1182                         if (alloc_flags & ALLOC_WMARK_MIN)
1183                                 mark = zone->pages_min;
1184                         else if (alloc_flags & ALLOC_WMARK_LOW)
1185                                 mark = zone->pages_low;
1186                         else
1187                                 mark = zone->pages_high;
1188                         if (!zone_watermark_ok(zone, order, mark,
1189                                     classzone_idx, alloc_flags)) {
1190                                 if (!zone_reclaim_mode ||
1191                                     !zone_reclaim(zone, gfp_mask, order))
1192                                         goto this_zone_full;
1193                         }
1194                 }
1195
1196                 page = buffered_rmqueue(zonelist, zone, order, gfp_mask);
1197                 if (page)
1198                         break;
1199 this_zone_full:
1200                 if (NUMA_BUILD)
1201                         zlc_mark_zone_full(zonelist, z);
1202 try_next_zone:
1203                 if (NUMA_BUILD && !did_zlc_setup) {
1204                         /* we do zlc_setup after the first zone is tried */
1205                         allowednodes = zlc_setup(zonelist, alloc_flags);
1206                         zlc_active = 1;
1207                         did_zlc_setup = 1;
1208                 }
1209         } while (*(++z) != NULL);
1210
1211         if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
1212                 /* Disable zlc cache for second zonelist scan */
1213                 zlc_active = 0;
1214                 goto zonelist_scan;
1215         }
1216         return page;
1217 }
1218
1219 /*
1220  * This is the 'heart' of the zoned buddy allocator.
1221  */
1222 struct page * fastcall
1223 __alloc_pages(gfp_t gfp_mask, unsigned int order,
1224                 struct zonelist *zonelist)
1225 {
1226         const gfp_t wait = gfp_mask & __GFP_WAIT;
1227         struct zone **z;
1228         struct page *page;
1229         struct reclaim_state reclaim_state;
1230         struct task_struct *p = current;
1231         int do_retry;
1232         int alloc_flags;
1233         int did_some_progress;
1234
1235         might_sleep_if(wait);
1236
1237         if (should_fail_alloc_page(gfp_mask, order))
1238                 return NULL;
1239
1240 restart:
1241         z = zonelist->zones;  /* the list of zones suitable for gfp_mask */
1242
1243         if (unlikely(*z == NULL)) {
1244                 /* Should this ever happen?? */
1245                 return NULL;
1246         }
1247
1248         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
1249                                 zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);
1250         if (page)
1251                 goto got_pg;
1252
1253         /*
1254          * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
1255          * __GFP_NOWARN set) should not cause reclaim since the subsystem
1256          * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
1257          * using a larger set of nodes after it has established that the
1258          * allowed per node queues are empty and that nodes are
1259          * over allocated.
1260          */
1261         if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
1262                 goto nopage;
1263
1264         for (z = zonelist->zones; *z; z++)
1265                 wakeup_kswapd(*z, order);
1266
1267         /*
1268          * OK, we're below the kswapd watermark and have kicked background
1269          * reclaim. Now things get more complex, so set up alloc_flags according
1270          * to how we want to proceed.
1271          *
1272          * The caller may dip into page reserves a bit more if the caller
1273          * cannot run direct reclaim, or if the caller has realtime scheduling
1274          * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
1275          * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
1276          */
1277         alloc_flags = ALLOC_WMARK_MIN;
1278         if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
1279                 alloc_flags |= ALLOC_HARDER;
1280         if (gfp_mask & __GFP_HIGH)
1281                 alloc_flags |= ALLOC_HIGH;
1282         if (wait)
1283                 alloc_flags |= ALLOC_CPUSET;
1284
1285         /*
1286          * Go through the zonelist again. Let __GFP_HIGH and allocations
1287          * coming from realtime tasks go deeper into reserves.
1288          *
1289          * This is the last chance, in general, before the goto nopage.
1290          * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
1291          * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1292          */
1293         page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);
1294         if (page)
1295                 goto got_pg;
1296
1297         /* This allocation should allow future memory freeing. */
1298
1299 rebalance:
1300         if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
1301                         && !in_interrupt()) {
1302                 if (!(gfp_mask & __GFP_NOMEMALLOC)) {
1303 nofail_alloc:
1304                         /* go through the zonelist yet again, ignoring mins */
1305                         page = get_page_from_freelist(gfp_mask, order,
1306                                 zonelist, ALLOC_NO_WATERMARKS);
1307                         if (page)
1308                                 goto got_pg;
1309                         if (gfp_mask & __GFP_NOFAIL) {
1310                                 congestion_wait(WRITE, HZ/50);
1311                                 goto nofail_alloc;
1312                         }
1313                 }
1314                 goto nopage;
1315         }
1316
1317         /* Atomic allocations - we can't balance anything */
1318         if (!wait)
1319                 goto nopage;
1320
1321         cond_resched();
1322
1323         /* We now go into synchronous reclaim */
1324         cpuset_memory_pressure_bump();
1325         p->flags |= PF_MEMALLOC;
1326         reclaim_state.reclaimed_slab = 0;
1327         p->reclaim_state = &reclaim_state;
1328
1329         did_some_progress = try_to_free_pages(zonelist->zones, order, gfp_mask);
1330
1331         p->reclaim_state = NULL;
1332         p->flags &= ~PF_MEMALLOC;
1333
1334         cond_resched();
1335
1336         if (likely(did_some_progress)) {
1337                 page = get_page_from_freelist(gfp_mask, order,
1338                                                 zonelist, alloc_flags);
1339                 if (page)
1340                         goto got_pg;
1341         } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
1342                 /*
1343                  * Go through the zonelist yet one more time, keep
1344                  * very high watermark here, this is only to catch
1345                  * a parallel oom killing, we must fail if we're still
1346                  * under heavy pressure.
1347                  */
1348                 page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
1349                                 zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
1350                 if (page)
1351                         goto got_pg;
1352
1353                 out_of_memory(zonelist, gfp_mask, order);
1354                 goto restart;
1355         }
1356
1357         /*
1358          * Don't let big-order allocations loop unless the caller explicitly
1359          * requests that.  Wait for some write requests to complete then retry.
1360          *
1361          * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
1362          * <= 3, but that may not be true in other implementations.
1363          */
1364         do_retry = 0;
1365         if (!(gfp_mask & __GFP_NORETRY)) {
1366                 if ((order <= PAGE_ALLOC_COSTLY_ORDER) ||
1367                                                 (gfp_mask & __GFP_REPEAT))
1368                         do_retry = 1;
1369                 if (gfp_mask & __GFP_NOFAIL)
1370                         do_retry = 1;
1371         }
1372         if (do_retry) {
1373                 congestion_wait(WRITE, HZ/50);
1374                 goto rebalance;
1375         }
1376
1377 nopage:
1378         if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
1379                 printk(KERN_WARNING "%s: page allocation failure."
1380                         " order:%d, mode:0x%x\n",
1381                         p->comm, order, gfp_mask);
1382                 dump_stack();
1383                 show_mem();
1384         }
1385 got_pg:
1386         return page;
1387 }
1388
1389 EXPORT_SYMBOL(__alloc_pages);
1390
1391 /*
1392  * Common helper functions.
1393  */
1394 fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
1395 {
1396         struct page * page;
1397         page = alloc_pages(gfp_mask, order);
1398         if (!page)
1399                 return 0;
1400         return (unsigned long) page_address(page);
1401 }
1402
1403 EXPORT_SYMBOL(__get_free_pages);
1404
1405 fastcall unsigned long get_zeroed_page(gfp_t gfp_mask)
1406 {
1407         struct page * page;
1408
1409         /*
1410          * get_zeroed_page() returns a 32-bit address, which cannot represent
1411          * a highmem page
1412          */
1413         VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
1414
1415         page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
1416         if (page)
1417                 return (unsigned long) page_address(page);
1418         return 0;
1419 }
1420
1421 EXPORT_SYMBOL(get_zeroed_page);
1422
1423 void __pagevec_free(struct pagevec *pvec)
1424 {
1425         int i = pagevec_count(pvec);
1426
1427         while (--i >= 0)
1428                 free_hot_cold_page(pvec->pages[i], pvec->cold);
1429 }
1430
1431 fastcall void __free_pages(struct page *page, unsigned int order)
1432 {
1433         if (put_page_testzero(page)) {
1434                 if (order == 0)
1435                         free_hot_page(page);
1436                 else
1437                         __free_pages_ok(page, order);
1438         }
1439 }
1440
1441 EXPORT_SYMBOL(__free_pages);
1442
1443 fastcall void free_pages(unsigned long addr, unsigned int order)
1444 {
1445         if (addr != 0) {
1446                 VM_BUG_ON(!virt_addr_valid((void *)addr));
1447                 __free_pages(virt_to_page((void *)addr), order);
1448         }
1449 }
1450
1451 EXPORT_SYMBOL(free_pages);
1452
1453 static unsigned int nr_free_zone_pages(int offset)
1454 {
1455         /* Just pick one node, since fallback list is circular */
1456         pg_data_t *pgdat = NODE_DATA(numa_node_id());
1457         unsigned int sum = 0;
1458
1459         struct zonelist *zonelist = pgdat->node_zonelists + offset;
1460         struct zone **zonep = zonelist->zones;
1461         struct zone *zone;
1462
1463         for (zone = *zonep++; zone; zone = *zonep++) {
1464                 unsigned long size = zone->present_pages;
1465                 unsigned long high = zone->pages_high;
1466                 if (size > high)
1467                         sum += size - high;
1468         }
1469
1470         return sum;
1471 }
1472
1473 /*
1474  * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
1475  */
1476 unsigned int nr_free_buffer_pages(void)
1477 {
1478         return nr_free_zone_pages(gfp_zone(GFP_USER));
1479 }
1480 EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
1481
1482 /*
1483  * Amount of free RAM allocatable within all zones
1484  */
1485 unsigned int nr_free_pagecache_pages(void)
1486 {
1487         return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
1488 }
1489
1490 static inline void show_node(struct zone *zone)
1491 {
1492         if (NUMA_BUILD)
1493                 printk("Node %d ", zone_to_nid(zone));
1494 }
1495
1496 void si_meminfo(struct sysinfo *val)
1497 {
1498         val->totalram = totalram_pages;
1499         val->sharedram = 0;
1500         val->freeram = global_page_state(NR_FREE_PAGES);
1501         val->bufferram = nr_blockdev_pages();
1502         val->totalhigh = totalhigh_pages;
1503         val->freehigh = nr_free_highpages();
1504         val->mem_unit = PAGE_SIZE;
1505 }
1506
1507 EXPORT_SYMBOL(si_meminfo);
1508
1509 #ifdef CONFIG_NUMA
1510 void si_meminfo_node(struct sysinfo *val, int nid)
1511 {
1512         pg_data_t *pgdat = NODE_DATA(nid);
1513
1514         val->totalram = pgdat->node_present_pages;
1515         val->freeram = node_page_state(nid, NR_FREE_PAGES);
1516 #ifdef CONFIG_HIGHMEM
1517         val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
1518         val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
1519                         NR_FREE_PAGES);
1520 #else
1521         val->totalhigh = 0;
1522         val->freehigh = 0;
1523 #endif
1524         val->mem_unit = PAGE_SIZE;
1525 }
1526 #endif
1527
1528 #define K(x) ((x) << (PAGE_SHIFT-10))
1529
1530 /*
1531  * Show free area list (used inside shift_scroll-lock stuff)
1532  * We also calculate the percentage fragmentation. We do this by counting the
1533  * memory on each free list with the exception of the first item on the list.
1534  */
1535 void show_free_areas(void)
1536 {
1537         int cpu;
1538         struct zone *zone;
1539
1540         for_each_zone(zone) {
1541                 if (!populated_zone(zone))
1542                         continue;
1543
1544                 show_node(zone);
1545                 printk("%s per-cpu:\n", zone->name);
1546
1547                 for_each_online_cpu(cpu) {
1548                         struct per_cpu_pageset *pageset;
1549
1550                         pageset = zone_pcp(zone, cpu);
1551
1552                         printk("CPU %4d: Hot: hi:%5d, btch:%4d usd:%4d   "
1553                                "Cold: hi:%5d, btch:%4d usd:%4d\n",
1554                                cpu, pageset->pcp[0].high,
1555                                pageset->pcp[0].batch, pageset->pcp[0].count,
1556                                pageset->pcp[1].high, pageset->pcp[1].batch,
1557                                pageset->pcp[1].count);
1558                 }
1559         }
1560
1561         printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu unstable:%lu\n"
1562                 " free:%lu slab:%lu mapped:%lu pagetables:%lu bounce:%lu\n",
1563                 global_page_state(NR_ACTIVE),
1564                 global_page_state(NR_INACTIVE),
1565                 global_page_state(NR_FILE_DIRTY),
1566                 global_page_state(NR_WRITEBACK),
1567                 global_page_state(NR_UNSTABLE_NFS),
1568                 global_page_state(NR_FREE_PAGES),
1569                 global_page_state(NR_SLAB_RECLAIMABLE) +
1570                         global_page_state(NR_SLAB_UNRECLAIMABLE),
1571                 global_page_state(NR_FILE_MAPPED),
1572                 global_page_state(NR_PAGETABLE),
1573                 global_page_state(NR_BOUNCE));
1574
1575         for_each_zone(zone) {
1576                 int i;
1577
1578                 if (!populated_zone(zone))
1579                         continue;
1580
1581                 show_node(zone);
1582                 printk("%s"
1583                         " free:%lukB"
1584                         " min:%lukB"
1585                         " low:%lukB"
1586                         " high:%lukB"
1587                         " active:%lukB"
1588                         " inactive:%lukB"
1589                         " present:%lukB"
1590                         " pages_scanned:%lu"
1591                         " all_unreclaimable? %s"
1592                         "\n",
1593                         zone->name,
1594                         K(zone_page_state(zone, NR_FREE_PAGES)),
1595                         K(zone->pages_min),
1596                         K(zone->pages_low),
1597                         K(zone->pages_high),
1598                         K(zone_page_state(zone, NR_ACTIVE)),
1599                         K(zone_page_state(zone, NR_INACTIVE)),
1600                         K(zone->present_pages),
1601                         zone->pages_scanned,
1602                         (zone->all_unreclaimable ? "yes" : "no")
1603                         );
1604                 printk("lowmem_reserve[]:");
1605                 for (i = 0; i < MAX_NR_ZONES; i++)
1606                         printk(" %lu", zone->lowmem_reserve[i]);
1607                 printk("\n");
1608         }
1609
1610         for_each_zone(zone) {
1611                 unsigned long nr[MAX_ORDER], flags, order, total = 0;
1612
1613                 if (!populated_zone(zone))
1614                         continue;
1615
1616                 show_node(zone);
1617                 printk("%s: ", zone->name);
1618
1619                 spin_lock_irqsave(&zone->lock, flags);
1620                 for (order = 0; order < MAX_ORDER; order++) {
1621                         nr[order] = zone->free_area[order].nr_free;
1622                         total += nr[order] << order;
1623                 }
1624                 spin_unlock_irqrestore(&zone->lock, flags);
1625                 for (order = 0; order < MAX_ORDER; order++)
1626                         printk("%lu*%lukB ", nr[order], K(1UL) << order);
1627                 printk("= %lukB\n", K(total));
1628         }
1629
1630         show_swap_cache_info();
1631 }
1632
1633 /*
1634  * Builds allocation fallback zone lists.
1635  *
1636  * Add all populated zones of a node to the zonelist.
1637  */
1638 static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
1639                                 int nr_zones, enum zone_type zone_type)
1640 {
1641         struct zone *zone;
1642
1643         BUG_ON(zone_type >= MAX_NR_ZONES);
1644         zone_type++;
1645
1646         do {
1647                 zone_type--;
1648                 zone = pgdat->node_zones + zone_type;
1649                 if (populated_zone(zone)) {
1650                         zonelist->zones[nr_zones++] = zone;
1651                         check_highest_zone(zone_type);
1652                 }
1653
1654         } while (zone_type);
1655         return nr_zones;
1656 }
1657
1658
1659 /*
1660  *  zonelist_order:
1661  *  0 = automatic detection of better ordering.
1662  *  1 = order by ([node] distance, -zonetype)
1663  *  2 = order by (-zonetype, [node] distance)
1664  *
1665  *  If not NUMA, ZONELIST_ORDER_ZONE and ZONELIST_ORDER_NODE will create
1666  *  the same zonelist. So only NUMA can configure this param.
1667  */
1668 #define ZONELIST_ORDER_DEFAULT  0
1669 #define ZONELIST_ORDER_NODE     1
1670 #define ZONELIST_ORDER_ZONE     2
1671
1672 /* zonelist order in the kernel.
1673  * set_zonelist_order() will set this to NODE or ZONE.
1674  */
1675 static int current_zonelist_order = ZONELIST_ORDER_DEFAULT;
1676 static char zonelist_order_name[3][8] = {"Default", "Node", "Zone"};
1677
1678
1679 #ifdef CONFIG_NUMA
1680 /* The value user specified ....changed by config */
1681 static int user_zonelist_order = ZONELIST_ORDER_DEFAULT;
1682 /* string for sysctl */
1683 #define NUMA_ZONELIST_ORDER_LEN 16
1684 char numa_zonelist_order[16] = "default";
1685
1686 /*
1687  * interface for configure zonelist ordering.
1688  * command line option "numa_zonelist_order"
1689  *      = "[dD]efault   - default, automatic configuration.
1690  *      = "[nN]ode      - order by node locality, then by zone within node
1691  *      = "[zZ]one      - order by zone, then by locality within zone
1692  */
1693
1694 static int __parse_numa_zonelist_order(char *s)
1695 {
1696         if (*s == 'd' || *s == 'D') {
1697                 user_zonelist_order = ZONELIST_ORDER_DEFAULT;
1698         } else if (*s == 'n' || *s == 'N') {
1699                 user_zonelist_order = ZONELIST_ORDER_NODE;
1700         } else if (*s == 'z' || *s == 'Z') {
1701                 user_zonelist_order = ZONELIST_ORDER_ZONE;
1702         } else {
1703                 printk(KERN_WARNING
1704                         "Ignoring invalid numa_zonelist_order value:  "
1705                         "%s\n", s);
1706                 return -EINVAL;
1707         }
1708         return 0;
1709 }
1710
1711 static __init int setup_numa_zonelist_order(char *s)
1712 {
1713         if (s)
1714                 return __parse_numa_zonelist_order(s);
1715         return 0;
1716 }
1717 early_param("numa_zonelist_order", setup_numa_zonelist_order);
1718
1719 /*
1720  * sysctl handler for numa_zonelist_order
1721  */
1722 int numa_zonelist_order_handler(ctl_table *table, int write,
1723                 struct file *file, void __user *buffer, size_t *length,
1724                 loff_t *ppos)
1725 {
1726         char saved_string[NUMA_ZONELIST_ORDER_LEN];
1727         int ret;
1728
1729         if (write)
1730                 strncpy(saved_string, (char*)table->data,
1731                         NUMA_ZONELIST_ORDER_LEN);
1732         ret = proc_dostring(table, write, file, buffer, length, ppos);
1733         if (ret)
1734                 return ret;
1735         if (write) {
1736                 int oldval = user_zonelist_order;
1737                 if (__parse_numa_zonelist_order((char*)table->data)) {
1738                         /*
1739                          * bogus value.  restore saved string
1740                          */
1741                         strncpy((char*)table->data, saved_string,
1742                                 NUMA_ZONELIST_ORDER_LEN);
1743                         user_zonelist_order = oldval;
1744                 } else if (oldval != user_zonelist_order)
1745                         build_all_zonelists();
1746         }
1747         return 0;
1748 }
1749
1750
1751 #define MAX_NODE_LOAD (num_online_nodes())
1752 static int node_load[MAX_NUMNODES];
1753
1754 /**
1755  * find_next_best_node - find the next node that should appear in a given node's fallback list
1756  * @node: node whose fallback list we're appending
1757  * @used_node_mask: nodemask_t of already used nodes
1758  *
1759  * We use a number of factors to determine which is the next node that should
1760  * appear on a given node's fallback list.  The node should not have appeared
1761  * already in @node's fallback list, and it should be the next closest node
1762  * according to the distance array (which contains arbitrary distance values
1763  * from each node to each node in the system), and should also prefer nodes
1764  * with no CPUs, since presumably they'll have very little allocation pressure
1765  * on them otherwise.
1766  * It returns -1 if no node is found.
1767  */
1768 static int find_next_best_node(int node, nodemask_t *used_node_mask)
1769 {
1770         int n, val;
1771         int min_val = INT_MAX;
1772         int best_node = -1;
1773
1774         /* Use the local node if we haven't already */
1775         if (!node_isset(node, *used_node_mask)) {
1776                 node_set(node, *used_node_mask);
1777                 return node;
1778         }
1779
1780         for_each_online_node(n) {
1781                 cpumask_t tmp;
1782
1783                 /* Don't want a node to appear more than once */
1784                 if (node_isset(n, *used_node_mask))
1785                         continue;
1786
1787                 /* Use the distance array to find the distance */
1788                 val = node_distance(node, n);
1789
1790                 /* Penalize nodes under us ("prefer the next node") */
1791                 val += (n < node);
1792
1793                 /* Give preference to headless and unused nodes */
1794                 tmp = node_to_cpumask(n);
1795                 if (!cpus_empty(tmp))
1796                         val += PENALTY_FOR_NODE_WITH_CPUS;
1797
1798                 /* Slight preference for less loaded node */
1799                 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
1800                 val += node_load[n];
1801
1802                 if (val < min_val) {
1803                         min_val = val;
1804                         best_node = n;
1805                 }
1806         }
1807
1808         if (best_node >= 0)
1809                 node_set(best_node, *used_node_mask);
1810
1811         return best_node;
1812 }
1813
1814
1815 /*
1816  * Build zonelists ordered by node and zones within node.
1817  * This results in maximum locality--normal zone overflows into local
1818  * DMA zone, if any--but risks exhausting DMA zone.
1819  */
1820 static void build_zonelists_in_node_order(pg_data_t *pgdat, int node)
1821 {
1822         enum zone_type i;
1823         int j;
1824         struct zonelist *zonelist;
1825
1826         for (i = 0; i < MAX_NR_ZONES; i++) {
1827                 zonelist = pgdat->node_zonelists + i;
1828                 for (j = 0; zonelist->zones[j] != NULL; j++)
1829                         ;
1830                 j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
1831                 zonelist->zones[j] = NULL;
1832         }
1833 }
1834
1835 /*
1836  * Build zonelists ordered by zone and nodes within zones.
1837  * This results in conserving DMA zone[s] until all Normal memory is
1838  * exhausted, but results in overflowing to remote node while memory
1839  * may still exist in local DMA zone.
1840  */
1841 static int node_order[MAX_NUMNODES];
1842
1843 static void build_zonelists_in_zone_order(pg_data_t *pgdat, int nr_nodes)
1844 {
1845         enum zone_type i;
1846         int pos, j, node;
1847         int zone_type;          /* needs to be signed */
1848         struct zone *z;
1849         struct zonelist *zonelist;
1850
1851         for (i = 0; i < MAX_NR_ZONES; i++) {
1852                 zonelist = pgdat->node_zonelists + i;
1853                 pos = 0;
1854                 for (zone_type = i; zone_type >= 0; zone_type--) {
1855                         for (j = 0; j < nr_nodes; j++) {
1856                                 node = node_order[j];
1857                                 z = &NODE_DATA(node)->node_zones[zone_type];
1858                                 if (populated_zone(z)) {
1859                                         zonelist->zones[pos++] = z;
1860                                         check_highest_zone(zone_type);
1861                                 }
1862                         }
1863                 }
1864                 zonelist->zones[pos] = NULL;
1865         }
1866 }
1867
1868 static int default_zonelist_order(void)
1869 {
1870         int nid, zone_type;
1871         unsigned long low_kmem_size,total_size;
1872         struct zone *z;
1873         int average_size;
1874         /*
1875          * ZONE_DMA and ZONE_DMA32 can be very small area in the sytem.
1876          * If they are really small and used heavily, the system can fall
1877          * into OOM very easily.
1878          * This function detect ZONE_DMA/DMA32 size and confgigures zone order.
1879          */
1880         /* Is there ZONE_NORMAL ? (ex. ppc has only DMA zone..) */
1881         low_kmem_size = 0;
1882         total_size = 0;
1883         for_each_online_node(nid) {
1884                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
1885                         z = &NODE_DATA(nid)->node_zones[zone_type];
1886                         if (populated_zone(z)) {
1887                                 if (zone_type < ZONE_NORMAL)
1888                                         low_kmem_size += z->present_pages;
1889                                 total_size += z->present_pages;
1890                         }
1891                 }
1892         }
1893         if (!low_kmem_size ||  /* there are no DMA area. */
1894             low_kmem_size > total_size/2) /* DMA/DMA32 is big. */
1895                 return ZONELIST_ORDER_NODE;
1896         /*
1897          * look into each node's config.
1898          * If there is a node whose DMA/DMA32 memory is very big area on
1899          * local memory, NODE_ORDER may be suitable.
1900          */
1901         average_size = total_size / (num_online_nodes() + 1);
1902         for_each_online_node(nid) {
1903                 low_kmem_size = 0;
1904                 total_size = 0;
1905                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
1906                         z = &NODE_DATA(nid)->node_zones[zone_type];
1907                         if (populated_zone(z)) {
1908                                 if (zone_type < ZONE_NORMAL)
1909                                         low_kmem_size += z->present_pages;
1910                                 total_size += z->present_pages;
1911                         }
1912                 }
1913                 if (low_kmem_size &&
1914                     total_size > average_size && /* ignore small node */
1915                     low_kmem_size > total_size * 70/100)
1916                         return ZONELIST_ORDER_NODE;
1917         }
1918         return ZONELIST_ORDER_ZONE;
1919 }
1920
1921 static void set_zonelist_order(void)
1922 {
1923         if (user_zonelist_order == ZONELIST_ORDER_DEFAULT)
1924                 current_zonelist_order = default_zonelist_order();
1925         else
1926                 current_zonelist_order = user_zonelist_order;
1927 }
1928
1929 static void build_zonelists(pg_data_t *pgdat)
1930 {
1931         int j, node, load;
1932         enum zone_type i;
1933         nodemask_t used_mask;
1934         int local_node, prev_node;
1935         struct zonelist *zonelist;
1936         int order = current_zonelist_order;
1937
1938         /* initialize zonelists */
1939         for (i = 0; i < MAX_NR_ZONES; i++) {
1940                 zonelist = pgdat->node_zonelists + i;
1941                 zonelist->zones[0] = NULL;
1942         }
1943
1944         /* NUMA-aware ordering of nodes */
1945         local_node = pgdat->node_id;
1946         load = num_online_nodes();
1947         prev_node = local_node;
1948         nodes_clear(used_mask);
1949
1950         memset(node_load, 0, sizeof(node_load));
1951         memset(node_order, 0, sizeof(node_order));
1952         j = 0;
1953
1954         while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
1955                 int distance = node_distance(local_node, node);
1956
1957                 /*
1958                  * If another node is sufficiently far away then it is better
1959                  * to reclaim pages in a zone before going off node.
1960                  */
1961                 if (distance > RECLAIM_DISTANCE)
1962                         zone_reclaim_mode = 1;
1963
1964                 /*
1965                  * We don't want to pressure a particular node.
1966                  * So adding penalty to the first node in same
1967                  * distance group to make it round-robin.
1968                  */
1969                 if (distance != node_distance(local_node, prev_node))
1970                         node_load[node] = load;
1971
1972                 prev_node = node;
1973                 load--;
1974                 if (order == ZONELIST_ORDER_NODE)
1975                         build_zonelists_in_node_order(pgdat, node);
1976                 else
1977                         node_order[j++] = node; /* remember order */
1978         }
1979
1980         if (order == ZONELIST_ORDER_ZONE) {
1981                 /* calculate node order -- i.e., DMA last! */
1982                 build_zonelists_in_zone_order(pgdat, j);
1983         }
1984 }
1985
1986 /* Construct the zonelist performance cache - see further mmzone.h */
1987 static void build_zonelist_cache(pg_data_t *pgdat)
1988 {
1989         int i;
1990
1991         for (i = 0; i < MAX_NR_ZONES; i++) {
1992                 struct zonelist *zonelist;
1993                 struct zonelist_cache *zlc;
1994                 struct zone **z;
1995
1996                 zonelist = pgdat->node_zonelists + i;
1997                 zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
1998                 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1999                 for (z = zonelist->zones; *z; z++)
2000                         zlc->z_to_n[z - zonelist->zones] = zone_to_nid(*z);
2001         }
2002 }
2003
2004
2005 #else   /* CONFIG_NUMA */
2006
2007 static void set_zonelist_order(void)
2008 {
2009         current_zonelist_order = ZONELIST_ORDER_ZONE;
2010 }
2011
2012 static void build_zonelists(pg_data_t *pgdat)
2013 {
2014         int node, local_node;
2015         enum zone_type i,j;
2016
2017         local_node = pgdat->node_id;
2018         for (i = 0; i < MAX_NR_ZONES; i++) {
2019                 struct zonelist *zonelist;
2020
2021                 zonelist = pgdat->node_zonelists + i;
2022
2023                 j = build_zonelists_node(pgdat, zonelist, 0, i);
2024                 /*
2025                  * Now we build the zonelist so that it contains the zones
2026                  * of all the other nodes.
2027                  * We don't want to pressure a particular node, so when
2028                  * building the zones for node N, we make sure that the
2029                  * zones coming right after the local ones are those from
2030                  * node N+1 (modulo N)
2031                  */
2032                 for (node = local_node + 1; node < MAX_NUMNODES; node++) {
2033                         if (!node_online(node))
2034                                 continue;
2035                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
2036                 }
2037                 for (node = 0; node < local_node; node++) {
2038                         if (!node_online(node))
2039                                 continue;
2040                         j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
2041                 }
2042
2043                 zonelist->zones[j] = NULL;
2044         }
2045 }
2046
2047 /* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
2048 static void build_zonelist_cache(pg_data_t *pgdat)
2049 {
2050         int i;
2051
2052         for (i = 0; i < MAX_NR_ZONES; i++)
2053                 pgdat->node_zonelists[i].zlcache_ptr = NULL;
2054 }
2055
2056 #endif  /* CONFIG_NUMA */
2057
2058 /* return values int ....just for stop_machine_run() */
2059 static int __build_all_zonelists(void *dummy)
2060 {
2061         int nid;
2062
2063         for_each_online_node(nid) {
2064                 build_zonelists(NODE_DATA(nid));
2065                 build_zonelist_cache(NODE_DATA(nid));
2066         }
2067         return 0;
2068 }
2069
2070 void build_all_zonelists(void)
2071 {
2072         set_zonelist_order();
2073
2074         if (system_state == SYSTEM_BOOTING) {
2075                 __build_all_zonelists(NULL);
2076                 cpuset_init_current_mems_allowed();
2077         } else {
2078                 /* we have to stop all cpus to guaranntee there is no user
2079                    of zonelist */
2080                 stop_machine_run(__build_all_zonelists, NULL, NR_CPUS);
2081                 /* cpuset refresh routine should be here */
2082         }
2083         vm_total_pages = nr_free_pagecache_pages();
2084         printk("Built %i zonelists in %s order.  Total pages: %ld\n",
2085                         num_online_nodes(),
2086                         zonelist_order_name[current_zonelist_order],
2087                         vm_total_pages);
2088 #ifdef CONFIG_NUMA
2089         printk("Policy zone: %s\n", zone_names[policy_zone]);
2090 #endif
2091 }
2092
2093 /*
2094  * Helper functions to size the waitqueue hash table.
2095  * Essentially these want to choose hash table sizes sufficiently
2096  * large so that collisions trying to wait on pages are rare.
2097  * But in fact, the number of active page waitqueues on typical
2098  * systems is ridiculously low, less than 200. So this is even
2099  * conservative, even though it seems large.
2100  *
2101  * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
2102  * waitqueues, i.e. the size of the waitq table given the number of pages.
2103  */
2104 #define PAGES_PER_WAITQUEUE     256
2105
2106 #ifndef CONFIG_MEMORY_HOTPLUG
2107 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
2108 {
2109         unsigned long size = 1;
2110
2111         pages /= PAGES_PER_WAITQUEUE;
2112
2113         while (size < pages)
2114                 size <<= 1;
2115
2116         /*
2117          * Once we have dozens or even hundreds of threads sleeping
2118          * on IO we've got bigger problems than wait queue collision.
2119          * Limit the size of the wait table to a reasonable size.
2120          */
2121         size = min(size, 4096UL);
2122
2123         return max(size, 4UL);
2124 }
2125 #else
2126 /*
2127  * A zone's size might be changed by hot-add, so it is not possible to determine
2128  * a suitable size for its wait_table.  So we use the maximum size now.
2129  *
2130  * The max wait table size = 4096 x sizeof(wait_queue_head_t).   ie:
2131  *
2132  *    i386 (preemption config)    : 4096 x 16 = 64Kbyte.
2133  *    ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
2134  *    ia64, x86-64 (preemption)   : 4096 x 24 = 96Kbyte.
2135  *
2136  * The maximum entries are prepared when a zone's memory is (512K + 256) pages
2137  * or more by the traditional way. (See above).  It equals:
2138  *
2139  *    i386, x86-64, powerpc(4K page size) : =  ( 2G + 1M)byte.
2140  *    ia64(16K page size)                 : =  ( 8G + 4M)byte.
2141  *    powerpc (64K page size)             : =  (32G +16M)byte.
2142  */
2143 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
2144 {
2145         return 4096UL;
2146 }
2147 #endif
2148
2149 /*
2150  * This is an integer logarithm so that shifts can be used later
2151  * to extract the more random high bits from the multiplicative
2152  * hash function before the remainder is taken.
2153  */
2154 static inline unsigned long wait_table_bits(unsigned long size)
2155 {
2156         return ffz(~size);
2157 }
2158
2159 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
2160
2161 /*
2162  * Initially all pages are reserved - free ones are freed
2163  * up by free_all_bootmem() once the early boot process is
2164  * done. Non-atomic initialization, single-pass.
2165  */
2166 void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
2167                 unsigned long start_pfn, enum memmap_context context)
2168 {
2169         struct page *page;
2170         unsigned long end_pfn = start_pfn + size;
2171         unsigned long pfn;
2172
2173         for (pfn = start_pfn; pfn < end_pfn; pfn++) {
2174                 /*
2175                  * There can be holes in boot-time mem_map[]s
2176                  * handed to this function.  They do not
2177                  * exist on hotplugged memory.
2178                  */
2179                 if (context == MEMMAP_EARLY) {
2180                         if (!early_pfn_valid(pfn))
2181                                 continue;
2182                         if (!early_pfn_in_nid(pfn, nid))
2183                                 continue;
2184                 }
2185                 page = pfn_to_page(pfn);
2186                 set_page_links(page, zone, nid, pfn);
2187                 init_page_count(page);
2188                 reset_page_mapcount(page);
2189                 SetPageReserved(page);
2190                 INIT_LIST_HEAD(&page->lru);
2191 #ifdef WANT_PAGE_VIRTUAL
2192                 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
2193                 if (!is_highmem_idx(zone))
2194                         set_page_address(page, __va(pfn << PAGE_SHIFT));
2195 #endif
2196         }
2197 }
2198
2199 static void __meminit zone_init_free_lists(struct pglist_data *pgdat,
2200                                 struct zone *zone, unsigned long size)
2201 {
2202         int order;
2203         for (order = 0; order < MAX_ORDER ; order++) {
2204                 INIT_LIST_HEAD(&zone->free_area[order].free_list);
2205                 zone->free_area[order].nr_free = 0;
2206         }
2207 }
2208
2209 #ifndef __HAVE_ARCH_MEMMAP_INIT
2210 #define memmap_init(size, nid, zone, start_pfn) \
2211         memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY)
2212 #endif
2213
2214 static int __devinit zone_batchsize(struct zone *zone)
2215 {
2216         int batch;
2217
2218         /*
2219          * The per-cpu-pages pools are set to around 1000th of the
2220          * size of the zone.  But no more than 1/2 of a meg.
2221          *
2222          * OK, so we don't know how big the cache is.  So guess.
2223          */
2224         batch = zone->present_pages / 1024;
2225         if (batch * PAGE_SIZE > 512 * 1024)
2226                 batch = (512 * 1024) / PAGE_SIZE;
2227         batch /= 4;             /* We effectively *= 4 below */
2228         if (batch < 1)
2229                 batch = 1;
2230
2231         /*
2232          * Clamp the batch to a 2^n - 1 value. Having a power
2233          * of 2 value was found to be more likely to have
2234          * suboptimal cache aliasing properties in some cases.
2235          *
2236          * For example if 2 tasks are alternately allocating
2237          * batches of pages, one task can end up with a lot
2238          * of pages of one half of the possible page colors
2239          * and the other with pages of the other colors.
2240          */
2241         batch = (1 << (fls(batch + batch/2)-1)) - 1;
2242
2243         return batch;
2244 }
2245
2246 inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
2247 {
2248         struct per_cpu_pages *pcp;
2249
2250         memset(p, 0, sizeof(*p));
2251
2252         pcp = &p->pcp[0];               /* hot */
2253         pcp->count = 0;
2254         pcp->high = 6 * batch;
2255         pcp->batch = max(1UL, 1 * batch);
2256         INIT_LIST_HEAD(&pcp->list);
2257
2258         pcp = &p->pcp[1];               /* cold*/
2259         pcp->count = 0;
2260         pcp->high = 2 * batch;
2261         pcp->batch = max(1UL, batch/2);
2262         INIT_LIST_HEAD(&pcp->list);
2263 }
2264
2265 /*
2266  * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
2267  * to the value high for the pageset p.
2268  */
2269
2270 static void setup_pagelist_highmark(struct per_cpu_pageset *p,
2271                                 unsigned long high)
2272 {
2273         struct per_cpu_pages *pcp;
2274
2275         pcp = &p->pcp[0]; /* hot list */
2276         pcp->high = high;
2277         pcp->batch = max(1UL, high/4);
2278         if ((high/4) > (PAGE_SHIFT * 8))
2279                 pcp->batch = PAGE_SHIFT * 8;
2280 }
2281
2282
2283 #ifdef CONFIG_NUMA
2284 /*
2285  * Boot pageset table. One per cpu which is going to be used for all
2286  * zones and all nodes. The parameters will be set in such a way
2287  * that an item put on a list will immediately be handed over to
2288  * the buddy list. This is safe since pageset manipulation is done
2289  * with interrupts disabled.
2290  *
2291  * Some NUMA counter updates may also be caught by the boot pagesets.
2292  *
2293  * The boot_pagesets must be kept even after bootup is complete for
2294  * unused processors and/or zones. They do play a role for bootstrapping
2295  * hotplugged processors.
2296  *
2297  * zoneinfo_show() and maybe other functions do
2298  * not check if the processor is online before following the pageset pointer.
2299  * Other parts of the kernel may not check if the zone is available.
2300  */
2301 static struct per_cpu_pageset boot_pageset[NR_CPUS];
2302
2303 /*
2304  * Dynamically allocate memory for the
2305  * per cpu pageset array in struct zone.
2306  */
2307 static int __cpuinit process_zones(int cpu)
2308 {
2309         struct zone *zone, *dzone;
2310
2311         for_each_zone(zone) {
2312
2313                 if (!populated_zone(zone))
2314                         continue;
2315
2316                 zone_pcp(zone, cpu) = kmalloc_node(sizeof(struct per_cpu_pageset),
2317                                          GFP_KERNEL, cpu_to_node(cpu));
2318                 if (!zone_pcp(zone, cpu))
2319                         goto bad;
2320
2321                 setup_pageset(zone_pcp(zone, cpu), zone_batchsize(zone));
2322
2323                 if (percpu_pagelist_fraction)
2324                         setup_pagelist_highmark(zone_pcp(zone, cpu),
2325                                 (zone->present_pages / percpu_pagelist_fraction));
2326         }
2327
2328         return 0;
2329 bad:
2330         for_each_zone(dzone) {
2331                 if (dzone == zone)
2332                         break;
2333                 kfree(zone_pcp(dzone, cpu));
2334                 zone_pcp(dzone, cpu) = NULL;
2335         }
2336         return -ENOMEM;
2337 }
2338
2339 static inline void free_zone_pagesets(int cpu)
2340 {
2341         struct zone *zone;
2342
2343         for_each_zone(zone) {
2344                 struct per_cpu_pageset *pset = zone_pcp(zone, cpu);
2345
2346                 /* Free per_cpu_pageset if it is slab allocated */
2347                 if (pset != &boot_pageset[cpu])
2348                         kfree(pset);
2349                 zone_pcp(zone, cpu) = NULL;
2350         }
2351 }
2352
2353 static int __cpuinit pageset_cpuup_callback(struct notifier_block *nfb,
2354                 unsigned long action,
2355                 void *hcpu)
2356 {
2357         int cpu = (long)hcpu;
2358         int ret = NOTIFY_OK;
2359
2360         switch (action) {
2361         case CPU_UP_PREPARE:
2362         case CPU_UP_PREPARE_FROZEN:
2363                 if (process_zones(cpu))
2364                         ret = NOTIFY_BAD;
2365                 break;
2366         case CPU_UP_CANCELED:
2367         case CPU_UP_CANCELED_FROZEN:
2368         case CPU_DEAD:
2369         case CPU_DEAD_FROZEN:
2370                 free_zone_pagesets(cpu);
2371                 break;
2372         default:
2373                 break;
2374         }
2375         return ret;
2376 }
2377
2378 static struct notifier_block __cpuinitdata pageset_notifier =
2379         { &pageset_cpuup_callback, NULL, 0 };
2380
2381 void __init setup_per_cpu_pageset(void)
2382 {
2383         int err;
2384
2385         /* Initialize per_cpu_pageset for cpu 0.
2386          * A cpuup callback will do this for every cpu
2387          * as it comes online
2388          */
2389         err = process_zones(smp_processor_id());
2390         BUG_ON(err);
2391         register_cpu_notifier(&pageset_notifier);
2392 }
2393
2394 #endif
2395
2396 static noinline __init_refok
2397 int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
2398 {
2399         int i;
2400         struct pglist_data *pgdat = zone->zone_pgdat;
2401         size_t alloc_size;
2402
2403         /*
2404          * The per-page waitqueue mechanism uses hashed waitqueues
2405          * per zone.
2406          */
2407         zone->wait_table_hash_nr_entries =
2408                  wait_table_hash_nr_entries(zone_size_pages);
2409         zone->wait_table_bits =
2410                 wait_table_bits(zone->wait_table_hash_nr_entries);
2411         alloc_size = zone->wait_table_hash_nr_entries
2412                                         * sizeof(wait_queue_head_t);
2413
2414         if (system_state == SYSTEM_BOOTING) {
2415                 zone->wait_table = (wait_queue_head_t *)
2416                         alloc_bootmem_node(pgdat, alloc_size);
2417         } else {
2418                 /*
2419                  * This case means that a zone whose size was 0 gets new memory
2420                  * via memory hot-add.
2421                  * But it may be the case that a new node was hot-added.  In
2422                  * this case vmalloc() will not be able to use this new node's
2423                  * memory - this wait_table must be initialized to use this new
2424                  * node itself as well.
2425                  * To use this new node's memory, further consideration will be
2426                  * necessary.
2427                  */
2428                 zone->wait_table = (wait_queue_head_t *)vmalloc(alloc_size);
2429         }
2430         if (!zone->wait_table)
2431                 return -ENOMEM;
2432
2433         for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
2434                 init_waitqueue_head(zone->wait_table + i);
2435
2436         return 0;
2437 }
2438
2439 static __meminit void zone_pcp_init(struct zone *zone)
2440 {
2441         int cpu;
2442         unsigned long batch = zone_batchsize(zone);
2443
2444         for (cpu = 0; cpu < NR_CPUS; cpu++) {
2445 #ifdef CONFIG_NUMA
2446                 /* Early boot. Slab allocator not functional yet */
2447                 zone_pcp(zone, cpu) = &boot_pageset[cpu];
2448                 setup_pageset(&boot_pageset[cpu],0);
2449 #else
2450                 setup_pageset(zone_pcp(zone,cpu), batch);
2451 #endif
2452         }
2453         if (zone->present_pages)
2454                 printk(KERN_DEBUG "  %s zone: %lu pages, LIFO batch:%lu\n",
2455                         zone->name, zone->present_pages, batch);
2456 }
2457
2458 __meminit int init_currently_empty_zone(struct zone *zone,
2459                                         unsigned long zone_start_pfn,
2460                                         unsigned long size,
2461                                         enum memmap_context context)
2462 {
2463         struct pglist_data *pgdat = zone->zone_pgdat;
2464         int ret;
2465         ret = zone_wait_table_init(zone, size);
2466         if (ret)
2467                 return ret;
2468         pgdat->nr_zones = zone_idx(zone) + 1;
2469
2470         zone->zone_start_pfn = zone_start_pfn;
2471
2472         memmap_init(size, pgdat->node_id, zone_idx(zone), zone_start_pfn);
2473
2474         zone_init_free_lists(pgdat, zone, zone->spanned_pages);
2475
2476         return 0;
2477 }
2478
2479 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
2480 /*
2481  * Basic iterator support. Return the first range of PFNs for a node
2482  * Note: nid == MAX_NUMNODES returns first region regardless of node
2483  */
2484 static int __meminit first_active_region_index_in_nid(int nid)
2485 {
2486         int i;
2487
2488         for (i = 0; i < nr_nodemap_entries; i++)
2489                 if (nid == MAX_NUMNODES || early_node_map[i].nid == nid)
2490                         return i;
2491
2492         return -1;
2493 }
2494
2495 /*
2496  * Basic iterator support. Return the next active range of PFNs for a node
2497  * Note: nid == MAX_NUMNODES returns next region regardles of node
2498  */
2499 static int __meminit next_active_region_index_in_nid(int index, int nid)
2500 {
2501         for (index = index + 1; index < nr_nodemap_entries; index++)
2502                 if (nid == MAX_NUMNODES || early_node_map[index].nid == nid)
2503                         return index;
2504
2505         return -1;
2506 }
2507
2508 #ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
2509 /*
2510  * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
2511  * Architectures may implement their own version but if add_active_range()
2512  * was used and there are no special requirements, this is a convenient
2513  * alternative
2514  */
2515 int __meminit early_pfn_to_nid(unsigned long pfn)
2516 {
2517         int i;
2518
2519         for (i = 0; i < nr_nodemap_entries; i++) {
2520                 unsigned long start_pfn = early_node_map[i].start_pfn;
2521                 unsigned long end_pfn = early_node_map[i].end_pfn;
2522
2523                 if (start_pfn <= pfn && pfn < end_pfn)
2524                         return early_node_map[i].nid;
2525         }
2526
2527         return 0;
2528 }
2529 #endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
2530
2531 /* Basic iterator support to walk early_node_map[] */
2532 #define for_each_active_range_index_in_nid(i, nid) \
2533         for (i = first_active_region_index_in_nid(nid); i != -1; \
2534                                 i = next_active_region_index_in_nid(i, nid))
2535
2536 /**
2537  * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
2538  * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
2539  * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
2540  *
2541  * If an architecture guarantees that all ranges registered with
2542  * add_active_ranges() contain no holes and may be freed, this
2543  * this function may be used instead of calling free_bootmem() manually.
2544  */
2545 void __init free_bootmem_with_active_regions(int nid,
2546                                                 unsigned long max_low_pfn)
2547 {
2548         int i;
2549
2550         for_each_active_range_index_in_nid(i, nid) {
2551                 unsigned long size_pages = 0;
2552                 unsigned long end_pfn = early_node_map[i].end_pfn;
2553
2554                 if (early_node_map[i].start_pfn >= max_low_pfn)
2555                         continue;
2556
2557                 if (end_pfn > max_low_pfn)
2558                         end_pfn = max_low_pfn;
2559
2560                 size_pages = end_pfn - early_node_map[i].start_pfn;
2561                 free_bootmem_node(NODE_DATA(early_node_map[i].nid),
2562                                 PFN_PHYS(early_node_map[i].start_pfn),
2563                                 size_pages << PAGE_SHIFT);
2564         }
2565 }
2566
2567 /**
2568  * sparse_memory_present_with_active_regions - Call memory_present for each active range
2569  * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
2570  *
2571  * If an architecture guarantees that all ranges registered with
2572  * add_active_ranges() contain no holes and may be freed, this
2573  * function may be used instead of calling memory_present() manually.
2574  */
2575 void __init sparse_memory_present_with_active_regions(int nid)
2576 {
2577         int i;
2578
2579         for_each_active_range_index_in_nid(i, nid)
2580                 memory_present(early_node_map[i].nid,
2581                                 early_node_map[i].start_pfn,
2582                                 early_node_map[i].end_pfn);
2583 }
2584
2585 /**
2586  * push_node_boundaries - Push node boundaries to at least the requested boundary
2587  * @nid: The nid of the node to push the boundary for
2588  * @start_pfn: The start pfn of the node
2589  * @end_pfn: The end pfn of the node
2590  *
2591  * In reserve-based hot-add, mem_map is allocated that is unused until hotadd
2592  * time. Specifically, on x86_64, SRAT will report ranges that can potentially
2593  * be hotplugged even though no physical memory exists. This function allows
2594  * an arch to push out the node boundaries so mem_map is allocated that can
2595  * be used later.
2596  */
2597 #ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
2598 void __init push_node_boundaries(unsigned int nid,
2599                 unsigned long start_pfn, unsigned long end_pfn)
2600 {
2601         printk(KERN_DEBUG "Entering push_node_boundaries(%u, %lu, %lu)\n",
2602                         nid, start_pfn, end_pfn);
2603
2604         /* Initialise the boundary for this node if necessary */
2605         if (node_boundary_end_pfn[nid] == 0)
2606                 node_boundary_start_pfn[nid] = -1UL;
2607
2608         /* Update the boundaries */
2609         if (node_boundary_start_pfn[nid] > start_pfn)
2610                 node_boundary_start_pfn[nid] = start_pfn;
2611         if (node_boundary_end_pfn[nid] < end_pfn)
2612                 node_boundary_end_pfn[nid] = end_pfn;
2613 }
2614
2615 /* If necessary, push the node boundary out for reserve hotadd */
2616 static void __meminit account_node_boundary(unsigned int nid,
2617                 unsigned long *start_pfn, unsigned long *end_pfn)
2618 {
2619         printk(KERN_DEBUG "Entering account_node_boundary(%u, %lu, %lu)\n",
2620                         nid, *start_pfn, *end_pfn);
2621
2622         /* Return if boundary information has not been provided */
2623         if (node_boundary_end_pfn[nid] == 0)
2624                 return;
2625
2626         /* Check the boundaries and update if necessary */
2627         if (node_boundary_start_pfn[nid] < *start_pfn)
2628                 *start_pfn = node_boundary_start_pfn[nid];
2629         if (node_boundary_end_pfn[nid] > *end_pfn)
2630                 *end_pfn = node_boundary_end_pfn[nid];
2631 }
2632 #else
2633 void __init push_node_boundaries(unsigned int nid,
2634                 unsigned long start_pfn, unsigned long end_pfn) {}
2635
2636 static void __meminit account_node_boundary(unsigned int nid,
2637                 unsigned long *start_pfn, unsigned long *end_pfn) {}
2638 #endif
2639
2640
2641 /**
2642  * get_pfn_range_for_nid - Return the start and end page frames for a node
2643  * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
2644  * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
2645  * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
2646  *
2647  * It returns the start and end page frame of a node based on information
2648  * provided by an arch calling add_active_range(). If called for a node
2649  * with no available memory, a warning is printed and the start and end
2650  * PFNs will be 0.
2651  */
2652 void __meminit get_pfn_range_for_nid(unsigned int nid,
2653                         unsigned long *start_pfn, unsigned long *end_pfn)
2654 {
2655         int i;
2656         *start_pfn = -1UL;
2657         *end_pfn = 0;
2658
2659         for_each_active_range_index_in_nid(i, nid) {
2660                 *start_pfn = min(*start_pfn, early_node_map[i].start_pfn);
2661                 *end_pfn = max(*end_pfn, early_node_map[i].end_pfn);
2662         }
2663
2664         if (*start_pfn == -1UL) {
2665                 printk(KERN_WARNING "Node %u active with no memory\n", nid);
2666                 *start_pfn = 0;
2667         }
2668
2669         /* Push the node boundaries out if requested */
2670         account_node_boundary(nid, start_pfn, end_pfn);
2671 }
2672
2673 /*
2674  * This finds a zone that can be used for ZONE_MOVABLE pages. The
2675  * assumption is made that zones within a node are ordered in monotonic
2676  * increasing memory addresses so that the "highest" populated zone is used
2677  */
2678 void __init find_usable_zone_for_movable(void)
2679 {
2680         int zone_index;
2681         for (zone_index = MAX_NR_ZONES - 1; zone_index >= 0; zone_index--) {
2682                 if (zone_index == ZONE_MOVABLE)
2683                         continue;
2684
2685                 if (arch_zone_highest_possible_pfn[zone_index] >
2686                                 arch_zone_lowest_possible_pfn[zone_index])
2687                         break;
2688         }
2689
2690         VM_BUG_ON(zone_index == -1);
2691         movable_zone = zone_index;
2692 }
2693
2694 /*
2695  * The zone ranges provided by the architecture do not include ZONE_MOVABLE
2696  * because it is sized independant of architecture. Unlike the other zones,
2697  * the starting point for ZONE_MOVABLE is not fixed. It may be different
2698  * in each node depending on the size of each node and how evenly kernelcore
2699  * is distributed. This helper function adjusts the zone ranges
2700  * provided by the architecture for a given node by using the end of the
2701  * highest usable zone for ZONE_MOVABLE. This preserves the assumption that
2702  * zones within a node are in order of monotonic increases memory addresses
2703  */
2704 void __meminit adjust_zone_range_for_zone_movable(int nid,
2705                                         unsigned long zone_type,
2706                                         unsigned long node_start_pfn,
2707                                         unsigned long node_end_pfn,
2708                                         unsigned long *zone_start_pfn,
2709                                         unsigned long *zone_end_pfn)
2710 {
2711         /* Only adjust if ZONE_MOVABLE is on this node */
2712         if (zone_movable_pfn[nid]) {
2713                 /* Size ZONE_MOVABLE */
2714                 if (zone_type == ZONE_MOVABLE) {
2715                         *zone_start_pfn = zone_movable_pfn[nid];
2716                         *zone_end_pfn = min(node_end_pfn,
2717                                 arch_zone_highest_possible_pfn[movable_zone]);
2718
2719                 /* Adjust for ZONE_MOVABLE starting within this range */
2720                 } else if (*zone_start_pfn < zone_movable_pfn[nid] &&
2721                                 *zone_end_pfn > zone_movable_pfn[nid]) {
2722                         *zone_end_pfn = zone_movable_pfn[nid];
2723
2724                 /* Check if this whole range is within ZONE_MOVABLE */
2725                 } else if (*zone_start_pfn >= zone_movable_pfn[nid])
2726                         *zone_start_pfn = *zone_end_pfn;
2727         }
2728 }
2729
2730 /*
2731  * Return the number of pages a zone spans in a node, including holes
2732  * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
2733  */
2734 static unsigned long __meminit zone_spanned_pages_in_node(int nid,
2735                                         unsigned long zone_type,
2736                                         unsigned long *ignored)
2737 {
2738         unsigned long node_start_pfn, node_end_pfn;
2739         unsigned long zone_start_pfn, zone_end_pfn;
2740
2741         /* Get the start and end of the node and zone */
2742         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
2743         zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
2744         zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
2745         adjust_zone_range_for_zone_movable(nid, zone_type,
2746                                 node_start_pfn, node_end_pfn,
2747                                 &zone_start_pfn, &zone_end_pfn);
2748
2749         /* Check that this node has pages within the zone's required range */
2750         if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
2751                 return 0;
2752
2753         /* Move the zone boundaries inside the node if necessary */
2754         zone_end_pfn = min(zone_end_pfn, node_end_pfn);
2755         zone_start_pfn = max(zone_start_pfn, node_start_pfn);
2756
2757         /* Return the spanned pages */
2758         return zone_end_pfn - zone_start_pfn;
2759 }
2760
2761 /*
2762  * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
2763  * then all holes in the requested range will be accounted for.
2764  */
2765 unsigned long __meminit __absent_pages_in_range(int nid,
2766                                 unsigned long range_start_pfn,
2767                                 unsigned long range_end_pfn)
2768 {
2769         int i = 0;
2770         unsigned long prev_end_pfn = 0, hole_pages = 0;
2771         unsigned long start_pfn;
2772
2773         /* Find the end_pfn of the first active range of pfns in the node */
2774         i = first_active_region_index_in_nid(nid);
2775         if (i == -1)
2776                 return 0;
2777
2778         /* Account for ranges before physical memory on this node */
2779         if (early_node_map[i].start_pfn > range_start_pfn)
2780                 hole_pages = early_node_map[i].start_pfn - range_start_pfn;
2781
2782         prev_end_pfn = early_node_map[i].start_pfn;
2783
2784         /* Find all holes for the zone within the node */
2785         for (; i != -1; i = next_active_region_index_in_nid(i, nid)) {
2786
2787                 /* No need to continue if prev_end_pfn is outside the zone */
2788                 if (prev_end_pfn >= range_end_pfn)
2789                         break;
2790
2791                 /* Make sure the end of the zone is not within the hole */
2792                 start_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
2793                 prev_end_pfn = max(prev_end_pfn, range_start_pfn);
2794
2795                 /* Update the hole size cound and move on */
2796                 if (start_pfn > range_start_pfn) {
2797                         BUG_ON(prev_end_pfn > start_pfn);
2798                         hole_pages += start_pfn - prev_end_pfn;
2799                 }
2800                 prev_end_pfn = early_node_map[i].end_pfn;
2801         }
2802
2803         /* Account for ranges past physical memory on this node */
2804         if (range_end_pfn > prev_end_pfn)
2805                 hole_pages += range_end_pfn -
2806                                 max(range_start_pfn, prev_end_pfn);
2807
2808         return hole_pages;
2809 }
2810
2811 /**
2812  * absent_pages_in_range - Return number of page frames in holes within a range
2813  * @start_pfn: The start PFN to start searching for holes
2814  * @end_pfn: The end PFN to stop searching for holes
2815  *
2816  * It returns the number of pages frames in memory holes within a range.
2817  */
2818 unsigned long __init absent_pages_in_range(unsigned long start_pfn,
2819                                                         unsigned long end_pfn)
2820 {
2821         return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
2822 }
2823
2824 /* Return the number of page frames in holes in a zone on a node */
2825 static unsigned long __meminit zone_absent_pages_in_node(int nid,
2826                                         unsigned long zone_type,
2827                                         unsigned long *ignored)
2828 {
2829         unsigned long node_start_pfn, node_end_pfn;
2830         unsigned long zone_start_pfn, zone_end_pfn;
2831
2832         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
2833         zone_start_pfn = max(arch_zone_lowest_possible_pfn[zone_type],
2834                                                         node_start_pfn);
2835         zone_end_pfn = min(arch_zone_highest_possible_pfn[zone_type],
2836                                                         node_end_pfn);
2837
2838         adjust_zone_range_for_zone_movable(nid, zone_type,
2839                         node_start_pfn, node_end_pfn,
2840                         &zone_start_pfn, &zone_end_pfn);
2841         return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
2842 }
2843
2844 #else
2845 static inline unsigned long __meminit zone_spanned_pages_in_node(int nid,
2846                                         unsigned long zone_type,
2847                                         unsigned long *zones_size)
2848 {
2849         return zones_size[zone_type];
2850 }
2851
2852 static inline unsigned long __meminit zone_absent_pages_in_node(int nid,
2853                                                 unsigned long zone_type,
2854                                                 unsigned long *zholes_size)
2855 {
2856         if (!zholes_size)
2857                 return 0;
2858
2859         return zholes_size[zone_type];
2860 }
2861
2862 #endif
2863
2864 static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,
2865                 unsigned long *zones_size, unsigned long *zholes_size)
2866 {
2867         unsigned long realtotalpages, totalpages = 0;
2868         enum zone_type i;
2869
2870         for (i = 0; i < MAX_NR_ZONES; i++)
2871                 totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
2872                                                                 zones_size);
2873         pgdat->node_spanned_pages = totalpages;
2874
2875         realtotalpages = totalpages;
2876         for (i = 0; i < MAX_NR_ZONES; i++)
2877                 realtotalpages -=
2878                         zone_absent_pages_in_node(pgdat->node_id, i,
2879                                                                 zholes_size);
2880         pgdat->node_present_pages = realtotalpages;
2881         printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
2882                                                         realtotalpages);
2883 }
2884
2885 /*
2886  * Set up the zone data structures:
2887  *   - mark all pages reserved
2888  *   - mark all memory queues empty
2889  *   - clear the memory bitmaps
2890  */
2891 static void __meminit free_area_init_core(struct pglist_data *pgdat,
2892                 unsigned long *zones_size, unsigned long *zholes_size)
2893 {
2894         enum zone_type j;
2895         int nid = pgdat->node_id;
2896         unsigned long zone_start_pfn = pgdat->node_start_pfn;
2897         int ret;
2898
2899         pgdat_resize_init(pgdat);
2900         pgdat->nr_zones = 0;
2901         init_waitqueue_head(&pgdat->kswapd_wait);
2902         pgdat->kswapd_max_order = 0;
2903         
2904         for (j = 0; j < MAX_NR_ZONES; j++) {
2905                 struct zone *zone = pgdat->node_zones + j;
2906                 unsigned long size, realsize, memmap_pages;
2907
2908                 size = zone_spanned_pages_in_node(nid, j, zones_size);
2909                 realsize = size - zone_absent_pages_in_node(nid, j,
2910                                                                 zholes_size);
2911
2912                 /*
2913                  * Adjust realsize so that it accounts for how much memory
2914                  * is used by this zone for memmap. This affects the watermark
2915                  * and per-cpu initialisations
2916                  */
2917                 memmap_pages = (size * sizeof(struct page)) >> PAGE_SHIFT;
2918                 if (realsize >= memmap_pages) {
2919                         realsize -= memmap_pages;
2920                         printk(KERN_DEBUG
2921                                 "  %s zone: %lu pages used for memmap\n",
2922                                 zone_names[j], memmap_pages);
2923                 } else
2924                         printk(KERN_WARNING
2925                                 "  %s zone: %lu pages exceeds realsize %lu\n",
2926                                 zone_names[j], memmap_pages, realsize);
2927
2928                 /* Account for reserved pages */
2929                 if (j == 0 && realsize > dma_reserve) {
2930                         realsize -= dma_reserve;
2931                         printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",
2932                                         zone_names[0], dma_reserve);
2933                 }
2934
2935                 if (!is_highmem_idx(j))
2936                         nr_kernel_pages += realsize;
2937                 nr_all_pages += realsize;
2938
2939                 zone->spanned_pages = size;
2940                 zone->present_pages = realsize;
2941 #ifdef CONFIG_NUMA
2942                 zone->node = nid;
2943                 zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
2944                                                 / 100;
2945                 zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
2946 #endif
2947                 zone->name = zone_names[j];
2948                 spin_lock_init(&zone->lock);
2949                 spin_lock_init(&zone->lru_lock);
2950                 zone_seqlock_init(zone);
2951                 zone->zone_pgdat = pgdat;
2952
2953                 zone->prev_priority = DEF_PRIORITY;
2954
2955                 zone_pcp_init(zone);
2956                 INIT_LIST_HEAD(&zone->active_list);
2957                 INIT_LIST_HEAD(&zone->inactive_list);
2958                 zone->nr_scan_active = 0;
2959                 zone->nr_scan_inactive = 0;
2960                 zap_zone_vm_stats(zone);
2961                 atomic_set(&zone->reclaim_in_progress, 0);
2962                 if (!size)
2963                         continue;
2964
2965                 ret = init_currently_empty_zone(zone, zone_start_pfn,
2966                                                 size, MEMMAP_EARLY);
2967                 BUG_ON(ret);
2968                 zone_start_pfn += size;
2969         }
2970 }
2971
2972 static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)
2973 {
2974         /* Skip empty nodes */
2975         if (!pgdat->node_spanned_pages)
2976                 return;
2977
2978 #ifdef CONFIG_FLAT_NODE_MEM_MAP
2979         /* ia64 gets its own node_mem_map, before this, without bootmem */
2980         if (!pgdat->node_mem_map) {
2981                 unsigned long size, start, end;
2982                 struct page *map;
2983
2984                 /*
2985                  * The zone's endpoints aren't required to be MAX_ORDER
2986                  * aligned but the node_mem_map endpoints must be in order
2987                  * for the buddy allocator to function correctly.
2988                  */
2989                 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
2990                 end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
2991                 end = ALIGN(end, MAX_ORDER_NR_PAGES);
2992                 size =  (end - start) * sizeof(struct page);
2993                 map = alloc_remap(pgdat->node_id, size);
2994                 if (!map)
2995                         map = alloc_bootmem_node(pgdat, size);
2996                 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
2997         }
2998 #ifndef CONFIG_NEED_MULTIPLE_NODES
2999         /*
3000          * With no DISCONTIG, the global mem_map is just set as node 0's
3001          */
3002         if (pgdat == NODE_DATA(0)) {
3003                 mem_map = NODE_DATA(0)->node_mem_map;
3004 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
3005                 if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
3006                         mem_map -= pgdat->node_start_pfn;
3007 #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
3008         }
3009 #endif
3010 #endif /* CONFIG_FLAT_NODE_MEM_MAP */
3011 }
3012
3013 void __meminit free_area_init_node(int nid, struct pglist_data *pgdat,
3014                 unsigned long *zones_size, unsigned long node_start_pfn,
3015                 unsigned long *zholes_size)
3016 {
3017         pgdat->node_id = nid;
3018         pgdat->node_start_pfn = node_start_pfn;
3019         calculate_node_totalpages(pgdat, zones_size, zholes_size);
3020
3021         alloc_node_mem_map(pgdat);
3022
3023         free_area_init_core(pgdat, zones_size, zholes_size);
3024 }
3025
3026 #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
3027
3028 #if MAX_NUMNODES > 1
3029 /*
3030  * Figure out the number of possible node ids.
3031  */
3032 static void __init setup_nr_node_ids(void)
3033 {
3034         unsigned int node;
3035         unsigned int highest = 0;
3036
3037         for_each_node_mask(node, node_possible_map)
3038                 highest = node;
3039         nr_node_ids = highest + 1;
3040 }
3041 #else
3042 static inline void setup_nr_node_ids(void)
3043 {
3044 }
3045 #endif
3046
3047 /**
3048  * add_active_range - Register a range of PFNs backed by physical memory
3049  * @nid: The node ID the range resides on
3050  * @start_pfn: The start PFN of the available physical memory
3051  * @end_pfn: The end PFN of the available physical memory
3052  *
3053  * These ranges are stored in an early_node_map[] and later used by
3054  * free_area_init_nodes() to calculate zone sizes and holes. If the
3055  * range spans a memory hole, it is up to the architecture to ensure
3056  * the memory is not freed by the bootmem allocator. If possible
3057  * the range being registered will be merged with existing ranges.
3058  */
3059 void __init add_active_range(unsigned int nid, unsigned long start_pfn,
3060                                                 unsigned long end_pfn)
3061 {
3062         int i;
3063
3064         printk(KERN_DEBUG "Entering add_active_range(%d, %lu, %lu) "
3065                           "%d entries of %d used\n",
3066                           nid, start_pfn, end_pfn,
3067                           nr_nodemap_entries, MAX_ACTIVE_REGIONS);
3068
3069         /* Merge with existing active regions if possible */
3070         for (i = 0; i < nr_nodemap_entries; i++) {
3071                 if (early_node_map[i].nid != nid)
3072                         continue;
3073
3074                 /* Skip if an existing region covers this new one */
3075                 if (start_pfn >= early_node_map[i].start_pfn &&
3076                                 end_pfn <= early_node_map[i].end_pfn)
3077                         return;
3078
3079                 /* Merge forward if suitable */
3080                 if (start_pfn <= early_node_map[i].end_pfn &&
3081                                 end_pfn > early_node_map[i].end_pfn) {
3082                         early_node_map[i].end_pfn = end_pfn;
3083                         return;
3084                 }
3085
3086                 /* Merge backward if suitable */
3087                 if (start_pfn < early_node_map[i].end_pfn &&
3088                                 end_pfn >= early_node_map[i].start_pfn) {
3089                         early_node_map[i].start_pfn = start_pfn;
3090                         return;
3091                 }
3092         }
3093
3094         /* Check that early_node_map is large enough */
3095         if (i >= MAX_ACTIVE_REGIONS) {
3096                 printk(KERN_CRIT "More than %d memory regions, truncating\n",
3097                                                         MAX_ACTIVE_REGIONS);
3098                 return;
3099         }
3100
3101         early_node_map[i].nid = nid;
3102         early_node_map[i].start_pfn = start_pfn;
3103         early_node_map[i].end_pfn = end_pfn;
3104         nr_nodemap_entries = i + 1;
3105 }
3106
3107 /**
3108  * shrink_active_range - Shrink an existing registered range of PFNs
3109  * @nid: The node id the range is on that should be shrunk
3110  * @old_end_pfn: The old end PFN of the range
3111  * @new_end_pfn: The new PFN of the range
3112  *
3113  * i386 with NUMA use alloc_remap() to store a node_mem_map on a local node.
3114  * The map is kept at the end physical page range that has already been
3115  * registered with add_active_range(). This function allows an arch to shrink
3116  * an existing registered range.
3117  */
3118 void __init shrink_active_range(unsigned int nid, unsigned long old_end_pfn,
3119                                                 unsigned long new_end_pfn)
3120 {
3121         int i;
3122
3123         /* Find the old active region end and shrink */
3124         for_each_active_range_index_in_nid(i, nid)
3125                 if (early_node_map[i].end_pfn == old_end_pfn) {
3126                         early_node_map[i].end_pfn = new_end_pfn;
3127                         break;
3128                 }
3129 }
3130
3131 /**
3132  * remove_all_active_ranges - Remove all currently registered regions
3133  *
3134  * During discovery, it may be found that a table like SRAT is invalid
3135  * and an alternative discovery method must be used. This function removes
3136  * all currently registered regions.
3137  */
3138 void __init remove_all_active_ranges(void)
3139 {
3140         memset(early_node_map, 0, sizeof(early_node_map));
3141         nr_nodemap_entries = 0;
3142 #ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
3143         memset(node_boundary_start_pfn, 0, sizeof(node_boundary_start_pfn));
3144         memset(node_boundary_end_pfn, 0, sizeof(node_boundary_end_pfn));
3145 #endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
3146 }
3147
3148 /* Compare two active node_active_regions */
3149 static int __init cmp_node_active_region(const void *a, const void *b)
3150 {
3151         struct node_active_region *arange = (struct node_active_region *)a;
3152         struct node_active_region *brange = (struct node_active_region *)b;
3153
3154         /* Done this way to avoid overflows */
3155         if (arange->start_pfn > brange->start_pfn)
3156                 return 1;
3157         if (arange->start_pfn < brange->start_pfn)
3158                 return -1;
3159
3160         return 0;
3161 }
3162
3163 /* sort the node_map by start_pfn */
3164 static void __init sort_node_map(void)
3165 {
3166         sort(early_node_map, (size_t)nr_nodemap_entries,
3167                         sizeof(struct node_active_region),
3168                         cmp_node_active_region, NULL);
3169 }
3170
3171 /* Find the lowest pfn for a node */
3172 unsigned long __init find_min_pfn_for_node(unsigned long nid)
3173 {
3174         int i;
3175         unsigned long min_pfn = ULONG_MAX;
3176
3177         /* Assuming a sorted map, the first range found has the starting pfn */
3178         for_each_active_range_index_in_nid(i, nid)
3179                 min_pfn = min(min_pfn, early_node_map[i].start_pfn);
3180
3181         if (min_pfn == ULONG_MAX) {
3182                 printk(KERN_WARNING
3183                         "Could not find start_pfn for node %lu\n", nid);
3184                 return 0;
3185         }
3186
3187         return min_pfn;
3188 }
3189
3190 /**
3191  * find_min_pfn_with_active_regions - Find the minimum PFN registered
3192  *
3193  * It returns the minimum PFN based on information provided via
3194  * add_active_range().
3195  */
3196 unsigned long __init find_min_pfn_with_active_regions(void)
3197 {
3198         return find_min_pfn_for_node(MAX_NUMNODES);
3199 }
3200
3201 /**
3202  * find_max_pfn_with_active_regions - Find the maximum PFN registered
3203  *
3204  * It returns the maximum PFN based on information provided via
3205  * add_active_range().
3206  */
3207 unsigned long __init find_max_pfn_with_active_regions(void)
3208 {
3209         int i;
3210         unsigned long max_pfn = 0;
3211
3212         for (i = 0; i < nr_nodemap_entries; i++)
3213                 max_pfn = max(max_pfn, early_node_map[i].end_pfn);
3214
3215         return max_pfn;
3216 }
3217
3218 unsigned long __init early_calculate_totalpages(void)
3219 {
3220         int i;
3221         unsigned long totalpages = 0;
3222
3223         for (i = 0; i < nr_nodemap_entries; i++)
3224                 totalpages += early_node_map[i].end_pfn -
3225                                                 early_node_map[i].start_pfn;
3226
3227         return totalpages;
3228 }
3229
3230 /*
3231  * Find the PFN the Movable zone begins in each node. Kernel memory
3232  * is spread evenly between nodes as long as the nodes have enough
3233  * memory. When they don't, some nodes will have more kernelcore than
3234  * others
3235  */
3236 void __init find_zone_movable_pfns_for_nodes(unsigned long *movable_pfn)
3237 {
3238         int i, nid;
3239         unsigned long usable_startpfn;
3240         unsigned long kernelcore_node, kernelcore_remaining;
3241         int usable_nodes = num_online_nodes();
3242
3243         /*
3244          * If movablecore was specified, calculate what size of
3245          * kernelcore that corresponds so that memory usable for
3246          * any allocation type is evenly spread. If both kernelcore
3247          * and movablecore are specified, then the value of kernelcore
3248          * will be used for required_kernelcore if it's greater than
3249          * what movablecore would have allowed.
3250          */
3251         if (required_movablecore) {
3252                 unsigned long totalpages = early_calculate_totalpages();
3253                 unsigned long corepages;
3254
3255                 /*
3256                  * Round-up so that ZONE_MOVABLE is at least as large as what
3257                  * was requested by the user
3258                  */
3259                 required_movablecore =
3260                         roundup(required_movablecore, MAX_ORDER_NR_PAGES);
3261                 corepages = totalpages - required_movablecore;
3262
3263                 required_kernelcore = max(required_kernelcore, corepages);
3264         }
3265
3266         /* If kernelcore was not specified, there is no ZONE_MOVABLE */
3267         if (!required_kernelcore)
3268                 return;
3269
3270         /* usable_startpfn is the lowest possible pfn ZONE_MOVABLE can be at */
3271         find_usable_zone_for_movable();
3272         usable_startpfn = arch_zone_lowest_possible_pfn[movable_zone];
3273
3274 restart:
3275         /* Spread kernelcore memory as evenly as possible throughout nodes */
3276         kernelcore_node = required_kernelcore / usable_nodes;
3277         for_each_online_node(nid) {
3278                 /*
3279                  * Recalculate kernelcore_node if the division per node
3280                  * now exceeds what is necessary to satisfy the requested
3281                  * amount of memory for the kernel
3282                  */
3283                 if (required_kernelcore < kernelcore_node)
3284                         kernelcore_node = required_kernelcore / usable_nodes;
3285
3286                 /*
3287                  * As the map is walked, we track how much memory is usable
3288                  * by the kernel using kernelcore_remaining. When it is
3289                  * 0, the rest of the node is usable by ZONE_MOVABLE
3290                  */
3291                 kernelcore_remaining = kernelcore_node;
3292
3293                 /* Go through each range of PFNs within this node */
3294                 for_each_active_range_index_in_nid(i, nid) {
3295                         unsigned long start_pfn, end_pfn;
3296                         unsigned long size_pages;
3297
3298                         start_pfn = max(early_node_map[i].start_pfn,
3299                                                 zone_movable_pfn[nid]);
3300                         end_pfn = early_node_map[i].end_pfn;
3301                         if (start_pfn >= end_pfn)
3302                                 continue;
3303
3304                         /* Account for what is only usable for kernelcore */
3305                         if (start_pfn < usable_startpfn) {
3306                                 unsigned long kernel_pages;
3307                                 kernel_pages = min(end_pfn, usable_startpfn)
3308                                                                 - start_pfn;
3309
3310                                 kernelcore_remaining -= min(kernel_pages,
3311                                                         kernelcore_remaining);
3312                                 required_kernelcore -= min(kernel_pages,
3313                                                         required_kernelcore);
3314
3315                                 /* Continue if range is now fully accounted */
3316                                 if (end_pfn <= usable_startpfn) {
3317
3318                                         /*
3319                                          * Push zone_movable_pfn to the end so
3320                                          * that if we have to rebalance
3321                                          * kernelcore across nodes, we will
3322                                          * not double account here
3323                                          */
3324                                         zone_movable_pfn[nid] = end_pfn;
3325                                         continue;
3326                                 }
3327                                 start_pfn = usable_startpfn;
3328                         }
3329
3330                         /*
3331                          * The usable PFN range for ZONE_MOVABLE is from
3332                          * start_pfn->end_pfn. Calculate size_pages as the
3333                          * number of pages used as kernelcore
3334                          */
3335                         size_pages = end_pfn - start_pfn;
3336                         if (size_pages > kernelcore_remaining)
3337                                 size_pages = kernelcore_remaining;
3338                         zone_movable_pfn[nid] = start_pfn + size_pages;
3339
3340                         /*
3341                          * Some kernelcore has been met, update counts and
3342                          * break if the kernelcore for this node has been
3343                          * satisified
3344                          */
3345                         required_kernelcore -= min(required_kernelcore,
3346                                                                 size_pages);
3347                         kernelcore_remaining -= size_pages;
3348                         if (!kernelcore_remaining)
3349                                 break;
3350                 }
3351         }
3352
3353         /*
3354          * If there is still required_kernelcore, we do another pass with one
3355          * less node in the count. This will push zone_movable_pfn[nid] further
3356          * along on the nodes that still have memory until kernelcore is
3357          * satisified
3358          */
3359         usable_nodes--;
3360         if (usable_nodes && required_kernelcore > usable_nodes)
3361                 goto restart;
3362
3363         /* Align start of ZONE_MOVABLE on all nids to MAX_ORDER_NR_PAGES */
3364         for (nid = 0; nid < MAX_NUMNODES; nid++)
3365                 zone_movable_pfn[nid] =
3366                         roundup(zone_movable_pfn[nid], MAX_ORDER_NR_PAGES);
3367 }
3368
3369 /**
3370  * free_area_init_nodes - Initialise all pg_data_t and zone data
3371  * @max_zone_pfn: an array of max PFNs for each zone
3372  *
3373  * This will call free_area_init_node() for each active node in the system.
3374  * Using the page ranges provided by add_active_range(), the size of each
3375  * zone in each node and their holes is calculated. If the maximum PFN
3376  * between two adjacent zones match, it is assumed that the zone is empty.
3377  * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
3378  * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
3379  * starts where the previous one ended. For example, ZONE_DMA32 starts
3380  * at arch_max_dma_pfn.
3381  */
3382 void __init free_area_init_nodes(unsigned long *max_zone_pfn)
3383 {
3384         unsigned long nid;
3385         enum zone_type i;
3386
3387         /* Sort early_node_map as initialisation assumes it is sorted */
3388         sort_node_map();
3389
3390         /* Record where the zone boundaries are */
3391         memset(arch_zone_lowest_possible_pfn, 0,
3392                                 sizeof(arch_zone_lowest_possible_pfn));
3393         memset(arch_zone_highest_possible_pfn, 0,
3394                                 sizeof(arch_zone_highest_possible_pfn));
3395         arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
3396         arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
3397         for (i = 1; i < MAX_NR_ZONES; i++) {
3398                 if (i == ZONE_MOVABLE)
3399                         continue;
3400                 arch_zone_lowest_possible_pfn[i] =
3401                         arch_zone_highest_possible_pfn[i-1];
3402                 arch_zone_highest_possible_pfn[i] =
3403                         max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
3404         }
3405         arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
3406         arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;
3407
3408         /* Find the PFNs that ZONE_MOVABLE begins at in each node */
3409         memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
3410         find_zone_movable_pfns_for_nodes(zone_movable_pfn);
3411
3412         /* Print out the zone ranges */
3413         printk("Zone PFN ranges:\n");
3414         for (i = 0; i < MAX_NR_ZONES; i++) {
3415                 if (i == ZONE_MOVABLE)
3416                         continue;
3417                 printk("  %-8s %8lu -> %8lu\n",
3418                                 zone_names[i],
3419                                 arch_zone_lowest_possible_pfn[i],
3420                                 arch_zone_highest_possible_pfn[i]);
3421         }
3422
3423         /* Print out the PFNs ZONE_MOVABLE begins at in each node */
3424         printk("Movable zone start PFN for each node\n");
3425         for (i = 0; i < MAX_NUMNODES; i++) {
3426                 if (zone_movable_pfn[i])
3427                         printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);
3428         }
3429
3430         /* Print out the early_node_map[] */
3431         printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
3432         for (i = 0; i < nr_nodemap_entries; i++)
3433                 printk("  %3d: %8lu -> %8lu\n", early_node_map[i].nid,
3434                                                 early_node_map[i].start_pfn,
3435                                                 early_node_map[i].end_pfn);
3436
3437         /* Initialise every node */
3438         setup_nr_node_ids();
3439         for_each_online_node(nid) {
3440                 pg_data_t *pgdat = NODE_DATA(nid);
3441                 free_area_init_node(nid, pgdat, NULL,
3442                                 find_min_pfn_for_node(nid), NULL);
3443         }
3444 }
3445
3446 static int __init cmdline_parse_core(char *p, unsigned long *core)
3447 {
3448         unsigned long long coremem;
3449         if (!p)
3450                 return -EINVAL;
3451
3452         coremem = memparse(p, &p);
3453         *core = coremem >> PAGE_SHIFT;
3454
3455         /* Paranoid check that UL is enough for the coremem value */
3456         WARN_ON((coremem >> PAGE_SHIFT) > ULONG_MAX);
3457
3458         return 0;
3459 }
3460
3461 /*
3462  * kernelcore=size sets the amount of memory for use for allocations that
3463  * cannot be reclaimed or migrated.
3464  */
3465 static int __init cmdline_parse_kernelcore(char *p)
3466 {
3467         return cmdline_parse_core(p, &required_kernelcore);
3468 }
3469
3470 /*
3471  * movablecore=size sets the amount of memory for use for allocations that
3472  * can be reclaimed or migrated.
3473  */
3474 static int __init cmdline_parse_movablecore(char *p)
3475 {
3476         return cmdline_parse_core(p, &required_movablecore);
3477 }
3478
3479 early_param("kernelcore", cmdline_parse_kernelcore);
3480 early_param("movablecore", cmdline_parse_movablecore);
3481
3482 #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
3483
3484 /**
3485  * set_dma_reserve - set the specified number of pages reserved in the first zone
3486  * @new_dma_reserve: The number of pages to mark reserved
3487  *
3488  * The per-cpu batchsize and zone watermarks are determined by present_pages.
3489  * In the DMA zone, a significant percentage may be consumed by kernel image
3490  * and other unfreeable allocations which can skew the watermarks badly. This
3491  * function may optionally be used to account for unfreeable pages in the
3492  * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
3493  * smaller per-cpu batchsize.
3494  */
3495 void __init set_dma_reserve(unsigned long new_dma_reserve)
3496 {
3497         dma_reserve = new_dma_reserve;
3498 }
3499
3500 #ifndef CONFIG_NEED_MULTIPLE_NODES
3501 static bootmem_data_t contig_bootmem_data;
3502 struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };
3503
3504 EXPORT_SYMBOL(contig_page_data);
3505 #endif
3506
3507 void __init free_area_init(unsigned long *zones_size)
3508 {
3509         free_area_init_node(0, NODE_DATA(0), zones_size,
3510                         __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
3511 }
3512
3513 static int page_alloc_cpu_notify(struct notifier_block *self,
3514                                  unsigned long action, void *hcpu)
3515 {
3516         int cpu = (unsigned long)hcpu;
3517
3518         if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
3519                 local_irq_disable();
3520                 __drain_pages(cpu);
3521                 vm_events_fold_cpu(cpu);
3522                 local_irq_enable();
3523                 refresh_cpu_vm_stats(cpu);
3524         }
3525         return NOTIFY_OK;
3526 }
3527
3528 void __init page_alloc_init(void)
3529 {
3530         hotcpu_notifier(page_alloc_cpu_notify, 0);
3531 }
3532
3533 /*
3534  * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio
3535  *      or min_free_kbytes changes.
3536  */
3537 static void calculate_totalreserve_pages(void)
3538 {
3539         struct pglist_data *pgdat;
3540         unsigned long reserve_pages = 0;
3541         enum zone_type i, j;
3542
3543         for_each_online_pgdat(pgdat) {
3544                 for (i = 0; i < MAX_NR_ZONES; i++) {
3545                         struct zone *zone = pgdat->node_zones + i;
3546                         unsigned long max = 0;
3547
3548                         /* Find valid and maximum lowmem_reserve in the zone */
3549                         for (j = i; j < MAX_NR_ZONES; j++) {
3550                                 if (zone->lowmem_reserve[j] > max)
3551                                         max = zone->lowmem_reserve[j];
3552                         }
3553
3554                         /* we treat pages_high as reserved pages. */
3555                         max += zone->pages_high;
3556
3557                         if (max > zone->present_pages)
3558                                 max = zone->present_pages;
3559                         reserve_pages += max;
3560                 }
3561         }
3562         totalreserve_pages = reserve_pages;
3563 }
3564
3565 /*
3566  * setup_per_zone_lowmem_reserve - called whenever
3567  *      sysctl_lower_zone_reserve_ratio changes.  Ensures that each zone
3568  *      has a correct pages reserved value, so an adequate number of
3569  *      pages are left in the zone after a successful __alloc_pages().
3570  */
3571 static void setup_per_zone_lowmem_reserve(void)
3572 {
3573         struct pglist_data *pgdat;
3574         enum zone_type j, idx;
3575
3576         for_each_online_pgdat(pgdat) {
3577                 for (j = 0; j < MAX_NR_ZONES; j++) {
3578                         struct zone *zone = pgdat->node_zones + j;
3579                         unsigned long present_pages = zone->present_pages;
3580
3581                         zone->lowmem_reserve[j] = 0;
3582
3583                         idx = j;
3584                         while (idx) {
3585                                 struct zone *lower_zone;
3586
3587                                 idx--;
3588
3589                                 if (sysctl_lowmem_reserve_ratio[idx] < 1)
3590                                         sysctl_lowmem_reserve_ratio[idx] = 1;
3591
3592                                 lower_zone = pgdat->node_zones + idx;
3593                                 lower_zone->lowmem_reserve[j] = present_pages /
3594                                         sysctl_lowmem_reserve_ratio[idx];
3595                                 present_pages += lower_zone->present_pages;
3596                         }
3597                 }
3598         }
3599
3600         /* update totalreserve_pages */
3601         calculate_totalreserve_pages();
3602 }
3603
3604 /**
3605  * setup_per_zone_pages_min - called when min_free_kbytes changes.
3606  *
3607  * Ensures that the pages_{min,low,high} values for each zone are set correctly
3608  * with respect to min_free_kbytes.
3609  */
3610 void setup_per_zone_pages_min(void)
3611 {
3612         unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
3613         unsigned long lowmem_pages = 0;
3614         struct zone *zone;
3615         unsigned long flags;
3616
3617         /* Calculate total number of !ZONE_HIGHMEM pages */
3618         for_each_zone(zone) {
3619                 if (!is_highmem(zone))
3620                         lowmem_pages += zone->present_pages;
3621         }
3622
3623         for_each_zone(zone) {
3624                 u64 tmp;
3625
3626                 spin_lock_irqsave(&zone->lru_lock, flags);
3627                 tmp = (u64)pages_min * zone->present_pages;
3628                 do_div(tmp, lowmem_pages);
3629                 if (is_highmem(zone)) {
3630                         /*
3631                          * __GFP_HIGH and PF_MEMALLOC allocations usually don't
3632                          * need highmem pages, so cap pages_min to a small
3633                          * value here.
3634                          *
3635                          * The (pages_high-pages_low) and (pages_low-pages_min)
3636                          * deltas controls asynch page reclaim, and so should
3637                          * not be capped for highmem.
3638                          */
3639                         int min_pages;
3640
3641                         min_pages = zone->present_pages / 1024;
3642                         if (min_pages < SWAP_CLUSTER_MAX)
3643                                 min_pages = SWAP_CLUSTER_MAX;
3644                         if (min_pages > 128)
3645                                 min_pages = 128;
3646                         zone->pages_min = min_pages;
3647                 } else {
3648                         /*
3649                          * If it's a lowmem zone, reserve a number of pages
3650                          * proportionate to the zone's size.
3651                          */
3652                         zone->pages_min = tmp;
3653                 }
3654
3655                 zone->pages_low   = zone->pages_min + (tmp >> 2);
3656                 zone->pages_high  = zone->pages_min + (tmp >> 1);
3657                 spin_unlock_irqrestore(&zone->lru_lock, flags);
3658         }
3659
3660         /* update totalreserve_pages */
3661         calculate_totalreserve_pages();
3662 }
3663
3664 /*
3665  * Initialise min_free_kbytes.
3666  *
3667  * For small machines we want it small (128k min).  For large machines
3668  * we want it large (64MB max).  But it is not linear, because network
3669  * bandwidth does not increase linearly with machine size.  We use
3670  *
3671  *      min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
3672  *      min_free_kbytes = sqrt(lowmem_kbytes * 16)
3673  *
3674  * which yields
3675  *
3676  * 16MB:        512k
3677  * 32MB:        724k
3678  * 64MB:        1024k
3679  * 128MB:       1448k
3680  * 256MB:       2048k
3681  * 512MB:       2896k
3682  * 1024MB:      4096k
3683  * 2048MB:      5792k
3684  * 4096MB:      8192k
3685  * 8192MB:      11584k
3686  * 16384MB:     16384k
3687  */
3688 static int __init init_per_zone_pages_min(void)
3689 {
3690         unsigned long lowmem_kbytes;
3691
3692         lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
3693
3694         min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
3695         if (min_free_kbytes < 128)
3696                 min_free_kbytes = 128;
3697         if (min_free_kbytes > 65536)
3698                 min_free_kbytes = 65536;
3699         setup_per_zone_pages_min();
3700         setup_per_zone_lowmem_reserve();
3701         return 0;
3702 }
3703 module_init(init_per_zone_pages_min)
3704
3705 /*
3706  * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 
3707  *      that we can call two helper functions whenever min_free_kbytes
3708  *      changes.
3709  */
3710 int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 
3711         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
3712 {
3713         proc_dointvec(table, write, file, buffer, length, ppos);
3714         if (write)
3715                 setup_per_zone_pages_min();
3716         return 0;
3717 }
3718
3719 #ifdef CONFIG_NUMA
3720 int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write,
3721         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
3722 {
3723         struct zone *zone;
3724         int rc;
3725
3726         rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
3727         if (rc)
3728                 return rc;
3729
3730         for_each_zone(zone)
3731                 zone->min_unmapped_pages = (zone->present_pages *
3732                                 sysctl_min_unmapped_ratio) / 100;
3733         return 0;
3734 }
3735
3736 int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write,
3737         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
3738 {
3739         struct zone *zone;
3740         int rc;
3741
3742         rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
3743         if (rc)
3744                 return rc;
3745
3746         for_each_zone(zone)
3747                 zone->min_slab_pages = (zone->present_pages *
3748                                 sysctl_min_slab_ratio) / 100;
3749         return 0;
3750 }
3751 #endif
3752
3753 /*
3754  * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
3755  *      proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
3756  *      whenever sysctl_lowmem_reserve_ratio changes.
3757  *
3758  * The reserve ratio obviously has absolutely no relation with the
3759  * pages_min watermarks. The lowmem reserve ratio can only make sense
3760  * if in function of the boot time zone sizes.
3761  */
3762 int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
3763         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
3764 {
3765         proc_dointvec_minmax(table, write, file, buffer, length, ppos);
3766         setup_per_zone_lowmem_reserve();
3767         return 0;
3768 }
3769
3770 /*
3771  * percpu_pagelist_fraction - changes the pcp->high for each zone on each
3772  * cpu.  It is the fraction of total pages in each zone that a hot per cpu pagelist
3773  * can have before it gets flushed back to buddy allocator.
3774  */
3775
3776 int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write,
3777         struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
3778 {
3779         struct zone *zone;
3780         unsigned int cpu;
3781         int ret;
3782
3783         ret = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
3784         if (!write || (ret == -EINVAL))
3785                 return ret;
3786         for_each_zone(zone) {
3787                 for_each_online_cpu(cpu) {
3788                         unsigned long  high;
3789                         high = zone->present_pages / percpu_pagelist_fraction;
3790                         setup_pagelist_highmark(zone_pcp(zone, cpu), high);
3791                 }
3792         }
3793         return 0;
3794 }
3795
3796 int hashdist = HASHDIST_DEFAULT;
3797
3798 #ifdef CONFIG_NUMA
3799 static int __init set_hashdist(char *str)
3800 {
3801         if (!str)
3802                 return 0;
3803         hashdist = simple_strtoul(str, &str, 0);
3804         return 1;
3805 }
3806 __setup("hashdist=", set_hashdist);
3807 #endif
3808
3809 /*
3810  * allocate a large system hash table from bootmem
3811  * - it is assumed that the hash table must contain an exact power-of-2
3812  *   quantity of entries
3813  * - limit is the number of hash buckets, not the total allocation size
3814  */
3815 void *__init alloc_large_system_hash(const char *tablename,
3816                                      unsigned long bucketsize,
3817                                      unsigned long numentries,
3818                                      int scale,
3819                                      int flags,
3820                                      unsigned int *_hash_shift,
3821                                      unsigned int *_hash_mask,
3822                                      unsigned long limit)
3823 {
3824         unsigned long long max = limit;
3825         unsigned long log2qty, size;
3826         void *table = NULL;
3827
3828         /* allow the kernel cmdline to have a say */
3829         if (!numentries) {
3830                 /* round applicable memory size up to nearest megabyte */
3831                 numentries = nr_kernel_pages;
3832                 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
3833                 numentries >>= 20 - PAGE_SHIFT;
3834                 numentries <<= 20 - PAGE_SHIFT;
3835
3836                 /* limit to 1 bucket per 2^scale bytes of low memory */
3837                 if (scale > PAGE_SHIFT)
3838                         numentries >>= (scale - PAGE_SHIFT);
3839                 else
3840                         numentries <<= (PAGE_SHIFT - scale);
3841
3842                 /* Make sure we've got at least a 0-order allocation.. */
3843                 if (unlikely((numentries * bucketsize) < PAGE_SIZE))
3844                         numentries = PAGE_SIZE / bucketsize;
3845         }
3846         numentries = roundup_pow_of_two(numentries);
3847
3848         /* limit allocation size to 1/16 total memory by default */
3849         if (max == 0) {
3850                 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
3851                 do_div(max, bucketsize);
3852         }
3853
3854         if (numentries > max)
3855                 numentries = max;
3856
3857         log2qty = ilog2(numentries);
3858
3859         do {
3860                 size = bucketsize << log2qty;
3861                 if (flags & HASH_EARLY)
3862                         table = alloc_bootmem(size);
3863                 else if (hashdist)
3864                         table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
3865                 else {
3866                         unsigned long order;
3867                         for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++)
3868                                 ;
3869                         table = (void*) __get_free_pages(GFP_ATOMIC, order);
3870                         /*
3871                          * If bucketsize is not a power-of-two, we may free
3872                          * some pages at the end of hash table.
3873                          */
3874                         if (table) {
3875                                 unsigned long alloc_end = (unsigned long)table +
3876                                                 (PAGE_SIZE << order);
3877                                 unsigned long used = (unsigned long)table +
3878                                                 PAGE_ALIGN(size);
3879                                 split_page(virt_to_page(table), order);
3880                                 while (used < alloc_end) {
3881                                         free_page(used);
3882                                         used += PAGE_SIZE;
3883                                 }
3884                         }
3885                 }
3886         } while (!table && size > PAGE_SIZE && --log2qty);
3887
3888         if (!table)
3889                 panic("Failed to allocate %s hash table\n", tablename);
3890
3891         printk(KERN_INFO "%s hash table entries: %d (order: %d, %lu bytes)\n",
3892                tablename,
3893                (1U << log2qty),
3894                ilog2(size) - PAGE_SHIFT,
3895                size);
3896
3897         if (_hash_shift)
3898                 *_hash_shift = log2qty;
3899         if (_hash_mask)
3900                 *_hash_mask = (1 << log2qty) - 1;
3901
3902         return table;
3903 }
3904
3905 #ifdef CONFIG_OUT_OF_LINE_PFN_TO_PAGE
3906 struct page *pfn_to_page(unsigned long pfn)
3907 {
3908         return __pfn_to_page(pfn);
3909 }
3910 unsigned long page_to_pfn(struct page *page)
3911 {
3912         return __page_to_pfn(page);
3913 }
3914 EXPORT_SYMBOL(pfn_to_page);
3915 EXPORT_SYMBOL(page_to_pfn);
3916 #endif /* CONFIG_OUT_OF_LINE_PFN_TO_PAGE */
3917
3918