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