4f95bcf0f2b17a0e3ece890fa3d097038f9c98f4
[linux-2.6.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/memblock.h>
25 #include <linux/compiler.h>
26 #include <linux/kernel.h>
27 #include <linux/kmemcheck.h>
28 #include <linux/module.h>
29 #include <linux/suspend.h>
30 #include <linux/pagevec.h>
31 #include <linux/blkdev.h>
32 #include <linux/slab.h>
33 #include <linux/ratelimit.h>
34 #include <linux/oom.h>
35 #include <linux/notifier.h>
36 #include <linux/topology.h>
37 #include <linux/sysctl.h>
38 #include <linux/cpu.h>
39 #include <linux/cpuset.h>
40 #include <linux/memory_hotplug.h>
41 #include <linux/nodemask.h>
42 #include <linux/vmalloc.h>
43 #include <linux/vmstat.h>
44 #include <linux/mempolicy.h>
45 #include <linux/stop_machine.h>
46 #include <linux/sort.h>
47 #include <linux/pfn.h>
48 #include <linux/backing-dev.h>
49 #include <linux/fault-inject.h>
50 #include <linux/page-isolation.h>
51 #include <linux/page_cgroup.h>
52 #include <linux/debugobjects.h>
53 #include <linux/kmemleak.h>
54 #include <linux/memory.h>
55 #include <linux/compaction.h>
56 #include <trace/events/kmem.h>
57 #include <linux/ftrace_event.h>
58 #include <linux/memcontrol.h>
59 #include <linux/prefetch.h>
60 #include <linux/page-debug-flags.h>
61
62 #include <asm/tlbflush.h>
63 #include <asm/div64.h>
64 #include "internal.h"
65
66 #ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
67 DEFINE_PER_CPU(int, numa_node);
68 EXPORT_PER_CPU_SYMBOL(numa_node);
69 #endif
70
71 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
72 /*
73  * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
74  * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
75  * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
76  * defined in <linux/topology.h>.
77  */
78 DEFINE_PER_CPU(int, _numa_mem_);                /* Kernel "local memory" node */
79 EXPORT_PER_CPU_SYMBOL(_numa_mem_);
80 #endif
81
82 /*
83  * Array of node states.
84  */
85 nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
86         [N_POSSIBLE] = NODE_MASK_ALL,
87         [N_ONLINE] = { { [0] = 1UL } },
88 #ifndef CONFIG_NUMA
89         [N_NORMAL_MEMORY] = { { [0] = 1UL } },
90 #ifdef CONFIG_HIGHMEM
91         [N_HIGH_MEMORY] = { { [0] = 1UL } },
92 #endif
93         [N_CPU] = { { [0] = 1UL } },
94 #endif  /* NUMA */
95 };
96 EXPORT_SYMBOL(node_states);
97
98 unsigned long totalram_pages __read_mostly;
99 unsigned long totalreserve_pages __read_mostly;
100 /*
101  * When calculating the number of globally allowed dirty pages, there
102  * is a certain number of per-zone reserves that should not be
103  * considered dirtyable memory.  This is the sum of those reserves
104  * over all existing zones that contribute dirtyable memory.
105  */
106 unsigned long dirty_balance_reserve __read_mostly;
107
108 int percpu_pagelist_fraction;
109 gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
110
111 #ifdef CONFIG_PM_SLEEP
112 /*
113  * The following functions are used by the suspend/hibernate code to temporarily
114  * change gfp_allowed_mask in order to avoid using I/O during memory allocations
115  * while devices are suspended.  To avoid races with the suspend/hibernate code,
116  * they should always be called with pm_mutex held (gfp_allowed_mask also should
117  * only be modified with pm_mutex held, unless the suspend/hibernate code is
118  * guaranteed not to run in parallel with that modification).
119  */
120
121 static gfp_t saved_gfp_mask;
122
123 void pm_restore_gfp_mask(void)
124 {
125         WARN_ON(!mutex_is_locked(&pm_mutex));
126         if (saved_gfp_mask) {
127                 gfp_allowed_mask = saved_gfp_mask;
128                 saved_gfp_mask = 0;
129         }
130 }
131
132 void pm_restrict_gfp_mask(void)
133 {
134         WARN_ON(!mutex_is_locked(&pm_mutex));
135         WARN_ON(saved_gfp_mask);
136         saved_gfp_mask = gfp_allowed_mask;
137         gfp_allowed_mask &= ~GFP_IOFS;
138 }
139
140 bool pm_suspended_storage(void)
141 {
142         if ((gfp_allowed_mask & GFP_IOFS) == GFP_IOFS)
143                 return false;
144         return true;
145 }
146 #endif /* CONFIG_PM_SLEEP */
147
148 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
149 int pageblock_order __read_mostly;
150 #endif
151
152 static void __free_pages_ok(struct page *page, unsigned int order);
153
154 /*
155  * results with 256, 32 in the lowmem_reserve sysctl:
156  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
157  *      1G machine -> (16M dma, 784M normal, 224M high)
158  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
159  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
160  *      HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
161  *
162  * TBD: should special case ZONE_DMA32 machines here - in those we normally
163  * don't need any ZONE_NORMAL reservation
164  */
165 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
166 #ifdef CONFIG_ZONE_DMA
167          256,
168 #endif
169 #ifdef CONFIG_ZONE_DMA32
170          256,
171 #endif
172 #ifdef CONFIG_HIGHMEM
173          32,
174 #endif
175          32,
176 };
177
178 EXPORT_SYMBOL(totalram_pages);
179
180 static char * const zone_names[MAX_NR_ZONES] = {
181 #ifdef CONFIG_ZONE_DMA
182          "DMA",
183 #endif
184 #ifdef CONFIG_ZONE_DMA32
185          "DMA32",
186 #endif
187          "Normal",
188 #ifdef CONFIG_HIGHMEM
189          "HighMem",
190 #endif
191          "Movable",
192 };
193
194 int min_free_kbytes = 1024;
195
196 static unsigned long __meminitdata nr_kernel_pages;
197 static unsigned long __meminitdata nr_all_pages;
198 static unsigned long __meminitdata dma_reserve;
199
200 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
201 static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
202 static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
203 static unsigned long __initdata required_kernelcore;
204 static unsigned long __initdata required_movablecore;
205 static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
206
207 /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
208 int movable_zone;
209 EXPORT_SYMBOL(movable_zone);
210 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
211
212 #if MAX_NUMNODES > 1
213 int nr_node_ids __read_mostly = MAX_NUMNODES;
214 int nr_online_nodes __read_mostly = 1;
215 EXPORT_SYMBOL(nr_node_ids);
216 EXPORT_SYMBOL(nr_online_nodes);
217 #endif
218
219 int page_group_by_mobility_disabled __read_mostly;
220
221 static void set_pageblock_migratetype(struct page *page, int migratetype)
222 {
223
224         if (unlikely(page_group_by_mobility_disabled))
225                 migratetype = MIGRATE_UNMOVABLE;
226
227         set_pageblock_flags_group(page, (unsigned long)migratetype,
228                                         PB_migrate, PB_migrate_end);
229 }
230
231 bool oom_killer_disabled __read_mostly;
232
233 #ifdef CONFIG_DEBUG_VM
234 static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
235 {
236         int ret = 0;
237         unsigned seq;
238         unsigned long pfn = page_to_pfn(page);
239
240         do {
241                 seq = zone_span_seqbegin(zone);
242                 if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
243                         ret = 1;
244                 else if (pfn < zone->zone_start_pfn)
245                         ret = 1;
246         } while (zone_span_seqretry(zone, seq));
247
248         return ret;
249 }
250
251 static int page_is_consistent(struct zone *zone, struct page *page)
252 {
253         if (!pfn_valid_within(page_to_pfn(page)))
254                 return 0;
255         if (zone != page_zone(page))
256                 return 0;
257
258         return 1;
259 }
260 /*
261  * Temporary debugging check for pages not lying within a given zone.
262  */
263 static int bad_range(struct zone *zone, struct page *page)
264 {
265         if (page_outside_zone_boundaries(zone, page))
266                 return 1;
267         if (!page_is_consistent(zone, page))
268                 return 1;
269
270         return 0;
271 }
272 #else
273 static inline int bad_range(struct zone *zone, struct page *page)
274 {
275         return 0;
276 }
277 #endif
278
279 static void bad_page(struct page *page)
280 {
281         static unsigned long resume;
282         static unsigned long nr_shown;
283         static unsigned long nr_unshown;
284
285         /* Don't complain about poisoned pages */
286         if (PageHWPoison(page)) {
287                 reset_page_mapcount(page); /* remove PageBuddy */
288                 return;
289         }
290
291         /*
292          * Allow a burst of 60 reports, then keep quiet for that minute;
293          * or allow a steady drip of one report per second.
294          */
295         if (nr_shown == 60) {
296                 if (time_before(jiffies, resume)) {
297                         nr_unshown++;
298                         goto out;
299                 }
300                 if (nr_unshown) {
301                         printk(KERN_ALERT
302                               "BUG: Bad page state: %lu messages suppressed\n",
303                                 nr_unshown);
304                         nr_unshown = 0;
305                 }
306                 nr_shown = 0;
307         }
308         if (nr_shown++ == 0)
309                 resume = jiffies + 60 * HZ;
310
311         printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx\n",
312                 current->comm, page_to_pfn(page));
313         dump_page(page);
314
315         print_modules();
316         dump_stack();
317 out:
318         /* Leave bad fields for debug, except PageBuddy could make trouble */
319         reset_page_mapcount(page); /* remove PageBuddy */
320         add_taint(TAINT_BAD_PAGE);
321 }
322
323 /*
324  * Higher-order pages are called "compound pages".  They are structured thusly:
325  *
326  * The first PAGE_SIZE page is called the "head page".
327  *
328  * The remaining PAGE_SIZE pages are called "tail pages".
329  *
330  * All pages have PG_compound set.  All tail pages have their ->first_page
331  * pointing at the head page.
332  *
333  * The first tail page's ->lru.next holds the address of the compound page's
334  * put_page() function.  Its ->lru.prev holds the order of allocation.
335  * This usage means that zero-order pages may not be compound.
336  */
337
338 static void free_compound_page(struct page *page)
339 {
340         __free_pages_ok(page, compound_order(page));
341 }
342
343 void prep_compound_page(struct page *page, unsigned long order)
344 {
345         int i;
346         int nr_pages = 1 << order;
347
348         set_compound_page_dtor(page, free_compound_page);
349         set_compound_order(page, order);
350         __SetPageHead(page);
351         for (i = 1; i < nr_pages; i++) {
352                 struct page *p = page + i;
353                 __SetPageTail(p);
354                 set_page_count(p, 0);
355                 p->first_page = page;
356         }
357 }
358
359 /* update __split_huge_page_refcount if you change this function */
360 static int destroy_compound_page(struct page *page, unsigned long order)
361 {
362         int i;
363         int nr_pages = 1 << order;
364         int bad = 0;
365
366         if (unlikely(compound_order(page) != order) ||
367             unlikely(!PageHead(page))) {
368                 bad_page(page);
369                 bad++;
370         }
371
372         __ClearPageHead(page);
373
374         for (i = 1; i < nr_pages; i++) {
375                 struct page *p = page + i;
376
377                 if (unlikely(!PageTail(p) || (p->first_page != page))) {
378                         bad_page(page);
379                         bad++;
380                 }
381                 __ClearPageTail(p);
382         }
383
384         return bad;
385 }
386
387 static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
388 {
389         int i;
390
391         /*
392          * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
393          * and __GFP_HIGHMEM from hard or soft interrupt context.
394          */
395         VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
396         for (i = 0; i < (1 << order); i++)
397                 clear_highpage(page + i);
398 }
399
400 #ifdef CONFIG_DEBUG_PAGEALLOC
401 unsigned int _debug_guardpage_minorder;
402
403 static int __init debug_guardpage_minorder_setup(char *buf)
404 {
405         unsigned long res;
406
407         if (kstrtoul(buf, 10, &res) < 0 ||  res > MAX_ORDER / 2) {
408                 printk(KERN_ERR "Bad debug_guardpage_minorder value\n");
409                 return 0;
410         }
411         _debug_guardpage_minorder = res;
412         printk(KERN_INFO "Setting debug_guardpage_minorder to %lu\n", res);
413         return 0;
414 }
415 __setup("debug_guardpage_minorder=", debug_guardpage_minorder_setup);
416
417 static inline void set_page_guard_flag(struct page *page)
418 {
419         __set_bit(PAGE_DEBUG_FLAG_GUARD, &page->debug_flags);
420 }
421
422 static inline void clear_page_guard_flag(struct page *page)
423 {
424         __clear_bit(PAGE_DEBUG_FLAG_GUARD, &page->debug_flags);
425 }
426 #else
427 static inline void set_page_guard_flag(struct page *page) { }
428 static inline void clear_page_guard_flag(struct page *page) { }
429 #endif
430
431 static inline void set_page_order(struct page *page, int order)
432 {
433         set_page_private(page, order);
434         __SetPageBuddy(page);
435 }
436
437 static inline void rmv_page_order(struct page *page)
438 {
439         __ClearPageBuddy(page);
440         set_page_private(page, 0);
441 }
442
443 /*
444  * Locate the struct page for both the matching buddy in our
445  * pair (buddy1) and the combined O(n+1) page they form (page).
446  *
447  * 1) Any buddy B1 will have an order O twin B2 which satisfies
448  * the following equation:
449  *     B2 = B1 ^ (1 << O)
450  * For example, if the starting buddy (buddy2) is #8 its order
451  * 1 buddy is #10:
452  *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
453  *
454  * 2) Any buddy B will have an order O+1 parent P which
455  * satisfies the following equation:
456  *     P = B & ~(1 << O)
457  *
458  * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
459  */
460 static inline unsigned long
461 __find_buddy_index(unsigned long page_idx, unsigned int order)
462 {
463         return page_idx ^ (1 << order);
464 }
465
466 /*
467  * This function checks whether a page is free && is the buddy
468  * we can do coalesce a page and its buddy if
469  * (a) the buddy is not in a hole &&
470  * (b) the buddy is in the buddy system &&
471  * (c) a page and its buddy have the same order &&
472  * (d) a page and its buddy are in the same zone.
473  *
474  * For recording whether a page is in the buddy system, we set ->_mapcount -2.
475  * Setting, clearing, and testing _mapcount -2 is serialized by zone->lock.
476  *
477  * For recording page's order, we use page_private(page).
478  */
479 static inline int page_is_buddy(struct page *page, struct page *buddy,
480                                                                 int order)
481 {
482         if (!pfn_valid_within(page_to_pfn(buddy)))
483                 return 0;
484
485         if (page_zone_id(page) != page_zone_id(buddy))
486                 return 0;
487
488         if (page_is_guard(buddy) && page_order(buddy) == order) {
489                 VM_BUG_ON(page_count(buddy) != 0);
490                 return 1;
491         }
492
493         if (PageBuddy(buddy) && page_order(buddy) == order) {
494                 VM_BUG_ON(page_count(buddy) != 0);
495                 return 1;
496         }
497         return 0;
498 }
499
500 /*
501  * Freeing function for a buddy system allocator.
502  *
503  * The concept of a buddy system is to maintain direct-mapped table
504  * (containing bit values) for memory blocks of various "orders".
505  * The bottom level table contains the map for the smallest allocatable
506  * units of memory (here, pages), and each level above it describes
507  * pairs of units from the levels below, hence, "buddies".
508  * At a high level, all that happens here is marking the table entry
509  * at the bottom level available, and propagating the changes upward
510  * as necessary, plus some accounting needed to play nicely with other
511  * parts of the VM system.
512  * At each level, we keep a list of pages, which are heads of continuous
513  * free pages of length of (1 << order) and marked with _mapcount -2. Page's
514  * order is recorded in page_private(page) field.
515  * So when we are allocating or freeing one, we can derive the state of the
516  * other.  That is, if we allocate a small block, and both were   
517  * free, the remainder of the region must be split into blocks.   
518  * If a block is freed, and its buddy is also free, then this
519  * triggers coalescing into a block of larger size.            
520  *
521  * -- wli
522  */
523
524 static inline void __free_one_page(struct page *page,
525                 struct zone *zone, unsigned int order,
526                 int migratetype)
527 {
528         unsigned long page_idx;
529         unsigned long combined_idx;
530         unsigned long uninitialized_var(buddy_idx);
531         struct page *buddy;
532
533         if (unlikely(PageCompound(page)))
534                 if (unlikely(destroy_compound_page(page, order)))
535                         return;
536
537         VM_BUG_ON(migratetype == -1);
538
539         page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
540
541         VM_BUG_ON(page_idx & ((1 << order) - 1));
542         VM_BUG_ON(bad_range(zone, page));
543
544         while (order < MAX_ORDER-1) {
545                 buddy_idx = __find_buddy_index(page_idx, order);
546                 buddy = page + (buddy_idx - page_idx);
547                 if (!page_is_buddy(page, buddy, order))
548                         break;
549                 /*
550                  * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
551                  * merge with it and move up one order.
552                  */
553                 if (page_is_guard(buddy)) {
554                         clear_page_guard_flag(buddy);
555                         set_page_private(page, 0);
556                         __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
557                 } else {
558                         list_del(&buddy->lru);
559                         zone->free_area[order].nr_free--;
560                         rmv_page_order(buddy);
561                 }
562                 combined_idx = buddy_idx & page_idx;
563                 page = page + (combined_idx - page_idx);
564                 page_idx = combined_idx;
565                 order++;
566         }
567         set_page_order(page, order);
568
569         /*
570          * If this is not the largest possible page, check if the buddy
571          * of the next-highest order is free. If it is, it's possible
572          * that pages are being freed that will coalesce soon. In case,
573          * that is happening, add the free page to the tail of the list
574          * so it's less likely to be used soon and more likely to be merged
575          * as a higher order page
576          */
577         if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
578                 struct page *higher_page, *higher_buddy;
579                 combined_idx = buddy_idx & page_idx;
580                 higher_page = page + (combined_idx - page_idx);
581                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
582                 higher_buddy = page + (buddy_idx - combined_idx);
583                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
584                         list_add_tail(&page->lru,
585                                 &zone->free_area[order].free_list[migratetype]);
586                         goto out;
587                 }
588         }
589
590         list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
591 out:
592         zone->free_area[order].nr_free++;
593 }
594
595 /*
596  * free_page_mlock() -- clean up attempts to free and mlocked() page.
597  * Page should not be on lru, so no need to fix that up.
598  * free_pages_check() will verify...
599  */
600 static inline void free_page_mlock(struct page *page)
601 {
602         __dec_zone_page_state(page, NR_MLOCK);
603         __count_vm_event(UNEVICTABLE_MLOCKFREED);
604 }
605
606 static inline int free_pages_check(struct page *page)
607 {
608         if (unlikely(page_mapcount(page) |
609                 (page->mapping != NULL)  |
610                 (atomic_read(&page->_count) != 0) |
611                 (page->flags & PAGE_FLAGS_CHECK_AT_FREE) |
612                 (mem_cgroup_bad_page_check(page)))) {
613                 bad_page(page);
614                 return 1;
615         }
616         if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
617                 page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
618         return 0;
619 }
620
621 /*
622  * Frees a number of pages from the PCP lists
623  * Assumes all pages on list are in same zone, and of same order.
624  * count is the number of pages to free.
625  *
626  * If the zone was previously in an "all pages pinned" state then look to
627  * see if this freeing clears that state.
628  *
629  * And clear the zone's pages_scanned counter, to hold off the "all pages are
630  * pinned" detection logic.
631  */
632 static void free_pcppages_bulk(struct zone *zone, int count,
633                                         struct per_cpu_pages *pcp)
634 {
635         int migratetype = 0;
636         int batch_free = 0;
637         int to_free = count;
638
639         spin_lock(&zone->lock);
640         zone->all_unreclaimable = 0;
641         zone->pages_scanned = 0;
642
643         while (to_free) {
644                 struct page *page;
645                 struct list_head *list;
646
647                 /*
648                  * Remove pages from lists in a round-robin fashion. A
649                  * batch_free count is maintained that is incremented when an
650                  * empty list is encountered.  This is so more pages are freed
651                  * off fuller lists instead of spinning excessively around empty
652                  * lists
653                  */
654                 do {
655                         batch_free++;
656                         if (++migratetype == MIGRATE_PCPTYPES)
657                                 migratetype = 0;
658                         list = &pcp->lists[migratetype];
659                 } while (list_empty(list));
660
661                 /* This is the only non-empty list. Free them all. */
662                 if (batch_free == MIGRATE_PCPTYPES)
663                         batch_free = to_free;
664
665                 do {
666                         page = list_entry(list->prev, struct page, lru);
667                         /* must delete as __free_one_page list manipulates */
668                         list_del(&page->lru);
669                         /* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
670                         __free_one_page(page, zone, 0, page_private(page));
671                         trace_mm_page_pcpu_drain(page, 0, page_private(page));
672                 } while (--to_free && --batch_free && !list_empty(list));
673         }
674         __mod_zone_page_state(zone, NR_FREE_PAGES, count);
675         spin_unlock(&zone->lock);
676 }
677
678 static void free_one_page(struct zone *zone, struct page *page, int order,
679                                 int migratetype)
680 {
681         spin_lock(&zone->lock);
682         zone->all_unreclaimable = 0;
683         zone->pages_scanned = 0;
684
685         __free_one_page(page, zone, order, migratetype);
686         __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
687         spin_unlock(&zone->lock);
688 }
689
690 static bool free_pages_prepare(struct page *page, unsigned int order)
691 {
692         int i;
693         int bad = 0;
694
695         trace_mm_page_free(page, order);
696         kmemcheck_free_shadow(page, order);
697
698         if (PageAnon(page))
699                 page->mapping = NULL;
700         for (i = 0; i < (1 << order); i++)
701                 bad += free_pages_check(page + i);
702         if (bad)
703                 return false;
704
705         if (!PageHighMem(page)) {
706                 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
707                 debug_check_no_obj_freed(page_address(page),
708                                            PAGE_SIZE << order);
709         }
710         arch_free_page(page, order);
711         kernel_map_pages(page, 1 << order, 0);
712
713         return true;
714 }
715
716 static void __free_pages_ok(struct page *page, unsigned int order)
717 {
718         unsigned long flags;
719         int wasMlocked = __TestClearPageMlocked(page);
720
721         if (!free_pages_prepare(page, order))
722                 return;
723
724         local_irq_save(flags);
725         if (unlikely(wasMlocked))
726                 free_page_mlock(page);
727         __count_vm_events(PGFREE, 1 << order);
728         free_one_page(page_zone(page), page, order,
729                                         get_pageblock_migratetype(page));
730         local_irq_restore(flags);
731 }
732
733 /*
734  * permit the bootmem allocator to evade page validation on high-order frees
735  */
736 void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
737 {
738         if (order == 0) {
739                 __ClearPageReserved(page);
740                 set_page_count(page, 0);
741                 set_page_refcounted(page);
742                 __free_page(page);
743         } else {
744                 int loop;
745
746                 prefetchw(page);
747                 for (loop = 0; loop < (1 << order); loop++) {
748                         struct page *p = &page[loop];
749
750                         if (loop + 1 < (1 << order))
751                                 prefetchw(p + 1);
752                         __ClearPageReserved(p);
753                         set_page_count(p, 0);
754                 }
755
756                 set_page_refcounted(page);
757                 __free_pages(page, order);
758         }
759 }
760
761
762 /*
763  * The order of subdivision here is critical for the IO subsystem.
764  * Please do not alter this order without good reasons and regression
765  * testing. Specifically, as large blocks of memory are subdivided,
766  * the order in which smaller blocks are delivered depends on the order
767  * they're subdivided in this function. This is the primary factor
768  * influencing the order in which pages are delivered to the IO
769  * subsystem according to empirical testing, and this is also justified
770  * by considering the behavior of a buddy system containing a single
771  * large block of memory acted on by a series of small allocations.
772  * This behavior is a critical factor in sglist merging's success.
773  *
774  * -- wli
775  */
776 static inline void expand(struct zone *zone, struct page *page,
777         int low, int high, struct free_area *area,
778         int migratetype)
779 {
780         unsigned long size = 1 << high;
781
782         while (high > low) {
783                 area--;
784                 high--;
785                 size >>= 1;
786                 VM_BUG_ON(bad_range(zone, &page[size]));
787
788 #ifdef CONFIG_DEBUG_PAGEALLOC
789                 if (high < debug_guardpage_minorder()) {
790                         /*
791                          * Mark as guard pages (or page), that will allow to
792                          * merge back to allocator when buddy will be freed.
793                          * Corresponding page table entries will not be touched,
794                          * pages will stay not present in virtual address space
795                          */
796                         INIT_LIST_HEAD(&page[size].lru);
797                         set_page_guard_flag(&page[size]);
798                         set_page_private(&page[size], high);
799                         /* Guard pages are not available for any usage */
800                         __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << high));
801                         continue;
802                 }
803 #endif
804                 list_add(&page[size].lru, &area->free_list[migratetype]);
805                 area->nr_free++;
806                 set_page_order(&page[size], high);
807         }
808 }
809
810 /*
811  * This page is about to be returned from the page allocator
812  */
813 static inline int check_new_page(struct page *page)
814 {
815         if (unlikely(page_mapcount(page) |
816                 (page->mapping != NULL)  |
817                 (atomic_read(&page->_count) != 0)  |
818                 (page->flags & PAGE_FLAGS_CHECK_AT_PREP) |
819                 (mem_cgroup_bad_page_check(page)))) {
820                 bad_page(page);
821                 return 1;
822         }
823         return 0;
824 }
825
826 static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
827 {
828         int i;
829
830         for (i = 0; i < (1 << order); i++) {
831                 struct page *p = page + i;
832                 if (unlikely(check_new_page(p)))
833                         return 1;
834         }
835
836         set_page_private(page, 0);
837         set_page_refcounted(page);
838
839         arch_alloc_page(page, order);
840         kernel_map_pages(page, 1 << order, 1);
841
842         if (gfp_flags & __GFP_ZERO)
843                 prep_zero_page(page, order, gfp_flags);
844
845         if (order && (gfp_flags & __GFP_COMP))
846                 prep_compound_page(page, order);
847
848         return 0;
849 }
850
851 /*
852  * Go through the free lists for the given migratetype and remove
853  * the smallest available page from the freelists
854  */
855 static inline
856 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
857                                                 int migratetype)
858 {
859         unsigned int current_order;
860         struct free_area * area;
861         struct page *page;
862
863         /* Find a page of the appropriate size in the preferred list */
864         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
865                 area = &(zone->free_area[current_order]);
866                 if (list_empty(&area->free_list[migratetype]))
867                         continue;
868
869                 page = list_entry(area->free_list[migratetype].next,
870                                                         struct page, lru);
871                 list_del(&page->lru);
872                 rmv_page_order(page);
873                 area->nr_free--;
874                 expand(zone, page, order, current_order, area, migratetype);
875                 return page;
876         }
877
878         return NULL;
879 }
880
881
882 /*
883  * This array describes the order lists are fallen back to when
884  * the free lists for the desirable migrate type are depleted
885  */
886 static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
887         [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
888         [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
889         [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
890         [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
891 };
892
893 /*
894  * Move the free pages in a range to the free lists of the requested type.
895  * Note that start_page and end_pages are not aligned on a pageblock
896  * boundary. If alignment is required, use move_freepages_block()
897  */
898 static int move_freepages(struct zone *zone,
899                           struct page *start_page, struct page *end_page,
900                           int migratetype)
901 {
902         struct page *page;
903         unsigned long order;
904         int pages_moved = 0;
905
906 #ifndef CONFIG_HOLES_IN_ZONE
907         /*
908          * page_zone is not safe to call in this context when
909          * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
910          * anyway as we check zone boundaries in move_freepages_block().
911          * Remove at a later date when no bug reports exist related to
912          * grouping pages by mobility
913          */
914         BUG_ON(page_zone(start_page) != page_zone(end_page));
915 #endif
916
917         for (page = start_page; page <= end_page;) {
918                 /* Make sure we are not inadvertently changing nodes */
919                 VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));
920
921                 if (!pfn_valid_within(page_to_pfn(page))) {
922                         page++;
923                         continue;
924                 }
925
926                 if (!PageBuddy(page)) {
927                         page++;
928                         continue;
929                 }
930
931                 order = page_order(page);
932                 list_move(&page->lru,
933                           &zone->free_area[order].free_list[migratetype]);
934                 page += 1 << order;
935                 pages_moved += 1 << order;
936         }
937
938         return pages_moved;
939 }
940
941 static int move_freepages_block(struct zone *zone, struct page *page,
942                                 int migratetype)
943 {
944         unsigned long start_pfn, end_pfn;
945         struct page *start_page, *end_page;
946
947         start_pfn = page_to_pfn(page);
948         start_pfn = start_pfn & ~(pageblock_nr_pages-1);
949         start_page = pfn_to_page(start_pfn);
950         end_page = start_page + pageblock_nr_pages - 1;
951         end_pfn = start_pfn + pageblock_nr_pages - 1;
952
953         /* Do not cross zone boundaries */
954         if (start_pfn < zone->zone_start_pfn)
955                 start_page = page;
956         if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
957                 return 0;
958
959         return move_freepages(zone, start_page, end_page, migratetype);
960 }
961
962 static void change_pageblock_range(struct page *pageblock_page,
963                                         int start_order, int migratetype)
964 {
965         int nr_pageblocks = 1 << (start_order - pageblock_order);
966
967         while (nr_pageblocks--) {
968                 set_pageblock_migratetype(pageblock_page, migratetype);
969                 pageblock_page += pageblock_nr_pages;
970         }
971 }
972
973 /* Remove an element from the buddy allocator from the fallback list */
974 static inline struct page *
975 __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
976 {
977         struct free_area * area;
978         int current_order;
979         struct page *page;
980         int migratetype, i;
981
982         /* Find the largest possible block of pages in the other list */
983         for (current_order = MAX_ORDER-1; current_order >= order;
984                                                 --current_order) {
985                 for (i = 0; i < MIGRATE_TYPES - 1; i++) {
986                         migratetype = fallbacks[start_migratetype][i];
987
988                         /* MIGRATE_RESERVE handled later if necessary */
989                         if (migratetype == MIGRATE_RESERVE)
990                                 continue;
991
992                         area = &(zone->free_area[current_order]);
993                         if (list_empty(&area->free_list[migratetype]))
994                                 continue;
995
996                         page = list_entry(area->free_list[migratetype].next,
997                                         struct page, lru);
998                         area->nr_free--;
999
1000                         /*
1001                          * If breaking a large block of pages, move all free
1002                          * pages to the preferred allocation list. If falling
1003                          * back for a reclaimable kernel allocation, be more
1004                          * aggressive about taking ownership of free pages
1005                          */
1006                         if (unlikely(current_order >= (pageblock_order >> 1)) ||
1007                                         start_migratetype == MIGRATE_RECLAIMABLE ||
1008                                         page_group_by_mobility_disabled) {
1009                                 unsigned long pages;
1010                                 pages = move_freepages_block(zone, page,
1011                                                                 start_migratetype);
1012
1013                                 /* Claim the whole block if over half of it is free */
1014                                 if (pages >= (1 << (pageblock_order-1)) ||
1015                                                 page_group_by_mobility_disabled)
1016                                         set_pageblock_migratetype(page,
1017                                                                 start_migratetype);
1018
1019                                 migratetype = start_migratetype;
1020                         }
1021
1022                         /* Remove the page from the freelists */
1023                         list_del(&page->lru);
1024                         rmv_page_order(page);
1025
1026                         /* Take ownership for orders >= pageblock_order */
1027                         if (current_order >= pageblock_order)
1028                                 change_pageblock_range(page, current_order,
1029                                                         start_migratetype);
1030
1031                         expand(zone, page, order, current_order, area, migratetype);
1032
1033                         trace_mm_page_alloc_extfrag(page, order, current_order,
1034                                 start_migratetype, migratetype);
1035
1036                         return page;
1037                 }
1038         }
1039
1040         return NULL;
1041 }
1042
1043 /*
1044  * Do the hard work of removing an element from the buddy allocator.
1045  * Call me with the zone->lock already held.
1046  */
1047 static struct page *__rmqueue(struct zone *zone, unsigned int order,
1048                                                 int migratetype)
1049 {
1050         struct page *page;
1051
1052 retry_reserve:
1053         page = __rmqueue_smallest(zone, order, migratetype);
1054
1055         if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
1056                 page = __rmqueue_fallback(zone, order, migratetype);
1057
1058                 /*
1059                  * Use MIGRATE_RESERVE rather than fail an allocation. goto
1060                  * is used because __rmqueue_smallest is an inline function
1061                  * and we want just one call site
1062                  */
1063                 if (!page) {
1064                         migratetype = MIGRATE_RESERVE;
1065                         goto retry_reserve;
1066                 }
1067         }
1068
1069         trace_mm_page_alloc_zone_locked(page, order, migratetype);
1070         return page;
1071 }
1072
1073 /* 
1074  * Obtain a specified number of elements from the buddy allocator, all under
1075  * a single hold of the lock, for efficiency.  Add them to the supplied list.
1076  * Returns the number of new pages which were placed at *list.
1077  */
1078 static int rmqueue_bulk(struct zone *zone, unsigned int order, 
1079                         unsigned long count, struct list_head *list,
1080                         int migratetype, int cold)
1081 {
1082         int i;
1083         
1084         spin_lock(&zone->lock);
1085         for (i = 0; i < count; ++i) {
1086                 struct page *page = __rmqueue(zone, order, migratetype);
1087                 if (unlikely(page == NULL))
1088                         break;
1089
1090                 /*
1091                  * Split buddy pages returned by expand() are received here
1092                  * in physical page order. The page is added to the callers and
1093                  * list and the list head then moves forward. From the callers
1094                  * perspective, the linked list is ordered by page number in
1095                  * some conditions. This is useful for IO devices that can
1096                  * merge IO requests if the physical pages are ordered
1097                  * properly.
1098                  */
1099                 if (likely(cold == 0))
1100                         list_add(&page->lru, list);
1101                 else
1102                         list_add_tail(&page->lru, list);
1103                 set_page_private(page, migratetype);
1104                 list = &page->lru;
1105         }
1106         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
1107         spin_unlock(&zone->lock);
1108         return i;
1109 }
1110
1111 #ifdef CONFIG_NUMA
1112 /*
1113  * Called from the vmstat counter updater to drain pagesets of this
1114  * currently executing processor on remote nodes after they have
1115  * expired.
1116  *
1117  * Note that this function must be called with the thread pinned to
1118  * a single processor.
1119  */
1120 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
1121 {
1122         unsigned long flags;
1123         int to_drain;
1124
1125         local_irq_save(flags);
1126         if (pcp->count >= pcp->batch)
1127                 to_drain = pcp->batch;
1128         else
1129                 to_drain = pcp->count;
1130         free_pcppages_bulk(zone, to_drain, pcp);
1131         pcp->count -= to_drain;
1132         local_irq_restore(flags);
1133 }
1134 #endif
1135
1136 /*
1137  * Drain pages of the indicated processor.
1138  *
1139  * The processor must either be the current processor and the
1140  * thread pinned to the current processor or a processor that
1141  * is not online.
1142  */
1143 static void drain_pages(unsigned int cpu)
1144 {
1145         unsigned long flags;
1146         struct zone *zone;
1147
1148         for_each_populated_zone(zone) {
1149                 struct per_cpu_pageset *pset;
1150                 struct per_cpu_pages *pcp;
1151
1152                 local_irq_save(flags);
1153                 pset = per_cpu_ptr(zone->pageset, cpu);
1154
1155                 pcp = &pset->pcp;
1156                 if (pcp->count) {
1157                         free_pcppages_bulk(zone, pcp->count, pcp);
1158                         pcp->count = 0;
1159                 }
1160                 local_irq_restore(flags);
1161         }
1162 }
1163
1164 /*
1165  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
1166  */
1167 void drain_local_pages(void *arg)
1168 {
1169         drain_pages(smp_processor_id());
1170 }
1171
1172 /*
1173  * Spill all the per-cpu pages from all CPUs back into the buddy allocator
1174  */
1175 void drain_all_pages(void)
1176 {
1177         on_each_cpu(drain_local_pages, NULL, 1);
1178 }
1179
1180 #ifdef CONFIG_HIBERNATION
1181
1182 void mark_free_pages(struct zone *zone)
1183 {
1184         unsigned long pfn, max_zone_pfn;
1185         unsigned long flags;
1186         int order, t;
1187         struct list_head *curr;
1188
1189         if (!zone->spanned_pages)
1190                 return;
1191
1192         spin_lock_irqsave(&zone->lock, flags);
1193
1194         max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
1195         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
1196                 if (pfn_valid(pfn)) {
1197                         struct page *page = pfn_to_page(pfn);
1198
1199                         if (!swsusp_page_is_forbidden(page))
1200                                 swsusp_unset_page_free(page);
1201                 }
1202
1203         for_each_migratetype_order(order, t) {
1204                 list_for_each(curr, &zone->free_area[order].free_list[t]) {
1205                         unsigned long i;
1206
1207                         pfn = page_to_pfn(list_entry(curr, struct page, lru));
1208                         for (i = 0; i < (1UL << order); i++)
1209                                 swsusp_set_page_free(pfn_to_page(pfn + i));
1210                 }
1211         }
1212         spin_unlock_irqrestore(&zone->lock, flags);
1213 }
1214 #endif /* CONFIG_PM */
1215
1216 /*
1217  * Free a 0-order page
1218  * cold == 1 ? free a cold page : free a hot page
1219  */
1220 void free_hot_cold_page(struct page *page, int cold)
1221 {
1222         struct zone *zone = page_zone(page);
1223         struct per_cpu_pages *pcp;
1224         unsigned long flags;
1225         int migratetype;
1226         int wasMlocked = __TestClearPageMlocked(page);
1227
1228         if (!free_pages_prepare(page, 0))
1229                 return;
1230
1231         migratetype = get_pageblock_migratetype(page);
1232         set_page_private(page, migratetype);
1233         local_irq_save(flags);
1234         if (unlikely(wasMlocked))
1235                 free_page_mlock(page);
1236         __count_vm_event(PGFREE);
1237
1238         /*
1239          * We only track unmovable, reclaimable and movable on pcp lists.
1240          * Free ISOLATE pages back to the allocator because they are being
1241          * offlined but treat RESERVE as movable pages so we can get those
1242          * areas back if necessary. Otherwise, we may have to free
1243          * excessively into the page allocator
1244          */
1245         if (migratetype >= MIGRATE_PCPTYPES) {
1246                 if (unlikely(migratetype == MIGRATE_ISOLATE)) {
1247                         free_one_page(zone, page, 0, migratetype);
1248                         goto out;
1249                 }
1250                 migratetype = MIGRATE_MOVABLE;
1251         }
1252
1253         pcp = &this_cpu_ptr(zone->pageset)->pcp;
1254         if (cold)
1255                 list_add_tail(&page->lru, &pcp->lists[migratetype]);
1256         else
1257                 list_add(&page->lru, &pcp->lists[migratetype]);
1258         pcp->count++;
1259         if (pcp->count >= pcp->high) {
1260                 free_pcppages_bulk(zone, pcp->batch, pcp);
1261                 pcp->count -= pcp->batch;
1262         }
1263
1264 out:
1265         local_irq_restore(flags);
1266 }
1267
1268 /*
1269  * Free a list of 0-order pages
1270  */
1271 void free_hot_cold_page_list(struct list_head *list, int cold)
1272 {
1273         struct page *page, *next;
1274
1275         list_for_each_entry_safe(page, next, list, lru) {
1276                 trace_mm_page_free_batched(page, cold);
1277                 free_hot_cold_page(page, cold);
1278         }
1279 }
1280
1281 /*
1282  * split_page takes a non-compound higher-order page, and splits it into
1283  * n (1<<order) sub-pages: page[0..n]
1284  * Each sub-page must be freed individually.
1285  *
1286  * Note: this is probably too low level an operation for use in drivers.
1287  * Please consult with lkml before using this in your driver.
1288  */
1289 void split_page(struct page *page, unsigned int order)
1290 {
1291         int i;
1292
1293         VM_BUG_ON(PageCompound(page));
1294         VM_BUG_ON(!page_count(page));
1295
1296 #ifdef CONFIG_KMEMCHECK
1297         /*
1298          * Split shadow pages too, because free(page[0]) would
1299          * otherwise free the whole shadow.
1300          */
1301         if (kmemcheck_page_is_tracked(page))
1302                 split_page(virt_to_page(page[0].shadow), order);
1303 #endif
1304
1305         for (i = 1; i < (1 << order); i++)
1306                 set_page_refcounted(page + i);
1307 }
1308
1309 /*
1310  * Similar to split_page except the page is already free. As this is only
1311  * being used for migration, the migratetype of the block also changes.
1312  * As this is called with interrupts disabled, the caller is responsible
1313  * for calling arch_alloc_page() and kernel_map_page() after interrupts
1314  * are enabled.
1315  *
1316  * Note: this is probably too low level an operation for use in drivers.
1317  * Please consult with lkml before using this in your driver.
1318  */
1319 int split_free_page(struct page *page)
1320 {
1321         unsigned int order;
1322         unsigned long watermark;
1323         struct zone *zone;
1324
1325         BUG_ON(!PageBuddy(page));
1326
1327         zone = page_zone(page);
1328         order = page_order(page);
1329
1330         /* Obey watermarks as if the page was being allocated */
1331         watermark = low_wmark_pages(zone) + (1 << order);
1332         if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
1333                 return 0;
1334
1335         /* Remove page from free list */
1336         list_del(&page->lru);
1337         zone->free_area[order].nr_free--;
1338         rmv_page_order(page);
1339         __mod_zone_page_state(zone, NR_FREE_PAGES, -(1UL << order));
1340
1341         /* Split into individual pages */
1342         set_page_refcounted(page);
1343         split_page(page, order);
1344
1345         if (order >= pageblock_order - 1) {
1346                 struct page *endpage = page + (1 << order) - 1;
1347                 for (; page < endpage; page += pageblock_nr_pages)
1348                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1349         }
1350
1351         return 1 << order;
1352 }
1353
1354 /*
1355  * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
1356  * we cheat by calling it from here, in the order > 0 path.  Saves a branch
1357  * or two.
1358  */
1359 static inline
1360 struct page *buffered_rmqueue(struct zone *preferred_zone,
1361                         struct zone *zone, int order, gfp_t gfp_flags,
1362                         int migratetype)
1363 {
1364         unsigned long flags;
1365         struct page *page;
1366         int cold = !!(gfp_flags & __GFP_COLD);
1367
1368 again:
1369         if (likely(order == 0)) {
1370                 struct per_cpu_pages *pcp;
1371                 struct list_head *list;
1372
1373                 local_irq_save(flags);
1374                 pcp = &this_cpu_ptr(zone->pageset)->pcp;
1375                 list = &pcp->lists[migratetype];
1376                 if (list_empty(list)) {
1377                         pcp->count += rmqueue_bulk(zone, 0,
1378                                         pcp->batch, list,
1379                                         migratetype, cold);
1380                         if (unlikely(list_empty(list)))
1381                                 goto failed;
1382                 }
1383
1384                 if (cold)
1385                         page = list_entry(list->prev, struct page, lru);
1386                 else
1387                         page = list_entry(list->next, struct page, lru);
1388
1389                 list_del(&page->lru);
1390                 pcp->count--;
1391         } else {
1392                 if (unlikely(gfp_flags & __GFP_NOFAIL)) {
1393                         /*
1394                          * __GFP_NOFAIL is not to be used in new code.
1395                          *
1396                          * All __GFP_NOFAIL callers should be fixed so that they
1397                          * properly detect and handle allocation failures.
1398                          *
1399                          * We most definitely don't want callers attempting to
1400                          * allocate greater than order-1 page units with
1401                          * __GFP_NOFAIL.
1402                          */
1403                         WARN_ON_ONCE(order > 1);
1404                 }
1405                 spin_lock_irqsave(&zone->lock, flags);
1406                 page = __rmqueue(zone, order, migratetype);
1407                 spin_unlock(&zone->lock);
1408                 if (!page)
1409                         goto failed;
1410                 __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));
1411         }
1412
1413         __count_zone_vm_events(PGALLOC, zone, 1 << order);
1414         zone_statistics(preferred_zone, zone, gfp_flags);
1415         local_irq_restore(flags);
1416
1417         VM_BUG_ON(bad_range(zone, page));
1418         if (prep_new_page(page, order, gfp_flags))
1419                 goto again;
1420         return page;
1421
1422 failed:
1423         local_irq_restore(flags);
1424         return NULL;
1425 }
1426
1427 /* The ALLOC_WMARK bits are used as an index to zone->watermark */
1428 #define ALLOC_WMARK_MIN         WMARK_MIN
1429 #define ALLOC_WMARK_LOW         WMARK_LOW
1430 #define ALLOC_WMARK_HIGH        WMARK_HIGH
1431 #define ALLOC_NO_WATERMARKS     0x04 /* don't check watermarks at all */
1432
1433 /* Mask to get the watermark bits */
1434 #define ALLOC_WMARK_MASK        (ALLOC_NO_WATERMARKS-1)
1435
1436 #define ALLOC_HARDER            0x10 /* try to alloc harder */
1437 #define ALLOC_HIGH              0x20 /* __GFP_HIGH set */
1438 #define ALLOC_CPUSET            0x40 /* check for correct cpuset */
1439
1440 #ifdef CONFIG_FAIL_PAGE_ALLOC
1441
1442 static struct {
1443         struct fault_attr attr;
1444
1445         u32 ignore_gfp_highmem;
1446         u32 ignore_gfp_wait;
1447         u32 min_order;
1448 } fail_page_alloc = {
1449         .attr = FAULT_ATTR_INITIALIZER,
1450         .ignore_gfp_wait = 1,
1451         .ignore_gfp_highmem = 1,
1452         .min_order = 1,
1453 };
1454
1455 static int __init setup_fail_page_alloc(char *str)
1456 {
1457         return setup_fault_attr(&fail_page_alloc.attr, str);
1458 }
1459 __setup("fail_page_alloc=", setup_fail_page_alloc);
1460
1461 static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1462 {
1463         if (order < fail_page_alloc.min_order)
1464                 return 0;
1465         if (gfp_mask & __GFP_NOFAIL)
1466                 return 0;
1467         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
1468                 return 0;
1469         if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
1470                 return 0;
1471
1472         return should_fail(&fail_page_alloc.attr, 1 << order);
1473 }
1474
1475 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1476
1477 static int __init fail_page_alloc_debugfs(void)
1478 {
1479         umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
1480         struct dentry *dir;
1481
1482         dir = fault_create_debugfs_attr("fail_page_alloc", NULL,
1483                                         &fail_page_alloc.attr);
1484         if (IS_ERR(dir))
1485                 return PTR_ERR(dir);
1486
1487         if (!debugfs_create_bool("ignore-gfp-wait", mode, dir,
1488                                 &fail_page_alloc.ignore_gfp_wait))
1489                 goto fail;
1490         if (!debugfs_create_bool("ignore-gfp-highmem", mode, dir,
1491                                 &fail_page_alloc.ignore_gfp_highmem))
1492                 goto fail;
1493         if (!debugfs_create_u32("min-order", mode, dir,
1494                                 &fail_page_alloc.min_order))
1495                 goto fail;
1496
1497         return 0;
1498 fail:
1499         debugfs_remove_recursive(dir);
1500
1501         return -ENOMEM;
1502 }
1503
1504 late_initcall(fail_page_alloc_debugfs);
1505
1506 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1507
1508 #else /* CONFIG_FAIL_PAGE_ALLOC */
1509
1510 static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1511 {
1512         return 0;
1513 }
1514
1515 #endif /* CONFIG_FAIL_PAGE_ALLOC */
1516
1517 /*
1518  * Return true if free pages are above 'mark'. This takes into account the order
1519  * of the allocation.
1520  */
1521 static bool __zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1522                       int classzone_idx, int alloc_flags, long free_pages)
1523 {
1524         /* free_pages my go negative - that's OK */
1525         long min = mark;
1526         int o;
1527
1528         free_pages -= (1 << order) + 1;
1529         if (alloc_flags & ALLOC_HIGH)
1530                 min -= min / 2;
1531         if (alloc_flags & ALLOC_HARDER)
1532                 min -= min / 4;
1533
1534         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
1535                 return false;
1536         for (o = 0; o < order; o++) {
1537                 /* At the next order, this order's pages become unavailable */
1538                 free_pages -= z->free_area[o].nr_free << o;
1539
1540                 /* Require fewer higher order pages to be free */
1541                 min >>= 1;
1542
1543                 if (free_pages <= min)
1544                         return false;
1545         }
1546         return true;
1547 }
1548
1549 bool zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1550                       int classzone_idx, int alloc_flags)
1551 {
1552         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1553                                         zone_page_state(z, NR_FREE_PAGES));
1554 }
1555
1556 bool zone_watermark_ok_safe(struct zone *z, int order, unsigned long mark,
1557                       int classzone_idx, int alloc_flags)
1558 {
1559         long free_pages = zone_page_state(z, NR_FREE_PAGES);
1560
1561         if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
1562                 free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
1563
1564         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1565                                                                 free_pages);
1566 }
1567
1568 #ifdef CONFIG_NUMA
1569 /*
1570  * zlc_setup - Setup for "zonelist cache".  Uses cached zone data to
1571  * skip over zones that are not allowed by the cpuset, or that have
1572  * been recently (in last second) found to be nearly full.  See further
1573  * comments in mmzone.h.  Reduces cache footprint of zonelist scans
1574  * that have to skip over a lot of full or unallowed zones.
1575  *
1576  * If the zonelist cache is present in the passed in zonelist, then
1577  * returns a pointer to the allowed node mask (either the current
1578  * tasks mems_allowed, or node_states[N_HIGH_MEMORY].)
1579  *
1580  * If the zonelist cache is not available for this zonelist, does
1581  * nothing and returns NULL.
1582  *
1583  * If the fullzones BITMAP in the zonelist cache is stale (more than
1584  * a second since last zap'd) then we zap it out (clear its bits.)
1585  *
1586  * We hold off even calling zlc_setup, until after we've checked the
1587  * first zone in the zonelist, on the theory that most allocations will
1588  * be satisfied from that first zone, so best to examine that zone as
1589  * quickly as we can.
1590  */
1591 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1592 {
1593         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1594         nodemask_t *allowednodes;       /* zonelist_cache approximation */
1595
1596         zlc = zonelist->zlcache_ptr;
1597         if (!zlc)
1598                 return NULL;
1599
1600         if (time_after(jiffies, zlc->last_full_zap + HZ)) {
1601                 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1602                 zlc->last_full_zap = jiffies;
1603         }
1604
1605         allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
1606                                         &cpuset_current_mems_allowed :
1607                                         &node_states[N_HIGH_MEMORY];
1608         return allowednodes;
1609 }
1610
1611 /*
1612  * Given 'z' scanning a zonelist, run a couple of quick checks to see
1613  * if it is worth looking at further for free memory:
1614  *  1) Check that the zone isn't thought to be full (doesn't have its
1615  *     bit set in the zonelist_cache fullzones BITMAP).
1616  *  2) Check that the zones node (obtained from the zonelist_cache
1617  *     z_to_n[] mapping) is allowed in the passed in allowednodes mask.
1618  * Return true (non-zero) if zone is worth looking at further, or
1619  * else return false (zero) if it is not.
1620  *
1621  * This check -ignores- the distinction between various watermarks,
1622  * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ...  If a zone is
1623  * found to be full for any variation of these watermarks, it will
1624  * be considered full for up to one second by all requests, unless
1625  * we are so low on memory on all allowed nodes that we are forced
1626  * into the second scan of the zonelist.
1627  *
1628  * In the second scan we ignore this zonelist cache and exactly
1629  * apply the watermarks to all zones, even it is slower to do so.
1630  * We are low on memory in the second scan, and should leave no stone
1631  * unturned looking for a free page.
1632  */
1633 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1634                                                 nodemask_t *allowednodes)
1635 {
1636         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1637         int i;                          /* index of *z in zonelist zones */
1638         int n;                          /* node that zone *z is on */
1639
1640         zlc = zonelist->zlcache_ptr;
1641         if (!zlc)
1642                 return 1;
1643
1644         i = z - zonelist->_zonerefs;
1645         n = zlc->z_to_n[i];
1646
1647         /* This zone is worth trying if it is allowed but not full */
1648         return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
1649 }
1650
1651 /*
1652  * Given 'z' scanning a zonelist, set the corresponding bit in
1653  * zlc->fullzones, so that subsequent attempts to allocate a page
1654  * from that zone don't waste time re-examining it.
1655  */
1656 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1657 {
1658         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1659         int i;                          /* index of *z in zonelist zones */
1660
1661         zlc = zonelist->zlcache_ptr;
1662         if (!zlc)
1663                 return;
1664
1665         i = z - zonelist->_zonerefs;
1666
1667         set_bit(i, zlc->fullzones);
1668 }
1669
1670 /*
1671  * clear all zones full, called after direct reclaim makes progress so that
1672  * a zone that was recently full is not skipped over for up to a second
1673  */
1674 static void zlc_clear_zones_full(struct zonelist *zonelist)
1675 {
1676         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1677
1678         zlc = zonelist->zlcache_ptr;
1679         if (!zlc)
1680                 return;
1681
1682         bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1683 }
1684
1685 #else   /* CONFIG_NUMA */
1686
1687 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1688 {
1689         return NULL;
1690 }
1691
1692 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1693                                 nodemask_t *allowednodes)
1694 {
1695         return 1;
1696 }
1697
1698 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1699 {
1700 }
1701
1702 static void zlc_clear_zones_full(struct zonelist *zonelist)
1703 {
1704 }
1705 #endif  /* CONFIG_NUMA */
1706
1707 /*
1708  * get_page_from_freelist goes through the zonelist trying to allocate
1709  * a page.
1710  */
1711 static struct page *
1712 get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
1713                 struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
1714                 struct zone *preferred_zone, int migratetype)
1715 {
1716         struct zoneref *z;
1717         struct page *page = NULL;
1718         int classzone_idx;
1719         struct zone *zone;
1720         nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
1721         int zlc_active = 0;             /* set if using zonelist_cache */
1722         int did_zlc_setup = 0;          /* just call zlc_setup() one time */
1723
1724         classzone_idx = zone_idx(preferred_zone);
1725 zonelist_scan:
1726         /*
1727          * Scan zonelist, looking for a zone with enough free.
1728          * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1729          */
1730         for_each_zone_zonelist_nodemask(zone, z, zonelist,
1731                                                 high_zoneidx, nodemask) {
1732                 if (NUMA_BUILD && zlc_active &&
1733                         !zlc_zone_worth_trying(zonelist, z, allowednodes))
1734                                 continue;
1735                 if ((alloc_flags & ALLOC_CPUSET) &&
1736                         !cpuset_zone_allowed_softwall(zone, gfp_mask))
1737                                 continue;
1738                 /*
1739                  * When allocating a page cache page for writing, we
1740                  * want to get it from a zone that is within its dirty
1741                  * limit, such that no single zone holds more than its
1742                  * proportional share of globally allowed dirty pages.
1743                  * The dirty limits take into account the zone's
1744                  * lowmem reserves and high watermark so that kswapd
1745                  * should be able to balance it without having to
1746                  * write pages from its LRU list.
1747                  *
1748                  * This may look like it could increase pressure on
1749                  * lower zones by failing allocations in higher zones
1750                  * before they are full.  But the pages that do spill
1751                  * over are limited as the lower zones are protected
1752                  * by this very same mechanism.  It should not become
1753                  * a practical burden to them.
1754                  *
1755                  * XXX: For now, allow allocations to potentially
1756                  * exceed the per-zone dirty limit in the slowpath
1757                  * (ALLOC_WMARK_LOW unset) before going into reclaim,
1758                  * which is important when on a NUMA setup the allowed
1759                  * zones are together not big enough to reach the
1760                  * global limit.  The proper fix for these situations
1761                  * will require awareness of zones in the
1762                  * dirty-throttling and the flusher threads.
1763                  */
1764                 if ((alloc_flags & ALLOC_WMARK_LOW) &&
1765                     (gfp_mask & __GFP_WRITE) && !zone_dirty_ok(zone))
1766                         goto this_zone_full;
1767
1768                 BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
1769                 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
1770                         unsigned long mark;
1771                         int ret;
1772
1773                         mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
1774                         if (zone_watermark_ok(zone, order, mark,
1775                                     classzone_idx, alloc_flags))
1776                                 goto try_this_zone;
1777
1778                         if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {
1779                                 /*
1780                                  * we do zlc_setup if there are multiple nodes
1781                                  * and before considering the first zone allowed
1782                                  * by the cpuset.
1783                                  */
1784                                 allowednodes = zlc_setup(zonelist, alloc_flags);
1785                                 zlc_active = 1;
1786                                 did_zlc_setup = 1;
1787                         }
1788
1789                         if (zone_reclaim_mode == 0)
1790                                 goto this_zone_full;
1791
1792                         /*
1793                          * As we may have just activated ZLC, check if the first
1794                          * eligible zone has failed zone_reclaim recently.
1795                          */
1796                         if (NUMA_BUILD && zlc_active &&
1797                                 !zlc_zone_worth_trying(zonelist, z, allowednodes))
1798                                 continue;
1799
1800                         ret = zone_reclaim(zone, gfp_mask, order);
1801                         switch (ret) {
1802                         case ZONE_RECLAIM_NOSCAN:
1803                                 /* did not scan */
1804                                 continue;
1805                         case ZONE_RECLAIM_FULL:
1806                                 /* scanned but unreclaimable */
1807                                 continue;
1808                         default:
1809                                 /* did we reclaim enough */
1810                                 if (!zone_watermark_ok(zone, order, mark,
1811                                                 classzone_idx, alloc_flags))
1812                                         goto this_zone_full;
1813                         }
1814                 }
1815
1816 try_this_zone:
1817                 page = buffered_rmqueue(preferred_zone, zone, order,
1818                                                 gfp_mask, migratetype);
1819                 if (page)
1820                         break;
1821 this_zone_full:
1822                 if (NUMA_BUILD)
1823                         zlc_mark_zone_full(zonelist, z);
1824         }
1825
1826         if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
1827                 /* Disable zlc cache for second zonelist scan */
1828                 zlc_active = 0;
1829                 goto zonelist_scan;
1830         }
1831         return page;
1832 }
1833
1834 /*
1835  * Large machines with many possible nodes should not always dump per-node
1836  * meminfo in irq context.
1837  */
1838 static inline bool should_suppress_show_mem(void)
1839 {
1840         bool ret = false;
1841
1842 #if NODES_SHIFT > 8
1843         ret = in_interrupt();
1844 #endif
1845         return ret;
1846 }
1847
1848 static DEFINE_RATELIMIT_STATE(nopage_rs,
1849                 DEFAULT_RATELIMIT_INTERVAL,
1850                 DEFAULT_RATELIMIT_BURST);
1851
1852 void warn_alloc_failed(gfp_t gfp_mask, int order, const char *fmt, ...)
1853 {
1854         unsigned int filter = SHOW_MEM_FILTER_NODES;
1855
1856         if ((gfp_mask & __GFP_NOWARN) || !__ratelimit(&nopage_rs) ||
1857             debug_guardpage_minorder() > 0)
1858                 return;
1859
1860         /*
1861          * This documents exceptions given to allocations in certain
1862          * contexts that are allowed to allocate outside current's set
1863          * of allowed nodes.
1864          */
1865         if (!(gfp_mask & __GFP_NOMEMALLOC))
1866                 if (test_thread_flag(TIF_MEMDIE) ||
1867                     (current->flags & (PF_MEMALLOC | PF_EXITING)))
1868                         filter &= ~SHOW_MEM_FILTER_NODES;
1869         if (in_interrupt() || !(gfp_mask & __GFP_WAIT))
1870                 filter &= ~SHOW_MEM_FILTER_NODES;
1871
1872         if (fmt) {
1873                 struct va_format vaf;
1874                 va_list args;
1875
1876                 va_start(args, fmt);
1877
1878                 vaf.fmt = fmt;
1879                 vaf.va = &args;
1880
1881                 pr_warn("%pV", &vaf);
1882
1883                 va_end(args);
1884         }
1885
1886         pr_warn("%s: page allocation failure: order:%d, mode:0x%x\n",
1887                 current->comm, order, gfp_mask);
1888
1889         dump_stack();
1890         if (!should_suppress_show_mem())
1891                 show_mem(filter);
1892 }
1893
1894 static inline int
1895 should_alloc_retry(gfp_t gfp_mask, unsigned int order,
1896                                 unsigned long did_some_progress,
1897                                 unsigned long pages_reclaimed)
1898 {
1899         /* Do not loop if specifically requested */
1900         if (gfp_mask & __GFP_NORETRY)
1901                 return 0;
1902
1903         /* Always retry if specifically requested */
1904         if (gfp_mask & __GFP_NOFAIL)
1905                 return 1;
1906
1907         /*
1908          * Suspend converts GFP_KERNEL to __GFP_WAIT which can prevent reclaim
1909          * making forward progress without invoking OOM. Suspend also disables
1910          * storage devices so kswapd will not help. Bail if we are suspending.
1911          */
1912         if (!did_some_progress && pm_suspended_storage())
1913                 return 0;
1914
1915         /*
1916          * In this implementation, order <= PAGE_ALLOC_COSTLY_ORDER
1917          * means __GFP_NOFAIL, but that may not be true in other
1918          * implementations.
1919          */
1920         if (order <= PAGE_ALLOC_COSTLY_ORDER)
1921                 return 1;
1922
1923         /*
1924          * For order > PAGE_ALLOC_COSTLY_ORDER, if __GFP_REPEAT is
1925          * specified, then we retry until we no longer reclaim any pages
1926          * (above), or we've reclaimed an order of pages at least as
1927          * large as the allocation's order. In both cases, if the
1928          * allocation still fails, we stop retrying.
1929          */
1930         if (gfp_mask & __GFP_REPEAT && pages_reclaimed < (1 << order))
1931                 return 1;
1932
1933         return 0;
1934 }
1935
1936 static inline struct page *
1937 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
1938         struct zonelist *zonelist, enum zone_type high_zoneidx,
1939         nodemask_t *nodemask, struct zone *preferred_zone,
1940         int migratetype)
1941 {
1942         struct page *page;
1943
1944         /* Acquire the OOM killer lock for the zones in zonelist */
1945         if (!try_set_zonelist_oom(zonelist, gfp_mask)) {
1946                 schedule_timeout_uninterruptible(1);
1947                 return NULL;
1948         }
1949
1950         /*
1951          * Go through the zonelist yet one more time, keep very high watermark
1952          * here, this is only to catch a parallel oom killing, we must fail if
1953          * we're still under heavy pressure.
1954          */
1955         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask,
1956                 order, zonelist, high_zoneidx,
1957                 ALLOC_WMARK_HIGH|ALLOC_CPUSET,
1958                 preferred_zone, migratetype);
1959         if (page)
1960                 goto out;
1961
1962         if (!(gfp_mask & __GFP_NOFAIL)) {
1963                 /* The OOM killer will not help higher order allocs */
1964                 if (order > PAGE_ALLOC_COSTLY_ORDER)
1965                         goto out;
1966                 /* The OOM killer does not needlessly kill tasks for lowmem */
1967                 if (high_zoneidx < ZONE_NORMAL)
1968                         goto out;
1969                 /*
1970                  * GFP_THISNODE contains __GFP_NORETRY and we never hit this.
1971                  * Sanity check for bare calls of __GFP_THISNODE, not real OOM.
1972                  * The caller should handle page allocation failure by itself if
1973                  * it specifies __GFP_THISNODE.
1974                  * Note: Hugepage uses it but will hit PAGE_ALLOC_COSTLY_ORDER.
1975                  */
1976                 if (gfp_mask & __GFP_THISNODE)
1977                         goto out;
1978         }
1979         /* Exhausted what can be done so it's blamo time */
1980         out_of_memory(zonelist, gfp_mask, order, nodemask);
1981
1982 out:
1983         clear_zonelist_oom(zonelist, gfp_mask);
1984         return page;
1985 }
1986
1987 #ifdef CONFIG_COMPACTION
1988 /* Try memory compaction for high-order allocations before reclaim */
1989 static struct page *
1990 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
1991         struct zonelist *zonelist, enum zone_type high_zoneidx,
1992         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
1993         int migratetype, unsigned long *did_some_progress,
1994         bool sync_migration)
1995 {
1996         struct page *page;
1997
1998         if (!order || compaction_deferred(preferred_zone))
1999                 return NULL;
2000
2001         current->flags |= PF_MEMALLOC;
2002         *did_some_progress = try_to_compact_pages(zonelist, order, gfp_mask,
2003                                                 nodemask, sync_migration);
2004         current->flags &= ~PF_MEMALLOC;
2005         if (*did_some_progress != COMPACT_SKIPPED) {
2006
2007                 /* Page migration frees to the PCP lists but we want merging */
2008                 drain_pages(get_cpu());
2009                 put_cpu();
2010
2011                 page = get_page_from_freelist(gfp_mask, nodemask,
2012                                 order, zonelist, high_zoneidx,
2013                                 alloc_flags, preferred_zone,
2014                                 migratetype);
2015                 if (page) {
2016                         preferred_zone->compact_considered = 0;
2017                         preferred_zone->compact_defer_shift = 0;
2018                         count_vm_event(COMPACTSUCCESS);
2019                         return page;
2020                 }
2021
2022                 /*
2023                  * It's bad if compaction run occurs and fails.
2024                  * The most likely reason is that pages exist,
2025                  * but not enough to satisfy watermarks.
2026                  */
2027                 count_vm_event(COMPACTFAIL);
2028                 defer_compaction(preferred_zone);
2029
2030                 cond_resched();
2031         }
2032
2033         return NULL;
2034 }
2035 #else
2036 static inline struct page *
2037 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
2038         struct zonelist *zonelist, enum zone_type high_zoneidx,
2039         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2040         int migratetype, unsigned long *did_some_progress,
2041         bool sync_migration)
2042 {
2043         return NULL;
2044 }
2045 #endif /* CONFIG_COMPACTION */
2046
2047 /* The really slow allocator path where we enter direct reclaim */
2048 static inline struct page *
2049 __alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
2050         struct zonelist *zonelist, enum zone_type high_zoneidx,
2051         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2052         int migratetype, unsigned long *did_some_progress)
2053 {
2054         struct page *page = NULL;
2055         struct reclaim_state reclaim_state;
2056         bool drained = false;
2057
2058         cond_resched();
2059
2060         /* We now go into synchronous reclaim */
2061         cpuset_memory_pressure_bump();
2062         current->flags |= PF_MEMALLOC;
2063         lockdep_set_current_reclaim_state(gfp_mask);
2064         reclaim_state.reclaimed_slab = 0;
2065         current->reclaim_state = &reclaim_state;
2066
2067         *did_some_progress = try_to_free_pages(zonelist, order, gfp_mask, nodemask);
2068
2069         current->reclaim_state = NULL;
2070         lockdep_clear_current_reclaim_state();
2071         current->flags &= ~PF_MEMALLOC;
2072
2073         cond_resched();
2074
2075         if (unlikely(!(*did_some_progress)))
2076                 return NULL;
2077
2078         /* After successful reclaim, reconsider all zones for allocation */
2079         if (NUMA_BUILD)
2080                 zlc_clear_zones_full(zonelist);
2081
2082 retry:
2083         page = get_page_from_freelist(gfp_mask, nodemask, order,
2084                                         zonelist, high_zoneidx,
2085                                         alloc_flags, preferred_zone,
2086                                         migratetype);
2087
2088         /*
2089          * If an allocation failed after direct reclaim, it could be because
2090          * pages are pinned on the per-cpu lists. Drain them and try again
2091          */
2092         if (!page && !drained) {
2093                 drain_all_pages();
2094                 drained = true;
2095                 goto retry;
2096         }
2097
2098         return page;
2099 }
2100
2101 /*
2102  * This is called in the allocator slow-path if the allocation request is of
2103  * sufficient urgency to ignore watermarks and take other desperate measures
2104  */
2105 static inline struct page *
2106 __alloc_pages_high_priority(gfp_t gfp_mask, unsigned int order,
2107         struct zonelist *zonelist, enum zone_type high_zoneidx,
2108         nodemask_t *nodemask, struct zone *preferred_zone,
2109         int migratetype)
2110 {
2111         struct page *page;
2112
2113         do {
2114                 page = get_page_from_freelist(gfp_mask, nodemask, order,
2115                         zonelist, high_zoneidx, ALLOC_NO_WATERMARKS,
2116                         preferred_zone, migratetype);
2117
2118                 if (!page && gfp_mask & __GFP_NOFAIL)
2119                         wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
2120         } while (!page && (gfp_mask & __GFP_NOFAIL));
2121
2122         return page;
2123 }
2124
2125 static inline
2126 void wake_all_kswapd(unsigned int order, struct zonelist *zonelist,
2127                                                 enum zone_type high_zoneidx,
2128                                                 enum zone_type classzone_idx)
2129 {
2130         struct zoneref *z;
2131         struct zone *zone;
2132
2133         for_each_zone_zonelist(zone, z, zonelist, high_zoneidx)
2134                 wakeup_kswapd(zone, order, classzone_idx);
2135 }
2136
2137 static inline int
2138 gfp_to_alloc_flags(gfp_t gfp_mask)
2139 {
2140         int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
2141         const gfp_t wait = gfp_mask & __GFP_WAIT;
2142
2143         /* __GFP_HIGH is assumed to be the same as ALLOC_HIGH to save a branch. */
2144         BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_HIGH);
2145
2146         /*
2147          * The caller may dip into page reserves a bit more if the caller
2148          * cannot run direct reclaim, or if the caller has realtime scheduling
2149          * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
2150          * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
2151          */
2152         alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);
2153
2154         if (!wait) {
2155                 /*
2156                  * Not worth trying to allocate harder for
2157                  * __GFP_NOMEMALLOC even if it can't schedule.
2158                  */
2159                 if  (!(gfp_mask & __GFP_NOMEMALLOC))
2160                         alloc_flags |= ALLOC_HARDER;
2161                 /*
2162                  * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
2163                  * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
2164                  */
2165                 alloc_flags &= ~ALLOC_CPUSET;
2166         } else if (unlikely(rt_task(current)) && !in_interrupt())
2167                 alloc_flags |= ALLOC_HARDER;
2168
2169         if (likely(!(gfp_mask & __GFP_NOMEMALLOC))) {
2170                 if (!in_interrupt() &&
2171                     ((current->flags & PF_MEMALLOC) ||
2172                      unlikely(test_thread_flag(TIF_MEMDIE))))
2173                         alloc_flags |= ALLOC_NO_WATERMARKS;
2174         }
2175
2176         return alloc_flags;
2177 }
2178
2179 static inline struct page *
2180 __alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
2181         struct zonelist *zonelist, enum zone_type high_zoneidx,
2182         nodemask_t *nodemask, struct zone *preferred_zone,
2183         int migratetype)
2184 {
2185         const gfp_t wait = gfp_mask & __GFP_WAIT;
2186         struct page *page = NULL;
2187         int alloc_flags;
2188         unsigned long pages_reclaimed = 0;
2189         unsigned long did_some_progress;
2190         bool sync_migration = false;
2191
2192         /*
2193          * In the slowpath, we sanity check order to avoid ever trying to
2194          * reclaim >= MAX_ORDER areas which will never succeed. Callers may
2195          * be using allocators in order of preference for an area that is
2196          * too large.
2197          */
2198         if (order >= MAX_ORDER) {
2199                 WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
2200                 return NULL;
2201         }
2202
2203         /*
2204          * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
2205          * __GFP_NOWARN set) should not cause reclaim since the subsystem
2206          * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
2207          * using a larger set of nodes after it has established that the
2208          * allowed per node queues are empty and that nodes are
2209          * over allocated.
2210          */
2211         if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
2212                 goto nopage;
2213
2214 restart:
2215         if (!(gfp_mask & __GFP_NO_KSWAPD))
2216                 wake_all_kswapd(order, zonelist, high_zoneidx,
2217                                                 zone_idx(preferred_zone));
2218
2219         /*
2220          * OK, we're below the kswapd watermark and have kicked background
2221          * reclaim. Now things get more complex, so set up alloc_flags according
2222          * to how we want to proceed.
2223          */
2224         alloc_flags = gfp_to_alloc_flags(gfp_mask);
2225
2226         /*
2227          * Find the true preferred zone if the allocation is unconstrained by
2228          * cpusets.
2229          */
2230         if (!(alloc_flags & ALLOC_CPUSET) && !nodemask)
2231                 first_zones_zonelist(zonelist, high_zoneidx, NULL,
2232                                         &preferred_zone);
2233
2234 rebalance:
2235         /* This is the last chance, in general, before the goto nopage. */
2236         page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
2237                         high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
2238                         preferred_zone, migratetype);
2239         if (page)
2240                 goto got_pg;
2241
2242         /* Allocate without watermarks if the context allows */
2243         if (alloc_flags & ALLOC_NO_WATERMARKS) {
2244                 page = __alloc_pages_high_priority(gfp_mask, order,
2245                                 zonelist, high_zoneidx, nodemask,
2246                                 preferred_zone, migratetype);
2247                 if (page)
2248                         goto got_pg;
2249         }
2250
2251         /* Atomic allocations - we can't balance anything */
2252         if (!wait)
2253                 goto nopage;
2254
2255         /* Avoid recursion of direct reclaim */
2256         if (current->flags & PF_MEMALLOC)
2257                 goto nopage;
2258
2259         /* Avoid allocations with no watermarks from looping endlessly */
2260         if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
2261                 goto nopage;
2262
2263         /*
2264          * Try direct compaction. The first pass is asynchronous. Subsequent
2265          * attempts after direct reclaim are synchronous
2266          */
2267         page = __alloc_pages_direct_compact(gfp_mask, order,
2268                                         zonelist, high_zoneidx,
2269                                         nodemask,
2270                                         alloc_flags, preferred_zone,
2271                                         migratetype, &did_some_progress,
2272                                         sync_migration);
2273         if (page)
2274                 goto got_pg;
2275         sync_migration = true;
2276
2277         /* Try direct reclaim and then allocating */
2278         page = __alloc_pages_direct_reclaim(gfp_mask, order,
2279                                         zonelist, high_zoneidx,
2280                                         nodemask,
2281                                         alloc_flags, preferred_zone,
2282                                         migratetype, &did_some_progress);
2283         if (page)
2284                 goto got_pg;
2285
2286         /*
2287          * If we failed to make any progress reclaiming, then we are
2288          * running out of options and have to consider going OOM
2289          */
2290         if (!did_some_progress) {
2291                 if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
2292                         if (oom_killer_disabled)
2293                                 goto nopage;
2294                         page = __alloc_pages_may_oom(gfp_mask, order,
2295                                         zonelist, high_zoneidx,
2296                                         nodemask, preferred_zone,
2297                                         migratetype);
2298                         if (page)
2299                                 goto got_pg;
2300
2301                         if (!(gfp_mask & __GFP_NOFAIL)) {
2302                                 /*
2303                                  * The oom killer is not called for high-order
2304                                  * allocations that may fail, so if no progress
2305                                  * is being made, there are no other options and
2306                                  * retrying is unlikely to help.
2307                                  */
2308                                 if (order > PAGE_ALLOC_COSTLY_ORDER)
2309                                         goto nopage;
2310                                 /*
2311                                  * The oom killer is not called for lowmem
2312                                  * allocations to prevent needlessly killing
2313                                  * innocent tasks.
2314                                  */
2315                                 if (high_zoneidx < ZONE_NORMAL)
2316                                         goto nopage;
2317                         }
2318
2319                         goto restart;
2320                 }
2321         }
2322
2323         /* Check if we should retry the allocation */
2324         pages_reclaimed += did_some_progress;
2325         if (should_alloc_retry(gfp_mask, order, did_some_progress,
2326                                                 pages_reclaimed)) {
2327                 /* Wait for some write requests to complete then retry */
2328                 wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
2329                 goto rebalance;
2330         } else {
2331                 /*
2332                  * High-order allocations do not necessarily loop after
2333                  * direct reclaim and reclaim/compaction depends on compaction
2334                  * being called after reclaim so call directly if necessary
2335                  */
2336                 page = __alloc_pages_direct_compact(gfp_mask, order,
2337                                         zonelist, high_zoneidx,
2338                                         nodemask,
2339                                         alloc_flags, preferred_zone,
2340                                         migratetype, &did_some_progress,
2341                                         sync_migration);
2342                 if (page)
2343                         goto got_pg;
2344         }
2345
2346 nopage:
2347         warn_alloc_failed(gfp_mask, order, NULL);
2348         return page;
2349 got_pg:
2350         if (kmemcheck_enabled)
2351                 kmemcheck_pagealloc_alloc(page, order, gfp_mask);
2352         return page;
2353
2354 }
2355
2356 /*
2357  * This is the 'heart' of the zoned buddy allocator.
2358  */
2359 struct page *
2360 __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
2361                         struct zonelist *zonelist, nodemask_t *nodemask)
2362 {
2363         enum zone_type high_zoneidx = gfp_zone(gfp_mask);
2364         struct zone *preferred_zone;
2365         struct page *page;
2366         int migratetype = allocflags_to_migratetype(gfp_mask);
2367
2368         gfp_mask &= gfp_allowed_mask;
2369
2370         lockdep_trace_alloc(gfp_mask);
2371
2372         might_sleep_if(gfp_mask & __GFP_WAIT);
2373
2374         if (should_fail_alloc_page(gfp_mask, order))
2375                 return NULL;
2376
2377         /*
2378          * Check the zones suitable for the gfp_mask contain at least one
2379          * valid zone. It's possible to have an empty zonelist as a result
2380          * of GFP_THISNODE and a memoryless node
2381          */
2382         if (unlikely(!zonelist->_zonerefs->zone))
2383                 return NULL;
2384
2385         get_mems_allowed();
2386         /* The preferred zone is used for statistics later */
2387         first_zones_zonelist(zonelist, high_zoneidx,
2388                                 nodemask ? : &cpuset_current_mems_allowed,
2389                                 &preferred_zone);
2390         if (!preferred_zone) {
2391                 put_mems_allowed();
2392                 return NULL;
2393         }
2394
2395         /* First allocation attempt */
2396         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
2397                         zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,
2398                         preferred_zone, migratetype);
2399         if (unlikely(!page))
2400                 page = __alloc_pages_slowpath(gfp_mask, order,
2401                                 zonelist, high_zoneidx, nodemask,
2402                                 preferred_zone, migratetype);
2403         put_mems_allowed();
2404
2405         trace_mm_page_alloc(page, order, gfp_mask, migratetype);
2406         return page;
2407 }
2408 EXPORT_SYMBOL(__alloc_pages_nodemask);
2409
2410 /*
2411  * Common helper functions.
2412  */
2413 unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
2414 {
2415         struct page *page;
2416
2417         /*
2418          * __get_free_pages() returns a 32-bit address, which cannot represent
2419          * a highmem page
2420          */
2421         VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
2422
2423         page = alloc_pages(gfp_mask, order);
2424         if (!page)
2425                 return 0;
2426         return (unsigned long) page_address(page);
2427 }
2428 EXPORT_SYMBOL(__get_free_pages);
2429
2430 unsigned long get_zeroed_page(gfp_t gfp_mask)
2431 {
2432         return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
2433 }
2434 EXPORT_SYMBOL(get_zeroed_page);
2435
2436 void __free_pages(struct page *page, unsigned int order)
2437 {
2438         if (put_page_testzero(page)) {
2439                 if (order == 0)
2440                         free_hot_cold_page(page, 0);
2441                 else
2442                         __free_pages_ok(page, order);
2443         }
2444 }
2445
2446 EXPORT_SYMBOL(__free_pages);
2447
2448 void free_pages(unsigned long addr, unsigned int order)
2449 {
2450         if (addr != 0) {
2451                 VM_BUG_ON(!virt_addr_valid((void *)addr));
2452                 __free_pages(virt_to_page((void *)addr), order);
2453         }
2454 }
2455
2456 EXPORT_SYMBOL(free_pages);
2457
2458 static void *make_alloc_exact(unsigned long addr, unsigned order, size_t size)
2459 {
2460         if (addr) {
2461                 unsigned long alloc_end = addr + (PAGE_SIZE << order);
2462                 unsigned long used = addr + PAGE_ALIGN(size);
2463
2464                 split_page(virt_to_page((void *)addr), order);
2465                 while (used < alloc_end) {
2466                         free_page(used);
2467                         used += PAGE_SIZE;
2468                 }
2469         }
2470         return (void *)addr;
2471 }
2472
2473 /**
2474  * alloc_pages_exact - allocate an exact number physically-contiguous pages.
2475  * @size: the number of bytes to allocate
2476  * @gfp_mask: GFP flags for the allocation
2477  *
2478  * This function is similar to alloc_pages(), except that it allocates the
2479  * minimum number of pages to satisfy the request.  alloc_pages() can only
2480  * allocate memory in power-of-two pages.
2481  *
2482  * This function is also limited by MAX_ORDER.
2483  *
2484  * Memory allocated by this function must be released by free_pages_exact().
2485  */
2486 void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
2487 {
2488         unsigned int order = get_order(size);
2489         unsigned long addr;
2490
2491         addr = __get_free_pages(gfp_mask, order);
2492         return make_alloc_exact(addr, order, size);
2493 }
2494 EXPORT_SYMBOL(alloc_pages_exact);
2495
2496 /**
2497  * alloc_pages_exact_nid - allocate an exact number of physically-contiguous
2498  *                         pages on a node.
2499  * @nid: the preferred node ID where memory should be allocated
2500  * @size: the number of bytes to allocate
2501  * @gfp_mask: GFP flags for the allocation
2502  *
2503  * Like alloc_pages_exact(), but try to allocate on node nid first before falling
2504  * back.
2505  * Note this is not alloc_pages_exact_node() which allocates on a specific node,
2506  * but is not exact.
2507  */
2508 void *alloc_pages_exact_nid(int nid, size_t size, gfp_t gfp_mask)
2509 {
2510         unsigned order = get_order(size);
2511         struct page *p = alloc_pages_node(nid, gfp_mask, order);
2512         if (!p)
2513                 return NULL;
2514         return make_alloc_exact((unsigned long)page_address(p), order, size);
2515 }
2516 EXPORT_SYMBOL(alloc_pages_exact_nid);
2517
2518 /**
2519  * free_pages_exact - release memory allocated via alloc_pages_exact()
2520  * @virt: the value returned by alloc_pages_exact.
2521  * @size: size of allocation, same value as passed to alloc_pages_exact().
2522  *
2523  * Release the memory allocated by a previous call to alloc_pages_exact.
2524  */
2525 void free_pages_exact(void *virt, size_t size)
2526 {
2527         unsigned long addr = (unsigned long)virt;
2528         unsigned long end = addr + PAGE_ALIGN(size);
2529
2530         while (addr < end) {
2531                 free_page(addr);
2532                 addr += PAGE_SIZE;
2533         }
2534 }
2535 EXPORT_SYMBOL(free_pages_exact);
2536
2537 static unsigned int nr_free_zone_pages(int offset)
2538 {
2539         struct zoneref *z;
2540         struct zone *zone;
2541
2542         /* Just pick one node, since fallback list is circular */
2543         unsigned int sum = 0;
2544
2545         struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);
2546
2547         for_each_zone_zonelist(zone, z, zonelist, offset) {
2548                 unsigned long size = zone->present_pages;
2549                 unsigned long high = high_wmark_pages(zone);
2550                 if (size > high)
2551                         sum += size - high;
2552         }
2553
2554         return sum;
2555 }
2556
2557 /*
2558  * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
2559  */
2560 unsigned int nr_free_buffer_pages(void)
2561 {
2562         return nr_free_zone_pages(gfp_zone(GFP_USER));
2563 }
2564 EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
2565
2566 /*
2567  * Amount of free RAM allocatable within all zones
2568  */
2569 unsigned int nr_free_pagecache_pages(void)
2570 {
2571         return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
2572 }
2573
2574 static inline void show_node(struct zone *zone)
2575 {
2576         if (NUMA_BUILD)
2577                 printk("Node %d ", zone_to_nid(zone));
2578 }
2579
2580 void si_meminfo(struct sysinfo *val)
2581 {
2582         val->totalram = totalram_pages;
2583         val->sharedram = 0;
2584         val->freeram = global_page_state(NR_FREE_PAGES);
2585         val->bufferram = nr_blockdev_pages();
2586         val->totalhigh = totalhigh_pages;
2587         val->freehigh = nr_free_highpages();
2588         val->mem_unit = PAGE_SIZE;
2589 }
2590
2591 EXPORT_SYMBOL(si_meminfo);
2592
2593 #ifdef CONFIG_NUMA
2594 void si_meminfo_node(struct sysinfo *val, int nid)
2595 {
2596         pg_data_t *pgdat = NODE_DATA(nid);
2597
2598         val->totalram = pgdat->node_present_pages;
2599         val->freeram = node_page_state(nid, NR_FREE_PAGES);
2600 #ifdef CONFIG_HIGHMEM
2601         val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
2602         val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
2603                         NR_FREE_PAGES);
2604 #else
2605         val->totalhigh = 0;
2606         val->freehigh = 0;
2607 #endif
2608         val->mem_unit = PAGE_SIZE;
2609 }
2610 #endif
2611
2612 /*
2613  * Determine whether the node should be displayed or not, depending on whether
2614  * SHOW_MEM_FILTER_NODES was passed to show_free_areas().
2615  */
2616 bool skip_free_areas_node(unsigned int flags, int nid)
2617 {
2618         bool ret = false;
2619
2620         if (!(flags & SHOW_MEM_FILTER_NODES))
2621                 goto out;
2622
2623         get_mems_allowed();
2624         ret = !node_isset(nid, cpuset_current_mems_allowed);
2625         put_mems_allowed();
2626 out:
2627         return ret;
2628 }
2629
2630 #define K(x) ((x) << (PAGE_SHIFT-10))
2631
2632 /*
2633  * Show free area list (used inside shift_scroll-lock stuff)
2634  * We also calculate the percentage fragmentation. We do this by counting the
2635  * memory on each free list with the exception of the first item on the list.
2636  * Suppresses nodes that are not allowed by current's cpuset if
2637  * SHOW_MEM_FILTER_NODES is passed.
2638  */
2639 void show_free_areas(unsigned int filter)
2640 {
2641         int cpu;
2642         struct zone *zone;
2643
2644         for_each_populated_zone(zone) {
2645                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2646                         continue;
2647                 show_node(zone);
2648                 printk("%s per-cpu:\n", zone->name);
2649
2650                 for_each_online_cpu(cpu) {
2651                         struct per_cpu_pageset *pageset;
2652
2653                         pageset = per_cpu_ptr(zone->pageset, cpu);
2654
2655                         printk("CPU %4d: hi:%5d, btch:%4d usd:%4d\n",
2656                                cpu, pageset->pcp.high,
2657                                pageset->pcp.batch, pageset->pcp.count);
2658                 }
2659         }
2660
2661         printk("active_anon:%lu inactive_anon:%lu isolated_anon:%lu\n"
2662                 " active_file:%lu inactive_file:%lu isolated_file:%lu\n"
2663                 " unevictable:%lu"
2664                 " dirty:%lu writeback:%lu unstable:%lu\n"
2665                 " free:%lu slab_reclaimable:%lu slab_unreclaimable:%lu\n"
2666                 " mapped:%lu shmem:%lu pagetables:%lu bounce:%lu\n",
2667                 global_page_state(NR_ACTIVE_ANON),
2668                 global_page_state(NR_INACTIVE_ANON),
2669                 global_page_state(NR_ISOLATED_ANON),
2670                 global_page_state(NR_ACTIVE_FILE),
2671                 global_page_state(NR_INACTIVE_FILE),
2672                 global_page_state(NR_ISOLATED_FILE),
2673                 global_page_state(NR_UNEVICTABLE),
2674                 global_page_state(NR_FILE_DIRTY),
2675                 global_page_state(NR_WRITEBACK),
2676                 global_page_state(NR_UNSTABLE_NFS),
2677                 global_page_state(NR_FREE_PAGES),
2678                 global_page_state(NR_SLAB_RECLAIMABLE),
2679                 global_page_state(NR_SLAB_UNRECLAIMABLE),
2680                 global_page_state(NR_FILE_MAPPED),
2681                 global_page_state(NR_SHMEM),
2682                 global_page_state(NR_PAGETABLE),
2683                 global_page_state(NR_BOUNCE));
2684
2685         for_each_populated_zone(zone) {
2686                 int i;
2687
2688                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2689                         continue;
2690                 show_node(zone);
2691                 printk("%s"
2692                         " free:%lukB"
2693                         " min:%lukB"
2694                         " low:%lukB"
2695                         " high:%lukB"
2696                         " active_anon:%lukB"
2697                         " inactive_anon:%lukB"
2698                         " active_file:%lukB"
2699                         " inactive_file:%lukB"
2700                         " unevictable:%lukB"
2701                         " isolated(anon):%lukB"
2702                         " isolated(file):%lukB"
2703                         " present:%lukB"
2704                         " mlocked:%lukB"
2705                         " dirty:%lukB"
2706                         " writeback:%lukB"
2707                         " mapped:%lukB"
2708                         " shmem:%lukB"
2709                         " slab_reclaimable:%lukB"
2710                         " slab_unreclaimable:%lukB"
2711                         " kernel_stack:%lukB"
2712                         " pagetables:%lukB"
2713                         " unstable:%lukB"
2714                         " bounce:%lukB"
2715                         " writeback_tmp:%lukB"
2716                         " pages_scanned:%lu"
2717                         " all_unreclaimable? %s"
2718                         "\n",
2719                         zone->name,
2720                         K(zone_page_state(zone, NR_FREE_PAGES)),
2721                         K(min_wmark_pages(zone)),
2722                         K(low_wmark_pages(zone)),
2723                         K(high_wmark_pages(zone)),
2724                         K(zone_page_state(zone, NR_ACTIVE_ANON)),
2725                         K(zone_page_state(zone, NR_INACTIVE_ANON)),
2726                         K(zone_page_state(zone, NR_ACTIVE_FILE)),
2727                         K(zone_page_state(zone, NR_INACTIVE_FILE)),
2728                         K(zone_page_state(zone, NR_UNEVICTABLE)),
2729                         K(zone_page_state(zone, NR_ISOLATED_ANON)),
2730                         K(zone_page_state(zone, NR_ISOLATED_FILE)),
2731                         K(zone->present_pages),
2732                         K(zone_page_state(zone, NR_MLOCK)),
2733                         K(zone_page_state(zone, NR_FILE_DIRTY)),
2734                         K(zone_page_state(zone, NR_WRITEBACK)),
2735                         K(zone_page_state(zone, NR_FILE_MAPPED)),
2736                         K(zone_page_state(zone, NR_SHMEM)),
2737                         K(zone_page_state(zone, NR_SLAB_RECLAIMABLE)),
2738                         K(zone_page_state(zone, NR_SLAB_UNRECLAIMABLE)),
2739                         zone_page_state(zone, NR_KERNEL_STACK) *
2740                                 THREAD_SIZE / 1024,
2741                         K(zone_page_state(zone, NR_PAGETABLE)),
2742                         K(zone_page_state(zone, NR_UNSTABLE_NFS)),
2743                         K(zone_page_state(zone, NR_BOUNCE)),
2744                         K(zone_page_state(zone, NR_WRITEBACK_TEMP)),
2745                         zone->pages_scanned,
2746                         (zone->all_unreclaimable ? "yes" : "no")
2747                         );
2748                 printk("lowmem_reserve[]:");
2749                 for (i = 0; i < MAX_NR_ZONES; i++)
2750                         printk(" %lu", zone->lowmem_reserve[i]);
2751                 printk("\n");
2752         }
2753
2754         for_each_populated_zone(zone) {
2755                 unsigned long nr[MAX_ORDER], flags, order, total = 0;
2756
2757                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2758                         continue;
2759                 show_node(zone);
2760                 printk("%s: ", zone->name);
2761
2762                 spin_lock_irqsave(&zone->lock, flags);
2763                 for (order = 0; order < MAX_ORDER; order++) {
2764                         nr[order] = zone->free_area[order].nr_free;
2765                         total += nr[order] << order;
2766                 }
2767                 spin_unlock_irqrestore(&zone->lock, flags);
2768                 for (order = 0; order < MAX_ORDER; order++)
2769                         printk("%lu*%lukB ", nr[order], K(1UL) << order);
2770                 printk("= %lukB\n", K(total));
2771         }
2772
2773         printk("%ld total pagecache pages\n", global_page_state(NR_FILE_PAGES));
2774
2775         show_swap_cache_info();
2776 }
2777
2778 static void zoneref_set_zone(struct zone *zone, struct zoneref *zoneref)
2779 {
2780         zoneref->zone = zone;
2781         zoneref->zone_idx = zone_idx(zone);
2782 }
2783
2784 /*
2785  * Builds allocation fallback zone lists.
2786  *
2787  * Add all populated zones of a node to the zonelist.
2788  */
2789 static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
2790                                 int nr_zones, enum zone_type zone_type)
2791 {
2792         struct zone *zone;
2793
2794         BUG_ON(zone_type >= MAX_NR_ZONES);
2795         zone_type++;
2796
2797         do {
2798                 zone_type--;
2799                 zone = pgdat->node_zones + zone_type;
2800                 if (populated_zone(zone)) {
2801                         zoneref_set_zone(zone,
2802                                 &zonelist->_zonerefs[nr_zones++]);
2803                         check_highest_zone(zone_type);
2804                 }
2805
2806         } while (zone_type);
2807         return nr_zones;
2808 }
2809
2810
2811 /*
2812  *  zonelist_order:
2813  *  0 = automatic detection of better ordering.
2814  *  1 = order by ([node] distance, -zonetype)
2815  *  2 = order by (-zonetype, [node] distance)
2816  *
2817  *  If not NUMA, ZONELIST_ORDER_ZONE and ZONELIST_ORDER_NODE will create
2818  *  the same zonelist. So only NUMA can configure this param.
2819  */
2820 #define ZONELIST_ORDER_DEFAULT  0
2821 #define ZONELIST_ORDER_NODE     1
2822 #define ZONELIST_ORDER_ZONE     2
2823
2824 /* zonelist order in the kernel.
2825  * set_zonelist_order() will set this to NODE or ZONE.
2826  */
2827 static int current_zonelist_order = ZONELIST_ORDER_DEFAULT;
2828 static char zonelist_order_name[3][8] = {"Default", "Node", "Zone"};
2829
2830
2831 #ifdef CONFIG_NUMA
2832 /* The value user specified ....changed by config */
2833 static int user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2834 /* string for sysctl */
2835 #define NUMA_ZONELIST_ORDER_LEN 16
2836 char numa_zonelist_order[16] = "default";
2837
2838 /*
2839  * interface for configure zonelist ordering.
2840  * command line option "numa_zonelist_order"
2841  *      = "[dD]efault   - default, automatic configuration.
2842  *      = "[nN]ode      - order by node locality, then by zone within node
2843  *      = "[zZ]one      - order by zone, then by locality within zone
2844  */
2845
2846 static int __parse_numa_zonelist_order(char *s)
2847 {
2848         if (*s == 'd' || *s == 'D') {
2849                 user_zonelist_order = ZONELIST_ORDER_DEFAULT;
2850         } else if (*s == 'n' || *s == 'N') {
2851                 user_zonelist_order = ZONELIST_ORDER_NODE;
2852         } else if (*s == 'z' || *s == 'Z') {
2853                 user_zonelist_order = ZONELIST_ORDER_ZONE;
2854         } else {
2855                 printk(KERN_WARNING
2856                         "Ignoring invalid numa_zonelist_order value:  "
2857                         "%s\n", s);
2858                 return -EINVAL;
2859         }
2860         return 0;
2861 }
2862
2863 static __init int setup_numa_zonelist_order(char *s)
2864 {
2865         int ret;
2866
2867         if (!s)
2868                 return 0;
2869
2870         ret = __parse_numa_zonelist_order(s);
2871         if (ret == 0)
2872                 strlcpy(numa_zonelist_order, s, NUMA_ZONELIST_ORDER_LEN);
2873
2874         return ret;
2875 }
2876 early_param("numa_zonelist_order", setup_numa_zonelist_order);
2877
2878 /*
2879  * sysctl handler for numa_zonelist_order
2880  */
2881 int numa_zonelist_order_handler(ctl_table *table, int write,
2882                 void __user *buffer, size_t *length,
2883                 loff_t *ppos)
2884 {
2885         char saved_string[NUMA_ZONELIST_ORDER_LEN];
2886         int ret;
2887         static DEFINE_MUTEX(zl_order_mutex);
2888
2889         mutex_lock(&zl_order_mutex);
2890         if (write)
2891                 strcpy(saved_string, (char*)table->data);
2892         ret = proc_dostring(table, write, buffer, length, ppos);
2893         if (ret)
2894                 goto out;
2895         if (write) {
2896                 int oldval = user_zonelist_order;
2897                 if (__parse_numa_zonelist_order((char*)table->data)) {
2898                         /*
2899                          * bogus value.  restore saved string
2900                          */
2901                         strncpy((char*)table->data, saved_string,
2902                                 NUMA_ZONELIST_ORDER_LEN);
2903                         user_zonelist_order = oldval;
2904                 } else if (oldval != user_zonelist_order) {
2905                         mutex_lock(&zonelists_mutex);
2906                         build_all_zonelists(NULL);
2907                         mutex_unlock(&zonelists_mutex);
2908                 }
2909         }
2910 out:
2911         mutex_unlock(&zl_order_mutex);
2912         return ret;
2913 }
2914
2915
2916 #define MAX_NODE_LOAD (nr_online_nodes)
2917 static int node_load[MAX_NUMNODES];
2918
2919 /**
2920  * find_next_best_node - find the next node that should appear in a given node's fallback list
2921  * @node: node whose fallback list we're appending
2922  * @used_node_mask: nodemask_t of already used nodes
2923  *
2924  * We use a number of factors to determine which is the next node that should
2925  * appear on a given node's fallback list.  The node should not have appeared
2926  * already in @node's fallback list, and it should be the next closest node
2927  * according to the distance array (which contains arbitrary distance values
2928  * from each node to each node in the system), and should also prefer nodes
2929  * with no CPUs, since presumably they'll have very little allocation pressure
2930  * on them otherwise.
2931  * It returns -1 if no node is found.
2932  */
2933 static int find_next_best_node(int node, nodemask_t *used_node_mask)
2934 {
2935         int n, val;
2936         int min_val = INT_MAX;
2937         int best_node = -1;
2938         const struct cpumask *tmp = cpumask_of_node(0);
2939
2940         /* Use the local node if we haven't already */
2941         if (!node_isset(node, *used_node_mask)) {
2942                 node_set(node, *used_node_mask);
2943                 return node;
2944         }
2945
2946         for_each_node_state(n, N_HIGH_MEMORY) {
2947
2948                 /* Don't want a node to appear more than once */
2949                 if (node_isset(n, *used_node_mask))
2950                         continue;
2951
2952                 /* Use the distance array to find the distance */
2953                 val = node_distance(node, n);
2954
2955                 /* Penalize nodes under us ("prefer the next node") */
2956                 val += (n < node);
2957
2958                 /* Give preference to headless and unused nodes */
2959                 tmp = cpumask_of_node(n);
2960                 if (!cpumask_empty(tmp))
2961                         val += PENALTY_FOR_NODE_WITH_CPUS;
2962
2963                 /* Slight preference for less loaded node */
2964                 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
2965                 val += node_load[n];
2966
2967                 if (val < min_val) {
2968                         min_val = val;
2969                         best_node = n;
2970                 }
2971         }
2972
2973         if (best_node >= 0)
2974                 node_set(best_node, *used_node_mask);
2975
2976         return best_node;
2977 }
2978
2979
2980 /*
2981  * Build zonelists ordered by node and zones within node.
2982  * This results in maximum locality--normal zone overflows into local
2983  * DMA zone, if any--but risks exhausting DMA zone.
2984  */
2985 static void build_zonelists_in_node_order(pg_data_t *pgdat, int node)
2986 {
2987         int j;
2988         struct zonelist *zonelist;
2989
2990         zonelist = &pgdat->node_zonelists[0];
2991         for (j = 0; zonelist->_zonerefs[j].zone != NULL; j++)
2992                 ;
2993         j = build_zonelists_node(NODE_DATA(node), zonelist, j,
2994                                                         MAX_NR_ZONES - 1);
2995         zonelist->_zonerefs[j].zone = NULL;
2996         zonelist->_zonerefs[j].zone_idx = 0;
2997 }
2998
2999 /*
3000  * Build gfp_thisnode zonelists
3001  */
3002 static void build_thisnode_zonelists(pg_data_t *pgdat)
3003 {
3004         int j;
3005         struct zonelist *zonelist;
3006
3007         zonelist = &pgdat->node_zonelists[1];
3008         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
3009         zonelist->_zonerefs[j].zone = NULL;
3010         zonelist->_zonerefs[j].zone_idx = 0;
3011 }
3012
3013 /*
3014  * Build zonelists ordered by zone and nodes within zones.
3015  * This results in conserving DMA zone[s] until all Normal memory is
3016  * exhausted, but results in overflowing to remote node while memory
3017  * may still exist in local DMA zone.
3018  */
3019 static int node_order[MAX_NUMNODES];
3020
3021 static void build_zonelists_in_zone_order(pg_data_t *pgdat, int nr_nodes)
3022 {
3023         int pos, j, node;
3024         int zone_type;          /* needs to be signed */
3025         struct zone *z;
3026         struct zonelist *zonelist;
3027
3028         zonelist = &pgdat->node_zonelists[0];
3029         pos = 0;
3030         for (zone_type = MAX_NR_ZONES - 1; zone_type >= 0; zone_type--) {
3031                 for (j = 0; j < nr_nodes; j++) {
3032                         node = node_order[j];
3033                         z = &NODE_DATA(node)->node_zones[zone_type];
3034                         if (populated_zone(z)) {
3035                                 zoneref_set_zone(z,
3036                                         &zonelist->_zonerefs[pos++]);
3037                                 check_highest_zone(zone_type);
3038                         }
3039                 }
3040         }
3041         zonelist->_zonerefs[pos].zone = NULL;
3042         zonelist->_zonerefs[pos].zone_idx = 0;
3043 }
3044
3045 static int default_zonelist_order(void)
3046 {
3047         int nid, zone_type;
3048         unsigned long low_kmem_size,total_size;
3049         struct zone *z;
3050         int average_size;
3051         /*
3052          * ZONE_DMA and ZONE_DMA32 can be very small area in the system.
3053          * If they are really small and used heavily, the system can fall
3054          * into OOM very easily.
3055          * This function detect ZONE_DMA/DMA32 size and configures zone order.
3056          */
3057         /* Is there ZONE_NORMAL ? (ex. ppc has only DMA zone..) */
3058         low_kmem_size = 0;
3059         total_size = 0;
3060         for_each_online_node(nid) {
3061                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
3062                         z = &NODE_DATA(nid)->node_zones[zone_type];
3063                         if (populated_zone(z)) {
3064                                 if (zone_type < ZONE_NORMAL)
3065                                         low_kmem_size += z->present_pages;
3066                                 total_size += z->present_pages;
3067                         } else if (zone_type == ZONE_NORMAL) {
3068                                 /*
3069                                  * If any node has only lowmem, then node order
3070                                  * is preferred to allow kernel allocations
3071                                  * locally; otherwise, they can easily infringe
3072                                  * on other nodes when there is an abundance of
3073                                  * lowmem available to allocate from.
3074                                  */
3075                                 return ZONELIST_ORDER_NODE;
3076                         }
3077                 }
3078         }
3079         if (!low_kmem_size ||  /* there are no DMA area. */
3080             low_kmem_size > total_size/2) /* DMA/DMA32 is big. */
3081                 return ZONELIST_ORDER_NODE;
3082         /*
3083          * look into each node's config.
3084          * If there is a node whose DMA/DMA32 memory is very big area on
3085          * local memory, NODE_ORDER may be suitable.
3086          */
3087         average_size = total_size /
3088                                 (nodes_weight(node_states[N_HIGH_MEMORY]) + 1);
3089         for_each_online_node(nid) {
3090                 low_kmem_size = 0;
3091                 total_size = 0;
3092                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
3093                         z = &NODE_DATA(nid)->node_zones[zone_type];
3094                         if (populated_zone(z)) {
3095                                 if (zone_type < ZONE_NORMAL)
3096                                         low_kmem_size += z->present_pages;
3097                                 total_size += z->present_pages;
3098                         }
3099                 }
3100                 if (low_kmem_size &&
3101                     total_size > average_size && /* ignore small node */
3102                     low_kmem_size > total_size * 70/100)
3103                         return ZONELIST_ORDER_NODE;
3104         }
3105         return ZONELIST_ORDER_ZONE;
3106 }
3107
3108 static void set_zonelist_order(void)
3109 {
3110         if (user_zonelist_order == ZONELIST_ORDER_DEFAULT)
3111                 current_zonelist_order = default_zonelist_order();
3112         else
3113                 current_zonelist_order = user_zonelist_order;
3114 }
3115
3116 static void build_zonelists(pg_data_t *pgdat)
3117 {
3118         int j, node, load;
3119         enum zone_type i;
3120         nodemask_t used_mask;
3121         int local_node, prev_node;
3122         struct zonelist *zonelist;
3123         int order = current_zonelist_order;
3124
3125         /* initialize zonelists */
3126         for (i = 0; i < MAX_ZONELISTS; i++) {
3127                 zonelist = pgdat->node_zonelists + i;
3128                 zonelist->_zonerefs[0].zone = NULL;
3129                 zonelist->_zonerefs[0].zone_idx = 0;
3130         }
3131
3132         /* NUMA-aware ordering of nodes */
3133         local_node = pgdat->node_id;
3134         load = nr_online_nodes;
3135         prev_node = local_node;
3136         nodes_clear(used_mask);
3137
3138         memset(node_order, 0, sizeof(node_order));
3139         j = 0;
3140
3141         while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
3142                 int distance = node_distance(local_node, node);
3143
3144                 /*
3145                  * If another node is sufficiently far away then it is better
3146                  * to reclaim pages in a zone before going off node.
3147                  */
3148                 if (distance > RECLAIM_DISTANCE)
3149                         zone_reclaim_mode = 1;
3150
3151                 /*
3152                  * We don't want to pressure a particular node.
3153                  * So adding penalty to the first node in same
3154                  * distance group to make it round-robin.
3155                  */
3156                 if (distance != node_distance(local_node, prev_node))
3157                         node_load[node] = load;
3158
3159                 prev_node = node;
3160                 load--;
3161                 if (order == ZONELIST_ORDER_NODE)
3162                         build_zonelists_in_node_order(pgdat, node);
3163                 else
3164                         node_order[j++] = node; /* remember order */
3165         }
3166
3167         if (order == ZONELIST_ORDER_ZONE) {
3168                 /* calculate node order -- i.e., DMA last! */
3169                 build_zonelists_in_zone_order(pgdat, j);
3170         }
3171
3172         build_thisnode_zonelists(pgdat);
3173 }
3174
3175 /* Construct the zonelist performance cache - see further mmzone.h */
3176 static void build_zonelist_cache(pg_data_t *pgdat)
3177 {
3178         struct zonelist *zonelist;
3179         struct zonelist_cache *zlc;
3180         struct zoneref *z;
3181
3182         zonelist = &pgdat->node_zonelists[0];
3183         zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
3184         bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
3185         for (z = zonelist->_zonerefs; z->zone; z++)
3186                 zlc->z_to_n[z - zonelist->_zonerefs] = zonelist_node_idx(z);
3187 }
3188
3189 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
3190 /*
3191  * Return node id of node used for "local" allocations.
3192  * I.e., first node id of first zone in arg node's generic zonelist.
3193  * Used for initializing percpu 'numa_mem', which is used primarily
3194  * for kernel allocations, so use GFP_KERNEL flags to locate zonelist.
3195  */
3196 int local_memory_node(int node)
3197 {
3198         struct zone *zone;
3199
3200         (void)first_zones_zonelist(node_zonelist(node, GFP_KERNEL),
3201                                    gfp_zone(GFP_KERNEL),
3202                                    NULL,
3203                                    &zone);
3204         return zone->node;
3205 }
3206 #endif
3207
3208 #else   /* CONFIG_NUMA */
3209
3210 static void set_zonelist_order(void)
3211 {
3212         current_zonelist_order = ZONELIST_ORDER_ZONE;
3213 }
3214
3215 static void build_zonelists(pg_data_t *pgdat)
3216 {
3217         int node, local_node;
3218         enum zone_type j;
3219         struct zonelist *zonelist;
3220
3221         local_node = pgdat->node_id;
3222
3223         zonelist = &pgdat->node_zonelists[0];
3224         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
3225
3226         /*
3227          * Now we build the zonelist so that it contains the zones
3228          * of all the other nodes.
3229          * We don't want to pressure a particular node, so when
3230          * building the zones for node N, we make sure that the
3231          * zones coming right after the local ones are those from
3232          * node N+1 (modulo N)
3233          */
3234         for (node = local_node + 1; node < MAX_NUMNODES; node++) {
3235                 if (!node_online(node))
3236                         continue;
3237                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3238                                                         MAX_NR_ZONES - 1);
3239         }
3240         for (node = 0; node < local_node; node++) {
3241                 if (!node_online(node))
3242                         continue;
3243                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3244                                                         MAX_NR_ZONES - 1);
3245         }
3246
3247         zonelist->_zonerefs[j].zone = NULL;
3248         zonelist->_zonerefs[j].zone_idx = 0;
3249 }
3250
3251 /* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
3252 static void build_zonelist_cache(pg_data_t *pgdat)
3253 {
3254         pgdat->node_zonelists[0].zlcache_ptr = NULL;
3255 }
3256
3257 #endif  /* CONFIG_NUMA */
3258
3259 /*
3260  * Boot pageset table. One per cpu which is going to be used for all
3261  * zones and all nodes. The parameters will be set in such a way
3262  * that an item put on a list will immediately be handed over to
3263  * the buddy list. This is safe since pageset manipulation is done
3264  * with interrupts disabled.
3265  *
3266  * The boot_pagesets must be kept even after bootup is complete for
3267  * unused processors and/or zones. They do play a role for bootstrapping
3268  * hotplugged processors.
3269  *
3270  * zoneinfo_show() and maybe other functions do
3271  * not check if the processor is online before following the pageset pointer.
3272  * Other parts of the kernel may not check if the zone is available.
3273  */
3274 static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch);
3275 static DEFINE_PER_CPU(struct per_cpu_pageset, boot_pageset);
3276 static void setup_zone_pageset(struct zone *zone);
3277
3278 /*
3279  * Global mutex to protect against size modification of zonelists
3280  * as well as to serialize pageset setup for the new populated zone.
3281  */
3282 DEFINE_MUTEX(zonelists_mutex);
3283
3284 /* return values int ....just for stop_machine() */
3285 static __init_refok int __build_all_zonelists(void *data)
3286 {
3287         int nid;
3288         int cpu;
3289
3290 #ifdef CONFIG_NUMA
3291         memset(node_load, 0, sizeof(node_load));
3292 #endif
3293         for_each_online_node(nid) {
3294                 pg_data_t *pgdat = NODE_DATA(nid);
3295
3296                 build_zonelists(pgdat);
3297                 build_zonelist_cache(pgdat);
3298         }
3299
3300         /*
3301          * Initialize the boot_pagesets that are going to be used
3302          * for bootstrapping processors. The real pagesets for
3303          * each zone will be allocated later when the per cpu
3304          * allocator is available.
3305          *
3306          * boot_pagesets are used also for bootstrapping offline
3307          * cpus if the system is already booted because the pagesets
3308          * are needed to initialize allocators on a specific cpu too.
3309          * F.e. the percpu allocator needs the page allocator which
3310          * needs the percpu allocator in order to allocate its pagesets
3311          * (a chicken-egg dilemma).
3312          */
3313         for_each_possible_cpu(cpu) {
3314                 setup_pageset(&per_cpu(boot_pageset, cpu), 0);
3315
3316 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
3317                 /*
3318                  * We now know the "local memory node" for each node--
3319                  * i.e., the node of the first zone in the generic zonelist.
3320                  * Set up numa_mem percpu variable for on-line cpus.  During
3321                  * boot, only the boot cpu should be on-line;  we'll init the
3322                  * secondary cpus' numa_mem as they come on-line.  During
3323                  * node/memory hotplug, we'll fixup all on-line cpus.
3324                  */
3325                 if (cpu_online(cpu))
3326                         set_cpu_numa_mem(cpu, local_memory_node(cpu_to_node(cpu)));
3327 #endif
3328         }
3329
3330         return 0;
3331 }
3332
3333 /*
3334  * Called with zonelists_mutex held always
3335  * unless system_state == SYSTEM_BOOTING.
3336  */
3337 void __ref build_all_zonelists(void *data)
3338 {
3339         set_zonelist_order();
3340
3341         if (system_state == SYSTEM_BOOTING) {
3342                 __build_all_zonelists(NULL);
3343                 mminit_verify_zonelist();
3344                 cpuset_init_current_mems_allowed();
3345         } else {
3346                 /* we have to stop all cpus to guarantee there is no user
3347                    of zonelist */
3348 #ifdef CONFIG_MEMORY_HOTPLUG
3349                 if (data)
3350                         setup_zone_pageset((struct zone *)data);
3351 #endif
3352                 stop_machine(__build_all_zonelists, NULL, NULL);
3353                 /* cpuset refresh routine should be here */
3354         }
3355         vm_total_pages = nr_free_pagecache_pages();
3356         /*
3357          * Disable grouping by mobility if the number of pages in the
3358          * system is too low to allow the mechanism to work. It would be
3359          * more accurate, but expensive to check per-zone. This check is
3360          * made on memory-hotadd so a system can start with mobility
3361          * disabled and enable it later
3362          */
3363         if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
3364                 page_group_by_mobility_disabled = 1;
3365         else
3366                 page_group_by_mobility_disabled = 0;
3367
3368         printk("Built %i zonelists in %s order, mobility grouping %s.  "
3369                 "Total pages: %ld\n",
3370                         nr_online_nodes,
3371                         zonelist_order_name[current_zonelist_order],
3372                         page_group_by_mobility_disabled ? "off" : "on",
3373                         vm_total_pages);
3374 #ifdef CONFIG_NUMA
3375         printk("Policy zone: %s\n", zone_names[policy_zone]);
3376 #endif
3377 }
3378
3379 /*
3380  * Helper functions to size the waitqueue hash table.
3381  * Essentially these want to choose hash table sizes sufficiently
3382  * large so that collisions trying to wait on pages are rare.
3383  * But in fact, the number of active page waitqueues on typical
3384  * systems is ridiculously low, less than 200. So this is even
3385  * conservative, even though it seems large.
3386  *
3387  * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
3388  * waitqueues, i.e. the size of the waitq table given the number of pages.
3389  */
3390 #define PAGES_PER_WAITQUEUE     256
3391
3392 #ifndef CONFIG_MEMORY_HOTPLUG
3393 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
3394 {
3395         unsigned long size = 1;
3396
3397         pages /= PAGES_PER_WAITQUEUE;
3398
3399         while (size < pages)
3400                 size <<= 1;
3401
3402         /*
3403          * Once we have dozens or even hundreds of threads sleeping
3404          * on IO we've got bigger problems than wait queue collision.
3405          * Limit the size of the wait table to a reasonable size.
3406          */
3407         size = min(size, 4096UL);
3408
3409         return max(size, 4UL);
3410 }
3411 #else
3412 /*
3413  * A zone's size might be changed by hot-add, so it is not possible to determine
3414  * a suitable size for its wait_table.  So we use the maximum size now.
3415  *
3416  * The max wait table size = 4096 x sizeof(wait_queue_head_t).   ie:
3417  *
3418  *    i386 (preemption config)    : 4096 x 16 = 64Kbyte.
3419  *    ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
3420  *    ia64, x86-64 (preemption)   : 4096 x 24 = 96Kbyte.
3421  *
3422  * The maximum entries are prepared when a zone's memory is (512K + 256) pages
3423  * or more by the traditional way. (See above).  It equals:
3424  *
3425  *    i386, x86-64, powerpc(4K page size) : =  ( 2G + 1M)byte.
3426  *    ia64(16K page size)                 : =  ( 8G + 4M)byte.
3427  *    powerpc (64K page size)             : =  (32G +16M)byte.
3428  */
3429 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
3430 {
3431         return 4096UL;
3432 }
3433 #endif
3434
3435 /*
3436  * This is an integer logarithm so that shifts can be used later
3437  * to extract the more random high bits from the multiplicative
3438  * hash function before the remainder is taken.
3439  */
3440 static inline unsigned long wait_table_bits(unsigned long size)
3441 {
3442         return ffz(~size);
3443 }
3444
3445 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
3446
3447 /*
3448  * Check if a pageblock contains reserved pages
3449  */
3450 static int pageblock_is_reserved(unsigned long start_pfn, unsigned long end_pfn)
3451 {
3452         unsigned long pfn;
3453
3454         for (pfn = start_pfn; pfn < end_pfn; pfn++) {
3455                 if (!pfn_valid_within(pfn) || PageReserved(pfn_to_page(pfn)))
3456                         return 1;
3457         }
3458         return 0;
3459 }
3460
3461 /*
3462  * Mark a number of pageblocks as MIGRATE_RESERVE. The number
3463  * of blocks reserved is based on min_wmark_pages(zone). The memory within
3464  * the reserve will tend to store contiguous free pages. Setting min_free_kbytes
3465  * higher will lead to a bigger reserve which will get freed as contiguous
3466  * blocks as reclaim kicks in
3467  */
3468 static void setup_zone_migrate_reserve(struct zone *zone)
3469 {
3470         unsigned long start_pfn, pfn, end_pfn, block_end_pfn;
3471         struct page *page;
3472         unsigned long block_migratetype;
3473         int reserve;
3474
3475         /*
3476          * Get the start pfn, end pfn and the number of blocks to reserve
3477          * We have to be careful to be aligned to pageblock_nr_pages to
3478          * make sure that we always check pfn_valid for the first page in
3479          * the block.
3480          */
3481         start_pfn = zone->zone_start_pfn;
3482         end_pfn = start_pfn + zone->spanned_pages;
3483         start_pfn = roundup(start_pfn, pageblock_nr_pages);
3484         reserve = roundup(min_wmark_pages(zone), pageblock_nr_pages) >>
3485                                                         pageblock_order;
3486
3487         /*
3488          * Reserve blocks are generally in place to help high-order atomic
3489          * allocations that are short-lived. A min_free_kbytes value that
3490          * would result in more than 2 reserve blocks for atomic allocations
3491          * is assumed to be in place to help anti-fragmentation for the
3492          * future allocation of hugepages at runtime.
3493          */
3494         reserve = min(2, reserve);
3495
3496         for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
3497                 if (!pfn_valid(pfn))
3498                         continue;
3499                 page = pfn_to_page(pfn);
3500
3501                 /* Watch out for overlapping nodes */
3502                 if (page_to_nid(page) != zone_to_nid(zone))
3503                         continue;
3504
3505                 block_migratetype = get_pageblock_migratetype(page);
3506
3507                 /* Only test what is necessary when the reserves are not met */
3508                 if (reserve > 0) {
3509                         /*
3510                          * Blocks with reserved pages will never free, skip
3511                          * them.
3512                          */
3513                         block_end_pfn = min(pfn + pageblock_nr_pages, end_pfn);
3514                         if (pageblock_is_reserved(pfn, block_end_pfn))
3515                                 continue;
3516
3517                         /* If this block is reserved, account for it */
3518                         if (block_migratetype == MIGRATE_RESERVE) {
3519                                 reserve--;
3520                                 continue;
3521                         }
3522
3523                         /* Suitable for reserving if this block is movable */
3524                         if (block_migratetype == MIGRATE_MOVABLE) {
3525                                 set_pageblock_migratetype(page,
3526                                                         MIGRATE_RESERVE);
3527                                 move_freepages_block(zone, page,
3528                                                         MIGRATE_RESERVE);
3529                                 reserve--;
3530                                 continue;
3531                         }
3532                 }
3533
3534                 /*
3535                  * If the reserve is met and this is a previous reserved block,
3536                  * take it back
3537                  */
3538                 if (block_migratetype == MIGRATE_RESERVE) {
3539                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
3540                         move_freepages_block(zone, page, MIGRATE_MOVABLE);
3541                 }
3542         }
3543 }
3544
3545 /*
3546  * Initially all pages are reserved - free ones are freed
3547  * up by free_all_bootmem() once the early boot process is
3548  * done. Non-atomic initialization, single-pass.
3549  */
3550 void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
3551                 unsigned long start_pfn, enum memmap_context context)
3552 {
3553         struct page *page;
3554         unsigned long end_pfn = start_pfn + size;
3555         unsigned long pfn;
3556         struct zone *z;
3557
3558         if (highest_memmap_pfn < end_pfn - 1)
3559                 highest_memmap_pfn = end_pfn - 1;
3560
3561         z = &NODE_DATA(nid)->node_zones[zone];
3562         for (pfn = start_pfn; pfn < end_pfn; pfn++) {
3563                 /*
3564                  * There can be holes in boot-time mem_map[]s
3565                  * handed to this function.  They do not
3566                  * exist on hotplugged memory.
3567                  */
3568                 if (context == MEMMAP_EARLY) {
3569                         if (!early_pfn_valid(pfn))
3570                                 continue;
3571                         if (!early_pfn_in_nid(pfn, nid))
3572                                 continue;
3573                 }
3574                 page = pfn_to_page(pfn);
3575                 set_page_links(page, zone, nid, pfn);
3576                 mminit_verify_page_links(page, zone, nid, pfn);
3577                 init_page_count(page);
3578                 reset_page_mapcount(page);
3579                 SetPageReserved(page);
3580                 /*
3581                  * Mark the block movable so that blocks are reserved for
3582                  * movable at startup. This will force kernel allocations
3583                  * to reserve their blocks rather than leaking throughout
3584                  * the address space during boot when many long-lived
3585                  * kernel allocations are made. Later some blocks near
3586                  * the start are marked MIGRATE_RESERVE by
3587                  * setup_zone_migrate_reserve()
3588                  *
3589                  * bitmap is created for zone's valid pfn range. but memmap
3590                  * can be created for invalid pages (for alignment)
3591                  * check here not to call set_pageblock_migratetype() against
3592                  * pfn out of zone.
3593                  */
3594                 if ((z->zone_start_pfn <= pfn)
3595                     && (pfn < z->zone_start_pfn + z->spanned_pages)
3596                     && !(pfn & (pageblock_nr_pages - 1)))
3597                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
3598
3599                 INIT_LIST_HEAD(&page->lru);
3600 #ifdef WANT_PAGE_VIRTUAL
3601                 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
3602                 if (!is_highmem_idx(zone))
3603                         set_page_address(page, __va(pfn << PAGE_SHIFT));
3604 #endif
3605         }
3606 }
3607
3608 static void __meminit zone_init_free_lists(struct zone *zone)
3609 {
3610         int order, t;
3611         for_each_migratetype_order(order, t) {
3612                 INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);
3613                 zone->free_area[order].nr_free = 0;
3614         }
3615 }
3616
3617 #ifndef __HAVE_ARCH_MEMMAP_INIT
3618 #define memmap_init(size, nid, zone, start_pfn) \
3619         memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY)
3620 #endif
3621
3622 static int zone_batchsize(struct zone *zone)
3623 {
3624 #ifdef CONFIG_MMU
3625         int batch;
3626
3627         /*
3628          * The per-cpu-pages pools are set to around 1000th of the
3629          * size of the zone.  But no more than 1/2 of a meg.
3630          *
3631          * OK, so we don't know how big the cache is.  So guess.
3632          */
3633         batch = zone->present_pages / 1024;
3634         if (batch * PAGE_SIZE > 512 * 1024)
3635                 batch = (512 * 1024) / PAGE_SIZE;
3636         batch /= 4;             /* We effectively *= 4 below */
3637         if (batch < 1)
3638                 batch = 1;
3639
3640         /*
3641          * Clamp the batch to a 2^n - 1 value. Having a power
3642          * of 2 value was found to be more likely to have
3643          * suboptimal cache aliasing properties in some cases.
3644          *
3645          * For example if 2 tasks are alternately allocating
3646          * batches of pages, one task can end up with a lot
3647          * of pages of one half of the possible page colors
3648          * and the other with pages of the other colors.
3649          */
3650         batch = rounddown_pow_of_two(batch + batch/2) - 1;
3651
3652         return batch;
3653
3654 #else
3655         /* The deferral and batching of frees should be suppressed under NOMMU
3656          * conditions.
3657          *
3658          * The problem is that NOMMU needs to be able to allocate large chunks
3659          * of contiguous memory as there's no hardware page translation to
3660          * assemble apparent contiguous memory from discontiguous pages.
3661          *
3662          * Queueing large contiguous runs of pages for batching, however,
3663          * causes the pages to actually be freed in smaller chunks.  As there
3664          * can be a significant delay between the individual batches being
3665          * recycled, this leads to the once large chunks of space being
3666          * fragmented and becoming unavailable for high-order allocations.
3667          */
3668         return 0;
3669 #endif
3670 }
3671
3672 static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
3673 {
3674         struct per_cpu_pages *pcp;
3675         int migratetype;
3676
3677         memset(p, 0, sizeof(*p));
3678
3679         pcp = &p->pcp;
3680         pcp->count = 0;
3681         pcp->high = 6 * batch;
3682         pcp->batch = max(1UL, 1 * batch);
3683         for (migratetype = 0; migratetype < MIGRATE_PCPTYPES; migratetype++)
3684                 INIT_LIST_HEAD(&pcp->lists[migratetype]);
3685 }
3686
3687 /*
3688  * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
3689  * to the value high for the pageset p.
3690  */
3691
3692 static void setup_pagelist_highmark(struct per_cpu_pageset *p,
3693                                 unsigned long high)
3694 {
3695         struct per_cpu_pages *pcp;
3696
3697         pcp = &p->pcp;
3698         pcp->high = high;
3699         pcp->batch = max(1UL, high/4);
3700         if ((high/4) > (PAGE_SHIFT * 8))
3701                 pcp->batch = PAGE_SHIFT * 8;
3702 }
3703
3704 static void setup_zone_pageset(struct zone *zone)
3705 {
3706         int cpu;
3707
3708         zone->pageset = alloc_percpu(struct per_cpu_pageset);
3709
3710         for_each_possible_cpu(cpu) {
3711                 struct per_cpu_pageset *pcp = per_cpu_ptr(zone->pageset, cpu);
3712
3713                 setup_pageset(pcp, zone_batchsize(zone));
3714
3715                 if (percpu_pagelist_fraction)
3716                         setup_pagelist_highmark(pcp,
3717                                 (zone->present_pages /
3718                                         percpu_pagelist_fraction));
3719         }
3720 }
3721
3722 /*
3723  * Allocate per cpu pagesets and initialize them.
3724  * Before this call only boot pagesets were available.
3725  */
3726 void __init setup_per_cpu_pageset(void)
3727 {
3728         struct zone *zone;
3729
3730         for_each_populated_zone(zone)
3731                 setup_zone_pageset(zone);
3732 }
3733
3734 static noinline __init_refok
3735 int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
3736 {
3737         int i;
3738         struct pglist_data *pgdat = zone->zone_pgdat;
3739         size_t alloc_size;
3740
3741         /*
3742          * The per-page waitqueue mechanism uses hashed waitqueues
3743          * per zone.
3744          */
3745         zone->wait_table_hash_nr_entries =
3746                  wait_table_hash_nr_entries(zone_size_pages);
3747         zone->wait_table_bits =
3748                 wait_table_bits(zone->wait_table_hash_nr_entries);
3749         alloc_size = zone->wait_table_hash_nr_entries
3750                                         * sizeof(wait_queue_head_t);
3751
3752         if (!slab_is_available()) {
3753                 zone->wait_table = (wait_queue_head_t *)
3754                         alloc_bootmem_node_nopanic(pgdat, alloc_size);
3755         } else {
3756                 /*
3757                  * This case means that a zone whose size was 0 gets new memory
3758                  * via memory hot-add.
3759                  * But it may be the case that a new node was hot-added.  In
3760                  * this case vmalloc() will not be able to use this new node's
3761                  * memory - this wait_table must be initialized to use this new
3762                  * node itself as well.
3763                  * To use this new node's memory, further consideration will be
3764                  * necessary.
3765                  */
3766                 zone->wait_table = vmalloc(alloc_size);
3767         }
3768         if (!zone->wait_table)
3769                 return -ENOMEM;
3770
3771         for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
3772                 init_waitqueue_head(zone->wait_table + i);
3773
3774         return 0;
3775 }
3776
3777 static int __zone_pcp_update(void *data)
3778 {
3779         struct zone *zone = data;
3780         int cpu;
3781         unsigned long batch = zone_batchsize(zone), flags;
3782
3783         for_each_possible_cpu(cpu) {
3784                 struct per_cpu_pageset *pset;
3785                 struct per_cpu_pages *pcp;
3786
3787                 pset = per_cpu_ptr(zone->pageset, cpu);
3788                 pcp = &pset->pcp;
3789
3790                 local_irq_save(flags);
3791                 free_pcppages_bulk(zone, pcp->count, pcp);
3792                 setup_pageset(pset, batch);
3793                 local_irq_restore(flags);
3794         }
3795         return 0;
3796 }
3797
3798 void zone_pcp_update(struct zone *zone)
3799 {
3800         stop_machine(__zone_pcp_update, zone, NULL);
3801 }
3802
3803 static __meminit void zone_pcp_init(struct zone *zone)
3804 {
3805         /*
3806          * per cpu subsystem is not up at this point. The following code
3807          * relies on the ability of the linker to provide the
3808          * offset of a (static) per cpu variable into the per cpu area.
3809          */
3810         zone->pageset = &boot_pageset;
3811
3812         if (zone->present_pages)
3813                 printk(KERN_DEBUG "  %s zone: %lu pages, LIFO batch:%u\n",
3814                         zone->name, zone->present_pages,
3815                                          zone_batchsize(zone));
3816 }
3817
3818 __meminit int init_currently_empty_zone(struct zone *zone,
3819                                         unsigned long zone_start_pfn,
3820                                         unsigned long size,
3821                                         enum memmap_context context)
3822 {
3823         struct pglist_data *pgdat = zone->zone_pgdat;
3824         int ret;
3825         ret = zone_wait_table_init(zone, size);
3826         if (ret)
3827                 return ret;
3828         pgdat->nr_zones = zone_idx(zone) + 1;
3829
3830         zone->zone_start_pfn = zone_start_pfn;
3831
3832         mminit_dprintk(MMINIT_TRACE, "memmap_init",
3833                         "Initialising map node %d zone %lu pfns %lu -> %lu\n",
3834                         pgdat->node_id,
3835                         (unsigned long)zone_idx(zone),
3836                         zone_start_pfn, (zone_start_pfn + size));
3837
3838         zone_init_free_lists(zone);
3839
3840         return 0;
3841 }
3842
3843 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
3844 #ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
3845 /*
3846  * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
3847  * Architectures may implement their own version but if add_active_range()
3848  * was used and there are no special requirements, this is a convenient
3849  * alternative
3850  */
3851 int __meminit __early_pfn_to_nid(unsigned long pfn)
3852 {
3853         unsigned long start_pfn, end_pfn;
3854         int i, nid;
3855
3856         for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid)
3857                 if (start_pfn <= pfn && pfn < end_pfn)
3858                         return nid;
3859         /* This is a memory hole */
3860         return -1;
3861 }
3862 #endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
3863
3864 int __meminit early_pfn_to_nid(unsigned long pfn)
3865 {
3866         int nid;
3867
3868         nid = __early_pfn_to_nid(pfn);
3869         if (nid >= 0)
3870                 return nid;
3871         /* just returns 0 */
3872         return 0;
3873 }
3874
3875 #ifdef CONFIG_NODES_SPAN_OTHER_NODES
3876 bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
3877 {
3878         int nid;
3879
3880         nid = __early_pfn_to_nid(pfn);
3881         if (nid >= 0 && nid != node)
3882                 return false;
3883         return true;
3884 }
3885 #endif
3886
3887 /**
3888  * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
3889  * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
3890  * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
3891  *
3892  * If an architecture guarantees that all ranges registered with
3893  * add_active_ranges() contain no holes and may be freed, this
3894  * this function may be used instead of calling free_bootmem() manually.
3895  */
3896 void __init free_bootmem_with_active_regions(int nid, unsigned long max_low_pfn)
3897 {
3898         unsigned long start_pfn, end_pfn;
3899         int i, this_nid;
3900
3901         for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, &this_nid) {
3902                 start_pfn = min(start_pfn, max_low_pfn);
3903                 end_pfn = min(end_pfn, max_low_pfn);
3904
3905                 if (start_pfn < end_pfn)
3906                         free_bootmem_node(NODE_DATA(this_nid),
3907                                           PFN_PHYS(start_pfn),
3908                                           (end_pfn - start_pfn) << PAGE_SHIFT);
3909         }
3910 }
3911
3912 int __init add_from_early_node_map(struct range *range, int az,
3913                                    int nr_range, int nid)
3914 {
3915         unsigned long start_pfn, end_pfn;
3916         int i;
3917
3918         /* need to go over early_node_map to find out good range for node */
3919         for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, NULL)
3920                 nr_range = add_range(range, az, nr_range, start_pfn, end_pfn);
3921         return nr_range;
3922 }
3923
3924 /**
3925  * sparse_memory_present_with_active_regions - Call memory_present for each active range
3926  * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
3927  *
3928  * If an architecture guarantees that all ranges registered with
3929  * add_active_ranges() contain no holes and may be freed, this
3930  * function may be used instead of calling memory_present() manually.
3931  */
3932 void __init sparse_memory_present_with_active_regions(int nid)
3933 {
3934         unsigned long start_pfn, end_pfn;
3935         int i, this_nid;
3936
3937         for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, &this_nid)
3938                 memory_present(this_nid, start_pfn, end_pfn);
3939 }
3940
3941 /**
3942  * get_pfn_range_for_nid - Return the start and end page frames for a node
3943  * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
3944  * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
3945  * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
3946  *
3947  * It returns the start and end page frame of a node based on information
3948  * provided by an arch calling add_active_range(). If called for a node
3949  * with no available memory, a warning is printed and the start and end
3950  * PFNs will be 0.
3951  */
3952 void __meminit get_pfn_range_for_nid(unsigned int nid,
3953                         unsigned long *start_pfn, unsigned long *end_pfn)
3954 {
3955         unsigned long this_start_pfn, this_end_pfn;
3956         int i;
3957
3958         *start_pfn = -1UL;
3959         *end_pfn = 0;
3960
3961         for_each_mem_pfn_range(i, nid, &this_start_pfn, &this_end_pfn, NULL) {
3962                 *start_pfn = min(*start_pfn, this_start_pfn);
3963                 *end_pfn = max(*end_pfn, this_end_pfn);
3964         }
3965
3966         if (*start_pfn == -1UL)
3967                 *start_pfn = 0;
3968 }
3969
3970 /*
3971  * This finds a zone that can be used for ZONE_MOVABLE pages. The
3972  * assumption is made that zones within a node are ordered in monotonic
3973  * increasing memory addresses so that the "highest" populated zone is used
3974  */
3975 static void __init find_usable_zone_for_movable(void)
3976 {
3977         int zone_index;
3978         for (zone_index = MAX_NR_ZONES - 1; zone_index >= 0; zone_index--) {
3979                 if (zone_index == ZONE_MOVABLE)
3980                         continue;
3981
3982                 if (arch_zone_highest_possible_pfn[zone_index] >
3983                                 arch_zone_lowest_possible_pfn[zone_index])
3984                         break;
3985         }
3986
3987         VM_BUG_ON(zone_index == -1);
3988         movable_zone = zone_index;
3989 }
3990
3991 /*
3992  * The zone ranges provided by the architecture do not include ZONE_MOVABLE
3993  * because it is sized independent of architecture. Unlike the other zones,
3994  * the starting point for ZONE_MOVABLE is not fixed. It may be different
3995  * in each node depending on the size of each node and how evenly kernelcore
3996  * is distributed. This helper function adjusts the zone ranges
3997  * provided by the architecture for a given node by using the end of the
3998  * highest usable zone for ZONE_MOVABLE. This preserves the assumption that
3999  * zones within a node are in order of monotonic increases memory addresses
4000  */
4001 static void __meminit adjust_zone_range_for_zone_movable(int nid,
4002                                         unsigned long zone_type,
4003                                         unsigned long node_start_pfn,
4004                                         unsigned long node_end_pfn,
4005                                         unsigned long *zone_start_pfn,
4006                                         unsigned long *zone_end_pfn)
4007 {
4008         /* Only adjust if ZONE_MOVABLE is on this node */
4009         if (zone_movable_pfn[nid]) {
4010                 /* Size ZONE_MOVABLE */
4011                 if (zone_type == ZONE_MOVABLE) {
4012                         *zone_start_pfn = zone_movable_pfn[nid];
4013                         *zone_end_pfn = min(node_end_pfn,
4014                                 arch_zone_highest_possible_pfn[movable_zone]);
4015
4016                 /* Adjust for ZONE_MOVABLE starting within this range */
4017                 } else if (*zone_start_pfn < zone_movable_pfn[nid] &&
4018                                 *zone_end_pfn > zone_movable_pfn[nid]) {
4019                         *zone_end_pfn = zone_movable_pfn[nid];
4020
4021                 /* Check if this whole range is within ZONE_MOVABLE */
4022                 } else if (*zone_start_pfn >= zone_movable_pfn[nid])
4023                         *zone_start_pfn = *zone_end_pfn;
4024         }
4025 }
4026
4027 /*
4028  * Return the number of pages a zone spans in a node, including holes
4029  * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
4030  */
4031 static unsigned long __meminit zone_spanned_pages_in_node(int nid,
4032                                         unsigned long zone_type,
4033                                         unsigned long *ignored)
4034 {
4035         unsigned long node_start_pfn, node_end_pfn;
4036         unsigned long zone_start_pfn, zone_end_pfn;
4037
4038         /* Get the start and end of the node and zone */
4039         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
4040         zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
4041         zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
4042         adjust_zone_range_for_zone_movable(nid, zone_type,
4043                                 node_start_pfn, node_end_pfn,
4044                                 &zone_start_pfn, &zone_end_pfn);
4045
4046         /* Check that this node has pages within the zone's required range */
4047         if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
4048                 return 0;
4049
4050         /* Move the zone boundaries inside the node if necessary */
4051         zone_end_pfn = min(zone_end_pfn, node_end_pfn);
4052         zone_start_pfn = max(zone_start_pfn, node_start_pfn);
4053
4054         /* Return the spanned pages */
4055         return zone_end_pfn - zone_start_pfn;
4056 }
4057
4058 /*
4059  * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
4060  * then all holes in the requested range will be accounted for.
4061  */
4062 unsigned long __meminit __absent_pages_in_range(int nid,
4063                                 unsigned long range_start_pfn,
4064                                 unsigned long range_end_pfn)
4065 {
4066         unsigned long nr_absent = range_end_pfn - range_start_pfn;
4067         unsigned long start_pfn, end_pfn;
4068         int i;
4069
4070         for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, NULL) {
4071                 start_pfn = clamp(start_pfn, range_start_pfn, range_end_pfn);
4072                 end_pfn = clamp(end_pfn, range_start_pfn, range_end_pfn);
4073                 nr_absent -= end_pfn - start_pfn;
4074         }
4075         return nr_absent;
4076 }
4077
4078 /**
4079  * absent_pages_in_range - Return number of page frames in holes within a range
4080  * @start_pfn: The start PFN to start searching for holes
4081  * @end_pfn: The end PFN to stop searching for holes
4082  *
4083  * It returns the number of pages frames in memory holes within a range.
4084  */
4085 unsigned long __init absent_pages_in_range(unsigned long start_pfn,
4086                                                         unsigned long end_pfn)
4087 {
4088         return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
4089 }
4090
4091 /* Return the number of page frames in holes in a zone on a node */
4092 static unsigned long __meminit zone_absent_pages_in_node(int nid,
4093                                         unsigned long zone_type,
4094                                         unsigned long *ignored)
4095 {
4096         unsigned long zone_low = arch_zone_lowest_possible_pfn[zone_type];
4097         unsigned long zone_high = arch_zone_highest_possible_pfn[zone_type];
4098         unsigned long node_start_pfn, node_end_pfn;
4099         unsigned long zone_start_pfn, zone_end_pfn;
4100
4101         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
4102         zone_start_pfn = clamp(node_start_pfn, zone_low, zone_high);
4103         zone_end_pfn = clamp(node_end_pfn, zone_low, zone_high);
4104
4105         adjust_zone_range_for_zone_movable(nid, zone_type,
4106                         node_start_pfn, node_end_pfn,
4107                         &zone_start_pfn, &zone_end_pfn);
4108         return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
4109 }
4110
4111 #else /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
4112 static inline unsigned long __meminit zone_spanned_pages_in_node(int nid,
4113                                         unsigned long zone_type,
4114                                         unsigned long *zones_size)
4115 {
4116         return zones_size[zone_type];
4117 }
4118
4119 static inline unsigned long __meminit zone_absent_pages_in_node(int nid,
4120                                                 unsigned long zone_type,
4121                                                 unsigned long *zholes_size)
4122 {
4123         if (!zholes_size)
4124                 return 0;
4125
4126         return zholes_size[zone_type];
4127 }
4128
4129 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
4130
4131 static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,
4132                 unsigned long *zones_size, unsigned long *zholes_size)
4133 {
4134         unsigned long realtotalpages, totalpages = 0;
4135         enum zone_type i;
4136
4137         for (i = 0; i < MAX_NR_ZONES; i++)
4138                 totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
4139                                                                 zones_size);
4140         pgdat->node_spanned_pages = totalpages;
4141
4142         realtotalpages = totalpages;
4143         for (i = 0; i < MAX_NR_ZONES; i++)
4144                 realtotalpages -=
4145                         zone_absent_pages_in_node(pgdat->node_id, i,
4146                                                                 zholes_size);
4147         pgdat->node_present_pages = realtotalpages;
4148         printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
4149                                                         realtotalpages);
4150 }
4151
4152 #ifndef CONFIG_SPARSEMEM
4153 /*
4154  * Calculate the size of the zone->blockflags rounded to an unsigned long
4155  * Start by making sure zonesize is a multiple of pageblock_order by rounding
4156  * up. Then use 1 NR_PAGEBLOCK_BITS worth of bits per pageblock, finally
4157  * round what is now in bits to nearest long in bits, then return it in
4158  * bytes.
4159  */
4160 static unsigned long __init usemap_size(unsigned long zonesize)
4161 {
4162         unsigned long usemapsize;
4163
4164         usemapsize = roundup(zonesize, pageblock_nr_pages);
4165         usemapsize = usemapsize >> pageblock_order;
4166         usemapsize *= NR_PAGEBLOCK_BITS;
4167         usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));
4168
4169         return usemapsize / 8;
4170 }
4171
4172 static void __init setup_usemap(struct pglist_data *pgdat,
4173                                 struct zone *zone, unsigned long zonesize)
4174 {
4175         unsigned long usemapsize = usemap_size(zonesize);
4176         zone->pageblock_flags = NULL;
4177         if (usemapsize)
4178                 zone->pageblock_flags = alloc_bootmem_node_nopanic(pgdat,
4179                                                                    usemapsize);
4180 }
4181 #else
4182 static inline void setup_usemap(struct pglist_data *pgdat,
4183                                 struct zone *zone, unsigned long zonesize) {}
4184 #endif /* CONFIG_SPARSEMEM */
4185
4186 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
4187
4188 /* Return a sensible default order for the pageblock size. */
4189 static inline int pageblock_default_order(void)
4190 {
4191         if (HPAGE_SHIFT > PAGE_SHIFT)
4192                 return HUGETLB_PAGE_ORDER;
4193
4194         return MAX_ORDER-1;
4195 }
4196
4197 /* Initialise the number of pages represented by NR_PAGEBLOCK_BITS */
4198 static inline void __init set_pageblock_order(unsigned int order)
4199 {
4200         /* Check that pageblock_nr_pages has not already been setup */
4201         if (pageblock_order)
4202                 return;
4203
4204         /*
4205          * Assume the largest contiguous order of interest is a huge page.
4206          * This value may be variable depending on boot parameters on IA64
4207          */
4208         pageblock_order = order;
4209 }
4210 #else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
4211
4212 /*
4213  * When CONFIG_HUGETLB_PAGE_SIZE_VARIABLE is not set, set_pageblock_order()
4214  * and pageblock_default_order() are unused as pageblock_order is set
4215  * at compile-time. See include/linux/pageblock-flags.h for the values of
4216  * pageblock_order based on the kernel config
4217  */
4218 static inline int pageblock_default_order(unsigned int order)
4219 {
4220         return MAX_ORDER-1;
4221 }
4222 #define set_pageblock_order(x)  do {} while (0)
4223
4224 #endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
4225
4226 /*
4227  * Set up the zone data structures:
4228  *   - mark all pages reserved
4229  *   - mark all memory queues empty
4230  *   - clear the memory bitmaps
4231  */
4232 static void __paginginit free_area_init_core(struct pglist_data *pgdat,
4233                 unsigned long *zones_size, unsigned long *zholes_size)
4234 {
4235         enum zone_type j;
4236         int nid = pgdat->node_id;
4237         unsigned long zone_start_pfn = pgdat->node_start_pfn;
4238         int ret;
4239
4240         pgdat_resize_init(pgdat);
4241         pgdat->nr_zones = 0;
4242         init_waitqueue_head(&pgdat->kswapd_wait);
4243         pgdat->kswapd_max_order = 0;
4244         pgdat_page_cgroup_init(pgdat);
4245         
4246         for (j = 0; j < MAX_NR_ZONES; j++) {
4247                 struct zone *zone = pgdat->node_zones + j;
4248                 unsigned long size, realsize, memmap_pages;
4249                 enum lru_list l;
4250
4251                 size = zone_spanned_pages_in_node(nid, j, zones_size);
4252                 realsize = size - zone_absent_pages_in_node(nid, j,
4253                                                                 zholes_size);
4254
4255                 /*
4256                  * Adjust realsize so that it accounts for how much memory
4257                  * is used by this zone for memmap. This affects the watermark
4258                  * and per-cpu initialisations
4259                  */
4260                 memmap_pages =
4261                         PAGE_ALIGN(size * sizeof(struct page)) >> PAGE_SHIFT;
4262                 if (realsize >= memmap_pages) {
4263                         realsize -= memmap_pages;
4264                         if (memmap_pages)
4265                                 printk(KERN_DEBUG
4266                                        "  %s zone: %lu pages used for memmap\n",
4267                                        zone_names[j], memmap_pages);
4268                 } else
4269                         printk(KERN_WARNING
4270                                 "  %s zone: %lu pages exceeds realsize %lu\n",
4271                                 zone_names[j], memmap_pages, realsize);
4272
4273                 /* Account for reserved pages */
4274                 if (j == 0 && realsize > dma_reserve) {
4275                         realsize -= dma_reserve;
4276                         printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",
4277                                         zone_names[0], dma_reserve);
4278                 }
4279
4280                 if (!is_highmem_idx(j))
4281                         nr_kernel_pages += realsize;
4282                 nr_all_pages += realsize;
4283
4284                 zone->spanned_pages = size;
4285                 zone->present_pages = realsize;
4286 #ifdef CONFIG_NUMA
4287                 zone->node = nid;
4288                 zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
4289                                                 / 100;
4290                 zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
4291 #endif
4292                 zone->name = zone_names[j];
4293                 spin_lock_init(&zone->lock);
4294                 spin_lock_init(&zone->lru_lock);
4295                 zone_seqlock_init(zone);
4296                 zone->zone_pgdat = pgdat;
4297
4298                 zone_pcp_init(zone);
4299                 for_each_lru(l)
4300                         INIT_LIST_HEAD(&zone->lru[l].list);
4301                 zone->reclaim_stat.recent_rotated[0] = 0;
4302                 zone->reclaim_stat.recent_rotated[1] = 0;
4303                 zone->reclaim_stat.recent_scanned[0] = 0;
4304                 zone->reclaim_stat.recent_scanned[1] = 0;
4305                 zap_zone_vm_stats(zone);
4306                 zone->flags = 0;
4307                 if (!size)
4308                         continue;
4309
4310                 set_pageblock_order(pageblock_default_order());
4311                 setup_usemap(pgdat, zone, size);
4312                 ret = init_currently_empty_zone(zone, zone_start_pfn,
4313                                                 size, MEMMAP_EARLY);
4314                 BUG_ON(ret);
4315                 memmap_init(size, nid, j, zone_start_pfn);
4316                 zone_start_pfn += size;
4317         }
4318 }
4319
4320 static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)
4321 {
4322         /* Skip empty nodes */
4323         if (!pgdat->node_spanned_pages)
4324                 return;
4325
4326 #ifdef CONFIG_FLAT_NODE_MEM_MAP
4327         /* ia64 gets its own node_mem_map, before this, without bootmem */
4328         if (!pgdat->node_mem_map) {
4329                 unsigned long size, start, end;
4330                 struct page *map;
4331
4332                 /*
4333                  * The zone's endpoints aren't required to be MAX_ORDER
4334                  * aligned but the node_mem_map endpoints must be in order
4335                  * for the buddy allocator to function correctly.
4336                  */
4337                 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
4338                 end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
4339                 end = ALIGN(end, MAX_ORDER_NR_PAGES);
4340                 size =  (end - start) * sizeof(struct page);
4341                 map = alloc_remap(pgdat->node_id, size);
4342                 if (!map)
4343                         map = alloc_bootmem_node_nopanic(pgdat, size);
4344                 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
4345         }
4346 #ifndef CONFIG_NEED_MULTIPLE_NODES
4347         /*
4348          * With no DISCONTIG, the global mem_map is just set as node 0's
4349          */
4350         if (pgdat == NODE_DATA(0)) {
4351                 mem_map = NODE_DATA(0)->node_mem_map;
4352 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
4353                 if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
4354                         mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);
4355 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
4356         }
4357 #endif
4358 #endif /* CONFIG_FLAT_NODE_MEM_MAP */
4359 }
4360
4361 void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
4362                 unsigned long node_start_pfn, unsigned long *zholes_size)
4363 {
4364         pg_data_t *pgdat = NODE_DATA(nid);
4365
4366         pgdat->node_id = nid;
4367         pgdat->node_start_pfn = node_start_pfn;
4368         calculate_node_totalpages(pgdat, zones_size, zholes_size);
4369
4370         alloc_node_mem_map(pgdat);
4371 #ifdef CONFIG_FLAT_NODE_MEM_MAP
4372         printk(KERN_DEBUG "free_area_init_node: node %d, pgdat %08lx, node_mem_map %08lx\n",
4373                 nid, (unsigned long)pgdat,
4374                 (unsigned long)pgdat->node_mem_map);
4375 #endif
4376
4377         free_area_init_core(pgdat, zones_size, zholes_size);
4378 }
4379
4380 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
4381
4382 #if MAX_NUMNODES > 1
4383 /*
4384  * Figure out the number of possible node ids.
4385  */
4386 static void __init setup_nr_node_ids(void)
4387 {
4388         unsigned int node;
4389         unsigned int highest = 0;
4390
4391         for_each_node_mask(node, node_possible_map)
4392                 highest = node;
4393         nr_node_ids = highest + 1;
4394 }
4395 #else
4396 static inline void setup_nr_node_ids(void)
4397 {
4398 }
4399 #endif
4400
4401 /**
4402  * node_map_pfn_alignment - determine the maximum internode alignment
4403  *
4404  * This function should be called after node map is populated and sorted.
4405  * It calculates the maximum power of two alignment which can distinguish
4406  * all the nodes.
4407  *
4408  * For example, if all nodes are 1GiB and aligned to 1GiB, the return value
4409  * would indicate 1GiB alignment with (1 << (30 - PAGE_SHIFT)).  If the
4410  * nodes are shifted by 256MiB, 256MiB.  Note that if only the last node is
4411  * shifted, 1GiB is enough and this function will indicate so.
4412  *
4413  * This is used to test whether pfn -> nid mapping of the chosen memory
4414  * model has fine enough granularity to avoid incorrect mapping for the
4415  * populated node map.
4416  *
4417  * Returns the determined alignment in pfn's.  0 if there is no alignment
4418  * requirement (single node).
4419  */
4420 unsigned long __init node_map_pfn_alignment(void)
4421 {
4422         unsigned long accl_mask = 0, last_end = 0;
4423         unsigned long start, end, mask;
4424         int last_nid = -1;
4425         int i, nid;
4426
4427         for_each_mem_pfn_range(i, MAX_NUMNODES, &start, &end, &nid) {
4428                 if (!start || last_nid < 0 || last_nid == nid) {
4429                         last_nid = nid;
4430                         last_end = end;
4431                         continue;
4432                 }
4433
4434                 /*
4435                  * Start with a mask granular enough to pin-point to the
4436                  * start pfn and tick off bits one-by-one until it becomes
4437                  * too coarse to separate the current node from the last.
4438                  */
4439                 mask = ~((1 << __ffs(start)) - 1);
4440                 while (mask && last_end <= (start & (mask << 1)))
4441                         mask <<= 1;
4442
4443                 /* accumulate all internode masks */
4444                 accl_mask |= mask;
4445         }
4446
4447         /* convert mask to number of pages */
4448         return ~accl_mask + 1;
4449 }
4450
4451 /* Find the lowest pfn for a node */
4452 static unsigned long __init find_min_pfn_for_node(int nid)
4453 {
4454         unsigned long min_pfn = ULONG_MAX;
4455         unsigned long start_pfn;
4456         int i;
4457
4458         for_each_mem_pfn_range(i, nid, &start_pfn, NULL, NULL)
4459                 min_pfn = min(min_pfn, start_pfn);
4460
4461         if (min_pfn == ULONG_MAX) {
4462                 printk(KERN_WARNING
4463                         "Could not find start_pfn for node %d\n", nid);
4464                 return 0;
4465         }
4466
4467         return min_pfn;
4468 }
4469
4470 /**
4471  * find_min_pfn_with_active_regions - Find the minimum PFN registered
4472  *
4473  * It returns the minimum PFN based on information provided via
4474  * add_active_range().
4475  */
4476 unsigned long __init find_min_pfn_with_active_regions(void)
4477 {
4478         return find_min_pfn_for_node(MAX_NUMNODES);
4479 }
4480
4481 /*
4482  * early_calculate_totalpages()
4483  * Sum pages in active regions for movable zone.
4484  * Populate N_HIGH_MEMORY for calculating usable_nodes.
4485  */
4486 static unsigned long __init early_calculate_totalpages(void)
4487 {
4488         unsigned long totalpages = 0;
4489         unsigned long start_pfn, end_pfn;
4490         int i, nid;
4491
4492         for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid) {
4493                 unsigned long pages = end_pfn - start_pfn;
4494
4495                 totalpages += pages;
4496                 if (pages)
4497                         node_set_state(nid, N_HIGH_MEMORY);
4498         }
4499         return totalpages;
4500 }
4501
4502 /*
4503  * Find the PFN the Movable zone begins in each node. Kernel memory
4504  * is spread evenly between nodes as long as the nodes have enough
4505  * memory. When they don't, some nodes will have more kernelcore than
4506  * others
4507  */
4508 static void __init find_zone_movable_pfns_for_nodes(unsigned long *movable_pfn)
4509 {
4510         int i, nid;
4511         unsigned long usable_startpfn;
4512         unsigned long kernelcore_node, kernelcore_remaining;
4513         /* save the state before borrow the nodemask */
4514         nodemask_t saved_node_state = node_states[N_HIGH_MEMORY];
4515         unsigned long totalpages = early_calculate_totalpages();
4516         int usable_nodes = nodes_weight(node_states[N_HIGH_MEMORY]);
4517
4518         /*
4519          * If movablecore was specified, calculate what size of
4520          * kernelcore that corresponds so that memory usable for
4521          * any allocation type is evenly spread. If both kernelcore
4522          * and movablecore are specified, then the value of kernelcore
4523          * will be used for required_kernelcore if it's greater than
4524          * what movablecore would have allowed.
4525          */
4526         if (required_movablecore) {
4527                 unsigned long corepages;
4528
4529                 /*
4530                  * Round-up so that ZONE_MOVABLE is at least as large as what
4531                  * was requested by the user
4532                  */
4533                 required_movablecore =
4534                         roundup(required_movablecore, MAX_ORDER_NR_PAGES);
4535                 corepages = totalpages - required_movablecore;
4536
4537                 required_kernelcore = max(required_kernelcore, corepages);
4538         }
4539
4540         /* If kernelcore was not specified, there is no ZONE_MOVABLE */
4541         if (!required_kernelcore)
4542                 goto out;
4543
4544         /* usable_startpfn is the lowest possible pfn ZONE_MOVABLE can be at */
4545         find_usable_zone_for_movable();
4546         usable_startpfn = arch_zone_lowest_possible_pfn[movable_zone];
4547
4548 restart:
4549         /* Spread kernelcore memory as evenly as possible throughout nodes */
4550         kernelcore_node = required_kernelcore / usable_nodes;
4551         for_each_node_state(nid, N_HIGH_MEMORY) {
4552                 unsigned long start_pfn, end_pfn;
4553
4554                 /*
4555                  * Recalculate kernelcore_node if the division per node
4556                  * now exceeds what is necessary to satisfy the requested
4557                  * amount of memory for the kernel
4558                  */
4559                 if (required_kernelcore < kernelcore_node)
4560                         kernelcore_node = required_kernelcore / usable_nodes;
4561
4562                 /*
4563                  * As the map is walked, we track how much memory is usable
4564                  * by the kernel using kernelcore_remaining. When it is
4565                  * 0, the rest of the node is usable by ZONE_MOVABLE
4566                  */
4567                 kernelcore_remaining = kernelcore_node;
4568
4569                 /* Go through each range of PFNs within this node */
4570                 for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, NULL) {
4571                         unsigned long size_pages;
4572
4573                         start_pfn = max(start_pfn, zone_movable_pfn[nid]);
4574                         if (start_pfn >= end_pfn)
4575                                 continue;
4576
4577                         /* Account for what is only usable for kernelcore */
4578                         if (start_pfn < usable_startpfn) {
4579                                 unsigned long kernel_pages;
4580                                 kernel_pages = min(end_pfn, usable_startpfn)
4581                                                                 - start_pfn;
4582
4583                                 kernelcore_remaining -= min(kernel_pages,
4584                                                         kernelcore_remaining);
4585                                 required_kernelcore -= min(kernel_pages,
4586                                                         required_kernelcore);
4587
4588                                 /* Continue if range is now fully accounted */
4589                                 if (end_pfn <= usable_startpfn) {
4590
4591                                         /*
4592                                          * Push zone_movable_pfn to the end so
4593                                          * that if we have to rebalance
4594                                          * kernelcore across nodes, we will
4595                                          * not double account here
4596                                          */
4597                                         zone_movable_pfn[nid] = end_pfn;
4598                                         continue;
4599                                 }
4600                                 start_pfn = usable_startpfn;
4601                         }
4602
4603                         /*
4604                          * The usable PFN range for ZONE_MOVABLE is from
4605                          * start_pfn->end_pfn. Calculate size_pages as the
4606                          * number of pages used as kernelcore
4607                          */
4608                         size_pages = end_pfn - start_pfn;
4609                         if (size_pages > kernelcore_remaining)
4610                                 size_pages = kernelcore_remaining;
4611                         zone_movable_pfn[nid] = start_pfn + size_pages;
4612
4613                         /*
4614                          * Some kernelcore has been met, update counts and
4615                          * break if the kernelcore for this node has been
4616                          * satisified
4617                          */
4618                         required_kernelcore -= min(required_kernelcore,
4619                                                                 size_pages);
4620                         kernelcore_remaining -= size_pages;
4621                         if (!kernelcore_remaining)
4622                                 break;
4623                 }
4624         }
4625
4626         /*
4627          * If there is still required_kernelcore, we do another pass with one
4628          * less node in the count. This will push zone_movable_pfn[nid] further
4629          * along on the nodes that still have memory until kernelcore is
4630          * satisified
4631          */
4632         usable_nodes--;
4633         if (usable_nodes && required_kernelcore > usable_nodes)
4634                 goto restart;
4635
4636         /* Align start of ZONE_MOVABLE on all nids to MAX_ORDER_NR_PAGES */
4637         for (nid = 0; nid < MAX_NUMNODES; nid++)
4638                 zone_movable_pfn[nid] =
4639                         roundup(zone_movable_pfn[nid], MAX_ORDER_NR_PAGES);
4640
4641 out:
4642         /* restore the node_state */
4643         node_states[N_HIGH_MEMORY] = saved_node_state;
4644 }
4645
4646 /* Any regular memory on that node ? */
4647 static void check_for_regular_memory(pg_data_t *pgdat)
4648 {
4649 #ifdef CONFIG_HIGHMEM
4650         enum zone_type zone_type;
4651
4652         for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {
4653                 struct zone *zone = &pgdat->node_zones[zone_type];
4654                 if (zone->present_pages)
4655                         node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);
4656         }
4657 #endif
4658 }
4659
4660 /**
4661  * free_area_init_nodes - Initialise all pg_data_t and zone data
4662  * @max_zone_pfn: an array of max PFNs for each zone
4663  *
4664  * This will call free_area_init_node() for each active node in the system.
4665  * Using the page ranges provided by add_active_range(), the size of each
4666  * zone in each node and their holes is calculated. If the maximum PFN
4667  * between two adjacent zones match, it is assumed that the zone is empty.
4668  * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
4669  * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
4670  * starts where the previous one ended. For example, ZONE_DMA32 starts
4671  * at arch_max_dma_pfn.
4672  */
4673 void __init free_area_init_nodes(unsigned long *max_zone_pfn)
4674 {
4675         unsigned long start_pfn, end_pfn;
4676         int i, nid;
4677
4678         /* Record where the zone boundaries are */
4679         memset(arch_zone_lowest_possible_pfn, 0,
4680                                 sizeof(arch_zone_lowest_possible_pfn));
4681         memset(arch_zone_highest_possible_pfn, 0,
4682                                 sizeof(arch_zone_highest_possible_pfn));
4683         arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
4684         arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
4685         for (i = 1; i < MAX_NR_ZONES; i++) {
4686                 if (i == ZONE_MOVABLE)
4687                         continue;
4688                 arch_zone_lowest_possible_pfn[i] =
4689                         arch_zone_highest_possible_pfn[i-1];
4690                 arch_zone_highest_possible_pfn[i] =
4691                         max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
4692         }
4693         arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
4694         arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;
4695
4696         /* Find the PFNs that ZONE_MOVABLE begins at in each node */
4697         memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
4698         find_zone_movable_pfns_for_nodes(zone_movable_pfn);
4699
4700         /* Print out the zone ranges */
4701         printk("Zone PFN ranges:\n");
4702         for (i = 0; i < MAX_NR_ZONES; i++) {
4703                 if (i == ZONE_MOVABLE)
4704                         continue;
4705                 printk("  %-8s ", zone_names[i]);
4706                 if (arch_zone_lowest_possible_pfn[i] ==
4707                                 arch_zone_highest_possible_pfn[i])
4708                         printk("empty\n");
4709                 else
4710                         printk("%0#10lx -> %0#10lx\n",
4711                                 arch_zone_lowest_possible_pfn[i],
4712                                 arch_zone_highest_possible_pfn[i]);
4713         }
4714
4715         /* Print out the PFNs ZONE_MOVABLE begins at in each node */
4716         printk("Movable zone start PFN for each node\n");
4717         for (i = 0; i < MAX_NUMNODES; i++) {
4718                 if (zone_movable_pfn[i])
4719                         printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);
4720         }
4721
4722         /* Print out the early_node_map[] */
4723         printk("Early memory PFN ranges\n");
4724         for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid)
4725                 printk("  %3d: %0#10lx -> %0#10lx\n", nid, start_pfn, end_pfn);
4726
4727         /* Initialise every node */
4728         mminit_verify_pageflags_layout();
4729         setup_nr_node_ids();
4730         for_each_online_node(nid) {
4731                 pg_data_t *pgdat = NODE_DATA(nid);
4732                 free_area_init_node(nid, NULL,
4733                                 find_min_pfn_for_node(nid), NULL);
4734
4735                 /* Any memory on that node */
4736                 if (pgdat->node_present_pages)
4737                         node_set_state(nid, N_HIGH_MEMORY);
4738                 check_for_regular_memory(pgdat);
4739         }
4740 }
4741
4742 static int __init cmdline_parse_core(char *p, unsigned long *core)
4743 {
4744         unsigned long long coremem;
4745         if (!p)
4746                 return -EINVAL;
4747
4748         coremem = memparse(p, &p);
4749         *core = coremem >> PAGE_SHIFT;
4750
4751         /* Paranoid check that UL is enough for the coremem value */
4752         WARN_ON((coremem >> PAGE_SHIFT) > ULONG_MAX);
4753
4754         return 0;
4755 }
4756
4757 /*
4758  * kernelcore=size sets the amount of memory for use for allocations that
4759  * cannot be reclaimed or migrated.
4760  */
4761 static int __init cmdline_parse_kernelcore(char *p)
4762 {
4763         return cmdline_parse_core(p, &required_kernelcore);
4764 }
4765
4766 /*
4767  * movablecore=size sets the amount of memory for use for allocations that
4768  * can be reclaimed or migrated.
4769  */
4770 static int __init cmdline_parse_movablecore(char *p)
4771 {
4772         return cmdline_parse_core(p, &required_movablecore);
4773 }
4774
4775 early_param("kernelcore", cmdline_parse_kernelcore);
4776 early_param("movablecore", cmdline_parse_movablecore);
4777
4778 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
4779
4780 /**
4781  * set_dma_reserve - set the specified number of pages reserved in the first zone
4782  * @new_dma_reserve: The number of pages to mark reserved
4783  *
4784  * The per-cpu batchsize and zone watermarks are determined by present_pages.
4785  * In the DMA zone, a significant percentage may be consumed by kernel image
4786  * and other unfreeable allocations which can skew the watermarks badly. This
4787  * function may optionally be used to account for unfreeable pages in the
4788  * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
4789  * smaller per-cpu batchsize.
4790  */
4791 void __init set_dma_reserve(unsigned long new_dma_reserve)
4792 {
4793         dma_reserve = new_dma_reserve;
4794 }
4795
4796 void __init free_area_init(unsigned long *zones_size)
4797 {
4798         free_area_init_node(0, zones_size,
4799                         __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
4800 }
4801
4802 static int page_alloc_cpu_notify(struct notifier_block *self,
4803                                  unsigned long action, void *hcpu)
4804 {
4805         int cpu = (unsigned long)hcpu;
4806
4807         if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
4808                 drain_pages(cpu);
4809
4810                 /*
4811                  * Spill the event counters of the dead processor
4812                  * into the current processors event counters.
4813                  * This artificially elevates the count of the current
4814                  * processor.
4815                  */
4816                 vm_events_fold_cpu(cpu);
4817
4818                 /*
4819                  * Zero the differential counters of the dead processor
4820                  * so that the vm statistics are consistent.
4821                  *
4822                  * This is only okay since the processor is dead and cannot
4823                  * race with what we are doing.
4824                  */
4825                 refresh_cpu_vm_stats(cpu);
4826         }
4827         return NOTIFY_OK;
4828 }
4829
4830 void __init page_alloc_init(void)
4831 {
4832         hotcpu_notifier(page_alloc_cpu_notify, 0);
4833 }
4834
4835 /*
4836  * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio
4837  *      or min_free_kbytes changes.
4838  */
4839 static void calculate_totalreserve_pages(void)
4840 {
4841         struct pglist_data *pgdat;
4842         unsigned long reserve_pages = 0;
4843         enum zone_type i, j;
4844
4845         for_each_online_pgdat(pgdat) {
4846                 for (i = 0; i < MAX_NR_ZONES; i++) {
4847                         struct zone *zone = pgdat->node_zones + i;
4848                         unsigned long max = 0;
4849
4850                         /* Find valid and maximum lowmem_reserve in the zone */
4851                         for (j = i; j < MAX_NR_ZONES; j++) {
4852                                 if (zone->lowmem_reserve[j] > max)
4853                                         max = zone->lowmem_reserve[j];
4854                         }
4855
4856                         /* we treat the high watermark as reserved pages. */
4857                         max += high_wmark_pages(zone);
4858
4859                         if (max > zone->present_pages)
4860                                 max = zone->present_pages;
4861                         reserve_pages += max;
4862                         /*
4863                          * Lowmem reserves are not available to
4864                          * GFP_HIGHUSER page cache allocations and
4865                          * kswapd tries to balance zones to their high
4866                          * watermark.  As a result, neither should be
4867                          * regarded as dirtyable memory, to prevent a
4868                          * situation where reclaim has to clean pages
4869                          * in order to balance the zones.
4870                          */
4871                         zone->dirty_balance_reserve = max;
4872                 }
4873         }
4874         dirty_balance_reserve = reserve_pages;
4875         totalreserve_pages = reserve_pages;
4876 }
4877
4878 /*
4879  * setup_per_zone_lowmem_reserve - called whenever
4880  *      sysctl_lower_zone_reserve_ratio changes.  Ensures that each zone
4881  *      has a correct pages reserved value, so an adequate number of
4882  *      pages are left in the zone after a successful __alloc_pages().
4883  */
4884 static void setup_per_zone_lowmem_reserve(void)
4885 {
4886         struct pglist_data *pgdat;
4887         enum zone_type j, idx;
4888
4889         for_each_online_pgdat(pgdat) {
4890                 for (j = 0; j < MAX_NR_ZONES; j++) {
4891                         struct zone *zone = pgdat->node_zones + j;
4892                         unsigned long present_pages = zone->present_pages;
4893
4894                         zone->lowmem_reserve[j] = 0;
4895
4896                         idx = j;
4897                         while (idx) {
4898                                 struct zone *lower_zone;
4899
4900                                 idx--;
4901
4902                                 if (sysctl_lowmem_reserve_ratio[idx] < 1)
4903                                         sysctl_lowmem_reserve_ratio[idx] = 1;
4904
4905                                 lower_zone = pgdat->node_zones + idx;
4906                                 lower_zone->lowmem_reserve[j] = present_pages /
4907                                         sysctl_lowmem_reserve_ratio[idx];
4908                                 present_pages += lower_zone->present_pages;
4909                         }
4910                 }
4911         }
4912
4913         /* update totalreserve_pages */
4914         calculate_totalreserve_pages();
4915 }
4916
4917 /**
4918  * setup_per_zone_wmarks - called when min_free_kbytes changes
4919  * or when memory is hot-{added|removed}
4920  *
4921  * Ensures that the watermark[min,low,high] values for each zone are set
4922  * correctly with respect to min_free_kbytes.
4923  */
4924 void setup_per_zone_wmarks(void)
4925 {
4926         unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
4927         unsigned long lowmem_pages = 0;
4928         struct zone *zone;
4929         unsigned long flags;
4930
4931         /* Calculate total number of !ZONE_HIGHMEM pages */
4932         for_each_zone(zone) {
4933                 if (!is_highmem(zone))
4934                         lowmem_pages += zone->present_pages;
4935         }
4936
4937         for_each_zone(zone) {
4938                 u64 tmp;
4939
4940                 spin_lock_irqsave(&zone->lock, flags);
4941                 tmp = (u64)pages_min * zone->present_pages;
4942                 do_div(tmp, lowmem_pages);
4943                 if (is_highmem(zone)) {
4944                         /*
4945                          * __GFP_HIGH and PF_MEMALLOC allocations usually don't
4946                          * need highmem pages, so cap pages_min to a small
4947                          * value here.
4948                          *
4949                          * The WMARK_HIGH-WMARK_LOW and (WMARK_LOW-WMARK_MIN)
4950                          * deltas controls asynch page reclaim, and so should
4951                          * not be capped for highmem.
4952                          */
4953                         int min_pages;
4954
4955                         min_pages = zone->present_pages / 1024;
4956                         if (min_pages < SWAP_CLUSTER_MAX)
4957                                 min_pages = SWAP_CLUSTER_MAX;
4958                         if (min_pages > 128)
4959                                 min_pages = 128;
4960                         zone->watermark[WMARK_MIN] = min_pages;
4961                 } else {
4962                         /*
4963                          * If it's a lowmem zone, reserve a number of pages
4964                          * proportionate to the zone's size.
4965                          */
4966                         zone->watermark[WMARK_MIN] = tmp;
4967                 }
4968
4969                 zone->watermark[WMARK_LOW]  = min_wmark_pages(zone) + (tmp >> 2);
4970                 zone->watermark[WMARK_HIGH] = min_wmark_pages(zone) + (tmp >> 1);
4971                 setup_zone_migrate_reserve(zone);
4972                 spin_unlock_irqrestore(&zone->lock, flags);
4973         }
4974
4975         /* update totalreserve_pages */
4976         calculate_totalreserve_pages();
4977 }
4978
4979 /*
4980  * The inactive anon list should be small enough that the VM never has to
4981  * do too much work, but large enough that each inactive page has a chance
4982  * to be referenced again before it is swapped out.
4983  *
4984  * The inactive_anon ratio is the target ratio of ACTIVE_ANON to
4985  * INACTIVE_ANON pages on this zone's LRU, maintained by the
4986  * pageout code. A zone->inactive_ratio of 3 means 3:1 or 25% of
4987  * the anonymous pages are kept on the inactive list.
4988  *
4989  * total     target    max
4990  * memory    ratio     inactive anon
4991  * -------------------------------------
4992  *   10MB       1         5MB
4993  *  100MB       1        50MB
4994  *    1GB       3       250MB
4995  *   10GB      10       0.9GB
4996  *  100GB      31         3GB
4997  *    1TB     101        10GB
4998  *   10TB     320        32GB
4999  */
5000 static void __meminit calculate_zone_inactive_ratio(struct zone *zone)
5001 {
5002         unsigned int gb, ratio;
5003
5004         /* Zone size in gigabytes */
5005         gb = zone->present_pages >> (30 - PAGE_SHIFT);
5006         if (gb)
5007                 ratio = int_sqrt(10 * gb);
5008         else
5009                 ratio = 1;
5010
5011         zone->inactive_ratio = ratio;
5012 }
5013
5014 static void __meminit setup_per_zone_inactive_ratio(void)
5015 {
5016         struct zone *zone;
5017
5018         for_each_zone(zone)
5019                 calculate_zone_inactive_ratio(zone);
5020 }
5021
5022 /*
5023  * Initialise min_free_kbytes.
5024  *
5025  * For small machines we want it small (128k min).  For large machines
5026  * we want it large (64MB max).  But it is not linear, because network
5027  * bandwidth does not increase linearly with machine size.  We use
5028  *
5029  *      min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
5030  *      min_free_kbytes = sqrt(lowmem_kbytes * 16)
5031  *
5032  * which yields
5033  *
5034  * 16MB:        512k
5035  * 32MB:        724k
5036  * 64MB:        1024k
5037  * 128MB:       1448k
5038  * 256MB:       2048k
5039  * 512MB:       2896k
5040  * 1024MB:      4096k
5041  * 2048MB:      5792k
5042  * 4096MB:      8192k
5043  * 8192MB:      11584k
5044  * 16384MB:     16384k
5045  */
5046 int __meminit init_per_zone_wmark_min(void)
5047 {
5048         unsigned long lowmem_kbytes;
5049
5050         lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
5051
5052         min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
5053         if (min_free_kbytes < 128)
5054                 min_free_kbytes = 128;
5055         if (min_free_kbytes > 65536)
5056                 min_free_kbytes = 65536;
5057         setup_per_zone_wmarks();
5058         refresh_zone_stat_thresholds();
5059         setup_per_zone_lowmem_reserve();
5060         setup_per_zone_inactive_ratio();
5061         return 0;
5062 }
5063 module_init(init_per_zone_wmark_min)
5064
5065 /*
5066  * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 
5067  *      that we can call two helper functions whenever min_free_kbytes
5068  *      changes.
5069  */
5070 int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 
5071         void __user *buffer, size_t *length, loff_t *ppos)
5072 {
5073         proc_dointvec(table, write, buffer, length, ppos);
5074         if (write)
5075                 setup_per_zone_wmarks();
5076         return 0;
5077 }
5078
5079 #ifdef CONFIG_NUMA
5080 int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write,
5081         void __user *buffer, size_t *length, loff_t *ppos)
5082 {
5083         struct zone *zone;
5084         int rc;
5085
5086         rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
5087         if (rc)
5088                 return rc;
5089
5090         for_each_zone(zone)
5091                 zone->min_unmapped_pages = (zone->present_pages *
5092                                 sysctl_min_unmapped_ratio) / 100;
5093         return 0;
5094 }
5095
5096 int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write,
5097         void __user *buffer, size_t *length, loff_t *ppos)
5098 {
5099         struct zone *zone;
5100         int rc;
5101
5102         rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
5103         if (rc)
5104                 return rc;
5105
5106         for_each_zone(zone)
5107                 zone->min_slab_pages = (zone->present_pages *
5108                                 sysctl_min_slab_ratio) / 100;
5109         return 0;
5110 }
5111 #endif
5112
5113 /*
5114  * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
5115  *      proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
5116  *      whenever sysctl_lowmem_reserve_ratio changes.
5117  *
5118  * The reserve ratio obviously has absolutely no relation with the
5119  * minimum watermarks. The lowmem reserve ratio can only make sense
5120  * if in function of the boot time zone sizes.
5121  */
5122 int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
5123         void __user *buffer, size_t *length, loff_t *ppos)
5124 {
5125         proc_dointvec_minmax(table, write, buffer, length, ppos);
5126         setup_per_zone_lowmem_reserve();
5127         return 0;
5128 }
5129
5130 /*
5131  * percpu_pagelist_fraction - changes the pcp->high for each zone on each
5132  * cpu.  It is the fraction of total pages in each zone that a hot per cpu pagelist
5133  * can have before it gets flushed back to buddy allocator.
5134  */
5135
5136 int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write,
5137         void __user *buffer, size_t *length, loff_t *ppos)
5138 {
5139         struct zone *zone;
5140         unsigned int cpu;
5141         int ret;
5142
5143         ret = proc_dointvec_minmax(table, write, buffer, length, ppos);
5144         if (!write || (ret == -EINVAL))
5145                 return ret;
5146         for_each_populated_zone(zone) {
5147                 for_each_possible_cpu(cpu) {
5148                         unsigned long  high;
5149                         high = zone->present_pages / percpu_pagelist_fraction;
5150                         setup_pagelist_highmark(
5151                                 per_cpu_ptr(zone->pageset, cpu), high);
5152                 }
5153         }
5154         return 0;
5155 }
5156
5157 int hashdist = HASHDIST_DEFAULT;
5158
5159 #ifdef CONFIG_NUMA
5160 static int __init set_hashdist(char *str)
5161 {
5162         if (!str)
5163                 return 0;
5164         hashdist = simple_strtoul(str, &str, 0);
5165         return 1;
5166 }
5167 __setup("hashdist=", set_hashdist);
5168 #endif
5169
5170 /*
5171  * allocate a large system hash table from bootmem
5172  * - it is assumed that the hash table must contain an exact power-of-2
5173  *   quantity of entries
5174  * - limit is the number of hash buckets, not the total allocation size
5175  */
5176 void *__init alloc_large_system_hash(const char *tablename,
5177                                      unsigned long bucketsize,
5178                                      unsigned long numentries,
5179                                      int scale,
5180                                      int flags,
5181                                      unsigned int *_hash_shift,
5182                                      unsigned int *_hash_mask,
5183                                      unsigned long limit)
5184 {
5185         unsigned long long max = limit;
5186         unsigned long log2qty, size;
5187         void *table = NULL;
5188
5189         /* allow the kernel cmdline to have a say */
5190         if (!numentries) {
5191                 /* round applicable memory size up to nearest megabyte */
5192                 numentries = nr_kernel_pages;
5193                 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
5194                 numentries >>= 20 - PAGE_SHIFT;
5195                 numentries <<= 20 - PAGE_SHIFT;
5196
5197                 /* limit to 1 bucket per 2^scale bytes of low memory */
5198                 if (scale > PAGE_SHIFT)
5199                         numentries >>= (scale - PAGE_SHIFT);
5200                 else
5201                         numentries <<= (PAGE_SHIFT - scale);
5202
5203                 /* Make sure we've got at least a 0-order allocation.. */
5204                 if (unlikely(flags & HASH_SMALL)) {
5205                         /* Makes no sense without HASH_EARLY */
5206                         WARN_ON(!(flags & HASH_EARLY));
5207                         if (!(numentries >> *_hash_shift)) {
5208                                 numentries = 1UL << *_hash_shift;
5209                                 BUG_ON(!numentries);
5210                         }
5211                 } else if (unlikely((numentries * bucketsize) < PAGE_SIZE))
5212                         numentries = PAGE_SIZE / bucketsize;
5213         }
5214         numentries = roundup_pow_of_two(numentries);
5215
5216         /* limit allocation size to 1/16 total memory by default */
5217         if (max == 0) {
5218                 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
5219                 do_div(max, bucketsize);
5220         }
5221
5222         if (numentries > max)
5223                 numentries = max;
5224
5225         log2qty = ilog2(numentries);
5226
5227         do {
5228                 size = bucketsize << log2qty;
5229                 if (flags & HASH_EARLY)
5230                         table = alloc_bootmem_nopanic(size);
5231                 else if (hashdist)
5232                         table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
5233                 else {
5234                         /*
5235                          * If bucketsize is not a power-of-two, we may free
5236                          * some pages at the end of hash table which
5237                          * alloc_pages_exact() automatically does
5238                          */
5239                         if (get_order(size) < MAX_ORDER) {
5240                                 table = alloc_pages_exact(size, GFP_ATOMIC);
5241                                 kmemleak_alloc(table, size, 1, GFP_ATOMIC);
5242                         }
5243                 }
5244         } while (!table && size > PAGE_SIZE && --log2qty);
5245
5246         if (!table)
5247                 panic("Failed to allocate %s hash table\n", tablename);
5248
5249         printk(KERN_INFO "%s hash table entries: %ld (order: %d, %lu bytes)\n",
5250                tablename,
5251                (1UL << log2qty),
5252                ilog2(size) - PAGE_SHIFT,
5253                size);
5254
5255         if (_hash_shift)
5256                 *_hash_shift = log2qty;
5257         if (_hash_mask)
5258                 *_hash_mask = (1 << log2qty) - 1;
5259
5260         return table;
5261 }
5262
5263 /* Return a pointer to the bitmap storing bits affecting a block of pages */
5264 static inline unsigned long *get_pageblock_bitmap(struct zone *zone,
5265                                                         unsigned long pfn)
5266 {
5267 #ifdef CONFIG_SPARSEMEM
5268         return __pfn_to_section(pfn)->pageblock_flags;
5269 #else
5270         return zone->pageblock_flags;
5271 #endif /* CONFIG_SPARSEMEM */
5272 }
5273
5274 static inline int pfn_to_bitidx(struct zone *zone, unsigned long pfn)
5275 {
5276 #ifdef CONFIG_SPARSEMEM
5277         pfn &= (PAGES_PER_SECTION-1);
5278         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
5279 #else
5280         pfn = pfn - zone->zone_start_pfn;
5281         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
5282 #endif /* CONFIG_SPARSEMEM */
5283 }
5284
5285 /**
5286  * get_pageblock_flags_group - Return the requested group of flags for the pageblock_nr_pages block of pages
5287  * @page: The page within the block of interest
5288  * @start_bitidx: The first bit of interest to retrieve
5289  * @end_bitidx: The last bit of interest
5290  * returns pageblock_bits flags
5291  */
5292 unsigned long get_pageblock_flags_group(struct page *page,
5293                                         int start_bitidx, int end_bitidx)
5294 {
5295         struct zone *zone;
5296         unsigned long *bitmap;
5297         unsigned long pfn, bitidx;
5298         unsigned long flags = 0;
5299         unsigned long value = 1;
5300
5301         zone = page_zone(page);
5302         pfn = page_to_pfn(page);
5303         bitmap = get_pageblock_bitmap(zone, pfn);
5304         bitidx = pfn_to_bitidx(zone, pfn);
5305
5306         for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
5307                 if (test_bit(bitidx + start_bitidx, bitmap))
5308                         flags |= value;
5309
5310         return flags;
5311 }
5312
5313 /**
5314  * set_pageblock_flags_group - Set the requested group of flags for a pageblock_nr_pages block of pages
5315  * @page: The page within the block of interest
5316  * @start_bitidx: The first bit of interest
5317  * @end_bitidx: The last bit of interest
5318  * @flags: The flags to set
5319  */
5320 void set_pageblock_flags_group(struct page *page, unsigned long flags,
5321                                         int start_bitidx, int end_bitidx)
5322 {
5323         struct zone *zone;
5324         unsigned long *bitmap;
5325         unsigned long pfn, bitidx;
5326         unsigned long value = 1;
5327
5328         zone = page_zone(page);
5329         pfn = page_to_pfn(page);
5330         bitmap = get_pageblock_bitmap(zone, pfn);
5331         bitidx = pfn_to_bitidx(zone, pfn);
5332         VM_BUG_ON(pfn < zone->zone_start_pfn);
5333         VM_BUG_ON(pfn >= zone->zone_start_pfn + zone->spanned_pages);
5334
5335         for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
5336                 if (flags & value)
5337                         __set_bit(bitidx + start_bitidx, bitmap);
5338                 else
5339                         __clear_bit(bitidx + start_bitidx, bitmap);
5340 }
5341
5342 /*
5343  * This is designed as sub function...plz see page_isolation.c also.
5344  * set/clear page block's type to be ISOLATE.
5345  * page allocater never alloc memory from ISOLATE block.
5346  */
5347
5348 static int
5349 __count_immobile_pages(struct zone *zone, struct page *page, int count)
5350 {
5351         unsigned long pfn, iter, found;
5352         /*
5353          * For avoiding noise data, lru_add_drain_all() should be called
5354          * If ZONE_MOVABLE, the zone never contains immobile pages
5355          */
5356         if (zone_idx(zone) == ZONE_MOVABLE)
5357                 return true;
5358
5359         if (get_pageblock_migratetype(page) == MIGRATE_MOVABLE)
5360                 return true;
5361
5362         pfn = page_to_pfn(page);
5363         for (found = 0, iter = 0; iter < pageblock_nr_pages; iter++) {
5364                 unsigned long check = pfn + iter;
5365
5366                 if (!pfn_valid_within(check))
5367                         continue;
5368
5369                 page = pfn_to_page(check);
5370                 if (!page_count(page)) {
5371                         if (PageBuddy(page))
5372                                 iter += (1 << page_order(page)) - 1;
5373                         continue;
5374                 }
5375                 if (!PageLRU(page))
5376                         found++;
5377                 /*
5378                  * If there are RECLAIMABLE pages, we need to check it.
5379                  * But now, memory offline itself doesn't call shrink_slab()
5380                  * and it still to be fixed.
5381                  */
5382                 /*
5383                  * If the page is not RAM, page_count()should be 0.
5384                  * we don't need more check. This is an _used_ not-movable page.
5385                  *
5386                  * The problematic thing here is PG_reserved pages. PG_reserved
5387                  * is set to both of a memory hole page and a _used_ kernel
5388                  * page at boot.
5389                  */
5390                 if (found > count)
5391                         return false;
5392         }
5393         return true;
5394 }
5395
5396 bool is_pageblock_removable_nolock(struct page *page)
5397 {
5398         struct zone *zone = page_zone(page);
5399         return __count_immobile_pages(zone, page, 0);
5400 }
5401
5402 int set_migratetype_isolate(struct page *page)
5403 {
5404         struct zone *zone;
5405         unsigned long flags, pfn;
5406         struct memory_isolate_notify arg;
5407         int notifier_ret;
5408         int ret = -EBUSY;
5409
5410         zone = page_zone(page);
5411
5412         spin_lock_irqsave(&zone->lock, flags);
5413
5414         pfn = page_to_pfn(page);
5415         arg.start_pfn = pfn;
5416         arg.nr_pages = pageblock_nr_pages;
5417         arg.pages_found = 0;
5418
5419         /*
5420          * It may be possible to isolate a pageblock even if the
5421          * migratetype is not MIGRATE_MOVABLE. The memory isolation
5422          * notifier chain is used by balloon drivers to return the
5423          * number of pages in a range that are held by the balloon
5424          * driver to shrink memory. If all the pages are accounted for
5425          * by balloons, are free, or on the LRU, isolation can continue.
5426          * Later, for example, when memory hotplug notifier runs, these
5427          * pages reported as "can be isolated" should be isolated(freed)
5428          * by the balloon driver through the memory notifier chain.
5429          */
5430         notifier_ret = memory_isolate_notify(MEM_ISOLATE_COUNT, &arg);
5431         notifier_ret = notifier_to_errno(notifier_ret);
5432         if (notifier_ret)
5433                 goto out;
5434         /*
5435          * FIXME: Now, memory hotplug doesn't call shrink_slab() by itself.
5436          * We just check MOVABLE pages.
5437          */
5438         if (__count_immobile_pages(zone, page, arg.pages_found))
5439                 ret = 0;
5440
5441         /*
5442          * immobile means "not-on-lru" paes. If immobile is larger than
5443          * removable-by-driver pages reported by notifier, we'll fail.
5444          */
5445
5446 out:
5447         if (!ret) {
5448                 set_pageblock_migratetype(page, MIGRATE_ISOLATE);
5449                 move_freepages_block(zone, page, MIGRATE_ISOLATE);
5450         }
5451
5452         spin_unlock_irqrestore(&zone->lock, flags);
5453         if (!ret)
5454                 drain_all_pages();
5455         return ret;
5456 }
5457
5458 void unset_migratetype_isolate(struct page *page)
5459 {
5460         struct zone *zone;
5461         unsigned long flags;
5462         zone = page_zone(page);
5463         spin_lock_irqsave(&zone->lock, flags);
5464         if (get_pageblock_migratetype(page) != MIGRATE_ISOLATE)
5465                 goto out;
5466         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
5467         move_freepages_block(zone, page, MIGRATE_MOVABLE);
5468 out:
5469         spin_unlock_irqrestore(&zone->lock, flags);
5470 }
5471
5472 #ifdef CONFIG_MEMORY_HOTREMOVE
5473 /*
5474  * All pages in the range must be isolated before calling this.
5475  */
5476 void
5477 __offline_isolated_pages(unsigned long start_pfn, unsigned long end_pfn)
5478 {
5479         struct page *page;
5480         struct zone *zone;
5481         int order, i;
5482         unsigned long pfn;
5483         unsigned long flags;
5484         /* find the first valid pfn */
5485         for (pfn = start_pfn; pfn < end_pfn; pfn++)
5486                 if (pfn_valid(pfn))
5487                         break;
5488         if (pfn == end_pfn)
5489                 return;
5490         zone = page_zone(pfn_to_page(pfn));
5491         spin_lock_irqsave(&zone->lock, flags);
5492         pfn = start_pfn;
5493         while (pfn < end_pfn) {
5494                 if (!pfn_valid(pfn)) {
5495                         pfn++;
5496                         continue;
5497                 }
5498                 page = pfn_to_page(pfn);
5499                 BUG_ON(page_count(page));
5500                 BUG_ON(!PageBuddy(page));
5501                 order = page_order(page);
5502 #ifdef CONFIG_DEBUG_VM
5503                 printk(KERN_INFO "remove from free list %lx %d %lx\n",
5504                        pfn, 1 << order, end_pfn);
5505 #endif
5506                 list_del(&page->lru);
5507                 rmv_page_order(page);
5508                 zone->free_area[order].nr_free--;
5509                 __mod_zone_page_state(zone, NR_FREE_PAGES,
5510                                       - (1UL << order));
5511                 for (i = 0; i < (1 << order); i++)
5512                         SetPageReserved((page+i));
5513                 pfn += (1 << order);
5514         }
5515         spin_unlock_irqrestore(&zone->lock, flags);
5516 }
5517 #endif
5518
5519 #ifdef CONFIG_MEMORY_FAILURE
5520 bool is_free_buddy_page(struct page *page)
5521 {
5522         struct zone *zone = page_zone(page);
5523         unsigned long pfn = page_to_pfn(page);
5524         unsigned long flags;
5525         int order;
5526
5527         spin_lock_irqsave(&zone->lock, flags);
5528         for (order = 0; order < MAX_ORDER; order++) {
5529                 struct page *page_head = page - (pfn & ((1 << order) - 1));
5530
5531                 if (PageBuddy(page_head) && page_order(page_head) >= order)
5532                         break;
5533         }
5534         spin_unlock_irqrestore(&zone->lock, flags);
5535
5536         return order < MAX_ORDER;
5537 }
5538 #endif
5539
5540 static struct trace_print_flags pageflag_names[] = {
5541         {1UL << PG_locked,              "locked"        },
5542         {1UL << PG_error,               "error"         },
5543         {1UL << PG_referenced,          "referenced"    },
5544         {1UL << PG_uptodate,            "uptodate"      },
5545         {1UL << PG_dirty,               "dirty"         },
5546         {1UL << PG_lru,                 "lru"           },
5547         {1UL << PG_active,              "active"        },
5548         {1UL << PG_slab,                "slab"          },
5549         {1UL << PG_owner_priv_1,        "owner_priv_1"  },
5550         {1UL << PG_arch_1,              "arch_1"        },
5551         {1UL << PG_reserved,            "reserved"      },
5552         {1UL << PG_private,             "private"       },
5553         {1UL << PG_private_2,           "private_2"     },
5554         {1UL << PG_writeback,           "writeback"     },
5555 #ifdef CONFIG_PAGEFLAGS_EXTENDED
5556         {1UL << PG_head,                "head"          },
5557         {1UL << PG_tail,                "tail"          },
5558 #else
5559         {1UL << PG_compound,            "compound"      },
5560 #endif
5561         {1UL << PG_swapcache,           "swapcache"     },
5562         {1UL << PG_mappedtodisk,        "mappedtodisk"  },
5563         {1UL << PG_reclaim,             "reclaim"       },
5564         {1UL << PG_swapbacked,          "swapbacked"    },
5565         {1UL << PG_unevictable,         "unevictable"   },
5566 #ifdef CONFIG_MMU
5567         {1UL << PG_mlocked,             "mlocked"       },
5568 #endif
5569 #ifdef CONFIG_ARCH_USES_PG_UNCACHED
5570         {1UL << PG_uncached,            "uncached"      },
5571 #endif
5572 #ifdef CONFIG_MEMORY_FAILURE
5573         {1UL << PG_hwpoison,            "hwpoison"      },
5574 #endif
5575         {-1UL,                          NULL            },
5576 };
5577
5578 static void dump_page_flags(unsigned long flags)
5579 {
5580         const char *delim = "";
5581         unsigned long mask;
5582         int i;
5583
5584         printk(KERN_ALERT "page flags: %#lx(", flags);
5585
5586         /* remove zone id */
5587         flags &= (1UL << NR_PAGEFLAGS) - 1;
5588
5589         for (i = 0; pageflag_names[i].name && flags; i++) {
5590
5591                 mask = pageflag_names[i].mask;
5592                 if ((flags & mask) != mask)
5593                         continue;
5594
5595                 flags &= ~mask;
5596                 printk("%s%s", delim, pageflag_names[i].name);
5597                 delim = "|";
5598         }
5599
5600         /* check for left over flags */
5601         if (flags)
5602                 printk("%s%#lx", delim, flags);
5603
5604         printk(")\n");
5605 }
5606
5607 void dump_page(struct page *page)
5608 {
5609         printk(KERN_ALERT
5610                "page:%p count:%d mapcount:%d mapping:%p index:%#lx\n",
5611                 page, atomic_read(&page->_count), page_mapcount(page),
5612                 page->mapping, page->index);
5613         dump_page_flags(page->flags);
5614         mem_cgroup_print_bad_page(page);
5615 }