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