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