mm/free_pcppages_bulk: do not hold lock when picking pages to free
[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         struct page *page, *tmp;
1084         LIST_HEAD(head);
1085
1086         while (count) {
1087                 struct list_head *list;
1088
1089                 /*
1090                  * Remove pages from lists in a round-robin fashion. A
1091                  * batch_free count is maintained that is incremented when an
1092                  * empty list is encountered.  This is so more pages are freed
1093                  * off fuller lists instead of spinning excessively around empty
1094                  * lists
1095                  */
1096                 do {
1097                         batch_free++;
1098                         if (++migratetype == MIGRATE_PCPTYPES)
1099                                 migratetype = 0;
1100                         list = &pcp->lists[migratetype];
1101                 } while (list_empty(list));
1102
1103                 /* This is the only non-empty list. Free them all. */
1104                 if (batch_free == MIGRATE_PCPTYPES)
1105                         batch_free = count;
1106
1107                 do {
1108                         page = list_last_entry(list, struct page, lru);
1109                         /* must delete to avoid corrupting pcp list */
1110                         list_del(&page->lru);
1111                         pcp->count--;
1112
1113                         if (bulkfree_pcp_prepare(page))
1114                                 continue;
1115
1116                         list_add_tail(&page->lru, &head);
1117                 } while (--count && --batch_free && !list_empty(list));
1118         }
1119
1120         spin_lock(&zone->lock);
1121         isolated_pageblocks = has_isolate_pageblock(zone);
1122
1123         /*
1124          * Use safe version since after __free_one_page(),
1125          * page->lru.next will not point to original list.
1126          */
1127         list_for_each_entry_safe(page, tmp, &head, lru) {
1128                 int mt = get_pcppage_migratetype(page);
1129                 /* MIGRATE_ISOLATE page should not go to pcplists */
1130                 VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
1131                 /* Pageblock could have been isolated meanwhile */
1132                 if (unlikely(isolated_pageblocks))
1133                         mt = get_pageblock_migratetype(page);
1134
1135                 __free_one_page(page, page_to_pfn(page), zone, 0, mt);
1136                 trace_mm_page_pcpu_drain(page, 0, mt);
1137         }
1138         spin_unlock(&zone->lock);
1139 }
1140
1141 static void free_one_page(struct zone *zone,
1142                                 struct page *page, unsigned long pfn,
1143                                 unsigned int order,
1144                                 int migratetype)
1145 {
1146         spin_lock(&zone->lock);
1147         if (unlikely(has_isolate_pageblock(zone) ||
1148                 is_migrate_isolate(migratetype))) {
1149                 migratetype = get_pfnblock_migratetype(page, pfn);
1150         }
1151         __free_one_page(page, pfn, zone, order, migratetype);
1152         spin_unlock(&zone->lock);
1153 }
1154
1155 static void __meminit __init_single_page(struct page *page, unsigned long pfn,
1156                                 unsigned long zone, int nid)
1157 {
1158         mm_zero_struct_page(page);
1159         set_page_links(page, zone, nid, pfn);
1160         init_page_count(page);
1161         page_mapcount_reset(page);
1162         page_cpupid_reset_last(page);
1163
1164         INIT_LIST_HEAD(&page->lru);
1165 #ifdef WANT_PAGE_VIRTUAL
1166         /* The shift won't overflow because ZONE_NORMAL is below 4G. */
1167         if (!is_highmem_idx(zone))
1168                 set_page_address(page, __va(pfn << PAGE_SHIFT));
1169 #endif
1170 }
1171
1172 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1173 static void __meminit init_reserved_page(unsigned long pfn)
1174 {
1175         pg_data_t *pgdat;
1176         int nid, zid;
1177
1178         if (!early_page_uninitialised(pfn))
1179                 return;
1180
1181         nid = early_pfn_to_nid(pfn);
1182         pgdat = NODE_DATA(nid);
1183
1184         for (zid = 0; zid < MAX_NR_ZONES; zid++) {
1185                 struct zone *zone = &pgdat->node_zones[zid];
1186
1187                 if (pfn >= zone->zone_start_pfn && pfn < zone_end_pfn(zone))
1188                         break;
1189         }
1190         __init_single_page(pfn_to_page(pfn), pfn, zid, nid);
1191 }
1192 #else
1193 static inline void init_reserved_page(unsigned long pfn)
1194 {
1195 }
1196 #endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
1197
1198 /*
1199  * Initialised pages do not have PageReserved set. This function is
1200  * called for each range allocated by the bootmem allocator and
1201  * marks the pages PageReserved. The remaining valid pages are later
1202  * sent to the buddy page allocator.
1203  */
1204 void __meminit reserve_bootmem_region(phys_addr_t start, phys_addr_t end)
1205 {
1206         unsigned long start_pfn = PFN_DOWN(start);
1207         unsigned long end_pfn = PFN_UP(end);
1208
1209         for (; start_pfn < end_pfn; start_pfn++) {
1210                 if (pfn_valid(start_pfn)) {
1211                         struct page *page = pfn_to_page(start_pfn);
1212
1213                         init_reserved_page(start_pfn);
1214
1215                         /* Avoid false-positive PageTail() */
1216                         INIT_LIST_HEAD(&page->lru);
1217
1218                         SetPageReserved(page);
1219                 }
1220         }
1221 }
1222
1223 static void __free_pages_ok(struct page *page, unsigned int order)
1224 {
1225         unsigned long flags;
1226         int migratetype;
1227         unsigned long pfn = page_to_pfn(page);
1228
1229         if (!free_pages_prepare(page, order, true))
1230                 return;
1231
1232         migratetype = get_pfnblock_migratetype(page, pfn);
1233         local_irq_save(flags);
1234         __count_vm_events(PGFREE, 1 << order);
1235         free_one_page(page_zone(page), page, pfn, order, migratetype);
1236         local_irq_restore(flags);
1237 }
1238
1239 static void __init __free_pages_boot_core(struct page *page, unsigned int order)
1240 {
1241         unsigned int nr_pages = 1 << order;
1242         struct page *p = page;
1243         unsigned int loop;
1244
1245         prefetchw(p);
1246         for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
1247                 prefetchw(p + 1);
1248                 __ClearPageReserved(p);
1249                 set_page_count(p, 0);
1250         }
1251         __ClearPageReserved(p);
1252         set_page_count(p, 0);
1253
1254         page_zone(page)->managed_pages += nr_pages;
1255         set_page_refcounted(page);
1256         __free_pages(page, order);
1257 }
1258
1259 #if defined(CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID) || \
1260         defined(CONFIG_HAVE_MEMBLOCK_NODE_MAP)
1261
1262 static struct mminit_pfnnid_cache early_pfnnid_cache __meminitdata;
1263
1264 int __meminit early_pfn_to_nid(unsigned long pfn)
1265 {
1266         static DEFINE_SPINLOCK(early_pfn_lock);
1267         int nid;
1268
1269         spin_lock(&early_pfn_lock);
1270         nid = __early_pfn_to_nid(pfn, &early_pfnnid_cache);
1271         if (nid < 0)
1272                 nid = first_online_node;
1273         spin_unlock(&early_pfn_lock);
1274
1275         return nid;
1276 }
1277 #endif
1278
1279 #ifdef CONFIG_NODES_SPAN_OTHER_NODES
1280 static inline bool __meminit __maybe_unused
1281 meminit_pfn_in_nid(unsigned long pfn, int node,
1282                    struct mminit_pfnnid_cache *state)
1283 {
1284         int nid;
1285
1286         nid = __early_pfn_to_nid(pfn, state);
1287         if (nid >= 0 && nid != node)
1288                 return false;
1289         return true;
1290 }
1291
1292 /* Only safe to use early in boot when initialisation is single-threaded */
1293 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1294 {
1295         return meminit_pfn_in_nid(pfn, node, &early_pfnnid_cache);
1296 }
1297
1298 #else
1299
1300 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1301 {
1302         return true;
1303 }
1304 static inline bool __meminit  __maybe_unused
1305 meminit_pfn_in_nid(unsigned long pfn, int node,
1306                    struct mminit_pfnnid_cache *state)
1307 {
1308         return true;
1309 }
1310 #endif
1311
1312
1313 void __init __free_pages_bootmem(struct page *page, unsigned long pfn,
1314                                                         unsigned int order)
1315 {
1316         if (early_page_uninitialised(pfn))
1317                 return;
1318         return __free_pages_boot_core(page, order);
1319 }
1320
1321 /*
1322  * Check that the whole (or subset of) a pageblock given by the interval of
1323  * [start_pfn, end_pfn) is valid and within the same zone, before scanning it
1324  * with the migration of free compaction scanner. The scanners then need to
1325  * use only pfn_valid_within() check for arches that allow holes within
1326  * pageblocks.
1327  *
1328  * Return struct page pointer of start_pfn, or NULL if checks were not passed.
1329  *
1330  * It's possible on some configurations to have a setup like node0 node1 node0
1331  * i.e. it's possible that all pages within a zones range of pages do not
1332  * belong to a single zone. We assume that a border between node0 and node1
1333  * can occur within a single pageblock, but not a node0 node1 node0
1334  * interleaving within a single pageblock. It is therefore sufficient to check
1335  * the first and last page of a pageblock and avoid checking each individual
1336  * page in a pageblock.
1337  */
1338 struct page *__pageblock_pfn_to_page(unsigned long start_pfn,
1339                                      unsigned long end_pfn, struct zone *zone)
1340 {
1341         struct page *start_page;
1342         struct page *end_page;
1343
1344         /* end_pfn is one past the range we are checking */
1345         end_pfn--;
1346
1347         if (!pfn_valid(start_pfn) || !pfn_valid(end_pfn))
1348                 return NULL;
1349
1350         start_page = pfn_to_online_page(start_pfn);
1351         if (!start_page)
1352                 return NULL;
1353
1354         if (page_zone(start_page) != zone)
1355                 return NULL;
1356
1357         end_page = pfn_to_page(end_pfn);
1358
1359         /* This gives a shorter code than deriving page_zone(end_page) */
1360         if (page_zone_id(start_page) != page_zone_id(end_page))
1361                 return NULL;
1362
1363         return start_page;
1364 }
1365
1366 void set_zone_contiguous(struct zone *zone)
1367 {
1368         unsigned long block_start_pfn = zone->zone_start_pfn;
1369         unsigned long block_end_pfn;
1370
1371         block_end_pfn = ALIGN(block_start_pfn + 1, pageblock_nr_pages);
1372         for (; block_start_pfn < zone_end_pfn(zone);
1373                         block_start_pfn = block_end_pfn,
1374                          block_end_pfn += pageblock_nr_pages) {
1375
1376                 block_end_pfn = min(block_end_pfn, zone_end_pfn(zone));
1377
1378                 if (!__pageblock_pfn_to_page(block_start_pfn,
1379                                              block_end_pfn, zone))
1380                         return;
1381         }
1382
1383         /* We confirm that there is no hole */
1384         zone->contiguous = true;
1385 }
1386
1387 void clear_zone_contiguous(struct zone *zone)
1388 {
1389         zone->contiguous = false;
1390 }
1391
1392 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1393 static void __init deferred_free_range(unsigned long pfn,
1394                                        unsigned long nr_pages)
1395 {
1396         struct page *page;
1397         unsigned long i;
1398
1399         if (!nr_pages)
1400                 return;
1401
1402         page = pfn_to_page(pfn);
1403
1404         /* Free a large naturally-aligned chunk if possible */
1405         if (nr_pages == pageblock_nr_pages &&
1406             (pfn & (pageblock_nr_pages - 1)) == 0) {
1407                 set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1408                 __free_pages_boot_core(page, pageblock_order);
1409                 return;
1410         }
1411
1412         for (i = 0; i < nr_pages; i++, page++, pfn++) {
1413                 if ((pfn & (pageblock_nr_pages - 1)) == 0)
1414                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
1415                 __free_pages_boot_core(page, 0);
1416         }
1417 }
1418
1419 /* Completion tracking for deferred_init_memmap() threads */
1420 static atomic_t pgdat_init_n_undone __initdata;
1421 static __initdata DECLARE_COMPLETION(pgdat_init_all_done_comp);
1422
1423 static inline void __init pgdat_init_report_one_done(void)
1424 {
1425         if (atomic_dec_and_test(&pgdat_init_n_undone))
1426                 complete(&pgdat_init_all_done_comp);
1427 }
1428
1429 /*
1430  * Returns true if page needs to be initialized or freed to buddy allocator.
1431  *
1432  * First we check if pfn is valid on architectures where it is possible to have
1433  * holes within pageblock_nr_pages. On systems where it is not possible, this
1434  * function is optimized out.
1435  *
1436  * Then, we check if a current large page is valid by only checking the validity
1437  * of the head pfn.
1438  *
1439  * Finally, meminit_pfn_in_nid is checked on systems where pfns can interleave
1440  * within a node: a pfn is between start and end of a node, but does not belong
1441  * to this memory node.
1442  */
1443 static inline bool __init
1444 deferred_pfn_valid(int nid, unsigned long pfn,
1445                    struct mminit_pfnnid_cache *nid_init_state)
1446 {
1447         if (!pfn_valid_within(pfn))
1448                 return false;
1449         if (!(pfn & (pageblock_nr_pages - 1)) && !pfn_valid(pfn))
1450                 return false;
1451         if (!meminit_pfn_in_nid(pfn, nid, nid_init_state))
1452                 return false;
1453         return true;
1454 }
1455
1456 /*
1457  * Free pages to buddy allocator. Try to free aligned pages in
1458  * pageblock_nr_pages sizes.
1459  */
1460 static void __init deferred_free_pages(int nid, int zid, unsigned long pfn,
1461                                        unsigned long end_pfn)
1462 {
1463         struct mminit_pfnnid_cache nid_init_state = { };
1464         unsigned long nr_pgmask = pageblock_nr_pages - 1;
1465         unsigned long nr_free = 0;
1466
1467         for (; pfn < end_pfn; pfn++) {
1468                 if (!deferred_pfn_valid(nid, pfn, &nid_init_state)) {
1469                         deferred_free_range(pfn - nr_free, nr_free);
1470                         nr_free = 0;
1471                 } else if (!(pfn & nr_pgmask)) {
1472                         deferred_free_range(pfn - nr_free, nr_free);
1473                         nr_free = 1;
1474                         touch_nmi_watchdog();
1475                 } else {
1476                         nr_free++;
1477                 }
1478         }
1479         /* Free the last block of pages to allocator */
1480         deferred_free_range(pfn - nr_free, nr_free);
1481 }
1482
1483 /*
1484  * Initialize struct pages.  We minimize pfn page lookups and scheduler checks
1485  * by performing it only once every pageblock_nr_pages.
1486  * Return number of pages initialized.
1487  */
1488 static unsigned long  __init deferred_init_pages(int nid, int zid,
1489                                                  unsigned long pfn,
1490                                                  unsigned long end_pfn)
1491 {
1492         struct mminit_pfnnid_cache nid_init_state = { };
1493         unsigned long nr_pgmask = pageblock_nr_pages - 1;
1494         unsigned long nr_pages = 0;
1495         struct page *page = NULL;
1496
1497         for (; pfn < end_pfn; pfn++) {
1498                 if (!deferred_pfn_valid(nid, pfn, &nid_init_state)) {
1499                         page = NULL;
1500                         continue;
1501                 } else if (!page || !(pfn & nr_pgmask)) {
1502                         page = pfn_to_page(pfn);
1503                         touch_nmi_watchdog();
1504                 } else {
1505                         page++;
1506                 }
1507                 __init_single_page(page, pfn, zid, nid);
1508                 nr_pages++;
1509         }
1510         return (nr_pages);
1511 }
1512
1513 /* Initialise remaining memory on a node */
1514 static int __init deferred_init_memmap(void *data)
1515 {
1516         pg_data_t *pgdat = data;
1517         int nid = pgdat->node_id;
1518         unsigned long start = jiffies;
1519         unsigned long nr_pages = 0;
1520         unsigned long spfn, epfn, first_init_pfn, flags;
1521         phys_addr_t spa, epa;
1522         int zid;
1523         struct zone *zone;
1524         const struct cpumask *cpumask = cpumask_of_node(pgdat->node_id);
1525         u64 i;
1526
1527         /* Bind memory initialisation thread to a local node if possible */
1528         if (!cpumask_empty(cpumask))
1529                 set_cpus_allowed_ptr(current, cpumask);
1530
1531         pgdat_resize_lock(pgdat, &flags);
1532         first_init_pfn = pgdat->first_deferred_pfn;
1533         if (first_init_pfn == ULONG_MAX) {
1534                 pgdat_resize_unlock(pgdat, &flags);
1535                 pgdat_init_report_one_done();
1536                 return 0;
1537         }
1538
1539         /* Sanity check boundaries */
1540         BUG_ON(pgdat->first_deferred_pfn < pgdat->node_start_pfn);
1541         BUG_ON(pgdat->first_deferred_pfn > pgdat_end_pfn(pgdat));
1542         pgdat->first_deferred_pfn = ULONG_MAX;
1543
1544         /* Only the highest zone is deferred so find it */
1545         for (zid = 0; zid < MAX_NR_ZONES; zid++) {
1546                 zone = pgdat->node_zones + zid;
1547                 if (first_init_pfn < zone_end_pfn(zone))
1548                         break;
1549         }
1550         first_init_pfn = max(zone->zone_start_pfn, first_init_pfn);
1551
1552         /*
1553          * Initialize and free pages. We do it in two loops: first we initialize
1554          * struct page, than free to buddy allocator, because while we are
1555          * freeing pages we can access pages that are ahead (computing buddy
1556          * page in __free_one_page()).
1557          */
1558         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1559                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1560                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1561                 nr_pages += deferred_init_pages(nid, zid, spfn, epfn);
1562         }
1563         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1564                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1565                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1566                 deferred_free_pages(nid, zid, spfn, epfn);
1567         }
1568         pgdat_resize_unlock(pgdat, &flags);
1569
1570         /* Sanity check that the next zone really is unpopulated */
1571         WARN_ON(++zid < MAX_NR_ZONES && populated_zone(++zone));
1572
1573         pr_info("node %d initialised, %lu pages in %ums\n", nid, nr_pages,
1574                                         jiffies_to_msecs(jiffies - start));
1575
1576         pgdat_init_report_one_done();
1577         return 0;
1578 }
1579
1580 /*
1581  * During boot we initialize deferred pages on-demand, as needed, but once
1582  * page_alloc_init_late() has finished, the deferred pages are all initialized,
1583  * and we can permanently disable that path.
1584  */
1585 static DEFINE_STATIC_KEY_TRUE(deferred_pages);
1586
1587 /*
1588  * If this zone has deferred pages, try to grow it by initializing enough
1589  * deferred pages to satisfy the allocation specified by order, rounded up to
1590  * the nearest PAGES_PER_SECTION boundary.  So we're adding memory in increments
1591  * of SECTION_SIZE bytes by initializing struct pages in increments of
1592  * PAGES_PER_SECTION * sizeof(struct page) bytes.
1593  *
1594  * Return true when zone was grown, otherwise return false. We return true even
1595  * when we grow less than requested, to let the caller decide if there are
1596  * enough pages to satisfy the allocation.
1597  *
1598  * Note: We use noinline because this function is needed only during boot, and
1599  * it is called from a __ref function _deferred_grow_zone. This way we are
1600  * making sure that it is not inlined into permanent text section.
1601  */
1602 static noinline bool __init
1603 deferred_grow_zone(struct zone *zone, unsigned int order)
1604 {
1605         int zid = zone_idx(zone);
1606         int nid = zone_to_nid(zone);
1607         pg_data_t *pgdat = NODE_DATA(nid);
1608         unsigned long nr_pages_needed = ALIGN(1 << order, PAGES_PER_SECTION);
1609         unsigned long nr_pages = 0;
1610         unsigned long first_init_pfn, spfn, epfn, t, flags;
1611         unsigned long first_deferred_pfn = pgdat->first_deferred_pfn;
1612         phys_addr_t spa, epa;
1613         u64 i;
1614
1615         /* Only the last zone may have deferred pages */
1616         if (zone_end_pfn(zone) != pgdat_end_pfn(pgdat))
1617                 return false;
1618
1619         pgdat_resize_lock(pgdat, &flags);
1620
1621         /*
1622          * If deferred pages have been initialized while we were waiting for
1623          * the lock, return true, as the zone was grown.  The caller will retry
1624          * this zone.  We won't return to this function since the caller also
1625          * has this static branch.
1626          */
1627         if (!static_branch_unlikely(&deferred_pages)) {
1628                 pgdat_resize_unlock(pgdat, &flags);
1629                 return true;
1630         }
1631
1632         /*
1633          * If someone grew this zone while we were waiting for spinlock, return
1634          * true, as there might be enough pages already.
1635          */
1636         if (first_deferred_pfn != pgdat->first_deferred_pfn) {
1637                 pgdat_resize_unlock(pgdat, &flags);
1638                 return true;
1639         }
1640
1641         first_init_pfn = max(zone->zone_start_pfn, first_deferred_pfn);
1642
1643         if (first_init_pfn >= pgdat_end_pfn(pgdat)) {
1644                 pgdat_resize_unlock(pgdat, &flags);
1645                 return false;
1646         }
1647
1648         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1649                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1650                 epfn = min_t(unsigned long, zone_end_pfn(zone), PFN_DOWN(epa));
1651
1652                 while (spfn < epfn && nr_pages < nr_pages_needed) {
1653                         t = ALIGN(spfn + PAGES_PER_SECTION, PAGES_PER_SECTION);
1654                         first_deferred_pfn = min(t, epfn);
1655                         nr_pages += deferred_init_pages(nid, zid, spfn,
1656                                                         first_deferred_pfn);
1657                         spfn = first_deferred_pfn;
1658                 }
1659
1660                 if (nr_pages >= nr_pages_needed)
1661                         break;
1662         }
1663
1664         for_each_free_mem_range(i, nid, MEMBLOCK_NONE, &spa, &epa, NULL) {
1665                 spfn = max_t(unsigned long, first_init_pfn, PFN_UP(spa));
1666                 epfn = min_t(unsigned long, first_deferred_pfn, PFN_DOWN(epa));
1667                 deferred_free_pages(nid, zid, spfn, epfn);
1668
1669                 if (first_deferred_pfn == epfn)
1670                         break;
1671         }
1672         pgdat->first_deferred_pfn = first_deferred_pfn;
1673         pgdat_resize_unlock(pgdat, &flags);
1674
1675         return nr_pages > 0;
1676 }
1677
1678 /*
1679  * deferred_grow_zone() is __init, but it is called from
1680  * get_page_from_freelist() during early boot until deferred_pages permanently
1681  * disables this call. This is why we have refdata wrapper to avoid warning,
1682  * and to ensure that the function body gets unloaded.
1683  */
1684 static bool __ref
1685 _deferred_grow_zone(struct zone *zone, unsigned int order)
1686 {
1687         return deferred_grow_zone(zone, order);
1688 }
1689
1690 #endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
1691
1692 void __init page_alloc_init_late(void)
1693 {
1694         struct zone *zone;
1695
1696 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1697         int nid;
1698
1699         /* There will be num_node_state(N_MEMORY) threads */
1700         atomic_set(&pgdat_init_n_undone, num_node_state(N_MEMORY));
1701         for_each_node_state(nid, N_MEMORY) {
1702                 kthread_run(deferred_init_memmap, NODE_DATA(nid), "pgdatinit%d", nid);
1703         }
1704
1705         /* Block until all are initialised */
1706         wait_for_completion(&pgdat_init_all_done_comp);
1707
1708         /*
1709          * We initialized the rest of the deferred pages.  Permanently disable
1710          * on-demand struct page initialization.
1711          */
1712         static_branch_disable(&deferred_pages);
1713
1714         /* Reinit limits that are based on free pages after the kernel is up */
1715         files_maxfiles_init();
1716 #endif
1717 #ifdef CONFIG_ARCH_DISCARD_MEMBLOCK
1718         /* Discard memblock private memory */
1719         memblock_discard();
1720 #endif
1721
1722         for_each_populated_zone(zone)
1723                 set_zone_contiguous(zone);
1724 }
1725
1726 #ifdef CONFIG_CMA
1727 /* Free whole pageblock and set its migration type to MIGRATE_CMA. */
1728 void __init init_cma_reserved_pageblock(struct page *page)
1729 {
1730         unsigned i = pageblock_nr_pages;
1731         struct page *p = page;
1732
1733         do {
1734                 __ClearPageReserved(p);
1735                 set_page_count(p, 0);
1736         } while (++p, --i);
1737
1738         set_pageblock_migratetype(page, MIGRATE_CMA);
1739
1740         if (pageblock_order >= MAX_ORDER) {
1741                 i = pageblock_nr_pages;
1742                 p = page;
1743                 do {
1744                         set_page_refcounted(p);
1745                         __free_pages(p, MAX_ORDER - 1);
1746                         p += MAX_ORDER_NR_PAGES;
1747                 } while (i -= MAX_ORDER_NR_PAGES);
1748         } else {
1749                 set_page_refcounted(page);
1750                 __free_pages(page, pageblock_order);
1751         }
1752
1753         adjust_managed_page_count(page, pageblock_nr_pages);
1754 }
1755 #endif
1756
1757 /*
1758  * The order of subdivision here is critical for the IO subsystem.
1759  * Please do not alter this order without good reasons and regression
1760  * testing. Specifically, as large blocks of memory are subdivided,
1761  * the order in which smaller blocks are delivered depends on the order
1762  * they're subdivided in this function. This is the primary factor
1763  * influencing the order in which pages are delivered to the IO
1764  * subsystem according to empirical testing, and this is also justified
1765  * by considering the behavior of a buddy system containing a single
1766  * large block of memory acted on by a series of small allocations.
1767  * This behavior is a critical factor in sglist merging's success.
1768  *
1769  * -- nyc
1770  */
1771 static inline void expand(struct zone *zone, struct page *page,
1772         int low, int high, struct free_area *area,
1773         int migratetype)
1774 {
1775         unsigned long size = 1 << high;
1776
1777         while (high > low) {
1778                 area--;
1779                 high--;
1780                 size >>= 1;
1781                 VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);
1782
1783                 /*
1784                  * Mark as guard pages (or page), that will allow to
1785                  * merge back to allocator when buddy will be freed.
1786                  * Corresponding page table entries will not be touched,
1787                  * pages will stay not present in virtual address space
1788                  */
1789                 if (set_page_guard(zone, &page[size], high, migratetype))
1790                         continue;
1791
1792                 list_add(&page[size].lru, &area->free_list[migratetype]);
1793                 area->nr_free++;
1794                 set_page_order(&page[size], high);
1795         }
1796 }
1797
1798 static void check_new_page_bad(struct page *page)
1799 {
1800         const char *bad_reason = NULL;
1801         unsigned long bad_flags = 0;
1802
1803         if (unlikely(atomic_read(&page->_mapcount) != -1))
1804                 bad_reason = "nonzero mapcount";
1805         if (unlikely(page->mapping != NULL))
1806                 bad_reason = "non-NULL mapping";
1807         if (unlikely(page_ref_count(page) != 0))
1808                 bad_reason = "nonzero _count";
1809         if (unlikely(page->flags & __PG_HWPOISON)) {
1810                 bad_reason = "HWPoisoned (hardware-corrupted)";
1811                 bad_flags = __PG_HWPOISON;
1812                 /* Don't complain about hwpoisoned pages */
1813                 page_mapcount_reset(page); /* remove PageBuddy */
1814                 return;
1815         }
1816         if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_PREP)) {
1817                 bad_reason = "PAGE_FLAGS_CHECK_AT_PREP flag set";
1818                 bad_flags = PAGE_FLAGS_CHECK_AT_PREP;
1819         }
1820 #ifdef CONFIG_MEMCG
1821         if (unlikely(page->mem_cgroup))
1822                 bad_reason = "page still charged to cgroup";
1823 #endif
1824         bad_page(page, bad_reason, bad_flags);
1825 }
1826
1827 /*
1828  * This page is about to be returned from the page allocator
1829  */
1830 static inline int check_new_page(struct page *page)
1831 {
1832         if (likely(page_expected_state(page,
1833                                 PAGE_FLAGS_CHECK_AT_PREP|__PG_HWPOISON)))
1834                 return 0;
1835
1836         check_new_page_bad(page);
1837         return 1;
1838 }
1839
1840 static inline bool free_pages_prezeroed(void)
1841 {
1842         return IS_ENABLED(CONFIG_PAGE_POISONING_ZERO) &&
1843                 page_poisoning_enabled();
1844 }
1845
1846 #ifdef CONFIG_DEBUG_VM
1847 static bool check_pcp_refill(struct page *page)
1848 {
1849         return false;
1850 }
1851
1852 static bool check_new_pcp(struct page *page)
1853 {
1854         return check_new_page(page);
1855 }
1856 #else
1857 static bool check_pcp_refill(struct page *page)
1858 {
1859         return check_new_page(page);
1860 }
1861 static bool check_new_pcp(struct page *page)
1862 {
1863         return false;
1864 }
1865 #endif /* CONFIG_DEBUG_VM */
1866
1867 static bool check_new_pages(struct page *page, unsigned int order)
1868 {
1869         int i;
1870         for (i = 0; i < (1 << order); i++) {
1871                 struct page *p = page + i;
1872
1873                 if (unlikely(check_new_page(p)))
1874                         return true;
1875         }
1876
1877         return false;
1878 }
1879
1880 inline void post_alloc_hook(struct page *page, unsigned int order,
1881                                 gfp_t gfp_flags)
1882 {
1883         set_page_private(page, 0);
1884         set_page_refcounted(page);
1885
1886         arch_alloc_page(page, order);
1887         kernel_map_pages(page, 1 << order, 1);
1888         kernel_poison_pages(page, 1 << order, 1);
1889         kasan_alloc_pages(page, order);
1890         set_page_owner(page, order, gfp_flags);
1891 }
1892
1893 static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags,
1894                                                         unsigned int alloc_flags)
1895 {
1896         int i;
1897
1898         post_alloc_hook(page, order, gfp_flags);
1899
1900         if (!free_pages_prezeroed() && (gfp_flags & __GFP_ZERO))
1901                 for (i = 0; i < (1 << order); i++)
1902                         clear_highpage(page + i);
1903
1904         if (order && (gfp_flags & __GFP_COMP))
1905                 prep_compound_page(page, order);
1906
1907         /*
1908          * page is set pfmemalloc when ALLOC_NO_WATERMARKS was necessary to
1909          * allocate the page. The expectation is that the caller is taking
1910          * steps that will free more memory. The caller should avoid the page
1911          * being used for !PFMEMALLOC purposes.
1912          */
1913         if (alloc_flags & ALLOC_NO_WATERMARKS)
1914                 set_page_pfmemalloc(page);
1915         else
1916                 clear_page_pfmemalloc(page);
1917 }
1918
1919 /*
1920  * Go through the free lists for the given migratetype and remove
1921  * the smallest available page from the freelists
1922  */
1923 static __always_inline
1924 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
1925                                                 int migratetype)
1926 {
1927         unsigned int current_order;
1928         struct free_area *area;
1929         struct page *page;
1930
1931         /* Find a page of the appropriate size in the preferred list */
1932         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
1933                 area = &(zone->free_area[current_order]);
1934                 page = list_first_entry_or_null(&area->free_list[migratetype],
1935                                                         struct page, lru);
1936                 if (!page)
1937                         continue;
1938                 list_del(&page->lru);
1939                 rmv_page_order(page);
1940                 area->nr_free--;
1941                 expand(zone, page, order, current_order, area, migratetype);
1942                 set_pcppage_migratetype(page, migratetype);
1943                 return page;
1944         }
1945
1946         return NULL;
1947 }
1948
1949
1950 /*
1951  * This array describes the order lists are fallen back to when
1952  * the free lists for the desirable migrate type are depleted
1953  */
1954 static int fallbacks[MIGRATE_TYPES][4] = {
1955         [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
1956         [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
1957         [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
1958 #ifdef CONFIG_CMA
1959         [MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
1960 #endif
1961 #ifdef CONFIG_MEMORY_ISOLATION
1962         [MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
1963 #endif
1964 };
1965
1966 #ifdef CONFIG_CMA
1967 static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1968                                         unsigned int order)
1969 {
1970         return __rmqueue_smallest(zone, order, MIGRATE_CMA);
1971 }
1972 #else
1973 static inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1974                                         unsigned int order) { return NULL; }
1975 #endif
1976
1977 /*
1978  * Move the free pages in a range to the free lists of the requested type.
1979  * Note that start_page and end_pages are not aligned on a pageblock
1980  * boundary. If alignment is required, use move_freepages_block()
1981  */
1982 static int move_freepages(struct zone *zone,
1983                           struct page *start_page, struct page *end_page,
1984                           int migratetype, int *num_movable)
1985 {
1986         struct page *page;
1987         unsigned int order;
1988         int pages_moved = 0;
1989
1990 #ifndef CONFIG_HOLES_IN_ZONE
1991         /*
1992          * page_zone is not safe to call in this context when
1993          * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
1994          * anyway as we check zone boundaries in move_freepages_block().
1995          * Remove at a later date when no bug reports exist related to
1996          * grouping pages by mobility
1997          */
1998         VM_BUG_ON(pfn_valid(page_to_pfn(start_page)) &&
1999                   pfn_valid(page_to_pfn(end_page)) &&
2000                   page_zone(start_page) != page_zone(end_page));
2001 #endif
2002
2003         if (num_movable)
2004                 *num_movable = 0;
2005
2006         for (page = start_page; page <= end_page;) {
2007                 if (!pfn_valid_within(page_to_pfn(page))) {
2008                         page++;
2009                         continue;
2010                 }
2011
2012                 /* Make sure we are not inadvertently changing nodes */
2013                 VM_BUG_ON_PAGE(page_to_nid(page) != zone_to_nid(zone), page);
2014
2015                 if (!PageBuddy(page)) {
2016                         /*
2017                          * We assume that pages that could be isolated for
2018                          * migration are movable. But we don't actually try
2019                          * isolating, as that would be expensive.
2020                          */
2021                         if (num_movable &&
2022                                         (PageLRU(page) || __PageMovable(page)))
2023                                 (*num_movable)++;
2024
2025                         page++;
2026                         continue;
2027                 }
2028
2029                 order = page_order(page);
2030                 list_move(&page->lru,
2031                           &zone->free_area[order].free_list[migratetype]);
2032                 page += 1 << order;
2033                 pages_moved += 1 << order;
2034         }
2035
2036         return pages_moved;
2037 }
2038
2039 int move_freepages_block(struct zone *zone, struct page *page,
2040                                 int migratetype, int *num_movable)
2041 {
2042         unsigned long start_pfn, end_pfn;
2043         struct page *start_page, *end_page;
2044
2045         start_pfn = page_to_pfn(page);
2046         start_pfn = start_pfn & ~(pageblock_nr_pages-1);
2047         start_page = pfn_to_page(start_pfn);
2048         end_page = start_page + pageblock_nr_pages - 1;
2049         end_pfn = start_pfn + pageblock_nr_pages - 1;
2050
2051         /* Do not cross zone boundaries */
2052         if (!zone_spans_pfn(zone, start_pfn))
2053                 start_page = page;
2054         if (!zone_spans_pfn(zone, end_pfn))
2055                 return 0;
2056
2057         return move_freepages(zone, start_page, end_page, migratetype,
2058                                                                 num_movable);
2059 }
2060
2061 static void change_pageblock_range(struct page *pageblock_page,
2062                                         int start_order, int migratetype)
2063 {
2064         int nr_pageblocks = 1 << (start_order - pageblock_order);
2065
2066         while (nr_pageblocks--) {
2067                 set_pageblock_migratetype(pageblock_page, migratetype);
2068                 pageblock_page += pageblock_nr_pages;
2069         }
2070 }
2071
2072 /*
2073  * When we are falling back to another migratetype during allocation, try to
2074  * steal extra free pages from the same pageblocks to satisfy further
2075  * allocations, instead of polluting multiple pageblocks.
2076  *
2077  * If we are stealing a relatively large buddy page, it is likely there will
2078  * be more free pages in the pageblock, so try to steal them all. For
2079  * reclaimable and unmovable allocations, we steal regardless of page size,
2080  * as fragmentation caused by those allocations polluting movable pageblocks
2081  * is worse than movable allocations stealing from unmovable and reclaimable
2082  * pageblocks.
2083  */
2084 static bool can_steal_fallback(unsigned int order, int start_mt)
2085 {
2086         /*
2087          * Leaving this order check is intended, although there is
2088          * relaxed order check in next check. The reason is that
2089          * we can actually steal whole pageblock if this condition met,
2090          * but, below check doesn't guarantee it and that is just heuristic
2091          * so could be changed anytime.
2092          */
2093         if (order >= pageblock_order)
2094                 return true;
2095
2096         if (order >= pageblock_order / 2 ||
2097                 start_mt == MIGRATE_RECLAIMABLE ||
2098                 start_mt == MIGRATE_UNMOVABLE ||
2099                 page_group_by_mobility_disabled)
2100                 return true;
2101
2102         return false;
2103 }
2104
2105 /*
2106  * This function implements actual steal behaviour. If order is large enough,
2107  * we can steal whole pageblock. If not, we first move freepages in this
2108  * pageblock to our migratetype and determine how many already-allocated pages
2109  * are there in the pageblock with a compatible migratetype. If at least half
2110  * of pages are free or compatible, we can change migratetype of the pageblock
2111  * itself, so pages freed in the future will be put on the correct free list.
2112  */
2113 static void steal_suitable_fallback(struct zone *zone, struct page *page,
2114                                         int start_type, bool whole_block)
2115 {
2116         unsigned int current_order = page_order(page);
2117         struct free_area *area;
2118         int free_pages, movable_pages, alike_pages;
2119         int old_block_type;
2120
2121         old_block_type = get_pageblock_migratetype(page);
2122
2123         /*
2124          * This can happen due to races and we want to prevent broken
2125          * highatomic accounting.
2126          */
2127         if (is_migrate_highatomic(old_block_type))
2128                 goto single_page;
2129
2130         /* Take ownership for orders >= pageblock_order */
2131         if (current_order >= pageblock_order) {
2132                 change_pageblock_range(page, current_order, start_type);
2133                 goto single_page;
2134         }
2135
2136         /* We are not allowed to try stealing from the whole block */
2137         if (!whole_block)
2138                 goto single_page;
2139
2140         free_pages = move_freepages_block(zone, page, start_type,
2141                                                 &movable_pages);
2142         /*
2143          * Determine how many pages are compatible with our allocation.
2144          * For movable allocation, it's the number of movable pages which
2145          * we just obtained. For other types it's a bit more tricky.
2146          */
2147         if (start_type == MIGRATE_MOVABLE) {
2148                 alike_pages = movable_pages;
2149         } else {
2150                 /*
2151                  * If we are falling back a RECLAIMABLE or UNMOVABLE allocation
2152                  * to MOVABLE pageblock, consider all non-movable pages as
2153                  * compatible. If it's UNMOVABLE falling back to RECLAIMABLE or
2154                  * vice versa, be conservative since we can't distinguish the
2155                  * exact migratetype of non-movable pages.
2156                  */
2157                 if (old_block_type == MIGRATE_MOVABLE)
2158                         alike_pages = pageblock_nr_pages
2159                                                 - (free_pages + movable_pages);
2160                 else
2161                         alike_pages = 0;
2162         }
2163
2164         /* moving whole block can fail due to zone boundary conditions */
2165         if (!free_pages)
2166                 goto single_page;
2167
2168         /*
2169          * If a sufficient number of pages in the block are either free or of
2170          * comparable migratability as our allocation, claim the whole block.
2171          */
2172         if (free_pages + alike_pages >= (1 << (pageblock_order-1)) ||
2173                         page_group_by_mobility_disabled)
2174                 set_pageblock_migratetype(page, start_type);
2175
2176         return;
2177
2178 single_page:
2179         area = &zone->free_area[current_order];
2180         list_move(&page->lru, &area->free_list[start_type]);
2181 }
2182
2183 /*
2184  * Check whether there is a suitable fallback freepage with requested order.
2185  * If only_stealable is true, this function returns fallback_mt only if
2186  * we can steal other freepages all together. This would help to reduce
2187  * fragmentation due to mixed migratetype pages in one pageblock.
2188  */
2189 int find_suitable_fallback(struct free_area *area, unsigned int order,
2190                         int migratetype, bool only_stealable, bool *can_steal)
2191 {
2192         int i;
2193         int fallback_mt;
2194
2195         if (area->nr_free == 0)
2196                 return -1;
2197
2198         *can_steal = false;
2199         for (i = 0;; i++) {
2200                 fallback_mt = fallbacks[migratetype][i];
2201                 if (fallback_mt == MIGRATE_TYPES)
2202                         break;
2203
2204                 if (list_empty(&area->free_list[fallback_mt]))
2205                         continue;
2206
2207                 if (can_steal_fallback(order, migratetype))
2208                         *can_steal = true;
2209
2210                 if (!only_stealable)
2211                         return fallback_mt;
2212
2213                 if (*can_steal)
2214                         return fallback_mt;
2215         }
2216
2217         return -1;
2218 }
2219
2220 /*
2221  * Reserve a pageblock for exclusive use of high-order atomic allocations if
2222  * there are no empty page blocks that contain a page with a suitable order
2223  */
2224 static void reserve_highatomic_pageblock(struct page *page, struct zone *zone,
2225                                 unsigned int alloc_order)
2226 {
2227         int mt;
2228         unsigned long max_managed, flags;
2229
2230         /*
2231          * Limit the number reserved to 1 pageblock or roughly 1% of a zone.
2232          * Check is race-prone but harmless.
2233          */
2234         max_managed = (zone->managed_pages / 100) + pageblock_nr_pages;
2235         if (zone->nr_reserved_highatomic >= max_managed)
2236                 return;
2237
2238         spin_lock_irqsave(&zone->lock, flags);
2239
2240         /* Recheck the nr_reserved_highatomic limit under the lock */
2241         if (zone->nr_reserved_highatomic >= max_managed)
2242                 goto out_unlock;
2243
2244         /* Yoink! */
2245         mt = get_pageblock_migratetype(page);
2246         if (!is_migrate_highatomic(mt) && !is_migrate_isolate(mt)
2247             && !is_migrate_cma(mt)) {
2248                 zone->nr_reserved_highatomic += pageblock_nr_pages;
2249                 set_pageblock_migratetype(page, MIGRATE_HIGHATOMIC);
2250                 move_freepages_block(zone, page, MIGRATE_HIGHATOMIC, NULL);
2251         }
2252
2253 out_unlock:
2254         spin_unlock_irqrestore(&zone->lock, flags);
2255 }
2256
2257 /*
2258  * Used when an allocation is about to fail under memory pressure. This
2259  * potentially hurts the reliability of high-order allocations when under
2260  * intense memory pressure but failed atomic allocations should be easier
2261  * to recover from than an OOM.
2262  *
2263  * If @force is true, try to unreserve a pageblock even though highatomic
2264  * pageblock is exhausted.
2265  */
2266 static bool unreserve_highatomic_pageblock(const struct alloc_context *ac,
2267                                                 bool force)
2268 {
2269         struct zonelist *zonelist = ac->zonelist;
2270         unsigned long flags;
2271         struct zoneref *z;
2272         struct zone *zone;
2273         struct page *page;
2274         int order;
2275         bool ret;
2276
2277         for_each_zone_zonelist_nodemask(zone, z, zonelist, ac->high_zoneidx,
2278                                                                 ac->nodemask) {
2279                 /*
2280                  * Preserve at least one pageblock unless memory pressure
2281                  * is really high.
2282                  */
2283                 if (!force && zone->nr_reserved_highatomic <=
2284                                         pageblock_nr_pages)
2285                         continue;
2286
2287                 spin_lock_irqsave(&zone->lock, flags);
2288                 for (order = 0; order < MAX_ORDER; order++) {
2289                         struct free_area *area = &(zone->free_area[order]);
2290
2291                         page = list_first_entry_or_null(
2292                                         &area->free_list[MIGRATE_HIGHATOMIC],
2293                                         struct page, lru);
2294                         if (!page)
2295                                 continue;
2296
2297                         /*
2298                          * In page freeing path, migratetype change is racy so
2299                          * we can counter several free pages in a pageblock
2300                          * in this loop althoug we changed the pageblock type
2301                          * from highatomic to ac->migratetype. So we should
2302                          * adjust the count once.
2303                          */
2304                         if (is_migrate_highatomic_page(page)) {
2305                                 /*
2306                                  * It should never happen but changes to
2307                                  * locking could inadvertently allow a per-cpu
2308                                  * drain to add pages to MIGRATE_HIGHATOMIC
2309                                  * while unreserving so be safe and watch for
2310                                  * underflows.
2311                                  */
2312                                 zone->nr_reserved_highatomic -= min(
2313                                                 pageblock_nr_pages,
2314                                                 zone->nr_reserved_highatomic);
2315                         }
2316
2317                         /*
2318                          * Convert to ac->migratetype and avoid the normal
2319                          * pageblock stealing heuristics. Minimally, the caller
2320                          * is doing the work and needs the pages. More
2321                          * importantly, if the block was always converted to
2322                          * MIGRATE_UNMOVABLE or another type then the number
2323                          * of pageblocks that cannot be completely freed
2324                          * may increase.
2325                          */
2326                         set_pageblock_migratetype(page, ac->migratetype);
2327                         ret = move_freepages_block(zone, page, ac->migratetype,
2328                                                                         NULL);
2329                         if (ret) {
2330                                 spin_unlock_irqrestore(&zone->lock, flags);
2331                                 return ret;
2332                         }
2333                 }
2334                 spin_unlock_irqrestore(&zone->lock, flags);
2335         }
2336
2337         return false;
2338 }
2339
2340 /*
2341  * Try finding a free buddy page on the fallback list and put it on the free
2342  * list of requested migratetype, possibly along with other pages from the same
2343  * block, depending on fragmentation avoidance heuristics. Returns true if
2344  * fallback was found so that __rmqueue_smallest() can grab it.
2345  *
2346  * The use of signed ints for order and current_order is a deliberate
2347  * deviation from the rest of this file, to make the for loop
2348  * condition simpler.
2349  */
2350 static __always_inline bool
2351 __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
2352 {
2353         struct free_area *area;
2354         int current_order;
2355         struct page *page;
2356         int fallback_mt;
2357         bool can_steal;
2358
2359         /*
2360          * Find the largest available free page in the other list. This roughly
2361          * approximates finding the pageblock with the most free pages, which
2362          * would be too costly to do exactly.
2363          */
2364         for (current_order = MAX_ORDER - 1; current_order >= order;
2365                                 --current_order) {
2366                 area = &(zone->free_area[current_order]);
2367                 fallback_mt = find_suitable_fallback(area, current_order,
2368                                 start_migratetype, false, &can_steal);
2369                 if (fallback_mt == -1)
2370                         continue;
2371
2372                 /*
2373                  * We cannot steal all free pages from the pageblock and the
2374                  * requested migratetype is movable. In that case it's better to
2375                  * steal and split the smallest available page instead of the
2376                  * largest available page, because even if the next movable
2377                  * allocation falls back into a different pageblock than this
2378                  * one, it won't cause permanent fragmentation.
2379                  */
2380                 if (!can_steal && start_migratetype == MIGRATE_MOVABLE
2381                                         && current_order > order)
2382                         goto find_smallest;
2383
2384                 goto do_steal;
2385         }
2386
2387         return false;
2388
2389 find_smallest:
2390         for (current_order = order; current_order < MAX_ORDER;
2391                                                         current_order++) {
2392                 area = &(zone->free_area[current_order]);
2393                 fallback_mt = find_suitable_fallback(area, current_order,
2394                                 start_migratetype, false, &can_steal);
2395                 if (fallback_mt != -1)
2396                         break;
2397         }
2398
2399         /*
2400          * This should not happen - we already found a suitable fallback
2401          * when looking for the largest page.
2402          */
2403         VM_BUG_ON(current_order == MAX_ORDER);
2404
2405 do_steal:
2406         page = list_first_entry(&area->free_list[fallback_mt],
2407                                                         struct page, lru);
2408
2409         steal_suitable_fallback(zone, page, start_migratetype, can_steal);
2410
2411         trace_mm_page_alloc_extfrag(page, order, current_order,
2412                 start_migratetype, fallback_mt);
2413
2414         return true;
2415
2416 }
2417
2418 /*
2419  * Do the hard work of removing an element from the buddy allocator.
2420  * Call me with the zone->lock already held.
2421  */
2422 static __always_inline struct page *
2423 __rmqueue(struct zone *zone, unsigned int order, int migratetype)
2424 {
2425         struct page *page;
2426
2427 retry:
2428         page = __rmqueue_smallest(zone, order, migratetype);
2429         if (unlikely(!page)) {
2430                 if (migratetype == MIGRATE_MOVABLE)
2431                         page = __rmqueue_cma_fallback(zone, order);
2432
2433                 if (!page && __rmqueue_fallback(zone, order, migratetype))
2434                         goto retry;
2435         }
2436
2437         trace_mm_page_alloc_zone_locked(page, order, migratetype);
2438         return page;
2439 }
2440
2441 /*
2442  * Obtain a specified number of elements from the buddy allocator, all under
2443  * a single hold of the lock, for efficiency.  Add them to the supplied list.
2444  * Returns the number of new pages which were placed at *list.
2445  */
2446 static int rmqueue_bulk(struct zone *zone, unsigned int order,
2447                         unsigned long count, struct list_head *list,
2448                         int migratetype)
2449 {
2450         int i, alloced = 0;
2451
2452         spin_lock(&zone->lock);
2453         for (i = 0; i < count; ++i) {
2454                 struct page *page = __rmqueue(zone, order, migratetype);
2455                 if (unlikely(page == NULL))
2456                         break;
2457
2458                 if (unlikely(check_pcp_refill(page)))
2459                         continue;
2460
2461                 /*
2462                  * Split buddy pages returned by expand() are received here in
2463                  * physical page order. The page is added to the tail of
2464                  * caller's list. From the callers perspective, the linked list
2465                  * is ordered by page number under some conditions. This is
2466                  * useful for IO devices that can forward direction from the
2467                  * head, thus also in the physical page order. This is useful
2468                  * for IO devices that can merge IO requests if the physical
2469                  * pages are ordered properly.
2470                  */
2471                 list_add_tail(&page->lru, list);
2472                 alloced++;
2473                 if (is_migrate_cma(get_pcppage_migratetype(page)))
2474                         __mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
2475                                               -(1 << order));
2476         }
2477
2478         /*
2479          * i pages were removed from the buddy list even if some leak due
2480          * to check_pcp_refill failing so adjust NR_FREE_PAGES based
2481          * on i. Do not confuse with 'alloced' which is the number of
2482          * pages added to the pcp list.
2483          */
2484         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
2485         spin_unlock(&zone->lock);
2486         return alloced;
2487 }
2488
2489 #ifdef CONFIG_NUMA
2490 /*
2491  * Called from the vmstat counter updater to drain pagesets of this
2492  * currently executing processor on remote nodes after they have
2493  * expired.
2494  *
2495  * Note that this function must be called with the thread pinned to
2496  * a single processor.
2497  */
2498 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
2499 {
2500         unsigned long flags;
2501         int to_drain, batch;
2502
2503         local_irq_save(flags);
2504         batch = READ_ONCE(pcp->batch);
2505         to_drain = min(pcp->count, batch);
2506         if (to_drain > 0)
2507                 free_pcppages_bulk(zone, to_drain, pcp);
2508         local_irq_restore(flags);
2509 }
2510 #endif
2511
2512 /*
2513  * Drain pcplists of the indicated processor and zone.
2514  *
2515  * The processor must either be the current processor and the
2516  * thread pinned to the current processor or a processor that
2517  * is not online.
2518  */
2519 static void drain_pages_zone(unsigned int cpu, struct zone *zone)
2520 {
2521         unsigned long flags;
2522         struct per_cpu_pageset *pset;
2523         struct per_cpu_pages *pcp;
2524
2525         local_irq_save(flags);
2526         pset = per_cpu_ptr(zone->pageset, cpu);
2527
2528         pcp = &pset->pcp;
2529         if (pcp->count)
2530                 free_pcppages_bulk(zone, pcp->count, pcp);
2531         local_irq_restore(flags);
2532 }
2533
2534 /*
2535  * Drain pcplists of all zones on the indicated processor.
2536  *
2537  * The processor must either be the current processor and the
2538  * thread pinned to the current processor or a processor that
2539  * is not online.
2540  */
2541 static void drain_pages(unsigned int cpu)
2542 {
2543         struct zone *zone;
2544
2545         for_each_populated_zone(zone) {
2546                 drain_pages_zone(cpu, zone);
2547         }
2548 }
2549
2550 /*
2551  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
2552  *
2553  * The CPU has to be pinned. When zone parameter is non-NULL, spill just
2554  * the single zone's pages.
2555  */
2556 void drain_local_pages(struct zone *zone)
2557 {
2558         int cpu = smp_processor_id();
2559
2560         if (zone)
2561                 drain_pages_zone(cpu, zone);
2562         else
2563                 drain_pages(cpu);
2564 }
2565
2566 static void drain_local_pages_wq(struct work_struct *work)
2567 {
2568         /*
2569          * drain_all_pages doesn't use proper cpu hotplug protection so
2570          * we can race with cpu offline when the WQ can move this from
2571          * a cpu pinned worker to an unbound one. We can operate on a different
2572          * cpu which is allright but we also have to make sure to not move to
2573          * a different one.
2574          */
2575         preempt_disable();
2576         drain_local_pages(NULL);
2577         preempt_enable();
2578 }
2579
2580 /*
2581  * Spill all the per-cpu pages from all CPUs back into the buddy allocator.
2582  *
2583  * When zone parameter is non-NULL, spill just the single zone's pages.
2584  *
2585  * Note that this can be extremely slow as the draining happens in a workqueue.
2586  */
2587 void drain_all_pages(struct zone *zone)
2588 {
2589         int cpu;
2590
2591         /*
2592          * Allocate in the BSS so we wont require allocation in
2593          * direct reclaim path for CONFIG_CPUMASK_OFFSTACK=y
2594          */
2595         static cpumask_t cpus_with_pcps;
2596
2597         /*
2598          * Make sure nobody triggers this path before mm_percpu_wq is fully
2599          * initialized.
2600          */
2601         if (WARN_ON_ONCE(!mm_percpu_wq))
2602                 return;
2603
2604         /*
2605          * Do not drain if one is already in progress unless it's specific to
2606          * a zone. Such callers are primarily CMA and memory hotplug and need
2607          * the drain to be complete when the call returns.
2608          */
2609         if (unlikely(!mutex_trylock(&pcpu_drain_mutex))) {
2610                 if (!zone)
2611                         return;
2612                 mutex_lock(&pcpu_drain_mutex);
2613         }
2614
2615         /*
2616          * We don't care about racing with CPU hotplug event
2617          * as offline notification will cause the notified
2618          * cpu to drain that CPU pcps and on_each_cpu_mask
2619          * disables preemption as part of its processing
2620          */
2621         for_each_online_cpu(cpu) {
2622                 struct per_cpu_pageset *pcp;
2623                 struct zone *z;
2624                 bool has_pcps = false;
2625
2626                 if (zone) {
2627                         pcp = per_cpu_ptr(zone->pageset, cpu);
2628                         if (pcp->pcp.count)
2629                                 has_pcps = true;
2630                 } else {
2631                         for_each_populated_zone(z) {
2632                                 pcp = per_cpu_ptr(z->pageset, cpu);
2633                                 if (pcp->pcp.count) {
2634                                         has_pcps = true;
2635                                         break;
2636                                 }
2637                         }
2638                 }
2639
2640                 if (has_pcps)
2641                         cpumask_set_cpu(cpu, &cpus_with_pcps);
2642                 else
2643                         cpumask_clear_cpu(cpu, &cpus_with_pcps);
2644         }
2645
2646         for_each_cpu(cpu, &cpus_with_pcps) {
2647                 struct work_struct *work = per_cpu_ptr(&pcpu_drain, cpu);
2648                 INIT_WORK(work, drain_local_pages_wq);
2649                 queue_work_on(cpu, mm_percpu_wq, work);
2650         }
2651         for_each_cpu(cpu, &cpus_with_pcps)
2652                 flush_work(per_cpu_ptr(&pcpu_drain, cpu));
2653
2654         mutex_unlock(&pcpu_drain_mutex);
2655 }
2656
2657 #ifdef CONFIG_HIBERNATION
2658
2659 /*
2660  * Touch the watchdog for every WD_PAGE_COUNT pages.
2661  */
2662 #define WD_PAGE_COUNT   (128*1024)
2663
2664 void mark_free_pages(struct zone *zone)
2665 {
2666         unsigned long pfn, max_zone_pfn, page_count = WD_PAGE_COUNT;
2667         unsigned long flags;
2668         unsigned int order, t;
2669         struct page *page;
2670
2671         if (zone_is_empty(zone))
2672                 return;
2673
2674         spin_lock_irqsave(&zone->lock, flags);
2675
2676         max_zone_pfn = zone_end_pfn(zone);
2677         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
2678                 if (pfn_valid(pfn)) {
2679                         page = pfn_to_page(pfn);
2680
2681                         if (!--page_count) {
2682                                 touch_nmi_watchdog();
2683                                 page_count = WD_PAGE_COUNT;
2684                         }
2685
2686                         if (page_zone(page) != zone)
2687                                 continue;
2688
2689                         if (!swsusp_page_is_forbidden(page))
2690                                 swsusp_unset_page_free(page);
2691                 }
2692
2693         for_each_migratetype_order(order, t) {
2694                 list_for_each_entry(page,
2695                                 &zone->free_area[order].free_list[t], lru) {
2696                         unsigned long i;
2697
2698                         pfn = page_to_pfn(page);
2699                         for (i = 0; i < (1UL << order); i++) {
2700                                 if (!--page_count) {
2701                                         touch_nmi_watchdog();
2702                                         page_count = WD_PAGE_COUNT;
2703                                 }
2704                                 swsusp_set_page_free(pfn_to_page(pfn + i));
2705                         }
2706                 }
2707         }
2708         spin_unlock_irqrestore(&zone->lock, flags);
2709 }
2710 #endif /* CONFIG_PM */
2711
2712 static bool free_unref_page_prepare(struct page *page, unsigned long pfn)
2713 {
2714         int migratetype;
2715
2716         if (!free_pcp_prepare(page))
2717                 return false;
2718
2719         migratetype = get_pfnblock_migratetype(page, pfn);
2720         set_pcppage_migratetype(page, migratetype);
2721         return true;
2722 }
2723
2724 static void free_unref_page_commit(struct page *page, unsigned long pfn)
2725 {
2726         struct zone *zone = page_zone(page);
2727         struct per_cpu_pages *pcp;
2728         int migratetype;
2729
2730         migratetype = get_pcppage_migratetype(page);
2731         __count_vm_event(PGFREE);
2732
2733         /*
2734          * We only track unmovable, reclaimable and movable on pcp lists.
2735          * Free ISOLATE pages back to the allocator because they are being
2736          * offlined but treat HIGHATOMIC as movable pages so we can get those
2737          * areas back if necessary. Otherwise, we may have to free
2738          * excessively into the page allocator
2739          */
2740         if (migratetype >= MIGRATE_PCPTYPES) {
2741                 if (unlikely(is_migrate_isolate(migratetype))) {
2742                         free_one_page(zone, page, pfn, 0, migratetype);
2743                         return;
2744                 }
2745                 migratetype = MIGRATE_MOVABLE;
2746         }
2747
2748         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2749         list_add(&page->lru, &pcp->lists[migratetype]);
2750         pcp->count++;
2751         if (pcp->count >= pcp->high) {
2752                 unsigned long batch = READ_ONCE(pcp->batch);
2753                 free_pcppages_bulk(zone, batch, pcp);
2754         }
2755 }
2756
2757 /*
2758  * Free a 0-order page
2759  */
2760 void free_unref_page(struct page *page)
2761 {
2762         unsigned long flags;
2763         unsigned long pfn = page_to_pfn(page);
2764
2765         if (!free_unref_page_prepare(page, pfn))
2766                 return;
2767
2768         local_irq_save(flags);
2769         free_unref_page_commit(page, pfn);
2770         local_irq_restore(flags);
2771 }
2772
2773 /*
2774  * Free a list of 0-order pages
2775  */
2776 void free_unref_page_list(struct list_head *list)
2777 {
2778         struct page *page, *next;
2779         unsigned long flags, pfn;
2780         int batch_count = 0;
2781
2782         /* Prepare pages for freeing */
2783         list_for_each_entry_safe(page, next, list, lru) {
2784                 pfn = page_to_pfn(page);
2785                 if (!free_unref_page_prepare(page, pfn))
2786                         list_del(&page->lru);
2787                 set_page_private(page, pfn);
2788         }
2789
2790         local_irq_save(flags);
2791         list_for_each_entry_safe(page, next, list, lru) {
2792                 unsigned long pfn = page_private(page);
2793
2794                 set_page_private(page, 0);
2795                 trace_mm_page_free_batched(page);
2796                 free_unref_page_commit(page, pfn);
2797
2798                 /*
2799                  * Guard against excessive IRQ disabled times when we get
2800                  * a large list of pages to free.
2801                  */
2802                 if (++batch_count == SWAP_CLUSTER_MAX) {
2803                         local_irq_restore(flags);
2804                         batch_count = 0;
2805                         local_irq_save(flags);
2806                 }
2807         }
2808         local_irq_restore(flags);
2809 }
2810
2811 /*
2812  * split_page takes a non-compound higher-order page, and splits it into
2813  * n (1<<order) sub-pages: page[0..n]
2814  * Each sub-page must be freed individually.
2815  *
2816  * Note: this is probably too low level an operation for use in drivers.
2817  * Please consult with lkml before using this in your driver.
2818  */
2819 void split_page(struct page *page, unsigned int order)
2820 {
2821         int i;
2822
2823         VM_BUG_ON_PAGE(PageCompound(page), page);
2824         VM_BUG_ON_PAGE(!page_count(page), page);
2825
2826         for (i = 1; i < (1 << order); i++)
2827                 set_page_refcounted(page + i);
2828         split_page_owner(page, order);
2829 }
2830 EXPORT_SYMBOL_GPL(split_page);
2831
2832 int __isolate_free_page(struct page *page, unsigned int order)
2833 {
2834         unsigned long watermark;
2835         struct zone *zone;
2836         int mt;
2837
2838         BUG_ON(!PageBuddy(page));
2839
2840         zone = page_zone(page);
2841         mt = get_pageblock_migratetype(page);
2842
2843         if (!is_migrate_isolate(mt)) {
2844                 /*
2845                  * Obey watermarks as if the page was being allocated. We can
2846                  * emulate a high-order watermark check with a raised order-0
2847                  * watermark, because we already know our high-order page
2848                  * exists.
2849                  */
2850                 watermark = min_wmark_pages(zone) + (1UL << order);
2851                 if (!zone_watermark_ok(zone, 0, watermark, 0, ALLOC_CMA))
2852                         return 0;
2853
2854                 __mod_zone_freepage_state(zone, -(1UL << order), mt);
2855         }
2856
2857         /* Remove page from free list */
2858         list_del(&page->lru);
2859         zone->free_area[order].nr_free--;
2860         rmv_page_order(page);
2861
2862         /*
2863          * Set the pageblock if the isolated page is at least half of a
2864          * pageblock
2865          */
2866         if (order >= pageblock_order - 1) {
2867                 struct page *endpage = page + (1 << order) - 1;
2868                 for (; page < endpage; page += pageblock_nr_pages) {
2869                         int mt = get_pageblock_migratetype(page);
2870                         if (!is_migrate_isolate(mt) && !is_migrate_cma(mt)
2871                             && !is_migrate_highatomic(mt))
2872                                 set_pageblock_migratetype(page,
2873                                                           MIGRATE_MOVABLE);
2874                 }
2875         }
2876
2877
2878         return 1UL << order;
2879 }
2880
2881 /*
2882  * Update NUMA hit/miss statistics
2883  *
2884  * Must be called with interrupts disabled.
2885  */
2886 static inline void zone_statistics(struct zone *preferred_zone, struct zone *z)
2887 {
2888 #ifdef CONFIG_NUMA
2889         enum numa_stat_item local_stat = NUMA_LOCAL;
2890
2891         /* skip numa counters update if numa stats is disabled */
2892         if (!static_branch_likely(&vm_numa_stat_key))
2893                 return;
2894
2895         if (z->node != numa_node_id())
2896                 local_stat = NUMA_OTHER;
2897
2898         if (z->node == preferred_zone->node)
2899                 __inc_numa_state(z, NUMA_HIT);
2900         else {
2901                 __inc_numa_state(z, NUMA_MISS);
2902                 __inc_numa_state(preferred_zone, NUMA_FOREIGN);
2903         }
2904         __inc_numa_state(z, local_stat);
2905 #endif
2906 }
2907
2908 /* Remove page from the per-cpu list, caller must protect the list */
2909 static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
2910                         struct per_cpu_pages *pcp,
2911                         struct list_head *list)
2912 {
2913         struct page *page;
2914
2915         do {
2916                 if (list_empty(list)) {
2917                         pcp->count += rmqueue_bulk(zone, 0,
2918                                         pcp->batch, list,
2919                                         migratetype);
2920                         if (unlikely(list_empty(list)))
2921                                 return NULL;
2922                 }
2923
2924                 page = list_first_entry(list, struct page, lru);
2925                 list_del(&page->lru);
2926                 pcp->count--;
2927         } while (check_new_pcp(page));
2928
2929         return page;
2930 }
2931
2932 /* Lock and remove page from the per-cpu list */
2933 static struct page *rmqueue_pcplist(struct zone *preferred_zone,
2934                         struct zone *zone, unsigned int order,
2935                         gfp_t gfp_flags, int migratetype)
2936 {
2937         struct per_cpu_pages *pcp;
2938         struct list_head *list;
2939         struct page *page;
2940         unsigned long flags;
2941
2942         local_irq_save(flags);
2943         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2944         list = &pcp->lists[migratetype];
2945         page = __rmqueue_pcplist(zone,  migratetype, pcp, list);
2946         if (page) {
2947                 __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2948                 zone_statistics(preferred_zone, zone);
2949         }
2950         local_irq_restore(flags);
2951         return page;
2952 }
2953
2954 /*
2955  * Allocate a page from the given zone. Use pcplists for order-0 allocations.
2956  */
2957 static inline
2958 struct page *rmqueue(struct zone *preferred_zone,
2959                         struct zone *zone, unsigned int order,
2960                         gfp_t gfp_flags, unsigned int alloc_flags,
2961                         int migratetype)
2962 {
2963         unsigned long flags;
2964         struct page *page;
2965
2966         if (likely(order == 0)) {
2967                 page = rmqueue_pcplist(preferred_zone, zone, order,
2968                                 gfp_flags, migratetype);
2969                 goto out;
2970         }
2971
2972         /*
2973          * We most definitely don't want callers attempting to
2974          * allocate greater than order-1 page units with __GFP_NOFAIL.
2975          */
2976         WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
2977         spin_lock_irqsave(&zone->lock, flags);
2978
2979         do {
2980                 page = NULL;
2981                 if (alloc_flags & ALLOC_HARDER) {
2982                         page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
2983                         if (page)
2984                                 trace_mm_page_alloc_zone_locked(page, order, migratetype);
2985                 }
2986                 if (!page)
2987                         page = __rmqueue(zone, order, migratetype);
2988         } while (page && check_new_pages(page, order));
2989         spin_unlock(&zone->lock);
2990         if (!page)
2991                 goto failed;
2992         __mod_zone_freepage_state(zone, -(1 << order),
2993                                   get_pcppage_migratetype(page));
2994
2995         __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2996         zone_statistics(preferred_zone, zone);
2997         local_irq_restore(flags);
2998
2999 out:
3000         VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
3001         return page;
3002
3003 failed:
3004         local_irq_restore(flags);
3005         return NULL;
3006 }
3007
3008 #ifdef CONFIG_FAIL_PAGE_ALLOC
3009
3010 static struct {
3011         struct fault_attr attr;
3012
3013         bool ignore_gfp_highmem;
3014         bool ignore_gfp_reclaim;
3015         u32 min_order;
3016 } fail_page_alloc = {
3017         .attr = FAULT_ATTR_INITIALIZER,
3018         .ignore_gfp_reclaim = true,
3019         .ignore_gfp_highmem = true,
3020         .min_order = 1,
3021 };
3022
3023 static int __init setup_fail_page_alloc(char *str)
3024 {
3025         return setup_fault_attr(&fail_page_alloc.attr, str);
3026 }
3027 __setup("fail_page_alloc=", setup_fail_page_alloc);
3028
3029 static bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
3030 {
3031         if (order < fail_page_alloc.min_order)
3032                 return false;
3033         if (gfp_mask & __GFP_NOFAIL)
3034                 return false;
3035         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
3036                 return false;
3037         if (fail_page_alloc.ignore_gfp_reclaim &&
3038                         (gfp_mask & __GFP_DIRECT_RECLAIM))
3039                 return false;
3040
3041         return should_fail(&fail_page_alloc.attr, 1 << order);
3042 }
3043
3044 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
3045
3046 static int __init fail_page_alloc_debugfs(void)
3047 {
3048         umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
3049         struct dentry *dir;
3050
3051         dir = fault_create_debugfs_attr("fail_page_alloc", NULL,
3052                                         &fail_page_alloc.attr);
3053         if (IS_ERR(dir))
3054                 return PTR_ERR(dir);
3055
3056         if (!debugfs_create_bool("ignore-gfp-wait", mode, dir,
3057                                 &fail_page_alloc.ignore_gfp_reclaim))
3058                 goto fail;
3059         if (!debugfs_create_bool("ignore-gfp-highmem", mode, dir,
3060                                 &fail_page_alloc.ignore_gfp_highmem))
3061                 goto fail;
3062         if (!debugfs_create_u32("min-order", mode, dir,
3063                                 &fail_page_alloc.min_order))
3064                 goto fail;
3065
3066         return 0;
3067 fail:
3068         debugfs_remove_recursive(dir);
3069
3070         return -ENOMEM;
3071 }
3072
3073 late_initcall(fail_page_alloc_debugfs);
3074
3075 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
3076
3077 #else /* CONFIG_FAIL_PAGE_ALLOC */
3078
3079 static inline bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
3080 {
3081         return false;
3082 }
3083
3084 #endif /* CONFIG_FAIL_PAGE_ALLOC */
3085
3086 /*
3087  * Return true if free base pages are above 'mark'. For high-order checks it
3088  * will return true of the order-0 watermark is reached and there is at least
3089  * one free page of a suitable size. Checking now avoids taking the zone lock
3090  * to check in the allocation paths if no pages are free.
3091  */
3092 bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
3093                          int classzone_idx, unsigned int alloc_flags,
3094                          long free_pages)
3095 {
3096         long min = mark;
3097         int o;
3098         const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM));
3099
3100         /* free_pages may go negative - that's OK */
3101         free_pages -= (1 << order) - 1;
3102
3103         if (alloc_flags & ALLOC_HIGH)
3104                 min -= min / 2;
3105
3106         /*
3107          * If the caller does not have rights to ALLOC_HARDER then subtract
3108          * the high-atomic reserves. This will over-estimate the size of the
3109          * atomic reserve but it avoids a search.
3110          */
3111         if (likely(!alloc_harder)) {
3112                 free_pages -= z->nr_reserved_highatomic;
3113         } else {
3114                 /*
3115                  * OOM victims can try even harder than normal ALLOC_HARDER
3116                  * users on the grounds that it's definitely going to be in
3117                  * the exit path shortly and free memory. Any allocation it
3118                  * makes during the free path will be small and short-lived.
3119                  */
3120                 if (alloc_flags & ALLOC_OOM)
3121                         min -= min / 2;
3122                 else
3123                         min -= min / 4;
3124         }
3125
3126
3127 #ifdef CONFIG_CMA
3128         /* If allocation can't use CMA areas don't use free CMA pages */
3129         if (!(alloc_flags & ALLOC_CMA))
3130                 free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);
3131 #endif
3132
3133         /*
3134          * Check watermarks for an order-0 allocation request. If these
3135          * are not met, then a high-order request also cannot go ahead
3136          * even if a suitable page happened to be free.
3137          */
3138         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
3139                 return false;
3140
3141         /* If this is an order-0 request then the watermark is fine */
3142         if (!order)
3143                 return true;
3144
3145         /* For a high-order request, check at least one suitable page is free */
3146         for (o = order; o < MAX_ORDER; o++) {
3147                 struct free_area *area = &z->free_area[o];
3148                 int mt;
3149
3150                 if (!area->nr_free)
3151                         continue;
3152
3153                 for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
3154                         if (!list_empty(&area->free_list[mt]))
3155                                 return true;
3156                 }
3157
3158 #ifdef CONFIG_CMA
3159                 if ((alloc_flags & ALLOC_CMA) &&
3160                     !list_empty(&area->free_list[MIGRATE_CMA])) {
3161                         return true;
3162                 }
3163 #endif
3164                 if (alloc_harder &&
3165                         !list_empty(&area->free_list[MIGRATE_HIGHATOMIC]))
3166                         return true;
3167         }
3168         return false;
3169 }
3170
3171 bool zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
3172                       int classzone_idx, unsigned int alloc_flags)
3173 {
3174         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
3175                                         zone_page_state(z, NR_FREE_PAGES));
3176 }
3177
3178 static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
3179                 unsigned long mark, int classzone_idx, unsigned int alloc_flags)
3180 {
3181         long free_pages = zone_page_state(z, NR_FREE_PAGES);
3182         long cma_pages = 0;
3183
3184 #ifdef CONFIG_CMA
3185         /* If allocation can't use CMA areas don't use free CMA pages */
3186         if (!(alloc_flags & ALLOC_CMA))
3187                 cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
3188 #endif
3189
3190         /*
3191          * Fast check for order-0 only. If this fails then the reserves
3192          * need to be calculated. There is a corner case where the check
3193          * passes but only the high-order atomic reserve are free. If
3194          * the caller is !atomic then it'll uselessly search the free
3195          * list. That corner case is then slower but it is harmless.
3196          */
3197         if (!order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])
3198                 return true;
3199
3200         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
3201                                         free_pages);
3202 }
3203
3204 bool zone_watermark_ok_safe(struct zone *z, unsigned int order,
3205                         unsigned long mark, int classzone_idx)
3206 {
3207         long free_pages = zone_page_state(z, NR_FREE_PAGES);
3208
3209         if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
3210                 free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
3211
3212         return __zone_watermark_ok(z, order, mark, classzone_idx, 0,
3213                                                                 free_pages);
3214 }
3215
3216 #ifdef CONFIG_NUMA
3217 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3218 {
3219         return node_distance(zone_to_nid(local_zone), zone_to_nid(zone)) <=
3220                                 RECLAIM_DISTANCE;
3221 }
3222 #else   /* CONFIG_NUMA */
3223 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3224 {
3225         return true;
3226 }
3227 #endif  /* CONFIG_NUMA */
3228
3229 /*
3230  * get_page_from_freelist goes through the zonelist trying to allocate
3231  * a page.
3232  */
3233 static struct page *
3234 get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
3235                                                 const struct alloc_context *ac)
3236 {
3237         struct zoneref *z = ac->preferred_zoneref;
3238         struct zone *zone;
3239         struct pglist_data *last_pgdat_dirty_limit = NULL;
3240
3241         /*
3242          * Scan zonelist, looking for a zone with enough free.
3243          * See also __cpuset_node_allowed() comment in kernel/cpuset.c.
3244          */
3245         for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
3246                                                                 ac->nodemask) {
3247                 struct page *page;
3248                 unsigned long mark;
3249
3250                 if (cpusets_enabled() &&
3251                         (alloc_flags & ALLOC_CPUSET) &&
3252                         !__cpuset_zone_allowed(zone, gfp_mask))
3253                                 continue;
3254                 /*
3255                  * When allocating a page cache page for writing, we
3256                  * want to get it from a node that is within its dirty
3257                  * limit, such that no single node holds more than its
3258                  * proportional share of globally allowed dirty pages.
3259                  * The dirty limits take into account the node's
3260                  * lowmem reserves and high watermark so that kswapd
3261                  * should be able to balance it without having to
3262                  * write pages from its LRU list.
3263                  *
3264                  * XXX: For now, allow allocations to potentially
3265                  * exceed the per-node dirty limit in the slowpath
3266                  * (spread_dirty_pages unset) before going into reclaim,
3267                  * which is important when on a NUMA setup the allowed
3268                  * nodes are together not big enough to reach the
3269                  * global limit.  The proper fix for these situations
3270                  * will require awareness of nodes in the
3271                  * dirty-throttling and the flusher threads.
3272                  */
3273                 if (ac->spread_dirty_pages) {
3274                         if (last_pgdat_dirty_limit == zone->zone_pgdat)
3275                                 continue;
3276
3277                         if (!node_dirty_ok(zone->zone_pgdat)) {
3278                                 last_pgdat_dirty_limit = zone->zone_pgdat;
3279                                 continue;
3280                         }
3281                 }
3282
3283                 mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
3284                 if (!zone_watermark_fast(zone, order, mark,
3285                                        ac_classzone_idx(ac), alloc_flags)) {
3286                         int ret;
3287
3288 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
3289                         /*
3290                          * Watermark failed for this zone, but see if we can
3291                          * grow this zone if it contains deferred pages.
3292                          */
3293                         if (static_branch_unlikely(&deferred_pages)) {
3294                                 if (_deferred_grow_zone(zone, order))
3295                                         goto try_this_zone;
3296                         }
3297 #endif
3298                         /* Checked here to keep the fast path fast */
3299                         BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
3300                         if (alloc_flags & ALLOC_NO_WATERMARKS)
3301                                 goto try_this_zone;
3302
3303                         if (node_reclaim_mode == 0 ||
3304                             !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
3305                                 continue;
3306
3307                         ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
3308                         switch (ret) {
3309                         case NODE_RECLAIM_NOSCAN:
3310                                 /* did not scan */
3311                                 continue;
3312                         case NODE_RECLAIM_FULL:
3313                                 /* scanned but unreclaimable */
3314                                 continue;
3315                         default:
3316                                 /* did we reclaim enough */
3317                                 if (zone_watermark_ok(zone, order, mark,
3318                                                 ac_classzone_idx(ac), alloc_flags))
3319                                         goto try_this_zone;
3320
3321                                 continue;
3322                         }
3323                 }
3324
3325 try_this_zone:
3326                 page = rmqueue(ac->preferred_zoneref->zone, zone, order,
3327                                 gfp_mask, alloc_flags, ac->migratetype);
3328                 if (page) {
3329                         prep_new_page(page, order, gfp_mask, alloc_flags);
3330
3331                         /*
3332                          * If this is a high-order atomic allocation then check
3333                          * if the pageblock should be reserved for the future
3334                          */
3335                         if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
3336                                 reserve_highatomic_pageblock(page, zone, order);
3337
3338                         return page;
3339                 } else {
3340 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
3341                         /* Try again if zone has deferred pages */
3342                         if (static_branch_unlikely(&deferred_pages)) {
3343                                 if (_deferred_grow_zone(zone, order))
3344                                         goto try_this_zone;
3345                         }
3346 #endif
3347                 }
3348         }
3349
3350         return NULL;
3351 }
3352
3353 /*
3354  * Large machines with many possible nodes should not always dump per-node
3355  * meminfo in irq context.
3356  */
3357 static inline bool should_suppress_show_mem(void)
3358 {
3359         bool ret = false;
3360
3361 #if NODES_SHIFT > 8
3362         ret = in_interrupt();
3363 #endif
3364         return ret;
3365 }
3366
3367 static void warn_alloc_show_mem(gfp_t gfp_mask, nodemask_t *nodemask)
3368 {
3369         unsigned int filter = SHOW_MEM_FILTER_NODES;
3370         static DEFINE_RATELIMIT_STATE(show_mem_rs, HZ, 1);
3371
3372         if (should_suppress_show_mem() || !__ratelimit(&show_mem_rs))
3373                 return;
3374
3375         /*
3376          * This documents exceptions given to allocations in certain
3377          * contexts that are allowed to allocate outside current's set
3378          * of allowed nodes.
3379          */
3380         if (!(gfp_mask & __GFP_NOMEMALLOC))
3381                 if (tsk_is_oom_victim(current) ||
3382                     (current->flags & (PF_MEMALLOC | PF_EXITING)))
3383                         filter &= ~SHOW_MEM_FILTER_NODES;
3384         if (in_interrupt() || !(gfp_mask & __GFP_DIRECT_RECLAIM))
3385                 filter &= ~SHOW_MEM_FILTER_NODES;
3386
3387         show_mem(filter, nodemask);
3388 }
3389
3390 void warn_alloc(gfp_t gfp_mask, nodemask_t *nodemask, const char *fmt, ...)
3391 {
3392         struct va_format vaf;
3393         va_list args;
3394         static DEFINE_RATELIMIT_STATE(nopage_rs, DEFAULT_RATELIMIT_INTERVAL,
3395                                       DEFAULT_RATELIMIT_BURST);
3396
3397         if ((gfp_mask & __GFP_NOWARN) || !__ratelimit(&nopage_rs))
3398                 return;
3399
3400         va_start(args, fmt);
3401         vaf.fmt = fmt;
3402         vaf.va = &args;
3403         pr_warn("%s: %pV, mode:%#x(%pGg), nodemask=%*pbl\n",
3404                         current->comm, &vaf, gfp_mask, &gfp_mask,
3405                         nodemask_pr_args(nodemask));
3406         va_end(args);
3407
3408         cpuset_print_current_mems_allowed();
3409
3410         dump_stack();
3411         warn_alloc_show_mem(gfp_mask, nodemask);
3412 }
3413
3414 static inline struct page *
3415 __alloc_pages_cpuset_fallback(gfp_t gfp_mask, unsigned int order,
3416                               unsigned int alloc_flags,
3417                               const struct alloc_context *ac)
3418 {
3419         struct page *page;
3420
3421         page = get_page_from_freelist(gfp_mask, order,
3422                         alloc_flags|ALLOC_CPUSET, ac);
3423         /*
3424          * fallback to ignore cpuset restriction if our nodes
3425          * are depleted
3426          */
3427         if (!page)
3428                 page = get_page_from_freelist(gfp_mask, order,
3429                                 alloc_flags, ac);
3430
3431         return page;
3432 }
3433
3434 static inline struct page *
3435 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
3436         const struct alloc_context *ac, unsigned long *did_some_progress)
3437 {
3438         struct oom_control oc = {
3439                 .zonelist = ac->zonelist,
3440                 .nodemask = ac->nodemask,
3441                 .memcg = NULL,
3442                 .gfp_mask = gfp_mask,
3443                 .order = order,
3444         };
3445         struct page *page;
3446
3447         *did_some_progress = 0;
3448
3449         /*
3450          * Acquire the oom lock.  If that fails, somebody else is
3451          * making progress for us.
3452          */
3453         if (!mutex_trylock(&oom_lock)) {
3454                 *did_some_progress = 1;
3455                 schedule_timeout_uninterruptible(1);
3456                 return NULL;
3457         }
3458
3459         /*
3460          * Go through the zonelist yet one more time, keep very high watermark
3461          * here, this is only to catch a parallel oom killing, we must fail if
3462          * we're still under heavy pressure. But make sure that this reclaim
3463          * attempt shall not depend on __GFP_DIRECT_RECLAIM && !__GFP_NORETRY
3464          * allocation which will never fail due to oom_lock already held.
3465          */
3466         page = get_page_from_freelist((gfp_mask | __GFP_HARDWALL) &
3467                                       ~__GFP_DIRECT_RECLAIM, order,
3468                                       ALLOC_WMARK_HIGH|ALLOC_CPUSET, ac);
3469         if (page)
3470                 goto out;
3471
3472         /* Coredumps can quickly deplete all memory reserves */
3473         if (current->flags & PF_DUMPCORE)
3474                 goto out;
3475         /* The OOM killer will not help higher order allocs */
3476         if (order > PAGE_ALLOC_COSTLY_ORDER)
3477                 goto out;
3478         /*
3479          * We have already exhausted all our reclaim opportunities without any
3480          * success so it is time to admit defeat. We will skip the OOM killer
3481          * because it is very likely that the caller has a more reasonable
3482          * fallback than shooting a random task.
3483          */
3484         if (gfp_mask & __GFP_RETRY_MAYFAIL)
3485                 goto out;
3486         /* The OOM killer does not needlessly kill tasks for lowmem */
3487         if (ac->high_zoneidx < ZONE_NORMAL)
3488                 goto out;
3489         if (pm_suspended_storage())
3490                 goto out;
3491         /*
3492          * XXX: GFP_NOFS allocations should rather fail than rely on
3493          * other request to make a forward progress.
3494          * We are in an unfortunate situation where out_of_memory cannot
3495          * do much for this context but let's try it to at least get
3496          * access to memory reserved if the current task is killed (see
3497          * out_of_memory). Once filesystems are ready to handle allocation
3498          * failures more gracefully we should just bail out here.
3499          */
3500
3501         /* The OOM killer may not free memory on a specific node */
3502         if (gfp_mask & __GFP_THISNODE)
3503                 goto out;
3504
3505         /* Exhausted what can be done so it's blame time */
3506         if (out_of_memory(&oc) || WARN_ON_ONCE(gfp_mask & __GFP_NOFAIL)) {
3507                 *did_some_progress = 1;
3508
3509                 /*
3510                  * Help non-failing allocations by giving them access to memory
3511                  * reserves
3512                  */
3513                 if (gfp_mask & __GFP_NOFAIL)
3514                         page = __alloc_pages_cpuset_fallback(gfp_mask, order,
3515                                         ALLOC_NO_WATERMARKS, ac);
3516         }
3517 out:
3518         mutex_unlock(&oom_lock);
3519         return page;
3520 }
3521
3522 /*
3523  * Maximum number of compaction retries wit a progress before OOM
3524  * killer is consider as the only way to move forward.
3525  */
3526 #define MAX_COMPACT_RETRIES 16
3527
3528 #ifdef CONFIG_COMPACTION
3529 /* Try memory compaction for high-order allocations before reclaim */
3530 static struct page *
3531 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3532                 unsigned int alloc_flags, const struct alloc_context *ac,
3533                 enum compact_priority prio, enum compact_result *compact_result)
3534 {
3535         struct page *page;
3536         unsigned int noreclaim_flag;
3537
3538         if (!order)
3539                 return NULL;
3540
3541         noreclaim_flag = memalloc_noreclaim_save();
3542         *compact_result = try_to_compact_pages(gfp_mask, order, alloc_flags, ac,
3543                                                                         prio);
3544         memalloc_noreclaim_restore(noreclaim_flag);
3545
3546         if (*compact_result <= COMPACT_INACTIVE)