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