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