mm: zero hash tables in allocator
[muen/linux.git] / mm / page_alloc.c
1 /*
2  *  linux/mm/page_alloc.c
3  *
4  *  Manages the free list, the system allocates free pages here.
5  *  Note that kmalloc() lives in slab.c
6  *
7  *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
8  *  Swap reorganised 29.12.95, Stephen Tweedie
9  *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
10  *  Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999
11  *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
12  *  Zone balancing, Kanoj Sarcar, SGI, Jan 2000
13  *  Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002
14  *          (lots of bits borrowed from Ingo Molnar & Andrew Morton)
15  */
16
17 #include <linux/stddef.h>
18 #include <linux/mm.h>
19 #include <linux/swap.h>
20 #include <linux/interrupt.h>
21 #include <linux/pagemap.h>
22 #include <linux/jiffies.h>
23 #include <linux/bootmem.h>
24 #include <linux/memblock.h>
25 #include <linux/compiler.h>
26 #include <linux/kernel.h>
27 #include <linux/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 #ifdef CONFIG_MOVABLE_NODE
117         [N_MEMORY] = { { [0] = 1UL } },
118 #endif
119         [N_CPU] = { { [0] = 1UL } },
120 #endif  /* NUMA */
121 };
122 EXPORT_SYMBOL(node_states);
123
124 /* Protect totalram_pages and zone->managed_pages */
125 static DEFINE_SPINLOCK(managed_page_count_lock);
126
127 unsigned long totalram_pages __read_mostly;
128 unsigned long totalreserve_pages __read_mostly;
129 unsigned long totalcma_pages __read_mostly;
130
131 int percpu_pagelist_fraction;
132 gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
133
134 /*
135  * A cached value of the page's pageblock's migratetype, used when the page is
136  * put on a pcplist. Used to avoid the pageblock migratetype lookup when
137  * freeing from pcplists in most cases, at the cost of possibly becoming stale.
138  * Also the migratetype set in the page does not necessarily match the pcplist
139  * index, e.g. page might have MIGRATE_CMA set but be on a pcplist with any
140  * other index - this ensures that it will be put on the correct CMA freelist.
141  */
142 static inline int get_pcppage_migratetype(struct page *page)
143 {
144         return page->index;
145 }
146
147 static inline void set_pcppage_migratetype(struct page *page, int migratetype)
148 {
149         page->index = migratetype;
150 }
151
152 #ifdef CONFIG_PM_SLEEP
153 /*
154  * The following functions are used by the suspend/hibernate code to temporarily
155  * change gfp_allowed_mask in order to avoid using I/O during memory allocations
156  * while devices are suspended.  To avoid races with the suspend/hibernate code,
157  * they should always be called with pm_mutex held (gfp_allowed_mask also should
158  * only be modified with pm_mutex held, unless the suspend/hibernate code is
159  * guaranteed not to run in parallel with that modification).
160  */
161
162 static gfp_t saved_gfp_mask;
163
164 void pm_restore_gfp_mask(void)
165 {
166         WARN_ON(!mutex_is_locked(&pm_mutex));
167         if (saved_gfp_mask) {
168                 gfp_allowed_mask = saved_gfp_mask;
169                 saved_gfp_mask = 0;
170         }
171 }
172
173 void pm_restrict_gfp_mask(void)
174 {
175         WARN_ON(!mutex_is_locked(&pm_mutex));
176         WARN_ON(saved_gfp_mask);
177         saved_gfp_mask = gfp_allowed_mask;
178         gfp_allowed_mask &= ~(__GFP_IO | __GFP_FS);
179 }
180
181 bool pm_suspended_storage(void)
182 {
183         if ((gfp_allowed_mask & (__GFP_IO | __GFP_FS)) == (__GFP_IO | __GFP_FS))
184                 return false;
185         return true;
186 }
187 #endif /* CONFIG_PM_SLEEP */
188
189 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
190 unsigned int pageblock_order __read_mostly;
191 #endif
192
193 static void __free_pages_ok(struct page *page, unsigned int order);
194
195 /*
196  * results with 256, 32 in the lowmem_reserve sysctl:
197  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
198  *      1G machine -> (16M dma, 784M normal, 224M high)
199  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
200  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
201  *      HIGHMEM allocation will leave (224M+784M)/256 of ram reserved in ZONE_DMA
202  *
203  * TBD: should special case ZONE_DMA32 machines here - in those we normally
204  * don't need any ZONE_NORMAL reservation
205  */
206 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
207 #ifdef CONFIG_ZONE_DMA
208          256,
209 #endif
210 #ifdef CONFIG_ZONE_DMA32
211          256,
212 #endif
213 #ifdef CONFIG_HIGHMEM
214          32,
215 #endif
216          32,
217 };
218
219 EXPORT_SYMBOL(totalram_pages);
220
221 static char * const zone_names[MAX_NR_ZONES] = {
222 #ifdef CONFIG_ZONE_DMA
223          "DMA",
224 #endif
225 #ifdef CONFIG_ZONE_DMA32
226          "DMA32",
227 #endif
228          "Normal",
229 #ifdef CONFIG_HIGHMEM
230          "HighMem",
231 #endif
232          "Movable",
233 #ifdef CONFIG_ZONE_DEVICE
234          "Device",
235 #endif
236 };
237
238 char * const migratetype_names[MIGRATE_TYPES] = {
239         "Unmovable",
240         "Movable",
241         "Reclaimable",
242         "HighAtomic",
243 #ifdef CONFIG_CMA
244         "CMA",
245 #endif
246 #ifdef CONFIG_MEMORY_ISOLATION
247         "Isolate",
248 #endif
249 };
250
251 compound_page_dtor * const compound_page_dtors[] = {
252         NULL,
253         free_compound_page,
254 #ifdef CONFIG_HUGETLB_PAGE
255         free_huge_page,
256 #endif
257 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
258         free_transhuge_page,
259 #endif
260 };
261
262 int min_free_kbytes = 1024;
263 int user_min_free_kbytes = -1;
264 int watermark_scale_factor = 10;
265
266 static unsigned long __meminitdata nr_kernel_pages;
267 static unsigned long __meminitdata nr_all_pages;
268 static unsigned long __meminitdata dma_reserve;
269
270 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
271 static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
272 static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
273 static unsigned long __initdata required_kernelcore;
274 static unsigned long __initdata required_movablecore;
275 static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
276 static bool mirrored_kernelcore;
277
278 /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
279 int movable_zone;
280 EXPORT_SYMBOL(movable_zone);
281 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
282
283 #if MAX_NUMNODES > 1
284 int nr_node_ids __read_mostly = MAX_NUMNODES;
285 int nr_online_nodes __read_mostly = 1;
286 EXPORT_SYMBOL(nr_node_ids);
287 EXPORT_SYMBOL(nr_online_nodes);
288 #endif
289
290 int page_group_by_mobility_disabled __read_mostly;
291
292 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
293 static inline void reset_deferred_meminit(pg_data_t *pgdat)
294 {
295         unsigned long max_initialise;
296         unsigned long reserved_lowmem;
297
298         /*
299          * Initialise at least 2G of a node but also take into account that
300          * two large system hashes that can take up 1GB for 0.25TB/node.
301          */
302         max_initialise = max(2UL << (30 - PAGE_SHIFT),
303                 (pgdat->node_spanned_pages >> 8));
304
305         /*
306          * Compensate the all the memblock reservations (e.g. crash kernel)
307          * from the initial estimation to make sure we will initialize enough
308          * memory to boot.
309          */
310         reserved_lowmem = memblock_reserved_memory_within(pgdat->node_start_pfn,
311                         pgdat->node_start_pfn + max_initialise);
312         max_initialise += reserved_lowmem;
313
314         pgdat->static_init_size = min(max_initialise, pgdat->node_spanned_pages);
315         pgdat->first_deferred_pfn = ULONG_MAX;
316 }
317
318 /* Returns true if the struct page for the pfn is uninitialised */
319 static inline bool __meminit early_page_uninitialised(unsigned long pfn)
320 {
321         int nid = early_pfn_to_nid(pfn);
322
323         if (node_online(nid) && pfn >= NODE_DATA(nid)->first_deferred_pfn)
324                 return true;
325
326         return false;
327 }
328
329 /*
330  * Returns false when the remaining initialisation should be deferred until
331  * later in the boot cycle when it can be parallelised.
332  */
333 static inline bool update_defer_init(pg_data_t *pgdat,
334                                 unsigned long pfn, unsigned long zone_end,
335                                 unsigned long *nr_initialised)
336 {
337         /* Always populate low zones for address-contrained allocations */
338         if (zone_end < pgdat_end_pfn(pgdat))
339                 return true;
340         (*nr_initialised)++;
341         if ((*nr_initialised > pgdat->static_init_size) &&
342             (pfn & (PAGES_PER_SECTION - 1)) == 0) {
343                 pgdat->first_deferred_pfn = pfn;
344                 return false;
345         }
346
347         return true;
348 }
349 #else
350 static inline void reset_deferred_meminit(pg_data_t *pgdat)
351 {
352 }
353
354 static inline bool early_page_uninitialised(unsigned long pfn)
355 {
356         return false;
357 }
358
359 static inline bool update_defer_init(pg_data_t *pgdat,
360                                 unsigned long pfn, unsigned long zone_end,
361                                 unsigned long *nr_initialised)
362 {
363         return true;
364 }
365 #endif
366
367 /* Return a pointer to the bitmap storing bits affecting a block of pages */
368 static inline unsigned long *get_pageblock_bitmap(struct page *page,
369                                                         unsigned long pfn)
370 {
371 #ifdef CONFIG_SPARSEMEM
372         return __pfn_to_section(pfn)->pageblock_flags;
373 #else
374         return page_zone(page)->pageblock_flags;
375 #endif /* CONFIG_SPARSEMEM */
376 }
377
378 static inline int pfn_to_bitidx(struct page *page, unsigned long pfn)
379 {
380 #ifdef CONFIG_SPARSEMEM
381         pfn &= (PAGES_PER_SECTION-1);
382         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
383 #else
384         pfn = pfn - round_down(page_zone(page)->zone_start_pfn, pageblock_nr_pages);
385         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
386 #endif /* CONFIG_SPARSEMEM */
387 }
388
389 /**
390  * get_pfnblock_flags_mask - Return the requested group of flags for the pageblock_nr_pages block of pages
391  * @page: The page within the block of interest
392  * @pfn: The target page frame number
393  * @end_bitidx: The last bit of interest to retrieve
394  * @mask: mask of bits that the caller is interested in
395  *
396  * Return: pageblock_bits flags
397  */
398 static __always_inline unsigned long __get_pfnblock_flags_mask(struct page *page,
399                                         unsigned long pfn,
400                                         unsigned long end_bitidx,
401                                         unsigned long mask)
402 {
403         unsigned long *bitmap;
404         unsigned long bitidx, word_bitidx;
405         unsigned long word;
406
407         bitmap = get_pageblock_bitmap(page, pfn);
408         bitidx = pfn_to_bitidx(page, pfn);
409         word_bitidx = bitidx / BITS_PER_LONG;
410         bitidx &= (BITS_PER_LONG-1);
411
412         word = bitmap[word_bitidx];
413         bitidx += end_bitidx;
414         return (word >> (BITS_PER_LONG - bitidx - 1)) & mask;
415 }
416
417 unsigned long get_pfnblock_flags_mask(struct page *page, unsigned long pfn,
418                                         unsigned long end_bitidx,
419                                         unsigned long mask)
420 {
421         return __get_pfnblock_flags_mask(page, pfn, end_bitidx, mask);
422 }
423
424 static __always_inline int get_pfnblock_migratetype(struct page *page, unsigned long pfn)
425 {
426         return __get_pfnblock_flags_mask(page, pfn, PB_migrate_end, MIGRATETYPE_MASK);
427 }
428
429 /**
430  * set_pfnblock_flags_mask - Set the requested group of flags for a pageblock_nr_pages block of pages
431  * @page: The page within the block of interest
432  * @flags: The flags to set
433  * @pfn: The target page frame number
434  * @end_bitidx: The last bit of interest
435  * @mask: mask of bits that the caller is interested in
436  */
437 void set_pfnblock_flags_mask(struct page *page, unsigned long flags,
438                                         unsigned long pfn,
439                                         unsigned long end_bitidx,
440                                         unsigned long mask)
441 {
442         unsigned long *bitmap;
443         unsigned long bitidx, word_bitidx;
444         unsigned long old_word, word;
445
446         BUILD_BUG_ON(NR_PAGEBLOCK_BITS != 4);
447
448         bitmap = get_pageblock_bitmap(page, pfn);
449         bitidx = pfn_to_bitidx(page, pfn);
450         word_bitidx = bitidx / BITS_PER_LONG;
451         bitidx &= (BITS_PER_LONG-1);
452
453         VM_BUG_ON_PAGE(!zone_spans_pfn(page_zone(page), pfn), page);
454
455         bitidx += end_bitidx;
456         mask <<= (BITS_PER_LONG - bitidx - 1);
457         flags <<= (BITS_PER_LONG - bitidx - 1);
458
459         word = READ_ONCE(bitmap[word_bitidx]);
460         for (;;) {
461                 old_word = cmpxchg(&bitmap[word_bitidx], word, (word & ~mask) | flags);
462                 if (word == old_word)
463                         break;
464                 word = old_word;
465         }
466 }
467
468 void set_pageblock_migratetype(struct page *page, int migratetype)
469 {
470         if (unlikely(page_group_by_mobility_disabled &&
471                      migratetype < MIGRATE_PCPTYPES))
472                 migratetype = MIGRATE_UNMOVABLE;
473
474         set_pageblock_flags_group(page, (unsigned long)migratetype,
475                                         PB_migrate, PB_migrate_end);
476 }
477
478 #ifdef CONFIG_DEBUG_VM
479 static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
480 {
481         int ret = 0;
482         unsigned seq;
483         unsigned long pfn = page_to_pfn(page);
484         unsigned long sp, start_pfn;
485
486         do {
487                 seq = zone_span_seqbegin(zone);
488                 start_pfn = zone->zone_start_pfn;
489                 sp = zone->spanned_pages;
490                 if (!zone_spans_pfn(zone, pfn))
491                         ret = 1;
492         } while (zone_span_seqretry(zone, seq));
493
494         if (ret)
495                 pr_err("page 0x%lx outside node %d zone %s [ 0x%lx - 0x%lx ]\n",
496                         pfn, zone_to_nid(zone), zone->name,
497                         start_pfn, start_pfn + sp);
498
499         return ret;
500 }
501
502 static int page_is_consistent(struct zone *zone, struct page *page)
503 {
504         if (!pfn_valid_within(page_to_pfn(page)))
505                 return 0;
506         if (zone != page_zone(page))
507                 return 0;
508
509         return 1;
510 }
511 /*
512  * Temporary debugging check for pages not lying within a given zone.
513  */
514 static int bad_range(struct zone *zone, struct page *page)
515 {
516         if (page_outside_zone_boundaries(zone, page))
517                 return 1;
518         if (!page_is_consistent(zone, page))
519                 return 1;
520
521         return 0;
522 }
523 #else
524 static inline int bad_range(struct zone *zone, struct page *page)
525 {
526         return 0;
527 }
528 #endif
529
530 static void bad_page(struct page *page, const char *reason,
531                 unsigned long bad_flags)
532 {
533         static unsigned long resume;
534         static unsigned long nr_shown;
535         static unsigned long nr_unshown;
536
537         /*
538          * Allow a burst of 60 reports, then keep quiet for that minute;
539          * or allow a steady drip of one report per second.
540          */
541         if (nr_shown == 60) {
542                 if (time_before(jiffies, resume)) {
543                         nr_unshown++;
544                         goto out;
545                 }
546                 if (nr_unshown) {
547                         pr_alert(
548                               "BUG: Bad page state: %lu messages suppressed\n",
549                                 nr_unshown);
550                         nr_unshown = 0;
551                 }
552                 nr_shown = 0;
553         }
554         if (nr_shown++ == 0)
555                 resume = jiffies + 60 * HZ;
556
557         pr_alert("BUG: Bad page state in process %s  pfn:%05lx\n",
558                 current->comm, page_to_pfn(page));
559         __dump_page(page, reason);
560         bad_flags &= page->flags;
561         if (bad_flags)
562                 pr_alert("bad because of flags: %#lx(%pGp)\n",
563                                                 bad_flags, &bad_flags);
564         dump_page_owner(page);
565
566         print_modules();
567         dump_stack();
568 out:
569         /* Leave bad fields for debug, except PageBuddy could make trouble */
570         page_mapcount_reset(page); /* remove PageBuddy */
571         add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE);
572 }
573
574 /*
575  * Higher-order pages are called "compound pages".  They are structured thusly:
576  *
577  * The first PAGE_SIZE page is called the "head page" and have PG_head set.
578  *
579  * The remaining PAGE_SIZE pages are called "tail pages". PageTail() is encoded
580  * in bit 0 of page->compound_head. The rest of bits is pointer to head page.
581  *
582  * The first tail page's ->compound_dtor holds the offset in array of compound
583  * page destructors. See compound_page_dtors.
584  *
585  * The first tail page's ->compound_order holds the order of allocation.
586  * This usage means that zero-order pages may not be compound.
587  */
588
589 void free_compound_page(struct page *page)
590 {
591         __free_pages_ok(page, compound_order(page));
592 }
593
594 void prep_compound_page(struct page *page, unsigned int order)
595 {
596         int i;
597         int nr_pages = 1 << order;
598
599         set_compound_page_dtor(page, COMPOUND_PAGE_DTOR);
600         set_compound_order(page, order);
601         __SetPageHead(page);
602         for (i = 1; i < nr_pages; i++) {
603                 struct page *p = page + i;
604                 set_page_count(p, 0);
605                 p->mapping = TAIL_MAPPING;
606                 set_compound_head(p, page);
607         }
608         atomic_set(compound_mapcount_ptr(page), -1);
609 }
610
611 #ifdef CONFIG_DEBUG_PAGEALLOC
612 unsigned int _debug_guardpage_minorder;
613 bool _debug_pagealloc_enabled __read_mostly
614                         = IS_ENABLED(CONFIG_DEBUG_PAGEALLOC_ENABLE_DEFAULT);
615 EXPORT_SYMBOL(_debug_pagealloc_enabled);
616 bool _debug_guardpage_enabled __read_mostly;
617
618 static int __init early_debug_pagealloc(char *buf)
619 {
620         if (!buf)
621                 return -EINVAL;
622         return kstrtobool(buf, &_debug_pagealloc_enabled);
623 }
624 early_param("debug_pagealloc", early_debug_pagealloc);
625
626 static bool need_debug_guardpage(void)
627 {
628         /* If we don't use debug_pagealloc, we don't need guard page */
629         if (!debug_pagealloc_enabled())
630                 return false;
631
632         if (!debug_guardpage_minorder())
633                 return false;
634
635         return true;
636 }
637
638 static void init_debug_guardpage(void)
639 {
640         if (!debug_pagealloc_enabled())
641                 return;
642
643         if (!debug_guardpage_minorder())
644                 return;
645
646         _debug_guardpage_enabled = true;
647 }
648
649 struct page_ext_operations debug_guardpage_ops = {
650         .need = need_debug_guardpage,
651         .init = init_debug_guardpage,
652 };
653
654 static int __init debug_guardpage_minorder_setup(char *buf)
655 {
656         unsigned long res;
657
658         if (kstrtoul(buf, 10, &res) < 0 ||  res > MAX_ORDER / 2) {
659                 pr_err("Bad debug_guardpage_minorder value\n");
660                 return 0;
661         }
662         _debug_guardpage_minorder = res;
663         pr_info("Setting debug_guardpage_minorder to %lu\n", res);
664         return 0;
665 }
666 early_param("debug_guardpage_minorder", debug_guardpage_minorder_setup);
667
668 static inline bool set_page_guard(struct zone *zone, struct page *page,
669                                 unsigned int order, int migratetype)
670 {
671         struct page_ext *page_ext;
672
673         if (!debug_guardpage_enabled())
674                 return false;
675
676         if (order >= debug_guardpage_minorder())
677                 return false;
678
679         page_ext = lookup_page_ext(page);
680         if (unlikely(!page_ext))
681                 return false;
682
683         __set_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);
684
685         INIT_LIST_HEAD(&page->lru);
686         set_page_private(page, order);
687         /* Guard pages are not available for any usage */
688         __mod_zone_freepage_state(zone, -(1 << order), migratetype);
689
690         return true;
691 }
692
693 static inline void clear_page_guard(struct zone *zone, struct page *page,
694                                 unsigned int order, int migratetype)
695 {
696         struct page_ext *page_ext;
697
698         if (!debug_guardpage_enabled())
699                 return;
700
701         page_ext = lookup_page_ext(page);
702         if (unlikely(!page_ext))
703                 return;
704
705         __clear_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);
706
707         set_page_private(page, 0);
708         if (!is_migrate_isolate(migratetype))
709                 __mod_zone_freepage_state(zone, (1 << order), migratetype);
710 }
711 #else
712 struct page_ext_operations debug_guardpage_ops;
713 static inline bool set_page_guard(struct zone *zone, struct page *page,
714                         unsigned int order, int migratetype) { return false; }
715 static inline void clear_page_guard(struct zone *zone, struct page *page,
716                                 unsigned int order, int migratetype) {}
717 #endif
718
719 static inline void set_page_order(struct page *page, unsigned int order)
720 {
721         set_page_private(page, order);
722         __SetPageBuddy(page);
723 }
724
725 static inline void rmv_page_order(struct page *page)
726 {
727         __ClearPageBuddy(page);
728         set_page_private(page, 0);
729 }
730
731 /*
732  * This function checks whether a page is free && is the buddy
733  * we can do coalesce a page and its buddy if
734  * (a) the buddy is not in a hole (check before calling!) &&
735  * (b) the buddy is in the buddy system &&
736  * (c) a page and its buddy have the same order &&
737  * (d) a page and its buddy are in the same zone.
738  *
739  * For recording whether a page is in the buddy system, we set ->_mapcount
740  * PAGE_BUDDY_MAPCOUNT_VALUE.
741  * Setting, clearing, and testing _mapcount PAGE_BUDDY_MAPCOUNT_VALUE is
742  * serialized by zone->lock.
743  *
744  * For recording page's order, we use page_private(page).
745  */
746 static inline int page_is_buddy(struct page *page, struct page *buddy,
747                                                         unsigned int order)
748 {
749         if (page_is_guard(buddy) && page_order(buddy) == order) {
750                 if (page_zone_id(page) != page_zone_id(buddy))
751                         return 0;
752
753                 VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);
754
755                 return 1;
756         }
757
758         if (PageBuddy(buddy) && page_order(buddy) == order) {
759                 /*
760                  * zone check is done late to avoid uselessly
761                  * calculating zone/node ids for pages that could
762                  * never merge.
763                  */
764                 if (page_zone_id(page) != page_zone_id(buddy))
765                         return 0;
766
767                 VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);
768
769                 return 1;
770         }
771         return 0;
772 }
773
774 /*
775  * Freeing function for a buddy system allocator.
776  *
777  * The concept of a buddy system is to maintain direct-mapped table
778  * (containing bit values) for memory blocks of various "orders".
779  * The bottom level table contains the map for the smallest allocatable
780  * units of memory (here, pages), and each level above it describes
781  * pairs of units from the levels below, hence, "buddies".
782  * At a high level, all that happens here is marking the table entry
783  * at the bottom level available, and propagating the changes upward
784  * as necessary, plus some accounting needed to play nicely with other
785  * parts of the VM system.
786  * At each level, we keep a list of pages, which are heads of continuous
787  * free pages of length of (1 << order) and marked with _mapcount
788  * PAGE_BUDDY_MAPCOUNT_VALUE. Page's order is recorded in page_private(page)
789  * field.
790  * So when we are allocating or freeing one, we can derive the state of the
791  * other.  That is, if we allocate a small block, and both were
792  * free, the remainder of the region must be split into blocks.
793  * If a block is freed, and its buddy is also free, then this
794  * triggers coalescing into a block of larger size.
795  *
796  * -- nyc
797  */
798
799 static inline void __free_one_page(struct page *page,
800                 unsigned long pfn,
801                 struct zone *zone, unsigned int order,
802                 int migratetype)
803 {
804         unsigned long combined_pfn;
805         unsigned long uninitialized_var(buddy_pfn);
806         struct page *buddy;
807         unsigned int max_order;
808
809         max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
810
811         VM_BUG_ON(!zone_is_initialized(zone));
812         VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);
813
814         VM_BUG_ON(migratetype == -1);
815         if (likely(!is_migrate_isolate(migratetype)))
816                 __mod_zone_freepage_state(zone, 1 << order, migratetype);
817
818         VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
819         VM_BUG_ON_PAGE(bad_range(zone, page), page);
820
821 continue_merging:
822         while (order < max_order - 1) {
823                 buddy_pfn = __find_buddy_pfn(pfn, order);
824                 buddy = page + (buddy_pfn - pfn);
825
826                 if (!pfn_valid_within(buddy_pfn))
827                         goto done_merging;
828                 if (!page_is_buddy(page, buddy, order))
829                         goto done_merging;
830                 /*
831                  * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
832                  * merge with it and move up one order.
833                  */
834                 if (page_is_guard(buddy)) {
835                         clear_page_guard(zone, buddy, order, migratetype);
836                 } else {
837                         list_del(&buddy->lru);
838                         zone->free_area[order].nr_free--;
839                         rmv_page_order(buddy);
840                 }
841                 combined_pfn = buddy_pfn & pfn;
842                 page = page + (combined_pfn - pfn);
843                 pfn = combined_pfn;
844                 order++;
845         }
846         if (max_order < MAX_ORDER) {
847                 /* If we are here, it means order is >= pageblock_order.
848                  * We want to prevent merge between freepages on isolate
849                  * pageblock and normal pageblock. Without this, pageblock
850                  * isolation could cause incorrect freepage or CMA accounting.
851                  *
852                  * We don't want to hit this code for the more frequent
853                  * low-order merging.
854                  */
855                 if (unlikely(has_isolate_pageblock(zone))) {
856                         int buddy_mt;
857
858                         buddy_pfn = __find_buddy_pfn(pfn, order);
859                         buddy = page + (buddy_pfn - pfn);
860                         buddy_mt = get_pageblock_migratetype(buddy);
861
862                         if (migratetype != buddy_mt
863                                         && (is_migrate_isolate(migratetype) ||
864                                                 is_migrate_isolate(buddy_mt)))
865                                 goto done_merging;
866                 }
867                 max_order++;
868                 goto continue_merging;
869         }
870
871 done_merging:
872         set_page_order(page, order);
873
874         /*
875          * If this is not the largest possible page, check if the buddy
876          * of the next-highest order is free. If it is, it's possible
877          * that pages are being freed that will coalesce soon. In case,
878          * that is happening, add the free page to the tail of the list
879          * so it's less likely to be used soon and more likely to be merged
880          * as a higher order page
881          */
882         if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)) {
883                 struct page *higher_page, *higher_buddy;
884                 combined_pfn = buddy_pfn & pfn;
885                 higher_page = page + (combined_pfn - pfn);
886                 buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
887                 higher_buddy = higher_page + (buddy_pfn - combined_pfn);
888                 if (pfn_valid_within(buddy_pfn) &&
889                     page_is_buddy(higher_page, higher_buddy, order + 1)) {
890                         list_add_tail(&page->lru,
891                                 &zone->free_area[order].free_list[migratetype]);
892                         goto out;
893                 }
894         }
895
896         list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
897 out:
898         zone->free_area[order].nr_free++;
899 }
900
901 /*
902  * A bad page could be due to a number of fields. Instead of multiple branches,
903  * try and check multiple fields with one check. The caller must do a detailed
904  * check if necessary.
905  */
906 static inline bool page_expected_state(struct page *page,
907                                         unsigned long check_flags)
908 {
909         if (unlikely(atomic_read(&page->_mapcount) != -1))
910                 return false;
911
912         if (unlikely((unsigned long)page->mapping |
913                         page_ref_count(page) |
914 #ifdef CONFIG_MEMCG
915                         (unsigned long)page->mem_cgroup |
916 #endif
917                         (page->flags & check_flags)))
918                 return false;
919
920         return true;
921 }
922
923 static void free_pages_check_bad(struct page *page)
924 {
925         const char *bad_reason;
926         unsigned long bad_flags;
927
928         bad_reason = NULL;
929         bad_flags = 0;
930
931         if (unlikely(atomic_read(&page->_mapcount) != -1))
932                 bad_reason = "nonzero mapcount";
933         if (unlikely(page->mapping != NULL))
934                 bad_reason = "non-NULL mapping";
935         if (unlikely(page_ref_count(page) != 0))
936                 bad_reason = "nonzero _refcount";
937         if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_FREE)) {
938                 bad_reason = "PAGE_FLAGS_CHECK_AT_FREE flag(s) set";
939                 bad_flags = PAGE_FLAGS_CHECK_AT_FREE;
940         }
941 #ifdef CONFIG_MEMCG
942         if (unlikely(page->mem_cgroup))
943                 bad_reason = "page still charged to cgroup";
944 #endif
945         bad_page(page, bad_reason, bad_flags);
946 }
947
948 static inline int free_pages_check(struct page *page)
949 {
950         if (likely(page_expected_state(page, PAGE_FLAGS_CHECK_AT_FREE)))
951                 return 0;
952
953         /* Something has gone sideways, find it */
954         free_pages_check_bad(page);
955         return 1;
956 }
957
958 static int free_tail_pages_check(struct page *head_page, struct page *page)
959 {
960         int ret = 1;
961
962         /*
963          * We rely page->lru.next never has bit 0 set, unless the page
964          * is PageTail(). Let's make sure that's true even for poisoned ->lru.
965          */
966         BUILD_BUG_ON((unsigned long)LIST_POISON1 & 1);
967
968         if (!IS_ENABLED(CONFIG_DEBUG_VM)) {
969                 ret = 0;
970                 goto out;
971         }
972         switch (page - head_page) {
973         case 1:
974                 /* the first tail page: ->mapping is compound_mapcount() */
975                 if (unlikely(compound_mapcount(page))) {
976                         bad_page(page, "nonzero compound_mapcount", 0);
977                         goto out;
978                 }
979                 break;
980         case 2:
981                 /*
982                  * the second tail page: ->mapping is
983                  * page_deferred_list().next -- ignore value.
984                  */
985                 break;
986         default:
987                 if (page->mapping != TAIL_MAPPING) {
988                         bad_page(page, "corrupted mapping in tail page", 0);
989                         goto out;
990                 }
991                 break;
992         }
993         if (unlikely(!PageTail(page))) {
994                 bad_page(page, "PageTail not set", 0);
995                 goto out;
996         }
997         if (unlikely(compound_head(page) != head_page)) {
998                 bad_page(page, "compound_head not consistent", 0);
999                 goto out;
1000         }
1001         ret = 0;
1002 out:
1003         page->mapping = NULL;
1004         clear_compound_head(page);
1005         return ret;
1006 }
1007
1008 static __always_inline bool free_pages_prepare(struct page *page,
1009                                         unsigned int order, bool check_free)
1010 {
1011         int bad = 0;
1012
1013         VM_BUG_ON_PAGE(PageTail(page), page);
1014
1015         trace_mm_page_free(page, order);
1016         kmemcheck_free_shadow(page, order);
1017
1018         /*
1019          * Check tail pages before head page information is cleared to
1020          * avoid checking PageCompound for order-0 pages.
1021          */
1022         if (unlikely(order)) {
1023                 bool compound = PageCompound(page);
1024                 int i;
1025
1026                 VM_BUG_ON_PAGE(compound && compound_order(page) != order, page);
1027
1028                 if (compound)
1029                         ClearPageDoubleMap(page);
1030                 for (i = 1; i < (1 << order); i++) {
1031                         if (compound)
1032                                 bad += free_tail_pages_check(page, page + i);
1033                         if (unlikely(free_pages_check(page + i))) {
1034                                 bad++;
1035                                 continue;
1036                         }
1037                         (page + i)->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
1038                 }
1039         }
1040         if (PageMappingFlags(page))
1041                 page->mapping = NULL;
1042         if (memcg_kmem_enabled() && PageKmemcg(page))
1043                 memcg_kmem_uncharge(page, order);
1044         if (check_free)
1045                 bad += free_pages_check(page);
1046         if (bad)
1047                 return false;
1048
1049         page_cpupid_reset_last(page);
1050         page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
1051         reset_page_owner(page, order);
1052
1053         if (!PageHighMem(page)) {
1054                 debug_check_no_locks_freed(page_address(page),
1055                                            PAGE_SIZE << order);
1056                 debug_check_no_obj_freed(page_address(page),
1057                                            PAGE_SIZE << order);
1058         }
1059         arch_free_page(page, order);
1060         kernel_poison_pages(page, 1 << order, 0);
1061         kernel_map_pages(page, 1 << order, 0);
1062         kasan_free_pages(page, order);
1063
1064         return true;
1065 }
1066
1067 #ifdef CONFIG_DEBUG_VM
1068 static inline bool free_pcp_prepare(struct page *page)
1069 {
1070         return free_pages_prepare(page, 0, true);
1071 }
1072
1073 static inline bool bulkfree_pcp_prepare(struct page *page)
1074 {
1075         return false;
1076 }
1077 #else
1078 static bool free_pcp_prepare(struct page *page)
1079 {
1080         return free_pages_prepare(page, 0, false);
1081 }
1082
1083 static bool bulkfree_pcp_prepare(struct page *page)
1084 {
1085         return free_pages_check(page);
1086 }
1087 #endif /* CONFIG_DEBUG_VM */
1088
1089 /*
1090  * Frees a number of pages from the PCP lists
1091  * Assumes all pages on list are in same zone, and of same order.
1092  * count is the number of pages to free.
1093  *
1094  * If the zone was previously in an "all pages pinned" state then look to
1095  * see if this freeing clears that state.
1096  *
1097  * And clear the zone's pages_scanned counter, to hold off the "all pages are
1098  * pinned" detection logic.
1099  */
1100 static void free_pcppages_bulk(struct zone *zone, int count,
1101                                         struct per_cpu_pages *pcp)
1102 {
1103         int migratetype = 0;
1104         int batch_free = 0;
1105         bool isolated_pageblocks;
1106
1107         spin_lock(&zone->lock);
1108         isolated_pageblocks = has_isolate_pageblock(zone);
1109
1110         while (count) {
1111                 struct page *page;
1112                 struct list_head *list;
1113
1114                 /*
1115                  * Remove pages from lists in a round-robin fashion. A
1116                  * batch_free count is maintained that is incremented when an
1117                  * empty list is encountered.  This is so more pages are freed
1118                  * off fuller lists instead of spinning excessively around empty
1119                  * lists
1120                  */
1121                 do {
1122                         batch_free++;
1123                         if (++migratetype == MIGRATE_PCPTYPES)
1124                                 migratetype = 0;
1125                         list = &pcp->lists[migratetype];
1126                 } while (list_empty(list));
1127
1128                 /* This is the only non-empty list. Free them all. */
1129                 if (batch_free == MIGRATE_PCPTYPES)
1130                         batch_free = count;
1131
1132                 do {
1133                         int mt; /* migratetype of the to-be-freed page */
1134
1135                         page = list_last_entry(list, struct page, lru);
1136                         /* must delete as __free_one_page list manipulates */
1137                         list_del(&page->lru);
1138
1139                         mt = get_pcppage_migratetype(page);
1140                         /* MIGRATE_ISOLATE page should not go to pcplists */
1141                         VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
1142                         /* Pageblock could have been isolated meanwhile */
1143                         if (unlikely(isolated_pageblocks))
1144                                 mt = get_pageblock_migratetype(page);
1145
1146                         if (bulkfree_pcp_prepare(page))
1147                                 continue;
1148
1149                         __free_one_page(page, page_to_pfn(page), zone, 0, mt);
1150                         trace_mm_page_pcpu_drain(page, 0, mt);
1151                 } while (--count && --batch_free && !list_empty(list));
1152         }
1153         spin_unlock(&zone->lock);
1154 }
1155
1156 static void free_one_page(struct zone *zone,
1157                                 struct page *page, unsigned long pfn,
1158                                 unsigned int order,
1159                                 int migratetype)
1160 {
1161         spin_lock(&zone->lock);
1162         if (unlikely(has_isolate_pageblock(zone) ||
1163                 is_migrate_isolate(migratetype))) {
1164                 migratetype = get_pfnblock_migratetype(page, pfn);
1165         }
1166         __free_one_page(page, pfn, zone, order, migratetype);
1167         spin_unlock(&zone->lock);
1168 }
1169
1170 static void __meminit __init_single_page(struct page *page, unsigned long pfn,
1171                                 unsigned long zone, int nid)
1172 {
1173         set_page_links(page, zone, nid, pfn);
1174         init_page_count(page);
1175         page_mapcount_reset(page);
1176         page_cpupid_reset_last(page);
1177
1178         INIT_LIST_HEAD(&page->lru);
1179 #ifdef WANT_PAGE_VIRTUAL
1180         /* The shift won't overflow because ZONE_NORMAL is below 4G. */
1181         if (!is_highmem_idx(zone))
1182                 set_page_address(page, __va(pfn << PAGE_SHIFT));
1183 #endif
1184 }
1185
1186 static void __meminit __init_single_pfn(unsigned long pfn, unsigned long zone,
1187                                         int nid)
1188 {
1189         return __init_single_page(pfn_to_page(pfn), pfn, zone, nid);
1190 }
1191
1192 #ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
1193 static void init_reserved_page(unsigned long pfn)
1194 {
1195         pg_data_t *pgdat;
1196         int nid, zid;
1197
1198         if (!early_page_uninitialised(pfn))
1199                 return;
1200
1201         nid = early_pfn_to_nid(pfn);
1202         pgdat = NODE_DATA(nid);
1203
1204         for (zid = 0; zid < MAX_NR_ZONES; zid++) {
1205                 struct zone *zone = &pgdat->node_zones[zid];
1206
1207                 if (pfn >= zone->zone_start_pfn && pfn < zone_end_pfn(zone))
1208                         break;
1209         }
1210         __init_single_pfn(pfn, zid, nid);
1211 }
1212 #else
1213 static inline void init_reserved_page(unsigned long pfn)
1214 {
1215 }
1216 #endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
1217
1218 /*
1219  * Initialised pages do not have PageReserved set. This function is
1220  * called for each range allocated by the bootmem allocator and
1221  * marks the pages PageReserved. The remaining valid pages are later
1222  * sent to the buddy page allocator.
1223  */
1224 void __meminit reserve_bootmem_region(phys_addr_t start, phys_addr_t end)
1225 {
1226         unsigned long start_pfn = PFN_DOWN(start);
1227         unsigned long end_pfn = PFN_UP(end);
1228
1229         for (; start_pfn < end_pfn; start_pfn++) {
1230                 if (pfn_valid(start_pfn)) {
1231                         struct page *page = pfn_to_page(start_pfn);
1232
1233                         init_reserved_page(start_pfn);
1234
1235                         /* Avoid false-positive PageTail() */
1236                         INIT_LIST_HEAD(&page->lru);
1237
1238                         SetPageReserved(page);
1239                 }
1240         }
1241 }
1242
1243 static void __free_pages_ok(struct page *page, unsigned int order)
1244 {
1245         unsigned long flags;
1246         int migratetype;
1247         unsigned long pfn = page_to_pfn(page);
1248
1249         if (!free_pages_prepare(page, order, true))
1250                 return;
1251
1252         migratetype = get_pfnblock_migratetype(page, pfn);
1253         local_irq_save(flags);
1254         __count_vm_events(PGFREE, 1 << order);
1255         free_one_page(page_zone(page), page, pfn, order, migratetype);
1256         local_irq_restore(flags);
1257 }
1258
1259 static void __init __free_pages_boot_core(struct page *page, unsigned int order)
1260 {
1261         unsigned int nr_pages = 1 << order;
1262         struct page *p = page;
1263         unsigned int loop;
1264
1265         prefetchw(p);
1266         for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
1267                 prefetchw(p + 1);
1268                 __ClearPageReserved(p);
1269                 set_page_count(p, 0);
1270         }
1271         __ClearPageReserved(p);
1272         set_page_count(p, 0);
1273
1274         page_zone(page)->managed_pages += nr_pages;
1275         set_page_refcounted(page);
1276         __free_pages(page, order);
1277 }
1278
1279 #if defined(CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID) || \
1280         defined(CONFIG_HAVE_MEMBLOCK_NODE_MAP)
1281
1282 static struct mminit_pfnnid_cache early_pfnnid_cache __meminitdata;
1283
1284 int __meminit early_pfn_to_nid(unsigned long pfn)
1285 {
1286         static DEFINE_SPINLOCK(early_pfn_lock);
1287         int nid;
1288
1289         spin_lock(&early_pfn_lock);
1290         nid = __early_pfn_to_nid(pfn, &early_pfnnid_cache);
1291         if (nid < 0)
1292                 nid = first_online_node;
1293         spin_unlock(&early_pfn_lock);
1294
1295         return nid;
1296 }
1297 #endif
1298
1299 #ifdef CONFIG_NODES_SPAN_OTHER_NODES
1300 static inline bool __meminit meminit_pfn_in_nid(unsigned long pfn, int node,
1301                                         struct mminit_pfnnid_cache *state)
1302 {
1303         int nid;
1304
1305         nid = __early_pfn_to_nid(pfn, state);
1306         if (nid >= 0 && nid != node)
1307                 return false;
1308         return true;
1309 }
1310
1311 /* Only safe to use early in boot when initialisation is single-threaded */
1312 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1313 {
1314         return meminit_pfn_in_nid(pfn, node, &early_pfnnid_cache);
1315 }
1316
1317 #else
1318
1319 static inline bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
1320 {
1321         return true;
1322 }
1323 static inline bool __meminit 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 static inline bool
2211 __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
2212 {
2213         struct free_area *area;
2214         unsigned int current_order;
2215         struct page *page;
2216         int fallback_mt;
2217         bool can_steal;
2218
2219         /* Find the largest possible block of pages in the other list */
2220         for (current_order = MAX_ORDER-1;
2221                                 current_order >= order && current_order <= MAX_ORDER-1;
2222                                 --current_order) {
2223                 area = &(zone->free_area[current_order]);
2224                 fallback_mt = find_suitable_fallback(area, current_order,
2225                                 start_migratetype, false, &can_steal);
2226                 if (fallback_mt == -1)
2227                         continue;
2228
2229                 page = list_first_entry(&area->free_list[fallback_mt],
2230                                                 struct page, lru);
2231
2232                 steal_suitable_fallback(zone, page, start_migratetype,
2233                                                                 can_steal);
2234
2235                 trace_mm_page_alloc_extfrag(page, order, current_order,
2236                         start_migratetype, fallback_mt);
2237
2238                 return true;
2239         }
2240
2241         return false;
2242 }
2243
2244 /*
2245  * Do the hard work of removing an element from the buddy allocator.
2246  * Call me with the zone->lock already held.
2247  */
2248 static struct page *__rmqueue(struct zone *zone, unsigned int order,
2249                                 int migratetype)
2250 {
2251         struct page *page;
2252
2253 retry:
2254         page = __rmqueue_smallest(zone, order, migratetype);
2255         if (unlikely(!page)) {
2256                 if (migratetype == MIGRATE_MOVABLE)
2257                         page = __rmqueue_cma_fallback(zone, order);
2258
2259                 if (!page && __rmqueue_fallback(zone, order, migratetype))
2260                         goto retry;
2261         }
2262
2263         trace_mm_page_alloc_zone_locked(page, order, migratetype);
2264         return page;
2265 }
2266
2267 /*
2268  * Obtain a specified number of elements from the buddy allocator, all under
2269  * a single hold of the lock, for efficiency.  Add them to the supplied list.
2270  * Returns the number of new pages which were placed at *list.
2271  */
2272 static int rmqueue_bulk(struct zone *zone, unsigned int order,
2273                         unsigned long count, struct list_head *list,
2274                         int migratetype, bool cold)
2275 {
2276         int i, alloced = 0;
2277
2278         spin_lock(&zone->lock);
2279         for (i = 0; i < count; ++i) {
2280                 struct page *page = __rmqueue(zone, order, migratetype);
2281                 if (unlikely(page == NULL))
2282                         break;
2283
2284                 if (unlikely(check_pcp_refill(page)))
2285                         continue;
2286
2287                 /*
2288                  * Split buddy pages returned by expand() are received here
2289                  * in physical page order. The page is added to the callers and
2290                  * list and the list head then moves forward. From the callers
2291                  * perspective, the linked list is ordered by page number in
2292                  * some conditions. This is useful for IO devices that can
2293                  * merge IO requests if the physical pages are ordered
2294                  * properly.
2295                  */
2296                 if (likely(!cold))
2297                         list_add(&page->lru, list);
2298                 else
2299                         list_add_tail(&page->lru, list);
2300                 list = &page->lru;
2301                 alloced++;
2302                 if (is_migrate_cma(get_pcppage_migratetype(page)))
2303                         __mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
2304                                               -(1 << order));
2305         }
2306
2307         /*
2308          * i pages were removed from the buddy list even if some leak due
2309          * to check_pcp_refill failing so adjust NR_FREE_PAGES based
2310          * on i. Do not confuse with 'alloced' which is the number of
2311          * pages added to the pcp list.
2312          */
2313         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
2314         spin_unlock(&zone->lock);
2315         return alloced;
2316 }
2317
2318 #ifdef CONFIG_NUMA
2319 /*
2320  * Called from the vmstat counter updater to drain pagesets of this
2321  * currently executing processor on remote nodes after they have
2322  * expired.
2323  *
2324  * Note that this function must be called with the thread pinned to
2325  * a single processor.
2326  */
2327 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
2328 {
2329         unsigned long flags;
2330         int to_drain, batch;
2331
2332         local_irq_save(flags);
2333         batch = READ_ONCE(pcp->batch);
2334         to_drain = min(pcp->count, batch);
2335         if (to_drain > 0) {
2336                 free_pcppages_bulk(zone, to_drain, pcp);
2337                 pcp->count -= to_drain;
2338         }
2339         local_irq_restore(flags);
2340 }
2341 #endif
2342
2343 /*
2344  * Drain pcplists of the indicated processor and zone.
2345  *
2346  * The processor must either be the current processor and the
2347  * thread pinned to the current processor or a processor that
2348  * is not online.
2349  */
2350 static void drain_pages_zone(unsigned int cpu, struct zone *zone)
2351 {
2352         unsigned long flags;
2353         struct per_cpu_pageset *pset;
2354         struct per_cpu_pages *pcp;
2355
2356         local_irq_save(flags);
2357         pset = per_cpu_ptr(zone->pageset, cpu);
2358
2359         pcp = &pset->pcp;
2360         if (pcp->count) {
2361                 free_pcppages_bulk(zone, pcp->count, pcp);
2362                 pcp->count = 0;
2363         }
2364         local_irq_restore(flags);
2365 }
2366
2367 /*
2368  * Drain pcplists of all zones on the indicated processor.
2369  *
2370  * The processor must either be the current processor and the
2371  * thread pinned to the current processor or a processor that
2372  * is not online.
2373  */
2374 static void drain_pages(unsigned int cpu)
2375 {
2376         struct zone *zone;
2377
2378         for_each_populated_zone(zone) {
2379                 drain_pages_zone(cpu, zone);
2380         }
2381 }
2382
2383 /*
2384  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
2385  *
2386  * The CPU has to be pinned. When zone parameter is non-NULL, spill just
2387  * the single zone's pages.
2388  */
2389 void drain_local_pages(struct zone *zone)
2390 {
2391         int cpu = smp_processor_id();
2392
2393         if (zone)
2394                 drain_pages_zone(cpu, zone);
2395         else
2396                 drain_pages(cpu);
2397 }
2398
2399 static void drain_local_pages_wq(struct work_struct *work)
2400 {
2401         /*
2402          * drain_all_pages doesn't use proper cpu hotplug protection so
2403          * we can race with cpu offline when the WQ can move this from
2404          * a cpu pinned worker to an unbound one. We can operate on a different
2405          * cpu which is allright but we also have to make sure to not move to
2406          * a different one.
2407          */
2408         preempt_disable();
2409         drain_local_pages(NULL);
2410         preempt_enable();
2411 }
2412
2413 /*
2414  * Spill all the per-cpu pages from all CPUs back into the buddy allocator.
2415  *
2416  * When zone parameter is non-NULL, spill just the single zone's pages.
2417  *
2418  * Note that this can be extremely slow as the draining happens in a workqueue.
2419  */
2420 void drain_all_pages(struct zone *zone)
2421 {
2422         int cpu;
2423
2424         /*
2425          * Allocate in the BSS so we wont require allocation in
2426          * direct reclaim path for CONFIG_CPUMASK_OFFSTACK=y
2427          */
2428         static cpumask_t cpus_with_pcps;
2429
2430         /*
2431          * Make sure nobody triggers this path before mm_percpu_wq is fully
2432          * initialized.
2433          */
2434         if (WARN_ON_ONCE(!mm_percpu_wq))
2435                 return;
2436
2437         /* Workqueues cannot recurse */
2438         if (current->flags & PF_WQ_WORKER)
2439                 return;
2440
2441         /*
2442          * Do not drain if one is already in progress unless it's specific to
2443          * a zone. Such callers are primarily CMA and memory hotplug and need
2444          * the drain to be complete when the call returns.
2445          */
2446         if (unlikely(!mutex_trylock(&pcpu_drain_mutex))) {
2447                 if (!zone)
2448                         return;
2449                 mutex_lock(&pcpu_drain_mutex);
2450         }
2451
2452         /*
2453          * We don't care about racing with CPU hotplug event
2454          * as offline notification will cause the notified
2455          * cpu to drain that CPU pcps and on_each_cpu_mask
2456          * disables preemption as part of its processing
2457          */
2458         for_each_online_cpu(cpu) {
2459                 struct per_cpu_pageset *pcp;
2460                 struct zone *z;
2461                 bool has_pcps = false;
2462
2463                 if (zone) {
2464                         pcp = per_cpu_ptr(zone->pageset, cpu);
2465                         if (pcp->pcp.count)
2466                                 has_pcps = true;
2467                 } else {
2468                         for_each_populated_zone(z) {
2469                                 pcp = per_cpu_ptr(z->pageset, cpu);
2470                                 if (pcp->pcp.count) {
2471                                         has_pcps = true;
2472                                         break;
2473                                 }
2474                         }
2475                 }
2476
2477                 if (has_pcps)
2478                         cpumask_set_cpu(cpu, &cpus_with_pcps);
2479                 else
2480                         cpumask_clear_cpu(cpu, &cpus_with_pcps);
2481         }
2482
2483         for_each_cpu(cpu, &cpus_with_pcps) {
2484                 struct work_struct *work = per_cpu_ptr(&pcpu_drain, cpu);
2485                 INIT_WORK(work, drain_local_pages_wq);
2486                 queue_work_on(cpu, mm_percpu_wq, work);
2487         }
2488         for_each_cpu(cpu, &cpus_with_pcps)
2489                 flush_work(per_cpu_ptr(&pcpu_drain, cpu));
2490
2491         mutex_unlock(&pcpu_drain_mutex);
2492 }
2493
2494 #ifdef CONFIG_HIBERNATION
2495
2496 void mark_free_pages(struct zone *zone)
2497 {
2498         unsigned long pfn, max_zone_pfn;
2499         unsigned long flags;
2500         unsigned int order, t;
2501         struct page *page;
2502
2503         if (zone_is_empty(zone))
2504                 return;
2505
2506         spin_lock_irqsave(&zone->lock, flags);
2507
2508         max_zone_pfn = zone_end_pfn(zone);
2509         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
2510                 if (pfn_valid(pfn)) {
2511                         page = pfn_to_page(pfn);
2512
2513                         if (page_zone(page) != zone)
2514                                 continue;
2515
2516                         if (!swsusp_page_is_forbidden(page))
2517                                 swsusp_unset_page_free(page);
2518                 }
2519
2520         for_each_migratetype_order(order, t) {
2521                 list_for_each_entry(page,
2522                                 &zone->free_area[order].free_list[t], lru) {
2523                         unsigned long i;
2524
2525                         pfn = page_to_pfn(page);
2526                         for (i = 0; i < (1UL << order); i++)
2527                                 swsusp_set_page_free(pfn_to_page(pfn + i));
2528                 }
2529         }
2530         spin_unlock_irqrestore(&zone->lock, flags);
2531 }
2532 #endif /* CONFIG_PM */
2533
2534 /*
2535  * Free a 0-order page
2536  * cold == true ? free a cold page : free a hot page
2537  */
2538 void free_hot_cold_page(struct page *page, bool cold)
2539 {
2540         struct zone *zone = page_zone(page);
2541         struct per_cpu_pages *pcp;
2542         unsigned long flags;
2543         unsigned long pfn = page_to_pfn(page);
2544         int migratetype;
2545
2546         if (!free_pcp_prepare(page))
2547                 return;
2548
2549         migratetype = get_pfnblock_migratetype(page, pfn);
2550         set_pcppage_migratetype(page, migratetype);
2551         local_irq_save(flags);
2552         __count_vm_event(PGFREE);
2553
2554         /*
2555          * We only track unmovable, reclaimable and movable on pcp lists.
2556          * Free ISOLATE pages back to the allocator because they are being
2557          * offlined but treat HIGHATOMIC as movable pages so we can get those
2558          * areas back if necessary. Otherwise, we may have to free
2559          * excessively into the page allocator
2560          */
2561         if (migratetype >= MIGRATE_PCPTYPES) {
2562                 if (unlikely(is_migrate_isolate(migratetype))) {
2563                         free_one_page(zone, page, pfn, 0, migratetype);
2564                         goto out;
2565                 }
2566                 migratetype = MIGRATE_MOVABLE;
2567         }
2568
2569         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2570         if (!cold)
2571                 list_add(&page->lru, &pcp->lists[migratetype]);
2572         else
2573                 list_add_tail(&page->lru, &pcp->lists[migratetype]);
2574         pcp->count++;
2575         if (pcp->count >= pcp->high) {
2576                 unsigned long batch = READ_ONCE(pcp->batch);
2577                 free_pcppages_bulk(zone, batch, pcp);
2578                 pcp->count -= batch;
2579         }
2580
2581 out:
2582         local_irq_restore(flags);
2583 }
2584
2585 /*
2586  * Free a list of 0-order pages
2587  */
2588 void free_hot_cold_page_list(struct list_head *list, bool cold)
2589 {
2590         struct page *page, *next;
2591
2592         list_for_each_entry_safe(page, next, list, lru) {
2593                 trace_mm_page_free_batched(page, cold);
2594                 free_hot_cold_page(page, cold);
2595         }
2596 }
2597
2598 /*
2599  * split_page takes a non-compound higher-order page, and splits it into
2600  * n (1<<order) sub-pages: page[0..n]
2601  * Each sub-page must be freed individually.
2602  *
2603  * Note: this is probably too low level an operation for use in drivers.
2604  * Please consult with lkml before using this in your driver.
2605  */
2606 void split_page(struct page *page, unsigned int order)
2607 {
2608         int i;
2609
2610         VM_BUG_ON_PAGE(PageCompound(page), page);
2611         VM_BUG_ON_PAGE(!page_count(page), page);
2612
2613 #ifdef CONFIG_KMEMCHECK
2614         /*
2615          * Split shadow pages too, because free(page[0]) would
2616          * otherwise free the whole shadow.
2617          */
2618         if (kmemcheck_page_is_tracked(page))
2619                 split_page(virt_to_page(page[0].shadow), order);
2620 #endif
2621
2622         for (i = 1; i < (1 << order); i++)
2623                 set_page_refcounted(page + i);
2624         split_page_owner(page, order);
2625 }
2626 EXPORT_SYMBOL_GPL(split_page);
2627
2628 int __isolate_free_page(struct page *page, unsigned int order)
2629 {
2630         unsigned long watermark;
2631         struct zone *zone;
2632         int mt;
2633
2634         BUG_ON(!PageBuddy(page));
2635
2636         zone = page_zone(page);
2637         mt = get_pageblock_migratetype(page);
2638
2639         if (!is_migrate_isolate(mt)) {
2640                 /*
2641                  * Obey watermarks as if the page was being allocated. We can
2642                  * emulate a high-order watermark check with a raised order-0
2643                  * watermark, because we already know our high-order page
2644                  * exists.
2645                  */
2646                 watermark = min_wmark_pages(zone) + (1UL << order);
2647                 if (!zone_watermark_ok(zone, 0, watermark, 0, ALLOC_CMA))
2648                         return 0;
2649
2650                 __mod_zone_freepage_state(zone, -(1UL << order), mt);
2651         }
2652
2653         /* Remove page from free list */
2654         list_del(&page->lru);
2655         zone->free_area[order].nr_free--;
2656         rmv_page_order(page);
2657
2658         /*
2659          * Set the pageblock if the isolated page is at least half of a
2660          * pageblock
2661          */
2662         if (order >= pageblock_order - 1) {
2663                 struct page *endpage = page + (1 << order) - 1;
2664                 for (; page < endpage; page += pageblock_nr_pages) {
2665                         int mt = get_pageblock_migratetype(page);
2666                         if (!is_migrate_isolate(mt) && !is_migrate_cma(mt)
2667                             && !is_migrate_highatomic(mt))
2668                                 set_pageblock_migratetype(page,
2669                                                           MIGRATE_MOVABLE);
2670                 }
2671         }
2672
2673
2674         return 1UL << order;
2675 }
2676
2677 /*
2678  * Update NUMA hit/miss statistics
2679  *
2680  * Must be called with interrupts disabled.
2681  */
2682 static inline void zone_statistics(struct zone *preferred_zone, struct zone *z)
2683 {
2684 #ifdef CONFIG_NUMA
2685         enum zone_stat_item local_stat = NUMA_LOCAL;
2686
2687         if (z->node != numa_node_id())
2688                 local_stat = NUMA_OTHER;
2689
2690         if (z->node == preferred_zone->node)
2691                 __inc_zone_state(z, NUMA_HIT);
2692         else {
2693                 __inc_zone_state(z, NUMA_MISS);
2694                 __inc_zone_state(preferred_zone, NUMA_FOREIGN);
2695         }
2696         __inc_zone_state(z, local_stat);
2697 #endif
2698 }
2699
2700 /* Remove page from the per-cpu list, caller must protect the list */
2701 static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
2702                         bool cold, struct per_cpu_pages *pcp,
2703                         struct list_head *list)
2704 {
2705         struct page *page;
2706
2707         do {
2708                 if (list_empty(list)) {
2709                         pcp->count += rmqueue_bulk(zone, 0,
2710                                         pcp->batch, list,
2711                                         migratetype, cold);
2712                         if (unlikely(list_empty(list)))
2713                                 return NULL;
2714                 }
2715
2716                 if (cold)
2717                         page = list_last_entry(list, struct page, lru);
2718                 else
2719                         page = list_first_entry(list, struct page, lru);
2720
2721                 list_del(&page->lru);
2722                 pcp->count--;
2723         } while (check_new_pcp(page));
2724
2725         return page;
2726 }
2727
2728 /* Lock and remove page from the per-cpu list */
2729 static struct page *rmqueue_pcplist(struct zone *preferred_zone,
2730                         struct zone *zone, unsigned int order,
2731                         gfp_t gfp_flags, int migratetype)
2732 {
2733         struct per_cpu_pages *pcp;
2734         struct list_head *list;
2735         bool cold = ((gfp_flags & __GFP_COLD) != 0);
2736         struct page *page;
2737         unsigned long flags;
2738
2739         local_irq_save(flags);
2740         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2741         list = &pcp->lists[migratetype];
2742         page = __rmqueue_pcplist(zone,  migratetype, cold, pcp, list);
2743         if (page) {
2744                 __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2745                 zone_statistics(preferred_zone, zone);
2746         }
2747         local_irq_restore(flags);
2748         return page;
2749 }
2750
2751 /*
2752  * Allocate a page from the given zone. Use pcplists for order-0 allocations.
2753  */
2754 static inline
2755 struct page *rmqueue(struct zone *preferred_zone,
2756                         struct zone *zone, unsigned int order,
2757                         gfp_t gfp_flags, unsigned int alloc_flags,
2758                         int migratetype)
2759 {
2760         unsigned long flags;
2761         struct page *page;
2762
2763         if (likely(order == 0)) {
2764                 page = rmqueue_pcplist(preferred_zone, zone, order,
2765                                 gfp_flags, migratetype);
2766                 goto out;
2767         }
2768
2769         /*
2770          * We most definitely don't want callers attempting to
2771          * allocate greater than order-1 page units with __GFP_NOFAIL.
2772          */
2773         WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
2774         spin_lock_irqsave(&zone->lock, flags);
2775
2776         do {
2777                 page = NULL;
2778                 if (alloc_flags & ALLOC_HARDER) {
2779                         page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
2780                         if (page)
2781                                 trace_mm_page_alloc_zone_locked(page, order, migratetype);
2782                 }
2783                 if (!page)
2784                         page = __rmqueue(zone, order, migratetype);
2785         } while (page && check_new_pages(page, order));
2786         spin_unlock(&zone->lock);
2787         if (!page)
2788                 goto failed;
2789         __mod_zone_freepage_state(zone, -(1 << order),
2790                                   get_pcppage_migratetype(page));
2791
2792         __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2793         zone_statistics(preferred_zone, zone);
2794         local_irq_restore(flags);
2795
2796 out:
2797         VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
2798         return page;
2799
2800 failed:
2801         local_irq_restore(flags);
2802         return NULL;
2803 }
2804
2805 #ifdef CONFIG_FAIL_PAGE_ALLOC
2806
2807 static struct {
2808         struct fault_attr attr;
2809
2810         bool ignore_gfp_highmem;
2811         bool ignore_gfp_reclaim;
2812         u32 min_order;
2813 } fail_page_alloc = {
2814         .attr = FAULT_ATTR_INITIALIZER,
2815         .ignore_gfp_reclaim = true,
2816         .ignore_gfp_highmem = true,
2817         .min_order = 1,
2818 };
2819
2820 static int __init setup_fail_page_alloc(char *str)
2821 {
2822         return setup_fault_attr(&fail_page_alloc.attr, str);
2823 }
2824 __setup("fail_page_alloc=", setup_fail_page_alloc);
2825
2826 static bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
2827 {
2828         if (order < fail_page_alloc.min_order)
2829                 return false;
2830         if (gfp_mask & __GFP_NOFAIL)
2831                 return false;
2832         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
2833                 return false;
2834         if (fail_page_alloc.ignore_gfp_reclaim &&
2835                         (gfp_mask & __GFP_DIRECT_RECLAIM))
2836                 return false;
2837
2838         return should_fail(&fail_page_alloc.attr, 1 << order);
2839 }
2840
2841 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
2842
2843 static int __init fail_page_alloc_debugfs(void)
2844 {
2845         umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
2846         struct dentry *dir;
2847
2848         dir = fault_create_debugfs_attr("fail_page_alloc", NULL,
2849                                         &fail_page_alloc.attr);
2850         if (IS_ERR(dir))
2851                 return PTR_ERR(dir);
2852
2853         if (!debugfs_create_bool("ignore-gfp-wait", mode, dir,
2854                                 &fail_page_alloc.ignore_gfp_reclaim))
2855                 goto fail;
2856         if (!debugfs_create_bool("ignore-gfp-highmem", mode, dir,
2857                                 &fail_page_alloc.ignore_gfp_highmem))
2858                 goto fail;
2859         if (!debugfs_create_u32("min-order", mode, dir,
2860                                 &fail_page_alloc.min_order))
2861                 goto fail;
2862
2863         return 0;
2864 fail:
2865         debugfs_remove_recursive(dir);
2866
2867         return -ENOMEM;
2868 }
2869
2870 late_initcall(fail_page_alloc_debugfs);
2871
2872 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
2873
2874 #else /* CONFIG_FAIL_PAGE_ALLOC */
2875
2876 static inline bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
2877 {
2878         return false;
2879 }
2880
2881 #endif /* CONFIG_FAIL_PAGE_ALLOC */
2882
2883 /*
2884  * Return true if free base pages are above 'mark'. For high-order checks it
2885  * will return true of the order-0 watermark is reached and there is at least
2886  * one free page of a suitable size. Checking now avoids taking the zone lock
2887  * to check in the allocation paths if no pages are free.
2888  */
2889 bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
2890                          int classzone_idx, unsigned int alloc_flags,
2891                          long free_pages)
2892 {
2893         long min = mark;
2894         int o;
2895         const bool alloc_harder = (alloc_flags & ALLOC_HARDER);
2896
2897         /* free_pages may go negative - that's OK */
2898         free_pages -= (1 << order) - 1;
2899
2900         if (alloc_flags & ALLOC_HIGH)
2901                 min -= min / 2;
2902
2903         /*
2904          * If the caller does not have rights to ALLOC_HARDER then subtract
2905          * the high-atomic reserves. This will over-estimate the size of the
2906          * atomic reserve but it avoids a search.
2907          */
2908         if (likely(!alloc_harder))
2909                 free_pages -= z->nr_reserved_highatomic;
2910         else
2911                 min -= min / 4;
2912
2913 #ifdef CONFIG_CMA
2914         /* If allocation can't use CMA areas don't use free CMA pages */
2915         if (!(alloc_flags & ALLOC_CMA))
2916                 free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);
2917 #endif
2918
2919         /*
2920          * Check watermarks for an order-0 allocation request. If these
2921          * are not met, then a high-order request also cannot go ahead
2922          * even if a suitable page happened to be free.
2923          */
2924         if (free_pages <= min + z->lowmem_reserve[classzone_idx])
2925                 return false;
2926
2927         /* If this is an order-0 request then the watermark is fine */
2928         if (!order)
2929                 return true;
2930
2931         /* For a high-order request, check at least one suitable page is free */
2932         for (o = order; o < MAX_ORDER; o++) {
2933                 struct free_area *area = &z->free_area[o];
2934                 int mt;
2935
2936                 if (!area->nr_free)
2937                         continue;
2938
2939                 if (alloc_harder)
2940                         return true;
2941
2942                 for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
2943                         if (!list_empty(&area->free_list[mt]))
2944                                 return true;
2945                 }
2946
2947 #ifdef CONFIG_CMA
2948                 if ((alloc_flags & ALLOC_CMA) &&
2949                     !list_empty(&area->free_list[MIGRATE_CMA])) {
2950                         return true;
2951                 }
2952 #endif
2953         }
2954         return false;
2955 }
2956
2957 bool zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
2958                       int classzone_idx, unsigned int alloc_flags)
2959 {
2960         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
2961                                         zone_page_state(z, NR_FREE_PAGES));
2962 }
2963
2964 static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
2965                 unsigned long mark, int classzone_idx, unsigned int alloc_flags)
2966 {
2967         long free_pages = zone_page_state(z, NR_FREE_PAGES);
2968         long cma_pages = 0;
2969
2970 #ifdef CONFIG_CMA
2971         /* If allocation can't use CMA areas don't use free CMA pages */
2972         if (!(alloc_flags & ALLOC_CMA))
2973                 cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
2974 #endif
2975
2976         /*
2977          * Fast check for order-0 only. If this fails then the reserves
2978          * need to be calculated. There is a corner case where the check
2979          * passes but only the high-order atomic reserve are free. If
2980          * the caller is !atomic then it'll uselessly search the free
2981          * list. That corner case is then slower but it is harmless.
2982          */
2983         if (!order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])
2984                 return true;
2985
2986         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
2987                                         free_pages);
2988 }
2989
2990 bool zone_watermark_ok_safe(struct zone *z, unsigned int order,
2991                         unsigned long mark, int classzone_idx)
2992 {
2993         long free_pages = zone_page_state(z, NR_FREE_PAGES);
2994
2995         if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
2996                 free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
2997
2998         return __zone_watermark_ok(z, order, mark, classzone_idx, 0,
2999                                                                 free_pages);
3000 }
3001
3002 #ifdef CONFIG_NUMA
3003 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3004 {
3005         return node_distance(zone_to_nid(local_zone), zone_to_nid(zone)) <=
3006                                 RECLAIM_DISTANCE;
3007 }
3008 #else   /* CONFIG_NUMA */
3009 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
3010 {
3011         return true;
3012 }
3013 #endif  /* CONFIG_NUMA */
3014
3015 /*
3016  * get_page_from_freelist goes through the zonelist trying to allocate
3017  * a page.
3018  */
3019 static struct page *
3020 get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
3021                                                 const struct alloc_context *ac)
3022 {
3023         struct zoneref *z = ac->preferred_zoneref;
3024         struct zone *zone;
3025         struct pglist_data *last_pgdat_dirty_limit = NULL;
3026
3027         /*
3028          * Scan zonelist, looking for a zone with enough free.
3029          * See also __cpuset_node_allowed() comment in kernel/cpuset.c.
3030          */
3031         for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
3032                                                                 ac->nodemask) {
3033                 struct page *page;
3034                 unsigned long mark;
3035
3036                 if (cpusets_enabled() &&
3037                         (alloc_flags & ALLOC_CPUSET) &&
3038                         !__cpuset_zone_allowed(zone, gfp_mask))
3039                                 continue;
3040                 /*
3041                  * When allocating a page cache page for writing, we
3042                  * want to get it from a node that is within its dirty
3043                  * limit, such that no single node holds more than its
3044                  * proportional share of globally allowed dirty pages.
3045                  * The dirty limits take into account the node's
3046                  * lowmem reserves and high watermark so that kswapd
3047                  * should be able to balance it without having to
3048                  * write pages from its LRU list.
3049                  *
3050                  * XXX: For now, allow allocations to potentially
3051                  * exceed the per-node dirty limit in the slowpath
3052                  * (spread_dirty_pages unset) before going into reclaim,
3053                  * which is important when on a NUMA setup the allowed
3054                  * nodes are together not big enough to reach the
3055                  * global limit.  The proper fix for these situations
3056                  * will require awareness of nodes in the
3057                  * dirty-throttling and the flusher threads.
3058                  */
3059                 if (ac->spread_dirty_pages) {
3060                         if (last_pgdat_dirty_limit == zone->zone_pgdat)
3061                                 continue;
3062
3063                         if (!node_dirty_ok(zone->zone_pgdat)) {
3064                                 last_pgdat_dirty_limit = zone->zone_pgdat;
3065                                 continue;
3066                         }
3067                 }
3068
3069                 mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
3070                 if (!zone_watermark_fast(zone, order, mark,
3071                                        ac_classzone_idx(ac), alloc_flags)) {
3072                         int ret;
3073
3074                         /* Checked here to keep the fast path fast */
3075                         BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
3076                         if (alloc_flags & ALLOC_NO_WATERMARKS)
3077                                 goto try_this_zone;
3078
3079                         if (node_reclaim_mode == 0 ||
3080                             !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
3081                                 continue;
3082
3083                         ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
3084                         switch (ret) {
3085                         case NODE_RECLAIM_NOSCAN:
3086                                 /* did not scan */
3087                                 continue;
3088                         case NODE_RECLAIM_FULL:
3089                                 /* scanned but unreclaimable */
3090                                 continue;
3091                         default:
3092                                 /* did we reclaim enough */
3093                                 if (zone_watermark_ok(zone, order, mark,
3094                                                 ac_classzone_idx(ac), alloc_flags))
3095                                         goto try_this_zone;
3096
3097                                 continue;
3098                         }
3099                 }
3100
3101 try_this_zone:
3102                 page = rmqueue(ac->preferred_zoneref->zone, zone, order,
3103                                 gfp_mask, alloc_flags, ac->migratetype);
3104                 if (page) {
3105                         prep_new_page(page, order, gfp_mask, alloc_flags);
3106
3107                         /*
3108                          * If this is a high-order atomic allocation then check
3109                          * if the pageblock should be reserved for the future
3110                          */
3111                         if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
3112                                 reserve_highatomic_pageblock(page, zone, order);
3113
3114                         return page;
3115                 }
3116         }
3117
3118         return NULL;
3119 }
3120
3121 /*
3122  * Large machines with many possible nodes should not always dump per-node
3123  * meminfo in irq context.
3124  */
3125 static inline bool should_suppress_show_mem(void)
3126 {
3127         bool ret = false;
3128
3129 #if NODES_SHIFT > 8
3130         ret = in_interrupt();
3131 #endif
3132         return ret;
3133 }
3134
3135 static void warn_alloc_show_mem(gfp_t gfp_mask, nodemask_t *nodemask)
3136 {
3137         unsigned int filter = SHOW_MEM_FILTER_NODES;
3138         static DEFINE_RATELIMIT_STATE(show_mem_rs, HZ, 1);
3139
3140         if (should_suppress_show_mem() || !__ratelimit(&show_mem_rs))
3141                 return;
3142
3143         /*
3144          * This documents exceptions given to allocations in certain
3145          * contexts that are allowed to allocate outside current's set
3146          * of allowed nodes.
3147          */
3148         if (!(gfp_mask & __GFP_NOMEMALLOC))
3149                 if (test_thread_flag(TIF_MEMDIE) ||
3150                     (current->flags & (PF_MEMALLOC | PF_EXITING)))
3151                         filter &= ~SHOW_MEM_FILTER_NODES;
3152         if (in_interrupt() || !(gfp_mask & __GFP_DIRECT_RECLAIM))
3153                 filter &= ~SHOW_MEM_FILTER_NODES;
3154
3155         show_mem(filter, nodemask);
3156 }
3157
3158 void warn_alloc(gfp_t gfp_mask, nodemask_t *nodemask, const char *fmt, ...)
3159 {
3160         struct va_format vaf;
3161         va_list args;
3162         static DEFINE_RATELIMIT_STATE(nopage_rs, DEFAULT_RATELIMIT_INTERVAL,
3163                                       DEFAULT_RATELIMIT_BURST);
3164
3165         if ((gfp_mask & __GFP_NOWARN) || !__ratelimit(&nopage_rs))
3166                 return;
3167
3168         pr_warn("%s: ", current->comm);
3169
3170         va_start(args, fmt);
3171         vaf.fmt = fmt;
3172         vaf.va = &args;
3173         pr_cont("%pV", &vaf);
3174         va_end(args);
3175
3176         pr_cont(", mode:%#x(%pGg), nodemask=", gfp_mask, &gfp_mask);
3177         if (nodemask)
3178                 pr_cont("%*pbl\n", nodemask_pr_args(nodemask));
3179         else
3180                 pr_cont("(null)\n");
3181
3182         cpuset_print_current_mems_allowed();
3183
3184         dump_stack();
3185         warn_alloc_show_mem(gfp_mask, nodemask);
3186 }
3187
3188 static inline struct page *
3189 __alloc_pages_cpuset_fallback(gfp_t gfp_mask, unsigned int order,
3190                               unsigned int alloc_flags,
3191                               const struct alloc_context *ac)
3192 {
3193         struct page *page;
3194
3195         page = get_page_from_freelist(gfp_mask, order,
3196                         alloc_flags|ALLOC_CPUSET, ac);
3197         /*
3198          * fallback to ignore cpuset restriction if our nodes
3199          * are depleted
3200          */
3201         if (!page)
3202                 page = get_page_from_freelist(gfp_mask, order,
3203                                 alloc_flags, ac);
3204
3205         return page;
3206 }
3207
3208 static inline struct page *
3209 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
3210         const struct alloc_context *ac, unsigned long *did_some_progress)
3211 {
3212         struct oom_control oc = {
3213                 .zonelist = ac->zonelist,
3214                 .nodemask = ac->nodemask,
3215                 .memcg = NULL,
3216                 .gfp_mask = gfp_mask,
3217                 .order = order,
3218         };
3219         struct page *page;
3220
3221         *did_some_progress = 0;
3222
3223         /*
3224          * Acquire the oom lock.  If that fails, somebody else is
3225          * making progress for us.
3226          */
3227         if (!mutex_trylock(&oom_lock)) {
3228                 *did_some_progress = 1;
3229                 schedule_timeout_uninterruptible(1);
3230                 return NULL;
3231         }
3232
3233         /*
3234          * Go through the zonelist yet one more time, keep very high watermark
3235          * here, this is only to catch a parallel oom killing, we must fail if
3236          * we're still under heavy pressure.
3237          */
3238         page = get_page_from_freelist(gfp_mask | __GFP_HARDWALL, order,
3239                                         ALLOC_WMARK_HIGH|ALLOC_CPUSET, ac);
3240         if (page)
3241                 goto out;
3242
3243         /* Coredumps can quickly deplete all memory reserves */
3244         if (current->flags & PF_DUMPCORE)
3245                 goto out;
3246         /* The OOM killer will not help higher order allocs */
3247         if (order > PAGE_ALLOC_COSTLY_ORDER)
3248                 goto out;
3249         /* The OOM killer does not needlessly kill tasks for lowmem */
3250         if (ac->high_zoneidx < ZONE_NORMAL)
3251                 goto out;
3252         if (pm_suspended_storage())
3253                 goto out;
3254         /*
3255          * XXX: GFP_NOFS allocations should rather fail than rely on
3256          * other request to make a forward progress.
3257          * We are in an unfortunate situation where out_of_memory cannot
3258          * do much for this context but let's try it to at least get
3259          * access to memory reserved if the current task is killed (see
3260          * out_of_memory). Once filesystems are ready to handle allocation
3261          * failures more gracefully we should just bail out here.
3262          */
3263
3264         /* The OOM killer may not free memory on a specific node */
3265         if (gfp_mask & __GFP_THISNODE)
3266                 goto out;
3267
3268         /* Exhausted what can be done so it's blamo time */
3269         if (out_of_memory(&oc) || WARN_ON_ONCE(gfp_mask & __GFP_NOFAIL)) {
3270                 *did_some_progress = 1;
3271
3272                 /*
3273                  * Help non-failing allocations by giving them access to memory
3274                  * reserves
3275                  */
3276                 if (gfp_mask & __GFP_NOFAIL)
3277                         page = __alloc_pages_cpuset_fallback(gfp_mask, order,
3278                                         ALLOC_NO_WATERMARKS, ac);
3279         }
3280 out:
3281         mutex_unlock(&oom_lock);
3282         return page;
3283 }
3284
3285 /*
3286  * Maximum number of compaction retries wit a progress before OOM
3287  * killer is consider as the only way to move forward.
3288  */
3289 #define MAX_COMPACT_RETRIES 16
3290
3291 #ifdef CONFIG_COMPACTION
3292 /* Try memory compaction for high-order allocations before reclaim */
3293 static struct page *
3294 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3295                 unsigned int alloc_flags, const struct alloc_context *ac,
3296                 enum compact_priority prio, enum compact_result *compact_result)
3297 {
3298         struct page *page;
3299         unsigned int noreclaim_flag;
3300
3301         if (!order)
3302                 return NULL;
3303
3304         noreclaim_flag = memalloc_noreclaim_save();
3305         *compact_result = try_to_compact_pages(gfp_mask, order, alloc_flags, ac,
3306                                                                         prio);
3307         memalloc_noreclaim_restore(noreclaim_flag);
3308
3309         if (*compact_result <= COMPACT_INACTIVE)
3310                 return NULL;
3311
3312         /*
3313          * At least in one zone compaction wasn't deferred or skipped, so let's
3314          * count a compaction stall
3315          */
3316         count_vm_event(COMPACTSTALL);
3317
3318         page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
3319
3320         if (page) {
3321                 struct zone *zone = page_zone(page);
3322
3323                 zone->compact_blockskip_flush = false;
3324                 compaction_defer_reset(zone, order, true);
3325                 count_vm_event(COMPACTSUCCESS);
3326                 return page;
3327         }
3328
3329         /*
3330          * It's bad if compaction run occurs and fails. The most likely reason
3331          * is that pages exist, but not enough to satisfy watermarks.
3332          */
3333         count_vm_event(COMPACTFAIL);
3334
3335         cond_resched();
3336
3337         return NULL;
3338 }
3339
3340 static inline bool
3341 should_compact_retry(struct alloc_context *ac, int order, int alloc_flags,
3342                      enum compact_result compact_result,
3343                      enum compact_priority *compact_priority,
3344                      int *compaction_retries)
3345 {
3346         int max_retries = MAX_COMPACT_RETRIES;
3347         int min_priority;
3348         bool ret = false;
3349         int retries = *compaction_retries;
3350         enum compact_priority priority = *compact_priority;
3351
3352         if (!order)
3353                 return false;
3354
3355         if (compaction_made_progress(compact_result))
3356                 (*compaction_retries)++;
3357
3358         /*
3359          * compaction considers all the zone as desperately out of memory
3360          * so it doesn't really make much sense to retry except when the
3361          * failure could be caused by insufficient priority
3362          */
3363         if (compaction_failed(compact_result))
3364                 goto check_priority;
3365
3366         /*
3367          * make sure the compaction wasn't deferred or didn't bail out early
3368          * due to locks contention before we declare that we should give up.
3369          * But do not retry if the given zonelist is not suitable for
3370          * compaction.
3371          */
3372         if (compaction_withdrawn(compact_result)) {
3373                 ret = compaction_zonelist_suitable(ac, order, alloc_flags);
3374                 goto out;
3375         }
3376
3377         /*
3378          * !costly requests are much more important than __GFP_REPEAT
3379          * costly ones because they are de facto nofail and invoke OOM
3380          * killer to move on while costly can fail and users are ready
3381          * to cope with that. 1/4 retries is rather arbitrary but we
3382          * would need much more detailed feedback from compaction to
3383          * make a better decision.
3384          */
3385         if (order > PAGE_ALLOC_COSTLY_ORDER)
3386                 max_retries /= 4;
3387         if (*compaction_retries <= max_retries) {
3388                 ret = true;
3389                 goto out;
3390         }
3391
3392         /*
3393          * Make sure there are attempts at the highest priority if we exhausted
3394          * all retries or failed at the lower priorities.
3395          */
3396 check_priority:
3397         min_priority = (order > PAGE_ALLOC_COSTLY_ORDER) ?
3398                         MIN_COMPACT_COSTLY_PRIORITY : MIN_COMPACT_PRIORITY;
3399
3400         if (*compact_priority > min_priority) {
3401                 (*compact_priority)--;
3402                 *compaction_retries = 0;
3403                 ret = true;
3404         }
3405 out:
3406         trace_compact_retry(order, priority, compact_result, retries, max_retries, ret);
3407         return ret;
3408 }
3409 #else
3410 static inline struct page *
3411 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3412                 unsigned int alloc_flags, const struct alloc_context *ac,
3413                 enum compact_priority prio, enum compact_result *compact_result)
3414 {
3415         *compact_result = COMPACT_SKIPPED;
3416         return NULL;
3417 }
3418
3419 static inline bool
3420 should_compact_retry(struct alloc_context *ac, unsigned int order, int alloc_flags,
3421                      enum compact_result compact_result,
3422                      enum compact_priority *compact_priority,
3423                      int *compaction_retries)
3424 {
3425         struct zone *zone;
3426         struct zoneref *z;
3427
3428         if (!order || order > PAGE_ALLOC_COSTLY_ORDER)
3429                 return false;
3430
3431         /*
3432          * There are setups with compaction disabled which would prefer to loop
3433          * inside the allocator rather than hit the oom killer prematurely.
3434          * Let's give them a good hope and keep retrying while the order-0
3435          * watermarks are OK.
3436          */
3437         for_each_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
3438                                         ac->nodemask) {
3439                 if (zone_watermark_ok(zone, 0, min_wmark_pages(zone),
3440                                         ac_classzone_idx(ac), alloc_flags))
3441                         return true;
3442         }
3443         return false;
3444 }
3445 #endif /* CONFIG_COMPACTION */
3446
3447 /* Perform direct synchronous page reclaim */
3448 static int
3449 __perform_reclaim(gfp_t gfp_mask, unsigned int order,
3450                                         const struct alloc_context *ac)
3451 {
3452         struct reclaim_state reclaim_state;
3453         int progress;
3454         unsigned int noreclaim_flag;
3455
3456         cond_resched();
3457
3458         /* We now go into synchronous reclaim */
3459         cpuset_memory_pressure_bump();
3460         noreclaim_flag = memalloc_noreclaim_save();
3461         lockdep_set_current_reclaim_state(gfp_mask);
3462         reclaim_state.reclaimed_slab = 0;
3463         current->reclaim_state = &reclaim_state;
3464
3465         progress = try_to_free_pages(ac->zonelist, order, gfp_mask,
3466                                                                 ac->nodemask);
3467
3468         current->reclaim_state = NULL;
3469         lockdep_clear_current_reclaim_state();
3470         memalloc_noreclaim_restore(noreclaim_flag);
3471
3472         cond_resched();
3473
3474         return progress;
3475 }
3476
3477 /* The really slow allocator path where we enter direct reclaim */
3478 static inline struct page *
3479 __alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
3480                 unsigned int alloc_flags, const struct alloc_context *ac,
3481                 unsigned long *did_some_progress)
3482 {
3483         struct page *page = NULL;
3484         bool drained = false;
3485
3486         *did_some_progress = __perform_reclaim(gfp_mask, order, ac);
3487         if (unlikely(!(*did_some_progress)))
3488                 return NULL;
3489
3490 retry:
3491         page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
3492
3493         /*
3494          * If an allocation failed after direct reclaim, it could be because
3495          * pages are pinned on the per-cpu lists or in high alloc reserves.
3496          * Shrink them them and try again
3497          */
3498         if (!page && !drained) {
3499                 unreserve_highatomic_pageblock(ac, false);
3500                 drain_all_pages(NULL);
3501                 drained = true;
3502                 goto retry;
3503         }
3504
3505         return page;
3506 }
3507
3508 static void wake_all_kswapds(unsigned int order, const struct alloc_context *ac)
3509 {
3510         struct zoneref *z;
3511         struct zone *zone;
3512         pg_data_t *last_pgdat = NULL;
3513
3514         for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
3515                                         ac->high_zoneidx, ac->nodemask) {
3516                 if (last_pgdat != zone->zone_pgdat)
3517                         wakeup_kswapd(zone, order, ac->high_zoneidx);
3518                 last_pgdat = zone->zone_pgdat;
3519         }
3520 }
3521
3522 static inline unsigned int
3523 gfp_to_alloc_flags(gfp_t gfp_mask)
3524 {
3525         unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
3526
3527         /* __GFP_HIGH is assumed to be the same as ALLOC_HIGH to save a branch. */
3528         BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_HIGH);
3529
3530         /*
3531          * The caller may dip into page reserves a bit more if the caller
3532          * cannot run direct reclaim, or if the caller has realtime scheduling
3533          * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
3534          * set both ALLOC_HARDER (__GFP_ATOMIC) and ALLOC_HIGH (__GFP_HIGH).
3535          */
3536         alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);
3537
3538         if (gfp_mask & __GFP_ATOMIC) {
3539                 /*
3540                  * Not worth trying to allocate harder for __GFP_NOMEMALLOC even
3541                  * if it can't schedule.
3542                  */
3543                 if (!(gfp_mask & __GFP_NOMEMALLOC))
3544                         alloc_flags |= ALLOC_HARDER;
3545                 /*
3546     &