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