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