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