3183eb2f579cb29a6cbb2d204e284e56c429dd33
[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/notifier.h>
36 #include <linux/topology.h>
37 #include <linux/sysctl.h>
38 #include <linux/cpu.h>
39 #include <linux/cpuset.h>
40 #include <linux/memory_hotplug.h>
41 #include <linux/nodemask.h>
42 #include <linux/vmalloc.h>
43 #include <linux/vmstat.h>
44 #include <linux/mempolicy.h>
45 #include <linux/memremap.h>
46 #include <linux/stop_machine.h>
47 #include <linux/sort.h>
48 #include <linux/pfn.h>
49 #include <xen/xen.h>
50 #include <linux/backing-dev.h>
51 #include <linux/fault-inject.h>
52 #include <linux/page-isolation.h>
53 #include <linux/page_ext.h>
54 #include <linux/debugobjects.h>
55 #include <linux/kmemleak.h>
56 #include <linux/compaction.h>
57 #include <trace/events/kmem.h>
58 #include <trace/events/oom.h>
59 #include <linux/prefetch.h>
60 #include <linux/mm_inline.h>
61 #include <linux/migrate.h>
62 #include <linux/hugetlb.h>
63 #include <linux/sched/rt.h>
64 #include <linux/sched/mm.h>
65 #include <linux/page_owner.h>
66 #include <linux/kthread.h>
67 #include <linux/memcontrol.h>
68 #include <linux/ftrace.h>
69 #include <linux/lockdep.h>
70 #include <linux/nmi.h>
71
72 #include <asm/sections.h>
73 #include <asm/tlbflush.h>
74 #include <asm/div64.h>
75 #include "internal.h"
76
77 /* prevent >1 _updater_ of zone percpu pageset ->high and ->batch fields */
78 static DEFINE_MUTEX(pcp_batch_high_lock);
79 #define MIN_PERCPU_PAGELIST_FRACTION    (8)
80
81 #ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
82 DEFINE_PER_CPU(int, numa_node);
83 EXPORT_PER_CPU_SYMBOL(numa_node);
84 #endif
85
86 DEFINE_STATIC_KEY_TRUE(vm_numa_stat_key);
87
88 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
89 /*
90  * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
91  * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
92  * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
93  * defined in <linux/topology.h>.
94  */
95 DEFINE_PER_CPU(int, _numa_mem_);                /* Kernel "local memory" node */
96 EXPORT_PER_CPU_SYMBOL(_numa_mem_);
97 int _node_numa_mem_[MAX_NUMNODES];
98 #endif
99
100 /* work_structs for global per-cpu drains */
101 DEFINE_MUTEX(pcpu_drain_mutex);
102 DEFINE_PER_CPU(struct work_struct, pcpu_drain);
103
104 #ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
105 volatile unsigned long latent_entropy __latent_entropy;
106 EXPORT_SYMBOL(latent_entropy);
107 #endif
108
109 /*
110  * Array of node states.
111  */
112 nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
113         [N_POSSIBLE] = NODE_MASK_ALL,
114         [N_ONLINE] = { { [0] = 1UL } },
115 #ifndef CONFIG_NUMA
116         [N_NORMAL_MEMORY] = { { [0] = 1UL } },
117 #ifdef CONFIG_HIGHMEM
118         [N_HIGH_MEMORY] = { { [0] = 1UL } },
119 #endif
120         [N_MEMORY] = { { [0] = 1UL } },
121         [N_CPU] = { { [0] = 1UL } },
122 #endif  /* NUMA */
123 };
124 EXPORT_SYMBOL(node_states);
125
126 /* Protect totalram_pages and zone->managed_pages */
127 static DEFINE_SPINLOCK(managed_page_count_lock);
128
129 unsigned long totalram_pages __read_mostly;
130 unsigned long totalreserve_pages __read_mostly;
131 unsigned long totalcma_pages __read_mostly;
132
133 int percpu_pagelist_fraction;
134 gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
135
136 /*
137  * A cached value of the page's pageblock's migratetype, used when the page is
138  * put on a pcplist. Used to avoid the pageblock migratetype lookup when
139  * freeing from pcplists in most cases, at the cost of possibly becoming stale.
140  * Also the migratetype set in the page does not necessarily match the pcplist
141  * index, e.g. page might have MIGRATE_CMA set but be on a pcplist with any
142  * other index - this ensures that it will be put on the correct CMA freelist.
143  */
144 static inline int get_pcppage_migratetype(struct page *page)
145 {
146         return page->index;
147 }
148
149 static inline void set_pcppage_migratetype(struct page *page, int migratetype)
150 {
151         page->index = migratetype;
152 }
153
154 #ifdef CONFIG_PM_SLEEP
155 /*
156  * The following functions are used by the suspend/hibernate code to temporarily
157  * change gfp_allowed_mask in order to avoid using I/O during memory allocations
158  * while devices are suspended.  To avoid races with the suspend/hibernate code,
159  * they should always be called with pm_mutex held (gfp_allowed_mask also should
160  * only be modified with pm_mutex held, unless the suspend/hibernate code is
161  * guaranteed not to run in parallel 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(&pm_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(&pm_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-1] = {
209 #ifdef CONFIG_ZONE_DMA
210          256,
211 #endif
212 #ifdef CONFIG_ZONE_DMA32
213          256,
214 #endif
215 #ifdef CONFIG_HIGHMEM
216          32,
217 #endif
218          32,
219 };
220
221 EXPORT_SYMBOL(totalram_pages);
222
223 static char * const zone_names[MAX_NR_ZONES] = {
224 #ifdef CONFIG_ZONE_DMA
225          "DMA",
226 #endif
227 #ifdef CONFIG_ZONE_DMA32
228          "DMA32",
229 #endif
230          "Normal",
231 #ifdef CONFIG_HIGHMEM
232          "HighMem",
233 #endif
234          "Movable",
235 #ifdef CONFIG_ZONE_DEVICE
236          "Device",
237 #endif
238 };
239
240 char * const migratetype_names[MIGRATE_TYPES] = {
241         "Unmovable",
242         "Movable",
243         "Reclaimable",
244         "HighAtomic",
245 #ifdef CONFIG_CMA
246         "CMA",
247 #endif
248 #ifdef CONFIG_MEMORY_ISOLATION
249         "Isolate",
250 #endif
251 };
252
253 compound_page_dtor * const compound_page_dtors[] = {
254         NULL,
255         free_compound_page,
256 #ifdef CONFIG_HUGETLB_PAGE
257         free_huge_page,
258 #endif
259 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
260         free_transhuge_page,
261 #endif
262 };
263
264 int min_free_kbytes = 1024;
265 int user_min_free_kbytes = -1;
266 int watermark_scale_factor = 10;
267
268 static unsigned long __meminitdata nr_kernel_pages;
269 static unsigned long __meminitdata nr_all_pages;
270 static unsigned long __meminitdata dma_reserve;
271
272 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
273 static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
274 static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
275 static unsigned long __initdata required_kernelcore;
276 static unsigned long __initdata required_movablecore;
277 static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
278 static bool mirrored_kernelcore;
279
280 /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
281 int movable_zone;
282 EXPORT_SYMBOL(movable_zone);
283 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
284
285 #if MAX_NUMNODES > 1
286 int nr_node_ids __read_mostly = MAX_NUMNODES;
287 int nr_online_nodes __read_mostly = 1;
288 EXPORT_SYMBOL(nr_node_ids);
289 EXPORT_SYMBOL(nr_online_nodes);
290 #endif
291
292 int page_group_by_mobility_disabled __read_mostly;
293
294 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
295 /* Returns true if the struct page for the pfn is uninitialised */
296 static inline bool __meminit early_page_uninitialised(unsigned long pfn)
297 {
298         int nid = early_pfn_to_nid(pfn);
299
300         if (node_online(nid) && pfn >= NODE_DATA(nid)->first_deferred_pfn)
301                 return true;
302
303         return false;
304 }
305
306 /*
307  * Returns false when the remaining initialisation should be deferred until
308  * later in the boot cycle when it can be parallelised.
309  */
310 static inline bool update_defer_init(pg_data_t *pgdat,
311                                 unsigned long pfn, unsigned long zone_end,
312                                 unsigned long *nr_initialised)
313 {
314         /* Always populate low zones for address-constrained allocations */
315         if (zone_end < pgdat_end_pfn(pgdat))
316                 return true;
317         /* Xen PV domains need page structures early */
318         if (xen_pv_domain())
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 do 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 ->_mapcount
716  * PAGE_BUDDY_MAPCOUNT_VALUE.
717  * Setting, clearing, and testing _mapcount PAGE_BUDDY_MAPCOUNT_VALUE is
718  * serialized by zone->lock.
719  *
720  * For recording page's order, we use page_private(page).
721  */
722 static inline int page_is_buddy(struct page *page, struct page *buddy,
723                                                         unsigned int order)
724 {
725         if (page_is_guard(buddy) && page_order(buddy) == order) {
726                 if (page_zone_id(page) != page_zone_id(buddy))
727                         return 0;
728
729                 VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);
730
731                 return 1;
732         }
733
734         if (PageBuddy(buddy) && page_order(buddy) == order) {
735                 /*
736                  * zone check is done late to avoid uselessly
737                  * calculating zone/node ids for pages that could
738                  * never merge.
739                  */
740                 if (page_zone_id(page) != page_zone_id(buddy))
741                         return 0;
742
743                 VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);
744
745                 return 1;
746         }
747         return 0;
748 }
749
750 /*
751  * Freeing function for a buddy system allocator.
752  *
753  * The concept of a buddy system is to maintain direct-mapped table
754  * (containing bit values) for memory blocks of various "orders".
755  * The bottom level table contains the map for the smallest allocatable
756  * units of memory (here, pages), and each level above it describes
757  * pairs of units from the levels below, hence, "buddies".
758  * At a high level, all that happens here is marking the table entry
759  * at the bottom level available, and propagating the changes upward
760  * as necessary, plus some accounting needed to play nicely with other
761  * parts of the VM system.
762  * At each level, we keep a list of pages, which are heads of continuous
763  * free pages of length of (1 << order) and marked with _mapcount
764  * PAGE_BUDDY_MAPCOUNT_VALUE. Page's order is recorded in page_private(page)
765  * field.
766  * So when we are allocating or freeing one, we can derive the state of the
767  * other.  That is, if we allocate a small block, and both were
768  * free, the remainder of the region must be split into blocks.
769  * If a block is freed, and its buddy is also free, then this
770  * triggers coalescing into a block of larger size.
771  *
772  * -- nyc
773  */
774
775 static inline void __free_one_page(struct page *page,
776                 unsigned long pfn,
777                 struct zone *zone, unsigned int order,
778                 int migratetype)
779 {
780         unsigned long combined_pfn;
781         unsigned long uninitialized_var(buddy_pfn);
782         struct page *buddy;
783         unsigned int max_order;
784
785         max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
786
787         VM_BUG_ON(!zone_is_initialized(zone));
788         VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);
789
790         VM_BUG_ON(migratetype == -1);
791         if (likely(!is_migrate_isolate(migratetype)))
792                 __mod_zone_freepage_state(zone, 1 << order, migratetype);
793
794         VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
795         VM_BUG_ON_PAGE(bad_range(zone, page), page);
796
797 continue_merging:
798         while (order < max_order - 1) {
799                 buddy_pfn = __find_buddy_pfn(pfn, order);
800                 buddy = page + (buddy_pfn - pfn);
801
802                 if (!pfn_valid_within(buddy_pfn))
803                         goto done_merging;
804                 if (!page_is_buddy(page, buddy, order))
805                         goto done_merging;
806                 /*
807                  * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
808                  * merge with it and move up one order.
809                  */
810                 if (page_is_guard(buddy)) {
811                         clear_page_guard(zone, buddy, order, migratetype);
812                 } else {
813                         list_del(&buddy->lru);
814                         zone->free_area[order].nr_free--;
815                         rmv_page_order(buddy);
816                 }
817                 combined_pfn = buddy_pfn & pfn;
818                 page = page + (combined_pfn - pfn);
819                 pfn = combined_pfn;
820                 order++;
821         }
822         if (max_order < MAX_ORDER) {
823                 /* If we are here, it means order is >= pageblock_order.
824                  * We want to prevent merge between freepages on isolate
825                  * pageblock and normal pageblock. Without this, pageblock
826                  * isolation could cause incorrect freepage or CMA accounting.
827                  *
828                  * We don't want to hit this code for the more frequent
829                  * low-order merging.
830                  */
831                 if (unlikely(has_isolate_pageblock(zone))) {
832                         int buddy_mt;
833
834                         buddy_pfn = __find_buddy_pfn(pfn, order);
835                         buddy = page + (buddy_pfn - pfn);
836                         buddy_mt = get_pageblock_migratetype(buddy);
837
838                         if (migratetype != buddy_mt
839                                         && (is_migrate_isolate(migratetype) ||
840                                                 is_migrate_isolate(buddy_mt)))
841                                 goto done_merging;
842                 }
843                 max_order++;
844                 goto continue_merging;
845         }
846
847 done_merging:
848         set_page_order(page, order);
849
850         /*
851          * If this is not the largest possible page, check if the buddy
852          * of the next-highest order is free. If it is, it's possible
853          * that pages are being freed that will coalesce soon. In case,
854          * that is happening, add the free page to the tail of the list
855          * so it's less likely to be used soon and more likely to be merged
856          * as a higher order page
857          */
858         if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)) {
859                 struct page *higher_page, *higher_buddy;
860                 combined_pfn = buddy_pfn & pfn;
861                 higher_page = page + (combined_pfn - pfn);
862                 buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
863                 higher_buddy = higher_page + (buddy_pfn - combined_pfn);
864                 if (pfn_valid_within(buddy_pfn) &&
865                     page_is_buddy(higher_page, higher_buddy, order + 1)) {
866                         list_add_tail(&page->lru,
867                                 &zone->free_area[order].free_list[migratetype]);
868                         goto out;
869                 }
870         }
871
872         list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
873 out:
874         zone->free_area[order].nr_free++;
875 }
876
877 /*
878  * A bad page could be due to a number of fields. Instead of multiple branches,
879  * try and check multiple fields with one check. The caller must do a detailed
880  * check if necessary.
881  */
882 static inline bool page_expected_state(struct page *page,
883                                         unsigned long check_flags)
884 {
885         if (unlikely(atomic_read(&page->_mapcount) != -1))
886                 return false;
887
888         if (unlikely((unsigned long)page->mapping |
889                         page_ref_count(page) |
890 #ifdef CONFIG_MEMCG
891                         (unsigned long)page->mem_cgroup |
892 #endif
893                         (page->flags & check_flags)))
894                 return false;
895
896         return true;
897 }
898
899 static void free_pages_check_bad(struct page *page)
900 {
901         const char *bad_reason;
902         unsigned long bad_flags;
903
904         bad_reason = NULL;
905         bad_flags = 0;
906
907         if (unlikely(atomic_read(&page->_mapcount) != -1))
908                 bad_reason = "nonzero mapcount";
909         if (unlikely(page->mapping != NULL))
910                 bad_reason = "non-NULL mapping";
911         if (unlikely(page_ref_count(page) != 0))
912                 bad_reason = "nonzero _refcount";
913         if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_FREE)) {
914                 bad_reason = "PAGE_FLAGS_CHECK_AT_FREE flag(s) set";
915                 bad_flags = PAGE_FLAGS_CHECK_AT_FREE;
916         }
917 #ifdef CONFIG_MEMCG
918         if (unlikely(page->mem_cgroup))
919                 bad_reason = "page still charged to cgroup";
920 #endif
921         bad_page(page, bad_reason, bad_flags);
922 }
923
924 static inline int free_pages_check(struct page *page)
925 {
926         if (likely(page_expected_state(page, PAGE_FLAGS_CHECK_AT_FREE)))
927                 return 0;
928
929         /* Something has gone sideways, find it */
930         free_pages_check_bad(page);
931         return 1;
932 }
933
934 static int free_tail_pages_check(struct page *head_page, struct page *page)
935 {
936         int ret = 1;
937
938         /*
939          * We rely page->lru.next never has bit 0 set, unless the page
940          * is PageTail(). Let's make sure that's true even for poisoned ->lru.
941          */
942         BUILD_BUG_ON((unsigned long)LIST_POISON1 & 1);
943
944         if (!IS_ENABLED(CONFIG_DEBUG_VM)) {
945                 ret = 0;
946                 goto out;
947         }
948         switch (page - head_page) {
949         case 1:
950                 /* the first tail page: ->mapping is compound_mapcount() */
951                 if (unlikely(compound_mapcount(page))) {
952                         bad_page(page, "nonzero compound_mapcount", 0);
953                         goto out;
954                 }
955                 break;
956         case 2:
957                 /*
958                  * the second tail page: ->mapping is
959                  * page_deferred_list().next -- ignore value.
960                  */
961                 break;
962         default:
963                 if (page->mapping != TAIL_MAPPING) {
964                         bad_page(page, "corrupted mapping in tail page", 0);
965                         goto out;
966                 }
967                 break;
968         }
969         if (unlikely(!PageTail(page))) {
970                 bad_page(page, "PageTail not set", 0);
971                 goto out;
972         }
973         if (unlikely(compound_head(page) != head_page)) {
974                 bad_page(page, "compound_head not consistent", 0);
975                 goto out;
976         }
977         ret = 0;
978 out:
979         page->mapping = NULL;
980         clear_compound_head(page);
981         return ret;
982 }
983
984 static __always_inline bool free_pages_prepare(struct page *page,
985                                         unsigned int order, bool check_free)
986 {
987         int bad = 0;
988
989         VM_BUG_ON_PAGE(PageTail(page), page);
990
991         trace_mm_page_free(page, order);
992
993         /*
994          * Check tail pages before head page information is cleared to
995          * avoid checking PageCompound for order-0 pages.
996          */
997         if (unlikely(order)) {
998                 bool compound = PageCompound(page);
999                 int i;
1000
1001                 VM_BUG_ON_PAGE(compound && compound_order(page) != order, page);
1002
1003                 if (compound)
1004                         ClearPageDoubleMap(page);
1005                 for (i = 1; i < (1 << order); i++) {
1006                         if (compound)
1007                                 bad += free_tail_pages_check(page, page + i);
1008                         if (unlikely(free_pages_check(page + i))) {
1009                                 bad++;
1010                                 continue;
1011                         }
1012                         (page + i)->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
1013                 }
1014         }
1015         if (PageMappingFlags(page))
1016                 page->mapping = NULL;
1017         if (memcg_kmem_enabled() && PageKmemcg(page))
1018                 memcg_kmem_uncharge(page, order);
1019         if (check_free)
1020                 bad += free_pages_check(page);
1021         if (bad)
1022                 return false;
1023
1024         page_cpupid_reset_last(page);
1025         page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
1026         reset_page_owner(page, order);
1027
1028         if (!PageHighMem(page)) {
1029                 debug_check_no_locks_freed(page_address(page),
1030                                            PAGE_SIZE << order);
1031                 debug_check_no_obj_freed(page_address(page),
1032                                            PAGE_SIZE << order);
1033         }
1034         arch_free_page(page, order);
1035         kernel_poison_pages(page, 1 << order, 0);
1036         kernel_map_pages(page, 1 << order, 0);
1037         kasan_free_pages(page, order);
1038
1039         return true;
1040 }
1041
1042 #ifdef CONFIG_DEBUG_VM
1043 static inline bool free_pcp_prepare(struct page *page)
1044 {
1045         return free_pages_prepare(page, 0, true);
1046 }
1047
1048 static inline bool bulkfree_pcp_prepare(struct page *page)
1049 {
1050         return false;
1051 }
1052 #else
1053 static bool free_pcp_prepare(struct page *page)
1054 {
1055         return free_pages_prepare(page, 0, false);
1056 }
1057
1058 static bool bulkfree_pcp_prepare(struct page *page)
1059 {
1060         return free_pages_check(page);
1061 }
1062 #endif /* CONFIG_DEBUG_VM */
1063
1064 /*
1065  * Frees a number of pages from the PCP lists
1066  * Assumes all pages on list are in same zone, and of same order.
1067  * count is the number of pages to free.
1068  *
1069  * If the zone was previously in an "all pages pinned" state then look to
1070  * see if this freeing clears that state.
1071  *
1072  * And clear the zone's pages_scanned counter, to hold off the "all pages are
1073  * pinned" detection logic.
1074  */
1075 static void free_pcppages_bulk(struct zone *zone, int count,
1076                                         struct per_cpu_pages *pcp)
1077 {
1078         int migratetype = 0;
1079         int batch_free = 0;
1080         bool isolated_pageblocks;
1081
1082         spin_lock(&zone->lock);
1083         isolated_pageblocks = has_isolate_pageblock(zone);
1084
1085         while (count) {
1086                 struct page *page;
1087                 struct list_head *list;
1088
1089                 /*
1090                  * Remove pages from lists in a round-robin fashion. A
1091                  * batch_free count is maintained that is incremented when an
1092                  * empty list is encountered.  This is so more pages are freed
1093                  * off fuller lists instead of spinning excessively around empty
1094                  * lists
1095                  */
1096                 do {
1097                         batch_free++;
1098                         if (++migratetype == MIGRATE_PCPTYPES)
1099                                 migratetype = 0;
1100                         list = &pcp->lists[migratetype];
1101                 } while (list_empty(list));
1102
1103                 /* This is the only non-empty list. Free them all. */
1104                 if (batch_free == MIGRATE_PCPTYPES)
1105                         batch_free = count;
1106
1107                 do {
1108                         int mt; /* migratetype of the to-be-freed page */
1109
1110                         page = list_last_entry(list, struct page, lru);
1111                         /* must delete as __free_one_page list manipulates */
1112                         list_del(&page->lru);
1113
1114                         mt = get_pcppage_migratetype(page);
1115                         /* MIGRATE_ISOLATE page should not go to pcplists */
1116                         VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
1117                         /* Pageblock could have been isolated meanwhile */
1118                         if (unlikely(isolated_pageblocks))
1119                                 mt = get_pageblock_migratetype(page);
1120
1121                         if (bulkfree_pcp_prepare(page))
1122                                 continue;
1123
1124                         __free_one_page(page, page_to_pfn(page), zone, 0, mt);
1125                         trace_mm_page_pcpu_drain(page, 0, mt);
1126                 } while (--count && --batch_free && !list_empty(list));
1127         }
1128         spin_unlock(&zone->lock);
1129 }
1130
1131 static void free_one_page(struct zone *zone,
1132                                 struct page *page, unsigned long pfn,
1133                                 unsigned int order,
1134                                 int migratetype)
1135 {
1136         spin_lock(&zone->lock);
1137         if (unlikely(has_isolate_pageblock(zone) ||
1138                 is_migrate_isolate(migratetype))) {
1139                 migratetype = get_pfnblock_migratetype(page, pfn);
1140         }
1141         __free_one_page(page, pfn, zone, order, migratetype);
1142         spin_unlock(&zone->lock);
1143 }
1144
1145 static void __meminit __init_single_page(struct page *page, unsigned long pfn,
1146                                 unsigned long zone, int nid, bool zero)
1147 {
1148         if (zero)
1149                 mm_zero_struct_page(page);
1150         set_page_links(page, zone, nid, pfn);
1151         init_page_count(page);
1152         page_mapcount_reset(page);
1153         page_cpupid_reset_last(page);
1154
1155         INIT_LIST_HEAD(&page->lru);
1156 #ifdef WANT_PAGE_VIRTUAL
1157         /* The shift won't overflow because ZONE_NORMAL is below 4G. */
1158         if (!is_highmem_idx(zone))
1159                 set_page_address(page, __va(pfn << PAGE_SHIFT));
1160 #endif
1161 }
1162
1163 static void __meminit __init_single_pfn(unsigned long pfn, unsigned long zone,
1164                                         int nid, bool zero)
1165 {
1166         return __init_single_page(pfn_to_page(pfn), pfn, zone, nid, zero);
1167 }
1168
1169 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1170 static void __meminit init_reserved_page(unsigned long pfn)
1171 {
1172         pg_data_t *pgdat;
1173         int nid, zid;
1174
1175         if (!early_page_uninitialised(pfn))
1176                 return;
1177
1178         nid = early_pfn_to_nid(pfn);
1179         pgdat = NODE_DATA(nid);
1180
1181         for (zid = 0; zid < MAX_NR_ZONES; zid++) {
1182                 struct zone *zone = &pgdat->node_zones[zid];
1183
1184                 if (pfn >= zone->zone_start_pfn && pfn < zone_end_pfn(zone))
1185                         break;
1186         }
1187         __init_single_pfn(pfn, zid, nid, true);
1188 }
1189 #else
1190 static inline void init_reserved_page(unsigned long pfn)
1191 {
1192 }
1193 #endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
1194
1195 /*
1196  * Initialised pages do not have PageReserved set. This function is
1197  * called for each range allocated by the bootmem allocator and
1198  * marks the pages PageReserved. The remaining valid pages are later
1199  * sent to the buddy page allocator.
1200  */
1201 void __meminit reserve_bootmem_region(phys_addr_t start, phys_addr_t end)
1202 {
1203         unsigned long start_pfn = PFN_DOWN(start);
1204         unsigned long end_pfn = PFN_UP(end);
1205
1206         for (; start_pfn < end_pfn; start_pfn++) {
1207                 if (pfn_valid(start_pfn)) {
1208                         struct page *page = pfn_to_page(start_pfn);
1209
1210                         init_reserved_page(start_pfn);
1211
1212                         /* Avoid false-positive PageTail() */
1213                         INIT_LIST_HEAD(&page->lru);
1214
1215                         SetPageReserved(page);
1216                 }
1217         }
1218 }
1219
1220 static void __free_pages_ok(struct page *page, unsigned int order)
1221 {
1222         unsigned long flags;
1223         int migratetype;
1224         unsigned long pfn = page_to_pfn(page);
1225
1226         if (!free_pages_prepare(page, order, true))
1227                 return;
1228
1229         migratetype = get_pfnblock_migratetype(page, pfn);
1230         local_irq_save(flags);
1231         __count_vm_events(PGFREE, 1 << order);
1232         free_one_page(page_zone(page), page, pfn, order, migratetype);
1233         local_irq_restore(flags);
1234 }
1235
1236 static void __init __free_pages_boot_core(struct page *page, unsigned int order)
1237 {
1238         unsigned int nr_pages = 1 << order;
1239         struct page *p = page;
1240         unsigned int loop;
1241
1242         prefetchw(p);
1243         for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
1244                 prefetchw(p + 1);
1245                 __ClearPageReserved(p);
1246                 set_page_count(p, 0);
1247         }
1248         __ClearPageReserved(p);
1249         set_page_count(p, 0);
1250
1251         page_zone(page)->managed_pages += nr_pages;
1252         set_page_refcounted(page);
1253         __free_pages(page, order);
1254 }
1255
1256 #if defined(CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID) || \
1257         defined(CONFIG_HAVE_MEMBLOCK_NODE_MAP)
1258
1259 static struct mminit_pfnnid_cache early_pfnnid_cache __meminitdata;
1260
1261 int __meminit early_pfn_to_nid(unsigned long pfn)
1262 {
1263         static DEFINE_SPINLOCK(early_pfn_lock);
1264         int nid;
1265
1266         spin_lock(&early_pfn_lock);
1267         nid = __early_pfn_to_nid(pfn, &early_pfnnid_cache);
1268         if (nid < 0)
1269                 nid = first_online_node;
1270         spin_unlock(&early_pfn_lock);
1271
1272         return nid;
1273 }
1274 #endif
1275
1276 #ifdef CONFIG_NODES_SPAN_OTHER_NODES
1277 static inline bool __meminit __maybe_unused
1278 meminit_pfn_in_nid(unsigned long pfn, int node,
1279                    struct mminit_pfnnid_cache *state)
1280 {
1281         int nid;
1282
1283         nid = __early_pfn_to_nid(pfn, state);
1284         if (nid >= 0 && nid != node)
1285                 return false;
1286         return true;
1287 }
1288
1289 /* Only safe to use early in boot when initialisation is single-threaded */
1290 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1291 {
1292         return meminit_pfn_in_nid(pfn, node, &early_pfnnid_cache);
1293 }
1294
1295 #else
1296
1297 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1298 {
1299         return true;
1300 }
1301 static inline bool __meminit  __maybe_unused
1302 meminit_pfn_in_nid(unsigned long pfn, int node,
1303                    struct mminit_pfnnid_cache *state)
1304 {
1305         return true;
1306 }
1307 #endif
1308
1309
1310 void __init __free_pages_bootmem(struct page *page, unsigned long pfn,
1311                                                         unsigned int order)
1312 {
1313         if (early_page_uninitialised(pfn))
1314                 return;
1315         return __free_pages_boot_core(page, order);
1316 }
1317
1318 /*
1319  * Check that the whole (or subset of) a pageblock given by the interval of
1320  * [start_pfn, end_pfn) is valid and within the same zone, before scanning it
1321  * with the migration of free compaction scanner. The scanners then need to
1322  * use only pfn_valid_within() check for arches that allow holes within
1323  * pageblocks.
1324  *
1325  * Return struct page pointer of start_pfn, or NULL if checks were not passed.
1326  *
1327  * It's possible on some configurations to have a setup like node0 node1 node0
1328  * i.e. it's possible that all pages within a zones range of pages do not
1329  * belong to a single zone. We assume that a border between node0 and node1
1330  * can occur within a single pageblock, but not a node0 node1 node0
1331  * interleaving within a single pageblock. It is therefore sufficient to check
1332  * the first and last page of a pageblock and avoid checking each individual
1333  * page in a pageblock.
1334  */
1335 struct page *__pageblock_pfn_to_page(unsigned long start_pfn,
1336                                      unsigned long end_pfn, struct zone *zone)
1337 {
1338         struct page *start_page;
1339         struct page *end_page;
1340
1341         /* end_pfn is one past the range we are checking */
1342         end_pfn--;
1343
1344         if (!pfn_valid(start_pfn) || !pfn_valid(end_pfn))
1345                 return NULL;
1346
1347         start_page = pfn_to_online_page(start_pfn);
1348         if (!start_page)
1349                 return NULL;
1350
1351         if (page_zone(start_page) != zone)
1352                 return NULL;
1353
1354         end_page = pfn_to_page(end_pfn);
1355
1356         /* This gives a shorter code than deriving page_zone(end_page) */
1357         if (page_zone_id(start_page) != page_zone_id(end_page))
1358                 return NULL;
1359
1360         return start_page;
1361 }
1362
1363 void set_zone_contiguous(struct zone *zone)
1364 {
1365         unsigned long block_start_pfn = zone->zone_start_pfn;
1366         unsigned long block_end_pfn;
1367
1368         block_end_pfn = ALIGN(block_start_pfn + 1, pageblock_nr_pages);
1369         for (; block_start_pfn < zone_end_pfn(zone);
1370                         block_start_pfn = block_end_pfn,
1371                          block_end_pfn += pageblock_nr_pages) {
1372
1373                 block_end_pfn = min(block_end_pfn, zone_end_pfn(zone));
1374
1375                 if (!__pageblock_pfn_to_page(block_start_pfn,
1376                                              block_end_pfn, zone))
1377                         return;
1378         }
1379
1380         /* We confirm that there is no hole */
1381         zone->contiguous = true;
1382 }
1383
1384 void clear_zone_contiguous(struct zone *zone)
1385 {
1386         zone->contiguous = false;
1387 }
1388
1389 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1390 static void __init deferred_free_range(unsigned long pfn,
1391                                        unsigned long nr_pages)
1392 {
1393         struct page *page;
1394         unsigned long i;
1395
1396         if (!nr_pages)
1397                 return;
1398
1399         page = pfn_to_page(pfn);
1400
1401         /* Free a large naturally-aligned chunk if possible */
1402         if (nr_pages == pageblock_nr_pages &&
1403             (pfn & (pageblock_nr_pages - 1)) == 0) {
1404                 set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1405                 __free_pages_boot_core(page, pageblock_order);
1406                 return;
1407         }
1408
1409         for (i = 0; i < nr_pages; i++, page++, pfn++) {
1410                 if ((pfn & (pageblock_nr_pages - 1)) == 0)
1411                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1412                 __free_pages_boot_core(page, 0);
1413         }
1414 }
1415
1416 /* Completion tracking for deferred_init_memmap() threads */
1417 static atomic_t pgdat_init_n_undone __initdata;
1418 static __initdata DECLARE_COMPLETION(pgdat_init_all_done_comp);
1419
1420 static inline void __init pgdat_init_report_one_done(void)
1421 {
1422         if (atomic_dec_and_test(&pgdat_init_n_undone))
1423                 complete(&pgdat_init_all_done_comp);
1424 }
1425
1426 /*
1427  * Returns true if page needs to be initialized or freed to buddy allocator.
1428  *
1429  * First we check if pfn is valid on architectures where it is possible to have
1430  * holes within pageblock_nr_pages. On systems where it is not possible, this
1431  * function is optimized out.
1432  *
1433  * Then, we check if a current large page is valid by only checking the validity
1434  * of the head pfn.
1435  *
1436  * Finally, meminit_pfn_in_nid is checked on systems where pfns can interleave
1437  * within a node: a pfn is between start and end of a node, but does not belong
1438  * to this memory node.
1439  */
1440 static inline bool __init
1441 deferred_pfn_valid(int nid, unsigned long pfn,
1442                    struct mminit_pfnnid_cache *nid_init_state)
1443 {
1444         if (!pfn_valid_within(pfn))
1445                 return false;
1446         if (!(pfn & (pageblock_nr_pages - 1)) && !pfn_valid(pfn))
1447                 return false;
1448         if (!meminit_pfn_in_nid(pfn, nid, nid_init_state))
1449                 return false;
1450         return true;
1451 }
1452
1453 /*
1454  * Free pages to buddy allocator. Try to free aligned pages in
1455  * pageblock_nr_pages sizes.
1456  */
1457 static void __init deferred_free_pages(int nid, int zid, unsigned long pfn,
1458                                        unsigned long end_pfn)
1459 {
1460         struct mminit_pfnnid_cache nid_init_state = { };
1461         unsigned long nr_pgmask = pageblock_nr_pages - 1;
1462         unsigned long nr_free = 0;
1463
1464         for (; pfn < end_pfn; pfn++) {
1465                 if (!deferred_pfn_valid(nid, pfn, &nid_init_state)) {
1466                         deferred_free_range(pfn - nr_free, nr_free);
1467                         nr_free = 0;
1468                 } else if (!(pfn & nr_pgmask)) {
1469                         deferred_free_range(pfn - nr_free, nr_free);
1470                         nr_free = 1;
1471                         touch_nmi_watchdog();
1472                 } else {
1473                         nr_free++;
1474                 }
1475         }
1476         /* Free the last block of pages to allocator */
1477         deferred_free_range(pfn - nr_free, nr_free);
1478 }
1479
1480 /*
1481  * Initialize struct pages.  We minimize pfn page lookups and scheduler checks
1482  * by performing it only once every pageblock_nr_pages.
1483  * Return number of pages initialized.
1484  */
1485 static unsigned long  __init deferred_init_pages(int nid, int zid,
1486                                                  unsigned long pfn,
1487                                                  unsigned long end_pfn)
1488 {
1489         struct mminit_pfnnid_cache nid_init_state = { };
1490         unsigned long nr_pgmask = pageblock_nr_pages - 1;
1491         unsigned long nr_pages = 0;
1492         struct page *page = NULL;
1493
1494         for (; pfn < end_pfn; pfn++) {
1495                 if (!deferred_pfn_valid(nid, pfn, &nid_init_state)) {
1496                         page = NULL;
1497                         continue;
1498                 } else if (!page || !(pfn & nr_pgmask)) {
1499                         page = pfn_to_page(pfn);
1500                         touch_nmi_watchdog();
1501                 } else {
1502                         page++;
1503                 }
1504                 __init_single_page(page, pfn, zid, nid, true);
1505                 nr_pages++;
1506         }
1507         return (nr_pages);
1508 }
1509
1510 /* Initialise remaining memory on a node */
1511 static int __init deferred_init_memmap(void *data)
1512 {
1513         pg_data_t *pgdat = data;
1514         int nid = pgdat->node_id;
1515         unsigned long start = jiffies;
1516         unsigned long nr_pages = 0;
1517         unsigned long spfn, epfn, first_init_pfn, flags;
1518         phys_addr_t spa, epa;
1519         int zid;
1520         struct zone *zone;
1521         const struct cpumask *cpumask = cpumask_of_node(pgdat->node_id);
1522         u64 i;
1523
1524         /* Bind memory initialisation thread to a local node if possible */
1525         if (!cpumask_empty(cpumask))
1526                 set_cpus_allowed_ptr(current, cpumask);
1527
1528         pgdat_resize_lock(pgdat, &flags);
1529         first_init_pfn = pgdat->first_deferred_pfn;
1530         if (first_init_pfn == ULONG_MAX) {
1531                 pgdat_resize_unlock(pgdat, &flags);
1532                 pgdat_init_report_one_done();
1533                 return 0;
1534         }
1535
1536         /* Sanity check boundaries */
1537         BUG_ON(pgdat->first_deferred_pfn < pgdat->node_start_pfn);
1538         BUG_ON(pgdat->first_deferred_pfn > pgdat_end_pfn(pgdat));
1539         pgdat->first_deferred_pfn = ULONG_MAX;
1540
1541         /* Only the highest zone is deferred so find it */
1542         for (zid = 0; zid < MAX_NR_ZONES; zid++) {
1543                 zone = pgdat->node_zones + zid;
1544                 if (first_init_pfn < zone_end_pfn(zone))
1545                         break;
1546         }
1547         first_init_pfn = max(zone->zone_start_pfn, first_init_pfn);
1548
1549         /*
1550          * Initialize and free pages. We do it in two loops: first we initialize
1551          * struct page, than free to buddy allocator, because while we are
1552          * freeing pages we can access pages that are ahead (computing buddy
1553          * page in __free_one_page()).
1554          */
1555         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1556                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1557                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1558                 nr_pages += deferred_init_pages(nid, zid, spfn, epfn);
1559         }
1560         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1561                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1562                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1563                 deferred_free_pages(nid, zid, spfn, epfn);
1564         }
1565         pgdat_resize_unlock(pgdat, &flags);
1566
1567         /* Sanity check that the next zone really is unpopulated */
1568         WARN_ON(++zid < MAX_NR_ZONES && populated_zone(++zone));
1569
1570         pr_info("node %d initialised, %lu pages in %ums\n", nid, nr_pages,
1571                                         jiffies_to_msecs(jiffies - start));
1572
1573         pgdat_init_report_one_done();
1574         return 0;
1575 }
1576
1577 /*
1578  * During boot we initialize deferred pages on-demand, as needed, but once
1579  * page_alloc_init_late() has finished, the deferred pages are all initialized,
1580  * and we can permanently disable that path.
1581  */
1582 static DEFINE_STATIC_KEY_TRUE(deferred_pages);
1583
1584 /*
1585  * If this zone has deferred pages, try to grow it by initializing enough
1586  * deferred pages to satisfy the allocation specified by order, rounded up to
1587  * the nearest PAGES_PER_SECTION boundary.  So we're adding memory in increments
1588  * of SECTION_SIZE bytes by initializing struct pages in increments of
1589  * PAGES_PER_SECTION * sizeof(struct page) bytes.
1590  *
1591  * Return true when zone was grown, otherwise return false. We return true even
1592  * when we grow less than requested, to let the caller decide if there are
1593  * enough pages to satisfy the allocation.
1594  *
1595  * Note: We use noinline because this function is needed only during boot, and
1596  * it is called from a __ref function _deferred_grow_zone. This way we are
1597  * making sure that it is not inlined into permanent text section.
1598  */
1599 static noinline bool __init
1600 deferred_grow_zone(struct zone *zone, unsigned int order)
1601 {
1602         int zid = zone_idx(zone);
1603         int nid = zone_to_nid(zone);
1604         pg_data_t *pgdat = NODE_DATA(nid);
1605         unsigned long nr_pages_needed = ALIGN(1 << order, PAGES_PER_SECTION);
1606         unsigned long nr_pages = 0;
1607         unsigned long first_init_pfn, spfn, epfn, t, flags;
1608         unsigned long first_deferred_pfn = pgdat->first_deferred_pfn;
1609         phys_addr_t spa, epa;
1610         u64 i;
1611
1612         /* Only the last zone may have deferred pages */
1613         if (zone_end_pfn(zone) != pgdat_end_pfn(pgdat))
1614                 return false;
1615
1616         pgdat_resize_lock(pgdat, &flags);
1617
1618         /*
1619          * If deferred pages have been initialized while we were waiting for
1620          * the lock, return true, as the zone was grown.  The caller will retry
1621          * this zone.  We won't return to this function since the caller also
1622          * has this static branch.
1623          */
1624         if (!static_branch_unlikely(&deferred_pages)) {
1625                 pgdat_resize_unlock(pgdat, &flags);
1626                 return true;
1627         }
1628
1629         /*
1630          * If someone grew this zone while we were waiting for spinlock, return
1631          * true, as there might be enough pages already.
1632          */
1633         if (first_deferred_pfn != pgdat->first_deferred_pfn) {
1634                 pgdat_resize_unlock(pgdat, &flags);
1635                 return true;
1636         }
1637
1638         first_init_pfn = max(zone->zone_start_pfn, first_deferred_pfn);
1639
1640         if (first_init_pfn >= pgdat_end_pfn(pgdat)) {
1641                 pgdat_resize_unlock(pgdat, &flags);
1642                 return false;
1643         }
1644
1645         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1646                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1647                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1648
1649                 while (spfn < epfn && nr_pages < nr_pages_needed) {
1650                         t = ALIGN(spfn + PAGES_PER_SECTION, PAGES_PER_SECTION);
1651                         first_deferred_pfn = min(t, epfn);
1652                         nr_pages += deferred_init_pages(nid, zid, spfn,
1653                                                         first_deferred_pfn);
1654                         spfn = first_deferred_pfn;
1655                 }
1656
1657                 if (nr_pages >= nr_pages_needed)
1658                         break;
1659         }
1660
1661         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1662                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1663                 epfn = min_t(unsigned long, first_deferred_pfn, PFN_DOWN(epa));
1664                 deferred_free_pages(nid, zid, spfn, epfn);
1665
1666                 if (first_deferred_pfn == epfn)
1667                         break;
1668         }
1669         pgdat->first_deferred_pfn = first_deferred_pfn;
1670         pgdat_resize_unlock(pgdat, &flags);
1671
1672         return nr_pages > 0;
1673 }
1674
1675 /*
1676  * deferred_grow_zone() is __init, but it is called from
1677  * get_page_from_freelist() during early boot until deferred_pages permanently
1678  * disables this call. This is why we have refdata wrapper to avoid warning,
1679  * and to ensure that the function body gets unloaded.
1680  */
1681 static bool __ref
1682 _deferred_grow_zone(struct zone *zone, unsigned int order)
1683 {
1684         return deferred_grow_zone(zone, order);
1685 }
1686
1687 #endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
1688
1689 void __init page_alloc_init_late(void)
1690 {
1691         struct zone *zone;
1692
1693 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1694         int nid;
1695
1696         /* There will be num_node_state(N_MEMORY) threads */
1697         atomic_set(&pgdat_init_n_undone, num_node_state(N_MEMORY));
1698         for_each_node_state(nid, N_MEMORY) {
1699                 kthread_run(deferred_init_memmap, NODE_DATA(nid), "pgdatinit%d", nid);
1700         }
1701
1702         /* Block until all are initialised */
1703         wait_for_completion(&pgdat_init_all_done_comp);
1704
1705         /*
1706          * We initialized the rest of the deferred pages.  Permanently disable
1707          * on-demand struct page initialization.
1708          */
1709         static_branch_disable(&deferred_pages);
1710
1711         /* Reinit limits that are based on free pages after the kernel is up */
1712         files_maxfiles_init();
1713 #endif
1714 #ifdef CONFIG_ARCH_DISCARD_MEMBLOCK
1715         /* Discard memblock private memory */
1716         memblock_discard();
1717 #endif
1718
1719         for_each_populated_zone(zone)
1720                 set_zone_contiguous(zone);
1721 }
1722
1723 #ifdef CONFIG_CMA
1724 /* Free whole pageblock and set its migration type to MIGRATE_CMA. */
1725 void __init init_cma_reserved_pageblock(struct page *page)
1726 {
1727         unsigned i = pageblock_nr_pages;
1728         struct page *p = page;
1729
1730         do {
1731                 __ClearPageReserved(p);
1732                 set_page_count(p, 0);
1733         } while (++p, --i);
1734
1735         set_pageblock_migratetype(page, MIGRATE_CMA);
1736
1737         if (pageblock_order >= MAX_ORDER) {
1738                 i = pageblock_nr_pages;
1739                 p = page;
1740                 do {
1741                         set_page_refcounted(p);
1742                         __free_pages(p, MAX_ORDER - 1);
1743                         p += MAX_ORDER_NR_PAGES;
1744                 } while (i -= MAX_ORDER_NR_PAGES);
1745         } else {
1746                 set_page_refcounted(page);
1747                 __free_pages(page, pageblock_order);
1748         }
1749
1750         adjust_managed_page_count(page, pageblock_nr_pages);
1751 }
1752 #endif
1753
1754 /*
1755  * The order of subdivision here is critical for the IO subsystem.
1756  * Please do not alter this order without good reasons and regression
1757  * testing. Specifically, as large blocks of memory are subdivided,
1758  * the order in which smaller blocks are delivered depends on the order
1759  * they're subdivided in this function. This is the primary factor
1760  * influencing the order in which pages are delivered to the IO
1761  * subsystem according to empirical testing, and this is also justified
1762  * by considering the behavior of a buddy system containing a single
1763  * large block of memory acted on by a series of small allocations.
1764  * This behavior is a critical factor in sglist merging's success.
1765  *
1766  * -- nyc
1767  */
1768 static inline void expand(struct zone *zone, struct page *page,
1769         int low, int high, struct free_area *area,
1770         int migratetype)
1771 {
1772         unsigned long size = 1 << high;
1773
1774         while (high > low) {
1775                 area--;
1776                 high--;
1777                 size >>= 1;
1778                 VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);
1779
1780                 /*
1781                  * Mark as guard pages (or page), that will allow to
1782                  * merge back to allocator when buddy will be freed.
1783                  * Corresponding page table entries will not be touched,
1784                  * pages will stay not present in virtual address space
1785                  */
1786                 if (set_page_guard(zone, &page[size], high, migratetype))
1787                         continue;
1788
1789                 list_add(&page[size].lru, &area->free_list[migratetype]);
1790                 area->nr_free++;
1791                 set_page_order(&page[size], high);
1792         }
1793 }
1794
1795 static void check_new_page_bad(struct page *page)
1796 {
1797         const char *bad_reason = NULL;
1798         unsigned long bad_flags = 0;
1799
1800         if (unlikely(atomic_read(&page->_mapcount) != -1))
1801                 bad_reason = "nonzero mapcount";
1802         if (unlikely(page->mapping != NULL))
1803                 bad_reason = "non-NULL mapping";
1804         if (unlikely(page_ref_count(page) != 0))
1805                 bad_reason = "nonzero _count";
1806         if (unlikely(page->flags & __PG_HWPOISON)) {
1807                 bad_reason = "HWPoisoned (hardware-corrupted)";
1808                 bad_flags = __PG_HWPOISON;
1809                 /* Don't complain about hwpoisoned pages */
1810                 page_mapcount_reset(page); /* remove PageBuddy */
1811                 return;
1812         }
1813         if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_PREP)) {
1814                 bad_reason = "PAGE_FLAGS_CHECK_AT_PREP flag set";
1815                 bad_flags = PAGE_FLAGS_CHECK_AT_PREP;
1816         }
1817 #ifdef CONFIG_MEMCG
1818         if (unlikely(page->mem_cgroup))
1819                 bad_reason = "page still charged to cgroup";
1820 #endif
1821         bad_page(page, bad_reason, bad_flags);
1822 }
1823
1824 /*
1825  * This page is about to be returned from the page allocator
1826  */
1827 static inline int check_new_page(struct page *page)
1828 {
1829         if (likely(page_expected_state(page,
1830                                 PAGE_FLAGS_CHECK_AT_PREP|__PG_HWPOISON)))
1831                 return 0;
1832
1833         check_new_page_bad(page);
1834         return 1;
1835 }
1836
1837 static inline bool free_pages_prezeroed(void)
1838 {
1839         return IS_ENABLED(CONFIG_PAGE_POISONING_ZERO) &&
1840                 page_poisoning_enabled();
1841 }
1842
1843 #ifdef CONFIG_DEBUG_VM
1844 static bool check_pcp_refill(struct page *page)
1845 {
1846         return false;
1847 }
1848
1849 static bool check_new_pcp(struct page *page)
1850 {
1851         return check_new_page(page);
1852 }
1853 #else
1854 static bool check_pcp_refill(struct page *page)
1855 {
1856         return check_new_page(page);
1857 }
1858 static bool check_new_pcp(struct page *page)
1859 {
1860         return false;
1861 }
1862 #endif /* CONFIG_DEBUG_VM */
1863
1864 static bool check_new_pages(struct page *page, unsigned int order)
1865 {
1866         int i;
1867         for (i = 0; i < (1 << order); i++) {
1868                 struct page *p = page + i;
1869
1870                 if (unlikely(check_new_page(p)))
1871                         return true;
1872         }
1873
1874         return false;
1875 }
1876
1877 inline void post_alloc_hook(struct page *page, unsigned int order,
1878                                 gfp_t gfp_flags)
1879 {
1880         set_page_private(page, 0);
1881         set_page_refcounted(page);
1882
1883         arch_alloc_page(page, order);
1884         kernel_map_pages(page, 1 << order, 1);
1885         kernel_poison_pages(page, 1 << order, 1);
1886         kasan_alloc_pages(page, order);
1887         set_page_owner(page, order, gfp_flags);
1888 }
1889
1890 static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags,
1891                                                         unsigned int alloc_flags)
1892 {
1893         int i;
1894
1895         post_alloc_hook(page, order, gfp_flags);
1896
1897         if (!free_pages_prezeroed() && (gfp_flags & __GFP_ZERO))
1898                 for (i = 0; i < (1 << order); i++)
1899                         clear_highpage(page + i);
1900
1901         if (order && (gfp_flags & __GFP_COMP))
1902                 prep_compound_page(page, order);
1903
1904         /*
1905          * page is set pfmemalloc when ALLOC_NO_WATERMARKS was necessary to
1906          * allocate the page. The expectation is that the caller is taking
1907          * steps that will free more memory. The caller should avoid the page
1908          * being used for !PFMEMALLOC purposes.
1909          */
1910         if (alloc_flags & ALLOC_NO_WATERMARKS)
1911                 set_page_pfmemalloc(page);
1912         else
1913                 clear_page_pfmemalloc(page);
1914 }
1915
1916 /*
1917  * Go through the free lists for the given migratetype and remove
1918  * the smallest available page from the freelists
1919  */
1920 static __always_inline
1921 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
1922                                                 int migratetype)
1923 {
1924         unsigned int current_order;
1925         struct free_area *area;
1926         struct page *page;
1927
1928         /* Find a page of the appropriate size in the preferred list */
1929         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
1930                 area = &(zone->free_area[current_order]);
1931                 page = list_first_entry_or_null(&area->free_list[migratetype],
1932                                                         struct page, lru);
1933                 if (!page)
1934                         continue;
1935                 list_del(&page->lru);
1936                 rmv_page_order(page);
1937                 area->nr_free--;
1938                 expand(zone, page, order, current_order, area, migratetype);
1939                 set_pcppage_migratetype(page, migratetype);
1940                 return page;
1941         }
1942
1943         return NULL;
1944 }
1945
1946
1947 /*
1948  * This array describes the order lists are fallen back to when
1949  * the free lists for the desirable migrate type are depleted
1950  */
1951 static int fallbacks[MIGRATE_TYPES][4] = {
1952         [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
1953         [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
1954         [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
1955 #ifdef CONFIG_CMA
1956         [MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
1957 #endif
1958 #ifdef CONFIG_MEMORY_ISOLATION
1959         [MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
1960 #endif
1961 };
1962
1963 #ifdef CONFIG_CMA
1964 static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1965                                         unsigned int order)
1966 {
1967         return __rmqueue_smallest(zone, order, MIGRATE_CMA);
1968 }
1969 #else
1970 static inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1971                                         unsigned int order) { return NULL; }
1972 #endif
1973
1974 /*
1975  * Move the free pages in a range to the free lists of the requested type.
1976  * Note that start_page and end_pages are not aligned on a pageblock
1977  * boundary. If alignment is required, use move_freepages_block()
1978  */
1979 static int move_freepages(struct zone *zone,
1980                           struct page *start_page, struct page *end_page,
1981                           int migratetype, int *num_movable)
1982 {
1983         struct page *page;
1984         unsigned int order;
1985         int pages_moved = 0;
1986
1987 #ifndef CONFIG_HOLES_IN_ZONE
1988         /*
1989          * page_zone is not safe to call in this context when
1990          * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
1991          * anyway as we check zone boundaries in move_freepages_block().
1992          * Remove at a later date when no bug reports exist related to
1993          * grouping pages by mobility
1994          */
1995         VM_BUG_ON(pfn_valid(page_to_pfn(start_page)) &&
1996                   pfn_valid(page_to_pfn(end_page)) &&
1997                   page_zone(start_page) != page_zone(end_page));
1998 #endif
1999
2000         if (num_movable)
2001                 *num_movable = 0;
2002
2003         for (page = start_page; page <= end_page;) {
2004                 if (!pfn_valid_within(page_to_pfn(page))) {
2005                         page++;
2006                         continue;
2007                 }
2008
2009                 /* Make sure we are not inadvertently changing nodes */
2010                 VM_BUG_ON_PAGE(page_to_nid(page) != zone_to_nid(zone), page);
2011
2012                 if (!PageBuddy(page)) {
2013                         /*
2014                          * We assume that pages that could be isolated for
2015                          * migration are movable. But we don't actually try
2016                          * isolating, as that would be expensive.
2017                          */
2018                         if (num_movable &&
2019                                         (PageLRU(page) || __PageMovable(page)))
2020                                 (*num_movable)++;
2021
2022                         page++;
2023                         continue;
2024                 }
2025
2026                 order = page_order(page);
2027                 list_move(&page->lru,
2028                           &zone->free_area[order].free_list[migratetype]);
2029                 page += 1 << order;
2030                 pages_moved += 1 << order;
2031         }
2032
2033         return pages_moved;
2034 }
2035
2036 int move_freepages_block(struct zone *zone, struct page *page,
2037                                 int migratetype, int *num_movable)
2038 {
2039         unsigned long start_pfn, end_pfn;
2040         struct page *start_page, *end_page;
2041
2042         start_pfn = page_to_pfn(page);
2043         start_pfn = start_pfn & ~(pageblock_nr_pages-1);
2044         start_page = pfn_to_page(start_pfn);
2045         end_page = start_page + pageblock_nr_pages - 1;
2046         end_pfn = start_pfn + pageblock_nr_pages - 1;
2047
2048         /* Do not cross zone boundaries */
2049         if (!zone_spans_pfn(zone, start_pfn))
2050                 start_page = page;
2051         if (!zone_spans_pfn(zone, end_pfn))
2052                 return 0;
2053
2054         return move_freepages(zone, start_page, end_page, migratetype,
2055                                                                 num_movable);
2056 }
2057
2058 static void change_pageblock_range(struct page *pageblock_page,
2059                                         int start_order, int migratetype)
2060 {
2061         int nr_pageblocks = 1 << (start_order - pageblock_order);
2062
2063         while (nr_pageblocks--) {
2064                 set_pageblock_migratetype(pageblock_page, migratetype);
2065                 pageblock_page += pageblock_nr_pages;
2066         }
2067 }
2068
2069 /*
2070  * When we are falling back to another migratetype during allocation, try to
2071  * steal extra free pages from the same pageblocks to satisfy further
2072  * allocations, instead of polluting multiple pageblocks.
2073  *
2074  * If we are stealing a relatively large buddy page, it is likely there will
2075  * be more free pages in the pageblock, so try to steal them all. For
2076  * reclaimable and unmovable allocations, we steal regardless of page size,
2077  * as fragmentation caused by those allocations polluting movable pageblocks
2078  * is worse than movable allocations stealing from unmovable and reclaimable
2079  * pageblocks.
2080  */
2081 static bool can_steal_fallback(unsigned int order, int start_mt)
2082 {
2083         /*
2084          * Leaving this order check is intended, although there is
2085          * relaxed order check in next check. The reason is that
2086          * we can actually steal whole pageblock if this condition met,
2087          * but, below check doesn't guarantee it and that is just heuristic
2088          * so could be changed anytime.
2089          */
2090         if (order >= pageblock_order)
2091                 return true;
2092
2093         if (order >= pageblock_order / 2 ||
2094                 start_mt == MIGRATE_RECLAIMABLE ||
2095                 start_mt == MIGRATE_UNMOVABLE ||
2096                 page_group_by_mobility_disabled)
2097                 return true;
2098
2099         return false;
2100 }
2101
2102 /*
2103  * This function implements actual steal behaviour. If order is large enough,
2104  * we can steal whole pageblock. If not, we first move freepages in this
2105  * pageblock to our migratetype and determine how many already-allocated pages
2106  * are there in the pageblock with a compatible migratetype. If at least half
2107  * of pages are free or compatible, we can change migratetype of the pageblock
2108  * itself, so pages freed in the future will be put on the correct free list.
2109  */
2110 static void steal_suitable_fallback(struct zone *zone, struct page *page,
2111                                         int start_type, bool whole_block)
2112 {
2113         unsigned int current_order = page_order(page);
2114         struct free_area *area;
2115         int free_pages, movable_pages, alike_pages;
2116         int old_block_type;
2117
2118         old_block_type = get_pageblock_migratetype(page);
2119
2120         /*
2121          * This can happen due to races and we want to prevent broken
2122          * highatomic accounting.
2123          */
2124         if (is_migrate_highatomic(old_block_type))
2125                 goto single_page;
2126
2127         /* Take ownership for orders >= pageblock_order */
2128         if (current_order >= pageblock_order) {
2129                 change_pageblock_range(page, current_order, start_type);
2130                 goto single_page;
2131         }
2132
2133         /* We are not allowed to try stealing from the whole block */
2134         if (!whole_block)
2135                 goto single_page;
2136
2137         free_pages = move_freepages_block(zone, page, start_type,
2138                                                 &movable_pages);
2139         /*
2140          * Determine how many pages are compatible with our allocation.
2141          * For movable allocation, it's the number of movable pages which
2142          * we just obtained. For other types it's a bit more tricky.
2143          */
2144         if (start_type == MIGRATE_MOVABLE) {
2145                 alike_pages = movable_pages;
2146         } else {
2147                 /*
2148                  * If we are falling back a RECLAIMABLE or UNMOVABLE allocation
2149                  * to MOVABLE pageblock, consider all non-movable pages as
2150                  * compatible. If it's UNMOVABLE falling back to RECLAIMABLE or
2151                  * vice versa, be conservative since we can't distinguish the
2152                  * exact migratetype of non-movable pages.
2153                  */
2154                 if (old_block_type == MIGRATE_MOVABLE)
2155                         alike_pages = pageblock_nr_pages
2156                                                 - (free_pages + movable_pages);
2157                 else
2158                         alike_pages = 0;
2159         }
2160
2161         /* moving whole block can fail due to zone boundary conditions */
2162         if (!free_pages)
2163                 goto single_page;
2164
2165         /*
2166          * If a sufficient number of pages in the block are either free or of
2167          * comparable migratability as our allocation, claim the whole block.
2168          */
2169         if (free_pages + alike_pages >= (1 << (pageblock_order-1)) ||
2170                         page_group_by_mobility_disabled)
2171                 set_pageblock_migratetype(page, start_type);
2172
2173         return;
2174
2175 single_page:
2176         area = &zone->free_area[current_order];
2177         list_move(&page->lru, &area->free_list[start_type]);
2178 }
2179
2180 /*
2181  * Check whether there is a suitable fallback freepage with requested order.
2182  * If only_stealable is true, this function returns fallback_mt only if
2183  * we can steal other freepages all together. This would help to reduce
2184  * fragmentation due to mixed migratetype pages in one pageblock.
2185  */
2186 int find_suitable_fallback(struct free_area *area, unsigned int order,
2187                         int migratetype, bool only_stealable, bool *can_steal)
2188 {
2189         int i;
2190         int fallback_mt;
2191
2192         if (area->nr_free == 0)
2193                 return -1;
2194
2195         *can_steal = false;
2196         for (i = 0;; i++) {
2197                 fallback_mt = fallbacks[migratetype][i];
2198                 if (fallback_mt == MIGRATE_TYPES)
2199                         break;
2200
2201                 if (list_empty(&area->free_list[fallback_mt]))
2202                         continue;
2203
2204                 if (can_steal_fallback(order, migratetype))
2205                         *can_steal = true;
2206
2207                 if (!only_stealable)
2208                         return fallback_mt;
2209
2210                 if (*can_steal)
2211                         return fallback_mt;
2212         }
2213
2214         return -1;
2215 }
2216
2217 /*
2218  * Reserve a pageblock for exclusive use of high-order atomic allocations if
2219  * there are no empty page blocks that contain a page with a suitable order
2220  */
2221 static void reserve_highatomic_pageblock(struct page *page, struct zone *zone,
2222                                 unsigned int alloc_order)
2223 {
2224         int mt;
2225         unsigned long max_managed, flags;
2226
2227         /*
2228          * Limit the number reserved to 1 pageblock or roughly 1% of a zone.
2229          * Check is race-prone but harmless.
2230          */
2231         max_managed = (zone->managed_pages / 100) + pageblock_nr_pages;
2232         if (zone->nr_reserved_highatomic >= max_managed)
2233                 return;
2234
2235         spin_lock_irqsave(&zone->lock, flags);
2236
2237         /* Recheck the nr_reserved_highatomic limit under the lock */
2238         if (zone->nr_reserved_highatomic >= max_managed)
2239                 goto out_unlock;
2240
2241         /* Yoink! */
2242         mt = get_pageblock_migratetype(page);
2243         if (!is_migrate_highatomic(mt) && !is_migrate_isolate(mt)
2244             && !is_migrate_cma(mt)) {
2245                 zone->nr_reserved_highatomic += pageblock_nr_pages;
2246                 set_pageblock_migratetype(page, MIGRATE_HIGHATOMIC);
2247                 move_freepages_block(zone, page, MIGRATE_HIGHATOMIC, NULL);
2248         }
2249
2250 out_unlock:
2251         spin_unlock_irqrestore(&zone->lock, flags);
2252 }
2253
2254 /*
2255  * Used when an allocation is about to fail under memory pressure. This
2256  * potentially hurts the reliability of high-order allocations when under
2257  * intense memory pressure but failed atomic allocations should be easier
2258  * to recover from than an OOM.
2259  *
2260  * If @force is true, try to unreserve a pageblock even though highatomic
2261  * pageblock is exhausted.
2262  */
2263 static bool unreserve_highatomic_pageblock(const struct alloc_context *ac,
2264                                                 bool force)
2265 {
2266         struct zonelist *zonelist = ac->zonelist;
2267         unsigned long flags;
2268         struct zoneref *z;
2269         struct zone *zone;
2270         struct page *page;
2271         int order;
2272         bool ret;
2273
2274         for_each_zone_zonelist_nodemask(zone, z, zonelist, ac->high_zoneidx,
2275                                                                 ac->nodemask) {
2276                 /*
2277                  * Preserve at least one pageblock unless memory pressure
2278                  * is really high.
2279                  */
2280                 if (!force && zone->nr_reserved_highatomic <=
2281                                         pageblock_nr_pages)
2282                         continue;
2283
2284                 spin_lock_irqsave(&zone->lock, flags);
2285                 for (order = 0; order < MAX_ORDER; order++) {
2286                         struct free_area *area = &(zone->free_area[order]);
2287
2288                         page = list_first_entry_or_null(
2289                                         &area->free_list[MIGRATE_HIGHATOMIC],
2290                                         struct page, lru);
2291                         if (!page)
2292                                 continue;
2293
2294                         /*
2295                          * In page freeing path, migratetype change is racy so
2296                          * we can counter several free pages in a pageblock
2297                          * in this loop althoug we changed the pageblock type
2298                          * from highatomic to ac->migratetype. So we should
2299                          * adjust the count once.
2300                          */
2301                         if (is_migrate_highatomic_page(page)) {
2302                                 /*
2303                                  * It should never happen but changes to
2304                                  * locking could inadvertently allow a per-cpu
2305                                  * drain to add pages to MIGRATE_HIGHATOMIC
2306                                  * while unreserving so be safe and watch for
2307                                  * underflows.
2308                                  */
2309                                 zone->nr_reserved_highatomic -= min(
2310                                                 pageblock_nr_pages,
2311                                                 zone->nr_reserved_highatomic);
2312                         }
2313
2314                         /*
2315                          * Convert to ac->migratetype and avoid the normal
2316                          * pageblock stealing heuristics. Minimally, the caller
2317                          * is doing the work and needs the pages. More
2318                          * importantly, if the block was always converted to
2319                          * MIGRATE_UNMOVABLE or another type then the number
2320                          * of pageblocks that cannot be completely freed
2321                          * may increase.
2322                          */
2323                         set_pageblock_migratetype(page, ac->migratetype);
2324                         ret = move_freepages_block(zone, page, ac->migratetype,
2325                                                                         NULL);
2326                         if (ret) {
2327                                 spin_unlock_irqrestore(&zone->lock, flags);
2328                                 return ret;
2329                         }
2330                 }
2331                 spin_unlock_irqrestore(&zone->lock, flags);
2332         }
2333
2334         return false;
2335 }
2336
2337 /*
2338  * Try finding a free buddy page on the fallback list and put it on the free
2339  * list of requested migratetype, possibly along with other pages from the same
2340  * block, depending on fragmentation avoidance heuristics. Returns true if
2341  * fallback was found so that __rmqueue_smallest() can grab it.
2342  *
2343  * The use of signed ints for order and current_order is a deliberate
2344  * deviation from the rest of this file, to make the for loop
2345  * condition simpler.
2346  */
2347 static __always_inline bool
2348 __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
2349 {
2350         struct free_area *area;
2351         int current_order;
2352         struct page *page;
2353         int fallback_mt;
2354         bool can_steal;
2355
2356         /*
2357          * Find the largest available free page in the other list. This roughly
2358          * approximates finding the pageblock with the most free pages, which
2359          * would be too costly to do exactly.
2360          */
2361         for (current_order = MAX_ORDER - 1; current_order >= order;
2362                                 --current_order) {
2363                 area = &(zone->free_area[current_order]);
2364                 fallback_mt = find_suitable_fallback(area, current_order,
2365                                 start_migratetype, false, &can_steal);
2366                 if (fallback_mt == -1)
2367                         continue;
2368
2369                 /*
2370                  * We cannot steal all free pages from the pageblock and the
2371                  * requested migratetype is movable. In that case it's better to
2372                  * steal and split the smallest available page instead of the
2373                  * largest available page, because even if the next movable
2374                  * allocation falls back into a different pageblock than this
2375                  * one, it won't cause permanent fragmentation.
2376                  */
2377                 if (!can_steal && start_migratetype == MIGRATE_MOVABLE
2378                                         && current_order > order)
2379                         goto find_smallest;
2380
2381                 goto do_steal;
2382         }
2383
2384         return false;
2385
2386 find_smallest:
2387         for (current_order = order; current_order < MAX_ORDER;
2388                                                         current_order++) {
2389                 area = &(zone->free_area[current_order]);
2390                 fallback_mt = find_suitable_fallback(area, current_order,
2391                                 start_migratetype, false, &can_steal);
2392                 if (fallback_mt != -1)
2393                         break;
2394         }
2395
2396         /*
2397          * This should not happen - we already found a suitable fallback
2398          * when looking for the largest page.
2399          */
2400         VM_BUG_ON(current_order == MAX_ORDER);
2401
2402 do_steal:
2403         page = list_first_entry(&area->free_list[fallback_mt],
2404                                                         struct page, lru);
2405
2406         steal_suitable_fallback(zone, page, start_migratetype, can_steal);
2407
2408         trace_mm_page_alloc_extfrag(page, order, current_order,
2409                 start_migratetype, fallback_mt);
2410
2411         return true;
2412
2413 }
2414
2415 /*
2416  * Do the hard work of removing an element from the buddy allocator.
2417  * Call me with the zone->lock already held.
2418  */
2419 static __always_inline struct page *
2420 __rmqueue(struct zone *zone, unsigned int order, int migratetype)
2421 {
2422         struct page *page;
2423
2424 retry:
2425         page = __rmqueue_smallest(zone, order, migratetype);
2426         if (unlikely(!page)) {
2427                 if (migratetype == MIGRATE_MOVABLE)
2428                         page = __rmqueue_cma_fallback(zone, order);
2429
2430                 if (!page && __rmqueue_fallback(zone, order, migratetype))
2431                         goto retry;
2432         }
2433
2434         trace_mm_page_alloc_zone_locked(page, order, migratetype);
2435         return page;
2436 }
2437
2438 /*
2439  * Obtain a specified number of elements from the buddy allocator, all under
2440  * a single hold of the lock, for efficiency.  Add them to the supplied list.
2441  * Returns the number of new pages which were placed at *list.
2442  */
2443 static int rmqueue_bulk(struct zone *zone, unsigned int order,
2444                         unsigned long count, struct list_head *list,
2445                         int migratetype)
2446 {
2447         int i, alloced = 0;
2448
2449         spin_lock(&zone->lock);
2450         for (i = 0; i < count; ++i) {
2451                 struct page *page = __rmqueue(zone, order, migratetype);
2452                 if (unlikely(page == NULL))
2453                         break;
2454
2455                 if (unlikely(check_pcp_refill(page)))
2456                         continue;
2457
2458                 /*
2459                  * Split buddy pages returned by expand() are received here in
2460                  * physical page order. The page is added to the tail of
2461                  * caller's list. From the callers perspective, the linked list
2462                  * is ordered by page number under some conditions. This is
2463                  * useful for IO devices that can forward direction from the
2464                  * head, thus also in the physical page order. This is useful
2465                  * for IO devices that can merge IO requests if the physical
2466                  * pages are ordered properly.
2467                  */
2468                 list_add_tail(&page->lru, list);
2469                 alloced++;
2470                 if (is_migrate_cma(get_pcppage_migratetype(page)))
2471                         __mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
2472                                               -(1 << order));
2473         }
2474
2475         /*
2476          * i pages were removed from the buddy list even if some leak due
2477          * to check_pcp_refill failing so adjust NR_FREE_PAGES based
2478          * on i. Do not confuse with 'alloced' which is the number of
2479          * pages added to the pcp list.
2480          */
2481         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
2482         spin_unlock(&zone->lock);
2483         return alloced;
2484 }
2485
2486 #ifdef CONFIG_NUMA
2487 /*
2488  * Called from the vmstat counter updater to drain pagesets of this
2489  * currently executing processor on remote nodes after they have
2490  * expired.
2491  *
2492  * Note that this function must be called with the thread pinned to
2493  * a single processor.
2494  */
2495 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
2496 {
2497         unsigned long flags;
2498         int to_drain, batch;
2499
2500         local_irq_save(flags);
2501         batch = READ_ONCE(pcp->batch);
2502         to_drain = min(pcp->count, batch);
2503         if (to_drain > 0) {
2504                 free_pcppages_bulk(zone, to_drain, pcp);
2505                 pcp->count -= to_drain;
2506         }
2507         local_irq_restore(flags);
2508 }
2509 #endif
2510
2511 /*
2512  * Drain pcplists of the indicated processor and zone.
2513  *
2514  * The processor must either be the current processor and the
2515  * thread pinned to the current processor or a processor that
2516  * is not online.
2517  */
2518 static void drain_pages_zone(unsigned int cpu, struct zone *zone)
2519 {
2520         unsigned long flags;
2521         struct per_cpu_pageset *pset;
2522         struct per_cpu_pages *pcp;
2523
2524         local_irq_save(flags);
2525         pset = per_cpu_ptr(zone->pageset, cpu);
2526
2527         pcp = &pset->pcp;
2528         if (pcp->count) {
2529                 free_pcppages_bulk(zone, pcp->count, pcp);
2530                 pcp->count = 0;
2531         }
2532         local_irq_restore(flags);
2533 }
2534
2535 /*
2536  * Drain pcplists of all zones on the indicated processor.
2537  *
2538  * The processor must either be the current processor and the
2539  * thread pinned to the current processor or a processor that
2540  * is not online.
2541  */
2542 static void drain_pages(unsigned int cpu)
2543 {
2544         struct zone *zone;
2545
2546         for_each_populated_zone(zone) {
2547                 drain_pages_zone(cpu, zone);
2548         }
2549 }
2550
2551 /*
2552  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
2553  *
2554  * The CPU has to be pinned. When zone parameter is non-NULL, spill just
2555  * the single zone's pages.
2556  */
2557 void drain_local_pages(struct zone *zone)
2558 {
2559         int cpu = smp_processor_id();
2560
2561         if (zone)
2562                 drain_pages_zone(cpu, zone);
2563         else
2564                 drain_pages(cpu);
2565 }
2566
2567 static void drain_local_pages_wq(struct work_struct *work)
2568 {
2569         /*
2570          * drain_all_pages doesn't use proper cpu hotplug protection so
2571          * we can race with cpu offline when the WQ can move this from
2572          * a cpu pinned worker to an unbound one. We can operate on a different
2573          * cpu which is allright but we also have to make sure to not move to
2574          * a different one.
2575          */
2576         preempt_disable();
2577         drain_local_pages(NULL);
2578         preempt_enable();
2579 }
2580
2581 /*
2582  * Spill all the per-cpu pages from all CPUs back into the buddy allocator.
2583  *
2584  * When zone parameter is non-NULL, spill just the single zone's pages.
2585  *
2586  * Note that this can be extremely slow as the draining happens in a workqueue.
2587  */
2588 void drain_all_pages(struct zone *zone)
2589 {
2590         int cpu;
2591
2592         /*
2593          * Allocate in the BSS so we wont require allocation in
2594          * direct reclaim path for CONFIG_CPUMASK_OFFSTACK=y
2595          */
2596         static cpumask_t cpus_with_pcps;
2597
2598         /*
2599          * Make sure nobody triggers this path before mm_percpu_wq is fully
2600          * initialized.
2601          */
2602         if (WARN_ON_ONCE(!mm_percpu_wq))
2603                 return;
2604
2605         /*
2606          * Do not drain if one is already in progress unless it's specific to
2607          * a zone. Such callers are primarily CMA and memory hotplug and need
2608          * the drain to be complete when the call returns.
2609          */
2610         if (unlikely(!mutex_trylock(&pcpu_drain_mutex))) {
2611                 if (!zone)
2612                         return;
2613                 mutex_lock(&pcpu_drain_mutex);
2614         }
2615
2616         /*
2617          * We don't care about racing with CPU hotplug event
2618          * as offline notification will cause the notified
2619          * cpu to drain that CPU pcps and on_each_cpu_mask
2620          * disables preemption as part of its processing
2621          */
2622         for_each_online_cpu(cpu) {
2623                 struct per_cpu_pageset *pcp;
2624                 struct zone *z;
2625                 bool has_pcps = false;
2626
2627                 if (zone) {
2628                         pcp = per_cpu_ptr(zone->pageset, cpu);
2629                         if (pcp->pcp.count)
2630                                 has_pcps = true;
2631                 } else {
2632                         for_each_populated_zone(z) {
2633                                 pcp = per_cpu_ptr(z->pageset, cpu);
2634                                 if (pcp->pcp.count) {
2635                                         has_pcps = true;
2636                                         break;
2637                                 }
2638                         }
2639                 }
2640
2641                 if (has_pcps)
2642                         cpumask_set_cpu(cpu, &cpus_with_pcps);
2643                 else
2644                         cpumask_clear_cpu(cpu, &cpus_with_pcps);
2645         }
2646
2647         for_each_cpu(cpu, &cpus_with_pcps) {
2648                 struct work_struct *work = per_cpu_ptr(&pcpu_drain, cpu);
2649                 INIT_WORK(work, drain_local_pages_wq);
2650                 queue_work_on(cpu, mm_percpu_wq, work);
2651         }
2652         for_each_cpu(cpu, &cpus_with_pcps)
2653                 flush_work(per_cpu_ptr(&pcpu_drain, cpu));
2654
2655         mutex_unlock(&pcpu_drain_mutex);
2656 }
2657
2658 #ifdef CONFIG_HIBERNATION
2659
2660 /*
2661  * Touch the watchdog for every WD_PAGE_COUNT pages.
2662  */
2663 #define WD_PAGE_COUNT   (128*1024)
2664
2665 void mark_free_pages(struct zone *zone)
2666 {
2667         unsigned long pfn, max_zone_pfn, page_count = WD_PAGE_COUNT;
2668         unsigned long flags;
2669         unsigned int order, t;
2670         struct page *page;
2671
2672         if (zone_is_empty(zone))
2673                 return;
2674
2675         spin_lock_irqsave(&zone->lock, flags);
2676
2677         max_zone_pfn = zone_end_pfn(zone);
2678         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
2679                 if (pfn_valid(pfn)) {
2680                         page = pfn_to_page(pfn);
2681
2682                         if (!--page_count) {
2683                                 touch_nmi_watchdog();
2684                                 page_count = WD_PAGE_COUNT;
2685                         }
2686
2687                         if (page_zone(page) != zone)
2688                                 continue;
2689
2690                         if (!swsusp_page_is_forbidden(page))
2691                                 swsusp_unset_page_free(page);
2692                 }
2693
2694         for_each_migratetype_order(order, t) {
2695                 list_for_each_entry(page,
2696                                 &zone->free_area[order].free_list[t], lru) {
2697                         unsigned long i;
2698
2699                         pfn = page_to_pfn(page);
2700                         for (i = 0; i < (1UL << order); i++) {
2701                                 if (!--page_count) {
2702                                         touch_nmi_watchdog();
2703                                         page_count = WD_PAGE_COUNT;
2704                                 }
2705                                 swsusp_set_page_free(pfn_to_page(pfn + i));
2706                         }
2707                 }
2708         }
2709         spin_unlock_irqrestore(&zone->lock, flags);
2710 }
2711 #endif /* CONFIG_PM */
2712
2713 static bool free_unref_page_prepare(struct page *page, unsigned long pfn)
2714 {
2715         int migratetype;
2716
2717         if (!free_pcp_prepare(page))
2718                 return false;
2719
2720         migratetype = get_pfnblock_migratetype(page, pfn);
2721         set_pcppage_migratetype(page, migratetype);
2722         return true;
2723 }
2724
2725 static void free_unref_page_commit(struct page *page, unsigned long pfn)
2726 {
2727         struct zone *zone = page_zone(page);
2728         struct per_cpu_pages *pcp;
2729         int migratetype;
2730
2731         migratetype = get_pcppage_migratetype(page);
2732         __count_vm_event(PGFREE);
2733
2734         /*
2735          * We only track unmovable, reclaimable and movable on pcp lists.
2736          * Free ISOLATE pages back to the allocator because they are being
2737          * offlined but treat HIGHATOMIC as movable pages so we can get those
2738          * areas back if necessary. Otherwise, we may have to free
2739          * excessively into the page allocator
2740          */
2741         if (migratetype >= MIGRATE_PCPTYPES) {
2742                 if (unlikely(is_migrate_isolate(migratetype))) {
2743                         free_one_page(zone, page, pfn, 0, migratetype);
2744                         return;
2745                 }
2746                 migratetype = MIGRATE_MOVABLE;
2747         }
2748
2749         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2750         list_add(&page->lru, &pcp->lists[migratetype]);
2751         pcp->count++;
2752         if (pcp->count >= pcp->high) {
2753                 unsigned long batch = READ_ONCE(pcp->batch);
2754                 free_pcppages_bulk(zone, batch, pcp);
2755                 pcp->count -= batch;
2756         }
2757 }
2758
2759 /*
2760  * Free a 0-order page
2761  */
2762 void free_unref_page(struct page *page)
2763 {
2764         unsigned long flags;
2765         unsigned long pfn = page_to_pfn(page);
2766
2767         if (!free_unref_page_prepare(page, pfn))
2768                 return;
2769
2770         local_irq_save(flags);
2771         free_unref_page_commit(page, pfn);
2772         local_irq_restore(flags);
2773 }
2774
2775 /*
2776  * Free a list of 0-order pages
2777  */
2778 void free_unref_page_list(struct list_head *list)
2779 {
2780         struct page *page, *next;
2781         unsigned long flags, pfn;
2782         int batch_count = 0;
2783
2784         /* Prepare pages for freeing */
2785         list_for_each_entry_safe(page, next, list, lru) {
2786                 pfn = page_to_pfn(page);
2787                 if (!free_unref_page_prepare(page, pfn))
2788                         list_del(&page->lru);
2789                 set_page_private(page, pfn);
2790         }
2791
2792         local_irq_save(flags);
2793         list_for_each_entry_safe(page, next, list, lru) {
2794                 unsigned long pfn = page_private(page);
2795
2796                 set_page_private(page, 0);
2797                 trace_mm_page_free_batched(page);
2798                 free_unref_page_commit(page, pfn);
2799
2800                 /*
2801                  * Guard against excessive IRQ disabled times when we get
2802                  * a large list of pages to free.
2803                  */
2804                 if (++batch_count == SWAP_CLUSTER_MAX) {
2805                         local_irq_restore(flags);
2806                         batch_count = 0;
2807                         local_irq_save(flags);
2808                 }
2809         }
2810         local_irq_restore(flags);
2811 }
2812
2813 /*
2814  * split_page takes a non-compound higher-order page, and splits it into
2815  * n (1<<order) sub-pages: page[0..n]
2816  * Each sub-page must be freed individually.
2817  *
2818  * Note: this is probably too low level an operation for use in drivers.
2819  * Please consult with lkml before using this in your driver.
2820  */
2821 void split_page(struct page *page, unsigned int order)
2822 {
2823         int i;
2824
2825         VM_BUG_ON_PAGE(PageCompound(page), page);
2826         VM_BUG_ON_PAGE(!page_count(page), page);
2827
2828         for (i = 1; i < (1 << order); i++)
2829                 set_page_refcounted(page + i);
2830         split_page_owner(page, order);
2831 }
2832 EXPORT_SYMBOL_GPL(split_page);
2833
2834 int __isolate_free_page(struct page *page, unsigned int order)
2835 {
2836         unsigned long watermark;
2837         struct zone *zone;
2838         int mt;
2839
2840         BUG_ON(!PageBuddy(page));
2841
2842         zone = page_zone(page);
2843         mt = get_pageblock_migratetype(page);
2844
2845         if (!is_migrate_isolate(mt)) {
2846                 /*
2847                  * Obey watermarks as if the page was being allocated. We can
2848                  * emulate a high-order watermark check with a raised order-0
2849                  * watermark, because we already know our high-order page
2850                  * exists.
2851                  */
2852                 watermark = min_wmark_pages(zone) + (1UL << order);
2853                 if (!zone_watermark_ok(zone, 0, watermark, 0, ALLOC_CMA))
2854                         return 0;
2855
2856                 __mod_zone_freepage_state(zone, -(1UL << order), mt);
2857         }
2858
2859         /* Remove page from free list */
2860         list_del(&page->lru);
2861         zone->free_area[order].nr_free--;
2862         rmv_page_order(page);
2863
2864         /*
2865          * Set the pageblock if the isolated page is at least half of a
2866          * pageblock
2867          */
2868         if (order >= pageblock_order - 1) {
2869                 struct page *endpage = page + (1 << order) - 1;
2870                 for (; page < endpage; page += pageblock_nr_pages) {
2871                         int mt = get_pageblock_migratetype(page);
2872                         if (!is_migrate_isolate(mt) && !is_migrate_cma(mt)
2873                             && !is_migrate_highatomic(mt))
2874                                 set_pageblock_migratetype(page,
2875                                                           MIGRATE_MOVABLE);
2876                 }
2877         }
2878
2879
2880         return 1UL << order;
2881 }
2882
2883 /*
2884  * Update NUMA hit/miss statistics
2885  *
2886  * Must be called with interrupts disabled.
2887  */
2888 static inline void zone_statistics(struct zone *preferred_zone, struct zone *z)
2889 {
2890 #ifdef CONFIG_NUMA
2891         enum numa_stat_item local_stat = NUMA_LOCAL;
2892
2893         /* skip numa counters update if numa stats is disabled */
2894         if (!static_branch_likely(&vm_numa_stat_key))
2895                 return;
2896
2897         if (z->node != numa_node_id())
2898                 local_stat = NUMA_OTHER;
2899
2900         if (z->node == preferred_zone->node)
2901                 __inc_numa_state(z, NUMA_HIT);
2902         else {
2903                 __inc_numa_state(z, NUMA_MISS);
2904                 __inc_numa_state(preferred_zone, NUMA_FOREIGN);
2905         }
2906         __inc_numa_state(z, local_stat);
2907 #endif
2908 }
2909
2910 /* Remove page from the per-cpu list, caller must protect the list */
2911 static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
2912                         struct per_cpu_pages *pcp,
2913                         struct list_head *list)
2914 {
2915         struct page *page;
2916
2917         do {
2918                 if (list_empty(list)) {
2919                         pcp->count += rmqueue_bulk(zone, 0,
2920                                         pcp->batch, list,
2921                                         migratetype);
2922                         if (unlikely(list_empty(list)))
2923                                 return NULL;
2924                 }
2925
2926                 page = list_first_entry(list, struct page, lru);
2927                 list_del(&page->lru);
2928                 pcp->count--;
2929         } while (check_new_pcp(page));
2930
2931         return page;
2932 }
2933
2934 /* Lock and remove page from the per-cpu list */
2935 static struct page *rmqueue_pcplist(struct zone *preferred_zone,
2936                         struct zone *zone, unsigned int order,
2937                         gfp_t gfp_flags, int migratetype)
2938 {
2939         struct per_cpu_pages *pcp;
2940         struct list_head *list;
2941         struct page *page;
2942         unsigned long flags;
2943
2944         local_irq_save(flags);
2945         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2946         list = &pcp->lists[migratetype];
2947         page = __rmqueue_pcplist(zone,  migratetype, pcp, list);
2948         if (page) {
2949                 __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2950                 zone_statistics(preferred_zone, zone);
2951         }
2952         local_irq_restore(flags);
2953         return page;
2954 }
2955
2956 /*
2957  * Allocate a page from the given zone. Use pcplists for order-0 allocations.
2958  */
2959 static inline
2960 struct page *rmqueue(struct zone *preferred_zone,
2961                         struct zone *zone, unsigned int order,
2962                         gfp_t gfp_flags, unsigned int alloc_flags,
2963                         int migratetype)
2964 {
2965         unsigned long flags;
2966         struct page *page;
2967
2968         if (likely(order == 0)) {
2969                 page = rmqueue_pcplist(preferred_zone, zone, order,
2970                                 gfp_flags, migratetype);
2971                 goto out;
2972         }
2973
2974         /*
2975          * We most definitely don't want callers attempting to
2976          * allocate greater than order-1 page units with __GFP_NOFAIL.
2977          */
2978         WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
2979         spin_lock_irqsave(&zone->lock, flags);
2980
2981         do {
2982                 page = NULL;
2983                 if (alloc_flags & ALLOC_HARDER) {
2984                         page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
2985                         if (page)
2986                                 trace_mm_page_alloc_zone_locked(page, order, migratetype);
2987                 }
2988                 if (!page)
2989                         page = __rmqueue(zone, order, migratetype);
2990         } while (page && check_new_pages(page, order));
2991         spin_unlock(&zone->lock);
2992         if (!page)
2993                 goto failed;
2994         __mod_zone_freepage_state(zone, -(1 << order),
2995                                   get_pcppage_migratetype(page));
2996
2997         __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2998         zone_statistics(preferred_zone, zone);
2999         local_irq_restore(flags);
3000
3001 out:
3002         VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
3003         return page;
3004
3005 failed:
3006         local_irq_restore(flags);
3007         return NULL;
3008 }
3009
3010 #ifdef CONFIG_FAIL_PAGE_ALLOC
3011
3012 static struct {
3013         struct fault_attr attr;
3014
3015         bool ignore_gfp_highmem;
3016         bool ignore_gfp_reclaim;
3017         u32 min_order;
3018 } fail_page_alloc = {
3019         .attr = FAULT_ATTR_INITIALIZER,
3020         .ignore_gfp_reclaim = true,
3021         .ignore_gfp_highmem = true,
3022         .min_order = 1,
3023 };
3024
3025 static int __init setup_fail_page_alloc(char *str)
3026 {
3027         return setup_fault_attr(&fail_page_alloc.attr, str);
3028 }
3029 __setup("fail_page_alloc=", setup_fail_page_alloc);
3030
3031 static bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
3032 {
3033         if (order < fail_page_alloc.min_order)
3034                 return false;
3035         if (gfp_mask & __GFP_NOFAIL)
3036                 return false;
3037         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
3038                 return false;
3039         if (fail_page_alloc.ignore_gfp_reclaim &&
3040                         (gfp_mask & __GFP_DIRECT_RECLAIM))
3041                 return false;
3042
3043         return should_fail(&fail_page_alloc.attr, 1 << order);
3044 }
3045
3046 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
3047
3048 static int __init fail_page_alloc_debugfs(void)
3049 {
3050         umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
3051         struct dentry *dir;
3052
3053         dir = fault_create_debugfs_attr("fail_page_alloc", NULL,
3054                                         &fail_page_alloc.attr);
3055         if (IS_ERR(dir))
3056                 return PTR_ERR(dir);
3057
3058         if (!debugfs_create_bool("ignore-gfp-wait", mode, dir,
3059                                 &fail_page_alloc.ignore_gfp_reclaim))
3060                 goto fail;
3061         if (!debugfs_create_bool("ignore-gfp-highmem", mode, dir,
3062                                 &fail_page_alloc.ignore_gfp_highmem))
3063                 goto fail;
3064         if (!debugfs_create_u32("min-order", mode, dir,
3065                                 &fail_page_alloc.min_order))
3066                 goto fail;
3067
3068         return 0;
3069 fail:
3070         debugfs_remove_recursive(dir);
3071
3072         return -ENOMEM;
3073 }
3074
3075 late_initcall(fail_page_alloc_debugfs);
3076
3077 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
3078
3079 #else /* CONFIG_FAIL_PAGE_ALLOC */
3080
3081 static inline bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
3082 {
3083         return false;
3084 }
3085
3086 #endif /* CONFIG_FAIL_PAGE_ALLOC */
3087
3088 /*
3089  * Return true if free base pages are above 'mark'. For high-order checks it
3090  * will return true of the order-0 watermark is reached and there is at least
3091  * one free page of a suitable size. Checking now avoids taking the zone lock
3092  * to check in the allocation paths if no pages are free.
3093  */
3094 bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
3095                          int classzone_idx, unsigned int alloc_flags,
3096                          long free_pages)
3097 {
3098         long min = mark;
3099         int o;
3100         const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM));
3101
3102         /* free_pages may go negative - that's OK */
3103         free_pages -= (1 << order) - 1;
3104
3105         if (alloc_flags & ALLOC_HIGH)
3106                 min -= min / 2;
3107
3108         /*
3109          * If the caller does not have rights to ALLOC_HARDER then subtract
3110          * the high-atomic reserves. This will over-estimate the size of the
3111          * atomic reserve but it avoids a search.
3112          */
3113         if (likely(!alloc_harder)) {
3114                 free_pages -= z->nr_reserved_highatomic;
3115         } else {
3116                 /*
3117                  * OOM victims can try even harder than normal ALLOC_HARDER
3118                  * users on the grounds that it's definitely going to be in
3119                  * the exit path shortly and free memory. Any allocation it
3120                  * makes during the free path will be small and short-lived.
3121                  */
3122                 if (alloc_flags & ALLOC_OOM)
3123                         min -= min / 2;
3124                 else
3125                         min -= min / 4;
3126         }
3127
3128
3129 #ifdef CONFIG_CMA
3130         /* If allocation can't use CMA areas don't use free CMA pages */
3131         if (!(alloc_flags & ALLOC_CMA))
3132                 free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);
3133 #endif
3134
3135         /*
3136          * Check watermarks for an order-0 allocation request. If these
3137          * are not met, then a high-order request also cannot go ahead
3138          * even if a suitable page happened to be free.
3139          */
3140         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
3141                 return false;
3142
3143         /* If this is an order-0 request then the watermark is fine */
3144         if (!order)
3145                 return true;
3146
3147         /* For a high-order request, check at least one suitable page is free */
3148         for (o = order; o < MAX_ORDER; o++) {
3149                 struct free_area *area = &z->free_area[o];
3150                 int mt;
3151
3152                 if (!area->nr_free)
3153                         continue;
3154
3155                 for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
3156                         if (!list_empty(&area->free_list[mt]))
3157                                 return true;
3158                 }
3159
3160 #ifdef CONFIG_CMA
3161                 if ((alloc_flags & ALLOC_CMA) &&
3162                     !list_empty(&area->free_list[MIGRATE_CMA])) {
3163                         return true;
3164                 }
3165 #endif
3166                 if (alloc_harder &&
3167                         !list_empty(&area->free_list[MIGRATE_HIGHATOMIC]))
3168                         return true;
3169         }
3170         return false;
3171 }
3172
3173 bool zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
3174                       int classzone_idx, unsigned int alloc_flags)
3175 {
3176         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
3177                                         zone_page_state(z, NR_FREE_PAGES));
3178 }
3179
3180 static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
3181                 unsigned long mark, int classzone_idx, unsigned int alloc_flags)
3182 {
3183         long free_pages = zone_page_state(z, NR_FREE_PAGES);
3184         long cma_pages = 0;
3185
3186 #ifdef CONFIG_CMA
3187         /* If allocation can't use CMA areas don't use free CMA pages */
3188         if (!(alloc_flags & ALLOC_CMA))
3189                 cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
3190 #endif
3191
3192         /*
3193          * Fast check for order-0 only. If this fails then the reserves
3194          * need to be calculated. There is a corner case where the check
3195          * passes but only the high-order atomic reserve are free. If
3196          * the caller is !atomic then it'll uselessly search the free
3197          * list. That corner case is then slower but it is harmless.
3198          */
3199         if (!order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])
3200                 return true;
3201
3202         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
3203                                         free_pages);
3204 }
3205
3206 bool zone_watermark_ok_safe(struct zone *z, unsigned int order,
3207                         unsigned long mark, int classzone_idx)
3208 {
3209         long free_pages = zone_page_state(z, NR_FREE_PAGES);
3210
3211         if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
3212                 free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
3213
3214         return __zone_watermark_ok(z, order, mark, classzone_idx, 0,
3215                                                                 free_pages);
3216 }
3217
3218 #ifdef CONFIG_NUMA
3219 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3220 {
3221         return node_distance(zone_to_nid(local_zone), zone_to_nid(zone)) <=
3222                                 RECLAIM_DISTANCE;
3223 }
3224 #else   /* CONFIG_NUMA */
3225 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3226 {
3227         return true;
3228 }
3229 #endif  /* CONFIG_NUMA */
3230
3231 /*
3232  * get_page_from_freelist goes through the zonelist trying to allocate
3233  * a page.
3234  */
3235 static struct page *
3236 get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
3237                                                 const struct alloc_context *ac)
3238 {
3239         struct zoneref *z = ac->preferred_zoneref;
3240         struct zone *zone;
3241         struct pglist_data *last_pgdat_dirty_limit = NULL;
3242
3243         /*
3244          * Scan zonelist, looking for a zone with enough free.
3245          * See also __cpuset_node_allowed() comment in kernel/cpuset.c.
3246          */
3247         for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
3248                                                                 ac->nodemask) {
3249                 struct page *page;
3250                 unsigned long mark;
3251
3252                 if (cpusets_enabled() &&
3253                         (alloc_flags & ALLOC_CPUSET) &&
3254                         !__cpuset_zone_allowed(zone, gfp_mask))
3255                                 continue;
3256                 /*
3257                  * When allocating a page cache page for writing, we
3258                  * want to get it from a node that is within its dirty
3259                  * limit, such that no single node holds more than its
3260                  * proportional share of globally allowed dirty pages.
3261                  * The dirty limits take into account the node's
3262                  * lowmem reserves and high watermark so that kswapd
3263                  * should be able to balance it without having to
3264                  * write pages from its LRU list.
3265                  *
3266                  * XXX: For now, allow allocations to potentially
3267                  * exceed the per-node dirty limit in the slowpath
3268                  * (spread_dirty_pages unset) before going into reclaim,
3269                  * which is important when on a NUMA setup the allowed
3270                  * nodes are together not big enough to reach the
3271                  * global limit.  The proper fix for these situations
3272                  * will require awareness of nodes in the
3273                  * dirty-throttling and the flusher threads.
3274                  */
3275                 if (ac->spread_dirty_pages) {
3276                         if (last_pgdat_dirty_limit == zone->zone_pgdat)
3277                                 continue;
3278
3279                         if (!node_dirty_ok(zone->zone_pgdat)) {
3280                                 last_pgdat_dirty_limit = zone->zone_pgdat;
3281                                 continue;
3282                         }
3283                 }
3284
3285                 mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
3286                 if (!zone_watermark_fast(zone, order, mark,
3287                                        ac_classzone_idx(ac), alloc_flags)) {
3288                         int ret;
3289
3290 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
3291                         /*
3292                          * Watermark failed for this zone, but see if we can
3293                          * grow this zone if it contains deferred pages.
3294                          */
3295                         if (static_branch_unlikely(&deferred_pages)) {
3296                                 if (_deferred_grow_zone(zone, order))
3297                                         goto try_this_zone;
3298                         }
3299 #endif
3300                         /* Checked here to keep the fast path fast */
3301                         BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
3302                         if (alloc_flags & ALLOC_NO_WATERMARKS)
3303                                 goto try_this_zone;
3304
3305                         if (node_reclaim_mode == 0 ||
3306                             !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
3307                                 continue;
3308
3309                         ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
3310                         switch (ret) {
3311                         case NODE_RECLAIM_NOSCAN:
3312                                 /* did not scan */
3313                                 continue;
3314                         case NODE_RECLAIM_FULL:
3315                                 /* scanned but unreclaimable */
3316                                 continue;
3317                         default:
3318                                 /* did we reclaim enough */
3319                                 if (zone_watermark_ok(zone, order, mark,
3320                                                 ac_classzone_idx(ac), alloc_flags))
3321                                         goto try_this_zone;
3322
3323                                 continue;
3324                         }
3325                 }
3326
3327 try_this_zone:
3328                 page = rmqueue(ac->preferred_zoneref->zone, zone, order,
3329                                 gfp_mask, alloc_flags, ac->migratetype);
3330                 if (page) {
3331                         prep_new_page(page, order, gfp_mask, alloc_flags);
3332
3333                         /*
3334                          * If this is a high-order atomic allocation then check
3335                          * if the pageblock should be reserved for the future
3336                          */
3337                         if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
3338                                 reserve_highatomic_pageblock(page, zone, order);
3339
3340                         return page;
3341                 } else {
3342 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
3343                         /* Try again if zone has deferred pages */
3344                         if (static_branch_unlikely(&deferred_pages)) {
3345                                 if (_deferred_grow_zone(zone, order))
3346                                         goto try_this_zone;
3347                         }
3348 #endif
3349                 }
3350         }
3351
3352         return NULL;
3353 }
3354
3355 /*
3356  * Large machines with many possible nodes should not always dump per-node
3357  * meminfo in irq context.
3358  */
3359 static inline bool should_suppress_show_mem(void)
3360 {
3361         bool ret = false;
3362
3363 #if NODES_SHIFT > 8
3364         ret = in_interrupt();
3365 #endif
3366         return ret;
3367 }
3368
3369 static void warn_alloc_show_mem(gfp_t gfp_mask, nodemask_t *nodemask)
3370 {
3371         unsigned int filter = SHOW_MEM_FILTER_NODES;
3372         static DEFINE_RATELIMIT_STATE(show_mem_rs, HZ, 1);
3373
3374         if (should_suppress_show_mem() || !__ratelimit(&show_mem_rs))
3375                 return;
3376
3377         /*
3378          * This documents exceptions given to allocations in certain
3379          * contexts that are allowed to allocate outside current's set
3380          * of allowed nodes.
3381          */
3382         if (!(gfp_mask & __GFP_NOMEMALLOC))
3383                 if (tsk_is_oom_victim(current) ||
3384                     (current->flags & (PF_MEMALLOC | PF_EXITING)))
3385                         filter &= ~SHOW_MEM_FILTER_NODES;
3386         if (in_interrupt() || !(gfp_mask & __GFP_DIRECT_RECLAIM))
3387                 filter &= ~SHOW_MEM_FILTER_NODES;
3388
3389         show_mem(filter, nodemask);
3390 }
3391
3392 void warn_alloc(gfp_t gfp_mask, nodemask_t *nodemask, const char *fmt, ...)
3393 {
3394         struct va_format vaf;
3395         va_list args;
3396         static DEFINE_RATELIMIT_STATE(nopage_rs, DEFAULT_RATELIMIT_INTERVAL,
3397                                       DEFAULT_RATELIMIT_BURST);
3398
3399         if ((gfp_mask & __GFP_NOWARN) || !__ratelimit(&nopage_rs))
3400                 return;
3401
3402         va_start(args, fmt);
3403         vaf.fmt = fmt;
3404         vaf.va = &args;
3405         pr_warn("%s: %pV, mode:%#x(%pGg), nodemask=%*pbl\n",
3406                         current->comm, &vaf, gfp_mask, &gfp_mask,
3407                         nodemask_pr_args(nodemask));
3408         va_end(args);
3409
3410         cpuset_print_current_mems_allowed();
3411
3412         dump_stack();
3413         warn_alloc_show_mem(gfp_mask, nodemask);
3414 }
3415
3416 static inline struct page *
3417 __alloc_pages_cpuset_fallback(gfp_t gfp_mask, unsigned int order,
3418                               unsigned int alloc_flags,
3419                               const struct alloc_context *ac)
3420 {
3421         struct page *page;
3422
3423         page = get_page_from_freelist(gfp_mask, order,
3424                         alloc_flags|ALLOC_CPUSET, ac);
3425         /*
3426          * fallback to ignore cpuset restriction if our nodes
3427          * are depleted
3428          */
3429         if (!page)
3430                 page = get_page_from_freelist(gfp_mask, order,
3431                                 alloc_flags, ac);
3432
3433         return page;
3434 }
3435
3436 static inline struct page *
3437 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
3438         const struct alloc_context *ac, unsigned long *did_some_progress)
3439 {
3440         struct oom_control oc = {
3441                 .zonelist = ac->zonelist,
3442                 .nodemask = ac->nodemask,
3443                 .memcg = NULL,
3444                 .gfp_mask = gfp_mask,
3445                 .order = order,
3446         };
3447         struct page *page;
3448
3449         *did_some_progress = 0;
3450
3451         /*
3452          * Acquire the oom lock.  If that fails, somebody else is
3453          * making progress for us.
3454          */
3455         if (!mutex_trylock(&oom_lock)) {
3456                 *did_some_progress = 1;
3457                 schedule_timeout_uninterruptible(1);
3458                 return NULL;
3459         }
3460
3461         /*
3462          * Go through the zonelist yet one more time, keep very high watermark
3463          * here, this is only to catch a parallel oom killing, we must fail if
3464          * we're still under heavy pressure. But make sure that this reclaim
3465          * attempt shall not depend on __GFP_DIRECT_RECLAIM && !__GFP_NORETRY
3466          * allocation which will never fail due to oom_lock already held.
3467          */
3468         page = get_page_from_freelist((gfp_mask | __GFP_HARDWALL) &
3469                                       ~__GFP_DIRECT_RECLAIM, order,
3470                                       ALLOC_WMARK_HIGH|ALLOC_CPUSET, ac);
3471         if (page)
3472                 goto out;
3473
3474         /* Coredumps can quickly deplete all memory reserves */
3475         if (current->flags & PF_DUMPCORE)
3476                 goto out;
3477         /* The OOM killer will not help higher order allocs */
3478         if (order > PAGE_ALLOC_COSTLY_ORDER)
3479                 goto out;
3480         /*
3481          * We have already exhausted all our reclaim opportunities without any
3482          * success so it is time to admit defeat. We will skip the OOM killer
3483          * because it is very likely that the caller has a more reasonable
3484          * fallback than shooting a random task.
3485          */
3486         if (gfp_mask & __GFP_RETRY_MAYFAIL)
3487                 goto out;
3488         /* The OOM killer does not needlessly kill tasks for lowmem */
3489         if (ac->high_zoneidx < ZONE_NORMAL)
3490                 goto out;
3491         if (pm_suspended_storage())
3492                 goto out;
3493         /*
3494          * XXX: GFP_NOFS allocations should rather fail than rely on
3495          * other request to make a forward progress.
3496          * We are in an unfortunate situation where out_of_memory cannot
3497          * do much for this context but let's try it to at least get
3498          * access to memory reserved if the current task is killed (see
3499          * out_of_memory). Once filesystems are ready to handle allocation
3500          * failures more gracefully we should just bail out here.
3501          */
3502
3503         /* The OOM killer may not free memory on a specific node */
3504         if (gfp_mask & __GFP_THISNODE)
3505                 goto out;
3506
3507         /* Exhausted what can be done so it's blame time */
3508         if (out_of_memory(&oc) || WARN_ON_ONCE(gfp_mask & __GFP_NOFAIL)) {
3509                 *did_some_progress = 1;
3510
3511                 /*
3512                  * Help non-failing allocations by giving them access to memory
3513                  * reserves
3514                  */
3515                 if (gfp_mask & __GFP_NOFAIL)
3516                         page = __alloc_pages_cpuset_fallback(gfp_mask, order,
3517                                         ALLOC_NO_WATERMARKS, ac);
3518         }
3519 out:
3520         mutex_unlock(&oom_lock);
3521         return page;
3522 }
3523
3524 /*
3525  * Maximum number of compaction retries wit a progress before OOM
3526  * killer is consider as the only way to move forward.
3527  */
3528 #define MAX_COMPACT_RETRIES 16
3529
3530 #ifdef CONFIG_COMPACTION
3531 /* Try memory compaction for high-order allocations before reclaim */
3532 static struct page *
3533 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3534                 unsigned int alloc_flags, const struct alloc_context *ac,
3535                 enum compact_priority prio, enum compact_result *compact_result)
3536 {
3537         struct page *page;
3538         unsigned int noreclaim_flag;
3539
3540         if (!order)
3541                 return NULL;
3542
3543         noreclaim_flag = memalloc_noreclaim_save();
3544         *compact_result = try_to_compact_pages(gfp_mask, order, alloc_flags, ac,
3545                                                                         prio);
3546         memalloc_noreclaim_restore(noreclaim_flag);
3547
3548         if (*compact_result <= COMPACT_INACTIVE)
3549                 return NULL;
3550
3551         /*
3552          * At least in one zone compaction wasn't deferred or skipped, so let's
3553          * count a compaction stall
3554          */
3555         count_vm_event(COMPACTSTALL);
3556
3557         page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
3558
3559         if (page) {
3560                 struct zone *zone = page_zone(page);
3561
3562                 zone->compact_blockskip_flush = false;
3563                 compaction_defer_reset(zone, order, true);
3564                 count_vm_event(COMPACTSUCCESS);
3565                 return page;
3566         }
3567
3568         /*
3569          * It's bad if compaction run occurs and fails. The most likely reason
3570          * is that pages exist, but not enough to satisfy watermarks.
3571          */
3572         count_vm_event(COMPACTFAIL);
3573
3574         cond_resched();
3575
3576         return NULL;
3577 }
3578
3579 static inline bool
3580 should_compact_retry(struct alloc_context *ac, int order, int alloc_flags,
3581                      enum compact_result compact_result,
3582                      enum compact_priority *compact_priority,
3583                      int *compaction_retries)
3584 {
3585         int max_retries = MAX_COMPACT_RETRIES;
3586         int min_priority;
3587         bool ret = false;
3588         int retries = *compaction_retries;
3589         enum compact_priority priority = *compact_priority;
3590
3591         if (!order)
3592                 return false;
3593
3594         if (compaction_made_progress(compact_result))
3595                 (*compaction_retries)++;
3596
3597         /*
3598          * compaction considers all the zone as desperately out of memory
3599          * so it doesn't really make much sense to retry except when the
3600          * failure could be caused by insufficient priority
3601          */
3602         if (compaction_failed(compact_result))
3603                 goto check_priority;
3604
3605         /*
3606          * make sure the compaction wasn't deferred or didn't bail out early
3607          * due to locks contention before we declare that we should give up.
3608          * But do not retry if the given zonelist is not suitable for
3609          * compaction.
3610          */
3611         if (compaction_withdrawn(compact_result)) {
3612                 ret = compaction_zonelist_suitable(ac, order, alloc_flags);
3613                 goto out;
3614         }
3615
3616         /*
3617          * !costly requests are much more important than __GFP_RETRY_MAYFAIL
3618          * costly ones because they are de facto nofail and invoke OOM
3619          * killer to move on while costly can fail and users are ready
3620          * to cope with that. 1/4 retries is rather arbitrary but we
3621          * would need much more detailed feedback from compaction to
3622          * make a better decision.
3623          */
3624         if (order > PAGE_ALLOC_COSTLY_ORDER)
3625                 max_retries /= 4;
3626         if (*compaction_retries <= max_retries) {
3627                 ret = true;
3628                 goto out;
3629         }
3630
3631         /*
3632          * Make sure there are attempts at the highest priority if we exhausted
3633          * all retries or failed at the lower priorities.
3634          */
3635 check_priority:
3636         min_priority = (order > PAGE_ALLOC_COSTLY_ORDER) ?
3637                         MIN_COMPACT_COSTLY_PRIORITY : MIN_COMPACT_PRIORITY;
3638
3639         if (*compact_priority > min_priority) {
3640                 (*compact_priority)--;
3641                 *compaction_retries = 0;
3642                 ret = true;
3643         }
3644 out:
3645         trace_compact_retry(order, priority, compact_result, retries, max_retries, ret);
3646         return ret;
3647 }
3648 #else
3649 static inline struct page *
3650 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3651                 unsigned int alloc_flags, const struct alloc_context *ac,
3652                 enum compact_priority prio, enum compact_result *compact_result)
3653 {
3654         *compact_result = COMPACT_SKIPPED;
3655         return NULL;
3656 }
3657
3658 static inline bool
3659 should_compact_retry(struct alloc_context *ac, unsigned int order, int alloc_flags,
3660                      enum compact_result compact_result,
3661                      enum compact_priority *compact_priority,
3662                      int *compaction_retries)
3663 {
3664         struct zone *zone;
3665         struct zoneref *z;
3666
3667         if (!order || order > PAGE_ALLOC_COSTLY_ORDER)
3668                 return false;
3669
3670         /*
3671          * There are setups with compaction disabled which would prefer to loop
3672          * inside the allocator rather than hit the oom killer prematurely.
3673          * Let's give them a good hope and keep retrying while the order-0
3674          * watermarks are OK.
3675          */
3676         for_each_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
3677                                         ac->nodemask) {
3678                 if (zone_watermark_ok(zone, 0, min_wmark_pages(zone),
3679                                         ac_classzone_idx(ac), alloc_flags))
3680                         return true;
3681         }
3682         return false;
3683 }
3684 #endif /* CONFIG_COMPACTION */
3685
3686 #ifdef CONFIG_LOCKDEP
3687 struct lockdep_map __fs_reclaim_map =
3688         STATIC_LOCKDEP_MAP_INIT("fs_reclaim", &__fs_reclaim_map);
3689
3690 static bool __need_fs_reclaim(gfp_t gfp_mask)
3691 {
3692         gfp_mask = current_gfp_context(gfp_mask);
3693
3694         /* no reclaim without waiting on it */
3695         if (!(gfp_mask & __GFP_DIRECT_RECLAIM))
3696                 return false;
3697
3698         /* this guy won't enter reclaim */
3699         if (current->flags & PF_MEMALLOC)
3700                 return false;
3701
3702         /* We're only interested __GFP_FS allocations for now */
3703         if (!(gfp_mask & __GFP_FS))
3704                 return false;
3705
3706         if (gfp_mask & __GFP_NOLOCKDEP)
3707                 return false;
3708
3709         return true;
3710 }
3711
3712 void fs_reclaim_acquire(gfp_t gfp_mask)
3713 {
3714         if (__need_fs_reclaim(gfp_mask))
3715                 lock_map_acquire(&__fs_reclaim_map);
3716 }
3717 EXPORT_SYMBOL_GPL(fs_reclaim_acquire);
3718
3719 void fs_reclaim_release(gfp_t gfp_mask)
3720 {
3721         if (__need_fs_reclaim(gfp_mask))
3722                 lock_map_release(&__fs_reclaim_map);
3723 }
3724 EXPORT_SYMBOL_GPL(fs_reclaim_release);
3725 #endif
3726
3727 /* Perform direct synchronous page reclaim */
3728 static int
3729 __perform_reclaim(gfp_t gfp_mask, unsigned int order,
3730                                         const struct alloc_context *ac)
3731 {
3732         struct reclaim_state reclaim_state;
3733         int progress;
3734         unsigned int noreclaim_flag;
3735
3736         cond_resched();
3737
3738         /* We now go into synchronous reclaim */
3739         cpuset_memory_pressure_bump();
3740         noreclaim_flag = memalloc_noreclaim_save();
3741         fs_reclaim_acquire(gfp_mask);
3742         reclaim_state.reclaimed_slab = 0;
3743         current->reclaim_state = &reclaim_state;
3744
3745         progress = try_to_free_pages(ac->zonelist, order, gfp_mask,
3746                                                                 ac->nodemask);
3747
3748         current->reclaim_state = NULL;
3749         fs_reclaim_release(gfp_mask);
3750         memalloc_noreclaim_restore(noreclaim_flag);
3751
3752         cond_resched();
3753
3754         return progress;
3755 }
3756
3757 /* The really slow allocator path where we enter direct reclaim */
3758 static inline struct page *
3759 __alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
3760                 unsigned int alloc_flags, const struct alloc_context *ac,
3761                 unsigned long *did_some_progress)
3762 {
3763         struct page *page = NULL;
3764         bool drained = false;
3765
3766         *did_some_progress = __perform_reclaim(gfp_mask, order, ac);
3767         if (unlikely(!(*did_some_progress)))
3768                 return NULL;
3769
3770 retry:
3771         page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
3772
3773         /*
3774          * If an allocation failed after direct reclaim, it could be because
3775          * pages are pinned on the per-cpu lists or in high alloc reserves.
3776          * Shrink them them and try again
3777          */
3778         if (!page && !drained) {
3779                 unreserve_highatomic_pageblock(ac, false);
3780                 drain_all_pages(NULL);
3781                 drained = true;
3782                 goto retry;
3783         }
3784
3785         return page;
3786 }
3787
3788 static void wake_all_kswapds(unsigned int order, const struct alloc_context *ac)
3789 {
3790         struct zoneref *z;
3791         struct zone *zone;
3792         pg_data_t *last_pgdat = NULL;
3793
3794         for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
3795                                         ac->high_zoneidx, ac->nodemask) {
3796                 if (last_pgdat != zone->zone_pgdat)
3797                         wakeup_kswapd(zone, order, ac->high_zoneidx);
3798                 last_pgdat = zone->zone_pgdat;
3799         }
3800 }
3801
3802 static inline unsigned int
3803 gfp_to_alloc_flags(gfp_t gfp_mask)
3804 {
3805         unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
3806
3807         /* __GFP_HIGH is assumed to be the same as ALLOC_HIGH to save a branch. */
3808         BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_HIGH);
3809
3810         /*
3811          * The caller may dip into page reserves a bit more if the caller
3812          * cannot run direct reclaim, or if the caller has realtime scheduling
3813          * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
3814          * set both ALLOC_HARDER (__GFP_ATOMIC) and ALLOC_HIGH (__GFP_HIGH).
3815          */
3816         alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);
3817
3818         if (gfp_mask & __GFP_ATOMIC) {
3819                 /*
3820                  * Not worth trying to allocate harder for __GFP_NOMEMALLOC even
3821                  * if it can't schedule.
3822                  */
3823                 if (!(gfp_mask & __GFP_NOMEMALLOC))
3824                         alloc_flags |= ALLOC_HARDER;
3825                 /*
3826                  * Ignore cpuset mems for GFP_ATOMIC rather than fail, see the
3827                  * comment for __cpuset_node_allowed().
3828                  */
3829                 alloc_flags &= ~ALLOC_CPUSET;
3830         } else if (unlikely(rt_task(current)) && !in_interrupt())
3831                 alloc_flags |= ALLOC_HARDER;
3832
3833 #ifdef CONFIG_CMA
3834         if (gfpflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
3835                 alloc_flags |= ALLOC_CMA;
3836 #endif
3837         return alloc_flags;
3838 }
3839
3840 static bool oom_reserves_allowed(struct task_struct *tsk)
3841 {
3842         if (!tsk_is_oom_victim(tsk))
3843                 return false;
3844
3845         /*
3846          * !MMU doesn't have oom reaper so give access to memory reserves
3847          * only to the thread with TIF_MEMDIE set
3848          */
3849         if (!IS_ENABLED(CONFIG_MMU) && !test_thread_flag(TIF_MEMDIE))
3850                 return false;
3851
3852         return true;
3853 }
3854
3855 /*
3856  * Distinguish requests which really need access to full memory
3857  * reserves from oom victims which can live with a portion of it
3858  */
3859 static inline int __gfp_pfmemalloc_flags(gfp_t gfp_mask)
3860 {
3861         if (unlikely(gfp_mask & __GFP_NOMEMALLOC))
3862                 return 0;
3863         if (gfp_mask & __GFP_MEMALLOC)
3864                 return ALLOC_NO_WATERMARKS;
3865         if (in_serving_softirq() && (current->flags & PF_MEMALLOC))
3866                 return ALLOC_NO_WATERMARKS;
3867         if (!in_interrupt()) {
3868                 if (current->flags & PF_MEMALLOC)
3869                         return ALLOC_NO_WATERMARKS;
3870                 else if (oom_reserves_allowed(current))
3871                         return ALLOC_OOM;
3872         }
3873
3874         return 0;
3875 }
3876
3877 bool gfp_pfmemalloc_allowed(gfp_t gfp_mask)
3878 {
3879         return !!__gfp_pfmemalloc_flags(gfp_mask);
3880 }
3881
3882 /*
3883  * Checks whether it makes sense to retry the reclaim to make a forward progress
3884  * for the given allocation request.
3885  *
3886  * We give up when we either have tried MAX_RECLAIM_RETRIES in a row
3887  * without success, or when we couldn't even meet the watermark if we
3888  * reclaimed all remaining pages on the LRU lists.
3889  *
3890  * Returns true if a retry is viable or false to enter the oom path.
3891  */
3892 static inline bool
3893 should_reclaim_retry(gfp_t gfp_mask, unsigned order,
3894                      struct alloc_context *ac, int alloc_flags,
3895                      bool did_some_progress, int *no_progress_loops)
3896 {
3897         struct zone *zone;
3898         struct zoneref *z;
3899
3900         /*
3901          * Costly allocations might have made a progress but this doesn't mean
3902          * their order will become available due to high fragmentation so
3903          * always increment the no progress counter for them
3904          */
3905         if (did_some_progress && order <= PAGE_ALLOC_COSTLY_ORDER)
3906                 *no_progress_loops = 0;
3907         else
3908                 (*no_progress_loops)++;
3909
3910         /*
3911          * Make sure we converge to OOM if we cannot make any progress
3912          * several times in the row.
3913          */
3914         if (*no_progress_loops > MAX_RECLAIM_RETRIES) {
3915                 /* Before OOM, exhaust highatomic_reserve */
3916                 return unreserve_highatomic_pageblock(ac, true);
3917         }
3918
3919         /*
3920          * Keep reclaiming pages while there is a chance this will lead
3921          * somewhere.  If none of the target zones can satisfy our allocation
3922          * request even if all reclaimable pages are considered then we are
3923          * screwed and have to go OOM.
3924          */
3925         for_each_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
3926                                         ac->nodemask) {
3927                 unsigned long available;
3928                 unsigned long reclaimable;
3929                 unsigned long min_wmark = min_wmark_pages(zone);
3930                 bool wmark;
3931
3932                 available = reclaimable = zone_reclaimable_pages(zone);
3933                 available += zone_page_state_snapshot(zone, NR_FREE_PAGES);
3934
3935                 /*
3936                  * Would the allocation succeed if we reclaimed all
3937                  * reclaimable pages?
3938                  */
3939                 wmark = __zone_watermark_ok(zone, order, min_wmark,
3940                                 ac_classzone_idx(ac), alloc_flags, available);
3941                 trace_reclaim_retry_zone(z, order, reclaimable,
3942                                 available, min_wmark, *no_progress_loops, wmark);
3943                 if (wmark) {
3944                         /*
3945                          * If we didn't make any progress and have a lot of
3946                          * dirty + writeback pages then we should wait for
3947                          * an IO to complete to slow down the reclaim and
3948                          * prevent from pre mature OOM
3949                          */
3950                         if (!did_some_progress) {
3951                                 unsigned long write_pending;
3952
3953                                 write_pending = zone_page_state_snapshot(zone,
3954                                                         NR_ZONE_WRITE_PENDING);
3955
3956                                 if (2 * write_pending > reclaimable) {
3957                                         congestion_wait(BLK_RW_ASYNC, HZ/10);
3958                                         return true;
3959                                 }
3960                         }
3961
3962                         /*
3963                          * Memory allocation/reclaim might be called from a WQ
3964                          * context and the current implementation of the WQ
3965                          * concurrency control doesn't recognize that
3966                          * a particular WQ is congested if the worker thread is
3967                          * looping without ever sleeping. Therefore we have to
3968                          * do a short sleep here rather than calling
3969                          * cond_resched().
3970                          */
3971                         if (current->flags & PF_WQ_WORKER)
3972                                 schedule_timeout_uninterruptible(1);
3973                         else
3974                                 cond_resched();
3975
3976                         return true;
3977                 }
3978         }
3979
3980         return false;
3981 }
3982
3983 static inline bool
3984 check_retry_cpuset(int cpuset_mems_cookie, struct alloc_context *ac)
3985 {
3986         /*
3987          * It's possible that cpuset's mems_allowed and the nodemask from
3988          * mempolicy don't intersect. This should be normally dealt with by
3989          * policy_nodemask(), but it's possible to race with cpuset update in
3990          * such a way the check therein was true, and then it became false
3991          * before we got our cpuset_mems_cookie here.
3992          * This assumes that for all allocations, ac->nodemask can come only
3993          * from MPOL_BIND mempolicy (whose documented semantics is to be ignored
3994          * when it does not intersect with the cpuset restrictions) or the
3995          * caller can deal with a violated nodemask.
3996          */
3997         if (cpusets_enabled() && ac->nodemask &&
3998                         !cpuset_nodemask_valid_mems_allowed(ac->nodemask)) {
3999                 ac->nodemask = NULL;
4000                 return true;
4001         }
4002
4003         /*
4004          * When updating a task's mems_allowed or mempolicy nodemask, it is
4005          * possible to race with parallel threads in such a way that our
4006          * allocation can fail while the mask is being updated. If we are about
4007          * to fail, check if the cpuset changed during allocation and if so,
4008          * retry.
4009          */
4010         if (read_mems_allowed_retry(cpuset_mems_cookie))
4011                 return true;
4012
4013         return false;
4014 }
4015
4016 static inline struct page *
4017 __alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
4018                                                 struct alloc_context *ac)
4019 {
4020         bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
4021         const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
4022         struct page *page = NULL;
4023         unsigned int alloc_flags;
4024         unsigned long did_some_progress;
4025         enum compact_priority compact_priority;
4026         enum compact_result compact_result;
4027         int compaction_retries;
4028         int no_progress_loops;
4029         unsigned int cpuset_mems_cookie;
4030         int reserve_flags;
4031
4032         /*
4033          * In the slowpath, we sanity check order to avoid ever trying to
4034          * reclaim >= MAX_ORDER areas which will never succeed. Callers may
4035          * be using allocators in order of preference for an area that is
4036          * too large.
4037          */
4038         if (order >= MAX_ORDER) {
4039                 WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
4040                 return NULL;
4041         }
4042
4043         /*
4044          * We also sanity check to catch abuse of atomic reserves being used by
4045          * callers that are not in atomic context.
4046          */
4047         if (WARN_ON_ONCE((gfp_mask & (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)) ==
4048                                 (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)))
4049                 gfp_mask &= ~__GFP_ATOMIC;
4050
4051 retry_cpuset:
4052         compaction_retries = 0;
4053         no_progress_loops = 0;
4054         compact_priority = DEF_COMPACT_PRIORITY;
4055         cpuset_mems_cookie = read_mems_allowed_begin();
4056
4057         /*
4058          * The fast path uses conservative alloc_flags to succeed only until
4059          * kswapd needs to be woken up, and to avoid the cost of setting up
4060          * alloc_flags precisely. So we do that now.
4061          */
4062         alloc_flags = gfp_to_alloc_flags(gfp_mask);
4063
4064         /*
4065          * We need to recalculate the starting point for the zonelist iterator
4066          * because we might have used different nodemask in the fast path, or
4067          * there was a cpuset modification and we are retrying - otherwise we
4068          * could end up iterating over non-eligible zones endlessly.
4069          */
4070         ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
4071                                         ac->high_zoneidx, ac->nodemask);
4072         if (!ac->preferred_zoneref->zone)
4073                 goto nopage;
4074
4075         if (gfp_mask & __GFP_KSWAPD_RECLAIM)
4076                 wake_all_kswapds(order, ac);
4077
4078         /*
4079          * The adjusted alloc_flags might result in immediate success, so try
4080          * that first
4081          */
4082         page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
4083         if (page)
4084                 goto got_pg;
4085
4086         /*
4087          * For costly allocations, try direct compaction first, as it's likely
4088          * that we have enough base pages and don't need to reclaim. For non-
4089          * movable high-order allocations, do that as well, as compaction will
4090          * try prevent permanent fragmentation by migrating from blocks of the
4091          * same migratetype.
4092          * Don't try this for allocations that are allowed to ignore
4093          * watermarks, as the ALLOC_NO_WATERMARKS attempt didn't yet happen.
4094          */
4095         if (can_direct_reclaim &&
4096                         (costly_order ||
4097                            (order > 0 && ac->migratetype != MIGRATE_MOVABLE))
4098                         && !gfp_pfmemalloc_allowed(gfp_mask)) {
4099                 page = __alloc_pages_direct_compact(gfp_mask, order,
4100                                                 alloc_flags, ac,
4101                                                 INIT_COMPACT_PRIORITY,
4102                                                 &compact_result);
4103                 if (page)
4104                         goto got_pg;
4105
4106                 /*
4107                  * Checks for costly allocations with __GFP_NORETRY, which
4108                  * includes THP page fault allocations
4109                  */
4110                 if (costly_order && (gfp_mask & __GFP_NORETRY)) {
4111                         /*
4112                          * If compaction is deferred for high-order allocations,
4113                          * it is because sync compaction recently failed. If
4114                          * this is the case and the caller requested a THP
4115                          * allocation, we do not want to heavily disrupt the
4116                          * system, so we fail the allocation instead of entering
4117                          * direct reclaim.
4118                          */
4119                         if (compact_result == COMPACT_DEFERRED)
4120                                 goto nopage;
4121
4122                         /*
4123                          * Looks like reclaim/compaction is worth trying, but
4124                          * sync compaction could be very expensive, so keep
4125                          * using async compaction.
4126                          */
4127                         compact_priority = INIT_COMPACT_PRIORITY;
4128                 }
4129         }
4130
4131 retry:
4132         /* Ensure kswapd doesn't accidentally go to sleep as long as we loop */
4133         if (gfp_mask & __GFP_KSWAPD_RECLAIM)
4134                 wake_all_kswapds(order, ac);
4135
4136         reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
4137         if (reserve_flags)
4138                 alloc_flags = reserve_flags;
4139
4140         /*
4141          * Reset the zonelist iterators if memory policies can be ignored.
4142          * These allocations are high priority and system rather than user