mm: create non-atomic version of SetPageReserved for init use
[muen/linux.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/kasan.h>
28 #include <linux/module.h>
29 #include <linux/suspend.h>
30 #include <linux/pagevec.h>
31 #include <linux/blkdev.h>
32 #include <linux/slab.h>
33 #include <linux/ratelimit.h>
34 #include <linux/oom.h>
35 #include <linux/topology.h>
36 #include <linux/sysctl.h>
37 #include <linux/cpu.h>
38 #include <linux/cpuset.h>
39 #include <linux/memory_hotplug.h>
40 #include <linux/nodemask.h>
41 #include <linux/vmalloc.h>
42 #include <linux/vmstat.h>
43 #include <linux/mempolicy.h>
44 #include <linux/memremap.h>
45 #include <linux/stop_machine.h>
46 #include <linux/sort.h>
47 #include <linux/pfn.h>
48 #include <linux/backing-dev.h>
49 #include <linux/fault-inject.h>
50 #include <linux/page-isolation.h>
51 #include <linux/page_ext.h>
52 #include <linux/debugobjects.h>
53 #include <linux/kmemleak.h>
54 #include <linux/compaction.h>
55 #include <trace/events/kmem.h>
56 #include <trace/events/oom.h>
57 #include <linux/prefetch.h>
58 #include <linux/mm_inline.h>
59 #include <linux/migrate.h>
60 #include <linux/hugetlb.h>
61 #include <linux/sched/rt.h>
62 #include <linux/sched/mm.h>
63 #include <linux/page_owner.h>
64 #include <linux/kthread.h>
65 #include <linux/memcontrol.h>
66 #include <linux/ftrace.h>
67 #include <linux/lockdep.h>
68 #include <linux/nmi.h>
69 #include <linux/psi.h>
70
71 #include <asm/sections.h>
72 #include <asm/tlbflush.h>
73 #include <asm/div64.h>
74 #include "internal.h"
75
76 /* prevent >1 _updater_ of zone percpu pageset ->high and ->batch fields */
77 static DEFINE_MUTEX(pcp_batch_high_lock);
78 #define MIN_PERCPU_PAGELIST_FRACTION    (8)
79
80 #ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
81 DEFINE_PER_CPU(int, numa_node);
82 EXPORT_PER_CPU_SYMBOL(numa_node);
83 #endif
84
85 DEFINE_STATIC_KEY_TRUE(vm_numa_stat_key);
86
87 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
88 /*
89  * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
90  * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
91  * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
92  * defined in <linux/topology.h>.
93  */
94 DEFINE_PER_CPU(int, _numa_mem_);                /* Kernel "local memory" node */
95 EXPORT_PER_CPU_SYMBOL(_numa_mem_);
96 int _node_numa_mem_[MAX_NUMNODES];
97 #endif
98
99 /* work_structs for global per-cpu drains */
100 DEFINE_MUTEX(pcpu_drain_mutex);
101 DEFINE_PER_CPU(struct work_struct, pcpu_drain);
102
103 #ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
104 volatile unsigned long latent_entropy __latent_entropy;
105 EXPORT_SYMBOL(latent_entropy);
106 #endif
107
108 /*
109  * Array of node states.
110  */
111 nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
112         [N_POSSIBLE] = NODE_MASK_ALL,
113         [N_ONLINE] = { { [0] = 1UL } },
114 #ifndef CONFIG_NUMA
115         [N_NORMAL_MEMORY] = { { [0] = 1UL } },
116 #ifdef CONFIG_HIGHMEM
117         [N_HIGH_MEMORY] = { { [0] = 1UL } },
118 #endif
119         [N_MEMORY] = { { [0] = 1UL } },
120         [N_CPU] = { { [0] = 1UL } },
121 #endif  /* NUMA */
122 };
123 EXPORT_SYMBOL(node_states);
124
125 /* Protect totalram_pages and zone->managed_pages */
126 static DEFINE_SPINLOCK(managed_page_count_lock);
127
128 unsigned long totalram_pages __read_mostly;
129 unsigned long totalreserve_pages __read_mostly;
130 unsigned long totalcma_pages __read_mostly;
131
132 int percpu_pagelist_fraction;
133 gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
134
135 /*
136  * A cached value of the page's pageblock's migratetype, used when the page is
137  * put on a pcplist. Used to avoid the pageblock migratetype lookup when
138  * freeing from pcplists in most cases, at the cost of possibly becoming stale.
139  * Also the migratetype set in the page does not necessarily match the pcplist
140  * index, e.g. page might have MIGRATE_CMA set but be on a pcplist with any
141  * other index - this ensures that it will be put on the correct CMA freelist.
142  */
143 static inline int get_pcppage_migratetype(struct page *page)
144 {
145         return page->index;
146 }
147
148 static inline void set_pcppage_migratetype(struct page *page, int migratetype)
149 {
150         page->index = migratetype;
151 }
152
153 #ifdef CONFIG_PM_SLEEP
154 /*
155  * The following functions are used by the suspend/hibernate code to temporarily
156  * change gfp_allowed_mask in order to avoid using I/O during memory allocations
157  * while devices are suspended.  To avoid races with the suspend/hibernate code,
158  * they should always be called with system_transition_mutex held
159  * (gfp_allowed_mask also should only be modified with system_transition_mutex
160  * held, unless the suspend/hibernate code is guaranteed not to run in parallel
161  * with that modification).
162  */
163
164 static gfp_t saved_gfp_mask;
165
166 void pm_restore_gfp_mask(void)
167 {
168         WARN_ON(!mutex_is_locked(&system_transition_mutex));
169         if (saved_gfp_mask) {
170                 gfp_allowed_mask = saved_gfp_mask;
171                 saved_gfp_mask = 0;
172         }
173 }
174
175 void pm_restrict_gfp_mask(void)
176 {
177         WARN_ON(!mutex_is_locked(&system_transition_mutex));
178         WARN_ON(saved_gfp_mask);
179         saved_gfp_mask = gfp_allowed_mask;
180         gfp_allowed_mask &= ~(__GFP_IO | __GFP_FS);
181 }
182
183 bool pm_suspended_storage(void)
184 {
185         if ((gfp_allowed_mask & (__GFP_IO | __GFP_FS)) == (__GFP_IO | __GFP_FS))
186                 return false;
187         return true;
188 }
189 #endif /* CONFIG_PM_SLEEP */
190
191 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
192 unsigned int pageblock_order __read_mostly;
193 #endif
194
195 static void __free_pages_ok(struct page *page, unsigned int order);
196
197 /*
198  * results with 256, 32 in the lowmem_reserve sysctl:
199  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
200  *      1G machine -> (16M dma, 784M normal, 224M high)
201  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
202  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
203  *      HIGHMEM allocation will leave (224M+784M)/256 of ram reserved in ZONE_DMA
204  *
205  * TBD: should special case ZONE_DMA32 machines here - in those we normally
206  * don't need any ZONE_NORMAL reservation
207  */
208 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES] = {
209 #ifdef CONFIG_ZONE_DMA
210         [ZONE_DMA] = 256,
211 #endif
212 #ifdef CONFIG_ZONE_DMA32
213         [ZONE_DMA32] = 256,
214 #endif
215         [ZONE_NORMAL] = 32,
216 #ifdef CONFIG_HIGHMEM
217         [ZONE_HIGHMEM] = 0,
218 #endif
219         [ZONE_MOVABLE] = 0,
220 };
221
222 EXPORT_SYMBOL(totalram_pages);
223
224 static char * const zone_names[MAX_NR_ZONES] = {
225 #ifdef CONFIG_ZONE_DMA
226          "DMA",
227 #endif
228 #ifdef CONFIG_ZONE_DMA32
229          "DMA32",
230 #endif
231          "Normal",
232 #ifdef CONFIG_HIGHMEM
233          "HighMem",
234 #endif
235          "Movable",
236 #ifdef CONFIG_ZONE_DEVICE
237          "Device",
238 #endif
239 };
240
241 char * const migratetype_names[MIGRATE_TYPES] = {
242         "Unmovable",
243         "Movable",
244         "Reclaimable",
245         "HighAtomic",
246 #ifdef CONFIG_CMA
247         "CMA",
248 #endif
249 #ifdef CONFIG_MEMORY_ISOLATION
250         "Isolate",
251 #endif
252 };
253
254 compound_page_dtor * const compound_page_dtors[] = {
255         NULL,
256         free_compound_page,
257 #ifdef CONFIG_HUGETLB_PAGE
258         free_huge_page,
259 #endif
260 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
261         free_transhuge_page,
262 #endif
263 };
264
265 int min_free_kbytes = 1024;
266 int user_min_free_kbytes = -1;
267 int watermark_scale_factor = 10;
268
269 static unsigned long nr_kernel_pages __meminitdata;
270 static unsigned long nr_all_pages __meminitdata;
271 static unsigned long dma_reserve __meminitdata;
272
273 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
274 static unsigned long arch_zone_lowest_possible_pfn[MAX_NR_ZONES] __meminitdata;
275 static unsigned long arch_zone_highest_possible_pfn[MAX_NR_ZONES] __meminitdata;
276 static unsigned long required_kernelcore __initdata;
277 static unsigned long required_kernelcore_percent __initdata;
278 static unsigned long required_movablecore __initdata;
279 static unsigned long required_movablecore_percent __initdata;
280 static unsigned long zone_movable_pfn[MAX_NUMNODES] __meminitdata;
281 static bool mirrored_kernelcore __meminitdata;
282
283 /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
284 int movable_zone;
285 EXPORT_SYMBOL(movable_zone);
286 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
287
288 #if MAX_NUMNODES > 1
289 int nr_node_ids __read_mostly = MAX_NUMNODES;
290 int nr_online_nodes __read_mostly = 1;
291 EXPORT_SYMBOL(nr_node_ids);
292 EXPORT_SYMBOL(nr_online_nodes);
293 #endif
294
295 int page_group_by_mobility_disabled __read_mostly;
296
297 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
298 /* Returns true if the struct page for the pfn is uninitialised */
299 static inline bool __meminit early_page_uninitialised(unsigned long pfn)
300 {
301         int nid = early_pfn_to_nid(pfn);
302
303         if (node_online(nid) && pfn >= NODE_DATA(nid)->first_deferred_pfn)
304                 return true;
305
306         return false;
307 }
308
309 /*
310  * Returns false when the remaining initialisation should be deferred until
311  * later in the boot cycle when it can be parallelised.
312  */
313 static inline bool update_defer_init(pg_data_t *pgdat,
314                                 unsigned long pfn, unsigned long zone_end,
315                                 unsigned long *nr_initialised)
316 {
317         /* Always populate low zones for address-constrained allocations */
318         if (zone_end < pgdat_end_pfn(pgdat))
319                 return true;
320         (*nr_initialised)++;
321         if ((*nr_initialised > pgdat->static_init_pgcnt) &&
322             (pfn & (PAGES_PER_SECTION - 1)) == 0) {
323                 pgdat->first_deferred_pfn = pfn;
324                 return false;
325         }
326
327         return true;
328 }
329 #else
330 static inline bool early_page_uninitialised(unsigned long pfn)
331 {
332         return false;
333 }
334
335 static inline bool update_defer_init(pg_data_t *pgdat,
336                                 unsigned long pfn, unsigned long zone_end,
337                                 unsigned long *nr_initialised)
338 {
339         return true;
340 }
341 #endif
342
343 /* Return a pointer to the bitmap storing bits affecting a block of pages */
344 static inline unsigned long *get_pageblock_bitmap(struct page *page,
345                                                         unsigned long pfn)
346 {
347 #ifdef CONFIG_SPARSEMEM
348         return __pfn_to_section(pfn)->pageblock_flags;
349 #else
350         return page_zone(page)->pageblock_flags;
351 #endif /* CONFIG_SPARSEMEM */
352 }
353
354 static inline int pfn_to_bitidx(struct page *page, unsigned long pfn)
355 {
356 #ifdef CONFIG_SPARSEMEM
357         pfn &= (PAGES_PER_SECTION-1);
358         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
359 #else
360         pfn = pfn - round_down(page_zone(page)->zone_start_pfn, pageblock_nr_pages);
361         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
362 #endif /* CONFIG_SPARSEMEM */
363 }
364
365 /**
366  * get_pfnblock_flags_mask - Return the requested group of flags for the pageblock_nr_pages block of pages
367  * @page: The page within the block of interest
368  * @pfn: The target page frame number
369  * @end_bitidx: The last bit of interest to retrieve
370  * @mask: mask of bits that the caller is interested in
371  *
372  * Return: pageblock_bits flags
373  */
374 static __always_inline unsigned long __get_pfnblock_flags_mask(struct page *page,
375                                         unsigned long pfn,
376                                         unsigned long end_bitidx,
377                                         unsigned long mask)
378 {
379         unsigned long *bitmap;
380         unsigned long bitidx, word_bitidx;
381         unsigned long word;
382
383         bitmap = get_pageblock_bitmap(page, pfn);
384         bitidx = pfn_to_bitidx(page, pfn);
385         word_bitidx = bitidx / BITS_PER_LONG;
386         bitidx &= (BITS_PER_LONG-1);
387
388         word = bitmap[word_bitidx];
389         bitidx += end_bitidx;
390         return (word >> (BITS_PER_LONG - bitidx - 1)) & mask;
391 }
392
393 unsigned long get_pfnblock_flags_mask(struct page *page, unsigned long pfn,
394                                         unsigned long end_bitidx,
395                                         unsigned long mask)
396 {
397         return __get_pfnblock_flags_mask(page, pfn, end_bitidx, mask);
398 }
399
400 static __always_inline int get_pfnblock_migratetype(struct page *page, unsigned long pfn)
401 {
402         return __get_pfnblock_flags_mask(page, pfn, PB_migrate_end, MIGRATETYPE_MASK);
403 }
404
405 /**
406  * set_pfnblock_flags_mask - Set the requested group of flags for a pageblock_nr_pages block of pages
407  * @page: The page within the block of interest
408  * @flags: The flags to set
409  * @pfn: The target page frame number
410  * @end_bitidx: The last bit of interest
411  * @mask: mask of bits that the caller is interested in
412  */
413 void set_pfnblock_flags_mask(struct page *page, unsigned long flags,
414                                         unsigned long pfn,
415                                         unsigned long end_bitidx,
416                                         unsigned long mask)
417 {
418         unsigned long *bitmap;
419         unsigned long bitidx, word_bitidx;
420         unsigned long old_word, word;
421
422         BUILD_BUG_ON(NR_PAGEBLOCK_BITS != 4);
423
424         bitmap = get_pageblock_bitmap(page, pfn);
425         bitidx = pfn_to_bitidx(page, pfn);
426         word_bitidx = bitidx / BITS_PER_LONG;
427         bitidx &= (BITS_PER_LONG-1);
428
429         VM_BUG_ON_PAGE(!zone_spans_pfn(page_zone(page), pfn), page);
430
431         bitidx += end_bitidx;
432         mask <<= (BITS_PER_LONG - bitidx - 1);
433         flags <<= (BITS_PER_LONG - bitidx - 1);
434
435         word = READ_ONCE(bitmap[word_bitidx]);
436         for (;;) {
437                 old_word = cmpxchg(&bitmap[word_bitidx], word, (word & ~mask) | flags);
438                 if (word == old_word)
439                         break;
440                 word = old_word;
441         }
442 }
443
444 void set_pageblock_migratetype(struct page *page, int migratetype)
445 {
446         if (unlikely(page_group_by_mobility_disabled &&
447                      migratetype < MIGRATE_PCPTYPES))
448                 migratetype = MIGRATE_UNMOVABLE;
449
450         set_pageblock_flags_group(page, (unsigned long)migratetype,
451                                         PB_migrate, PB_migrate_end);
452 }
453
454 #ifdef CONFIG_DEBUG_VM
455 static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
456 {
457         int ret = 0;
458         unsigned seq;
459         unsigned long pfn = page_to_pfn(page);
460         unsigned long sp, start_pfn;
461
462         do {
463                 seq = zone_span_seqbegin(zone);
464                 start_pfn = zone->zone_start_pfn;
465                 sp = zone->spanned_pages;
466                 if (!zone_spans_pfn(zone, pfn))
467                         ret = 1;
468         } while (zone_span_seqretry(zone, seq));
469
470         if (ret)
471                 pr_err("page 0x%lx outside node %d zone %s [ 0x%lx - 0x%lx ]\n",
472                         pfn, zone_to_nid(zone), zone->name,
473                         start_pfn, start_pfn + sp);
474
475         return ret;
476 }
477
478 static int page_is_consistent(struct zone *zone, struct page *page)
479 {
480         if (!pfn_valid_within(page_to_pfn(page)))
481                 return 0;
482         if (zone != page_zone(page))
483                 return 0;
484
485         return 1;
486 }
487 /*
488  * Temporary debugging check for pages not lying within a given zone.
489  */
490 static int __maybe_unused bad_range(struct zone *zone, struct page *page)
491 {
492         if (page_outside_zone_boundaries(zone, page))
493                 return 1;
494         if (!page_is_consistent(zone, page))
495                 return 1;
496
497         return 0;
498 }
499 #else
500 static inline int __maybe_unused bad_range(struct zone *zone, struct page *page)
501 {
502         return 0;
503 }
504 #endif
505
506 static void bad_page(struct page *page, const char *reason,
507                 unsigned long bad_flags)
508 {
509         static unsigned long resume;
510         static unsigned long nr_shown;
511         static unsigned long nr_unshown;
512
513         /*
514          * Allow a burst of 60 reports, then keep quiet for that minute;
515          * or allow a steady drip of one report per second.
516          */
517         if (nr_shown == 60) {
518                 if (time_before(jiffies, resume)) {
519                         nr_unshown++;
520                         goto out;
521                 }
522                 if (nr_unshown) {
523                         pr_alert(
524                               "BUG: Bad page state: %lu messages suppressed\n",
525                                 nr_unshown);
526                         nr_unshown = 0;
527                 }
528                 nr_shown = 0;
529         }
530         if (nr_shown++ == 0)
531                 resume = jiffies + 60 * HZ;
532
533         pr_alert("BUG: Bad page state in process %s  pfn:%05lx\n",
534                 current->comm, page_to_pfn(page));
535         __dump_page(page, reason);
536         bad_flags &= page->flags;
537         if (bad_flags)
538                 pr_alert("bad because of flags: %#lx(%pGp)\n",
539                                                 bad_flags, &bad_flags);
540         dump_page_owner(page);
541
542         print_modules();
543         dump_stack();
544 out:
545         /* Leave bad fields for debug, except PageBuddy could make trouble */
546         page_mapcount_reset(page); /* remove PageBuddy */
547         add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE);
548 }
549
550 /*
551  * Higher-order pages are called "compound pages".  They are structured thusly:
552  *
553  * The first PAGE_SIZE page is called the "head page" and have PG_head set.
554  *
555  * The remaining PAGE_SIZE pages are called "tail pages". PageTail() is encoded
556  * in bit 0 of page->compound_head. The rest of bits is pointer to head page.
557  *
558  * The first tail page's ->compound_dtor holds the offset in array of compound
559  * page destructors. See compound_page_dtors.
560  *
561  * The first tail page's ->compound_order holds the order of allocation.
562  * This usage means that zero-order pages may not be compound.
563  */
564
565 void free_compound_page(struct page *page)
566 {
567         __free_pages_ok(page, compound_order(page));
568 }
569
570 void prep_compound_page(struct page *page, unsigned int order)
571 {
572         int i;
573         int nr_pages = 1 << order;
574
575         set_compound_page_dtor(page, COMPOUND_PAGE_DTOR);
576         set_compound_order(page, order);
577         __SetPageHead(page);
578         for (i = 1; i < nr_pages; i++) {
579                 struct page *p = page + i;
580                 set_page_count(p, 0);
581                 p->mapping = TAIL_MAPPING;
582                 set_compound_head(p, page);
583         }
584         atomic_set(compound_mapcount_ptr(page), -1);
585 }
586
587 #ifdef CONFIG_DEBUG_PAGEALLOC
588 unsigned int _debug_guardpage_minorder;
589 bool _debug_pagealloc_enabled __read_mostly
590                         = IS_ENABLED(CONFIG_DEBUG_PAGEALLOC_ENABLE_DEFAULT);
591 EXPORT_SYMBOL(_debug_pagealloc_enabled);
592 bool _debug_guardpage_enabled __read_mostly;
593
594 static int __init early_debug_pagealloc(char *buf)
595 {
596         if (!buf)
597                 return -EINVAL;
598         return kstrtobool(buf, &_debug_pagealloc_enabled);
599 }
600 early_param("debug_pagealloc", early_debug_pagealloc);
601
602 static bool need_debug_guardpage(void)
603 {
604         /* If we don't use debug_pagealloc, we don't need guard page */
605         if (!debug_pagealloc_enabled())
606                 return false;
607
608         if (!debug_guardpage_minorder())
609                 return false;
610
611         return true;
612 }
613
614 static void init_debug_guardpage(void)
615 {
616         if (!debug_pagealloc_enabled())
617                 return;
618
619         if (!debug_guardpage_minorder())
620                 return;
621
622         _debug_guardpage_enabled = true;
623 }
624
625 struct page_ext_operations debug_guardpage_ops = {
626         .need = need_debug_guardpage,
627         .init = init_debug_guardpage,
628 };
629
630 static int __init debug_guardpage_minorder_setup(char *buf)
631 {
632         unsigned long res;
633
634         if (kstrtoul(buf, 10, &res) < 0 ||  res > MAX_ORDER / 2) {
635                 pr_err("Bad debug_guardpage_minorder value\n");
636                 return 0;
637         }
638         _debug_guardpage_minorder = res;
639         pr_info("Setting debug_guardpage_minorder to %lu\n", res);
640         return 0;
641 }
642 early_param("debug_guardpage_minorder", debug_guardpage_minorder_setup);
643
644 static inline bool set_page_guard(struct zone *zone, struct page *page,
645                                 unsigned int order, int migratetype)
646 {
647         struct page_ext *page_ext;
648
649         if (!debug_guardpage_enabled())
650                 return false;
651
652         if (order >= debug_guardpage_minorder())
653                 return false;
654
655         page_ext = lookup_page_ext(page);
656         if (unlikely(!page_ext))
657                 return false;
658
659         __set_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);
660
661         INIT_LIST_HEAD(&page->lru);
662         set_page_private(page, order);
663         /* Guard pages are not available for any usage */
664         __mod_zone_freepage_state(zone, -(1 << order), migratetype);
665
666         return true;
667 }
668
669 static inline void clear_page_guard(struct zone *zone, struct page *page,
670                                 unsigned int order, int migratetype)
671 {
672         struct page_ext *page_ext;
673
674         if (!debug_guardpage_enabled())
675                 return;
676
677         page_ext = lookup_page_ext(page);
678         if (unlikely(!page_ext))
679                 return;
680
681         __clear_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);
682
683         set_page_private(page, 0);
684         if (!is_migrate_isolate(migratetype))
685                 __mod_zone_freepage_state(zone, (1 << order), migratetype);
686 }
687 #else
688 struct page_ext_operations debug_guardpage_ops;
689 static inline bool set_page_guard(struct zone *zone, struct page *page,
690                         unsigned int order, int migratetype) { return false; }
691 static inline void clear_page_guard(struct zone *zone, struct page *page,
692                                 unsigned int order, int migratetype) {}
693 #endif
694
695 static inline void set_page_order(struct page *page, unsigned int order)
696 {
697         set_page_private(page, order);
698         __SetPageBuddy(page);
699 }
700
701 static inline void rmv_page_order(struct page *page)
702 {
703         __ClearPageBuddy(page);
704         set_page_private(page, 0);
705 }
706
707 /*
708  * This function checks whether a page is free && is the buddy
709  * we can coalesce a page and its buddy if
710  * (a) the buddy is not in a hole (check before calling!) &&
711  * (b) the buddy is in the buddy system &&
712  * (c) a page and its buddy have the same order &&
713  * (d) a page and its buddy are in the same zone.
714  *
715  * For recording whether a page is in the buddy system, we set PageBuddy.
716  * Setting, clearing, and testing PageBuddy is serialized by zone->lock.
717  *
718  * For recording page's order, we use page_private(page).
719  */
720 static inline int page_is_buddy(struct page *page, struct page *buddy,
721                                                         unsigned int order)
722 {
723         if (page_is_guard(buddy) && page_order(buddy) == order) {
724                 if (page_zone_id(page) != page_zone_id(buddy))
725                         return 0;
726
727                 VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);
728
729                 return 1;
730         }
731
732         if (PageBuddy(buddy) && page_order(buddy) == order) {
733                 /*
734                  * zone check is done late to avoid uselessly
735                  * calculating zone/node ids for pages that could
736                  * never merge.
737                  */
738                 if (page_zone_id(page) != page_zone_id(buddy))
739                         return 0;
740
741                 VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);
742
743                 return 1;
744         }
745         return 0;
746 }
747
748 /*
749  * Freeing function for a buddy system allocator.
750  *
751  * The concept of a buddy system is to maintain direct-mapped table
752  * (containing bit values) for memory blocks of various "orders".
753  * The bottom level table contains the map for the smallest allocatable
754  * units of memory (here, pages), and each level above it describes
755  * pairs of units from the levels below, hence, "buddies".
756  * At a high level, all that happens here is marking the table entry
757  * at the bottom level available, and propagating the changes upward
758  * as necessary, plus some accounting needed to play nicely with other
759  * parts of the VM system.
760  * At each level, we keep a list of pages, which are heads of continuous
761  * free pages of length of (1 << order) and marked with PageBuddy.
762  * Page's order is recorded in page_private(page) field.
763  * So when we are allocating or freeing one, we can derive the state of the
764  * other.  That is, if we allocate a small block, and both were
765  * free, the remainder of the region must be split into blocks.
766  * If a block is freed, and its buddy is also free, then this
767  * triggers coalescing into a block of larger size.
768  *
769  * -- nyc
770  */
771
772 static inline void __free_one_page(struct page *page,
773                 unsigned long pfn,
774                 struct zone *zone, unsigned int order,
775                 int migratetype)
776 {
777         unsigned long combined_pfn;
778         unsigned long uninitialized_var(buddy_pfn);
779         struct page *buddy;
780         unsigned int max_order;
781
782         max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
783
784         VM_BUG_ON(!zone_is_initialized(zone));
785         VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);
786
787         VM_BUG_ON(migratetype == -1);
788         if (likely(!is_migrate_isolate(migratetype)))
789                 __mod_zone_freepage_state(zone, 1 << order, migratetype);
790
791         VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
792         VM_BUG_ON_PAGE(bad_range(zone, page), page);
793
794 continue_merging:
795         while (order < max_order - 1) {
796                 buddy_pfn = __find_buddy_pfn(pfn, order);
797                 buddy = page + (buddy_pfn - pfn);
798
799                 if (!pfn_valid_within(buddy_pfn))
800                         goto done_merging;
801                 if (!page_is_buddy(page, buddy, order))
802                         goto done_merging;
803                 /*
804                  * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
805                  * merge with it and move up one order.
806                  */
807                 if (page_is_guard(buddy)) {
808                         clear_page_guard(zone, buddy, order, migratetype);
809                 } else {
810                         list_del(&buddy->lru);
811                         zone->free_area[order].nr_free--;
812                         rmv_page_order(buddy);
813                 }
814                 combined_pfn = buddy_pfn & pfn;
815                 page = page + (combined_pfn - pfn);
816                 pfn = combined_pfn;
817                 order++;
818         }
819         if (max_order < MAX_ORDER) {
820                 /* If we are here, it means order is >= pageblock_order.
821                  * We want to prevent merge between freepages on isolate
822                  * pageblock and normal pageblock. Without this, pageblock
823                  * isolation could cause incorrect freepage or CMA accounting.
824                  *
825                  * We don't want to hit this code for the more frequent
826                  * low-order merging.
827                  */
828                 if (unlikely(has_isolate_pageblock(zone))) {
829                         int buddy_mt;
830
831                         buddy_pfn = __find_buddy_pfn(pfn, order);
832                         buddy = page + (buddy_pfn - pfn);
833                         buddy_mt = get_pageblock_migratetype(buddy);
834
835                         if (migratetype != buddy_mt
836                                         && (is_migrate_isolate(migratetype) ||
837                                                 is_migrate_isolate(buddy_mt)))
838                                 goto done_merging;
839                 }
840                 max_order++;
841                 goto continue_merging;
842         }
843
844 done_merging:
845         set_page_order(page, order);
846
847         /*
848          * If this is not the largest possible page, check if the buddy
849          * of the next-highest order is free. If it is, it's possible
850          * that pages are being freed that will coalesce soon. In case,
851          * that is happening, add the free page to the tail of the list
852          * so it's less likely to be used soon and more likely to be merged
853          * as a higher order page
854          */
855         if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)) {
856                 struct page *higher_page, *higher_buddy;
857                 combined_pfn = buddy_pfn & pfn;
858                 higher_page = page + (combined_pfn - pfn);
859                 buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
860                 higher_buddy = higher_page + (buddy_pfn - combined_pfn);
861                 if (pfn_valid_within(buddy_pfn) &&
862                     page_is_buddy(higher_page, higher_buddy, order + 1)) {
863                         list_add_tail(&page->lru,
864                                 &zone->free_area[order].free_list[migratetype]);
865                         goto out;
866                 }
867         }
868
869         list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
870 out:
871         zone->free_area[order].nr_free++;
872 }
873
874 /*
875  * A bad page could be due to a number of fields. Instead of multiple branches,
876  * try and check multiple fields with one check. The caller must do a detailed
877  * check if necessary.
878  */
879 static inline bool page_expected_state(struct page *page,
880                                         unsigned long check_flags)
881 {
882         if (unlikely(atomic_read(&page->_mapcount) != -1))
883                 return false;
884
885         if (unlikely((unsigned long)page->mapping |
886                         page_ref_count(page) |
887 #ifdef CONFIG_MEMCG
888                         (unsigned long)page->mem_cgroup |
889 #endif
890                         (page->flags & check_flags)))
891                 return false;
892
893         return true;
894 }
895
896 static void free_pages_check_bad(struct page *page)
897 {
898         const char *bad_reason;
899         unsigned long bad_flags;
900
901         bad_reason = NULL;
902         bad_flags = 0;
903
904         if (unlikely(atomic_read(&page->_mapcount) != -1))
905                 bad_reason = "nonzero mapcount";
906         if (unlikely(page->mapping != NULL))
907                 bad_reason = "non-NULL mapping";
908         if (unlikely(page_ref_count(page) != 0))
909                 bad_reason = "nonzero _refcount";
910         if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_FREE)) {
911                 bad_reason = "PAGE_FLAGS_CHECK_AT_FREE flag(s) set";
912                 bad_flags = PAGE_FLAGS_CHECK_AT_FREE;
913         }
914 #ifdef CONFIG_MEMCG
915         if (unlikely(page->mem_cgroup))
916                 bad_reason = "page still charged to cgroup";
917 #endif
918         bad_page(page, bad_reason, bad_flags);
919 }
920
921 static inline int free_pages_check(struct page *page)
922 {
923         if (likely(page_expected_state(page, PAGE_FLAGS_CHECK_AT_FREE)))
924                 return 0;
925
926         /* Something has gone sideways, find it */
927         free_pages_check_bad(page);
928         return 1;
929 }
930
931 static int free_tail_pages_check(struct page *head_page, struct page *page)
932 {
933         int ret = 1;
934
935         /*
936          * We rely page->lru.next never has bit 0 set, unless the page
937          * is PageTail(). Let's make sure that's true even for poisoned ->lru.
938          */
939         BUILD_BUG_ON((unsigned long)LIST_POISON1 & 1);
940
941         if (!IS_ENABLED(CONFIG_DEBUG_VM)) {
942                 ret = 0;
943                 goto out;
944         }
945         switch (page - head_page) {
946         case 1:
947                 /* the first tail page: ->mapping may be compound_mapcount() */
948                 if (unlikely(compound_mapcount(page))) {
949                         bad_page(page, "nonzero compound_mapcount", 0);
950                         goto out;
951                 }
952                 break;
953         case 2:
954                 /*
955                  * the second tail page: ->mapping is
956                  * deferred_list.next -- ignore value.
957                  */
958                 break;
959         default:
960                 if (page->mapping != TAIL_MAPPING) {
961                         bad_page(page, "corrupted mapping in tail page", 0);
962                         goto out;
963                 }
964                 break;
965         }
966         if (unlikely(!PageTail(page))) {
967                 bad_page(page, "PageTail not set", 0);
968                 goto out;
969         }
970         if (unlikely(compound_head(page) != head_page)) {
971                 bad_page(page, "compound_head not consistent", 0);
972                 goto out;
973         }
974         ret = 0;
975 out:
976         page->mapping = NULL;
977         clear_compound_head(page);
978         return ret;
979 }
980
981 static __always_inline bool free_pages_prepare(struct page *page,
982                                         unsigned int order, bool check_free)
983 {
984         int bad = 0;
985
986         VM_BUG_ON_PAGE(PageTail(page), page);
987
988         trace_mm_page_free(page, order);
989
990         /*
991          * Check tail pages before head page information is cleared to
992          * avoid checking PageCompound for order-0 pages.
993          */
994         if (unlikely(order)) {
995                 bool compound = PageCompound(page);
996                 int i;
997
998                 VM_BUG_ON_PAGE(compound && compound_order(page) != order, page);
999
1000                 if (compound)
1001                         ClearPageDoubleMap(page);
1002                 for (i = 1; i < (1 << order); i++) {
1003                         if (compound)
1004                                 bad += free_tail_pages_check(page, page + i);
1005                         if (unlikely(free_pages_check(page + i))) {
1006                                 bad++;
1007                                 continue;
1008                         }
1009                         (page + i)->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
1010                 }
1011         }
1012         if (PageMappingFlags(page))
1013                 page->mapping = NULL;
1014         if (memcg_kmem_enabled() && PageKmemcg(page))
1015                 memcg_kmem_uncharge(page, order);
1016         if (check_free)
1017                 bad += free_pages_check(page);
1018         if (bad)
1019                 return false;
1020
1021         page_cpupid_reset_last(page);
1022         page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
1023         reset_page_owner(page, order);
1024
1025         if (!PageHighMem(page)) {
1026                 debug_check_no_locks_freed(page_address(page),
1027                                            PAGE_SIZE << order);
1028                 debug_check_no_obj_freed(page_address(page),
1029                                            PAGE_SIZE << order);
1030         }
1031         arch_free_page(page, order);
1032         kernel_poison_pages(page, 1 << order, 0);
1033         kernel_map_pages(page, 1 << order, 0);
1034         kasan_free_pages(page, order);
1035
1036         return true;
1037 }
1038
1039 #ifdef CONFIG_DEBUG_VM
1040 static inline bool free_pcp_prepare(struct page *page)
1041 {
1042         return free_pages_prepare(page, 0, true);
1043 }
1044
1045 static inline bool bulkfree_pcp_prepare(struct page *page)
1046 {
1047         return false;
1048 }
1049 #else
1050 static bool free_pcp_prepare(struct page *page)
1051 {
1052         return free_pages_prepare(page, 0, false);
1053 }
1054
1055 static bool bulkfree_pcp_prepare(struct page *page)
1056 {
1057         return free_pages_check(page);
1058 }
1059 #endif /* CONFIG_DEBUG_VM */
1060
1061 static inline void prefetch_buddy(struct page *page)
1062 {
1063         unsigned long pfn = page_to_pfn(page);
1064         unsigned long buddy_pfn = __find_buddy_pfn(pfn, 0);
1065         struct page *buddy = page + (buddy_pfn - pfn);
1066
1067         prefetch(buddy);
1068 }
1069
1070 /*
1071  * Frees a number of pages from the PCP lists
1072  * Assumes all pages on list are in same zone, and of same order.
1073  * count is the number of pages to free.
1074  *
1075  * If the zone was previously in an "all pages pinned" state then look to
1076  * see if this freeing clears that state.
1077  *
1078  * And clear the zone's pages_scanned counter, to hold off the "all pages are
1079  * pinned" detection logic.
1080  */
1081 static void free_pcppages_bulk(struct zone *zone, int count,
1082                                         struct per_cpu_pages *pcp)
1083 {
1084         int migratetype = 0;
1085         int batch_free = 0;
1086         int prefetch_nr = 0;
1087         bool isolated_pageblocks;
1088         struct page *page, *tmp;
1089         LIST_HEAD(head);
1090
1091         while (count) {
1092                 struct list_head *list;
1093
1094                 /*
1095                  * Remove pages from lists in a round-robin fashion. A
1096                  * batch_free count is maintained that is incremented when an
1097                  * empty list is encountered.  This is so more pages are freed
1098                  * off fuller lists instead of spinning excessively around empty
1099                  * lists
1100                  */
1101                 do {
1102                         batch_free++;
1103                         if (++migratetype == MIGRATE_PCPTYPES)
1104                                 migratetype = 0;
1105                         list = &pcp->lists[migratetype];
1106                 } while (list_empty(list));
1107
1108                 /* This is the only non-empty list. Free them all. */
1109                 if (batch_free == MIGRATE_PCPTYPES)
1110                         batch_free = count;
1111
1112                 do {
1113                         page = list_last_entry(list, struct page, lru);
1114                         /* must delete to avoid corrupting pcp list */
1115                         list_del(&page->lru);
1116                         pcp->count--;
1117
1118                         if (bulkfree_pcp_prepare(page))
1119                                 continue;
1120
1121                         list_add_tail(&page->lru, &head);
1122
1123                         /*
1124                          * We are going to put the page back to the global
1125                          * pool, prefetch its buddy to speed up later access
1126                          * under zone->lock. It is believed the overhead of
1127                          * an additional test and calculating buddy_pfn here
1128                          * can be offset by reduced memory latency later. To
1129                          * avoid excessive prefetching due to large count, only
1130                          * prefetch buddy for the first pcp->batch nr of pages.
1131                          */
1132                         if (prefetch_nr++ < pcp->batch)
1133                                 prefetch_buddy(page);
1134                 } while (--count && --batch_free && !list_empty(list));
1135         }
1136
1137         spin_lock(&zone->lock);
1138         isolated_pageblocks = has_isolate_pageblock(zone);
1139
1140         /*
1141          * Use safe version since after __free_one_page(),
1142          * page->lru.next will not point to original list.
1143          */
1144         list_for_each_entry_safe(page, tmp, &head, lru) {
1145                 int mt = get_pcppage_migratetype(page);
1146                 /* MIGRATE_ISOLATE page should not go to pcplists */
1147                 VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
1148                 /* Pageblock could have been isolated meanwhile */
1149                 if (unlikely(isolated_pageblocks))
1150                         mt = get_pageblock_migratetype(page);
1151
1152                 __free_one_page(page, page_to_pfn(page), zone, 0, mt);
1153                 trace_mm_page_pcpu_drain(page, 0, mt);
1154         }
1155         spin_unlock(&zone->lock);
1156 }
1157
1158 static void free_one_page(struct zone *zone,
1159                                 struct page *page, unsigned long pfn,
1160                                 unsigned int order,
1161                                 int migratetype)
1162 {
1163         spin_lock(&zone->lock);
1164         if (unlikely(has_isolate_pageblock(zone) ||
1165                 is_migrate_isolate(migratetype))) {
1166                 migratetype = get_pfnblock_migratetype(page, pfn);
1167         }
1168         __free_one_page(page, pfn, zone, order, migratetype);
1169         spin_unlock(&zone->lock);
1170 }
1171
1172 static void __meminit __init_single_page(struct page *page, unsigned long pfn,
1173                                 unsigned long zone, int nid)
1174 {
1175         mm_zero_struct_page(page);
1176         set_page_links(page, zone, nid, pfn);
1177         init_page_count(page);
1178         page_mapcount_reset(page);
1179         page_cpupid_reset_last(page);
1180
1181         INIT_LIST_HEAD(&page->lru);
1182 #ifdef WANT_PAGE_VIRTUAL
1183         /* The shift won't overflow because ZONE_NORMAL is below 4G. */
1184         if (!is_highmem_idx(zone))
1185                 set_page_address(page, __va(pfn << PAGE_SHIFT));
1186 #endif
1187 }
1188
1189 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1190 static void __meminit init_reserved_page(unsigned long pfn)
1191 {
1192         pg_data_t *pgdat;
1193         int nid, zid;
1194
1195         if (!early_page_uninitialised(pfn))
1196                 return;
1197
1198         nid = early_pfn_to_nid(pfn);
1199         pgdat = NODE_DATA(nid);
1200
1201         for (zid = 0; zid < MAX_NR_ZONES; zid++) {
1202                 struct zone *zone = &pgdat->node_zones[zid];
1203
1204                 if (pfn >= zone->zone_start_pfn && pfn < zone_end_pfn(zone))
1205                         break;
1206         }
1207         __init_single_page(pfn_to_page(pfn), pfn, zid, nid);
1208 }
1209 #else
1210 static inline void init_reserved_page(unsigned long pfn)
1211 {
1212 }
1213 #endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
1214
1215 /*
1216  * Initialised pages do not have PageReserved set. This function is
1217  * called for each range allocated by the bootmem allocator and
1218  * marks the pages PageReserved. The remaining valid pages are later
1219  * sent to the buddy page allocator.
1220  */
1221 void __meminit reserve_bootmem_region(phys_addr_t start, phys_addr_t end)
1222 {
1223         unsigned long start_pfn = PFN_DOWN(start);
1224         unsigned long end_pfn = PFN_UP(end);
1225
1226         for (; start_pfn < end_pfn; start_pfn++) {
1227                 if (pfn_valid(start_pfn)) {
1228                         struct page *page = pfn_to_page(start_pfn);
1229
1230                         init_reserved_page(start_pfn);
1231
1232                         /* Avoid false-positive PageTail() */
1233                         INIT_LIST_HEAD(&page->lru);
1234
1235                         /*
1236                          * no need for atomic set_bit because the struct
1237                          * page is not visible yet so nobody should
1238                          * access it yet.
1239                          */
1240                         __SetPageReserved(page);
1241                 }
1242         }
1243 }
1244
1245 static void __free_pages_ok(struct page *page, unsigned int order)
1246 {
1247         unsigned long flags;
1248         int migratetype;
1249         unsigned long pfn = page_to_pfn(page);
1250
1251         if (!free_pages_prepare(page, order, true))
1252                 return;
1253
1254         migratetype = get_pfnblock_migratetype(page, pfn);
1255         local_irq_save(flags);
1256         __count_vm_events(PGFREE, 1 << order);
1257         free_one_page(page_zone(page), page, pfn, order, migratetype);
1258         local_irq_restore(flags);
1259 }
1260
1261 static void __init __free_pages_boot_core(struct page *page, unsigned int order)
1262 {
1263         unsigned int nr_pages = 1 << order;
1264         struct page *p = page;
1265         unsigned int loop;
1266
1267         prefetchw(p);
1268         for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
1269                 prefetchw(p + 1);
1270                 __ClearPageReserved(p);
1271                 set_page_count(p, 0);
1272         }
1273         __ClearPageReserved(p);
1274         set_page_count(p, 0);
1275
1276         page_zone(page)->managed_pages += nr_pages;
1277         set_page_refcounted(page);
1278         __free_pages(page, order);
1279 }
1280
1281 #if defined(CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID) || \
1282         defined(CONFIG_HAVE_MEMBLOCK_NODE_MAP)
1283
1284 static struct mminit_pfnnid_cache early_pfnnid_cache __meminitdata;
1285
1286 int __meminit early_pfn_to_nid(unsigned long pfn)
1287 {
1288         static DEFINE_SPINLOCK(early_pfn_lock);
1289         int nid;
1290
1291         spin_lock(&early_pfn_lock);
1292         nid = __early_pfn_to_nid(pfn, &early_pfnnid_cache);
1293         if (nid < 0)
1294                 nid = first_online_node;
1295         spin_unlock(&early_pfn_lock);
1296
1297         return nid;
1298 }
1299 #endif
1300
1301 #ifdef CONFIG_NODES_SPAN_OTHER_NODES
1302 static inline bool __meminit __maybe_unused
1303 meminit_pfn_in_nid(unsigned long pfn, int node,
1304                    struct mminit_pfnnid_cache *state)
1305 {
1306         int nid;
1307
1308         nid = __early_pfn_to_nid(pfn, state);
1309         if (nid >= 0 && nid != node)
1310                 return false;
1311         return true;
1312 }
1313
1314 /* Only safe to use early in boot when initialisation is single-threaded */
1315 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1316 {
1317         return meminit_pfn_in_nid(pfn, node, &early_pfnnid_cache);
1318 }
1319
1320 #else
1321
1322 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1323 {
1324         return true;
1325 }
1326 static inline bool __meminit  __maybe_unused
1327 meminit_pfn_in_nid(unsigned long pfn, int node,
1328                    struct mminit_pfnnid_cache *state)
1329 {
1330         return true;
1331 }
1332 #endif
1333
1334
1335 void __init __free_pages_bootmem(struct page *page, unsigned long pfn,
1336                                                         unsigned int order)
1337 {
1338         if (early_page_uninitialised(pfn))
1339                 return;
1340         return __free_pages_boot_core(page, order);
1341 }
1342
1343 /*
1344  * Check that the whole (or subset of) a pageblock given by the interval of
1345  * [start_pfn, end_pfn) is valid and within the same zone, before scanning it
1346  * with the migration of free compaction scanner. The scanners then need to
1347  * use only pfn_valid_within() check for arches that allow holes within
1348  * pageblocks.
1349  *
1350  * Return struct page pointer of start_pfn, or NULL if checks were not passed.
1351  *
1352  * It's possible on some configurations to have a setup like node0 node1 node0
1353  * i.e. it's possible that all pages within a zones range of pages do not
1354  * belong to a single zone. We assume that a border between node0 and node1
1355  * can occur within a single pageblock, but not a node0 node1 node0
1356  * interleaving within a single pageblock. It is therefore sufficient to check
1357  * the first and last page of a pageblock and avoid checking each individual
1358  * page in a pageblock.
1359  */
1360 struct page *__pageblock_pfn_to_page(unsigned long start_pfn,
1361                                      unsigned long end_pfn, struct zone *zone)
1362 {
1363         struct page *start_page;
1364         struct page *end_page;
1365
1366         /* end_pfn is one past the range we are checking */
1367         end_pfn--;
1368
1369         if (!pfn_valid(start_pfn) || !pfn_valid(end_pfn))
1370                 return NULL;
1371
1372         start_page = pfn_to_online_page(start_pfn);
1373         if (!start_page)
1374                 return NULL;
1375
1376         if (page_zone(start_page) != zone)
1377                 return NULL;
1378
1379         end_page = pfn_to_page(end_pfn);
1380
1381         /* This gives a shorter code than deriving page_zone(end_page) */
1382         if (page_zone_id(start_page) != page_zone_id(end_page))
1383                 return NULL;
1384
1385         return start_page;
1386 }
1387
1388 void set_zone_contiguous(struct zone *zone)
1389 {
1390         unsigned long block_start_pfn = zone->zone_start_pfn;
1391         unsigned long block_end_pfn;
1392
1393         block_end_pfn = ALIGN(block_start_pfn + 1, pageblock_nr_pages);
1394         for (; block_start_pfn < zone_end_pfn(zone);
1395                         block_start_pfn = block_end_pfn,
1396                          block_end_pfn += pageblock_nr_pages) {
1397
1398                 block_end_pfn = min(block_end_pfn, zone_end_pfn(zone));
1399
1400                 if (!__pageblock_pfn_to_page(block_start_pfn,
1401                                              block_end_pfn, zone))
1402                         return;
1403         }
1404
1405         /* We confirm that there is no hole */
1406         zone->contiguous = true;
1407 }
1408
1409 void clear_zone_contiguous(struct zone *zone)
1410 {
1411         zone->contiguous = false;
1412 }
1413
1414 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1415 static void __init deferred_free_range(unsigned long pfn,
1416                                        unsigned long nr_pages)
1417 {
1418         struct page *page;
1419         unsigned long i;
1420
1421         if (!nr_pages)
1422                 return;
1423
1424         page = pfn_to_page(pfn);
1425
1426         /* Free a large naturally-aligned chunk if possible */
1427         if (nr_pages == pageblock_nr_pages &&
1428             (pfn & (pageblock_nr_pages - 1)) == 0) {
1429                 set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1430                 __free_pages_boot_core(page, pageblock_order);
1431                 return;
1432         }
1433
1434         for (i = 0; i < nr_pages; i++, page++, pfn++) {
1435                 if ((pfn & (pageblock_nr_pages - 1)) == 0)
1436                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1437                 __free_pages_boot_core(page, 0);
1438         }
1439 }
1440
1441 /* Completion tracking for deferred_init_memmap() threads */
1442 static atomic_t pgdat_init_n_undone __initdata;
1443 static __initdata DECLARE_COMPLETION(pgdat_init_all_done_comp);
1444
1445 static inline void __init pgdat_init_report_one_done(void)
1446 {
1447         if (atomic_dec_and_test(&pgdat_init_n_undone))
1448                 complete(&pgdat_init_all_done_comp);
1449 }
1450
1451 /*
1452  * Returns true if page needs to be initialized or freed to buddy allocator.
1453  *
1454  * First we check if pfn is valid on architectures where it is possible to have
1455  * holes within pageblock_nr_pages. On systems where it is not possible, this
1456  * function is optimized out.
1457  *
1458  * Then, we check if a current large page is valid by only checking the validity
1459  * of the head pfn.
1460  *
1461  * Finally, meminit_pfn_in_nid is checked on systems where pfns can interleave
1462  * within a node: a pfn is between start and end of a node, but does not belong
1463  * to this memory node.
1464  */
1465 static inline bool __init
1466 deferred_pfn_valid(int nid, unsigned long pfn,
1467                    struct mminit_pfnnid_cache *nid_init_state)
1468 {
1469         if (!pfn_valid_within(pfn))
1470                 return false;
1471         if (!(pfn & (pageblock_nr_pages - 1)) && !pfn_valid(pfn))
1472                 return false;
1473         if (!meminit_pfn_in_nid(pfn, nid, nid_init_state))
1474                 return false;
1475         return true;
1476 }
1477
1478 /*
1479  * Free pages to buddy allocator. Try to free aligned pages in
1480  * pageblock_nr_pages sizes.
1481  */
1482 static void __init deferred_free_pages(int nid, int zid, unsigned long pfn,
1483                                        unsigned long end_pfn)
1484 {
1485         struct mminit_pfnnid_cache nid_init_state = { };
1486         unsigned long nr_pgmask = pageblock_nr_pages - 1;
1487         unsigned long nr_free = 0;
1488
1489         for (; pfn < end_pfn; pfn++) {
1490                 if (!deferred_pfn_valid(nid, pfn, &nid_init_state)) {
1491                         deferred_free_range(pfn - nr_free, nr_free);
1492                         nr_free = 0;
1493                 } else if (!(pfn & nr_pgmask)) {
1494                         deferred_free_range(pfn - nr_free, nr_free);
1495                         nr_free = 1;
1496                         touch_nmi_watchdog();
1497                 } else {
1498                         nr_free++;
1499                 }
1500         }
1501         /* Free the last block of pages to allocator */
1502         deferred_free_range(pfn - nr_free, nr_free);
1503 }
1504
1505 /*
1506  * Initialize struct pages.  We minimize pfn page lookups and scheduler checks
1507  * by performing it only once every pageblock_nr_pages.
1508  * Return number of pages initialized.
1509  */
1510 static unsigned long  __init deferred_init_pages(int nid, int zid,
1511                                                  unsigned long pfn,
1512                                                  unsigned long end_pfn)
1513 {
1514         struct mminit_pfnnid_cache nid_init_state = { };
1515         unsigned long nr_pgmask = pageblock_nr_pages - 1;
1516         unsigned long nr_pages = 0;
1517         struct page *page = NULL;
1518
1519         for (; pfn < end_pfn; pfn++) {
1520                 if (!deferred_pfn_valid(nid, pfn, &nid_init_state)) {
1521                         page = NULL;
1522                         continue;
1523                 } else if (!page || !(pfn & nr_pgmask)) {
1524                         page = pfn_to_page(pfn);
1525                         touch_nmi_watchdog();
1526                 } else {
1527                         page++;
1528                 }
1529                 __init_single_page(page, pfn, zid, nid);
1530                 nr_pages++;
1531         }
1532         return (nr_pages);
1533 }
1534
1535 /* Initialise remaining memory on a node */
1536 static int __init deferred_init_memmap(void *data)
1537 {
1538         pg_data_t *pgdat = data;
1539         int nid = pgdat->node_id;
1540         unsigned long start = jiffies;
1541         unsigned long nr_pages = 0;
1542         unsigned long spfn, epfn, first_init_pfn, flags;
1543         phys_addr_t spa, epa;
1544         int zid;
1545         struct zone *zone;
1546         const struct cpumask *cpumask = cpumask_of_node(pgdat->node_id);
1547         u64 i;
1548
1549         /* Bind memory initialisation thread to a local node if possible */
1550         if (!cpumask_empty(cpumask))
1551                 set_cpus_allowed_ptr(current, cpumask);
1552
1553         pgdat_resize_lock(pgdat, &flags);
1554         first_init_pfn = pgdat->first_deferred_pfn;
1555         if (first_init_pfn == ULONG_MAX) {
1556                 pgdat_resize_unlock(pgdat, &flags);
1557                 pgdat_init_report_one_done();
1558                 return 0;
1559         }
1560
1561         /* Sanity check boundaries */
1562         BUG_ON(pgdat->first_deferred_pfn < pgdat->node_start_pfn);
1563         BUG_ON(pgdat->first_deferred_pfn > pgdat_end_pfn(pgdat));
1564         pgdat->first_deferred_pfn = ULONG_MAX;
1565
1566         /* Only the highest zone is deferred so find it */
1567         for (zid = 0; zid < MAX_NR_ZONES; zid++) {
1568                 zone = pgdat->node_zones + zid;
1569                 if (first_init_pfn < zone_end_pfn(zone))
1570                         break;
1571         }
1572         first_init_pfn = max(zone->zone_start_pfn, first_init_pfn);
1573
1574         /*
1575          * Initialize and free pages. We do it in two loops: first we initialize
1576          * struct page, than free to buddy allocator, because while we are
1577          * freeing pages we can access pages that are ahead (computing buddy
1578          * page in __free_one_page()).
1579          */
1580         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1581                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1582                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1583                 nr_pages += deferred_init_pages(nid, zid, spfn, epfn);
1584         }
1585         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1586                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1587                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1588                 deferred_free_pages(nid, zid, spfn, epfn);
1589         }
1590         pgdat_resize_unlock(pgdat, &flags);
1591
1592         /* Sanity check that the next zone really is unpopulated */
1593         WARN_ON(++zid < MAX_NR_ZONES && populated_zone(++zone));
1594
1595         pr_info("node %d initialised, %lu pages in %ums\n", nid, nr_pages,
1596                                         jiffies_to_msecs(jiffies - start));
1597
1598         pgdat_init_report_one_done();
1599         return 0;
1600 }
1601
1602 /*
1603  * During boot we initialize deferred pages on-demand, as needed, but once
1604  * page_alloc_init_late() has finished, the deferred pages are all initialized,
1605  * and we can permanently disable that path.
1606  */
1607 static DEFINE_STATIC_KEY_TRUE(deferred_pages);
1608
1609 /*
1610  * If this zone has deferred pages, try to grow it by initializing enough
1611  * deferred pages to satisfy the allocation specified by order, rounded up to
1612  * the nearest PAGES_PER_SECTION boundary.  So we're adding memory in increments
1613  * of SECTION_SIZE bytes by initializing struct pages in increments of
1614  * PAGES_PER_SECTION * sizeof(struct page) bytes.
1615  *
1616  * Return true when zone was grown, otherwise return false. We return true even
1617  * when we grow less than requested, to let the caller decide if there are
1618  * enough pages to satisfy the allocation.
1619  *
1620  * Note: We use noinline because this function is needed only during boot, and
1621  * it is called from a __ref function _deferred_grow_zone. This way we are
1622  * making sure that it is not inlined into permanent text section.
1623  */
1624 static noinline bool __init
1625 deferred_grow_zone(struct zone *zone, unsigned int order)
1626 {
1627         int zid = zone_idx(zone);
1628         int nid = zone_to_nid(zone);
1629         pg_data_t *pgdat = NODE_DATA(nid);
1630         unsigned long nr_pages_needed = ALIGN(1 << order, PAGES_PER_SECTION);
1631         unsigned long nr_pages = 0;
1632         unsigned long first_init_pfn, spfn, epfn, t, flags;
1633         unsigned long first_deferred_pfn = pgdat->first_deferred_pfn;
1634         phys_addr_t spa, epa;
1635         u64 i;
1636
1637         /* Only the last zone may have deferred pages */
1638         if (zone_end_pfn(zone) != pgdat_end_pfn(pgdat))
1639                 return false;
1640
1641         pgdat_resize_lock(pgdat, &flags);
1642
1643         /*
1644          * If deferred pages have been initialized while we were waiting for
1645          * the lock, return true, as the zone was grown.  The caller will retry
1646          * this zone.  We won't return to this function since the caller also
1647          * has this static branch.
1648          */
1649         if (!static_branch_unlikely(&deferred_pages)) {
1650                 pgdat_resize_unlock(pgdat, &flags);
1651                 return true;
1652         }
1653
1654         /*
1655          * If someone grew this zone while we were waiting for spinlock, return
1656          * true, as there might be enough pages already.
1657          */
1658         if (first_deferred_pfn != pgdat->first_deferred_pfn) {
1659                 pgdat_resize_unlock(pgdat, &flags);
1660                 return true;
1661         }
1662
1663         first_init_pfn = max(zone->zone_start_pfn, first_deferred_pfn);
1664
1665         if (first_init_pfn >= pgdat_end_pfn(pgdat)) {
1666                 pgdat_resize_unlock(pgdat, &flags);
1667                 return false;
1668         }
1669
1670         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1671                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1672                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1673
1674                 while (spfn < epfn && nr_pages < nr_pages_needed) {
1675                         t = ALIGN(spfn + PAGES_PER_SECTION, PAGES_PER_SECTION);
1676                         first_deferred_pfn = min(t, epfn);
1677                         nr_pages += deferred_init_pages(nid, zid, spfn,
1678                                                         first_deferred_pfn);
1679                         spfn = first_deferred_pfn;
1680                 }
1681
1682                 if (nr_pages >= nr_pages_needed)
1683                         break;
1684         }
1685
1686         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1687                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1688                 epfn = min_t(unsigned long, first_deferred_pfn, PFN_DOWN(epa));
1689                 deferred_free_pages(nid, zid, spfn, epfn);
1690
1691                 if (first_deferred_pfn == epfn)
1692                         break;
1693         }
1694         pgdat->first_deferred_pfn = first_deferred_pfn;
1695         pgdat_resize_unlock(pgdat, &flags);
1696
1697         return nr_pages > 0;
1698 }
1699
1700 /*
1701  * deferred_grow_zone() is __init, but it is called from
1702  * get_page_from_freelist() during early boot until deferred_pages permanently
1703  * disables this call. This is why we have refdata wrapper to avoid warning,
1704  * and to ensure that the function body gets unloaded.
1705  */
1706 static bool __ref
1707 _deferred_grow_zone(struct zone *zone, unsigned int order)
1708 {
1709         return deferred_grow_zone(zone, order);
1710 }
1711
1712 #endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
1713
1714 void __init page_alloc_init_late(void)
1715 {
1716         struct zone *zone;
1717
1718 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1719         int nid;
1720
1721         /* There will be num_node_state(N_MEMORY) threads */
1722         atomic_set(&pgdat_init_n_undone, num_node_state(N_MEMORY));
1723         for_each_node_state(nid, N_MEMORY) {
1724                 kthread_run(deferred_init_memmap, NODE_DATA(nid), "pgdatinit%d", nid);
1725         }
1726
1727         /* Block until all are initialised */
1728         wait_for_completion(&pgdat_init_all_done_comp);
1729
1730         /*
1731          * We initialized the rest of the deferred pages.  Permanently disable
1732          * on-demand struct page initialization.
1733          */
1734         static_branch_disable(&deferred_pages);
1735
1736         /* Reinit limits that are based on free pages after the kernel is up */
1737         files_maxfiles_init();
1738 #endif
1739 #ifdef CONFIG_ARCH_DISCARD_MEMBLOCK
1740         /* Discard memblock private memory */
1741         memblock_discard();
1742 #endif
1743
1744         for_each_populated_zone(zone)
1745                 set_zone_contiguous(zone);
1746 }
1747
1748 #ifdef CONFIG_CMA
1749 /* Free whole pageblock and set its migration type to MIGRATE_CMA. */
1750 void __init init_cma_reserved_pageblock(struct page *page)
1751 {
1752         unsigned i = pageblock_nr_pages;
1753         struct page *p = page;
1754
1755         do {
1756                 __ClearPageReserved(p);
1757                 set_page_count(p, 0);
1758         } while (++p, --i);
1759
1760         set_pageblock_migratetype(page, MIGRATE_CMA);
1761
1762         if (pageblock_order >= MAX_ORDER) {
1763                 i = pageblock_nr_pages;
1764                 p = page;
1765                 do {
1766                         set_page_refcounted(p);
1767                         __free_pages(p, MAX_ORDER - 1);
1768                         p += MAX_ORDER_NR_PAGES;
1769                 } while (i -= MAX_ORDER_NR_PAGES);
1770         } else {
1771                 set_page_refcounted(page);
1772                 __free_pages(page, pageblock_order);
1773         }
1774
1775         adjust_managed_page_count(page, pageblock_nr_pages);
1776 }
1777 #endif
1778
1779 /*
1780  * The order of subdivision here is critical for the IO subsystem.
1781  * Please do not alter this order without good reasons and regression
1782  * testing. Specifically, as large blocks of memory are subdivided,
1783  * the order in which smaller blocks are delivered depends on the order
1784  * they're subdivided in this function. This is the primary factor
1785  * influencing the order in which pages are delivered to the IO
1786  * subsystem according to empirical testing, and this is also justified
1787  * by considering the behavior of a buddy system containing a single
1788  * large block of memory acted on by a series of small allocations.
1789  * This behavior is a critical factor in sglist merging's success.
1790  *
1791  * -- nyc
1792  */
1793 static inline void expand(struct zone *zone, struct page *page,
1794         int low, int high, struct free_area *area,
1795         int migratetype)
1796 {
1797         unsigned long size = 1 << high;
1798
1799         while (high > low) {
1800                 area--;
1801                 high--;
1802                 size >>= 1;
1803                 VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);
1804
1805                 /*
1806                  * Mark as guard pages (or page), that will allow to
1807                  * merge back to allocator when buddy will be freed.
1808                  * Corresponding page table entries will not be touched,
1809                  * pages will stay not present in virtual address space
1810                  */
1811                 if (set_page_guard(zone, &page[size], high, migratetype))
1812                         continue;
1813
1814                 list_add(&page[size].lru, &area->free_list[migratetype]);
1815                 area->nr_free++;
1816                 set_page_order(&page[size], high);
1817         }
1818 }
1819
1820 static void check_new_page_bad(struct page *page)
1821 {
1822         const char *bad_reason = NULL;
1823         unsigned long bad_flags = 0;
1824
1825         if (unlikely(atomic_read(&page->_mapcount) != -1))
1826                 bad_reason = "nonzero mapcount";
1827         if (unlikely(page->mapping != NULL))
1828                 bad_reason = "non-NULL mapping";
1829         if (unlikely(page_ref_count(page) != 0))
1830                 bad_reason = "nonzero _count";
1831         if (unlikely(page->flags & __PG_HWPOISON)) {
1832                 bad_reason = "HWPoisoned (hardware-corrupted)";
1833                 bad_flags = __PG_HWPOISON;
1834                 /* Don't complain about hwpoisoned pages */
1835                 page_mapcount_reset(page); /* remove PageBuddy */
1836                 return;
1837         }
1838         if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_PREP)) {
1839                 bad_reason = "PAGE_FLAGS_CHECK_AT_PREP flag set";
1840                 bad_flags = PAGE_FLAGS_CHECK_AT_PREP;
1841         }
1842 #ifdef CONFIG_MEMCG
1843         if (unlikely(page->mem_cgroup))
1844                 bad_reason = "page still charged to cgroup";
1845 #endif
1846         bad_page(page, bad_reason, bad_flags);
1847 }
1848
1849 /*
1850  * This page is about to be returned from the page allocator
1851  */
1852 static inline int check_new_page(struct page *page)
1853 {
1854         if (likely(page_expected_state(page,
1855                                 PAGE_FLAGS_CHECK_AT_PREP|__PG_HWPOISON)))
1856                 return 0;
1857
1858         check_new_page_bad(page);
1859         return 1;
1860 }
1861
1862 static inline bool free_pages_prezeroed(void)
1863 {
1864         return IS_ENABLED(CONFIG_PAGE_POISONING_ZERO) &&
1865                 page_poisoning_enabled();
1866 }
1867
1868 #ifdef CONFIG_DEBUG_VM
1869 static bool check_pcp_refill(struct page *page)
1870 {
1871         return false;
1872 }
1873
1874 static bool check_new_pcp(struct page *page)
1875 {
1876         return check_new_page(page);
1877 }
1878 #else
1879 static bool check_pcp_refill(struct page *page)
1880 {
1881         return check_new_page(page);
1882 }
1883 static bool check_new_pcp(struct page *page)
1884 {
1885         return false;
1886 }
1887 #endif /* CONFIG_DEBUG_VM */
1888
1889 static bool check_new_pages(struct page *page, unsigned int order)
1890 {
1891         int i;
1892         for (i = 0; i < (1 << order); i++) {
1893                 struct page *p = page + i;
1894
1895                 if (unlikely(check_new_page(p)))
1896                         return true;
1897         }
1898
1899         return false;
1900 }
1901
1902 inline void post_alloc_hook(struct page *page, unsigned int order,
1903                                 gfp_t gfp_flags)
1904 {
1905         set_page_private(page, 0);
1906         set_page_refcounted(page);
1907
1908         arch_alloc_page(page, order);
1909         kernel_map_pages(page, 1 << order, 1);
1910         kernel_poison_pages(page, 1 << order, 1);
1911         kasan_alloc_pages(page, order);
1912         set_page_owner(page, order, gfp_flags);
1913 }
1914
1915 static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags,
1916                                                         unsigned int alloc_flags)
1917 {
1918         int i;
1919
1920         post_alloc_hook(page, order, gfp_flags);
1921
1922         if (!free_pages_prezeroed() && (gfp_flags & __GFP_ZERO))
1923                 for (i = 0; i < (1 << order); i++)
1924                         clear_highpage(page + i);
1925
1926         if (order && (gfp_flags & __GFP_COMP))
1927                 prep_compound_page(page, order);
1928
1929         /*
1930          * page is set pfmemalloc when ALLOC_NO_WATERMARKS was necessary to
1931          * allocate the page. The expectation is that the caller is taking
1932          * steps that will free more memory. The caller should avoid the page
1933          * being used for !PFMEMALLOC purposes.
1934          */
1935         if (alloc_flags & ALLOC_NO_WATERMARKS)
1936                 set_page_pfmemalloc(page);
1937         else
1938                 clear_page_pfmemalloc(page);
1939 }
1940
1941 /*
1942  * Go through the free lists for the given migratetype and remove
1943  * the smallest available page from the freelists
1944  */
1945 static __always_inline
1946 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
1947                                                 int migratetype)
1948 {
1949         unsigned int current_order;
1950         struct free_area *area;
1951         struct page *page;
1952
1953         /* Find a page of the appropriate size in the preferred list */
1954         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
1955                 area = &(zone->free_area[current_order]);
1956                 page = list_first_entry_or_null(&area->free_list[migratetype],
1957                                                         struct page, lru);
1958                 if (!page)
1959                         continue;
1960                 list_del(&page->lru);
1961                 rmv_page_order(page);
1962                 area->nr_free--;
1963                 expand(zone, page, order, current_order, area, migratetype);
1964                 set_pcppage_migratetype(page, migratetype);
1965                 return page;
1966         }
1967
1968         return NULL;
1969 }
1970
1971
1972 /*
1973  * This array describes the order lists are fallen back to when
1974  * the free lists for the desirable migrate type are depleted
1975  */
1976 static int fallbacks[MIGRATE_TYPES][4] = {
1977         [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
1978         [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
1979         [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
1980 #ifdef CONFIG_CMA
1981         [MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
1982 #endif
1983 #ifdef CONFIG_MEMORY_ISOLATION
1984         [MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
1985 #endif
1986 };
1987
1988 #ifdef CONFIG_CMA
1989 static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1990                                         unsigned int order)
1991 {
1992         return __rmqueue_smallest(zone, order, MIGRATE_CMA);
1993 }
1994 #else
1995 static inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1996                                         unsigned int order) { return NULL; }
1997 #endif
1998
1999 /*
2000  * Move the free pages in a range to the free lists of the requested type.
2001  * Note that start_page and end_pages are not aligned on a pageblock
2002  * boundary. If alignment is required, use move_freepages_block()
2003  */
2004 static int move_freepages(struct zone *zone,
2005                           struct page *start_page, struct page *end_page,
2006                           int migratetype, int *num_movable)
2007 {
2008         struct page *page;
2009         unsigned int order;
2010         int pages_moved = 0;
2011
2012 #ifndef CONFIG_HOLES_IN_ZONE
2013         /*
2014          * page_zone is not safe to call in this context when
2015          * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
2016          * anyway as we check zone boundaries in move_freepages_block().
2017          * Remove at a later date when no bug reports exist related to
2018          * grouping pages by mobility
2019          */
2020         VM_BUG_ON(pfn_valid(page_to_pfn(start_page)) &&
2021                   pfn_valid(page_to_pfn(end_page)) &&
2022                   page_zone(start_page) != page_zone(end_page));
2023 #endif
2024
2025         if (num_movable)
2026                 *num_movable = 0;
2027
2028         for (page = start_page; page <= end_page;) {
2029                 if (!pfn_valid_within(page_to_pfn(page))) {
2030                         page++;
2031                         continue;
2032                 }
2033
2034                 /* Make sure we are not inadvertently changing nodes */
2035                 VM_BUG_ON_PAGE(page_to_nid(page) != zone_to_nid(zone), page);
2036
2037                 if (!PageBuddy(page)) {
2038                         /*
2039                          * We assume that pages that could be isolated for
2040                          * migration are movable. But we don't actually try
2041                          * isolating, as that would be expensive.
2042                          */
2043                         if (num_movable &&
2044                                         (PageLRU(page) || __PageMovable(page)))
2045                                 (*num_movable)++;
2046
2047                         page++;
2048                         continue;
2049                 }
2050
2051                 order = page_order(page);
2052                 list_move(&page->lru,
2053                           &zone->free_area[order].free_list[migratetype]);
2054                 page += 1 << order;
2055                 pages_moved += 1 << order;
2056         }
2057
2058         return pages_moved;
2059 }
2060
2061 int move_freepages_block(struct zone *zone, struct page *page,
2062                                 int migratetype, int *num_movable)
2063 {
2064         unsigned long start_pfn, end_pfn;
2065         struct page *start_page, *end_page;
2066
2067         start_pfn = page_to_pfn(page);
2068         start_pfn = start_pfn & ~(pageblock_nr_pages-1);
2069         start_page = pfn_to_page(start_pfn);
2070         end_page = start_page + pageblock_nr_pages - 1;
2071         end_pfn = start_pfn + pageblock_nr_pages - 1;
2072
2073         /* Do not cross zone boundaries */
2074         if (!zone_spans_pfn(zone, start_pfn))
2075                 start_page = page;
2076         if (!zone_spans_pfn(zone, end_pfn))
2077                 return 0;
2078
2079         return move_freepages(zone, start_page, end_page, migratetype,
2080                                                                 num_movable);
2081 }
2082
2083 static void change_pageblock_range(struct page *pageblock_page,
2084                                         int start_order, int migratetype)
2085 {
2086         int nr_pageblocks = 1 << (start_order - pageblock_order);
2087
2088         while (nr_pageblocks--) {
2089                 set_pageblock_migratetype(pageblock_page, migratetype);
2090                 pageblock_page += pageblock_nr_pages;
2091         }
2092 }
2093
2094 /*
2095  * When we are falling back to another migratetype during allocation, try to
2096  * steal extra free pages from the same pageblocks to satisfy further
2097  * allocations, instead of polluting multiple pageblocks.
2098  *
2099  * If we are stealing a relatively large buddy page, it is likely there will
2100  * be more free pages in the pageblock, so try to steal them all. For
2101  * reclaimable and unmovable allocations, we steal regardless of page size,
2102  * as fragmentation caused by those allocations polluting movable pageblocks
2103  * is worse than movable allocations stealing from unmovable and reclaimable
2104  * pageblocks.
2105  */
2106 static bool can_steal_fallback(unsigned int order, int start_mt)
2107 {
2108         /*
2109          * Leaving this order check is intended, although there is
2110          * relaxed order check in next check. The reason is that
2111          * we can actually steal whole pageblock if this condition met,
2112          * but, below check doesn't guarantee it and that is just heuristic
2113          * so could be changed anytime.
2114          */
2115         if (order >= pageblock_order)
2116                 return true;
2117
2118         if (order >= pageblock_order / 2 ||
2119                 start_mt == MIGRATE_RECLAIMABLE ||
2120                 start_mt == MIGRATE_UNMOVABLE ||
2121                 page_group_by_mobility_disabled)
2122                 return true;
2123
2124         return false;
2125 }
2126
2127 /*
2128  * This function implements actual steal behaviour. If order is large enough,
2129  * we can steal whole pageblock. If not, we first move freepages in this
2130  * pageblock to our migratetype and determine how many already-allocated pages
2131  * are there in the pageblock with a compatible migratetype. If at least half
2132  * of pages are free or compatible, we can change migratetype of the pageblock
2133  * itself, so pages freed in the future will be put on the correct free list.
2134  */
2135 static void steal_suitable_fallback(struct zone *zone, struct page *page,
2136                                         int start_type, bool whole_block)
2137 {
2138         unsigned int current_order = page_order(page);
2139         struct free_area *area;
2140         int free_pages, movable_pages, alike_pages;
2141         int old_block_type;
2142
2143         old_block_type = get_pageblock_migratetype(page);
2144
2145         /*
2146          * This can happen due to races and we want to prevent broken
2147          * highatomic accounting.
2148          */
2149         if (is_migrate_highatomic(old_block_type))
2150                 goto single_page;
2151
2152         /* Take ownership for orders >= pageblock_order */
2153         if (current_order >= pageblock_order) {
2154                 change_pageblock_range(page, current_order, start_type);
2155                 goto single_page;
2156         }
2157
2158         /* We are not allowed to try stealing from the whole block */
2159         if (!whole_block)
2160                 goto single_page;
2161
2162         free_pages = move_freepages_block(zone, page, start_type,
2163                                                 &movable_pages);
2164         /*
2165          * Determine how many pages are compatible with our allocation.
2166          * For movable allocation, it's the number of movable pages which
2167          * we just obtained. For other types it's a bit more tricky.
2168          */
2169         if (start_type == MIGRATE_MOVABLE) {
2170                 alike_pages = movable_pages;
2171         } else {
2172                 /*
2173                  * If we are falling back a RECLAIMABLE or UNMOVABLE allocation
2174                  * to MOVABLE pageblock, consider all non-movable pages as
2175                  * compatible. If it's UNMOVABLE falling back to RECLAIMABLE or
2176                  * vice versa, be conservative since we can't distinguish the
2177                  * exact migratetype of non-movable pages.
2178                  */
2179                 if (old_block_type == MIGRATE_MOVABLE)
2180                         alike_pages = pageblock_nr_pages
2181                                                 - (free_pages + movable_pages);
2182                 else
2183                         alike_pages = 0;
2184         }
2185
2186         /* moving whole block can fail due to zone boundary conditions */
2187         if (!free_pages)
2188                 goto single_page;
2189
2190         /*
2191          * If a sufficient number of pages in the block are either free or of
2192          * comparable migratability as our allocation, claim the whole block.
2193          */
2194         if (free_pages + alike_pages >= (1 << (pageblock_order-1)) ||
2195                         page_group_by_mobility_disabled)
2196                 set_pageblock_migratetype(page, start_type);
2197
2198         return;
2199
2200 single_page:
2201         area = &zone->free_area[current_order];
2202         list_move(&page->lru, &area->free_list[start_type]);
2203 }
2204
2205 /*
2206  * Check whether there is a suitable fallback freepage with requested order.
2207  * If only_stealable is true, this function returns fallback_mt only if
2208  * we can steal other freepages all together. This would help to reduce
2209  * fragmentation due to mixed migratetype pages in one pageblock.
2210  */
2211 int find_suitable_fallback(struct free_area *area, unsigned int order,
2212                         int migratetype, bool only_stealable, bool *can_steal)
2213 {
2214         int i;
2215         int fallback_mt;
2216
2217         if (area->nr_free == 0)
2218                 return -1;
2219
2220         *can_steal = false;
2221         for (i = 0;; i++) {
2222                 fallback_mt = fallbacks[migratetype][i];
2223                 if (fallback_mt == MIGRATE_TYPES)
2224                         break;
2225
2226                 if (list_empty(&area->free_list[fallback_mt]))
2227                         continue;
2228
2229                 if (can_steal_fallback(order, migratetype))
2230                         *can_steal = true;
2231
2232                 if (!only_stealable)
2233                         return fallback_mt;
2234
2235                 if (*can_steal)
2236                         return fallback_mt;
2237         }
2238
2239         return -1;
2240 }
2241
2242 /*
2243  * Reserve a pageblock for exclusive use of high-order atomic allocations if
2244  * there are no empty page blocks that contain a page with a suitable order
2245  */
2246 static void reserve_highatomic_pageblock(struct page *page, struct zone *zone,
2247                                 unsigned int alloc_order)
2248 {
2249         int mt;
2250         unsigned long max_managed, flags;
2251
2252         /*
2253          * Limit the number reserved to 1 pageblock or roughly 1% of a zone.
2254          * Check is race-prone but harmless.
2255          */
2256         max_managed = (zone->managed_pages / 100) + pageblock_nr_pages;
2257         if (zone->nr_reserved_highatomic >= max_managed)
2258                 return;
2259
2260         spin_lock_irqsave(&zone->lock, flags);
2261
2262         /* Recheck the nr_reserved_highatomic limit under the lock */
2263         if (zone->nr_reserved_highatomic >= max_managed)
2264                 goto out_unlock;
2265
2266         /* Yoink! */
2267         mt = get_pageblock_migratetype(page);
2268         if (!is_migrate_highatomic(mt) && !is_migrate_isolate(mt)
2269             && !is_migrate_cma(mt)) {
2270                 zone->nr_reserved_highatomic += pageblock_nr_pages;
2271                 set_pageblock_migratetype(page, MIGRATE_HIGHATOMIC);
2272                 move_freepages_block(zone, page, MIGRATE_HIGHATOMIC, NULL);
2273         }
2274
2275 out_unlock:
2276         spin_unlock_irqrestore(&zone->lock, flags);
2277 }
2278
2279 /*
2280  * Used when an allocation is about to fail under memory pressure. This
2281  * potentially hurts the reliability of high-order allocations when under
2282  * intense memory pressure but failed atomic allocations should be easier
2283  * to recover from than an OOM.
2284  *
2285  * If @force is true, try to unreserve a pageblock even though highatomic
2286  * pageblock is exhausted.
2287  */
2288 static bool unreserve_highatomic_pageblock(const struct alloc_context *ac,
2289                                                 bool force)
2290 {
2291         struct zonelist *zonelist = ac->zonelist;
2292         unsigned long flags;
2293         struct zoneref *z;
2294         struct zone *zone;
2295         struct page *page;
2296         int order;
2297         bool ret;
2298
2299         for_each_zone_zonelist_nodemask(zone, z, zonelist, ac->high_zoneidx,
2300                                                                 ac->nodemask) {
2301                 /*
2302                  * Preserve at least one pageblock unless memory pressure
2303                  * is really high.
2304                  */
2305                 if (!force && zone->nr_reserved_highatomic <=
2306                                         pageblock_nr_pages)
2307                         continue;
2308
2309                 spin_lock_irqsave(&zone->lock, flags);
2310                 for (order = 0; order < MAX_ORDER; order++) {
2311                         struct free_area *area = &(zone->free_area[order]);
2312
2313                         page = list_first_entry_or_null(
2314                                         &area->free_list[MIGRATE_HIGHATOMIC],
2315                                         struct page, lru);
2316                         if (!page)
2317                                 continue;
2318
2319                         /*
2320                          * In page freeing path, migratetype change is racy so
2321                          * we can counter several free pages in a pageblock
2322                          * in this loop althoug we changed the pageblock type
2323                          * from highatomic to ac->migratetype. So we should
2324                          * adjust the count once.
2325                          */
2326                         if (is_migrate_highatomic_page(page)) {
2327                                 /*
2328                                  * It should never happen but changes to
2329                                  * locking could inadvertently allow a per-cpu
2330                                  * drain to add pages to MIGRATE_HIGHATOMIC
2331                                  * while unreserving so be safe and watch for
2332                                  * underflows.
2333                                  */
2334                                 zone->nr_reserved_highatomic -= min(
2335                                                 pageblock_nr_pages,
2336                                                 zone->nr_reserved_highatomic);
2337                         }
2338
2339                         /*
2340                          * Convert to ac->migratetype and avoid the normal
2341                          * pageblock stealing heuristics. Minimally, the caller
2342                          * is doing the work and needs the pages. More
2343                          * importantly, if the block was always converted to
2344                          * MIGRATE_UNMOVABLE or another type then the number
2345                          * of pageblocks that cannot be completely freed
2346                          * may increase.
2347                          */
2348                         set_pageblock_migratetype(page, ac->migratetype);
2349                         ret = move_freepages_block(zone, page, ac->migratetype,
2350                                                                         NULL);
2351                         if (ret) {
2352                                 spin_unlock_irqrestore(&zone->lock, flags);
2353                                 return ret;
2354                         }
2355                 }
2356                 spin_unlock_irqrestore(&zone->lock, flags);
2357         }
2358
2359         return false;
2360 }
2361
2362 /*
2363  * Try finding a free buddy page on the fallback list and put it on the free
2364  * list of requested migratetype, possibly along with other pages from the same
2365  * block, depending on fragmentation avoidance heuristics. Returns true if
2366  * fallback was found so that __rmqueue_smallest() can grab it.
2367  *
2368  * The use of signed ints for order and current_order is a deliberate
2369  * deviation from the rest of this file, to make the for loop
2370  * condition simpler.
2371  */
2372 static __always_inline bool
2373 __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
2374 {
2375         struct free_area *area;
2376         int current_order;
2377         struct page *page;
2378         int fallback_mt;
2379         bool can_steal;
2380
2381         /*
2382          * Find the largest available free page in the other list. This roughly
2383          * approximates finding the pageblock with the most free pages, which
2384          * would be too costly to do exactly.
2385          */
2386         for (current_order = MAX_ORDER - 1; current_order >= order;
2387                                 --current_order) {
2388                 area = &(zone->free_area[current_order]);
2389                 fallback_mt = find_suitable_fallback(area, current_order,
2390                                 start_migratetype, false, &can_steal);
2391                 if (fallback_mt == -1)
2392                         continue;
2393
2394                 /*
2395                  * We cannot steal all free pages from the pageblock and the
2396                  * requested migratetype is movable. In that case it's better to
2397                  * steal and split the smallest available page instead of the
2398                  * largest available page, because even if the next movable
2399                  * allocation falls back into a different pageblock than this
2400                  * one, it won't cause permanent fragmentation.
2401                  */
2402                 if (!can_steal && start_migratetype == MIGRATE_MOVABLE
2403                                         && current_order > order)
2404                         goto find_smallest;
2405
2406                 goto do_steal;
2407         }
2408
2409         return false;
2410
2411 find_smallest:
2412         for (current_order = order; current_order < MAX_ORDER;
2413                                                         current_order++) {
2414                 area = &(zone->free_area[current_order]);
2415                 fallback_mt = find_suitable_fallback(area, current_order,
2416                                 start_migratetype, false, &can_steal);
2417                 if (fallback_mt != -1)
2418                         break;
2419         }
2420
2421         /*
2422          * This should not happen - we already found a suitable fallback
2423          * when looking for the largest page.
2424          */
2425         VM_BUG_ON(current_order == MAX_ORDER);
2426
2427 do_steal:
2428         page = list_first_entry(&area->free_list[fallback_mt],
2429                                                         struct page, lru);
2430
2431         steal_suitable_fallback(zone, page, start_migratetype, can_steal);
2432
2433         trace_mm_page_alloc_extfrag(page, order, current_order,
2434                 start_migratetype, fallback_mt);
2435
2436         return true;
2437
2438 }
2439
2440 /*
2441  * Do the hard work of removing an element from the buddy allocator.
2442  * Call me with the zone->lock already held.
2443  */
2444 static __always_inline struct page *
2445 __rmqueue(struct zone *zone, unsigned int order, int migratetype)
2446 {
2447         struct page *page;
2448
2449 retry:
2450         page = __rmqueue_smallest(zone, order, migratetype);
2451         if (unlikely(!page)) {
2452                 if (migratetype == MIGRATE_MOVABLE)
2453                         page = __rmqueue_cma_fallback(zone, order);
2454
2455                 if (!page && __rmqueue_fallback(zone, order, migratetype))
2456                         goto retry;
2457         }
2458
2459         trace_mm_page_alloc_zone_locked(page, order, migratetype);
2460         return page;
2461 }
2462
2463 /*
2464  * Obtain a specified number of elements from the buddy allocator, all under
2465  * a single hold of the lock, for efficiency.  Add them to the supplied list.
2466  * Returns the number of new pages which were placed at *list.
2467  */
2468 static int rmqueue_bulk(struct zone *zone, unsigned int order,
2469                         unsigned long count, struct list_head *list,
2470                         int migratetype)
2471 {
2472         int i, alloced = 0;
2473
2474         spin_lock(&zone->lock);
2475         for (i = 0; i < count; ++i) {
2476                 struct page *page = __rmqueue(zone, order, migratetype);
2477                 if (unlikely(page == NULL))
2478                         break;
2479
2480                 if (unlikely(check_pcp_refill(page)))
2481                         continue;
2482
2483                 /*
2484                  * Split buddy pages returned by expand() are received here in
2485                  * physical page order. The page is added to the tail of
2486                  * caller's list. From the callers perspective, the linked list
2487                  * is ordered by page number under some conditions. This is
2488                  * useful for IO devices that can forward direction from the
2489                  * head, thus also in the physical page order. This is useful
2490                  * for IO devices that can merge IO requests if the physical
2491                  * pages are ordered properly.
2492                  */
2493                 list_add_tail(&page->lru, list);
2494                 alloced++;
2495                 if (is_migrate_cma(get_pcppage_migratetype(page)))
2496                         __mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
2497                                               -(1 << order));
2498         }
2499
2500         /*
2501          * i pages were removed from the buddy list even if some leak due
2502          * to check_pcp_refill failing so adjust NR_FREE_PAGES based
2503          * on i. Do not confuse with 'alloced' which is the number of
2504          * pages added to the pcp list.
2505          */
2506         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
2507         spin_unlock(&zone->lock);
2508         return alloced;
2509 }
2510
2511 #ifdef CONFIG_NUMA
2512 /*
2513  * Called from the vmstat counter updater to drain pagesets of this
2514  * currently executing processor on remote nodes after they have
2515  * expired.
2516  *
2517  * Note that this function must be called with the thread pinned to
2518  * a single processor.
2519  */
2520 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
2521 {
2522         unsigned long flags;
2523         int to_drain, batch;
2524
2525         local_irq_save(flags);
2526         batch = READ_ONCE(pcp->batch);
2527         to_drain = min(pcp->count, batch);
2528         if (to_drain > 0)
2529                 free_pcppages_bulk(zone, to_drain, pcp);
2530         local_irq_restore(flags);
2531 }
2532 #endif
2533
2534 /*
2535  * Drain pcplists of the indicated processor and zone.
2536  *
2537  * The processor must either be the current processor and the
2538  * thread pinned to the current processor or a processor that
2539  * is not online.
2540  */
2541 static void drain_pages_zone(unsigned int cpu, struct zone *zone)
2542 {
2543         unsigned long flags;
2544         struct per_cpu_pageset *pset;
2545         struct per_cpu_pages *pcp;
2546
2547         local_irq_save(flags);
2548         pset = per_cpu_ptr(zone->pageset, cpu);
2549
2550         pcp = &pset->pcp;
2551         if (pcp->count)
2552                 free_pcppages_bulk(zone, pcp->count, pcp);
2553         local_irq_restore(flags);
2554 }
2555
2556 /*
2557  * Drain pcplists of all zones on the indicated processor.
2558  *
2559  * The processor must either be the current processor and the
2560  * thread pinned to the current processor or a processor that
2561  * is not online.
2562  */
2563 static void drain_pages(unsigned int cpu)
2564 {
2565         struct zone *zone;
2566
2567         for_each_populated_zone(zone) {
2568                 drain_pages_zone(cpu, zone);
2569         }
2570 }
2571
2572 /*
2573  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
2574  *
2575  * The CPU has to be pinned. When zone parameter is non-NULL, spill just
2576  * the single zone's pages.
2577  */
2578 void drain_local_pages(struct zone *zone)
2579 {
2580         int cpu = smp_processor_id();
2581
2582         if (zone)
2583                 drain_pages_zone(cpu, zone);
2584         else
2585                 drain_pages(cpu);
2586 }
2587
2588 static void drain_local_pages_wq(struct work_struct *work)
2589 {
2590         /*
2591          * drain_all_pages doesn't use proper cpu hotplug protection so
2592          * we can race with cpu offline when the WQ can move this from
2593          * a cpu pinned worker to an unbound one. We can operate on a different
2594          * cpu which is allright but we also have to make sure to not move to
2595          * a different one.
2596          */
2597         preempt_disable();
2598         drain_local_pages(NULL);
2599         preempt_enable();
2600 }
2601
2602 /*
2603  * Spill all the per-cpu pages from all CPUs back into the buddy allocator.
2604  *
2605  * When zone parameter is non-NULL, spill just the single zone's pages.
2606  *
2607  * Note that this can be extremely slow as the draining happens in a workqueue.
2608  */
2609 void drain_all_pages(struct zone *zone)
2610 {
2611         int cpu;
2612
2613         /*
2614          * Allocate in the BSS so we wont require allocation in
2615          * direct reclaim path for CONFIG_CPUMASK_OFFSTACK=y
2616          */
2617         static cpumask_t cpus_with_pcps;
2618
2619         /*
2620          * Make sure nobody triggers this path before mm_percpu_wq is fully
2621          * initialized.
2622          */
2623         if (WARN_ON_ONCE(!mm_percpu_wq))
2624                 return;
2625
2626         /*
2627          * Do not drain if one is already in progress unless it's specific to
2628          * a zone. Such callers are primarily CMA and memory hotplug and need
2629          * the drain to be complete when the call returns.
2630          */
2631         if (unlikely(!mutex_trylock(&pcpu_drain_mutex))) {
2632                 if (!zone)
2633                         return;
2634                 mutex_lock(&pcpu_drain_mutex);
2635         }
2636
2637         /*
2638          * We don't care about racing with CPU hotplug event
2639          * as offline notification will cause the notified
2640          * cpu to drain that CPU pcps and on_each_cpu_mask
2641          * disables preemption as part of its processing
2642          */
2643         for_each_online_cpu(cpu) {
2644                 struct per_cpu_pageset *pcp;
2645                 struct zone *z;
2646                 bool has_pcps = false;
2647
2648                 if (zone) {
2649                         pcp = per_cpu_ptr(zone->pageset, cpu);
2650                         if (pcp->pcp.count)
2651                                 has_pcps = true;
2652                 } else {
2653                         for_each_populated_zone(z) {
2654                                 pcp = per_cpu_ptr(z->pageset, cpu);
2655                                 if (pcp->pcp.count) {
2656                                         has_pcps = true;
2657                                         break;
2658                                 }
2659                         }
2660                 }
2661
2662                 if (has_pcps)
2663                         cpumask_set_cpu(cpu, &cpus_with_pcps);
2664                 else
2665                         cpumask_clear_cpu(cpu, &cpus_with_pcps);
2666         }
2667
2668         for_each_cpu(cpu, &cpus_with_pcps) {
2669                 struct work_struct *work = per_cpu_ptr(&pcpu_drain, cpu);
2670                 INIT_WORK(work, drain_local_pages_wq);
2671                 queue_work_on(cpu, mm_percpu_wq, work);
2672         }
2673         for_each_cpu(cpu, &cpus_with_pcps)
2674                 flush_work(per_cpu_ptr(&pcpu_drain, cpu));
2675
2676         mutex_unlock(&pcpu_drain_mutex);
2677 }
2678
2679 #ifdef CONFIG_HIBERNATION
2680
2681 /*
2682  * Touch the watchdog for every WD_PAGE_COUNT pages.
2683  */
2684 #define WD_PAGE_COUNT   (128*1024)
2685
2686 void mark_free_pages(struct zone *zone)
2687 {
2688         unsigned long pfn, max_zone_pfn, page_count = WD_PAGE_COUNT;
2689         unsigned long flags;
2690         unsigned int order, t;
2691         struct page *page;
2692
2693         if (zone_is_empty(zone))
2694                 return;
2695
2696         spin_lock_irqsave(&zone->lock, flags);
2697
2698         max_zone_pfn = zone_end_pfn(zone);
2699         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
2700                 if (pfn_valid(pfn)) {
2701                         page = pfn_to_page(pfn);
2702
2703                         if (!--page_count) {
2704                                 touch_nmi_watchdog();
2705                                 page_count = WD_PAGE_COUNT;
2706                         }
2707
2708                         if (page_zone(page) != zone)
2709                                 continue;
2710
2711                         if (!swsusp_page_is_forbidden(page))
2712                                 swsusp_unset_page_free(page);
2713                 }
2714
2715         for_each_migratetype_order(order, t) {
2716                 list_for_each_entry(page,
2717                                 &zone->free_area[order].free_list[t], lru) {
2718                         unsigned long i;
2719
2720                         pfn = page_to_pfn(page);
2721                         for (i = 0; i < (1UL << order); i++) {
2722                                 if (!--page_count) {
2723                                         touch_nmi_watchdog();
2724                                         page_count = WD_PAGE_COUNT;
2725                                 }
2726                                 swsusp_set_page_free(pfn_to_page(pfn + i));
2727                         }
2728                 }
2729         }
2730         spin_unlock_irqrestore(&zone->lock, flags);
2731 }
2732 #endif /* CONFIG_PM */
2733
2734 static bool free_unref_page_prepare(struct page *page, unsigned long pfn)
2735 {
2736         int migratetype;
2737
2738         if (!free_pcp_prepare(page))
2739                 return false;
2740
2741         migratetype = get_pfnblock_migratetype(page, pfn);
2742         set_pcppage_migratetype(page, migratetype);
2743         return true;
2744 }
2745
2746 static void free_unref_page_commit(struct page *page, unsigned long pfn)
2747 {
2748         struct zone *zone = page_zone(page);
2749         struct per_cpu_pages *pcp;
2750         int migratetype;
2751
2752         migratetype = get_pcppage_migratetype(page);
2753         __count_vm_event(PGFREE);
2754
2755         /*
2756          * We only track unmovable, reclaimable and movable on pcp lists.
2757          * Free ISOLATE pages back to the allocator because they are being
2758          * offlined but treat HIGHATOMIC as movable pages so we can get those
2759          * areas back if necessary. Otherwise, we may have to free
2760          * excessively into the page allocator
2761          */
2762         if (migratetype >= MIGRATE_PCPTYPES) {
2763                 if (unlikely(is_migrate_isolate(migratetype))) {
2764                         free_one_page(zone, page, pfn, 0, migratetype);
2765                         return;
2766                 }
2767                 migratetype = MIGRATE_MOVABLE;
2768         }
2769
2770         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2771         list_add(&page->lru, &pcp->lists[migratetype]);
2772         pcp->count++;
2773         if (pcp->count >= pcp->high) {
2774                 unsigned long batch = READ_ONCE(pcp->batch);
2775                 free_pcppages_bulk(zone, batch, pcp);
2776         }
2777 }
2778
2779 /*
2780  * Free a 0-order page
2781  */
2782 void free_unref_page(struct page *page)
2783 {
2784         unsigned long flags;
2785         unsigned long pfn = page_to_pfn(page);
2786
2787         if (!free_unref_page_prepare(page, pfn))
2788                 return;
2789
2790         local_irq_save(flags);
2791         free_unref_page_commit(page, pfn);
2792         local_irq_restore(flags);
2793 }
2794
2795 /*
2796  * Free a list of 0-order pages
2797  */
2798 void free_unref_page_list(struct list_head *list)
2799 {
2800         struct page *page, *next;
2801         unsigned long flags, pfn;
2802         int batch_count = 0;
2803
2804         /* Prepare pages for freeing */
2805         list_for_each_entry_safe(page, next, list, lru) {
2806                 pfn = page_to_pfn(page);
2807                 if (!free_unref_page_prepare(page, pfn))
2808                         list_del(&page->lru);
2809                 set_page_private(page, pfn);
2810         }
2811
2812         local_irq_save(flags);
2813         list_for_each_entry_safe(page, next, list, lru) {
2814                 unsigned long pfn = page_private(page);
2815
2816                 set_page_private(page, 0);
2817                 trace_mm_page_free_batched(page);
2818                 free_unref_page_commit(page, pfn);
2819
2820                 /*
2821                  * Guard against excessive IRQ disabled times when we get
2822                  * a large list of pages to free.
2823                  */
2824                 if (++batch_count == SWAP_CLUSTER_MAX) {
2825                         local_irq_restore(flags);
2826                         batch_count = 0;
2827                         local_irq_save(flags);
2828                 }
2829         }
2830         local_irq_restore(flags);
2831 }
2832
2833 /*
2834  * split_page takes a non-compound higher-order page, and splits it into
2835  * n (1<<order) sub-pages: page[0..n]
2836  * Each sub-page must be freed individually.
2837  *
2838  * Note: this is probably too low level an operation for use in drivers.
2839  * Please consult with lkml before using this in your driver.
2840  */
2841 void split_page(struct page *page, unsigned int order)
2842 {
2843         int i;
2844
2845         VM_BUG_ON_PAGE(PageCompound(page), page);
2846         VM_BUG_ON_PAGE(!page_count(page), page);
2847
2848         for (i = 1; i < (1 << order); i++)
2849                 set_page_refcounted(page + i);
2850         split_page_owner(page, order);
2851 }
2852 EXPORT_SYMBOL_GPL(split_page);
2853
2854 int __isolate_free_page(struct page *page, unsigned int order)
2855 {
2856         unsigned long watermark;
2857         struct zone *zone;
2858         int mt;
2859
2860         BUG_ON(!PageBuddy(page));
2861
2862         zone = page_zone(page);
2863         mt = get_pageblock_migratetype(page);
2864
2865         if (!is_migrate_isolate(mt)) {
2866                 /*
2867                  * Obey watermarks as if the page was being allocated. We can
2868                  * emulate a high-order watermark check with a raised order-0
2869                  * watermark, because we already know our high-order page
2870                  * exists.
2871                  */
2872                 watermark = min_wmark_pages(zone) + (1UL << order);
2873                 if (!zone_watermark_ok(zone, 0, watermark, 0, ALLOC_CMA))
2874                         return 0;
2875
2876                 __mod_zone_freepage_state(zone, -(1UL << order), mt);
2877         }
2878
2879         /* Remove page from free list */
2880         list_del(&page->lru);
2881         zone->free_area[order].nr_free--;
2882         rmv_page_order(page);
2883
2884         /*
2885          * Set the pageblock if the isolated page is at least half of a
2886          * pageblock
2887          */
2888         if (order >= pageblock_order - 1) {
2889                 struct page *endpage = page + (1 << order) - 1;
2890                 for (; page < endpage; page += pageblock_nr_pages) {
2891                         int mt = get_pageblock_migratetype(page);
2892                         if (!is_migrate_isolate(mt) && !is_migrate_cma(mt)
2893                             && !is_migrate_highatomic(mt))
2894                                 set_pageblock_migratetype(page,
2895                                                           MIGRATE_MOVABLE);
2896                 }
2897         }
2898
2899
2900         return 1UL << order;
2901 }
2902
2903 /*
2904  * Update NUMA hit/miss statistics
2905  *
2906  * Must be called with interrupts disabled.
2907  */
2908 static inline void zone_statistics(struct zone *preferred_zone, struct zone *z)
2909 {
2910 #ifdef CONFIG_NUMA
2911         enum numa_stat_item local_stat = NUMA_LOCAL;
2912
2913         /* skip numa counters update if numa stats is disabled */
2914         if (!static_branch_likely(&vm_numa_stat_key))
2915                 return;
2916
2917         if (zone_to_nid(z) != numa_node_id())
2918                 local_stat = NUMA_OTHER;
2919
2920         if (zone_to_nid(z) == zone_to_nid(preferred_zone))
2921                 __inc_numa_state(z, NUMA_HIT);
2922         else {
2923                 __inc_numa_state(z, NUMA_MISS);
2924                 __inc_numa_state(preferred_zone, NUMA_FOREIGN);
2925         }
2926         __inc_numa_state(z, local_stat);
2927 #endif
2928 }
2929
2930 /* Remove page from the per-cpu list, caller must protect the list */
2931 static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
2932                         struct per_cpu_pages *pcp,
2933                         struct list_head *list)
2934 {
2935         struct page *page;
2936
2937         do {
2938                 if (list_empty(list)) {
2939                         pcp->count += rmqueue_bulk(zone, 0,
2940                                         pcp->batch, list,
2941                                         migratetype);
2942                         if (unlikely(list_empty(list)))
2943                                 return NULL;
2944                 }
2945
2946                 page = list_first_entry(list, struct page, lru);
2947                 list_del(&page->lru);
2948                 pcp->count--;
2949         } while (check_new_pcp(page));
2950
2951         return page;
2952 }
2953
2954 /* Lock and remove page from the per-cpu list */
2955 static struct page *rmqueue_pcplist(struct zone *preferred_zone,
2956                         struct zone *zone, unsigned int order,
2957                         gfp_t gfp_flags, int migratetype)
2958 {
2959         struct per_cpu_pages *pcp;
2960         struct list_head *list;
2961         struct page *page;
2962         unsigned long flags;
2963
2964         local_irq_save(flags);
2965         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2966         list = &pcp->lists[migratetype];
2967         page = __rmqueue_pcplist(zone,  migratetype, pcp, list);
2968         if (page) {
2969                 __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2970                 zone_statistics(preferred_zone, zone);
2971         }
2972         local_irq_restore(flags);
2973         return page;
2974 }
2975
2976 /*
2977  * Allocate a page from the given zone. Use pcplists for order-0 allocations.
2978  */
2979 static inline
2980 struct page *rmqueue(struct zone *preferred_zone,
2981                         struct zone *zone, unsigned int order,
2982                         gfp_t gfp_flags, unsigned int alloc_flags,
2983                         int migratetype)
2984 {
2985         unsigned long flags;
2986         struct page *page;
2987
2988         if (likely(order == 0)) {
2989                 page = rmqueue_pcplist(preferred_zone, zone, order,
2990                                 gfp_flags, migratetype);
2991                 goto out;
2992         }
2993
2994         /*
2995          * We most definitely don't want callers attempting to
2996          * allocate greater than order-1 page units with __GFP_NOFAIL.
2997          */
2998         WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
2999         spin_lock_irqsave(&zone->lock, flags);
3000
3001         do {
3002                 page = NULL;
3003                 if (alloc_flags & ALLOC_HARDER) {
3004                         page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
3005                         if (page)
3006                                 trace_mm_page_alloc_zone_locked(page, order, migratetype);
3007                 }
3008                 if (!page)
3009                         page = __rmqueue(zone, order, migratetype);
3010         } while (page && check_new_pages(page, order));
3011         spin_unlock(&zone->lock);
3012         if (!page)
3013                 goto failed;
3014         __mod_zone_freepage_state(zone, -(1 << order),
3015                                   get_pcppage_migratetype(page));
3016
3017         __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
3018         zone_statistics(preferred_zone, zone);
3019         local_irq_restore(flags);
3020
3021 out:
3022         VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
3023         return page;
3024
3025 failed:
3026         local_irq_restore(flags);
3027         return NULL;
3028 }
3029
3030 #ifdef CONFIG_FAIL_PAGE_ALLOC
3031
3032 static struct {
3033         struct fault_attr attr;
3034
3035         bool ignore_gfp_highmem;
3036         bool ignore_gfp_reclaim;
3037         u32 min_order;
3038 } fail_page_alloc = {
3039         .attr = FAULT_ATTR_INITIALIZER,
3040         .ignore_gfp_reclaim = true,
3041         .ignore_gfp_highmem = true,
3042         .min_order = 1,
3043 };
3044
3045 static int __init setup_fail_page_alloc(char *str)
3046 {
3047         return setup_fault_attr(&fail_page_alloc.attr, str);
3048 }
3049 __setup("fail_page_alloc=", setup_fail_page_alloc);
3050
3051 static bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
3052 {
3053         if (order < fail_page_alloc.min_order)
3054                 return false;
3055         if (gfp_mask & __GFP_NOFAIL)
3056                 return false;
3057         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
3058                 return false;
3059         if (fail_page_alloc.ignore_gfp_reclaim &&
3060                         (gfp_mask & __GFP_DIRECT_RECLAIM))
3061                 return false;
3062
3063         return should_fail(&fail_page_alloc.attr, 1 << order);
3064 }
3065
3066 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
3067
3068 static int __init fail_page_alloc_debugfs(void)
3069 {
3070         umode_t mode = S_IFREG | 0600;
3071         struct dentry *dir;
3072
3073         dir = fault_create_debugfs_attr("fail_page_alloc", NULL,
3074                                         &fail_page_alloc.attr);
3075         if (IS_ERR(dir))
3076                 return PTR_ERR(dir);
3077
3078         if (!debugfs_create_bool("ignore-gfp-wait", mode, dir,
3079                                 &fail_page_alloc.ignore_gfp_reclaim))
3080                 goto fail;
3081         if (!debugfs_create_bool("ignore-gfp-highmem", mode, dir,
3082                                 &fail_page_alloc.ignore_gfp_highmem))
3083                 goto fail;
3084         if (!debugfs_create_u32("min-order", mode, dir,
3085                                 &fail_page_alloc.min_order))
3086                 goto fail;
3087
3088         return 0;
3089 fail:
3090         debugfs_remove_recursive(dir);
3091
3092         return -ENOMEM;
3093 }
3094
3095 late_initcall(fail_page_alloc_debugfs);
3096
3097 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
3098
3099 #else /* CONFIG_FAIL_PAGE_ALLOC */
3100
3101 static inline bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
3102 {
3103         return false;
3104 }
3105
3106 #endif /* CONFIG_FAIL_PAGE_ALLOC */
3107
3108 /*
3109  * Return true if free base pages are above 'mark'. For high-order checks it
3110  * will return true of the order-0 watermark is reached and there is at least
3111  * one free page of a suitable size. Checking now avoids taking the zone lock
3112  * to check in the allocation paths if no pages are free.
3113  */
3114 bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
3115                          int classzone_idx, unsigned int alloc_flags,
3116                          long free_pages)
3117 {
3118         long min = mark;
3119         int o;
3120         const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM));
3121
3122         /* free_pages may go negative - that's OK */
3123         free_pages -= (1 << order) - 1;
3124
3125         if (alloc_flags & ALLOC_HIGH)
3126                 min -= min / 2;
3127
3128         /*
3129          * If the caller does not have rights to ALLOC_HARDER then subtract
3130          * the high-atomic reserves. This will over-estimate the size of the
3131          * atomic reserve but it avoids a search.
3132          */
3133         if (likely(!alloc_harder)) {
3134                 free_pages -= z->nr_reserved_highatomic;
3135         } else {
3136                 /*
3137                  * OOM victims can try even harder than normal ALLOC_HARDER
3138                  * users on the grounds that it's definitely going to be in
3139                  * the exit path shortly and free memory. Any allocation it
3140                  * makes during the free path will be small and short-lived.
3141                  */
3142                 if (alloc_flags & ALLOC_OOM)
3143                         min -= min / 2;
3144                 else
3145                         min -= min / 4;
3146         }
3147
3148
3149 #ifdef CONFIG_CMA
3150         /* If allocation can't use CMA areas don't use free CMA pages */
3151         if (!(alloc_flags & ALLOC_CMA))
3152                 free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);
3153 #endif
3154
3155         /*
3156          * Check watermarks for an order-0 allocation request. If these
3157          * are not met, then a high-order request also cannot go ahead
3158          * even if a suitable page happened to be free.
3159          */
3160         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
3161                 return false;
3162
3163         /* If this is an order-0 request then the watermark is fine */
3164         if (!order)
3165                 return true;
3166
3167         /* For a high-order request, check at least one suitable page is free */
3168         for (o = order; o < MAX_ORDER; o++) {
3169                 struct free_area *area = &z->free_area[o];
3170                 int mt;
3171
3172                 if (!area->nr_free)
3173                         continue;
3174
3175                 for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
3176                         if (!list_empty(&area->free_list[mt]))
3177                                 return true;
3178                 }
3179
3180 #ifdef CONFIG_CMA
3181                 if ((alloc_flags & ALLOC_CMA) &&
3182                     !list_empty(&area->free_list[MIGRATE_CMA])) {
3183                         return true;
3184                 }
3185 #endif
3186                 if (alloc_harder &&
3187                         !list_empty(&area->free_list[MIGRATE_HIGHATOMIC]))
3188                         return true;
3189         }
3190         return false;
3191 }
3192
3193 bool zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
3194                       int classzone_idx, unsigned int alloc_flags)
3195 {
3196         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
3197                                         zone_page_state(z, NR_FREE_PAGES));
3198 }
3199
3200 static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
3201                 unsigned long mark, int classzone_idx, unsigned int alloc_flags)
3202 {
3203         long free_pages = zone_page_state(z, NR_FREE_PAGES);
3204         long cma_pages = 0;
3205
3206 #ifdef CONFIG_CMA
3207         /* If allocation can't use CMA areas don't use free CMA pages */
3208         if (!(alloc_flags & ALLOC_CMA))
3209                 cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
3210 #endif
3211
3212         /*
3213          * Fast check for order-0 only. If this fails then the reserves
3214          * need to be calculated. There is a corner case where the check
3215          * passes but only the high-order atomic reserve are free. If
3216          * the caller is !atomic then it'll uselessly search the free
3217          * list. That corner case is then slower but it is harmless.
3218          */
3219         if (!order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])
3220                 return true;
3221
3222         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
3223                                         free_pages);
3224 }
3225
3226 bool zone_watermark_ok_safe(struct zone *z, unsigned int order,
3227                         unsigned long mark, int classzone_idx)
3228 {
3229         long free_pages = zone_page_state(z, NR_FREE_PAGES);
3230
3231         if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
3232                 free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
3233
3234         return __zone_watermark_ok(z, order, mark, classzone_idx, 0,
3235                                                                 free_pages);
3236 }
3237
3238 #ifdef CONFIG_NUMA
3239 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3240 {
3241         return node_distance(zone_to_nid(local_zone), zone_to_nid(zone)) <=
3242                                 RECLAIM_DISTANCE;
3243 }
3244 #else   /* CONFIG_NUMA */
3245 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3246 {
3247         return true;
3248 }
3249 #endif  /* CONFIG_NUMA */
3250
3251 /*
3252  * get_page_from_freelist goes through the zonelist trying to allocate
3253  * a page.
3254  */
3255 static struct page *
3256 get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
3257                                                 const struct alloc_context *ac)
3258 {
3259         struct zoneref *z = ac->preferred_zoneref;
3260         struct zone *zone;
3261         struct pglist_data *last_pgdat_dirty_limit = NULL;
3262
3263         /*
3264          * Scan zonelist, looking for a zone with enough free.
3265          * See also __cpuset_node_allowed() comment in kernel/cpuset.c.
3266          */
3267         for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
3268                                                                 ac->nodemask) {
3269                 struct page *page;
3270                 unsigned long mark;
3271
3272                 if (cpusets_enabled() &&
3273                         (alloc_flags & ALLOC_CPUSET) &&
3274                         !__cpuset_zone_allowed(zone, gfp_mask))
3275                                 continue;
3276                 /*
3277                  * When allocating a page cache page for writing, we
3278                  * want to get it from a node that is within its dirty
3279                  * limit, such that no single node holds more than its
3280                  * proportional share of globally allowed dirty pages.
3281                  * The dirty limits take into account the node's
3282                  * lowmem reserves and high watermark so that kswapd
3283                  * should be able to balance it without having to
3284                  * write pages from its LRU list.
3285                  *
3286                  * XXX: For now, allow allocations to potentially
3287                  * exceed the per-node dirty limit in the slowpath
3288                  * (spread_dirty_pages unset) before going into reclaim,
3289                  * which is important when on a NUMA setup the allowed
3290                  * nodes are together not big enough to reach the
3291                  * global limit.  The proper fix for these situations
3292                  * will require awareness of nodes in the
3293                  * dirty-throttling and the flusher threads.
3294                  */
3295                 if (ac->spread_dirty_pages) {
3296                         if (last_pgdat_dirty_limit == zone->zone_pgdat)
3297                                 continue;
3298
3299                         if (!node_dirty_ok(zone->zone_pgdat)) {
3300                                 last_pgdat_dirty_limit = zone->zone_pgdat;
3301                                 continue;
3302                         }
3303                 }
3304
3305                 mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
3306                 if (!zone_watermark_fast(zone, order, mark,
3307                                        ac_classzone_idx(ac), alloc_flags)) {
3308                         int ret;
3309
3310 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
3311                         /*
3312                          * Watermark failed for this zone, but see if we can
3313                          * grow this zone if it contains deferred pages.
3314                          */
3315                         if (static_branch_unlikely(&deferred_pages)) {
3316                                 if (_deferred_grow_zone(zone, order))
3317                                         goto try_this_zone;
3318                         }
3319 #endif
3320                         /* Checked here to keep the fast path fast */
3321                         BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
3322                         if (alloc_flags & ALLOC_NO_WATERMARKS)
3323                                 goto try_this_zone;
3324
3325                         if (node_reclaim_mode == 0 ||
3326                             !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
3327                                 continue;
3328
3329                         ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
3330                         switch (ret) {
3331                         case NODE_RECLAIM_NOSCAN:
3332                                 /* did not scan */
3333                                 continue;
3334                         case NODE_RECLAIM_FULL:
3335                                 /* scanned but unreclaimable */
3336                                 continue;
3337                         default:
3338                                 /* did we reclaim enough */
3339                                 if (zone_watermark_ok(zone, order, mark,
3340                                                 ac_classzone_idx(ac), alloc_flags))
3341                                         goto try_this_zone;
3342
3343                                 continue;
3344                         }
3345                 }
3346
3347 try_this_zone:
3348                 page = rmqueue(ac->preferred_zoneref->zone, zone, order,
3349                                 gfp_mask, alloc_flags, ac->migratetype);
3350                 if (page) {
3351                         prep_new_page(page, order, gfp_mask, alloc_flags);
3352
3353                         /*
3354                          * If this is a high-order atomic allocation then check
3355                          * if the pageblock should be reserved for the future
3356                          */
3357                         if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
3358                                 reserve_highatomic_pageblock(page, zone, order);
3359
3360                         return page;
3361                 } else {
3362 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
3363                         /* Try again if zone has deferred pages */
3364                         if (static_branch_unlikely(&deferred_pages)) {
3365                                 if (_deferred_grow_zone(zone, order))
3366                                         goto try_this_zone;
3367                         }
3368 #endif
3369                 }
3370         }
3371
3372         return NULL;
3373 }
3374
3375 static void warn_alloc_show_mem(gfp_t gfp_mask, nodemask_t *nodemask)
3376 {
3377         unsigned int filter = SHOW_MEM_FILTER_NODES;
3378         static DEFINE_RATELIMIT_STATE(show_mem_rs, HZ, 1);
3379
3380         if (!__ratelimit(&show_mem_rs))
3381                 return;
3382
3383         /*
3384          * This documents exceptions given to allocations in certain
3385          * contexts that are allowed to allocate outside current's set
3386          * of allowed nodes.
3387          */
3388         if (!(gfp_mask & __GFP_NOMEMALLOC))
3389                 if (tsk_is_oom_victim(current) ||
3390                     (current->flags & (PF_MEMALLOC | PF_EXITING)))
3391                         filter &= ~SHOW_MEM_FILTER_NODES;
3392         if (in_interrupt() || !(gfp_mask & __GFP_DIRECT_RECLAIM))
3393                 filter &= ~SHOW_MEM_FILTER_NODES;
3394
3395         show_mem(filter, nodemask);
3396 }
3397
3398 void warn_alloc(gfp_t gfp_mask, nodemask_t *nodemask, const char *fmt, ...)
3399 {
3400         struct va_format vaf;
3401         va_list args;
3402         static DEFINE_RATELIMIT_STATE(nopage_rs, DEFAULT_RATELIMIT_INTERVAL,
3403                                       DEFAULT_RATELIMIT_BURST);
3404
3405         if ((gfp_mask & __GFP_NOWARN) || !__ratelimit(&nopage_rs))
3406                 return;
3407
3408         va_start(args, fmt);
3409         vaf.fmt = fmt;
3410         vaf.va = &args;
3411         pr_warn("%s: %pV, mode:%#x(%pGg), nodemask=%*pbl\n",
3412                         current->comm, &vaf, gfp_mask, &gfp_mask,
3413                         nodemask_pr_args(nodemask));
3414         va_end(args);
3415
3416         cpuset_print_current_mems_allowed();
3417
3418         dump_stack();
3419         warn_alloc_show_mem(gfp_mask, nodemask);
3420 }
3421
3422 static inline struct page *
3423 __alloc_pages_cpuset_fallback(gfp_t gfp_mask, unsigned int order,
3424                               unsigned int alloc_flags,
3425                               const struct alloc_context *ac)
3426 {
3427         struct page *page;
3428
3429         page = get_page_from_freelist(gfp_mask, order,
3430                         alloc_flags|ALLOC_CPUSET, ac);
3431         /*
3432          * fallback to ignore cpuset restriction if our nodes
3433          * are depleted
3434          */
3435         if (!page)
3436                 page = get_page_from_freelist(gfp_mask, order,
3437                                 alloc_flags, ac);
3438
3439         return page;
3440 }
3441
3442 static inline struct page *
3443 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
3444         const struct alloc_context *ac, unsigned long *did_some_progress)
3445 {
3446         struct oom_control oc = {
3447                 .zonelist = ac->zonelist,
3448                 .nodemask = ac->nodemask,
3449                 .memcg = NULL,
3450                 .gfp_mask = gfp_mask,
3451                 .order = order,
3452         };
3453         struct page *page;
3454
3455         *did_some_progress = 0;
3456
3457         /*
3458          * Acquire the oom lock.  If that fails, somebody else is
3459          * making progress for us.
3460          */
3461         if (!mutex_trylock(&oom_lock)) {
3462                 *did_some_progress = 1;
3463                 schedule_timeout_uninterruptible(1);
3464                 return NULL;
3465         }
3466
3467         /*
3468          * Go through the zonelist yet one more time, keep very high watermark
3469          * here, this is only to catch a parallel oom killing, we must fail if
3470          * we're still under heavy pressure. But make sure that this reclaim
3471          * attempt shall not depend on __GFP_DIRECT_RECLAIM && !__GFP_NORETRY
3472          * allocation which will never fail due to oom_lock already held.
3473          */
3474         page = get_page_from_freelist((gfp_mask | __GFP_HARDWALL) &
3475                                       ~__GFP_DIRECT_RECLAIM, order,
3476                                       ALLOC_WMARK_HIGH|ALLOC_CPUSET, ac);
3477         if (page)
3478                 goto out;
3479
3480         /* Coredumps can quickly deplete all memory reserves */
3481         if (current->flags & PF_DUMPCORE)
3482                 goto out;
3483         /* The OOM killer will not help higher order allocs */
3484         if (order > PAGE_ALLOC_COSTLY_ORDER)
3485                 goto out;
3486         /*
3487          * We have already exhausted all our reclaim opportunities without any
3488          * success so it is time to admit defeat. We will skip the OOM killer
3489          * because it is very likely that the caller has a more reasonable
3490          * fallback than shooting a random task.
3491          */
3492         if (gfp_mask & __GFP_RETRY_MAYFAIL)
3493                 goto out;
3494         /* The OOM killer does not needlessly kill tasks for lowmem */
3495         if (ac->high_zoneidx < ZONE_NORMAL)
3496                 goto out;
3497         if (pm_suspended_storage())
3498                 goto out;
3499         /*
3500          * XXX: GFP_NOFS allocations should rather fail than rely on
3501          * other request to make a forward progress.
3502          * We are in an unfortunate situation where out_of_memory cannot
3503          * do much for this context but let's try it to at least get
3504          * access to memory reserved if the current task is killed (see
3505          * out_of_memory). Once filesystems are ready to handle allocation
3506          * failures more gracefully we should just bail out here.
3507          */
3508
3509         /* The OOM killer may not free memory on a specific node */
3510         if (gfp_mask & __GFP_THISNODE)
3511                 goto out;
3512
3513         /* Exhausted what can be done so it's blame time */
3514         if (out_of_memory(&oc) || WARN_ON_ONCE(gfp_mask & __GFP_NOFAIL)) {
3515                 *did_some_progress = 1;
3516
3517                 /*
3518                  * Help non-failing allocations by giving them access to memory
3519                  * reserves
3520                  */
3521                 if (gfp_mask & __GFP_NOFAIL)
3522                         page = __alloc_pages_cpuset_fallback(gfp_mask, order,
3523                                         ALLOC_NO_WATERMARKS, ac);
3524         }
3525 out:
3526         mutex_unlock(&oom_lock);
3527         return page;
3528 }
3529
3530 /*
3531  * Maximum number of compaction retries wit a progress before OOM
3532  * killer is consider as the only way to move forward.
3533  */
3534 #define MAX_COMPACT_RETRIES 16
3535
3536 #ifdef CONFIG_COMPACTION
3537 /* Try memory compaction for high-order allocations before reclaim */
3538 static struct page *
3539 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,