mm/page_alloc.c

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