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