page_alloc.c 186 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0-only
Linus Torvalds's avatar
Linus Torvalds committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/*
 *  linux/mm/page_alloc.c
 *
 *  Manages the free list, the system allocates free pages here.
 *  Note that kmalloc() lives in slab.c
 *
 *  Copyright (C) 1991, 1992, 1993, 1994  Linus Torvalds
 *  Swap reorganised 29.12.95, Stephen Tweedie
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999
 *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
 *  Zone balancing, Kanoj Sarcar, SGI, Jan 2000
 *  Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002
 *          (lots of bits borrowed from Ingo Molnar & Andrew Morton)
 */

#include <linux/stddef.h>
#include <linux/mm.h>
20
#include <linux/highmem.h>
Linus Torvalds's avatar
Linus Torvalds committed
21
#include <linux/interrupt.h>
22
#include <linux/jiffies.h>
Linus Torvalds's avatar
Linus Torvalds committed
23
#include <linux/compiler.h>
24
#include <linux/kernel.h>
25
#include <linux/kasan.h>
26
#include <linux/kmsan.h>
Linus Torvalds's avatar
Linus Torvalds committed
27 28
#include <linux/module.h>
#include <linux/suspend.h>
29
#include <linux/ratelimit.h>
30
#include <linux/oom.h>
Linus Torvalds's avatar
Linus Torvalds committed
31 32 33 34
#include <linux/topology.h>
#include <linux/sysctl.h>
#include <linux/cpu.h>
#include <linux/cpuset.h>
35
#include <linux/memory_hotplug.h>
Linus Torvalds's avatar
Linus Torvalds committed
36
#include <linux/nodemask.h>
37
#include <linux/vmstat.h>
38
#include <linux/fault-inject.h>
39
#include <linux/compaction.h>
40
#include <trace/events/kmem.h>
41
#include <trace/events/oom.h>
42
#include <linux/prefetch.h>
43
#include <linux/mm_inline.h>
44
#include <linux/mmu_notifier.h>
45
#include <linux/migrate.h>
46
#include <linux/sched/mm.h>
47
#include <linux/page_owner.h>
Pasha Tatashin's avatar
Pasha Tatashin committed
48
#include <linux/page_table_check.h>
49
#include <linux/memcontrol.h>
50
#include <linux/ftrace.h>
51
#include <linux/lockdep.h>
52
#include <linux/psi.h>
53
#include <linux/khugepaged.h>
54
#include <linux/delayacct.h>
55
#include <asm/div64.h>
Linus Torvalds's avatar
Linus Torvalds committed
56
#include "internal.h"
57
#include "shuffle.h"
58
#include "page_reporting.h"
Linus Torvalds's avatar
Linus Torvalds committed
59

60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
/* Free Page Internal flags: for internal, non-pcp variants of free_pages(). */
typedef int __bitwise fpi_t;

/* No special request */
#define FPI_NONE		((__force fpi_t)0)

/*
 * Skip free page reporting notification for the (possibly merged) page.
 * This does not hinder free page reporting from grabbing the page,
 * reporting it and marking it "reported" -  it only skips notifying
 * the free page reporting infrastructure about a newly freed page. For
 * example, used when temporarily pulling a page from a freelist and
 * putting it back unmodified.
 */
#define FPI_SKIP_REPORT_NOTIFY	((__force fpi_t)BIT(0))

76 77 78 79 80 81 82 83 84 85 86 87
/*
 * Place the (possibly merged) page to the tail of the freelist. Will ignore
 * page shuffling (relevant code - e.g., memory onlining - is expected to
 * shuffle the whole zone).
 *
 * Note: No code should rely on this flag for correctness - it's purely
 *       to allow for optimizations when handing back either fresh pages
 *       (memory onlining) or untouched pages (page isolation, free page
 *       reporting).
 */
#define FPI_TO_TAIL		((__force fpi_t)BIT(1))

88 89
/* prevent >1 _updater_ of zone percpu pageset ->high and ->batch fields */
static DEFINE_MUTEX(pcp_batch_high_lock);
90
#define MIN_PERCPU_PAGELIST_HIGH_FRACTION (8)
91

92 93 94 95 96 97 98 99 100 101 102 103 104 105
#if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT_RT)
/*
 * On SMP, spin_trylock is sufficient protection.
 * On PREEMPT_RT, spin_trylock is equivalent on both SMP and UP.
 */
#define pcp_trylock_prepare(flags)	do { } while (0)
#define pcp_trylock_finish(flag)	do { } while (0)
#else

/* UP spin_trylock always succeeds so disable IRQs to prevent re-entrancy. */
#define pcp_trylock_prepare(flags)	local_irq_save(flags)
#define pcp_trylock_finish(flags)	local_irq_restore(flags)
#endif

106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
/*
 * Locking a pcp requires a PCP lookup followed by a spinlock. To avoid
 * a migration causing the wrong PCP to be locked and remote memory being
 * potentially allocated, pin the task to the CPU for the lookup+lock.
 * preempt_disable is used on !RT because it is faster than migrate_disable.
 * migrate_disable is used on RT because otherwise RT spinlock usage is
 * interfered with and a high priority task cannot preempt the allocator.
 */
#ifndef CONFIG_PREEMPT_RT
#define pcpu_task_pin()		preempt_disable()
#define pcpu_task_unpin()	preempt_enable()
#else
#define pcpu_task_pin()		migrate_disable()
#define pcpu_task_unpin()	migrate_enable()
#endif
121

122 123 124 125 126 127 128 129 130 131 132 133 134
/*
 * Generic helper to lookup and a per-cpu variable with an embedded spinlock.
 * Return value should be used with equivalent unlock helper.
 */
#define pcpu_spin_lock(type, member, ptr)				\
({									\
	type *_ret;							\
	pcpu_task_pin();						\
	_ret = this_cpu_ptr(ptr);					\
	spin_lock(&_ret->member);					\
	_ret;								\
})

135
#define pcpu_spin_trylock(type, member, ptr)				\
136 137 138 139
({									\
	type *_ret;							\
	pcpu_task_pin();						\
	_ret = this_cpu_ptr(ptr);					\
140
	if (!spin_trylock(&_ret->member)) {				\
141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
		pcpu_task_unpin();					\
		_ret = NULL;						\
	}								\
	_ret;								\
})

#define pcpu_spin_unlock(member, ptr)					\
({									\
	spin_unlock(&ptr->member);					\
	pcpu_task_unpin();						\
})

/* struct per_cpu_pages specific helpers. */
#define pcp_spin_lock(ptr)						\
	pcpu_spin_lock(struct per_cpu_pages, lock, ptr)

157 158
#define pcp_spin_trylock(ptr)						\
	pcpu_spin_trylock(struct per_cpu_pages, lock, ptr)
159 160 161 162

#define pcp_spin_unlock(ptr)						\
	pcpu_spin_unlock(lock, ptr)

163 164 165 166 167
#ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
DEFINE_PER_CPU(int, numa_node);
EXPORT_PER_CPU_SYMBOL(numa_node);
#endif

168 169
DEFINE_STATIC_KEY_TRUE(vm_numa_stat_key);

170 171 172 173 174 175 176 177 178 179 180
#ifdef CONFIG_HAVE_MEMORYLESS_NODES
/*
 * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
 * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
 * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
 * defined in <linux/topology.h>.
 */
DEFINE_PER_CPU(int, _numa_mem_);		/* Kernel "local memory" node */
EXPORT_PER_CPU_SYMBOL(_numa_mem_);
#endif

181
static DEFINE_MUTEX(pcpu_drain_mutex);
182

183
#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
184
volatile unsigned long latent_entropy __latent_entropy;
185 186 187
EXPORT_SYMBOL(latent_entropy);
#endif

Linus Torvalds's avatar
Linus Torvalds committed
188
/*
189
 * Array of node states.
Linus Torvalds's avatar
Linus Torvalds committed
190
 */
191 192 193 194 195 196 197
nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
	[N_POSSIBLE] = NODE_MASK_ALL,
	[N_ONLINE] = { { [0] = 1UL } },
#ifndef CONFIG_NUMA
	[N_NORMAL_MEMORY] = { { [0] = 1UL } },
#ifdef CONFIG_HIGHMEM
	[N_HIGH_MEMORY] = { { [0] = 1UL } },
198 199
#endif
	[N_MEMORY] = { { [0] = 1UL } },
200 201 202 203 204
	[N_CPU] = { { [0] = 1UL } },
#endif	/* NUMA */
};
EXPORT_SYMBOL(node_states);

205
gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
206

207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
/*
 * A cached value of the page's pageblock's migratetype, used when the page is
 * put on a pcplist. Used to avoid the pageblock migratetype lookup when
 * freeing from pcplists in most cases, at the cost of possibly becoming stale.
 * Also the migratetype set in the page does not necessarily match the pcplist
 * index, e.g. page might have MIGRATE_CMA set but be on a pcplist with any
 * other index - this ensures that it will be put on the correct CMA freelist.
 */
static inline int get_pcppage_migratetype(struct page *page)
{
	return page->index;
}

static inline void set_pcppage_migratetype(struct page *page, int migratetype)
{
	page->index = migratetype;
}

225
#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
226
unsigned int pageblock_order __read_mostly;
227 228
#endif

229 230
static void __free_pages_ok(struct page *page, unsigned int order,
			    fpi_t fpi_flags);
231

Linus Torvalds's avatar
Linus Torvalds committed
232 233 234 235 236 237
/*
 * results with 256, 32 in the lowmem_reserve sysctl:
 *	1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
 *	1G machine -> (16M dma, 784M normal, 224M high)
 *	NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
 *	HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
Yaowei Bai's avatar
Yaowei Bai committed
238
 *	HIGHMEM allocation will leave (224M+784M)/256 of ram reserved in ZONE_DMA
239 240 241
 *
 * TBD: should special case ZONE_DMA32 machines here - in those we normally
 * don't need any ZONE_NORMAL reservation
Linus Torvalds's avatar
Linus Torvalds committed
242
 */
243
static int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES] = {
244
#ifdef CONFIG_ZONE_DMA
245
	[ZONE_DMA] = 256,
246
#endif
247
#ifdef CONFIG_ZONE_DMA32
248
	[ZONE_DMA32] = 256,
249
#endif
250
	[ZONE_NORMAL] = 32,
251
#ifdef CONFIG_HIGHMEM
252
	[ZONE_HIGHMEM] = 0,
253
#endif
254
	[ZONE_MOVABLE] = 0,
255
};
Linus Torvalds's avatar
Linus Torvalds committed
256

257
char * const zone_names[MAX_NR_ZONES] = {
258
#ifdef CONFIG_ZONE_DMA
259
	 "DMA",
260
#endif
261
#ifdef CONFIG_ZONE_DMA32
262
	 "DMA32",
263
#endif
264
	 "Normal",
265
#ifdef CONFIG_HIGHMEM
Mel Gorman's avatar
Mel Gorman committed
266
	 "HighMem",
267
#endif
Mel Gorman's avatar
Mel Gorman committed
268
	 "Movable",
269 270 271
#ifdef CONFIG_ZONE_DEVICE
	 "Device",
#endif
272 273
};

274
const char * const migratetype_names[MIGRATE_TYPES] = {
275 276 277 278 279 280 281 282 283 284 285 286
	"Unmovable",
	"Movable",
	"Reclaimable",
	"HighAtomic",
#ifdef CONFIG_CMA
	"CMA",
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	"Isolate",
#endif
};

287
static compound_page_dtor * const compound_page_dtors[NR_COMPOUND_DTORS] = {
288 289
	[NULL_COMPOUND_DTOR] = NULL,
	[COMPOUND_PAGE_DTOR] = free_compound_page,
290
#ifdef CONFIG_HUGETLB_PAGE
291
	[HUGETLB_PAGE_DTOR] = free_huge_page,
292
#endif
293
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
294
	[TRANSHUGE_PAGE_DTOR] = free_transhuge_page,
295
#endif
296 297
};

Linus Torvalds's avatar
Linus Torvalds committed
298
int min_free_kbytes = 1024;
299
int user_min_free_kbytes = -1;
300 301
static int watermark_boost_factor __read_mostly = 15000;
static int watermark_scale_factor = 10;
Tejun Heo's avatar
Tejun Heo committed
302 303 304 305

/* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
int movable_zone;
EXPORT_SYMBOL(movable_zone);
306

307
#if MAX_NUMNODES > 1
308
unsigned int nr_node_ids __read_mostly = MAX_NUMNODES;
309
unsigned int nr_online_nodes __read_mostly = 1;
310
EXPORT_SYMBOL(nr_node_ids);
311
EXPORT_SYMBOL(nr_online_nodes);
312 313
#endif

314 315 316 317 318 319
static bool page_contains_unaccepted(struct page *page, unsigned int order);
static void accept_page(struct page *page, unsigned int order);
static bool try_to_accept_memory(struct zone *zone, unsigned int order);
static inline bool has_unaccepted_memory(void);
static bool __free_unaccepted(struct page *page);

320 321
int page_group_by_mobility_disabled __read_mostly;

322
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
323 324 325 326 327
/*
 * During boot we initialize deferred pages on-demand, as needed, but once
 * page_alloc_init_late() has finished, the deferred pages are all initialized,
 * and we can permanently disable that path.
 */
328
DEFINE_STATIC_KEY_TRUE(deferred_pages);
329

330
static inline bool deferred_pages_enabled(void)
331
{
332
	return static_branch_unlikely(&deferred_pages);
333 334
}

335
/*
336 337 338 339
 * deferred_grow_zone() is __init, but it is called from
 * get_page_from_freelist() during early boot until deferred_pages permanently
 * disables this call. This is why we have refdata wrapper to avoid warning,
 * and to ensure that the function body gets unloaded.
340
 */
341 342
static bool __ref
_deferred_grow_zone(struct zone *zone, unsigned int order)
343
{
344
       return deferred_grow_zone(zone, order);
345 346
}
#else
347
static inline bool deferred_pages_enabled(void)
348
{
349
	return false;
350
}
351
#endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
352

353
/* Return a pointer to the bitmap storing bits affecting a block of pages */
354
static inline unsigned long *get_pageblock_bitmap(const struct page *page,
355 356 357
							unsigned long pfn)
{
#ifdef CONFIG_SPARSEMEM
358
	return section_to_usemap(__pfn_to_section(pfn));
359 360 361 362 363
#else
	return page_zone(page)->pageblock_flags;
#endif /* CONFIG_SPARSEMEM */
}

364
static inline int pfn_to_bitidx(const struct page *page, unsigned long pfn)
365 366 367 368
{
#ifdef CONFIG_SPARSEMEM
	pfn &= (PAGES_PER_SECTION-1);
#else
369
	pfn = pfn - pageblock_start_pfn(page_zone(page)->zone_start_pfn);
370
#endif /* CONFIG_SPARSEMEM */
371
	return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
372 373
}

374
static __always_inline
375
unsigned long __get_pfnblock_flags_mask(const struct page *page,
376 377 378 379 380 381 382 383 384 385 386
					unsigned long pfn,
					unsigned long mask)
{
	unsigned long *bitmap;
	unsigned long bitidx, word_bitidx;
	unsigned long word;

	bitmap = get_pageblock_bitmap(page, pfn);
	bitidx = pfn_to_bitidx(page, pfn);
	word_bitidx = bitidx / BITS_PER_LONG;
	bitidx &= (BITS_PER_LONG-1);
387 388 389 390 391 392
	/*
	 * This races, without locks, with set_pfnblock_flags_mask(). Ensure
	 * a consistent read of the memory array, so that results, even though
	 * racy, are not corrupted.
	 */
	word = READ_ONCE(bitmap[word_bitidx]);
393
	return (word >> bitidx) & mask;
394 395
}

396 397 398 399 400 401 402 403
/**
 * get_pfnblock_flags_mask - Return the requested group of flags for the pageblock_nr_pages block of pages
 * @page: The page within the block of interest
 * @pfn: The target page frame number
 * @mask: mask of bits that the caller is interested in
 *
 * Return: pageblock_bits flags
 */
404 405
unsigned long get_pfnblock_flags_mask(const struct page *page,
					unsigned long pfn, unsigned long mask)
406
{
407
	return __get_pfnblock_flags_mask(page, pfn, mask);
408 409
}

410 411
static __always_inline int get_pfnblock_migratetype(const struct page *page,
					unsigned long pfn)
412
{
413
	return __get_pfnblock_flags_mask(page, pfn, MIGRATETYPE_MASK);
414 415 416 417 418 419 420 421 422 423 424 425 426 427 428
}

/**
 * set_pfnblock_flags_mask - Set the requested group of flags for a pageblock_nr_pages block of pages
 * @page: The page within the block of interest
 * @flags: The flags to set
 * @pfn: The target page frame number
 * @mask: mask of bits that the caller is interested in
 */
void set_pfnblock_flags_mask(struct page *page, unsigned long flags,
					unsigned long pfn,
					unsigned long mask)
{
	unsigned long *bitmap;
	unsigned long bitidx, word_bitidx;
429
	unsigned long word;
430 431

	BUILD_BUG_ON(NR_PAGEBLOCK_BITS != 4);
432
	BUILD_BUG_ON(MIGRATE_TYPES > (1 << PB_migratetype_bits));
433 434 435 436 437 438 439 440

	bitmap = get_pageblock_bitmap(page, pfn);
	bitidx = pfn_to_bitidx(page, pfn);
	word_bitidx = bitidx / BITS_PER_LONG;
	bitidx &= (BITS_PER_LONG-1);

	VM_BUG_ON_PAGE(!zone_spans_pfn(page_zone(page), pfn), page);

441 442
	mask <<= bitidx;
	flags <<= bitidx;
443 444

	word = READ_ONCE(bitmap[word_bitidx]);
445 446
	do {
	} while (!try_cmpxchg(&bitmap[word_bitidx], &word, (word & ~mask) | flags));
447
}
448

449
void set_pageblock_migratetype(struct page *page, int migratetype)
450
{
451 452
	if (unlikely(page_group_by_mobility_disabled &&
		     migratetype < MIGRATE_PCPTYPES))
453 454
		migratetype = MIGRATE_UNMOVABLE;

455
	set_pfnblock_flags_mask(page, (unsigned long)migratetype,
456
				page_to_pfn(page), MIGRATETYPE_MASK);
457 458
}

Nick Piggin's avatar
Nick Piggin committed
459
#ifdef CONFIG_DEBUG_VM
460
static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
461
{
462 463 464
	int ret = 0;
	unsigned seq;
	unsigned long pfn = page_to_pfn(page);
465
	unsigned long sp, start_pfn;
466

467 468
	do {
		seq = zone_span_seqbegin(zone);
469 470
		start_pfn = zone->zone_start_pfn;
		sp = zone->spanned_pages;
471
		if (!zone_spans_pfn(zone, pfn))
472 473 474
			ret = 1;
	} while (zone_span_seqretry(zone, seq));

475
	if (ret)
476 477 478
		pr_err("page 0x%lx outside node %d zone %s [ 0x%lx - 0x%lx ]\n",
			pfn, zone_to_nid(zone), zone->name,
			start_pfn, start_pfn + sp);
479

480
	return ret;
481 482 483 484 485
}

/*
 * Temporary debugging check for pages not lying within a given zone.
 */
486
static int __maybe_unused bad_range(struct zone *zone, struct page *page)
487 488
{
	if (page_outside_zone_boundaries(zone, page))
Linus Torvalds's avatar
Linus Torvalds committed
489
		return 1;
490
	if (zone != page_zone(page))
491 492
		return 1;

Linus Torvalds's avatar
Linus Torvalds committed
493 494
	return 0;
}
Nick Piggin's avatar
Nick Piggin committed
495
#else
496
static inline int __maybe_unused bad_range(struct zone *zone, struct page *page)
Nick Piggin's avatar
Nick Piggin committed
497 498 499 500 501
{
	return 0;
}
#endif

502
static void bad_page(struct page *page, const char *reason)
Linus Torvalds's avatar
Linus Torvalds committed
503
{
504 505 506 507 508 509 510 511 512 513 514 515 516 517
	static unsigned long resume;
	static unsigned long nr_shown;
	static unsigned long nr_unshown;

	/*
	 * Allow a burst of 60 reports, then keep quiet for that minute;
	 * or allow a steady drip of one report per second.
	 */
	if (nr_shown == 60) {
		if (time_before(jiffies, resume)) {
			nr_unshown++;
			goto out;
		}
		if (nr_unshown) {
518
			pr_alert(
519
			      "BUG: Bad page state: %lu messages suppressed\n",
520 521 522 523 524 525 526 527
				nr_unshown);
			nr_unshown = 0;
		}
		nr_shown = 0;
	}
	if (nr_shown++ == 0)
		resume = jiffies + 60 * HZ;

528
	pr_alert("BUG: Bad page state in process %s  pfn:%05lx\n",
529
		current->comm, page_to_pfn(page));
530
	dump_page(page, reason);
531

532
	print_modules();
Linus Torvalds's avatar
Linus Torvalds committed
533
	dump_stack();
534
out:
535
	/* Leave bad fields for debug, except PageBuddy could make trouble */
536
	page_mapcount_reset(page); /* remove PageBuddy */
537
	add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE);
Linus Torvalds's avatar
Linus Torvalds committed
538 539
}

540 541 542 543 544 545 546
static inline unsigned int order_to_pindex(int migratetype, int order)
{
	int base = order;

#ifdef CONFIG_TRANSPARENT_HUGEPAGE
	if (order > PAGE_ALLOC_COSTLY_ORDER) {
		VM_BUG_ON(order != pageblock_order);
547
		return NR_LOWORDER_PCP_LISTS;
548 549 550 551 552 553 554 555 556 557 558 559 560
	}
#else
	VM_BUG_ON(order > PAGE_ALLOC_COSTLY_ORDER);
#endif

	return (MIGRATE_PCPTYPES * base) + migratetype;
}

static inline int pindex_to_order(unsigned int pindex)
{
	int order = pindex / MIGRATE_PCPTYPES;

#ifdef CONFIG_TRANSPARENT_HUGEPAGE
561
	if (pindex == NR_LOWORDER_PCP_LISTS)
562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580
		order = pageblock_order;
#else
	VM_BUG_ON(order > PAGE_ALLOC_COSTLY_ORDER);
#endif

	return order;
}

static inline bool pcp_allowed_order(unsigned int order)
{
	if (order <= PAGE_ALLOC_COSTLY_ORDER)
		return true;
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
	if (order == pageblock_order)
		return true;
#endif
	return false;
}

581 582
static inline void free_the_page(struct page *page, unsigned int order)
{
583 584
	if (pcp_allowed_order(order))		/* Via pcp? */
		free_unref_page(page, order);
585 586 587 588
	else
		__free_pages_ok(page, order, FPI_NONE);
}

Linus Torvalds's avatar
Linus Torvalds committed
589 590 591
/*
 * Higher-order pages are called "compound pages".  They are structured thusly:
 *
592
 * The first PAGE_SIZE page is called the "head page" and have PG_head set.
Linus Torvalds's avatar
Linus Torvalds committed
593
 *
594 595
 * The remaining PAGE_SIZE pages are called "tail pages". PageTail() is encoded
 * in bit 0 of page->compound_head. The rest of bits is pointer to head page.
Linus Torvalds's avatar
Linus Torvalds committed
596
 *
597 598
 * The first tail page's ->compound_dtor holds the offset in array of compound
 * page destructors. See compound_page_dtors.
Linus Torvalds's avatar
Linus Torvalds committed
599
 *
600
 * The first tail page's ->compound_order holds the order of allocation.
601
 * This usage means that zero-order pages may not be compound.
Linus Torvalds's avatar
Linus Torvalds committed
602
 */
603

604
void free_compound_page(struct page *page)
605
{
606
	mem_cgroup_uncharge(page_folio(page));
607
	free_the_page(page, compound_order(page));
608 609
}

610
void prep_compound_page(struct page *page, unsigned int order)
611 612 613 614 615
{
	int i;
	int nr_pages = 1 << order;

	__SetPageHead(page);
616 617
	for (i = 1; i < nr_pages; i++)
		prep_compound_tail(page, i);
618

619
	prep_compound_head(page, order);
620 621
}

622 623
void destroy_large_folio(struct folio *folio)
{
624
	enum compound_dtor_id dtor = folio->_folio_dtor;
625 626 627 628 629

	VM_BUG_ON_FOLIO(dtor >= NR_COMPOUND_DTORS, folio);
	compound_page_dtors[dtor](&folio->page);
}

630
static inline void set_buddy_order(struct page *page, unsigned int order)
631
{
632
	set_page_private(page, order);
633
	__SetPageBuddy(page);
Linus Torvalds's avatar
Linus Torvalds committed
634 635
}

636 637 638 639 640
#ifdef CONFIG_COMPACTION
static inline struct capture_control *task_capc(struct zone *zone)
{
	struct capture_control *capc = current->capture_control;

641
	return unlikely(capc) &&
642 643
		!(current->flags & PF_KTHREAD) &&
		!capc->page &&
644
		capc->cc->zone == zone ? capc : NULL;
645 646 647 648 649 650 651 652 653 654 655 656 657 658 659
}

static inline bool
compaction_capture(struct capture_control *capc, struct page *page,
		   int order, int migratetype)
{
	if (!capc || order != capc->cc->order)
		return false;

	/* Do not accidentally pollute CMA or isolated regions*/
	if (is_migrate_cma(migratetype) ||
	    is_migrate_isolate(migratetype))
		return false;

	/*
Ingo Molnar's avatar
Ingo Molnar committed
660
	 * Do not let lower order allocations pollute a movable pageblock.
661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685
	 * This might let an unmovable request use a reclaimable pageblock
	 * and vice-versa but no more than normal fallback logic which can
	 * have trouble finding a high-order free page.
	 */
	if (order < pageblock_order && migratetype == MIGRATE_MOVABLE)
		return false;

	capc->page = page;
	return true;
}

#else
static inline struct capture_control *task_capc(struct zone *zone)
{
	return NULL;
}

static inline bool
compaction_capture(struct capture_control *capc, struct page *page,
		   int order, int migratetype)
{
	return false;
}
#endif /* CONFIG_COMPACTION */

686 687 688 689 690 691
/* Used for pages not on another list */
static inline void add_to_free_list(struct page *page, struct zone *zone,
				    unsigned int order, int migratetype)
{
	struct free_area *area = &zone->free_area[order];

692
	list_add(&page->buddy_list, &area->free_list[migratetype]);
693 694 695 696 697 698 699 700 701
	area->nr_free++;
}

/* Used for pages not on another list */
static inline void add_to_free_list_tail(struct page *page, struct zone *zone,
					 unsigned int order, int migratetype)
{
	struct free_area *area = &zone->free_area[order];

702
	list_add_tail(&page->buddy_list, &area->free_list[migratetype]);
703 704 705
	area->nr_free++;
}

706 707 708 709 710
/*
 * Used for pages which are on another list. Move the pages to the tail
 * of the list - so the moved pages won't immediately be considered for
 * allocation again (e.g., optimization for memory onlining).
 */
711 712 713 714 715
static inline void move_to_free_list(struct page *page, struct zone *zone,
				     unsigned int order, int migratetype)
{
	struct free_area *area = &zone->free_area[order];

716
	list_move_tail(&page->buddy_list, &area->free_list[migratetype]);
717 718 719 720 721
}

static inline void del_page_from_free_list(struct page *page, struct zone *zone,
					   unsigned int order)
{
722 723 724 725
	/* clear reported state and update reported page count */
	if (page_reported(page))
		__ClearPageReported(page);

726
	list_del(&page->buddy_list);
727 728 729 730 731
	__ClearPageBuddy(page);
	set_page_private(page, 0);
	zone->free_area[order].nr_free--;
}

732 733 734 735
static inline struct page *get_page_from_free_area(struct free_area *area,
					    int migratetype)
{
	return list_first_entry_or_null(&area->free_list[migratetype],
736
					struct page, buddy_list);
737 738
}

739 740 741 742 743 744 745 746 747 748 749 750
/*
 * If this is not the largest possible page, check if the buddy
 * of the next-highest order is free. If it is, it's possible
 * that pages are being freed that will coalesce soon. In case,
 * that is happening, add the free page to the tail of the list
 * so it's less likely to be used soon and more likely to be merged
 * as a higher order page
 */
static inline bool
buddy_merge_likely(unsigned long pfn, unsigned long buddy_pfn,
		   struct page *page, unsigned int order)
{
751 752
	unsigned long higher_page_pfn;
	struct page *higher_page;
753

754
	if (order >= MAX_ORDER - 1)
755 756
		return false;

757 758
	higher_page_pfn = buddy_pfn & pfn;
	higher_page = page + (higher_page_pfn - pfn);
759

760 761
	return find_buddy_page_pfn(higher_page, higher_page_pfn, order + 1,
			NULL) != NULL;
762 763
}

Linus Torvalds's avatar
Linus Torvalds committed
764 765 766 767 768 769 770 771 772 773 774 775 776
/*
 * Freeing function for a buddy system allocator.
 *
 * The concept of a buddy system is to maintain direct-mapped table
 * (containing bit values) for memory blocks of various "orders".
 * The bottom level table contains the map for the smallest allocatable
 * units of memory (here, pages), and each level above it describes
 * pairs of units from the levels below, hence, "buddies".
 * At a high level, all that happens here is marking the table entry
 * at the bottom level available, and propagating the changes upward
 * as necessary, plus some accounting needed to play nicely with other
 * parts of the VM system.
 * At each level, we keep a list of pages, which are heads of continuous
777 778
 * free pages of length of (1 << order) and marked with PageBuddy.
 * Page's order is recorded in page_private(page) field.
Linus Torvalds's avatar
Linus Torvalds committed
779
 * So when we are allocating or freeing one, we can derive the state of the
780 781
 * other.  That is, if we allocate a small block, and both were
 * free, the remainder of the region must be split into blocks.
Linus Torvalds's avatar
Linus Torvalds committed
782
 * If a block is freed, and its buddy is also free, then this
783
 * triggers coalescing into a block of larger size.
Linus Torvalds's avatar
Linus Torvalds committed
784
 *
785
 * -- nyc
Linus Torvalds's avatar
Linus Torvalds committed
786 787
 */

Nick Piggin's avatar
Nick Piggin committed
788
static inline void __free_one_page(struct page *page,
789
		unsigned long pfn,
790
		struct zone *zone, unsigned int order,
791
		int migratetype, fpi_t fpi_flags)
Linus Torvalds's avatar
Linus Torvalds committed
792
{
793
	struct capture_control *capc = task_capc(zone);
794
	unsigned long buddy_pfn = 0;
795 796 797
	unsigned long combined_pfn;
	struct page *buddy;
	bool to_tail;
798

799
	VM_BUG_ON(!zone_is_initialized(zone));
800
	VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);
Linus Torvalds's avatar
Linus Torvalds committed
801

802
	VM_BUG_ON(migratetype == -1);
803
	if (likely(!is_migrate_isolate(migratetype)))
804
		__mod_zone_freepage_state(zone, 1 << order, migratetype);
805

806
	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
807
	VM_BUG_ON_PAGE(bad_range(zone, page), page);
Linus Torvalds's avatar
Linus Torvalds committed
808

809
	while (order < MAX_ORDER) {
810 811 812 813 814
		if (compaction_capture(capc, page, order, migratetype)) {
			__mod_zone_freepage_state(zone, -(1 << order),
								migratetype);
			return;
		}
815

816 817
		buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn);
		if (!buddy)
818
			goto done_merging;
819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834

		if (unlikely(order >= pageblock_order)) {
			/*
			 * We want to prevent merge between freepages on pageblock
			 * without fallbacks and normal pageblock. Without this,
			 * pageblock isolation could cause incorrect freepage or CMA
			 * accounting or HIGHATOMIC accounting.
			 */
			int buddy_mt = get_pageblock_migratetype(buddy);

			if (migratetype != buddy_mt
					&& (!migratetype_is_mergeable(migratetype) ||
						!migratetype_is_mergeable(buddy_mt)))
				goto done_merging;
		}

835 836 837 838
		/*
		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
		 * merge with it and move up one order.
		 */
839
		if (page_is_guard(buddy))
840
			clear_page_guard(zone, buddy, order, migratetype);
841
		else
842
			del_page_from_free_list(buddy, zone, order);
843 844 845
		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
Linus Torvalds's avatar
Linus Torvalds committed
846 847
		order++;
	}
848 849

done_merging:
850
	set_buddy_order(page, order);
851

852 853 854
	if (fpi_flags & FPI_TO_TAIL)
		to_tail = true;
	else if (is_shuffle_order(order))
855
		to_tail = shuffle_pick_tail();
856
	else
857
		to_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);
858

859
	if (to_tail)
860
		add_to_free_list_tail(page, zone, order, migratetype);
861
	else
862
		add_to_free_list(page, zone, order, migratetype);
863 864

	/* Notify page reporting subsystem of freed page */
865
	if (!(fpi_flags & FPI_SKIP_REPORT_NOTIFY))
866
		page_reporting_notify_free(order);
Linus Torvalds's avatar
Linus Torvalds committed
867 868
}

869 870 871 872 873 874
/**
 * split_free_page() -- split a free page at split_pfn_offset
 * @free_page:		the original free page
 * @order:		the order of the page
 * @split_pfn_offset:	split offset within the page
 *
875 876
 * Return -ENOENT if the free page is changed, otherwise 0
 *
877 878 879 880 881
 * It is used when the free page crosses two pageblocks with different migratetypes
 * at split_pfn_offset within the page. The split free page will be put into
 * separate migratetype lists afterwards. Otherwise, the function achieves
 * nothing.
 */
882 883
int split_free_page(struct page *free_page,
			unsigned int order, unsigned long split_pfn_offset)
884 885 886 887 888 889
{
	struct zone *zone = page_zone(free_page);
	unsigned long free_page_pfn = page_to_pfn(free_page);
	unsigned long pfn;
	unsigned long flags;
	int free_page_order;
890 891
	int mt;
	int ret = 0;
892

893
	if (split_pfn_offset == 0)
894
		return ret;
895

896
	spin_lock_irqsave(&zone->lock, flags);
897 898 899 900 901 902 903 904 905 906

	if (!PageBuddy(free_page) || buddy_order(free_page) != order) {
		ret = -ENOENT;
		goto out;
	}

	mt = get_pageblock_migratetype(free_page);
	if (likely(!is_migrate_isolate(mt)))
		__mod_zone_freepage_state(zone, -(1UL << order), mt);

907 908 909 910 911
	del_page_from_free_list(free_page, zone, order);
	for (pfn = free_page_pfn;
	     pfn < free_page_pfn + (1UL << order);) {
		int mt = get_pfnblock_migratetype(pfn_to_page(pfn), pfn);

912
		free_page_order = min_t(unsigned int,
913 914
					pfn ? __ffs(pfn) : order,
					__fls(split_pfn_offset));
915 916 917 918 919 920 921 922
		__free_one_page(pfn_to_page(pfn), pfn, zone, free_page_order,
				mt, FPI_NONE);
		pfn += 1UL << free_page_order;
		split_pfn_offset -= (1UL << free_page_order);
		/* we have done the first part, now switch to second part */
		if (split_pfn_offset == 0)
			split_pfn_offset = (1UL << order) - (pfn - free_page_pfn);
	}
923
out:
924
	spin_unlock_irqrestore(&zone->lock, flags);
925
	return ret;
926
}
927 928 929 930 931 932 933 934 935 936 937 938 939 940
/*
 * A bad page could be due to a number of fields. Instead of multiple branches,
 * try and check multiple fields with one check. The caller must do a detailed
 * check if necessary.
 */
static inline bool page_expected_state(struct page *page,
					unsigned long check_flags)
{
	if (unlikely(atomic_read(&page->_mapcount) != -1))
		return false;

	if (unlikely((unsigned long)page->mapping |
			page_ref_count(page) |
#ifdef CONFIG_MEMCG
941
			page->memcg_data |
942 943 944 945 946 947 948
#endif
			(page->flags & check_flags)))
		return false;

	return true;
}

949
static const char *page_bad_reason(struct page *page, unsigned long flags)
Linus Torvalds's avatar
Linus Torvalds committed
950
{
951
	const char *bad_reason = NULL;
952

953
	if (unlikely(atomic_read(&page->_mapcount) != -1))
954 955 956
		bad_reason = "nonzero mapcount";
	if (unlikely(page->mapping != NULL))
		bad_reason = "non-NULL mapping";
957
	if (unlikely(page_ref_count(page) != 0))
958
		bad_reason = "nonzero _refcount";
959 960 961 962 963
	if (unlikely(page->flags & flags)) {
		if (flags == PAGE_FLAGS_CHECK_AT_PREP)
			bad_reason = "PAGE_FLAGS_CHECK_AT_PREP flag(s) set";
		else
			bad_reason = "PAGE_FLAGS_CHECK_AT_FREE flag(s) set";
964
	}
965
#ifdef CONFIG_MEMCG
966
	if (unlikely(page->memcg_data))
967 968
		bad_reason = "page still charged to cgroup";
#endif
969 970 971
	return bad_reason;
}

972
static void free_page_is_bad_report(struct page *page)
973 974 975
{
	bad_page(page,
		 page_bad_reason(page, PAGE_FLAGS_CHECK_AT_FREE));
976 977
}

978
static inline bool free_page_is_bad(struct page *page)
979
{
980
	if (likely(page_expected_state(page, PAGE_FLAGS_CHECK_AT_FREE)))
981
		return false;
982 983

	/* Something has gone sideways, find it */
984 985
	free_page_is_bad_report(page);
	return true;
Linus Torvalds's avatar
Linus Torvalds committed
986 987
}

988 989 990 991 992
static inline bool is_check_pages_enabled(void)
{
	return static_branch_unlikely(&check_pages_enabled);
}

993
static int free_tail_page_prepare(struct page *head_page, struct page *page)
994
{
995
	struct folio *folio = (struct folio *)head_page;
996 997 998 999 1000 1001 1002 1003
	int ret = 1;

	/*
	 * We rely page->lru.next never has bit 0 set, unless the page
	 * is PageTail(). Let's make sure that's true even for poisoned ->lru.
	 */
	BUILD_BUG_ON((unsigned long)LIST_POISON1 & 1);

1004
	if (!is_check_pages_enabled()) {
1005 1006 1007 1008 1009
		ret = 0;
		goto out;
	}
	switch (page - head_page) {
	case 1:
1010
		/* the first tail page: these may be in place of ->mapping */
1011 1012
		if (unlikely(folio_entire_mapcount(folio))) {
			bad_page(page, "nonzero entire_mapcount");
1013 1014
			goto out;
		}
1015 1016
		if (unlikely(atomic_read(&folio->_nr_pages_mapped))) {
			bad_page(page, "nonzero nr_pages_mapped");
1017 1018
			goto out;
		}
1019 1020
		if (unlikely(atomic_read(&folio->_pincount))) {
			bad_page(page, "nonzero pincount");
1021 1022
			goto out;
		}
1023 1024 1025 1026
		break;
	case 2:
		/*
		 * the second tail page: ->mapping is
1027
		 * deferred_list.next -- ignore value.
1028 1029 1030 1031
		 */
		break;
	default:
		if (page->mapping != TAIL_MAPPING) {
1032
			bad_page(page, "corrupted mapping in tail page");
1033 1034 1035 1036 1037
			goto out;
		}
		break;
	}
	if (unlikely(!PageTail(page))) {
1038
		bad_page(page, "PageTail not set");
1039 1040 1041
		goto out;
	}
	if (unlikely(compound_head(page) != head_page)) {
1042
		bad_page(page, "compound_head not consistent");
1043 1044 1045 1046 1047 1048 1049 1050 1051
		goto out;
	}
	ret = 0;
out:
	page->mapping = NULL;
	clear_compound_head(page);
	return ret;
}

1052 1053 1054
/*
 * Skip KASAN memory poisoning when either:
 *
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067
 * 1. For generic KASAN: deferred memory initialization has not yet completed.
 *    Tag-based KASAN modes skip pages freed via deferred memory initialization
 *    using page tags instead (see below).
 * 2. For tag-based KASAN modes: the page has a match-all KASAN tag, indicating
 *    that error detection is disabled for accesses via the page address.
 *
 * Pages will have match-all tags in the following circumstances:
 *
 * 1. Pages are being initialized for the first time, including during deferred
 *    memory init; see the call to page_kasan_tag_reset in __init_single_page.
 * 2. The allocation was not unpoisoned due to __GFP_SKIP_KASAN, with the
 *    exception of pages unpoisoned by kasan_unpoison_vmalloc.
 * 3. The allocation was excluded from being checked due to sampling,
1068
 *    see the call to kasan_unpoison_pages.
1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082
 *
 * Poisoning pages during deferred memory init will greatly lengthen the
 * process and cause problem in large memory systems as the deferred pages
 * initialization is done with interrupt disabled.
 *
 * Assuming that there will be no reference to those newly initialized
 * pages before they are ever allocated, this should have no effect on
 * KASAN memory tracking as the poison will be properly inserted at page
 * allocation time. The only corner case is when pages are allocated by
 * on-demand allocation and then freed again before the deferred pages
 * initialization is done, but this is not likely to happen.
 */
static inline bool should_skip_kasan_poison(struct page *page, fpi_t fpi_flags)
{
1083 1084 1085 1086
	if (IS_ENABLED(CONFIG_KASAN_GENERIC))
		return deferred_pages_enabled();

	return page_kasan_tag(page) == 0xff;
1087 1088
}

1089
static void kernel_init_pages(struct page *page, int numpages)
1090 1091 1092
{
	int i;

1093 1094
	/* s390's use of memset() could override KASAN redzones. */
	kasan_disable_current();
1095 1096
	for (i = 0; i < numpages; i++)
		clear_highpage_kasan_tagged(page + i);
1097
	kasan_enable_current();
1098 1099
}

1100
static __always_inline bool free_pages_prepare(struct page *page,
1101
			unsigned int order, fpi_t fpi_flags)
1102
{
1103
	int bad = 0;
1104
	bool skip_kasan_poison = should_skip_kasan_poison(page, fpi_flags);
1105
	bool init = want_init_on_free();
1106 1107 1108

	VM_BUG_ON_PAGE(PageTail(page), page);

1109
	trace_mm_page_free(page, order);
1110
	kmsan_free_page(page, order);
1111

1112 1113 1114 1115 1116
	if (unlikely(PageHWPoison(page)) && !order) {
		/*
		 * Do not let hwpoison pages hit pcplists/buddy
		 * Untie memcg state and reset page's owner
		 */
1117
		if (memcg_kmem_online() && PageMemcgKmem(page))
1118 1119
			__memcg_kmem_uncharge_page(page, order);
		reset_page_owner(page, order);
Pasha Tatashin's avatar
Pasha Tatashin committed
1120
		page_table_check_free(page, order);
1121 1122 1123
		return false;
	}

1124 1125 1126 1127 1128 1129 1130 1131 1132
	/*
	 * Check tail pages before head page information is cleared to
	 * avoid checking PageCompound for order-0 pages.
	 */
	if (unlikely(order)) {
		bool compound = PageCompound(page);
		int i;

		VM_BUG_ON_PAGE(compound && compound_order(page) != order, page);
1133

1134
		if (compound)
1135
			ClearPageHasHWPoisoned(page);
1136 1137
		for (i = 1; i < (1 << order); i++) {
			if (compound)
1138
				bad += free_tail_page_prepare(page, page + i);
1139
			if (is_check_pages_enabled()) {
1140
				if (free_page_is_bad(page + i)) {
1141 1142 1143
					bad++;
					continue;
				}
1144 1145 1146 1147
			}
			(page + i)->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
		}
	}
1148
	if (PageMappingFlags(page))
1149
		page->mapping = NULL;
1150
	if (memcg_kmem_online() && PageMemcgKmem(page))
1151
		__memcg_kmem_uncharge_page(page, order);
1152
	if (is_check_pages_enabled()) {
1153 1154 1155 1156 1157
		if (free_page_is_bad(page))
			bad++;
		if (bad)
			return false;
	}
1158

1159 1160 1161
	page_cpupid_reset_last(page);
	page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
	reset_page_owner(page, order);
Pasha Tatashin's avatar
Pasha Tatashin committed
1162
	page_table_check_free(page, order);
1163 1164 1165

	if (!PageHighMem(page)) {
		debug_check_no_locks_freed(page_address(page),
1166
					   PAGE_SIZE << order);
1167
		debug_check_no_obj_freed(page_address(page),
1168
					   PAGE_SIZE << order);
1169
	}
1170

1171 1172
	kernel_poison_pages(page, 1 << order);

1173
	/*
1174
	 * As memory initialization might be integrated into KASAN,
1175
	 * KASAN poisoning and memory initialization code must be
1176 1177
	 * kept together to avoid discrepancies in behavior.
	 *
1178 1179 1180
	 * With hardware tag-based KASAN, memory tags must be set before the
	 * page becomes unavailable via debug_pagealloc or arch_free_page.
	 */
1181
	if (!skip_kasan_poison) {
1182
		kasan_poison_pages(page, order, init);
1183

1184 1185 1186 1187 1188
		/* Memory is already initialized if KASAN did it internally. */
		if (kasan_has_integrated_init())
			init = false;
	}
	if (init)
1189
		kernel_init_pages(page, 1 << order);
1190

1191 1192 1193 1194 1195 1196 1197
	/*
	 * arch_free_page() can make the page's contents inaccessible.  s390
	 * does this.  So nothing which can access the page's contents should
	 * happen after this.
	 */
	arch_free_page(page, order);

1198
	debug_pagealloc_unmap_pages(page, 1 << order);
1199

1200 1201 1202
	return true;
}

Linus Torvalds's avatar
Linus Torvalds committed
1203
/*
1204
 * Frees a number of pages from the PCP lists
1205
 * Assumes all pages on list are in same zone.
1206
 * count is the number of pages to free.
Linus Torvalds's avatar
Linus Torvalds committed
1207
 */
1208
static void free_pcppages_bulk(struct zone *zone, int count,
1209 1210
					struct per_cpu_pages *pcp,
					int pindex)
Linus Torvalds's avatar
Linus Torvalds committed
1211
{
1212
	unsigned long flags;
1213 1214
	int min_pindex = 0;
	int max_pindex = NR_PCP_LISTS - 1;
1215
	unsigned int order;
1216
	bool isolated_pageblocks;
1217
	struct page *page;
1218

1219 1220 1221 1222 1223
	/*
	 * Ensure proper count is passed which otherwise would stuck in the
	 * below while (list_empty(list)) loop.
	 */
	count = min(pcp->count, count);
1224 1225 1226 1227

	/* Ensure requested pindex is drained first. */
	pindex = pindex - 1;

1228
	spin_lock_irqsave(&zone->lock, flags);
1229 1230
	isolated_pageblocks = has_isolate_pageblock(zone);

1231
	while (count > 0) {
1232
		struct list_head *list;
1233
		int nr_pages;
1234

1235
		/* Remove pages from lists in a round-robin fashion. */
1236
		do {
1237 1238
			if (++pindex > max_pindex)
				pindex = min_pindex;
1239
			list = &pcp->lists[pindex];
1240 1241 1242 1243 1244 1245 1246 1247
			if (!list_empty(list))
				break;

			if (pindex == max_pindex)
				max_pindex--;
			if (pindex == min_pindex)
				min_pindex++;
		} while (1);
Nick Piggin's avatar
Nick Piggin committed
1248

1249
		order = pindex_to_order(pindex);
1250
		nr_pages = 1 << order;
1251
		do {
1252 1253
			int mt;

1254
			page = list_last_entry(list, struct page, pcp_list);
1255 1256
			mt = get_pcppage_migratetype(page);

1257
			/* must delete to avoid corrupting pcp list */
1258
			list_del(&page->pcp_list);
1259 1260
			count -= nr_pages;
			pcp->count -= nr_pages;
1261

1262 1263 1264 1265 1266
			/* MIGRATE_ISOLATE page should not go to pcplists */
			VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
			/* Pageblock could have been isolated meanwhile */
			if (unlikely(isolated_pageblocks))
				mt = get_pageblock_migratetype(page);
1267

1268 1269 1270
			__free_one_page(page, page_to_pfn(page), zone, order, mt, FPI_NONE);
			trace_mm_page_pcpu_drain(page, order, mt);
		} while (count > 0 && !list_empty(list));
1271
	}
1272

1273
	spin_unlock_irqrestore(&zone->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
1274 1275
}

1276 1277
static void free_one_page(struct zone *zone,
				struct page *page, unsigned long pfn,
1278
				unsigned int order,
1279
				int migratetype, fpi_t fpi_flags)
Linus Torvalds's avatar
Linus Torvalds committed
1280
{
1281 1282 1283
	unsigned long flags;

	spin_lock_irqsave(&zone->lock, flags);
1284 1285 1286 1287
	if (unlikely(has_isolate_pageblock(zone) ||
		is_migrate_isolate(migratetype))) {
		migratetype = get_pfnblock_migratetype(page, pfn);
	}
1288
	__free_one_page(page, pfn, zone, order, migratetype, fpi_flags);
1289
	spin_unlock_irqrestore(&zone->lock, flags);
Nick Piggin's avatar
Nick Piggin committed
1290 1291
}

1292 1293
static void __free_pages_ok(struct page *page, unsigned int order,
			    fpi_t fpi_flags)
1294
{
1295
	unsigned long flags;
1296
	int migratetype;
1297
	unsigned long pfn = page_to_pfn(page);
1298
	struct zone *zone = page_zone(page);
1299

1300
	if (!free_pages_prepare(page, order, fpi_flags))
1301 1302
		return;

1303 1304 1305 1306 1307
	/*
	 * Calling get_pfnblock_migratetype() without spin_lock_irqsave() here
	 * is used to avoid calling get_pfnblock_migratetype() under the lock.
	 * This will reduce the lock holding time.
	 */
1308
	migratetype = get_pfnblock_migratetype(page, pfn);
1309

1310 1311 1312 1313 1314 1315 1316
	spin_lock_irqsave(&zone->lock, flags);
	if (unlikely(has_isolate_pageblock(zone) ||
		is_migrate_isolate(migratetype))) {
		migratetype = get_pfnblock_migratetype(page, pfn);
	}
	__free_one_page(page, pfn, zone, order, migratetype, fpi_flags);
	spin_unlock_irqrestore(&zone->lock, flags);
1317

1318
	__count_vm_events(PGFREE, 1 << order);
Linus Torvalds's avatar
Linus Torvalds committed
1319 1320
}

1321
void __free_pages_core(struct page *page, unsigned int order)
1322
{
1323
	unsigned int nr_pages = 1 << order;
1324
	struct page *p = page;
1325
	unsigned int loop;
1326

1327 1328 1329 1330 1331
	/*
	 * When initializing the memmap, __init_single_page() sets the refcount
	 * of all pages to 1 ("allocated"/"not free"). We have to set the
	 * refcount of all involved pages to 0.
	 */
1332 1333 1334
	prefetchw(p);
	for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
		prefetchw(p + 1);
1335 1336
		__ClearPageReserved(p);
		set_page_count(p, 0);
1337
	}
1338 1339
	__ClearPageReserved(p);
	set_page_count(p, 0);
1340

1341
	atomic_long_add(nr_pages, &page_zone(page)->managed_pages);
1342

1343 1344 1345 1346 1347 1348 1349
	if (page_contains_unaccepted(page, order)) {
		if (order == MAX_ORDER && __free_unaccepted(page))
			return;

		accept_page(page, order);
	}

1350 1351 1352 1353
	/*
	 * Bypass PCP and place fresh pages right to the tail, primarily
	 * relevant for memory onlining.
	 */
1354
	__free_pages_ok(page, order, FPI_TO_TAIL);
1355 1356
}

1357 1358 1359
/*
 * Check that the whole (or subset of) a pageblock given by the interval of
 * [start_pfn, end_pfn) is valid and within the same zone, before scanning it
1360
 * with the migration of free compaction scanner.
1361 1362 1363 1364 1365 1366 1367 1368 1369 1370
 *
 * Return struct page pointer of start_pfn, or NULL if checks were not passed.
 *
 * It's possible on some configurations to have a setup like node0 node1 node0
 * i.e. it's possible that all pages within a zones range of pages do not
 * belong to a single zone. We assume that a border between node0 and node1
 * can occur within a single pageblock, but not a node0 node1 node0
 * interleaving within a single pageblock. It is therefore sufficient to check
 * the first and last page of a pageblock and avoid checking each individual
 * page in a pageblock.
1371 1372 1373 1374 1375 1376 1377 1378 1379
 *
 * Note: the function may return non-NULL struct page even for a page block
 * which contains a memory hole (i.e. there is no physical memory for a subset
 * of the pfn range). For example, if the pageblock order is MAX_ORDER, which
 * will fall into 2 sub-sections, and the end pfn of the pageblock may be hole
 * even though the start pfn is online and valid. This should be safe most of
 * the time because struct pages are still initialized via init_unavailable_range()
 * and pfn walkers shouldn't touch any physical memory range for which they do
 * not recognize any specific metadata in struct pages.
1380 1381 1382 1383 1384 1385 1386 1387 1388 1389
 */
struct page *__pageblock_pfn_to_page(unsigned long start_pfn,
				     unsigned long end_pfn, struct zone *zone)
{
	struct page *start_page;
	struct page *end_page;

	/* end_pfn is one past the range we are checking */
	end_pfn--;

1390
	if (!pfn_valid(end_pfn))
1391 1392
		return NULL;

1393 1394 1395
	start_page = pfn_to_online_page(start_pfn);
	if (!start_page)
		return NULL;
1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408

	if (page_zone(start_page) != zone)
		return NULL;

	end_page = pfn_to_page(end_pfn);

	/* This gives a shorter code than deriving page_zone(end_page) */
	if (page_zone_id(start_page) != page_zone_id(end_page))
		return NULL;

	return start_page;
}

1409
/*
1410 1411 1412 1413 1414 1415 1416 1417 1418 1419
 * The order of subdivision here is critical for the IO subsystem.
 * Please do not alter this order without good reasons and regression
 * testing. Specifically, as large blocks of memory are subdivided,
 * the order in which smaller blocks are delivered depends on the order
 * they're subdivided in this function. This is the primary factor
 * influencing the order in which pages are delivered to the IO
 * subsystem according to empirical testing, and this is also justified
 * by considering the behavior of a buddy system containing a single
 * large block of memory acted on by a series of small allocations.
 * This behavior is a critical factor in sglist merging's success.
1420
 *
1421
 * -- nyc
1422
 */
1423 1424
static inline void expand(struct zone *zone, struct page *page,
	int low, int high, int migratetype)
1425
{
1426
	unsigned long size = 1 << high;
1427

1428 1429 1430 1431
	while (high > low) {
		high--;
		size >>= 1;
		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);
1432

1433 1434 1435 1436 1437 1438 1439
		/*
		 * Mark as guard pages (or page), that will allow to
		 * merge back to allocator when buddy will be freed.
		 * Corresponding page table entries will not be touched,
		 * pages will stay not present in virtual address space
		 */
		if (set_page_guard(zone, &page[size], high, migratetype))
1440
			continue;
1441 1442 1443

		add_to_free_list(&page[size], zone, high, migratetype);
		set_buddy_order(&page[size], high);
1444 1445 1446
	}
}

1447
static void check_new_page_bad(struct page *page)
1448
{
1449 1450 1451 1452
	if (unlikely(page->flags & __PG_HWPOISON)) {
		/* Don't complain about hwpoisoned pages */
		page_mapcount_reset(page); /* remove PageBuddy */
		return;
1453 1454
	}

1455 1456
	bad_page(page,
		 page_bad_reason(page, PAGE_FLAGS_CHECK_AT_PREP));
1457 1458 1459
}

/*
1460
 * This page is about to be returned from the page allocator
1461
 */
1462
static int check_new_page(struct page *page)
1463
{
1464 1465 1466
	if (likely(page_expected_state(page,
				PAGE_FLAGS_CHECK_AT_PREP|__PG_HWPOISON)))
		return 0;
1467

1468 1469 1470
	check_new_page_bad(page);
	return 1;
}
1471

1472 1473 1474 1475 1476
static inline bool check_new_pages(struct page *page, unsigned int order)
{
	if (is_check_pages_enabled()) {
		for (int i = 0; i < (1 << order); i++) {
			struct page *p = page + i;
1477

1478
			if (check_new_page(p))
1479
				return true;
1480 1481 1482
		}
	}

1483
	return false;
1484 1485
}

1486
static inline bool should_skip_kasan_unpoison(gfp_t flags)
1487
{
1488 1489 1490 1491
	/* Don't skip if a software KASAN mode is enabled. */
	if (IS_ENABLED(CONFIG_KASAN_GENERIC) ||
	    IS_ENABLED(CONFIG_KASAN_SW_TAGS))
		return false;
1492

1493 1494 1495
	/* Skip, if hardware tag-based KASAN is not enabled. */
	if (!kasan_hw_tags_enabled())
		return true;
1496 1497

	/*
1498 1499
	 * With hardware tag-based KASAN enabled, skip if this has been
	 * requested via __GFP_SKIP_KASAN.
1500
	 */
1501
	return flags & __GFP_SKIP_KASAN;
1502 1503
}

1504
static inline bool should_skip_init(gfp_t flags)
1505
{
1506 1507 1508 1509 1510 1511
	/* Don't skip, if hardware tag-based KASAN is not enabled. */
	if (!kasan_hw_tags_enabled())
		return false;

	/* For hardware tag-based KASAN, skip if requested. */
	return (flags & __GFP_SKIP_ZERO);
1512 1513
}

1514 1515
inline void post_alloc_hook(struct page *page, unsigned int order,
				gfp_t gfp_flags)
1516
{
1517 1518 1519 1520 1521 1522 1523
	bool init = !want_init_on_free() && want_init_on_alloc(gfp_flags) &&
			!should_skip_init(gfp_flags);
	bool zero_tags = init && (gfp_flags & __GFP_ZEROTAGS);
	int i;

	set_page_private(page, 0);
	set_page_refcounted(page);
1524

1525 1526
	arch_alloc_page(page, order);
	debug_pagealloc_map_pages(page, 1 << order);
1527

1528
	/*
1529 1530 1531
	 * Page unpoisoning must happen before memory initialization.
	 * Otherwise, the poison pattern will be overwritten for __GFP_ZERO
	 * allocations and the page unpoisoning code will complain.
1532
	 */
1533
	kernel_unpoison_pages(page, 1 << order);
1534

1535 1536
	/*
	 * As memory initialization might be integrated into KASAN,
1537
	 * KASAN unpoisoning and memory initializion code must be
1538 1539
	 * kept together to avoid discrepancies in behavior.
	 */
1540 1541

	/*
1542 1543
	 * If memory tags should be zeroed
	 * (which happens only when memory should be initialized as well).
1544
	 */
1545
	if (zero_tags) {
1546
		/* Initialize both memory and memory tags. */
1547 1548 1549
		for (i = 0; i != 1 << order; ++i)
			tag_clear_highpage(page + i);

1550
		/* Take note that memory was initialized by the loop above. */
1551 1552
		init = false;
	}
1553 1554 1555 1556 1557 1558 1559 1560 1561 1562
	if (!should_skip_kasan_unpoison(gfp_flags) &&
	    kasan_unpoison_pages(page, order, init)) {
		/* Take note that memory was initialized by KASAN. */
		if (kasan_has_integrated_init())
			init = false;
	} else {
		/*
		 * If memory tags have not been set by KASAN, reset the page
		 * tags to ensure page_address() dereferencing does not fault.
		 */
1563 1564
		for (i = 0; i != 1 << order; ++i)
			page_kasan_tag_reset(page + i);
1565
	}
1566
	/* If memory is still not initialized, initialize it now. */
1567
	if (init)
1568
		kernel_init_pages(page, 1 << order);
1569 1570

	set_page_owner(page, order, gfp_flags);
Pasha Tatashin's avatar
Pasha Tatashin committed
1571
	page_table_check_alloc(page, order);
1572 1573
}

1574
static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags,
1575
							unsigned int alloc_flags)
1576
{
1577
	post_alloc_hook(page, order, gfp_flags);
1578 1579 1580 1581

	if (order && (gfp_flags & __GFP_COMP))
		prep_compound_page(page, order);

1582
	/*
1583
	 * page is set pfmemalloc when ALLOC_NO_WATERMARKS was necessary to
1584 1585 1586 1587
	 * allocate the page. The expectation is that the caller is taking
	 * steps that will free more memory. The caller should avoid the page
	 * being used for !PFMEMALLOC purposes.
	 */
1588 1589 1590 1591
	if (alloc_flags & ALLOC_NO_WATERMARKS)
		set_page_pfmemalloc(page);
	else
		clear_page_pfmemalloc(page);
Linus Torvalds's avatar
Linus Torvalds committed
1592 1593
}

1594 1595 1596 1597
/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
1598
static __always_inline
1599
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
1600 1601 1602
						int migratetype)
{
	unsigned int current_order;
1603
	struct free_area *area;
1604 1605 1606
	struct page *page;

	/* Find a page of the appropriate size in the preferred list */
1607
	for (current_order = order; current_order <= MAX_ORDER; ++current_order) {
1608
		area = &(zone->free_area[current_order]);
1609
		page = get_page_from_free_area(area, migratetype);
1610 1611
		if (!page)
			continue;
1612 1613
		del_page_from_free_list(page, zone, current_order);
		expand(zone, page, order, current_order, migratetype);
1614
		set_pcppage_migratetype(page, migratetype);
1615 1616 1617
		trace_mm_page_alloc_zone_locked(page, order, migratetype,
				pcp_allowed_order(order) &&
				migratetype < MIGRATE_PCPTYPES);
1618 1619 1620 1621 1622 1623 1624
		return page;
	}

	return NULL;
}


1625 1626 1627
/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
1628 1629
 *
 * The other migratetypes do not have fallbacks.
1630
 */
1631 1632 1633 1634
static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE   },
	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE   },
1635 1636
};

1637
#ifdef CONFIG_CMA
1638
static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1639 1640 1641 1642 1643 1644 1645 1646 1647
					unsigned int order)
{
	return __rmqueue_smallest(zone, order, MIGRATE_CMA);
}
#else
static inline struct page *__rmqueue_cma_fallback(struct zone *zone,
					unsigned int order) { return NULL; }
#endif

1648
/*
1649
 * Move the free pages in a range to the freelist tail of the requested type.
1650
 * Note that start_page and end_pages are not aligned on a pageblock
1651 1652
 * boundary. If alignment is required, use move_freepages_block()
 */
1653
static int move_freepages(struct zone *zone,
1654
			  unsigned long start_pfn, unsigned long end_pfn,
1655
			  int migratetype, int *num_movable)
1656 1657
{
	struct page *page;
1658
	unsigned long pfn;
1659
	unsigned int order;
1660
	int pages_moved = 0;
1661

1662 1663
	for (pfn = start_pfn; pfn <= end_pfn;) {
		page = pfn_to_page(pfn);
1664
		if (!PageBuddy(page)) {
1665 1666 1667 1668 1669 1670 1671 1672
			/*
			 * We assume that pages that could be isolated for
			 * migration are movable. But we don't actually try
			 * isolating, as that would be expensive.
			 */
			if (num_movable &&
					(PageLRU(page) || __PageMovable(page)))
				(*num_movable)++;
1673
			pfn++;
1674 1675 1676
			continue;
		}

1677 1678 1679 1680
		/* Make sure we are not inadvertently changing nodes */
		VM_BUG_ON_PAGE(page_to_nid(page) != zone_to_nid(zone), page);
		VM_BUG_ON_PAGE(page_zone(page) != zone, page);

1681
		order = buddy_order(page);
1682
		move_to_free_list(page, zone, order, migratetype);
1683
		pfn += 1 << order;
1684
		pages_moved += 1 << order;
1685 1686
	}

1687
	return pages_moved;
1688 1689
}

1690
int move_freepages_block(struct zone *zone, struct page *page,
1691
				int migratetype, int *num_movable)
1692
{
1693
	unsigned long start_pfn, end_pfn, pfn;
1694

1695 1696 1697
	if (num_movable)
		*num_movable = 0;

1698
	pfn = page_to_pfn(page);
1699 1700
	start_pfn = pageblock_start_pfn(pfn);
	end_pfn = pageblock_end_pfn(pfn) - 1;
1701 1702

	/* Do not cross zone boundaries */
1703
	if (!zone_spans_pfn(zone, start_pfn))
1704
		start_pfn = pfn;
1705
	if (!zone_spans_pfn(zone, end_pfn))
1706 1707
		return 0;

1708
	return move_freepages(zone, start_pfn, end_pfn, migratetype,
1709
								num_movable);
1710 1711
}

1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722
static void change_pageblock_range(struct page *pageblock_page,
					int start_order, int migratetype)
{
	int nr_pageblocks = 1 << (start_order - pageblock_order);

	while (nr_pageblocks--) {
		set_pageblock_migratetype(pageblock_page, migratetype);
		pageblock_page += pageblock_nr_pages;
	}
}

1723
/*
1724 1725 1726 1727 1728 1729 1730 1731 1732 1733
 * When we are falling back to another migratetype during allocation, try to
 * steal extra free pages from the same pageblocks to satisfy further
 * allocations, instead of polluting multiple pageblocks.
 *
 * If we are stealing a relatively large buddy page, it is likely there will
 * be more free pages in the pageblock, so try to steal them all. For
 * reclaimable and unmovable allocations, we steal regardless of page size,
 * as fragmentation caused by those allocations polluting movable pageblocks
 * is worse than movable allocations stealing from unmovable and reclaimable
 * pageblocks.
1734
 */
1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755
static bool can_steal_fallback(unsigned int order, int start_mt)
{
	/*
	 * Leaving this order check is intended, although there is
	 * relaxed order check in next check. The reason is that
	 * we can actually steal whole pageblock if this condition met,
	 * but, below check doesn't guarantee it and that is just heuristic
	 * so could be changed anytime.
	 */
	if (order >= pageblock_order)
		return true;

	if (order >= pageblock_order / 2 ||
		start_mt == MIGRATE_RECLAIMABLE ||
		start_mt == MIGRATE_UNMOVABLE ||
		page_group_by_mobility_disabled)
		return true;

	return false;
}

1756
static inline bool boost_watermark(struct zone *zone)
1757 1758 1759 1760
{
	unsigned long max_boost;

	if (!watermark_boost_factor)
1761
		return false;
1762 1763 1764 1765 1766 1767 1768
	/*
	 * Don't bother in zones that are unlikely to produce results.
	 * On small machines, including kdump capture kernels running
	 * in a small area, boosting the watermark can cause an out of
	 * memory situation immediately.
	 */
	if ((pageblock_nr_pages * 4) > zone_managed_pages(zone))
1769
		return false;
1770 1771 1772

	max_boost = mult_frac(zone->_watermark[WMARK_HIGH],
			watermark_boost_factor, 10000);
1773 1774 1775 1776 1777 1778 1779 1780 1781 1782

	/*
	 * high watermark may be uninitialised if fragmentation occurs
	 * very early in boot so do not boost. We do not fall
	 * through and boost by pageblock_nr_pages as failing
	 * allocations that early means that reclaim is not going
	 * to help and it may even be impossible to reclaim the
	 * boosted watermark resulting in a hang.
	 */
	if (!max_boost)
1783
		return false;
1784

1785 1786 1787 1788
	max_boost = max(pageblock_nr_pages, max_boost);

	zone->watermark_boost = min(zone->watermark_boost + pageblock_nr_pages,
		max_boost);
1789 1790

	return true;
1791 1792
}

1793 1794 1795
/*
 * This function implements actual steal behaviour. If order is large enough,
 * we can steal whole pageblock. If not, we first move freepages in this
1796 1797 1798 1799
 * pageblock to our migratetype and determine how many already-allocated pages
 * are there in the pageblock with a compatible migratetype. If at least half
 * of pages are free or compatible, we can change migratetype of the pageblock
 * itself, so pages freed in the future will be put on the correct free list.
1800 1801
 */
static void steal_suitable_fallback(struct zone *zone, struct page *page,
1802
		unsigned int alloc_flags, int start_type, bool whole_block)
1803
{
1804
	unsigned int current_order = buddy_order(page);
1805 1806 1807 1808
	int free_pages, movable_pages, alike_pages;
	int old_block_type;

	old_block_type = get_pageblock_migratetype(page);
1809

1810 1811 1812 1813
	/*
	 * This can happen due to races and we want to prevent broken
	 * highatomic accounting.
	 */
1814
	if (is_migrate_highatomic(old_block_type))
1815 1816
		goto single_page;

1817 1818 1819
	/* Take ownership for orders >= pageblock_order */
	if (current_order >= pageblock_order) {
		change_pageblock_range(page, current_order, start_type);
1820
		goto single_page;
1821 1822
	}

1823 1824 1825 1826 1827
	/*
	 * Boost watermarks to increase reclaim pressure to reduce the
	 * likelihood of future fallbacks. Wake kswapd now as the node
	 * may be balanced overall and kswapd will not wake naturally.
	 */
1828
	if (boost_watermark(zone) && (alloc_flags & ALLOC_KSWAPD))
1829
		set_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
1830

1831 1832 1833 1834
	/* We are not allowed to try stealing from the whole block */
	if (!whole_block)
		goto single_page;

1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858
	free_pages = move_freepages_block(zone, page, start_type,
						&movable_pages);
	/*
	 * Determine how many pages are compatible with our allocation.
	 * For movable allocation, it's the number of movable pages which
	 * we just obtained. For other types it's a bit more tricky.
	 */
	if (start_type == MIGRATE_MOVABLE) {
		alike_pages = movable_pages;
	} else {
		/*
		 * If we are falling back a RECLAIMABLE or UNMOVABLE allocation
		 * to MOVABLE pageblock, consider all non-movable pages as
		 * compatible. If it's UNMOVABLE falling back to RECLAIMABLE or
		 * vice versa, be conservative since we can't distinguish the
		 * exact migratetype of non-movable pages.
		 */
		if (old_block_type == MIGRATE_MOVABLE)
			alike_pages = pageblock_nr_pages
						- (free_pages + movable_pages);
		else
			alike_pages = 0;
	}

1859
	/* moving whole block can fail due to zone boundary conditions */
1860
	if (!free_pages)
1861
		goto single_page;
1862

1863 1864 1865 1866 1867
	/*
	 * If a sufficient number of pages in the block are either free or of
	 * comparable migratability as our allocation, claim the whole block.
	 */
	if (free_pages + alike_pages >= (1 << (pageblock_order-1)) ||
1868 1869
			page_group_by_mobility_disabled)
		set_pageblock_migratetype(page, start_type);
1870 1871 1872 1873

	return;

single_page:
1874
	move_to_free_list(page, zone, current_order, start_type);
1875 1876
}

1877 1878 1879 1880 1881 1882 1883 1884
/*
 * Check whether there is a suitable fallback freepage with requested order.
 * If only_stealable is true, this function returns fallback_mt only if
 * we can steal other freepages all together. This would help to reduce
 * fragmentation due to mixed migratetype pages in one pageblock.
 */
int find_suitable_fallback(struct free_area *area, unsigned int order,
			int migratetype, bool only_stealable, bool *can_steal)
1885 1886 1887 1888 1889 1890 1891 1892
{
	int i;
	int fallback_mt;

	if (area->nr_free == 0)
		return -1;

	*can_steal = false;
1893
	for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
1894
		fallback_mt = fallbacks[migratetype][i];
1895
		if (free_area_empty(area, fallback_mt))
1896
			continue;
1897

1898 1899 1900
		if (can_steal_fallback(order, migratetype))
			*can_steal = true;

1901 1902 1903 1904 1905
		if (!only_stealable)
			return fallback_mt;

		if (*can_steal)
			return fallback_mt;
1906
	}
1907 1908

	return -1;
1909 1910
}

1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924
/*
 * Reserve a pageblock for exclusive use of high-order atomic allocations if
 * there are no empty page blocks that contain a page with a suitable order
 */
static void reserve_highatomic_pageblock(struct page *page, struct zone *zone,
				unsigned int alloc_order)
{
	int mt;
	unsigned long max_managed, flags;

	/*
	 * Limit the number reserved to 1 pageblock or roughly 1% of a zone.
	 * Check is race-prone but harmless.
	 */
1925
	max_managed = (zone_managed_pages(zone) / 100) + pageblock_nr_pages;
1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936
	if (zone->nr_reserved_highatomic >= max_managed)
		return;

	spin_lock_irqsave(&zone->lock, flags);

	/* Recheck the nr_reserved_highatomic limit under the lock */
	if (zone->nr_reserved_highatomic >= max_managed)
		goto out_unlock;

	/* Yoink! */
	mt = get_pageblock_migratetype(page);
1937 1938
	/* Only reserve normal pageblocks (i.e., they can merge with others) */
	if (migratetype_is_mergeable(mt)) {
1939 1940
		zone->nr_reserved_highatomic += pageblock_nr_pages;
		set_pageblock_migratetype(page, MIGRATE_HIGHATOMIC);
1941
		move_freepages_block(zone, page, MIGRATE_HIGHATOMIC, NULL);
1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952
	}

out_unlock:
	spin_unlock_irqrestore(&zone->lock, flags);
}

/*
 * Used when an allocation is about to fail under memory pressure. This
 * potentially hurts the reliability of high-order allocations when under
 * intense memory pressure but failed atomic allocations should be easier
 * to recover from than an OOM.
1953 1954 1955
 *
 * If @force is true, try to unreserve a pageblock even though highatomic
 * pageblock is exhausted.
1956
 */
1957 1958
static bool unreserve_highatomic_pageblock(const struct alloc_context *ac,
						bool force)
1959 1960 1961 1962 1963 1964 1965
{
	struct zonelist *zonelist = ac->zonelist;
	unsigned long flags;
	struct zoneref *z;
	struct zone *zone;
	struct page *page;
	int order;
1966
	bool ret;
1967

1968
	for_each_zone_zonelist_nodemask(zone, z, zonelist, ac->highest_zoneidx,
1969
								ac->nodemask) {
1970 1971 1972 1973 1974 1975
		/*
		 * Preserve at least one pageblock unless memory pressure
		 * is really high.
		 */
		if (!force && zone->nr_reserved_highatomic <=
					pageblock_nr_pages)
1976 1977 1978
			continue;

		spin_lock_irqsave(&zone->lock, flags);
1979
		for (order = 0; order <= MAX_ORDER; order++) {
1980 1981
			struct free_area *area = &(zone->free_area[order]);

1982
			page = get_page_from_free_area(area, MIGRATE_HIGHATOMIC);
1983
			if (!page)
1984 1985 1986
				continue;

			/*
1987 1988
			 * In page freeing path, migratetype change is racy so
			 * we can counter several free pages in a pageblock
Ingo Molnar's avatar
Ingo Molnar committed
1989
			 * in this loop although we changed the pageblock type
1990 1991
			 * from highatomic to ac->migratetype. So we should
			 * adjust the count once.
1992
			 */
1993
			if (is_migrate_highatomic_page(page)) {
1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004
				/*
				 * It should never happen but changes to
				 * locking could inadvertently allow a per-cpu
				 * drain to add pages to MIGRATE_HIGHATOMIC
				 * while unreserving so be safe and watch for
				 * underflows.
				 */
				zone->nr_reserved_highatomic -= min(
						pageblock_nr_pages,
						zone->nr_reserved_highatomic);
			}
2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015

			/*
			 * Convert to ac->migratetype and avoid the normal
			 * pageblock stealing heuristics. Minimally, the caller
			 * is doing the work and needs the pages. More
			 * importantly, if the block was always converted to
			 * MIGRATE_UNMOVABLE or another type then the number
			 * of pageblocks that cannot be completely freed
			 * may increase.
			 */
			set_pageblock_migratetype(page, ac->migratetype);
2016 2017
			ret = move_freepages_block(zone, page, ac->migratetype,
									NULL);
2018 2019 2020 2021
			if (ret) {
				spin_unlock_irqrestore(&zone->lock, flags);
				return ret;
			}
2022 2023 2024
		}
		spin_unlock_irqrestore(&zone->lock, flags);
	}
2025 2026

	return false;
2027 2028
}

2029 2030 2031 2032 2033
/*
 * Try finding a free buddy page on the fallback list and put it on the free
 * list of requested migratetype, possibly along with other pages from the same
 * block, depending on fragmentation avoidance heuristics. Returns true if
 * fallback was found so that __rmqueue_smallest() can grab it.
2034 2035 2036 2037
 *
 * The use of signed ints for order and current_order is a deliberate
 * deviation from the rest of this file, to make the for loop
 * condition simpler.
2038
 */
2039
static __always_inline bool
2040 2041
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype,
						unsigned int alloc_flags)
2042
{
2043
	struct free_area *area;
2044
	int current_order;
2045
	int min_order = order;
2046
	struct page *page;
2047 2048
	int fallback_mt;
	bool can_steal;
2049

2050 2051 2052 2053 2054
	/*
	 * Do not steal pages from freelists belonging to other pageblocks
	 * i.e. orders < pageblock_order. If there are no local zones free,
	 * the zonelists will be reiterated without ALLOC_NOFRAGMENT.
	 */
2055
	if (order < pageblock_order && alloc_flags & ALLOC_NOFRAGMENT)
2056 2057
		min_order = pageblock_order;

2058 2059 2060 2061 2062
	/*
	 * Find the largest available free page in the other list. This roughly
	 * approximates finding the pageblock with the most free pages, which
	 * would be too costly to do exactly.
	 */
2063
	for (current_order = MAX_ORDER; current_order >= min_order;
2064
				--current_order) {
2065 2066
		area = &(zone->free_area[current_order]);
		fallback_mt = find_suitable_fallback(area, current_order,
2067
				start_migratetype, false, &can_steal);
2068 2069
		if (fallback_mt == -1)
			continue;
2070

2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081
		/*
		 * We cannot steal all free pages from the pageblock and the
		 * requested migratetype is movable. In that case it's better to
		 * steal and split the smallest available page instead of the
		 * largest available page, because even if the next movable
		 * allocation falls back into a different pageblock than this
		 * one, it won't cause permanent fragmentation.
		 */
		if (!can_steal && start_migratetype == MIGRATE_MOVABLE
					&& current_order > order)
			goto find_smallest;
2082

2083 2084
		goto do_steal;
	}
2085

2086
	return false;
2087

2088
find_smallest:
2089
	for (current_order = order; current_order <= MAX_ORDER;
2090 2091 2092 2093 2094 2095
							current_order++) {
		area = &(zone->free_area[current_order]);
		fallback_mt = find_suitable_fallback(area, current_order,
				start_migratetype, false, &can_steal);
		if (fallback_mt != -1)
			break;
2096 2097
	}

2098 2099 2100 2101
	/*
	 * This should not happen - we already found a suitable fallback
	 * when looking for the largest page.
	 */
2102
	VM_BUG_ON(current_order > MAX_ORDER);
2103 2104

do_steal:
2105
	page = get_page_from_free_area(area, fallback_mt);
2106

2107 2108
	steal_suitable_fallback(zone, page, alloc_flags, start_migratetype,
								can_steal);
2109 2110 2111 2112 2113 2114

	trace_mm_page_alloc_extfrag(page, order, current_order,
		start_migratetype, fallback_mt);

	return true;

2115 2116
}

2117
/*
Linus Torvalds's avatar
Linus Torvalds committed
2118 2119 2120
 * Do the hard work of removing an element from the buddy allocator.
 * Call me with the zone->lock already held.
 */
2121
static __always_inline struct page *
2122 2123
__rmqueue(struct zone *zone, unsigned int order, int migratetype,
						unsigned int alloc_flags)
Linus Torvalds's avatar
Linus Torvalds committed
2124 2125 2126
{
	struct page *page;

2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137
	if (IS_ENABLED(CONFIG_CMA)) {
		/*
		 * Balance movable allocations between regular and CMA areas by
		 * allocating from CMA when over half of the zone's free memory
		 * is in the CMA area.
		 */
		if (alloc_flags & ALLOC_CMA &&
		    zone_page_state(zone, NR_FREE_CMA_PAGES) >
		    zone_page_state(zone, NR_FREE_PAGES) / 2) {
			page = __rmqueue_cma_fallback(zone, order);
			if (page)
2138
				return page;
2139
		}
2140
	}
2141
retry:
2142
	page = __rmqueue_smallest(zone, order, migratetype);
2143
	if (unlikely(!page)) {
2144
		if (alloc_flags & ALLOC_CMA)
2145 2146
			page = __rmqueue_cma_fallback(zone, order);

2147 2148
		if (!page && __rmqueue_fallback(zone, order, migratetype,
								alloc_flags))
2149
			goto retry;
2150
	}
2151
	return page;
Linus Torvalds's avatar
Linus Torvalds committed
2152 2153
}

2154
/*
Linus Torvalds's avatar
Linus Torvalds committed
2155 2156 2157 2158
 * Obtain a specified number of elements from the buddy allocator, all under
 * a single hold of the lock, for efficiency.  Add them to the supplied list.
 * Returns the number of new pages which were placed at *list.
 */
2159
static int rmqueue_bulk(struct zone *zone, unsigned int order,
2160
			unsigned long count, struct list_head *list,
2161
			int migratetype, unsigned int alloc_flags)
Linus Torvalds's avatar
Linus Torvalds committed
2162
{
2163
	unsigned long flags;
2164
	int i;
2165

2166
	spin_lock_irqsave(&zone->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
2167
	for (i = 0; i < count; ++i) {
2168 2169
		struct page *page = __rmqueue(zone, order, migratetype,
								alloc_flags);
2170
		if (unlikely(page == NULL))
Linus Torvalds's avatar
Linus Torvalds committed
2171
			break;
2172 2173

		/*
2174 2175 2176 2177 2178 2179 2180 2181
		 * Split buddy pages returned by expand() are received here in
		 * physical page order. The page is added to the tail of
		 * caller's list. From the callers perspective, the linked list
		 * is ordered by page number under some conditions. This is
		 * useful for IO devices that can forward direction from the
		 * head, thus also in the physical page order. This is useful
		 * for IO devices that can merge IO requests if the physical
		 * pages are ordered properly.
2182
		 */
2183
		list_add_tail(&page->pcp_list, list);
2184
		if (is_migrate_cma(get_pcppage_migratetype(page)))
2185 2186
			__mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
					      -(1 << order));
Linus Torvalds's avatar
Linus Torvalds committed
2187
	}
2188

2189
	__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
2190
	spin_unlock_irqrestore(&zone->lock, flags);
2191

2192
	return i;
Linus Torvalds's avatar
Linus Torvalds committed
2193 2194
}

2195
#ifdef CONFIG_NUMA
2196
/*
2197 2198 2199
 * Called from the vmstat counter updater to drain pagesets of this
 * currently executing processor on remote nodes after they have
 * expired.
2200
 */
2201
void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
2202
{
2203
	int to_drain, batch;
2204

2205
	batch = READ_ONCE(pcp->batch);
2206
	to_drain = min(pcp->count, batch);
2207
	if (to_drain > 0) {
2208
		spin_lock(&pcp->lock);
2209
		free_pcppages_bulk(zone, to_drain, pcp, 0);
2210
		spin_unlock(&pcp->lock);
2211
	}
2212 2213 2214
}
#endif

2215
/*
2216
 * Drain pcplists of the indicated processor and zone.
2217
 */
2218
static void drain_pages_zone(unsigned int cpu, struct zone *zone)
Linus Torvalds's avatar
Linus Torvalds committed
2219
{
2220
	struct per_cpu_pages *pcp;
Linus Torvalds's avatar
Linus Torvalds committed
2221

2222
	pcp = per_cpu_ptr(zone->per_cpu_pageset, cpu);
2223
	if (pcp->count) {
2224
		spin_lock(&pcp->lock);
2225
		free_pcppages_bulk(zone, pcp->count, pcp, 0);
2226
		spin_unlock(&pcp->lock);
2227
	}
2228
}
2229

2230 2231 2232 2233 2234 2235 2236 2237 2238
/*
 * Drain pcplists of all zones on the indicated processor.
 */
static void drain_pages(unsigned int cpu)
{
	struct zone *zone;

	for_each_populated_zone(zone) {
		drain_pages_zone(cpu, zone);
Linus Torvalds's avatar
Linus Torvalds committed
2239 2240 2241
	}
}

2242 2243 2244
/*
 * Spill all of this CPU's per-cpu pages back into the buddy allocator.
 */
2245
void drain_local_pages(struct zone *zone)
2246
{
2247 2248 2249 2250 2251 2252
	int cpu = smp_processor_id();

	if (zone)
		drain_pages_zone(cpu, zone);
	else
		drain_pages(cpu);
2253 2254 2255
}

/*
2256 2257
 * The implementation of drain_all_pages(), exposing an extra parameter to
 * drain on all cpus.
2258
 *
2259 2260 2261 2262 2263
 * drain_all_pages() is optimized to only execute on cpus where pcplists are
 * not empty. The check for non-emptiness can however race with a free to
 * pcplist that has not yet increased the pcp->count from 0 to 1. Callers
 * that need the guarantee that every CPU has drained can disable the
 * optimizing racy check.
2264
 */
2265
static void __drain_all_pages(struct zone *zone, bool force_all_cpus)
2266
{
2267 2268 2269
	int cpu;

	/*
Zhen Lei's avatar
Zhen Lei committed
2270
	 * Allocate in the BSS so we won't require allocation in
2271 2272 2273 2274
	 * direct reclaim path for CONFIG_CPUMASK_OFFSTACK=y
	 */
	static cpumask_t cpus_with_pcps;

2275 2276 2277 2278 2279 2280 2281 2282 2283 2284
	/*
	 * Do not drain if one is already in progress unless it's specific to
	 * a zone. Such callers are primarily CMA and memory hotplug and need
	 * the drain to be complete when the call returns.
	 */
	if (unlikely(!mutex_trylock(&pcpu_drain_mutex))) {
		if (!zone)
			return;
		mutex_lock(&pcpu_drain_mutex);
	}
2285

2286 2287 2288 2289 2290 2291 2292
	/*
	 * We don't care about racing with CPU hotplug event
	 * as offline notification will cause the notified
	 * cpu to drain that CPU pcps and on_each_cpu_mask
	 * disables preemption as part of its processing
	 */
	for_each_online_cpu(cpu) {
2293
		struct per_cpu_pages *pcp;
2294
		struct zone *z;
2295
		bool has_pcps = false;
2296

2297 2298 2299 2300 2301 2302 2303
		if (force_all_cpus) {
			/*
			 * The pcp.count check is racy, some callers need a
			 * guarantee that no cpu is missed.
			 */
			has_pcps = true;
		} else if (zone) {
2304 2305
			pcp = per_cpu_ptr(zone->per_cpu_pageset, cpu);
			if (pcp->count)
2306
				has_pcps = true;
2307 2308
		} else {
			for_each_populated_zone(z) {
2309 2310
				pcp = per_cpu_ptr(z->per_cpu_pageset, cpu);
				if (pcp->count) {
2311 2312 2313
					has_pcps = true;
					break;
				}
2314 2315
			}
		}
2316

2317 2318 2319 2320 2321
		if (has_pcps)
			cpumask_set_cpu(cpu, &cpus_with_pcps);
		else
			cpumask_clear_cpu(cpu, &cpus_with_pcps);
	}
2322

2323
	for_each_cpu(cpu, &cpus_with_pcps) {
2324 2325 2326 2327
		if (zone)
			drain_pages_zone(cpu, zone);
		else
			drain_pages(cpu);
2328
	}
2329 2330

	mutex_unlock(&pcpu_drain_mutex);
2331 2332
}

2333 2334 2335 2336 2337 2338 2339 2340 2341 2342
/*
 * Spill all the per-cpu pages from all CPUs back into the buddy allocator.
 *
 * When zone parameter is non-NULL, spill just the single zone's pages.
 */
void drain_all_pages(struct zone *zone)
{
	__drain_all_pages(zone, false);
}

2343 2344
static bool free_unref_page_prepare(struct page *page, unsigned long pfn,
							unsigned int order)
Linus Torvalds's avatar
Linus Torvalds committed
2345
{
2346
	int migratetype;
Linus Torvalds's avatar
Linus Torvalds committed
2347

2348
	if (!free_pages_prepare(page, order, FPI_NONE))
2349
		return false;
2350

2351
	migratetype = get_pfnblock_migratetype(page, pfn);
2352
	set_pcppage_migratetype(page, migratetype);
2353 2354 2355
	return true;
}

2356 2357
static int nr_pcp_free(struct per_cpu_pages *pcp, int high, int batch,
		       bool free_high)
2358 2359 2360
{
	int min_nr_free, max_nr_free;

2361 2362 2363 2364
	/* Free everything if batch freeing high-order pages. */
	if (unlikely(free_high))
		return pcp->count;

2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384
	/* Check for PCP disabled or boot pageset */
	if (unlikely(high < batch))
		return 1;

	/* Leave at least pcp->batch pages on the list */
	min_nr_free = batch;
	max_nr_free = high - batch;

	/*
	 * Double the number of pages freed each time there is subsequent
	 * freeing of pages without any allocation.
	 */
	batch <<= pcp->free_factor;
	if (batch < max_nr_free)
		pcp->free_factor++;
	batch = clamp(batch, min_nr_free, max_nr_free);

	return batch;
}

2385 2386
static int nr_pcp_high(struct per_cpu_pages *pcp, struct zone *zone,
		       bool free_high)
2387 2388 2389
{
	int high = READ_ONCE(pcp->high);

2390
	if (unlikely(!high || free_high))
2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402
		return 0;

	if (!test_bit(ZONE_RECLAIM_ACTIVE, &zone->flags))
		return high;

	/*
	 * If reclaim is active, limit the number of pages that can be
	 * stored on pcp lists
	 */
	return min(READ_ONCE(pcp->batch) << 2, high);
}

2403 2404
static void free_unref_page_commit(struct zone *zone, struct per_cpu_pages *pcp,
				   struct page *page, int migratetype,
2405
				   unsigned int order)
2406
{
2407
	int high;
2408
	int pindex;
2409
	bool free_high;
2410

2411
	__count_vm_events(PGFREE, 1 << order);
2412
	pindex = order_to_pindex(migratetype, order);
2413
	list_add(&page->pcp_list, &pcp->lists[pindex]);
2414
	pcp->count += 1 << order;
2415 2416 2417 2418 2419 2420 2421 2422 2423 2424

	/*
	 * As high-order pages other than THP's stored on PCP can contribute
	 * to fragmentation, limit the number stored when PCP is heavily
	 * freeing without allocation. The remainder after bulk freeing
	 * stops will be drained from vmstat refresh context.
	 */
	free_high = (pcp->free_factor && order && order <= PAGE_ALLOC_COSTLY_ORDER);

	high = nr_pcp_high(pcp, zone, free_high);
2425 2426 2427
	if (pcp->count >= high) {
		int batch = READ_ONCE(pcp->batch);

2428
		free_pcppages_bulk(zone, nr_pcp_free(pcp, high, batch, free_high), pcp, pindex);
2429
	}
2430
}
2431

2432
/*
2433
 * Free a pcp page
2434
 */
2435
void free_unref_page(struct page *page, unsigned int order)
2436
{
2437 2438 2439
	unsigned long __maybe_unused UP_flags;
	struct per_cpu_pages *pcp;
	struct zone *zone;
2440
	unsigned long pfn = page_to_pfn(page);
2441
	int migratetype;
2442

2443
	if (!free_unref_page_prepare(page, pfn, order))
2444
		return;
2445

2446 2447
	/*
	 * We only track unmovable, reclaimable and movable on pcp lists.
2448
	 * Place ISOLATE pages on the isolated list because they are being
2449
	 * offlined but treat HIGHATOMIC as movable pages so we can get those
2450 2451 2452
	 * areas back if necessary. Otherwise, we may have to free
	 * excessively into the page allocator
	 */
2453 2454
	migratetype = get_pcppage_migratetype(page);
	if (unlikely(migratetype >= MIGRATE_PCPTYPES)) {
2455
		if (unlikely(is_migrate_isolate(migratetype))) {
2456
			free_one_page(page_zone(page), page, pfn, order, migratetype, FPI_NONE);
2457
			return;
2458 2459 2460 2461
		}
		migratetype = MIGRATE_MOVABLE;
	}

2462 2463
	zone = page_zone(page);
	pcp_trylock_prepare(UP_flags);
2464
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
2465
	if (pcp) {
2466
		free_unref_page_commit(zone, pcp, page, migratetype, order);
2467
		pcp_spin_unlock(pcp);
2468 2469 2470 2471
	} else {
		free_one_page(zone, page, pfn, order, migratetype, FPI_NONE);
	}
	pcp_trylock_finish(UP_flags);
Linus Torvalds's avatar
Linus Torvalds committed
2472 2473
}

2474 2475 2476
/*
 * Free a list of 0-order pages
 */
2477
void free_unref_page_list(struct list_head *list)
2478
{
2479
	unsigned long __maybe_unused UP_flags;
2480
	struct page *page, *next;
2481 2482
	struct per_cpu_pages *pcp = NULL;
	struct zone *locked_zone = NULL;
2483
	int batch_count = 0;
2484
	int migratetype;
2485 2486 2487

	/* Prepare pages for freeing */
	list_for_each_entry_safe(page, next, list, lru) {
2488
		unsigned long pfn = page_to_pfn(page);
2489
		if (!free_unref_page_prepare(page, pfn, 0)) {
2490
			list_del(&page->lru);
2491 2492
			continue;
		}
2493 2494 2495 2496 2497 2498

		/*
		 * Free isolated pages directly to the allocator, see
		 * comment in free_unref_page.
		 */
		migratetype = get_pcppage_migratetype(page);
2499 2500 2501 2502
		if (unlikely(is_migrate_isolate(migratetype))) {
			list_del(&page->lru);
			free_one_page(page_zone(page), page, pfn, 0, migratetype, FPI_NONE);
			continue;
2503
		}
2504
	}
2505 2506

	list_for_each_entry_safe(page, next, list, lru) {
2507 2508
		struct zone *zone = page_zone(page);

2509
		list_del(&page->lru);
2510
		migratetype = get_pcppage_migratetype(page);
2511

2512 2513 2514 2515 2516 2517
		/*
		 * Either different zone requiring a different pcp lock or
		 * excessive lock hold times when freeing a large list of
		 * pages.
		 */
		if (zone != locked_zone || batch_count == SWAP_CLUSTER_MAX) {
2518 2519 2520 2521
			if (pcp) {
				pcp_spin_unlock(pcp);
				pcp_trylock_finish(UP_flags);
			}
2522

2523 2524
			batch_count = 0;

2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537
			/*
			 * trylock is necessary as pages may be getting freed
			 * from IRQ or SoftIRQ context after an IO completion.
			 */
			pcp_trylock_prepare(UP_flags);
			pcp = pcp_spin_trylock(zone->per_cpu_pageset);
			if (unlikely(!pcp)) {
				pcp_trylock_finish(UP_flags);
				free_one_page(zone, page, page_to_pfn(page),
					      0, migratetype, FPI_NONE);
				locked_zone = NULL;
				continue;
			}
2538 2539 2540
			locked_zone = zone;
		}

2541 2542 2543 2544 2545 2546 2547
		/*
		 * Non-isolated types over MIGRATE_PCPTYPES get added
		 * to the MIGRATE_MOVABLE pcp list.
		 */
		if (unlikely(migratetype >= MIGRATE_PCPTYPES))
			migratetype = MIGRATE_MOVABLE;

2548
		trace_mm_page_free_batched(page);
2549
		free_unref_page_commit(zone, pcp, page, migratetype, 0);
2550
		batch_count++;
2551
	}
2552

2553 2554 2555 2556
	if (pcp) {
		pcp_spin_unlock(pcp);
		pcp_trylock_finish(UP_flags);
	}
2557 2558
}

2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570
/*
 * split_page takes a non-compound higher-order page, and splits it into
 * n (1<<order) sub-pages: page[0..n]
 * Each sub-page must be freed individually.
 *
 * Note: this is probably too low level an operation for use in drivers.
 * Please consult with lkml before using this in your driver.
 */
void split_page(struct page *page, unsigned int order)
{
	int i;

2571 2572
	VM_BUG_ON_PAGE(PageCompound(page), page);
	VM_BUG_ON_PAGE(!page_count(page), page);
2573

2574
	for (i = 1; i < (1 << order); i++)
2575
		set_page_refcounted(page + i);
2576
	split_page_owner(page, 1 << order);
2577
	split_page_memcg(page, 1 << order);
2578
}
K. Y. Srinivasan's avatar
K. Y. Srinivasan committed
2579
EXPORT_SYMBOL_GPL(split_page);
2580

2581
int __isolate_free_page(struct page *page, unsigned int order)
2582
{
2583 2584
	struct zone *zone = page_zone(page);
	int mt = get_pageblock_migratetype(page);
2585

2586
	if (!is_migrate_isolate(mt)) {
2587
		unsigned long watermark;
2588 2589 2590 2591 2592 2593
		/*
		 * Obey watermarks as if the page was being allocated. We can
		 * emulate a high-order watermark check with a raised order-0
		 * watermark, because we already know our high-order page
		 * exists.
		 */
2594
		watermark = zone->_watermark[WMARK_MIN] + (1UL << order);
2595
		if (!zone_watermark_ok(zone, 0, watermark, 0, ALLOC_CMA))
2596 2597
			return 0;

2598
		__mod_zone_freepage_state(zone, -(1UL << order), mt);
2599
	}
2600

2601
	del_page_from_free_list(page, zone, order);
2602

2603 2604 2605 2606
	/*
	 * Set the pageblock if the isolated page is at least half of a
	 * pageblock
	 */
2607 2608
	if (order >= pageblock_order - 1) {
		struct page *endpage = page + (1 << order) - 1;
2609 2610
		for (; page < endpage; page += pageblock_nr_pages) {
			int mt = get_pageblock_migratetype(page);
2611 2612 2613 2614 2615
			/*
			 * Only change normal pageblocks (i.e., they can merge
			 * with others)
			 */
			if (migratetype_is_mergeable(mt))
2616 2617 2618
				set_pageblock_migratetype(page,
							  MIGRATE_MOVABLE);
		}
2619 2620
	}

2621
	return 1UL << order;
2622 2623
}

2624 2625 2626 2627
/**
 * __putback_isolated_page - Return a now-isolated page back where we got it
 * @page: Page that was isolated
 * @order: Order of the isolated page
2628
 * @mt: The page's pageblock's migratetype
2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640
 *
 * This function is meant to return a page pulled from the free lists via
 * __isolate_free_page back to the free lists they were pulled from.
 */
void __putback_isolated_page(struct page *page, unsigned int order, int mt)
{
	struct zone *zone = page_zone(page);

	/* zone lock should be held when this function is called */
	lockdep_assert_held(&zone->lock);

	/* Return isolated page to tail of freelist. */
2641
	__free_one_page(page, page_to_pfn(page), zone, order, mt,
2642
			FPI_SKIP_REPORT_NOTIFY | FPI_TO_TAIL);
2643 2644
}

2645 2646 2647
/*
 * Update NUMA hit/miss statistics
 */
2648 2649
static inline void zone_statistics(struct zone *preferred_zone, struct zone *z,
				   long nr_account)
2650 2651
{
#ifdef CONFIG_NUMA
2652
	enum numa_stat_item local_stat = NUMA_LOCAL;
2653

2654 2655 2656 2657
	/* skip numa counters update if numa stats is disabled */
	if (!static_branch_likely(&vm_numa_stat_key))
		return;

2658
	if (zone_to_nid(z) != numa_node_id())
2659 2660
		local_stat = NUMA_OTHER;

2661
	if (zone_to_nid(z) == zone_to_nid(preferred_zone))
2662
		__count_numa_events(z, NUMA_HIT, nr_account);
2663
	else {
2664 2665
		__count_numa_events(z, NUMA_MISS, nr_account);
		__count_numa_events(preferred_zone, NUMA_FOREIGN, nr_account);
2666
	}
2667
	__count_numa_events(z, local_stat, nr_account);
2668 2669 2670
#endif
}

2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687
static __always_inline
struct page *rmqueue_buddy(struct zone *preferred_zone, struct zone *zone,
			   unsigned int order, unsigned int alloc_flags,
			   int migratetype)
{
	struct page *page;
	unsigned long flags;

	do {
		page = NULL;
		spin_lock_irqsave(&zone->lock, flags);
		/*
		 * order-0 request can reach here when the pcplist is skipped
		 * due to non-CMA allocation context. HIGHATOMIC area is
		 * reserved for high-order atomic allocation, so order-0
		 * request should skip it.
		 */
2688
		if (alloc_flags & ALLOC_HIGHATOMIC)
2689 2690 2691
			page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
		if (!page) {
			page = __rmqueue(zone, order, migratetype, alloc_flags);
2692 2693 2694 2695 2696 2697 2698 2699 2700 2701

			/*
			 * If the allocation fails, allow OOM handling access
			 * to HIGHATOMIC reserves as failing now is worse than
			 * failing a high-order atomic allocation in the
			 * future.
			 */
			if (!page && (alloc_flags & ALLOC_OOM))
				page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);

2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717
			if (!page) {
				spin_unlock_irqrestore(&zone->lock, flags);
				return NULL;
			}
		}
		__mod_zone_freepage_state(zone, -(1 << order),
					  get_pcppage_migratetype(page));
		spin_unlock_irqrestore(&zone->lock, flags);
	} while (check_new_pages(page, order));

	__count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
	zone_statistics(preferred_zone, zone, 1);

	return page;
}

2718
/* Remove page from the per-cpu list, caller must protect the list */
2719
static inline
2720 2721
struct page *__rmqueue_pcplist(struct zone *zone, unsigned int order,
			int migratetype,
2722
			unsigned int alloc_flags,
Mel Gorman's avatar
Mel Gorman committed
2723
			struct per_cpu_pages *pcp,
2724 2725 2726 2727 2728 2729
			struct list_head *list)
{
	struct page *page;

	do {
		if (list_empty(list)) {
2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743
			int batch = READ_ONCE(pcp->batch);
			int alloced;

			/*
			 * Scale batch relative to order if batch implies
			 * free pages can be stored on the PCP. Batch can
			 * be 1 for small zones or for boot pagesets which
			 * should never store free pages as the pages may
			 * belong to arbitrary zones.
			 */
			if (batch > 1)
				batch = max(batch >> order, 2);
			alloced = rmqueue_bulk(zone, order,
					batch, list,
2744
					migratetype, alloc_flags);
2745 2746

			pcp->count += alloced << order;
2747 2748 2749 2750
			if (unlikely(list_empty(list)))
				return NULL;
		}

2751 2752
		page = list_first_entry(list, struct page, pcp_list);
		list_del(&page->pcp_list);
2753
		pcp->count -= 1 << order;
2754
	} while (check_new_pages(page, order));
2755 2756 2757 2758 2759 2760

	return page;
}

/* Lock and remove page from the per-cpu list */
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
2761
			struct zone *zone, unsigned int order,
2762
			int migratetype, unsigned int alloc_flags)
2763 2764 2765 2766
{
	struct per_cpu_pages *pcp;
	struct list_head *list;
	struct page *page;
2767
	unsigned long __maybe_unused UP_flags;
2768

2769
	/* spin_trylock may fail due to a parallel drain or IRQ reentrancy. */
2770
	pcp_trylock_prepare(UP_flags);
2771
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
2772
	if (!pcp) {
2773 2774 2775
		pcp_trylock_finish(UP_flags);
		return NULL;
	}
2776 2777 2778 2779 2780 2781 2782

	/*
	 * On allocation, reduce the number of pages that are batch freed.
	 * See nr_pcp_free() where free_factor is increased for subsequent
	 * frees.
	 */
	pcp->free_factor >>= 1;
2783 2784
	list = &pcp->lists[order_to_pindex(migratetype, order)];
	page = __rmqueue_pcplist(zone, order, migratetype, alloc_flags, pcp, list);
2785
	pcp_spin_unlock(pcp);
2786
	pcp_trylock_finish(UP_flags);
2787
	if (page) {
2788
		__count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2789
		zone_statistics(preferred_zone, zone, 1);
2790 2791 2792 2793
	}
	return page;
}

Linus Torvalds's avatar
Linus Torvalds committed
2794
/*
2795 2796
 * Allocate a page from the given zone.
 * Use pcplists for THP or "cheap" high-order allocations.
Linus Torvalds's avatar
Linus Torvalds committed
2797
 */
2798 2799 2800 2801 2802 2803

/*
 * Do not instrument rmqueue() with KMSAN. This function may call
 * __msan_poison_alloca() through a call to set_pfnblock_flags_mask().
 * If __msan_poison_alloca() attempts to allocate pages for the stack depot, it
 * may call rmqueue() again, which will result in a deadlock.
Linus Torvalds's avatar
Linus Torvalds committed
2804
 */
2805
__no_sanitize_memory
2806
static inline
2807
struct page *rmqueue(struct zone *preferred_zone,
2808
			struct zone *zone, unsigned int order,
2809 2810
			gfp_t gfp_flags, unsigned int alloc_flags,
			int migratetype)
Linus Torvalds's avatar
Linus Torvalds committed
2811
{
2812
	struct page *page;
Linus Torvalds's avatar
Linus Torvalds committed
2813

2814 2815 2816 2817 2818 2819
	/*
	 * We most definitely don't want callers attempting to
	 * allocate greater than order-1 page units with __GFP_NOFAIL.
	 */
	WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));

2820
	if (likely(pcp_allowed_order(order))) {
2821 2822 2823 2824 2825 2826
		/*
		 * MIGRATE_MOVABLE pcplist could have the pages on CMA area and
		 * we need to skip it when CMA area isn't allowed.
		 */
		if (!IS_ENABLED(CONFIG_CMA) || alloc_flags & ALLOC_CMA ||
				migratetype != MIGRATE_MOVABLE) {
2827
			page = rmqueue_pcplist(preferred_zone, zone, order,
2828
					migratetype, alloc_flags);
2829 2830
			if (likely(page))
				goto out;
2831
		}
2832
	}
2833

2834 2835
	page = rmqueue_buddy(preferred_zone, zone, order, alloc_flags,
							migratetype);
Linus Torvalds's avatar
Linus Torvalds committed
2836

2837
out:
2838
	/* Separate test+clear to avoid unnecessary atomics */
2839 2840
	if ((alloc_flags & ALLOC_KSWAPD) &&
	    unlikely(test_bit(ZONE_BOOSTED_WATERMARK, &zone->flags))) {
2841 2842 2843 2844
		clear_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
		wakeup_kswapd(zone, 0, 0, zone_idx(zone));
	}

2845
	VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
Linus Torvalds's avatar
Linus Torvalds committed
2846 2847 2848
	return page;
}

2849
noinline bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
2850 2851 2852 2853 2854
{
	return __should_fail_alloc_page(gfp_mask, order);
}
ALLOW_ERROR_INJECTION(should_fail_alloc_page, TRUE);

2855 2856 2857 2858 2859 2860
static inline long __zone_watermark_unusable_free(struct zone *z,
				unsigned int order, unsigned int alloc_flags)
{
	long unusable_free = (1 << order) - 1;

	/*
2861 2862 2863
	 * If the caller does not have rights to reserves below the min
	 * watermark then subtract the high-atomic reserves. This will
	 * over-estimate the size of the atomic reserve but it avoids a search.
2864
	 */
2865
	if (likely(!(alloc_flags & ALLOC_RESERVES)))
2866 2867 2868 2869 2870 2871 2872
		unusable_free += z->nr_reserved_highatomic;

#ifdef CONFIG_CMA
	/* If allocation can't use CMA areas don't use free CMA pages */
	if (!(alloc_flags & ALLOC_CMA))
		unusable_free += zone_page_state(z, NR_FREE_CMA_PAGES);
#endif
2873 2874 2875
#ifdef CONFIG_UNACCEPTED_MEMORY
	unusable_free += zone_page_state(z, NR_UNACCEPTED);
#endif
2876 2877 2878 2879

	return unusable_free;
}

Linus Torvalds's avatar
Linus Torvalds committed
2880
/*
2881 2882 2883 2884
 * Return true if free base pages are above 'mark'. For high-order checks it
 * will return true of the order-0 watermark is reached and there is at least
 * one free page of a suitable size. Checking now avoids taking the zone lock
 * to check in the allocation paths if no pages are free.
Linus Torvalds's avatar
Linus Torvalds committed
2885
 */
2886
bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
2887
			 int highest_zoneidx, unsigned int alloc_flags,
2888
			 long free_pages)
Linus Torvalds's avatar
Linus Torvalds committed
2889
{
2890
	long min = mark;
Linus Torvalds's avatar
Linus Torvalds committed
2891 2892
	int o;

2893
	/* free_pages may go negative - that's OK */
2894
	free_pages -= __zone_watermark_unusable_free(z, order, alloc_flags);
2895

2896 2897 2898 2899 2900
	if (unlikely(alloc_flags & ALLOC_RESERVES)) {
		/*
		 * __GFP_HIGH allows access to 50% of the min reserve as well
		 * as OOM.
		 */
2901
		if (alloc_flags & ALLOC_MIN_RESERVE) {
2902
			min -= min / 2;
2903

2904 2905 2906 2907 2908 2909 2910 2911 2912 2913
			/*
			 * Non-blocking allocations (e.g. GFP_ATOMIC) can
			 * access more reserves than just __GFP_HIGH. Other
			 * non-blocking allocations requests such as GFP_NOWAIT
			 * or (GFP_KERNEL & ~__GFP_DIRECT_RECLAIM) do not get
			 * access to the min reserve.
			 */
			if (alloc_flags & ALLOC_NON_BLOCK)
				min -= min / 4;
		}
2914

2915
		/*
2916
		 * OOM victims can try even harder than the normal reserve
2917 2918 2919 2920 2921 2922 2923 2924
		 * users on the grounds that it's definitely going to be in
		 * the exit path shortly and free memory. Any allocation it
		 * makes during the free path will be small and short-lived.
		 */
		if (alloc_flags & ALLOC_OOM)
			min -= min / 2;
	}

2925 2926 2927 2928 2929
	/*
	 * Check watermarks for an order-0 allocation request. If these
	 * are not met, then a high-order request also cannot go ahead
	 * even if a suitable page happened to be free.
	 */
2930
	if (free_pages <= min + z->lowmem_reserve[highest_zoneidx])
2931
		return false;
Linus Torvalds's avatar
Linus Torvalds committed
2932

2933 2934 2935 2936 2937
	/* If this is an order-0 request then the watermark is fine */
	if (!order)
		return true;

	/* For a high-order request, check at least one suitable page is free */
2938
	for (o = order; o <= MAX_ORDER; o++) {
2939 2940 2941 2942 2943 2944 2945
		struct free_area *area = &z->free_area[o];
		int mt;

		if (!area->nr_free)
			continue;

		for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
2946
			if (!free_area_empty(area, mt))
2947 2948 2949 2950
				return true;
		}

#ifdef CONFIG_CMA
2951
		if ((alloc_flags & ALLOC_CMA) &&
2952
		    !free_area_empty(area, MIGRATE_CMA)) {
2953
			return true;
2954
		}
2955
#endif
2956 2957
		if ((alloc_flags & (ALLOC_HIGHATOMIC|ALLOC_OOM)) &&
		    !free_area_empty(area, MIGRATE_HIGHATOMIC)) {
2958
			return true;
2959
		}
Linus Torvalds's avatar
Linus Torvalds committed
2960
	}
2961
	return false;
2962 2963
}

2964
bool zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
2965
		      int highest_zoneidx, unsigned int alloc_flags)
2966
{
2967
	return __zone_watermark_ok(z, order, mark, highest_zoneidx, alloc_flags,
2968 2969 2970
					zone_page_state(z, NR_FREE_PAGES));
}

2971
static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
2972
				unsigned long mark, int highest_zoneidx,
2973
				unsigned int alloc_flags, gfp_t gfp_mask)
2974
{
2975
	long free_pages;
2976

2977
	free_pages = zone_page_state(z, NR_FREE_PAGES);
2978 2979 2980

	/*
	 * Fast check for order-0 only. If this fails then the reserves
2981
	 * need to be calculated.
2982
	 */
2983
	if (!order) {
2984 2985
		long usable_free;
		long reserved;
2986

2987 2988 2989 2990 2991 2992
		usable_free = free_pages;
		reserved = __zone_watermark_unusable_free(z, 0, alloc_flags);

		/* reserved may over estimate high-atomic reserves. */
		usable_free -= min(usable_free, reserved);
		if (usable_free > mark + z->lowmem_reserve[highest_zoneidx])
2993 2994
			return true;
	}
2995

2996 2997 2998
	if (__zone_watermark_ok(z, order, mark, highest_zoneidx, alloc_flags,
					free_pages))
		return true;
NeilBrown's avatar
NeilBrown committed
2999

3000
	/*
NeilBrown's avatar
NeilBrown committed
3001
	 * Ignore watermark boosting for __GFP_HIGH order-0 allocations
3002 3003 3004 3005
	 * when checking the min watermark. The min watermark is the
	 * point where boosting is ignored so that kswapd is woken up
	 * when below the low watermark.
	 */
NeilBrown's avatar
NeilBrown committed
3006
	if (unlikely(!order && (alloc_flags & ALLOC_MIN_RESERVE) && z->watermark_boost
3007 3008 3009 3010 3011 3012 3013
		&& ((alloc_flags & ALLOC_WMARK_MASK) == WMARK_MIN))) {
		mark = z->_watermark[WMARK_MIN];
		return __zone_watermark_ok(z, order, mark, highest_zoneidx,
					alloc_flags, free_pages);
	}

	return false;
3014 3015
}

3016
bool zone_watermark_ok_safe(struct zone *z, unsigned int order,
3017
			unsigned long mark, int highest_zoneidx)
3018 3019 3020 3021 3022 3023
{
	long free_pages = zone_page_state(z, NR_FREE_PAGES);

	if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
		free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);

3024
	return __zone_watermark_ok(z, order, mark, highest_zoneidx, 0,
3025
								free_pages);
Linus Torvalds's avatar
Linus Torvalds committed
3026 3027
}

3028
#ifdef CONFIG_NUMA
3029 3030
int __read_mostly node_reclaim_distance = RECLAIM_DISTANCE;

3031 3032
static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
{
3033
	return node_distance(zone_to_nid(local_zone), zone_to_nid(zone)) <=
3034
				node_reclaim_distance;
3035
}
3036
#else	/* CONFIG_NUMA */
3037 3038 3039 3040
static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
{
	return true;
}
3041 3042
#endif	/* CONFIG_NUMA */

3043 3044 3045 3046 3047 3048 3049 3050 3051
/*
 * The restriction on ZONE_DMA32 as being a suitable zone to use to avoid
 * fragmentation is subtle. If the preferred zone was HIGHMEM then
 * premature use of a lower zone may cause lowmem pressure problems that
 * are worse than fragmentation. If the next zone is ZONE_DMA then it is
 * probably too small. It only makes sense to spread allocations to avoid
 * fragmentation between the Normal and DMA32 zones.
 */
static inline unsigned int
3052
alloc_flags_nofragment(struct zone *zone, gfp_t gfp_mask)
3053
{
3054
	unsigned int alloc_flags;
3055

3056 3057 3058 3059 3060
	/*
	 * __GFP_KSWAPD_RECLAIM is assumed to be the same as ALLOC_KSWAPD
	 * to save a branch.
	 */
	alloc_flags = (__force int) (gfp_mask & __GFP_KSWAPD_RECLAIM);
3061 3062

#ifdef CONFIG_ZONE_DMA32
3063 3064 3065
	if (!zone)
		return alloc_flags;

3066
	if (zone_idx(zone) != ZONE_NORMAL)
3067
		return alloc_flags;
3068 3069 3070 3071 3072 3073 3074 3075

	/*
	 * If ZONE_DMA32 exists, assume it is the one after ZONE_NORMAL and
	 * the pointer is within zone->zone_pgdat->node_zones[]. Also assume
	 * on UMA that if Normal is populated then so is DMA32.
	 */
	BUILD_BUG_ON(ZONE_NORMAL - ZONE_DMA32 != 1);
	if (nr_online_nodes > 1 && !populated_zone(--zone))
3076
		return alloc_flags;
3077

3078
	alloc_flags |= ALLOC_NOFRAGMENT;
3079 3080
#endif /* CONFIG_ZONE_DMA32 */
	return alloc_flags;
3081 3082
}

3083 3084 3085
/* Must be called after current_gfp_context() which can change gfp_mask */
static inline unsigned int gfp_to_alloc_flags_cma(gfp_t gfp_mask,
						  unsigned int alloc_flags)
3086 3087
{
#ifdef CONFIG_CMA
3088
	if (gfp_migratetype(gfp_mask) == MIGRATE_MOVABLE)
3089 3090 3091 3092 3093
		alloc_flags |= ALLOC_CMA;
#endif
	return alloc_flags;
}

3094
/*
3095
 * get_page_from_freelist goes through the zonelist trying to allocate
3096 3097 3098
 * a page.
 */
static struct page *
3099 3100
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
						const struct alloc_context *ac)
3101
{
3102
	struct zoneref *z;
3103
	struct zone *zone;
3104 3105
	struct pglist_data *last_pgdat = NULL;
	bool last_pgdat_dirty_ok = false;
3106
	bool no_fallback;
3107

3108
retry:
3109
	/*
3110
	 * Scan zonelist, looking for a zone with enough free.
3111
	 * See also cpuset_node_allowed() comment in kernel/cgroup/cpuset.c.
3112
	 */
3113 3114
	no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
	z = ac->preferred_zoneref;
3115 3116
	for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
					ac->nodemask) {
3117
		struct page *page;
3118 3119
		unsigned long mark;

3120 3121
		if (cpusets_enabled() &&
			(alloc_flags & ALLOC_CPUSET) &&
3122
			!__cpuset_zone_allowed(zone, gfp_mask))
3123
				continue;
3124 3125
		/*
		 * When allocating a page cache page for writing, we
3126 3127
		 * want to get it from a node that is within its dirty
		 * limit, such that no single node holds more than its
3128
		 * proportional share of globally allowed dirty pages.
3129
		 * The dirty limits take into account the node's
3130 3131 3132 3133 3134
		 * lowmem reserves and high watermark so that kswapd
		 * should be able to balance it without having to
		 * write pages from its LRU list.
		 *
		 * XXX: For now, allow allocations to potentially
3135
		 * exceed the per-node dirty limit in the slowpath
3136
		 * (spread_dirty_pages unset) before going into reclaim,
3137
		 * which is important when on a NUMA setup the allowed
3138
		 * nodes are together not big enough to reach the
3139
		 * global limit.  The proper fix for these situations
3140
		 * will require awareness of nodes in the
3141 3142
		 * dirty-throttling and the flusher threads.
		 */
3143
		if (ac->spread_dirty_pages) {
3144 3145 3146 3147
			if (last_pgdat != zone->zone_pgdat) {
				last_pgdat = zone->zone_pgdat;
				last_pgdat_dirty_ok = node_dirty_ok(zone->zone_pgdat);
			}
3148

3149
			if (!last_pgdat_dirty_ok)
3150 3151
				continue;
		}
3152

3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168
		if (no_fallback && nr_online_nodes > 1 &&
		    zone != ac->preferred_zoneref->zone) {
			int local_nid;

			/*
			 * If moving to a remote node, retry but allow
			 * fragmenting fallbacks. Locality is more important
			 * than fragmentation avoidance.
			 */
			local_nid = zone_to_nid(ac->preferred_zoneref->zone);
			if (zone_to_nid(zone) != local_nid) {
				alloc_flags &= ~ALLOC_NOFRAGMENT;
				goto retry;
			}
		}

3169
		mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);
3170
		if (!zone_watermark_fast(zone, order, mark,
3171 3172
				       ac->highest_zoneidx, alloc_flags,
				       gfp_mask)) {
3173 3174
			int ret;

3175 3176 3177 3178 3179
			if (has_unaccepted_memory()) {
				if (try_to_accept_memory(zone, order))
					goto try_this_zone;
			}

3180 3181 3182 3183 3184
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/*
			 * Watermark failed for this zone, but see if we can
			 * grow this zone if it contains deferred pages.
			 */
3185
			if (deferred_pages_enabled()) {
3186 3187 3188 3189
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
3190 3191 3192 3193 3194
			/* Checked here to keep the fast path fast */
			BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
			if (alloc_flags & ALLOC_NO_WATERMARKS)
				goto try_this_zone;

3195
			if (!node_reclaim_enabled() ||
3196
			    !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
3197 3198
				continue;

3199
			ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
3200
			switch (ret) {
3201
			case NODE_RECLAIM_NOSCAN:
3202
				/* did not scan */
3203
				continue;
3204
			case NODE_RECLAIM_FULL:
3205
				/* scanned but unreclaimable */
3206
				continue;
3207 3208
			default:
				/* did we reclaim enough */
3209
				if (zone_watermark_ok(zone, order, mark,
3210
					ac->highest_zoneidx, alloc_flags))
3211 3212 3213
					goto try_this_zone;

				continue;
3214
			}
3215 3216
		}

3217
try_this_zone:
3218
		page = rmqueue(ac->preferred_zoneref->zone, zone, order,
3219
				gfp_mask, alloc_flags, ac->migratetype);
3220
		if (page) {
3221
			prep_new_page(page, order, gfp_mask, alloc_flags);
3222 3223 3224 3225 3226

			/*
			 * If this is a high-order atomic allocation then check
			 * if the pageblock should be reserved for the future
			 */
3227
			if (unlikely(alloc_flags & ALLOC_HIGHATOMIC))
3228 3229
				reserve_highatomic_pageblock(page, zone, order);

3230
			return page;
3231
		} else {
3232 3233 3234 3235 3236
			if (has_unaccepted_memory()) {
				if (try_to_accept_memory(zone, order))
					goto try_this_zone;
			}

3237 3238
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/* Try again if zone has deferred pages */
3239
			if (deferred_pages_enabled()) {
3240 3241 3242 3243
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
3244
		}
3245
	}
3246

3247 3248 3249 3250 3251 3252 3253 3254 3255
	/*
	 * It's possible on a UMA machine to get through all zones that are
	 * fragmented. If avoiding fragmentation, reset and try again.
	 */
	if (no_fallback) {
		alloc_flags &= ~ALLOC_NOFRAGMENT;
		goto retry;
	}

3256
	return NULL;
3257 3258
}

3259
static void warn_alloc_show_mem(gfp_t gfp_mask, nodemask_t *nodemask)
3260 3261 3262 3263 3264 3265 3266 3267 3268
{
	unsigned int filter = SHOW_MEM_FILTER_NODES;

	/*
	 * This documents exceptions given to allocations in certain
	 * contexts that are allowed to allocate outside current's set
	 * of allowed nodes.
	 */
	if (!(gfp_mask & __GFP_NOMEMALLOC))
3269
		if (tsk_is_oom_victim(current) ||
3270 3271
		    (current->flags & (PF_MEMALLOC | PF_EXITING)))
			filter &= ~SHOW_MEM_FILTER_NODES;
3272
	if (!in_task() || !(gfp_mask & __GFP_DIRECT_RECLAIM))
3273 3274
		filter &= ~SHOW_MEM_FILTER_NODES;

3275
	__show_mem(filter, nodemask, gfp_zone(gfp_mask));
3276 3277
}

3278
void warn_alloc(gfp_t gfp_mask, nodemask_t *nodemask, const char *fmt, ...)
3279 3280 3281
{
	struct va_format vaf;
	va_list args;
3282
	static DEFINE_RATELIMIT_STATE(nopage_rs, 10*HZ, 1);
3283

3284 3285 3286
	if ((gfp_mask & __GFP_NOWARN) ||
	     !__ratelimit(&nopage_rs) ||
	     ((gfp_mask & __GFP_DMA) && !has_managed_dma()))
3287 3288
		return;

3289 3290 3291
	va_start(args, fmt);
	vaf.fmt = fmt;
	vaf.va = &args;
3292
	pr_warn("%s: %pV, mode:%#x(%pGg), nodemask=%*pbl",
3293 3294
			current->comm, &vaf, gfp_mask, &gfp_mask,
			nodemask_pr_args(nodemask));
3295
	va_end(args);
Joe Perches's avatar
Joe Perches committed
3296

3297
	cpuset_print_current_mems_allowed();
3298
	pr_cont("\n");
3299
	dump_stack();
3300
	warn_alloc_show_mem(gfp_mask, nodemask);
3301 3302
}

3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322
static inline struct page *
__alloc_pages_cpuset_fallback(gfp_t gfp_mask, unsigned int order,
			      unsigned int alloc_flags,
			      const struct alloc_context *ac)
{
	struct page *page;

	page = get_page_from_freelist(gfp_mask, order,
			alloc_flags|ALLOC_CPUSET, ac);
	/*
	 * fallback to ignore cpuset restriction if our nodes
	 * are depleted
	 */
	if (!page)
		page = get_page_from_freelist(gfp_mask, order,
				alloc_flags, ac);

	return page;
}

3323 3324
static inline struct page *
__alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
3325
	const struct alloc_context *ac, unsigned long *did_some_progress)
3326
{
3327 3328 3329
	struct oom_control oc = {
		.zonelist = ac->zonelist,
		.nodemask = ac->nodemask,
3330
		.memcg = NULL,
3331 3332 3333
		.gfp_mask = gfp_mask,
		.order = order,
	};
3334 3335
	struct page *page;

3336 3337 3338
	*did_some_progress = 0;

	/*
3339 3340
	 * Acquire the oom lock.  If that fails, somebody else is
	 * making progress for us.
3341
	 */
3342
	if (!mutex_trylock(&oom_lock)) {
3343
		*did_some_progress = 1;
3344
		schedule_timeout_uninterruptible(1);
Linus Torvalds's avatar
Linus Torvalds committed
3345 3346
		return NULL;
	}
3347

3348 3349 3350
	/*
	 * Go through the zonelist yet one more time, keep very high watermark
	 * here, this is only to catch a parallel oom killing, we must fail if
3351 3352 3353
	 * we're still under heavy pressure. But make sure that this reclaim
	 * attempt shall not depend on __GFP_DIRECT_RECLAIM && !__GFP_NORETRY
	 * allocation which will never fail due to oom_lock already held.
3354
	 */
3355 3356 3357
	page = get_page_from_freelist((gfp_mask | __GFP_HARDWALL) &
				      ~__GFP_DIRECT_RECLAIM, order,
				      ALLOC_WMARK_HIGH|ALLOC_CPUSET, ac);
3358
	if (page)
3359 3360
		goto out;

3361 3362 3363 3364 3365 3366
	/* Coredumps can quickly deplete all memory reserves */
	if (current->flags & PF_DUMPCORE)
		goto out;
	/* The OOM killer will not help higher order allocs */
	if (order > PAGE_ALLOC_COSTLY_ORDER)
		goto out;
3367 3368 3369 3370 3371
	/*
	 * We have already exhausted all our reclaim opportunities without any
	 * success so it is time to admit defeat. We will skip the OOM killer
	 * because it is very likely that the caller has a more reasonable
	 * fallback than shooting a random task.
3372 3373
	 *
	 * The OOM killer may not free memory on a specific node.
3374
	 */
3375
	if (gfp_mask & (__GFP_RETRY_MAYFAIL | __GFP_THISNODE))
3376
		goto out;
3377
	/* The OOM killer does not needlessly kill tasks for lowmem */
3378
	if (ac->highest_zoneidx < ZONE_NORMAL)
3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391
		goto out;
	if (pm_suspended_storage())
		goto out;
	/*
	 * XXX: GFP_NOFS allocations should rather fail than rely on
	 * other request to make a forward progress.
	 * We are in an unfortunate situation where out_of_memory cannot
	 * do much for this context but let's try it to at least get
	 * access to memory reserved if the current task is killed (see
	 * out_of_memory). Once filesystems are ready to handle allocation
	 * failures more gracefully we should just bail out here.
	 */

3392
	/* Exhausted what can be done so it's blame time */
3393 3394
	if (out_of_memory(&oc) ||
	    WARN_ON_ONCE_GFP(gfp_mask & __GFP_NOFAIL, gfp_mask)) {
3395
		*did_some_progress = 1;
3396

3397 3398 3399 3400 3401 3402
		/*
		 * Help non-failing allocations by giving them access to memory
		 * reserves
		 */
		if (gfp_mask & __GFP_NOFAIL)
			page = __alloc_pages_cpuset_fallback(gfp_mask, order,
3403 3404
					ALLOC_NO_WATERMARKS, ac);
	}
3405
out:
3406
	mutex_unlock(&oom_lock);
3407 3408 3409
	return page;
}

3410
/*
Lu Jialin's avatar
Lu Jialin committed
3411
 * Maximum number of compaction retries with a progress before OOM
3412 3413 3414 3415
 * killer is consider as the only way to move forward.
 */
#define MAX_COMPACT_RETRIES 16

3416 3417 3418 3419
#ifdef CONFIG_COMPACTION
/* Try memory compaction for high-order allocations before reclaim */
static struct page *
__alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3420
		unsigned int alloc_flags, const struct alloc_context *ac,
3421
		enum compact_priority prio, enum compact_result *compact_result)
3422
{
3423
	struct page *page = NULL;
3424
	unsigned long pflags;
3425
	unsigned int noreclaim_flag;
3426 3427

	if (!order)
3428 3429
		return NULL;

3430
	psi_memstall_enter(&pflags);
3431
	delayacct_compact_start();
3432
	noreclaim_flag = memalloc_noreclaim_save();
3433

3434
	*compact_result = try_to_compact_pages(gfp_mask, order, alloc_flags, ac,
3435
								prio, &page);
3436

3437
	memalloc_noreclaim_restore(noreclaim_flag);
3438
	psi_memstall_leave(&pflags);
3439
	delayacct_compact_end();
3440

3441 3442
	if (*compact_result == COMPACT_SKIPPED)
		return NULL;
3443 3444 3445 3446 3447
	/*
	 * At least in one zone compaction wasn't deferred or skipped, so let's
	 * count a compaction stall
	 */
	count_vm_event(COMPACTSTALL);
3448

3449 3450 3451 3452 3453 3454 3455
	/* Prep a captured page if available */
	if (page)
		prep_new_page(page, order, gfp_mask, alloc_flags);

	/* Try get a page from the freelist if available */
	if (!page)
		page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
3456

3457 3458
	if (page) {
		struct zone *zone = page_zone(page);
3459

3460 3461 3462 3463 3464
		zone->compact_blockskip_flush = false;
		compaction_defer_reset(zone, order, true);
		count_vm_event(COMPACTSUCCESS);
		return page;
	}
3465

3466 3467 3468 3469 3470
	/*
	 * It's bad if compaction run occurs and fails. The most likely reason
	 * is that pages exist, but not enough to satisfy watermarks.
	 */
	count_vm_event(COMPACTFAIL);
3471

3472
	cond_resched();
3473 3474 3475

	return NULL;
}
3476

3477 3478 3479 3480
static inline bool
should_compact_retry(struct alloc_context *ac, int order, int alloc_flags,
		     enum compact_result compact_result,
		     enum compact_priority *compact_priority,
3481
		     int *compaction_retries)
3482 3483
{
	int max_retries = MAX_COMPACT_RETRIES;
3484
	int min_priority;
3485 3486 3487
	bool ret = false;
	int retries = *compaction_retries;
	enum compact_priority priority = *compact_priority;
3488 3489 3490 3491

	if (!order)
		return false;

3492 3493 3494
	if (fatal_signal_pending(current))
		return false;

3495
	/*
3496 3497
	 * Compaction was skipped due to a lack of free order-0
	 * migration targets. Continue if reclaim can help.
3498
	 */
3499
	if (compact_result == COMPACT_SKIPPED) {
3500 3501 3502 3503
		ret = compaction_zonelist_suitable(ac, order, alloc_flags);
		goto out;
	}

3504
	/*
3505 3506
	 * Compaction managed to coalesce some page blocks, but the
	 * allocation failed presumably due to a race. Retry some.
3507
	 */
3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519
	if (compact_result == COMPACT_SUCCESS) {
		/*
		 * !costly requests are much more important than
		 * __GFP_RETRY_MAYFAIL costly ones because they are de
		 * facto nofail and invoke OOM killer to move on while
		 * costly can fail and users are ready to cope with
		 * that. 1/4 retries is rather arbitrary but we would
		 * need much more detailed feedback from compaction to
		 * make a better decision.
		 */
		if (order > PAGE_ALLOC_COSTLY_ORDER)
			max_retries /= 4;
3520

3521 3522 3523 3524
		if (++(*compaction_retries) <= max_retries) {
			ret = true;
			goto out;
		}
3525
	}
3526

3527
	/*
3528
	 * Compaction failed. Retry with increasing priority.
3529
	 */
3530 3531
	min_priority = (order > PAGE_ALLOC_COSTLY_ORDER) ?
			MIN_COMPACT_COSTLY_PRIORITY : MIN_COMPACT_PRIORITY;
3532

3533
	if (*compact_priority > min_priority) {
3534 3535
		(*compact_priority)--;
		*compaction_retries = 0;
3536
		ret = true;
3537
	}
3538 3539 3540
out:
	trace_compact_retry(order, priority, compact_result, retries, max_retries, ret);
	return ret;
3541
}
3542 3543 3544
#else
static inline struct page *
__alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3545
		unsigned int alloc_flags, const struct alloc_context *ac,
3546
		enum compact_priority prio, enum compact_result *compact_result)
3547
{
3548
	*compact_result = COMPACT_SKIPPED;
3549 3550
	return NULL;
}
3551 3552

static inline bool
3553 3554
should_compact_retry(struct alloc_context *ac, unsigned int order, int alloc_flags,
		     enum compact_result compact_result,
3555
		     enum compact_priority *compact_priority,
3556
		     int *compaction_retries)
3557
{
3558 3559 3560 3561 3562 3563 3564 3565 3566 3567 3568 3569
	struct zone *zone;
	struct zoneref *z;

	if (!order || order > PAGE_ALLOC_COSTLY_ORDER)
		return false;

	/*
	 * There are setups with compaction disabled which would prefer to loop
	 * inside the allocator rather than hit the oom killer prematurely.
	 * Let's give them a good hope and keep retrying while the order-0
	 * watermarks are OK.
	 */
3570 3571
	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
				ac->highest_zoneidx, ac->nodemask) {
3572
		if (zone_watermark_ok(zone, 0, min_wmark_pages(zone),
3573
					ac->highest_zoneidx, alloc_flags))
3574 3575
			return true;
	}
3576 3577
	return false;
}
3578
#endif /* CONFIG_COMPACTION */
3579

3580
#ifdef CONFIG_LOCKDEP
3581
static struct lockdep_map __fs_reclaim_map =
3582 3583
	STATIC_LOCKDEP_MAP_INIT("fs_reclaim", &__fs_reclaim_map);

3584
static bool __need_reclaim(gfp_t gfp_mask)
3585 3586 3587 3588 3589 3590
{
	/* no reclaim without waiting on it */
	if (!(gfp_mask & __GFP_DIRECT_RECLAIM))
		return false;

	/* this guy won't enter reclaim */
3591
	if (current->flags & PF_MEMALLOC)
3592 3593 3594 3595 3596 3597 3598 3599
		return false;

	if (gfp_mask & __GFP_NOLOCKDEP)
		return false;

	return true;
}

3600
void __fs_reclaim_acquire(unsigned long ip)
3601
{
3602
	lock_acquire_exclusive(&__fs_reclaim_map, 0, 0, NULL, ip);
3603 3604
}

3605
void __fs_reclaim_release(unsigned long ip)
3606
{
3607
	lock_release(&__fs_reclaim_map, ip);
3608 3609
}

3610 3611
void fs_reclaim_acquire(gfp_t gfp_mask)
{
3612 3613 3614 3615
	gfp_mask = current_gfp_context(gfp_mask);

	if (__need_reclaim(gfp_mask)) {
		if (gfp_mask & __GFP_FS)
3616
			__fs_reclaim_acquire(_RET_IP_);
3617 3618 3619 3620 3621 3622 3623

#ifdef CONFIG_MMU_NOTIFIER
		lock_map_acquire(&__mmu_notifier_invalidate_range_start_map);
		lock_map_release(&__mmu_notifier_invalidate_range_start_map);
#endif

	}
3624 3625 3626 3627 3628
}
EXPORT_SYMBOL_GPL(fs_reclaim_acquire);

void fs_reclaim_release(gfp_t gfp_mask)
{
3629 3630 3631 3632
	gfp_mask = current_gfp_context(gfp_mask);

	if (__need_reclaim(gfp_mask)) {
		if (gfp_mask & __GFP_FS)
3633
			__fs_reclaim_release(_RET_IP_);
3634
	}
3635 3636 3637 3638
}
EXPORT_SYMBOL_GPL(fs_reclaim_release);
#endif

3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662
/*
 * Zonelists may change due to hotplug during allocation. Detect when zonelists
 * have been rebuilt so allocation retries. Reader side does not lock and
 * retries the allocation if zonelist changes. Writer side is protected by the
 * embedded spin_lock.
 */
static DEFINE_SEQLOCK(zonelist_update_seq);

static unsigned int zonelist_iter_begin(void)
{
	if (IS_ENABLED(CONFIG_MEMORY_HOTREMOVE))
		return read_seqbegin(&zonelist_update_seq);

	return 0;
}

static unsigned int check_retry_zonelist(unsigned int seq)
{
	if (IS_ENABLED(CONFIG_MEMORY_HOTREMOVE))
		return read_seqretry(&zonelist_update_seq, seq);

	return seq;
}

3663
/* Perform direct synchronous page reclaim */
3664
static unsigned long
3665 3666
__perform_reclaim(gfp_t gfp_mask, unsigned int order,
					const struct alloc_context *ac)
3667
{
3668
	unsigned int noreclaim_flag;
3669
	unsigned long progress;
3670 3671 3672 3673 3674

	cond_resched();

	/* We now go into synchronous reclaim */
	cpuset_memory_pressure_bump();
3675
	fs_reclaim_acquire(gfp_mask);
3676
	noreclaim_flag = memalloc_noreclaim_save();
3677

3678 3679
	progress = try_to_free_pages(ac->zonelist, order, gfp_mask,
								ac->nodemask);
3680

3681
	memalloc_noreclaim_restore(noreclaim_flag);
3682
	fs_reclaim_release(gfp_mask);
3683 3684 3685

	cond_resched();

3686 3687 3688 3689 3690 3691
	return progress;
}

/* The really slow allocator path where we enter direct reclaim */
static inline struct page *
__alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
3692
		unsigned int alloc_flags, const struct alloc_context *ac,
3693
		unsigned long *did_some_progress)
3694 3695
{
	struct page *page = NULL;
3696
	unsigned long pflags;
3697 3698
	bool drained = false;

3699
	psi_memstall_enter(&pflags);
3700
	*did_some_progress = __perform_reclaim(gfp_mask, order, ac);
3701
	if (unlikely(!(*did_some_progress)))
3702
		goto out;
3703

3704
retry:
3705
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
3706 3707 3708

	/*
	 * If an allocation failed after direct reclaim, it could be because
3709
	 * pages are pinned on the per-cpu lists or in high alloc reserves.
3710
	 * Shrink them and try again
3711 3712
	 */
	if (!page && !drained) {
3713
		unreserve_highatomic_pageblock(ac, false);
3714
		drain_all_pages(NULL);
3715 3716 3717
		drained = true;
		goto retry;
	}
3718 3719
out:
	psi_memstall_leave(&pflags);
3720

3721 3722 3723
	return page;
}

3724 3725
static void wake_all_kswapds(unsigned int order, gfp_t gfp_mask,
			     const struct alloc_context *ac)
3726 3727 3728
{
	struct zoneref *z;
	struct zone *zone;
3729
	pg_data_t *last_pgdat = NULL;
3730
	enum zone_type highest_zoneidx = ac->highest_zoneidx;
3731

3732
	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist, highest_zoneidx,
3733
					ac->nodemask) {
3734 3735
		if (!managed_zone(zone))
			continue;
3736
		if (last_pgdat != zone->zone_pgdat) {
3737
			wakeup_kswapd(zone, gfp_mask, order, highest_zoneidx);
3738 3739
			last_pgdat = zone->zone_pgdat;
		}
3740
	}
3741 3742
}

3743
static inline unsigned int
3744
gfp_to_alloc_flags(gfp_t gfp_mask, unsigned int order)
3745
{
3746
	unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
Linus Torvalds's avatar
Linus Torvalds committed
3747

3748
	/*
3749
	 * __GFP_HIGH is assumed to be the same as ALLOC_MIN_RESERVE
3750 3751 3752
	 * and __GFP_KSWAPD_RECLAIM is assumed to be the same as ALLOC_KSWAPD
	 * to save two branches.
	 */
3753
	BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_MIN_RESERVE);
3754
	BUILD_BUG_ON(__GFP_KSWAPD_RECLAIM != (__force gfp_t) ALLOC_KSWAPD);
3755

3756 3757 3758 3759
	/*
	 * The caller may dip into page reserves a bit more if the caller
	 * cannot run direct reclaim, or if the caller has realtime scheduling
	 * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
3760
	 * set both ALLOC_NON_BLOCK and ALLOC_MIN_RESERVE(__GFP_HIGH).
3761
	 */
3762 3763
	alloc_flags |= (__force int)
		(gfp_mask & (__GFP_HIGH | __GFP_KSWAPD_RECLAIM));
Linus Torvalds's avatar
Linus Torvalds committed
3764

3765
	if (!(gfp_mask & __GFP_DIRECT_RECLAIM)) {
3766
		/*
3767 3768
		 * Not worth trying to allocate harder for __GFP_NOMEMALLOC even
		 * if it can't schedule.
3769
		 */
3770
		if (!(gfp_mask & __GFP_NOMEMALLOC)) {
3771
			alloc_flags |= ALLOC_NON_BLOCK;
3772 3773 3774 3775 3776

			if (order > 0)
				alloc_flags |= ALLOC_HIGHATOMIC;
		}

3777
		/*
3778 3779
		 * Ignore cpuset mems for non-blocking __GFP_HIGH (probably
		 * GFP_ATOMIC) rather than fail, see the comment for
3780
		 * cpuset_node_allowed().
3781
		 */
3782 3783
		if (alloc_flags & ALLOC_MIN_RESERVE)
			alloc_flags &= ~ALLOC_CPUSET;
3784
	} else if (unlikely(rt_task(current)) && in_task())
3785
		alloc_flags |= ALLOC_MIN_RESERVE;
3786

3787
	alloc_flags = gfp_to_alloc_flags_cma(gfp_mask, alloc_flags);
3788

3789 3790 3791
	return alloc_flags;
}

3792
static bool oom_reserves_allowed(struct task_struct *tsk)
3793
{
3794 3795 3796 3797 3798 3799 3800 3801
	if (!tsk_is_oom_victim(tsk))
		return false;

	/*
	 * !MMU doesn't have oom reaper so give access to memory reserves
	 * only to the thread with TIF_MEMDIE set
	 */
	if (!IS_ENABLED(CONFIG_MMU) && !test_thread_flag(TIF_MEMDIE))
3802 3803
		return false;

3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814
	return true;
}

/*
 * Distinguish requests which really need access to full memory
 * reserves from oom victims which can live with a portion of it
 */
static inline int __gfp_pfmemalloc_flags(gfp_t gfp_mask)
{
	if (unlikely(gfp_mask & __GFP_NOMEMALLOC))
		return 0;
3815
	if (gfp_mask & __GFP_MEMALLOC)
3816
		return ALLOC_NO_WATERMARKS;
3817
	if (in_serving_softirq() && (current->flags & PF_MEMALLOC))
3818 3819 3820 3821 3822 3823 3824
		return ALLOC_NO_WATERMARKS;
	if (!in_interrupt()) {
		if (current->flags & PF_MEMALLOC)
			return ALLOC_NO_WATERMARKS;
		else if (oom_reserves_allowed(current))
			return ALLOC_OOM;
	}
3825

3826 3827 3828 3829 3830 3831
	return 0;
}

bool gfp_pfmemalloc_allowed(gfp_t gfp_mask)
{
	return !!__gfp_pfmemalloc_flags(gfp_mask);
3832 3833
}

3834 3835 3836
/*
 * Checks whether it makes sense to retry the reclaim to make a forward progress
 * for the given allocation request.
3837 3838 3839 3840
 *
 * We give up when we either have tried MAX_RECLAIM_RETRIES in a row
 * without success, or when we couldn't even meet the watermark if we
 * reclaimed all remaining pages on the LRU lists.
3841 3842 3843 3844 3845 3846
 *
 * Returns true if a retry is viable or false to enter the oom path.
 */
static inline bool
should_reclaim_retry(gfp_t gfp_mask, unsigned order,
		     struct alloc_context *ac, int alloc_flags,
3847
		     bool did_some_progress, int *no_progress_loops)
3848 3849 3850
{
	struct zone *zone;
	struct zoneref *z;
3851
	bool ret = false;
3852

3853 3854 3855 3856 3857 3858 3859 3860 3861 3862
	/*
	 * Costly allocations might have made a progress but this doesn't mean
	 * their order will become available due to high fragmentation so
	 * always increment the no progress counter for them
	 */
	if (did_some_progress && order <= PAGE_ALLOC_COSTLY_ORDER)
		*no_progress_loops = 0;
	else
		(*no_progress_loops)++;

3863 3864 3865 3866
	/*
	 * Make sure we converge to OOM if we cannot make any progress
	 * several times in the row.
	 */
3867 3868
	if (*no_progress_loops > MAX_RECLAIM_RETRIES) {
		/* Before OOM, exhaust highatomic_reserve */
3869
		return unreserve_highatomic_pageblock(ac, true);
3870
	}
3871

3872 3873 3874 3875 3876
	/*
	 * Keep reclaiming pages while there is a chance this will lead
	 * somewhere.  If none of the target zones can satisfy our allocation
	 * request even if all reclaimable pages are considered then we are
	 * screwed and have to go OOM.
3877
	 */
3878 3879
	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
				ac->highest_zoneidx, ac->nodemask) {
3880
		unsigned long available;
3881
		unsigned long reclaimable;
3882 3883
		unsigned long min_wmark = min_wmark_pages(zone);
		bool wmark;
3884

3885 3886
		available = reclaimable = zone_reclaimable_pages(zone);
		available += zone_page_state_snapshot(zone, NR_FREE_PAGES);
3887 3888

		/*
3889 3890
		 * Would the allocation succeed if we reclaimed all
		 * reclaimable pages?
3891
		 */
3892
		wmark = __zone_watermark_ok(zone, order, min_wmark,
3893
				ac->highest_zoneidx, alloc_flags, available);
3894 3895 3896
		trace_reclaim_retry_zone(z, order, reclaimable,
				available, min_wmark, *no_progress_loops, wmark);
		if (wmark) {
3897
			ret = true;
3898
			break;
3899 3900 3901
		}
	}

3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913
	/*
	 * Memory allocation/reclaim might be called from a WQ context and the
	 * current implementation of the WQ concurrency control doesn't
	 * recognize that a particular WQ is congested if the worker thread is
	 * looping without ever sleeping. Therefore we have to do a short sleep
	 * here rather than calling cond_resched().
	 */
	if (current->flags & PF_WQ_WORKER)
		schedule_timeout_uninterruptible(1);
	else
		cond_resched();
	return ret;
3914 3915
}

3916 3917 3918 3919 3920 3921 3922 3923 3924 3925 3926 3927 3928 3929 3930 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948
static inline bool
check_retry_cpuset(int cpuset_mems_cookie, struct alloc_context *ac)
{
	/*
	 * It's possible that cpuset's mems_allowed and the nodemask from
	 * mempolicy don't intersect. This should be normally dealt with by
	 * policy_nodemask(), but it's possible to race with cpuset update in
	 * such a way the check therein was true, and then it became false
	 * before we got our cpuset_mems_cookie here.
	 * This assumes that for all allocations, ac->nodemask can come only
	 * from MPOL_BIND mempolicy (whose documented semantics is to be ignored
	 * when it does not intersect with the cpuset restrictions) or the
	 * caller can deal with a violated nodemask.
	 */
	if (cpusets_enabled() && ac->nodemask &&
			!cpuset_nodemask_valid_mems_allowed(ac->nodemask)) {
		ac->nodemask = NULL;
		return true;
	}

	/*
	 * When updating a task's mems_allowed or mempolicy nodemask, it is
	 * possible to race with parallel threads in such a way that our
	 * allocation can fail while the mask is being updated. If we are about
	 * to fail, check if the cpuset changed during allocation and if so,
	 * retry.
	 */
	if (read_mems_allowed_retry(cpuset_mems_cookie))
		return true;

	return false;
}

3949 3950
static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
3951
						struct alloc_context *ac)
3952
{
3953
	bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
3954
	const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
3955
	struct page *page = NULL;
3956
	unsigned int alloc_flags;
3957
	unsigned long did_some_progress;
3958
	enum compact_priority compact_priority;
3959
	enum compact_result compact_result;
3960 3961 3962
	int compaction_retries;
	int no_progress_loops;
	unsigned int cpuset_mems_cookie;
3963
	unsigned int zonelist_iter_cookie;
3964
	int reserve_flags;
Linus Torvalds's avatar
Linus Torvalds committed
3965

3966
restart:
3967 3968 3969 3970
	compaction_retries = 0;
	no_progress_loops = 0;
	compact_priority = DEF_COMPACT_PRIORITY;
	cpuset_mems_cookie = read_mems_allowed_begin();
3971
	zonelist_iter_cookie = zonelist_iter_begin();
3972 3973 3974 3975 3976 3977

	/*
	 * The fast path uses conservative alloc_flags to succeed only until
	 * kswapd needs to be woken up, and to avoid the cost of setting up
	 * alloc_flags precisely. So we do that now.
	 */
3978
	alloc_flags = gfp_to_alloc_flags(gfp_mask, order);
3979

3980 3981 3982 3983 3984 3985 3986
	/*
	 * We need to recalculate the starting point for the zonelist iterator
	 * because we might have used different nodemask in the fast path, or
	 * there was a cpuset modification and we are retrying - otherwise we
	 * could end up iterating over non-eligible zones endlessly.
	 */
	ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
3987
					ac->highest_zoneidx, ac->nodemask);
3988 3989 3990
	if (!ac->preferred_zoneref->zone)
		goto nopage;

3991 3992 3993 3994 3995 3996 3997 3998 3999 4000 4001 4002 4003
	/*
	 * Check for insane configurations where the cpuset doesn't contain
	 * any suitable zone to satisfy the request - e.g. non-movable
	 * GFP_HIGHUSER allocations from MOVABLE nodes only.
	 */
	if (cpusets_insane_config() && (gfp_mask & __GFP_HARDWALL)) {
		struct zoneref *z = first_zones_zonelist(ac->zonelist,
					ac->highest_zoneidx,
					&cpuset_current_mems_allowed);
		if (!z->zone)
			goto nopage;
	}

4004
	if (alloc_flags & ALLOC_KSWAPD)
4005
		wake_all_kswapds(order, gfp_mask, ac);
4006 4007 4008 4009 4010 4011 4012 4013 4014

	/*
	 * The adjusted alloc_flags might result in immediate success, so try
	 * that first
	 */
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;

4015 4016
	/*
	 * For costly allocations, try direct compaction first, as it's likely
4017 4018 4019 4020 4021 4022
	 * that we have enough base pages and don't need to reclaim. For non-
	 * movable high-order allocations, do that as well, as compaction will
	 * try prevent permanent fragmentation by migrating from blocks of the
	 * same migratetype.
	 * Don't try this for allocations that are allowed to ignore
	 * watermarks, as the ALLOC_NO_WATERMARKS attempt didn't yet happen.
4023
	 */
4024 4025 4026 4027
	if (can_direct_reclaim &&
			(costly_order ||
			   (order > 0 && ac->migratetype != MIGRATE_MOVABLE))
			&& !gfp_pfmemalloc_allowed(gfp_mask)) {
4028 4029
		page = __alloc_pages_direct_compact(gfp_mask, order,
						alloc_flags, ac,
4030
						INIT_COMPACT_PRIORITY,
4031 4032 4033 4034
						&compact_result);
		if (page)
			goto got_pg;

4035 4036 4037 4038 4039
		/*
		 * Checks for costly allocations with __GFP_NORETRY, which
		 * includes some THP page fault allocations
		 */
		if (costly_order && (gfp_mask & __GFP_NORETRY)) {
4040 4041 4042 4043
			/*
			 * If allocating entire pageblock(s) and compaction
			 * failed because all zones are below low watermarks
			 * or is prohibited because it recently failed at this
4044 4045
			 * order, fail immediately unless the allocator has
			 * requested compaction and reclaim retry.
4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059
			 *
			 * Reclaim is
			 *  - potentially very expensive because zones are far
			 *    below their low watermarks or this is part of very
			 *    bursty high order allocations,
			 *  - not guaranteed to help because isolate_freepages()
			 *    may not iterate over freed pages as part of its
			 *    linear scan, and
			 *  - unlikely to make entire pageblocks free on its
			 *    own.
			 */
			if (compact_result == COMPACT_SKIPPED ||
			    compact_result == COMPACT_DEFERRED)
				goto nopage;
4060 4061

			/*
4062 4063
			 * Looks like reclaim/compaction is worth trying, but
			 * sync compaction could be very expensive, so keep
4064
			 * using async compaction.
4065
			 */
4066
			compact_priority = INIT_COMPACT_PRIORITY;
4067 4068
		}
	}
4069

4070
retry:
4071
	/* Ensure kswapd doesn't accidentally go to sleep as long as we loop */
4072
	if (alloc_flags & ALLOC_KSWAPD)
4073
		wake_all_kswapds(order, gfp_mask, ac);
4074

4075 4076
	reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
	if (reserve_flags)
4077 4078
		alloc_flags = gfp_to_alloc_flags_cma(gfp_mask, reserve_flags) |
					  (alloc_flags & ALLOC_KSWAPD);
4079

4080
	/*
4081 4082 4083
	 * Reset the nodemask and zonelist iterators if memory policies can be
	 * ignored. These allocations are high priority and system rather than
	 * user oriented.
4084
	 */
4085
	if (!(alloc_flags & ALLOC_CPUSET) || reserve_flags) {
4086
		ac->nodemask = NULL;
4087
		ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
4088
					ac->highest_zoneidx, ac->nodemask);
4089 4090
	}

4091
	/* Attempt with potentially adjusted zonelist and alloc_flags */
4092
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
4093 4094
	if (page)
		goto got_pg;
Linus Torvalds's avatar
Linus Torvalds committed
4095

4096
	/* Caller is not willing to reclaim, we can't balance anything */
4097
	if (!can_direct_reclaim)
Linus Torvalds's avatar
Linus Torvalds committed
4098 4099
		goto nopage;

4100 4101
	/* Avoid recursion of direct reclaim */
	if (current->flags & PF_MEMALLOC)
4102 4103
		goto nopage;

4104 4105 4106 4107 4108 4109 4110
	/* Try direct reclaim and then allocating */
	page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,
							&did_some_progress);
	if (page)
		goto got_pg;

	/* Try direct compaction and then allocating */
4111
	page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
4112
					compact_priority, &compact_result);
4113 4114
	if (page)
		goto got_pg;
4115

4116 4117
	/* Do not loop if specifically requested */
	if (gfp_mask & __GFP_NORETRY)
4118
		goto nopage;
4119

4120 4121
	/*
	 * Do not retry costly high order allocations unless they are
4122
	 * __GFP_RETRY_MAYFAIL
4123
	 */
4124
	if (costly_order && !(gfp_mask & __GFP_RETRY_MAYFAIL))
4125
		goto nopage;
4126 4127

	if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
4128
				 did_some_progress > 0, &no_progress_loops))
4129 4130
		goto retry;

4131 4132 4133 4134 4135 4136 4137
	/*
	 * It doesn't make any sense to retry for the compaction if the order-0
	 * reclaim is not able to make any progress because the current
	 * implementation of the compaction depends on the sufficient amount
	 * of free memory (see __compaction_suitable)
	 */
	if (did_some_progress > 0 &&
4138
			should_compact_retry(ac, order, alloc_flags,
4139
				compact_result, &compact_priority,
4140
				&compaction_retries))
4141 4142
		goto retry;

4143

4144 4145 4146 4147 4148 4149 4150
	/*
	 * Deal with possible cpuset update races or zonelist updates to avoid
	 * a unnecessary OOM kill.
	 */
	if (check_retry_cpuset(cpuset_mems_cookie, ac) ||
	    check_retry_zonelist(zonelist_iter_cookie))
		goto restart;
4151

4152 4153 4154 4155 4156
	/* Reclaim has failed us, start killing things */
	page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
	if (page)
		goto got_pg;

4157
	/* Avoid allocations with no watermarks from looping endlessly */
4158
	if (tsk_is_oom_victim(current) &&
4159
	    (alloc_flags & ALLOC_OOM ||
4160
	     (gfp_mask & __GFP_NOMEMALLOC)))
4161 4162
		goto nopage;

4163
	/* Retry as long as the OOM killer is making progress */
4164 4165
	if (did_some_progress) {
		no_progress_loops = 0;
4166
		goto retry;
4167
	}
4168

Linus Torvalds's avatar
Linus Torvalds committed
4169
nopage:
4170 4171 4172 4173 4174 4175 4176
	/*
	 * Deal with possible cpuset update races or zonelist updates to avoid
	 * a unnecessary OOM kill.
	 */
	if (check_retry_cpuset(cpuset_mems_cookie, ac) ||
	    check_retry_zonelist(zonelist_iter_cookie))
		goto restart;
4177

4178 4179 4180 4181 4182 4183 4184 4185 4186
	/*
	 * Make sure that __GFP_NOFAIL request doesn't leak out and make sure
	 * we always retry
	 */
	if (gfp_mask & __GFP_NOFAIL) {
		/*
		 * All existing users of the __GFP_NOFAIL are blockable, so warn
		 * of any new users that actually require GFP_NOWAIT
		 */
4187
		if (WARN_ON_ONCE_GFP(!can_direct_reclaim, gfp_mask))
4188 4189 4190 4191 4192 4193 4194
			goto fail;

		/*
		 * PF_MEMALLOC request from this context is rather bizarre
		 * because we cannot reclaim anything and only can loop waiting
		 * for somebody to do a work for us
		 */
4195
		WARN_ON_ONCE_GFP(current->flags & PF_MEMALLOC, gfp_mask);
4196 4197 4198 4199 4200 4201 4202

		/*
		 * non failing costly orders are a hard requirement which we
		 * are not prepared for much so let's warn about these users
		 * so that we can identify them and convert them to something
		 * else.
		 */
4203
		WARN_ON_ONCE_GFP(costly_order, gfp_mask);
4204

4205
		/*
4206 4207 4208
		 * Help non-failing allocations by giving some access to memory
		 * reserves normally used for high priority non-blocking
		 * allocations but do not use ALLOC_NO_WATERMARKS because this
4209
		 * could deplete whole memory reserves which would just make
4210
		 * the situation worse.
4211
		 */
4212
		page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_MIN_RESERVE, ac);
4213 4214 4215
		if (page)
			goto got_pg;

4216 4217 4218 4219
		cond_resched();
		goto retry;
	}
fail:
4220
	warn_alloc(gfp_mask, ac->nodemask,
4221
			"page allocation failure: order:%u", order);
Linus Torvalds's avatar
Linus Torvalds committed
4222
got_pg:
4223
	return page;
Linus Torvalds's avatar
Linus Torvalds committed
4224
}
4225

4226
static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
4227
		int preferred_nid, nodemask_t *nodemask,
4228
		struct alloc_context *ac, gfp_t *alloc_gfp,
4229
		unsigned int *alloc_flags)
4230
{
4231
	ac->highest_zoneidx = gfp_zone(gfp_mask);
4232
	ac->zonelist = node_zonelist(preferred_nid, gfp_mask);
4233
	ac->nodemask = nodemask;
4234
	ac->migratetype = gfp_migratetype(gfp_mask);
4235

4236
	if (cpusets_enabled()) {
4237
		*alloc_gfp |= __GFP_HARDWALL;
4238 4239 4240 4241
		/*
		 * When we are in the interrupt context, it is irrelevant
		 * to the current task context. It means that any node ok.
		 */
4242
		if (in_task() && !ac->nodemask)
4243
			ac->nodemask = &cpuset_current_mems_allowed;
4244 4245
		else
			*alloc_flags |= ALLOC_CPUSET;
4246 4247
	}

4248
	might_alloc(gfp_mask);
4249 4250

	if (should_fail_alloc_page(gfp_mask, order))
4251
		return false;
4252

4253
	*alloc_flags = gfp_to_alloc_flags_cma(gfp_mask, *alloc_flags);
4254

4255
	/* Dirty zone balancing only done in the fast path */
4256
	ac->spread_dirty_pages = (gfp_mask & __GFP_WRITE);
4257

4258 4259 4260 4261 4262
	/*
	 * The preferred zone is used for statistics but crucially it is
	 * also used as the starting point for the zonelist iterator. It
	 * may get reset for allocations that ignore memory policies.
	 */
4263
	ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
4264
					ac->highest_zoneidx, ac->nodemask);
4265 4266

	return true;
4267 4268
}

4269
/*
4270
 * __alloc_pages_bulk - Allocate a number of order-0 pages to a list or array
4271 4272 4273
 * @gfp: GFP flags for the allocation
 * @preferred_nid: The preferred NUMA node ID to allocate from
 * @nodemask: Set of nodes to allocate from, may be NULL
4274 4275 4276
 * @nr_pages: The number of pages desired on the list or array
 * @page_list: Optional list to store the allocated pages
 * @page_array: Optional array to store the pages
4277 4278
 *
 * This is a batched version of the page allocator that attempts to
4279 4280
 * allocate nr_pages quickly. Pages are added to page_list if page_list
 * is not NULL, otherwise it is assumed that the page_array is valid.
4281
 *
4282 4283 4284 4285 4286 4287
 * For lists, nr_pages is the number of pages that should be allocated.
 *
 * For arrays, only NULL elements are populated with pages and nr_pages
 * is the maximum number of pages that will be stored in the array.
 *
 * Returns the number of pages on the list or array.
4288 4289 4290
 */
unsigned long __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
			nodemask_t *nodemask, int nr_pages,
4291 4292
			struct list_head *page_list,
			struct page **page_array)
4293 4294
{
	struct page *page;
4295
	unsigned long __maybe_unused UP_flags;
4296 4297 4298 4299 4300 4301 4302
	struct zone *zone;
	struct zoneref *z;
	struct per_cpu_pages *pcp;
	struct list_head *pcp_list;
	struct alloc_context ac;
	gfp_t alloc_gfp;
	unsigned int alloc_flags = ALLOC_WMARK_LOW;
4303
	int nr_populated = 0, nr_account = 0;
4304

4305 4306 4307 4308
	/*
	 * Skip populated array elements to determine if any pages need
	 * to be allocated before disabling IRQs.
	 */
4309
	while (page_array && nr_populated < nr_pages && page_array[nr_populated])
4310 4311
		nr_populated++;

4312 4313 4314 4315
	/* No pages requested? */
	if (unlikely(nr_pages <= 0))
		goto out;

4316 4317
	/* Already populated array? */
	if (unlikely(page_array && nr_pages - nr_populated == 0))
4318
		goto out;
4319

4320
	/* Bulk allocator does not support memcg accounting. */
4321
	if (memcg_kmem_online() && (gfp & __GFP_ACCOUNT))
4322 4323
		goto failed;

4324
	/* Use the single page allocator for one page. */
4325
	if (nr_pages - nr_populated == 1)
4326 4327
		goto failed;

4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339
#ifdef CONFIG_PAGE_OWNER
	/*
	 * PAGE_OWNER may recurse into the allocator to allocate space to
	 * save the stack with pagesets.lock held. Releasing/reacquiring
	 * removes much of the performance benefit of bulk allocation so
	 * force the caller to allocate one page at a time as it'll have
	 * similar performance to added complexity to the bulk allocator.
	 */
	if (static_branch_unlikely(&page_owner_inited))
		goto failed;
#endif

4340 4341 4342 4343
	/* May set ALLOC_NOFRAGMENT, fragmentation will return 1 page. */
	gfp &= gfp_allowed_mask;
	alloc_gfp = gfp;
	if (!prepare_alloc_pages(gfp, 0, preferred_nid, nodemask, &ac, &alloc_gfp, &alloc_flags))
4344
		goto out;
4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372
	gfp = alloc_gfp;

	/* Find an allowed local zone that meets the low watermark. */
	for_each_zone_zonelist_nodemask(zone, z, ac.zonelist, ac.highest_zoneidx, ac.nodemask) {
		unsigned long mark;

		if (cpusets_enabled() && (alloc_flags & ALLOC_CPUSET) &&
		    !__cpuset_zone_allowed(zone, gfp)) {
			continue;
		}

		if (nr_online_nodes > 1 && zone != ac.preferred_zoneref->zone &&
		    zone_to_nid(zone) != zone_to_nid(ac.preferred_zoneref->zone)) {
			goto failed;
		}

		mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK) + nr_pages;
		if (zone_watermark_fast(zone, 0,  mark,
				zonelist_zone_idx(ac.preferred_zoneref),
				alloc_flags, gfp)) {
			break;
		}
	}

	/*
	 * If there are no allowed local zones that meets the watermarks then
	 * try to allocate a single page and reclaim if necessary.
	 */
4373
	if (unlikely(!zone))
4374 4375
		goto failed;

4376
	/* spin_trylock may fail due to a parallel drain or IRQ reentrancy. */
4377
	pcp_trylock_prepare(UP_flags);
4378
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
4379
	if (!pcp)
4380
		goto failed_irq;
4381 4382

	/* Attempt the batch allocation */
4383
	pcp_list = &pcp->lists[order_to_pindex(ac.migratetype, 0)];
4384 4385 4386 4387 4388 4389 4390 4391
	while (nr_populated < nr_pages) {

		/* Skip existing pages */
		if (page_array && page_array[nr_populated]) {
			nr_populated++;
			continue;
		}

4392
		page = __rmqueue_pcplist(zone, 0, ac.migratetype, alloc_flags,
4393
								pcp, pcp_list);
4394
		if (unlikely(!page)) {
4395
			/* Try and allocate at least one page */
4396
			if (!nr_account) {
4397
				pcp_spin_unlock(pcp);
4398
				goto failed_irq;
4399
			}
4400 4401
			break;
		}
4402
		nr_account++;
4403 4404

		prep_new_page(page, 0, gfp, 0);
4405 4406 4407 4408 4409
		if (page_list)
			list_add(&page->lru, page_list);
		else
			page_array[nr_populated] = page;
		nr_populated++;
4410 4411
	}

4412
	pcp_spin_unlock(pcp);
4413
	pcp_trylock_finish(UP_flags);
4414

4415 4416
	__count_zid_vm_events(PGALLOC, zone_idx(zone), nr_account);
	zone_statistics(ac.preferred_zoneref->zone, zone, nr_account);
4417

4418
out:
4419
	return nr_populated;
4420 4421

failed_irq:
4422
	pcp_trylock_finish(UP_flags);
4423 4424 4425 4426

failed:
	page = __alloc_pages(gfp, 0, preferred_nid, nodemask);
	if (page) {
4427 4428 4429 4430 4431
		if (page_list)
			list_add(&page->lru, page_list);
		else
			page_array[nr_populated] = page;
		nr_populated++;
4432 4433
	}

4434
	goto out;
4435 4436 4437
}
EXPORT_SYMBOL_GPL(__alloc_pages_bulk);

4438 4439 4440
/*
 * This is the 'heart' of the zoned buddy allocator.
 */
4441
struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid,
4442
							nodemask_t *nodemask)
4443 4444 4445
{
	struct page *page;
	unsigned int alloc_flags = ALLOC_WMARK_LOW;
4446
	gfp_t alloc_gfp; /* The gfp_t that was actually used for allocation */
4447 4448
	struct alloc_context ac = { };

4449 4450 4451 4452
	/*
	 * There are several places where we assume that the order value is sane
	 * so bail out early if the request is out of bound.
	 */
4453
	if (WARN_ON_ONCE_GFP(order > MAX_ORDER, gfp))
4454 4455
		return NULL;

4456
	gfp &= gfp_allowed_mask;
4457 4458 4459 4460
	/*
	 * Apply scoped allocation constraints. This is mainly about GFP_NOFS
	 * resp. GFP_NOIO which has to be inherited for all allocation requests
	 * from a particular context which has been marked by
4461 4462
	 * memalloc_no{fs,io}_{save,restore}. And PF_MEMALLOC_PIN which ensures
	 * movable zones are not used during allocation.
4463 4464
	 */
	gfp = current_gfp_context(gfp);
4465 4466
	alloc_gfp = gfp;
	if (!prepare_alloc_pages(gfp, order, preferred_nid, nodemask, &ac,
4467
			&alloc_gfp, &alloc_flags))
4468 4469
		return NULL;

4470 4471 4472 4473
	/*
	 * Forbid the first pass from falling back to types that fragment
	 * memory until all local zones are considered.
	 */
4474
	alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp);
4475

4476
	/* First allocation attempt */
4477
	page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac);
4478 4479
	if (likely(page))
		goto out;
4480

4481
	alloc_gfp = gfp;
4482
	ac.spread_dirty_pages = false;
4483

4484 4485 4486 4487
	/*
	 * Restore the original nodemask if it was potentially replaced with
	 * &cpuset_current_mems_allowed to optimize the fast-path attempt.
	 */
4488
	ac.nodemask = nodemask;
4489

4490
	page = __alloc_pages_slowpath(alloc_gfp, order, &ac);
4491

4492
out:
4493
	if (memcg_kmem_online() && (gfp & __GFP_ACCOUNT) && page &&
4494
	    unlikely(__memcg_kmem_charge_page(page, gfp, order) != 0)) {
4495 4496
		__free_pages(page, order);
		page = NULL;
4497 4498
	}

4499
	trace_mm_page_alloc(page, order, alloc_gfp, ac.migratetype);
4500
	kmsan_alloc_page(page, order, alloc_gfp);
4501

4502
	return page;
Linus Torvalds's avatar
Linus Torvalds committed
4503
}
4504
EXPORT_SYMBOL(__alloc_pages);
Linus Torvalds's avatar
Linus Torvalds committed
4505

4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517
struct folio *__folio_alloc(gfp_t gfp, unsigned int order, int preferred_nid,
		nodemask_t *nodemask)
{
	struct page *page = __alloc_pages(gfp | __GFP_COMP, order,
			preferred_nid, nodemask);

	if (page && order > 1)
		prep_transhuge_page(page);
	return (struct folio *)page;
}
EXPORT_SYMBOL(__folio_alloc);

Linus Torvalds's avatar
Linus Torvalds committed
4518
/*
4519 4520 4521
 * Common helper functions. Never use with __GFP_HIGHMEM because the returned
 * address cannot represent highmem pages. Use alloc_pages and then kmap if
 * you need to access high mem.
Linus Torvalds's avatar
Linus Torvalds committed
4522
 */
4523
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
Linus Torvalds's avatar
Linus Torvalds committed
4524
{
4525 4526
	struct page *page;

4527
	page = alloc_pages(gfp_mask & ~__GFP_HIGHMEM, order);
Linus Torvalds's avatar
Linus Torvalds committed
4528 4529 4530 4531 4532 4533
	if (!page)
		return 0;
	return (unsigned long) page_address(page);
}
EXPORT_SYMBOL(__get_free_pages);

4534
unsigned long get_zeroed_page(gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
4535
{
4536
	return __get_free_page(gfp_mask | __GFP_ZERO);
Linus Torvalds's avatar
Linus Torvalds committed
4537 4538 4539
}
EXPORT_SYMBOL(get_zeroed_page);

4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559
/**
 * __free_pages - Free pages allocated with alloc_pages().
 * @page: The page pointer returned from alloc_pages().
 * @order: The order of the allocation.
 *
 * This function can free multi-page allocations that are not compound
 * pages.  It does not check that the @order passed in matches that of
 * the allocation, so it is easy to leak memory.  Freeing more memory
 * than was allocated will probably emit a warning.
 *
 * If the last reference to this page is speculative, it will be released
 * by put_page() which only frees the first page of a non-compound
 * allocation.  To prevent the remaining pages from being leaked, we free
 * the subsequent pages here.  If you want to use the page's reference
 * count to decide when to free the allocation, you should allocate a
 * compound page, and use put_page() instead of __free_pages().
 *
 * Context: May be called in interrupt context or while holding a normal
 * spinlock, but not in NMI context or while holding a raw spinlock.
 */
4560 4561
void __free_pages(struct page *page, unsigned int order)
{
4562 4563 4564
	/* get PageHead before we drop reference */
	int head = PageHead(page);

4565 4566
	if (put_page_testzero(page))
		free_the_page(page, order);
4567
	else if (!head)
4568 4569
		while (order-- > 0)
			free_the_page(page + (1 << order), order);
4570
}
Linus Torvalds's avatar
Linus Torvalds committed
4571 4572
EXPORT_SYMBOL(__free_pages);

4573
void free_pages(unsigned long addr, unsigned int order)
Linus Torvalds's avatar
Linus Torvalds committed
4574 4575
{
	if (addr != 0) {
Nick Piggin's avatar
Nick Piggin committed
4576
		VM_BUG_ON(!virt_addr_valid((void *)addr));
Linus Torvalds's avatar
Linus Torvalds committed
4577 4578 4579 4580 4581 4582
		__free_pages(virt_to_page((void *)addr), order);
	}
}

EXPORT_SYMBOL(free_pages);

4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593
/*
 * Page Fragment:
 *  An arbitrary-length arbitrary-offset area of memory which resides
 *  within a 0 or higher order page.  Multiple fragments within that page
 *  are individually refcounted, in the page's reference counter.
 *
 * The page_frag functions below provide a simple allocation framework for
 * page fragments.  This is used by the network stack and network device
 * drivers to provide a backing region of memory for use as either an
 * sk_buff->head, or to be used in the "frags" portion of skb_shared_info.
 */
4594 4595
static struct page *__page_frag_cache_refill(struct page_frag_cache *nc,
					     gfp_t gfp_mask)
4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614
{
	struct page *page = NULL;
	gfp_t gfp = gfp_mask;

#if (PAGE_SIZE < PAGE_FRAG_CACHE_MAX_SIZE)
	gfp_mask |= __GFP_COMP | __GFP_NOWARN | __GFP_NORETRY |
		    __GFP_NOMEMALLOC;
	page = alloc_pages_node(NUMA_NO_NODE, gfp_mask,
				PAGE_FRAG_CACHE_MAX_ORDER);
	nc->size = page ? PAGE_FRAG_CACHE_MAX_SIZE : PAGE_SIZE;
#endif
	if (unlikely(!page))
		page = alloc_pages_node(NUMA_NO_NODE, gfp, 0);

	nc->va = page ? page_address(page) : NULL;

	return page;
}

4615
void __page_frag_cache_drain(struct page *page, unsigned int count)
4616 4617 4618
{
	VM_BUG_ON_PAGE(page_ref_count(page) == 0, page);

4619 4620
	if (page_ref_sub_and_test(page, count))
		free_the_page(page, compound_order(page));
4621
}
4622
EXPORT_SYMBOL(__page_frag_cache_drain);
4623

4624 4625 4626
void *page_frag_alloc_align(struct page_frag_cache *nc,
		      unsigned int fragsz, gfp_t gfp_mask,
		      unsigned int align_mask)
4627 4628 4629 4630 4631 4632 4633
{
	unsigned int size = PAGE_SIZE;
	struct page *page;
	int offset;

	if (unlikely(!nc->va)) {
refill:
4634
		page = __page_frag_cache_refill(nc, gfp_mask);
4635 4636 4637 4638 4639 4640 4641 4642 4643 4644
		if (!page)
			return NULL;

#if (PAGE_SIZE < PAGE_FRAG_CACHE_MAX_SIZE)
		/* if size can vary use size else just use PAGE_SIZE */
		size = nc->size;
#endif
		/* Even if we own the page, we do not use atomic_set().
		 * This would break get_page_unless_zero() users.
		 */
4645
		page_ref_add(page, PAGE_FRAG_CACHE_MAX_SIZE);
4646 4647

		/* reset page count bias and offset to start of new frag */
4648
		nc->pfmemalloc = page_is_pfmemalloc(page);
4649
		nc->pagecnt_bias = PAGE_FRAG_CACHE_MAX_SIZE + 1;
4650 4651 4652 4653 4654 4655 4656
		nc->offset = size;
	}

	offset = nc->offset - fragsz;
	if (unlikely(offset < 0)) {
		page = virt_to_page(nc->va);

4657
		if (!page_ref_sub_and_test(page, nc->pagecnt_bias))
4658 4659
			goto refill;

4660 4661 4662 4663 4664
		if (unlikely(nc->pfmemalloc)) {
			free_the_page(page, compound_order(page));
			goto refill;
		}

4665 4666 4667 4668 4669
#if (PAGE_SIZE < PAGE_FRAG_CACHE_MAX_SIZE)
		/* if size can vary use size else just use PAGE_SIZE */
		size = nc->size;
#endif
		/* OK, page count is 0, we can safely set it */
4670
		set_page_count(page, PAGE_FRAG_CACHE_MAX_SIZE + 1);
4671 4672

		/* reset page count bias and offset to start of new frag */
4673
		nc->pagecnt_bias = PAGE_FRAG_CACHE_MAX_SIZE + 1;
4674
		offset = size - fragsz;
4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686
		if (unlikely(offset < 0)) {
			/*
			 * The caller is trying to allocate a fragment
			 * with fragsz > PAGE_SIZE but the cache isn't big
			 * enough to satisfy the request, this may
			 * happen in low memory conditions.
			 * We don't release the cache page because
			 * it could make memory pressure worse
			 * so we simply return NULL here.
			 */
			return NULL;
		}
4687 4688 4689
	}

	nc->pagecnt_bias--;
4690
	offset &= align_mask;
4691 4692 4693 4694
	nc->offset = offset;

	return nc->va + offset;
}
4695
EXPORT_SYMBOL(page_frag_alloc_align);
4696 4697 4698 4699

/*
 * Frees a page fragment allocated out of either a compound or order 0 page.
 */
4700
void page_frag_free(void *addr)
4701 4702 4703
{
	struct page *page = virt_to_head_page(addr);

4704 4705
	if (unlikely(put_page_testzero(page)))
		free_the_page(page, compound_order(page));
4706
}
4707
EXPORT_SYMBOL(page_frag_free);
4708

4709 4710
static void *make_alloc_exact(unsigned long addr, unsigned int order,
		size_t size)
Andi Kleen's avatar
Andi Kleen committed
4711 4712
{
	if (addr) {
4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724
		unsigned long nr = DIV_ROUND_UP(size, PAGE_SIZE);
		struct page *page = virt_to_page((void *)addr);
		struct page *last = page + nr;

		split_page_owner(page, 1 << order);
		split_page_memcg(page, 1 << order);
		while (page < --last)
			set_page_refcounted(last);

		last = page + (1UL << order);
		for (page += nr; page < last; page++)
			__free_pages_ok(page, 0, FPI_TO_TAIL);
Andi Kleen's avatar
Andi Kleen committed
4725 4726 4727 4728
	}
	return (void *)addr;
}

4729 4730 4731
/**
 * alloc_pages_exact - allocate an exact number physically-contiguous pages.
 * @size: the number of bytes to allocate
4732
 * @gfp_mask: GFP flags for the allocation, must not contain __GFP_COMP
4733 4734 4735 4736 4737 4738 4739 4740
 *
 * This function is similar to alloc_pages(), except that it allocates the
 * minimum number of pages to satisfy the request.  alloc_pages() can only
 * allocate memory in power-of-two pages.
 *
 * This function is also limited by MAX_ORDER.
 *
 * Memory allocated by this function must be released by free_pages_exact().
4741 4742
 *
 * Return: pointer to the allocated area or %NULL in case of error.
4743 4744 4745 4746 4747 4748
 */
void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
{
	unsigned int order = get_order(size);
	unsigned long addr;

4749 4750
	if (WARN_ON_ONCE(gfp_mask & (__GFP_COMP | __GFP_HIGHMEM)))
		gfp_mask &= ~(__GFP_COMP | __GFP_HIGHMEM);
4751

4752
	addr = __get_free_pages(gfp_mask, order);
Andi Kleen's avatar
Andi Kleen committed
4753
	return make_alloc_exact(addr, order, size);
4754 4755 4756
}
EXPORT_SYMBOL(alloc_pages_exact);

Andi Kleen's avatar
Andi Kleen committed
4757 4758 4759
/**
 * alloc_pages_exact_nid - allocate an exact number of physically-contiguous
 *			   pages on a node.
4760
 * @nid: the preferred node ID where memory should be allocated
Andi Kleen's avatar
Andi Kleen committed
4761
 * @size: the number of bytes to allocate
4762
 * @gfp_mask: GFP flags for the allocation, must not contain __GFP_COMP
Andi Kleen's avatar
Andi Kleen committed
4763 4764 4765
 *
 * Like alloc_pages_exact(), but try to allocate on node nid first before falling
 * back.
4766 4767
 *
 * Return: pointer to the allocated area or %NULL in case of error.
Andi Kleen's avatar
Andi Kleen committed
4768
 */
4769
void * __meminit alloc_pages_exact_nid(int nid, size_t size, gfp_t gfp_mask)
Andi Kleen's avatar
Andi Kleen committed
4770
{
4771
	unsigned int order = get_order(size);
4772 4773
	struct page *p;

4774 4775
	if (WARN_ON_ONCE(gfp_mask & (__GFP_COMP | __GFP_HIGHMEM)))
		gfp_mask &= ~(__GFP_COMP | __GFP_HIGHMEM);
4776 4777

	p = alloc_pages_node(nid, gfp_mask, order);
Andi Kleen's avatar
Andi Kleen committed
4778 4779 4780 4781 4782
	if (!p)
		return NULL;
	return make_alloc_exact((unsigned long)page_address(p), order, size);
}

4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 4794 4795 4796 4797 4798 4799 4800 4801
/**
 * free_pages_exact - release memory allocated via alloc_pages_exact()
 * @virt: the value returned by alloc_pages_exact.
 * @size: size of allocation, same value as passed to alloc_pages_exact().
 *
 * Release the memory allocated by a previous call to alloc_pages_exact.
 */
void free_pages_exact(void *virt, size_t size)
{
	unsigned long addr = (unsigned long)virt;
	unsigned long end = addr + PAGE_ALIGN(size);

	while (addr < end) {
		free_page(addr);
		addr += PAGE_SIZE;
	}
}
EXPORT_SYMBOL(free_pages_exact);

4802 4803 4804 4805
/**
 * nr_free_zone_pages - count number of pages beyond high watermark
 * @offset: The zone index of the highest zone
 *
4806
 * nr_free_zone_pages() counts the number of pages which are beyond the
4807 4808
 * high watermark within all zones at or below a given zone index.  For each
 * zone, the number of pages is calculated as:
4809 4810
 *
 *     nr_free_zone_pages = managed_pages - high_pages
4811 4812
 *
 * Return: number of pages beyond high watermark.
4813
 */
4814
static unsigned long nr_free_zone_pages(int offset)
Linus Torvalds's avatar
Linus Torvalds committed
4815
{
4816
	struct zoneref *z;
4817 4818
	struct zone *zone;

4819
	/* Just pick one node, since fallback list is circular */
4820
	unsigned long sum = 0;
Linus Torvalds's avatar
Linus Torvalds committed
4821

4822
	struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);
Linus Torvalds's avatar
Linus Torvalds committed
4823

4824
	for_each_zone_zonelist(zone, z, zonelist, offset) {
4825
		unsigned long size = zone_managed_pages(zone);
4826
		unsigned long high = high_wmark_pages(zone);
4827 4828
		if (size > high)
			sum += size - high;
Linus Torvalds's avatar
Linus Torvalds committed
4829 4830 4831 4832 4833
	}

	return sum;
}

4834 4835 4836 4837 4838
/**
 * nr_free_buffer_pages - count number of pages beyond high watermark
 *
 * nr_free_buffer_pages() counts the number of pages which are beyond the high
 * watermark within ZONE_DMA and ZONE_NORMAL.
4839 4840 4841
 *
 * Return: number of pages beyond high watermark within ZONE_DMA and
 * ZONE_NORMAL.
Linus Torvalds's avatar
Linus Torvalds committed
4842
 */
4843
unsigned long nr_free_buffer_pages(void)
Linus Torvalds's avatar
Linus Torvalds committed
4844
{
Al Viro's avatar
Al Viro committed
4845
	return nr_free_zone_pages(gfp_zone(GFP_USER));
Linus Torvalds's avatar
Linus Torvalds committed
4846
}
4847
EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
Linus Torvalds's avatar
Linus Torvalds committed
4848

4849 4850 4851 4852 4853 4854
static void zoneref_set_zone(struct zone *zone, struct zoneref *zoneref)
{
	zoneref->zone = zone;
	zoneref->zone_idx = zone_idx(zone);
}

Linus Torvalds's avatar
Linus Torvalds committed
4855 4856
/*
 * Builds allocation fallback zone lists.
4857 4858
 *
 * Add all populated zones of a node to the zonelist.
Linus Torvalds's avatar
Linus Torvalds committed
4859
 */
4860
static int build_zonerefs_node(pg_data_t *pgdat, struct zoneref *zonerefs)
Linus Torvalds's avatar
Linus Torvalds committed
4861
{
4862
	struct zone *zone;
4863
	enum zone_type zone_type = MAX_NR_ZONES;
4864
	int nr_zones = 0;
4865 4866

	do {
4867
		zone_type--;
4868
		zone = pgdat->node_zones + zone_type;
4869
		if (populated_zone(zone)) {
4870
			zoneref_set_zone(zone, &zonerefs[nr_zones++]);
4871
			check_highest_zone(zone_type);
Linus Torvalds's avatar
Linus Torvalds committed
4872
		}
4873
	} while (zone_type);
4874

4875
	return nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
4876 4877 4878
}

#ifdef CONFIG_NUMA
4879 4880 4881

static int __parse_numa_zonelist_order(char *s)
{
4882
	/*
Ingo Molnar's avatar
Ingo Molnar committed
4883
	 * We used to support different zonelists modes but they turned
4884 4885 4886 4887 4888 4889
	 * out to be just not useful. Let's keep the warning in place
	 * if somebody still use the cmd line parameter so that we do
	 * not fail it silently
	 */
	if (!(*s == 'd' || *s == 'D' || *s == 'n' || *s == 'N')) {
		pr_warn("Ignoring unsupported numa_zonelist_order value:  %s\n", s);
4890 4891 4892 4893 4894
		return -EINVAL;
	}
	return 0;
}

4895 4896
static char numa_zonelist_order[] = "Node";
#define NUMA_ZONELIST_ORDER_LEN	16
4897 4898 4899
/*
 * sysctl handler for numa_zonelist_order
 */
4900
static int numa_zonelist_order_handler(struct ctl_table *table, int write,
4901
		void *buffer, size_t *length, loff_t *ppos)
4902
{
4903 4904 4905
	if (write)
		return __parse_numa_zonelist_order(buffer);
	return proc_dostring(table, write, buffer, length, ppos);
4906 4907 4908 4909
}

static int node_load[MAX_NUMNODES];

Linus Torvalds's avatar
Linus Torvalds committed
4910
/**
4911
 * find_next_best_node - find the next node that should appear in a given node's fallback list
Linus Torvalds's avatar
Linus Torvalds committed
4912 4913 4914 4915 4916 4917 4918 4919 4920 4921
 * @node: node whose fallback list we're appending
 * @used_node_mask: nodemask_t of already used nodes
 *
 * We use a number of factors to determine which is the next node that should
 * appear on a given node's fallback list.  The node should not have appeared
 * already in @node's fallback list, and it should be the next closest node
 * according to the distance array (which contains arbitrary distance values
 * from each node to each node in the system), and should also prefer nodes
 * with no CPUs, since presumably they'll have very little allocation pressure
 * on them otherwise.
4922 4923
 *
 * Return: node id of the found node or %NUMA_NO_NODE if no node is found.
Linus Torvalds's avatar
Linus Torvalds committed
4924
 */
4925
int find_next_best_node(int node, nodemask_t *used_node_mask)
Linus Torvalds's avatar
Linus Torvalds committed
4926
{
4927
	int n, val;
Linus Torvalds's avatar
Linus Torvalds committed
4928
	int min_val = INT_MAX;
David Rientjes's avatar
David Rientjes committed
4929
	int best_node = NUMA_NO_NODE;
Linus Torvalds's avatar
Linus Torvalds committed
4930

4931 4932 4933 4934 4935
	/* Use the local node if we haven't already */
	if (!node_isset(node, *used_node_mask)) {
		node_set(node, *used_node_mask);
		return node;
	}
Linus Torvalds's avatar
Linus Torvalds committed
4936

4937
	for_each_node_state(n, N_MEMORY) {
Linus Torvalds's avatar
Linus Torvalds committed
4938 4939 4940 4941 4942 4943 4944 4945

		/* Don't want a node to appear more than once */
		if (node_isset(n, *used_node_mask))
			continue;

		/* Use the distance array to find the distance */
		val = node_distance(node, n);

4946 4947 4948
		/* Penalize nodes under us ("prefer the next node") */
		val += (n < node);

Linus Torvalds's avatar
Linus Torvalds committed
4949
		/* Give preference to headless and unused nodes */
4950
		if (!cpumask_empty(cpumask_of_node(n)))
Linus Torvalds's avatar
Linus Torvalds committed
4951 4952 4953
			val += PENALTY_FOR_NODE_WITH_CPUS;

		/* Slight preference for less loaded node */
4954
		val *= MAX_NUMNODES;
Linus Torvalds's avatar
Linus Torvalds committed
4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968
		val += node_load[n];

		if (val < min_val) {
			min_val = val;
			best_node = n;
		}
	}

	if (best_node >= 0)
		node_set(best_node, *used_node_mask);

	return best_node;
}

4969 4970 4971 4972 4973 4974

/*
 * Build zonelists ordered by node and zones within node.
 * This results in maximum locality--normal zone overflows into local
 * DMA zone, if any--but risks exhausting DMA zone.
 */
4975 4976
static void build_zonelists_in_node_order(pg_data_t *pgdat, int *node_order,
		unsigned nr_nodes)
Linus Torvalds's avatar
Linus Torvalds committed
4977
{
4978 4979 4980 4981 4982 4983 4984 4985 4986
	struct zoneref *zonerefs;
	int i;

	zonerefs = pgdat->node_zonelists[ZONELIST_FALLBACK]._zonerefs;

	for (i = 0; i < nr_nodes; i++) {
		int nr_zones;

		pg_data_t *node = NODE_DATA(node_order[i]);
4987

4988 4989 4990 4991 4992
		nr_zones = build_zonerefs_node(node, zonerefs);
		zonerefs += nr_zones;
	}
	zonerefs->zone = NULL;
	zonerefs->zone_idx = 0;
4993 4994
}

4995 4996 4997 4998 4999
/*
 * Build gfp_thisnode zonelists
 */
static void build_thisnode_zonelists(pg_data_t *pgdat)
{
5000 5001
	struct zoneref *zonerefs;
	int nr_zones;
5002

5003 5004 5005 5006 5007
	zonerefs = pgdat->node_zonelists[ZONELIST_NOFALLBACK]._zonerefs;
	nr_zones = build_zonerefs_node(pgdat, zonerefs);
	zonerefs += nr_zones;
	zonerefs->zone = NULL;
	zonerefs->zone_idx = 0;
5008 5009
}

5010 5011 5012 5013 5014 5015 5016 5017 5018
/*
 * Build zonelists ordered by zone and nodes within zones.
 * This results in conserving DMA zone[s] until all Normal memory is
 * exhausted, but results in overflowing to remote node while memory
 * may still exist in local DMA zone.
 */

static void build_zonelists(pg_data_t *pgdat)
{
5019
	static int node_order[MAX_NUMNODES];
5020
	int node, nr_nodes = 0;
5021
	nodemask_t used_mask = NODE_MASK_NONE;
5022
	int local_node, prev_node;
Linus Torvalds's avatar
Linus Torvalds committed
5023 5024 5025 5026

	/* NUMA-aware ordering of nodes */
	local_node = pgdat->node_id;
	prev_node = local_node;
5027 5028

	memset(node_order, 0, sizeof(node_order));
Linus Torvalds's avatar
Linus Torvalds committed
5029 5030 5031 5032 5033 5034
	while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
		/*
		 * We don't want to pressure a particular node.
		 * So adding penalty to the first node in same
		 * distance group to make it round-robin.
		 */
5035 5036
		if (node_distance(local_node, node) !=
		    node_distance(local_node, prev_node))
5037
			node_load[node] += 1;
5038

5039
		node_order[nr_nodes++] = node;
Linus Torvalds's avatar
Linus Torvalds committed
5040 5041
		prev_node = node;
	}
5042

5043
	build_zonelists_in_node_order(pgdat, node_order, nr_nodes);
5044
	build_thisnode_zonelists(pgdat);
5045 5046 5047 5048
	pr_info("Fallback order for Node %d: ", local_node);
	for (node = 0; node < nr_nodes; node++)
		pr_cont("%d ", node_order[node]);
	pr_cont("\n");
Linus Torvalds's avatar
Linus Torvalds committed
5049 5050
}

5051 5052 5053 5054 5055 5056 5057 5058 5059
#ifdef CONFIG_HAVE_MEMORYLESS_NODES
/*
 * Return node id of node used for "local" allocations.
 * I.e., first node id of first zone in arg node's generic zonelist.
 * Used for initializing percpu 'numa_mem', which is used primarily
 * for kernel allocations, so use GFP_KERNEL flags to locate zonelist.
 */
int local_memory_node(int node)
{
5060
	struct zoneref *z;
5061

5062
	z = first_zones_zonelist(node_zonelist(node, GFP_KERNEL),
5063
				   gfp_zone(GFP_KERNEL),
5064
				   NULL);
5065
	return zone_to_nid(z->zone);
5066 5067
}
#endif
5068

5069 5070
static void setup_min_unmapped_ratio(void);
static void setup_min_slab_ratio(void);
Linus Torvalds's avatar
Linus Torvalds committed
5071 5072
#else	/* CONFIG_NUMA */

5073
static void build_zonelists(pg_data_t *pgdat)
Linus Torvalds's avatar
Linus Torvalds committed
5074
{
5075
	int node, local_node;
5076 5077
	struct zoneref *zonerefs;
	int nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
5078 5079 5080

	local_node = pgdat->node_id;

5081 5082 5083
	zonerefs = pgdat->node_zonelists[ZONELIST_FALLBACK]._zonerefs;
	nr_zones = build_zonerefs_node(pgdat, zonerefs);
	zonerefs += nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
5084

5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095
	/*
	 * Now we build the zonelist so that it contains the zones
	 * of all the other nodes.
	 * We don't want to pressure a particular node, so when
	 * building the zones for node N, we make sure that the
	 * zones coming right after the local ones are those from
	 * node N+1 (modulo N)
	 */
	for (node = local_node + 1; node < MAX_NUMNODES; node++) {
		if (!node_online(node))
			continue;
5096 5097
		nr_zones = build_zonerefs_node(NODE_DATA(node), zonerefs);
		zonerefs += nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
5098
	}
5099 5100 5101
	for (node = 0; node < local_node; node++) {
		if (!node_online(node))
			continue;
5102 5103
		nr_zones = build_zonerefs_node(NODE_DATA(node), zonerefs);
		zonerefs += nr_zones;
5104 5105
	}

5106 5107
	zonerefs->zone = NULL;
	zonerefs->zone_idx = 0;
Linus Torvalds's avatar
Linus Torvalds committed
5108 5109 5110 5111
}

#endif	/* CONFIG_NUMA */

5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126
/*
 * Boot pageset table. One per cpu which is going to be used for all
 * zones and all nodes. The parameters will be set in such a way
 * that an item put on a list will immediately be handed over to
 * the buddy list. This is safe since pageset manipulation is done
 * with interrupts disabled.
 *
 * The boot_pagesets must be kept even after bootup is complete for
 * unused processors and/or zones. They do play a role for bootstrapping
 * hotplugged processors.
 *
 * zoneinfo_show() and maybe other functions do
 * not check if the processor is online before following the pageset pointer.
 * Other parts of the kernel may not check if the zone is available.
 */
5127
static void per_cpu_pages_init(struct per_cpu_pages *pcp, struct per_cpu_zonestat *pzstats);
5128 5129 5130
/* These effectively disable the pcplists in the boot pageset completely */
#define BOOT_PAGESET_HIGH	0
#define BOOT_PAGESET_BATCH	1
5131 5132
static DEFINE_PER_CPU(struct per_cpu_pages, boot_pageset);
static DEFINE_PER_CPU(struct per_cpu_zonestat, boot_zonestats);
5133

5134
static void __build_all_zonelists(void *data)
Linus Torvalds's avatar
Linus Torvalds committed
5135
{
5136
	int nid;
5137
	int __maybe_unused cpu;
5138
	pg_data_t *self = data;
5139
	unsigned long flags;
5140

5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153
	/*
	 * Explicitly disable this CPU's interrupts before taking seqlock
	 * to prevent any IRQ handler from calling into the page allocator
	 * (e.g. GFP_ATOMIC) that could hit zonelist_iter_begin and livelock.
	 */
	local_irq_save(flags);
	/*
	 * Explicitly disable this CPU's synchronous printk() before taking
	 * seqlock to prevent any printk() from trying to hold port->lock, for
	 * tty_insert_flip_string_and_push_buffer() on other CPU might be
	 * calling kmalloc(GFP_ATOMIC | __GFP_NOWARN) with port->lock held.
	 */
	printk_deferred_enter();
5154
	write_seqlock(&zonelist_update_seq);
5155

5156 5157 5158
#ifdef CONFIG_NUMA
	memset(node_load, 0, sizeof(node_load));
#endif
5159

5160 5161 5162 5163
	/*
	 * This node is hotadded and no memory is yet present.   So just
	 * building zonelists is fine - no need to touch other nodes.
	 */
5164 5165
	if (self && !node_online(self->node_id)) {
		build_zonelists(self);
5166
	} else {
5167 5168 5169 5170 5171
		/*
		 * All possible nodes have pgdat preallocated
		 * in free_area_init
		 */
		for_each_node(nid) {
5172
			pg_data_t *pgdat = NODE_DATA(nid);
5173

5174 5175
			build_zonelists(pgdat);
		}
5176

5177 5178 5179 5180 5181 5182 5183 5184 5185
#ifdef CONFIG_HAVE_MEMORYLESS_NODES
		/*
		 * We now know the "local memory node" for each node--
		 * i.e., the node of the first zone in the generic zonelist.
		 * Set up numa_mem percpu variable for on-line cpus.  During
		 * boot, only the boot cpu should be on-line;  we'll init the
		 * secondary cpus' numa_mem as they come on-line.  During
		 * node/memory hotplug, we'll fixup all on-line cpus.
		 */
5186
		for_each_online_cpu(cpu)
5187
			set_cpu_numa_mem(cpu, local_memory_node(cpu_to_node(cpu)));
5188
#endif
5189
	}
5190

5191
	write_sequnlock(&zonelist_update_seq);
5192 5193
	printk_deferred_exit();
	local_irq_restore(flags);
5194 5195
}

5196 5197 5198
static noinline void __init
build_all_zonelists_init(void)
{
5199 5200
	int cpu;

5201
	__build_all_zonelists(NULL);
5202 5203 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216

	/*
	 * Initialize the boot_pagesets that are going to be used
	 * for bootstrapping processors. The real pagesets for
	 * each zone will be allocated later when the per cpu
	 * allocator is available.
	 *
	 * boot_pagesets are used also for bootstrapping offline
	 * cpus if the system is already booted because the pagesets
	 * are needed to initialize allocators on a specific cpu too.
	 * F.e. the percpu allocator needs the page allocator which
	 * needs the percpu allocator in order to allocate its pagesets
	 * (a chicken-egg dilemma).
	 */
	for_each_possible_cpu(cpu)
5217
		per_cpu_pages_init(&per_cpu(boot_pageset, cpu), &per_cpu(boot_zonestats, cpu));
5218

5219 5220 5221 5222
	mminit_verify_zonelist();
	cpuset_init_current_mems_allowed();
}

5223 5224
/*
 * unless system_state == SYSTEM_BOOTING.
5225
 *
5226
 * __ref due to call of __init annotated helper build_all_zonelists_init
5227
 * [protected by SYSTEM_BOOTING].
5228
 */
5229
void __ref build_all_zonelists(pg_data_t *pgdat)
5230
{
5231 5232
	unsigned long vm_total_pages;

5233
	if (system_state == SYSTEM_BOOTING) {
5234
		build_all_zonelists_init();
5235
	} else {
5236
		__build_all_zonelists(pgdat);
5237 5238
		/* cpuset refresh routine should be here */
	}
5239 5240
	/* Get the number of free pages beyond high watermark in all zones. */
	vm_total_pages = nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
5241 5242 5243 5244 5245 5246 5247
	/*
	 * Disable grouping by mobility if the number of pages in the
	 * system is too low to allow the mechanism to work. It would be
	 * more accurate, but expensive to check per-zone. This check is
	 * made on memory-hotadd so a system can start with mobility
	 * disabled and enable it later
	 */
5248
	if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
5249 5250 5251 5252
		page_group_by_mobility_disabled = 1;
	else
		page_group_by_mobility_disabled = 0;

5253
	pr_info("Built %u zonelists, mobility grouping %s.  Total pages: %ld\n",
Joe Perches's avatar
Joe Perches committed
5254 5255 5256
		nr_online_nodes,
		page_group_by_mobility_disabled ? "off" : "on",
		vm_total_pages);
5257
#ifdef CONFIG_NUMA
5258
	pr_info("Policy zone: %s\n", zone_names[policy_zone]);
5259
#endif
Linus Torvalds's avatar
Linus Torvalds committed
5260 5261
}

5262
static int zone_batchsize(struct zone *zone)
Linus Torvalds's avatar
Linus Torvalds committed
5263
{
5264 5265
#ifdef CONFIG_MMU
	int batch;
Linus Torvalds's avatar
Linus Torvalds committed
5266

5267 5268 5269 5270 5271 5272 5273 5274 5275 5276
	/*
	 * The number of pages to batch allocate is either ~0.1%
	 * of the zone or 1MB, whichever is smaller. The batch
	 * size is striking a balance between allocation latency
	 * and zone lock contention.
	 */
	batch = min(zone_managed_pages(zone) >> 10, SZ_1M / PAGE_SIZE);
	batch /= 4;		/* We effectively *= 4 below */
	if (batch < 1)
		batch = 1;
5277

5278
	/*
5279 5280 5281 5282 5283 5284 5285 5286
	 * Clamp the batch to a 2^n - 1 value. Having a power
	 * of 2 value was found to be more likely to have
	 * suboptimal cache aliasing properties in some cases.
	 *
	 * For example if 2 tasks are alternately allocating
	 * batches of pages, one task can end up with a lot
	 * of pages of one half of the possible page colors
	 * and the other with pages of the other colors.
5287
	 */
5288
	batch = rounddown_pow_of_two(batch + batch/2) - 1;
5289

5290
	return batch;
5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307

#else
	/* The deferral and batching of frees should be suppressed under NOMMU
	 * conditions.
	 *
	 * The problem is that NOMMU needs to be able to allocate large chunks
	 * of contiguous memory as there's no hardware page translation to
	 * assemble apparent contiguous memory from discontiguous pages.
	 *
	 * Queueing large contiguous runs of pages for batching, however,
	 * causes the pages to actually be freed in smaller chunks.  As there
	 * can be a significant delay between the individual batches being
	 * recycled, this leads to the once large chunks of space being
	 * fragmented and becoming unavailable for high-order allocations.
	 */
	return 0;
#endif
5308 5309
}

5310
static int percpu_pagelist_high_fraction;
5311
static int zone_highsize(struct zone *zone, int batch, int cpu_online)
5312
{
5313 5314 5315 5316
#ifdef CONFIG_MMU
	int high;
	int nr_split_cpus;
	unsigned long total_pages;
5317

5318
	if (!percpu_pagelist_high_fraction) {
Mel Gorman's avatar
Mel Gorman committed
5319
		/*
5320 5321 5322
		 * By default, the high value of the pcp is based on the zone
		 * low watermark so that if they are full then background
		 * reclaim will not be started prematurely.
Mel Gorman's avatar
Mel Gorman committed
5323
		 */
5324 5325
		total_pages = low_wmark_pages(zone);
	} else {
Mel Gorman's avatar
Mel Gorman committed
5326
		/*
5327 5328 5329
		 * If percpu_pagelist_high_fraction is configured, the high
		 * value is based on a fraction of the managed pages in the
		 * zone.
Mel Gorman's avatar
Mel Gorman committed
5330
		 */
5331
		total_pages = zone_managed_pages(zone) / percpu_pagelist_high_fraction;
Mel Gorman's avatar
Mel Gorman committed
5332 5333 5334
	}

	/*
5335 5336 5337 5338 5339 5340
	 * Split the high value across all online CPUs local to the zone. Note
	 * that early in boot that CPUs may not be online yet and that during
	 * CPU hotplug that the cpumask is not yet updated when a CPU is being
	 * onlined. For memory nodes that have no CPUs, split pcp->high across
	 * all online CPUs to mitigate the risk that reclaim is triggered
	 * prematurely due to pages stored on pcp lists.
Mel Gorman's avatar
Mel Gorman committed
5341
	 */
5342 5343 5344 5345
	nr_split_cpus = cpumask_weight(cpumask_of_node(zone_to_nid(zone))) + cpu_online;
	if (!nr_split_cpus)
		nr_split_cpus = num_online_cpus();
	high = total_pages / nr_split_cpus;
Mel Gorman's avatar
Mel Gorman committed
5346

5347 5348 5349 5350 5351
	/*
	 * Ensure high is at least batch*4. The multiple is based on the
	 * historical relationship between high and batch.
	 */
	high = max(high, batch << 2);
5352

5353 5354 5355 5356
	return high;
#else
	return 0;
#endif
5357 5358
}

5359
/*
5360 5361 5362 5363 5364 5365 5366 5367 5368 5369 5370 5371 5372 5373
 * pcp->high and pcp->batch values are related and generally batch is lower
 * than high. They are also related to pcp->count such that count is lower
 * than high, and as soon as it reaches high, the pcplist is flushed.
 *
 * However, guaranteeing these relations at all times would require e.g. write
 * barriers here but also careful usage of read barriers at the read side, and
 * thus be prone to error and bad for performance. Thus the update only prevents
 * store tearing. Any new users of pcp->batch and pcp->high should ensure they
 * can cope with those fields changing asynchronously, and fully trust only the
 * pcp->count field on the local CPU with interrupts disabled.
 *
 * mutex_is_locked(&pcp_batch_high_lock) required when calling this function
 * outside of boot time (or some other assurance that no concurrent updaters
 * exist).
5374
 */
5375 5376
static void pageset_update(struct per_cpu_pages *pcp, unsigned long high,
		unsigned long batch)
5377
{
5378 5379
	WRITE_ONCE(pcp->batch, batch);
	WRITE_ONCE(pcp->high, high);
5380 5381
}

5382
static void per_cpu_pages_init(struct per_cpu_pages *pcp, struct per_cpu_zonestat *pzstats)
5383
{
5384
	int pindex;
5385

5386 5387
	memset(pcp, 0, sizeof(*pcp));
	memset(pzstats, 0, sizeof(*pzstats));
5388

5389 5390 5391
	spin_lock_init(&pcp->lock);
	for (pindex = 0; pindex < NR_PCP_LISTS; pindex++)
		INIT_LIST_HEAD(&pcp->lists[pindex]);
Mel Gorman's avatar
Mel Gorman committed
5392

5393 5394 5395 5396 5397 5398 5399 5400 5401 5402
	/*
	 * Set batch and high values safe for a boot pageset. A true percpu
	 * pageset's initialization will update them subsequently. Here we don't
	 * need to be as careful as pageset_update() as nobody can access the
	 * pageset yet.
	 */
	pcp->high = BOOT_PAGESET_HIGH;
	pcp->batch = BOOT_PAGESET_BATCH;
	pcp->free_factor = 0;
}
5403

5404 5405 5406 5407 5408
static void __zone_set_pageset_high_and_batch(struct zone *zone, unsigned long high,
		unsigned long batch)
{
	struct per_cpu_pages *pcp;
	int cpu;
Mel Gorman's avatar
Mel Gorman committed
5409

5410 5411 5412
	for_each_possible_cpu(cpu) {
		pcp = per_cpu_ptr(zone->per_cpu_pageset, cpu);
		pageset_update(pcp, high, batch);
Mel Gorman's avatar
Mel Gorman committed
5413
	}
5414
}
5415

5416 5417 5418 5419 5420 5421 5422
/*
 * Calculate and set new high and batch values for all per-cpu pagesets of a
 * zone based on the zone's size.
 */
static void zone_set_pageset_high_and_batch(struct zone *zone, int cpu_online)
{
	int new_high, new_batch;
5423

5424 5425
	new_batch = max(1, zone_batchsize(zone));
	new_high = zone_highsize(zone, new_batch, cpu_online);
5426

5427 5428 5429
	if (zone->pageset_high == new_high &&
	    zone->pageset_batch == new_batch)
		return;
5430

5431 5432
	zone->pageset_high = new_high;
	zone->pageset_batch = new_batch;
5433

5434
	__zone_set_pageset_high_and_batch(zone, new_high, new_batch);
5435
}
Mel Gorman's avatar
Mel Gorman committed
5436

5437
void __meminit setup_zone_pageset(struct zone *zone)
Mel Gorman's avatar
Mel Gorman committed
5438
{
5439
	int cpu;
Mel Gorman's avatar
Mel Gorman committed
5440

5441 5442 5443
	/* Size may be 0 on !SMP && !NUMA */
	if (sizeof(struct per_cpu_zonestat) > 0)
		zone->per_cpu_zonestats = alloc_percpu(struct per_cpu_zonestat);
Mel Gorman's avatar
Mel Gorman committed
5444

5445 5446 5447 5448
	zone->per_cpu_pageset = alloc_percpu(struct per_cpu_pages);
	for_each_possible_cpu(cpu) {
		struct per_cpu_pages *pcp;
		struct per_cpu_zonestat *pzstats;
Mel Gorman's avatar
Mel Gorman committed
5449

5450 5451 5452
		pcp = per_cpu_ptr(zone->per_cpu_pageset, cpu);
		pzstats = per_cpu_ptr(zone->per_cpu_zonestats, cpu);
		per_cpu_pages_init(pcp, pzstats);
5453
	}
5454 5455

	zone_set_pageset_high_and_batch(zone, 0);
Mel Gorman's avatar
Mel Gorman committed
5456
}
Mel Gorman's avatar
Mel Gorman committed
5457

5458
/*
5459 5460
 * The zone indicated has a new number of managed_pages; batch sizes and percpu
 * page high values need to be recalculated.
5461
 */
5462
static void zone_pcp_update(struct zone *zone, int cpu_online)
5463
{
5464 5465 5466
	mutex_lock(&pcp_batch_high_lock);
	zone_set_pageset_high_and_batch(zone, cpu_online);
	mutex_unlock(&pcp_batch_high_lock);
5467 5468 5469
}

/*
5470 5471
 * Allocate per cpu pagesets and initialize them.
 * Before this call only boot pagesets were available.
5472
 */
5473
void __init setup_per_cpu_pageset(void)
5474
{
5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498
	struct pglist_data *pgdat;
	struct zone *zone;
	int __maybe_unused cpu;

	for_each_populated_zone(zone)
		setup_zone_pageset(zone);

#ifdef CONFIG_NUMA
	/*
	 * Unpopulated zones continue using the boot pagesets.
	 * The numa stats for these pagesets need to be reset.
	 * Otherwise, they will end up skewing the stats of
	 * the nodes these zones are associated with.
	 */
	for_each_possible_cpu(cpu) {
		struct per_cpu_zonestat *pzstats = &per_cpu(boot_zonestats, cpu);
		memset(pzstats->vm_numa_event, 0,
		       sizeof(pzstats->vm_numa_event));
	}
#endif

	for_each_online_pgdat(pgdat)
		pgdat->per_cpu_nodestats =
			alloc_percpu(struct per_cpu_nodestat);
5499 5500
}

5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516
__meminit void zone_pcp_init(struct zone *zone)
{
	/*
	 * per cpu subsystem is not up at this point. The following code
	 * relies on the ability of the linker to provide the
	 * offset of a (static) per cpu variable into the per cpu area.
	 */
	zone->per_cpu_pageset = &boot_pageset;
	zone->per_cpu_zonestats = &boot_zonestats;
	zone->pageset_high = BOOT_PAGESET_HIGH;
	zone->pageset_batch = BOOT_PAGESET_BATCH;

	if (populated_zone(zone))
		pr_debug("  %s zone: %lu pages, LIFO batch:%u\n", zone->name,
			 zone->present_pages, zone_batchsize(zone));
}
Mel Gorman's avatar
Mel Gorman committed
5517

5518 5519
void adjust_managed_page_count(struct page *page, long count)
{
5520
	atomic_long_add(count, &page_zone(page)->managed_pages);
5521
	totalram_pages_add(count);
5522 5523
#ifdef CONFIG_HIGHMEM
	if (PageHighMem(page))
5524
		totalhigh_pages_add(count);
5525
#endif
5526
}
5527
EXPORT_SYMBOL(adjust_managed_page_count);
5528

5529
unsigned long free_reserved_area(void *start, void *end, int poison, const char *s)
5530
{
5531 5532
	void *pos;
	unsigned long pages = 0;
5533

5534 5535 5536
	start = (void *)PAGE_ALIGN((unsigned long)start);
	end = (void *)((unsigned long)end & PAGE_MASK);
	for (pos = start; pos < end; pos += PAGE_SIZE, pages++) {
5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5547
		struct page *page = virt_to_page(pos);
		void *direct_map_addr;

		/*
		 * 'direct_map_addr' might be different from 'pos'
		 * because some architectures' virt_to_page()
		 * work with aliases.  Getting the direct map
		 * address ensures that we get a _writeable_
		 * alias for the memset().
		 */
		direct_map_addr = page_address(page);
5548 5549 5550 5551 5552
		/*
		 * Perform a kasan-unchecked memset() since this memory
		 * has not been initialized.
		 */
		direct_map_addr = kasan_reset_tag(direct_map_addr);
5553
		if ((unsigned int)poison <= 0xFF)
5554 5555 5556
			memset(direct_map_addr, poison, PAGE_SIZE);

		free_reserved_page(page);
5557 5558 5559
	}

	if (pages && s)
5560
		pr_info("Freeing %s memory: %ldK\n", s, K(pages));
5561 5562 5563 5564

	return pages;
}

5565
static int page_alloc_cpu_dead(unsigned int cpu)
Linus Torvalds's avatar
Linus Torvalds committed
5566
{
5567
	struct zone *zone;
Linus Torvalds's avatar
Linus Torvalds committed
5568

5569
	lru_add_drain_cpu(cpu);
5570
	mlock_drain_remote(cpu);
5571
	drain_pages(cpu);
5572

5573 5574 5575 5576 5577 5578 5579
	/*
	 * Spill the event counters of the dead processor
	 * into the current processors event counters.
	 * This artificially elevates the count of the current
	 * processor.
	 */
	vm_events_fold_cpu(cpu);
5580

5581 5582 5583 5584 5585 5586 5587 5588
	/*
	 * Zero the differential counters of the dead processor
	 * so that the vm statistics are consistent.
	 *
	 * This is only okay since the processor is dead and cannot
	 * race with what we are doing.
	 */
	cpu_vm_stats_fold(cpu);
5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 5599 5600 5601

	for_each_populated_zone(zone)
		zone_pcp_update(zone, 0);

	return 0;
}

static int page_alloc_cpu_online(unsigned int cpu)
{
	struct zone *zone;

	for_each_populated_zone(zone)
		zone_pcp_update(zone, 1);
5602
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
5603 5604
}

5605
void __init page_alloc_init_cpuhp(void)
Linus Torvalds's avatar
Linus Torvalds committed
5606
{
5607 5608
	int ret;

5609 5610 5611
	ret = cpuhp_setup_state_nocalls(CPUHP_PAGE_ALLOC,
					"mm/page_alloc:pcp",
					page_alloc_cpu_online,
5612 5613
					page_alloc_cpu_dead);
	WARN_ON(ret < 0);
Linus Torvalds's avatar
Linus Torvalds committed
5614 5615
}

5616
/*
5617
 * calculate_totalreserve_pages - called when sysctl_lowmem_reserve_ratio
5618 5619 5620 5621 5622 5623
 *	or min_free_kbytes changes.
 */
static void calculate_totalreserve_pages(void)
{
	struct pglist_data *pgdat;
	unsigned long reserve_pages = 0;
5624
	enum zone_type i, j;
5625 5626

	for_each_online_pgdat(pgdat) {
5627 5628 5629

		pgdat->totalreserve_pages = 0;

5630 5631
		for (i = 0; i < MAX_NR_ZONES; i++) {
			struct zone *zone = pgdat->node_zones + i;
5632
			long max = 0;
5633
			unsigned long managed_pages = zone_managed_pages(zone);
5634 5635 5636 5637 5638 5639 5640

			/* Find valid and maximum lowmem_reserve in the zone */
			for (j = i; j < MAX_NR_ZONES; j++) {
				if (zone->lowmem_reserve[j] > max)
					max = zone->lowmem_reserve[j];
			}

5641 5642
			/* we treat the high watermark as reserved pages. */
			max += high_wmark_pages(zone);
5643

5644 5645
			if (max > managed_pages)
				max = managed_pages;
5646

5647
			pgdat->totalreserve_pages += max;
5648

5649 5650 5651 5652 5653 5654
			reserve_pages += max;
		}
	}
	totalreserve_pages = reserve_pages;
}

Linus Torvalds's avatar
Linus Torvalds committed
5655 5656
/*
 * setup_per_zone_lowmem_reserve - called whenever
5657
 *	sysctl_lowmem_reserve_ratio changes.  Ensures that each zone
Linus Torvalds's avatar
Linus Torvalds committed
5658 5659 5660 5661 5662 5663
 *	has a correct pages reserved value, so an adequate number of
 *	pages are left in the zone after a successful __alloc_pages().
 */
static void setup_per_zone_lowmem_reserve(void)
{
	struct pglist_data *pgdat;
5664
	enum zone_type i, j;
Linus Torvalds's avatar
Linus Torvalds committed
5665

5666
	for_each_online_pgdat(pgdat) {
5667 5668 5669 5670 5671 5672 5673
		for (i = 0; i < MAX_NR_ZONES - 1; i++) {
			struct zone *zone = &pgdat->node_zones[i];
			int ratio = sysctl_lowmem_reserve_ratio[i];
			bool clear = !ratio || !zone_managed_pages(zone);
			unsigned long managed_pages = 0;

			for (j = i + 1; j < MAX_NR_ZONES; j++) {
5674 5675 5676
				struct zone *upper_zone = &pgdat->node_zones[j];

				managed_pages += zone_managed_pages(upper_zone);
5677

5678 5679 5680
				if (clear)
					zone->lowmem_reserve[j] = 0;
				else
5681
					zone->lowmem_reserve[j] = managed_pages / ratio;
Linus Torvalds's avatar
Linus Torvalds committed
5682 5683 5684
			}
		}
	}
5685 5686 5687

	/* update totalreserve_pages */
	calculate_totalreserve_pages();
Linus Torvalds's avatar
Linus Torvalds committed
5688 5689
}

5690
static void __setup_per_zone_wmarks(void)
Linus Torvalds's avatar
Linus Torvalds committed
5691 5692 5693 5694 5695 5696 5697 5698 5699
{
	unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
	unsigned long lowmem_pages = 0;
	struct zone *zone;
	unsigned long flags;

	/* Calculate total number of !ZONE_HIGHMEM pages */
	for_each_zone(zone) {
		if (!is_highmem(zone))
5700
			lowmem_pages += zone_managed_pages(zone);
Linus Torvalds's avatar
Linus Torvalds committed
5701 5702 5703
	}

	for_each_zone(zone) {
5704 5705
		u64 tmp;

5706
		spin_lock_irqsave(&zone->lock, flags);
5707
		tmp = (u64)pages_min * zone_managed_pages(zone);
5708
		do_div(tmp, lowmem_pages);
Linus Torvalds's avatar
Linus Torvalds committed
5709 5710
		if (is_highmem(zone)) {
			/*
Nick Piggin's avatar
Nick Piggin committed
5711 5712 5713 5714
			 * __GFP_HIGH and PF_MEMALLOC allocations usually don't
			 * need highmem pages, so cap pages_min to a small
			 * value here.
			 *
5715
			 * The WMARK_HIGH-WMARK_LOW and (WMARK_LOW-WMARK_MIN)
5716
			 * deltas control async page reclaim, and so should
Nick Piggin's avatar
Nick Piggin committed
5717
			 * not be capped for highmem.
Linus Torvalds's avatar
Linus Torvalds committed
5718
			 */
5719
			unsigned long min_pages;
Linus Torvalds's avatar
Linus Torvalds committed
5720

5721
			min_pages = zone_managed_pages(zone) / 1024;
5722
			min_pages = clamp(min_pages, SWAP_CLUSTER_MAX, 128UL);
5723
			zone->_watermark[WMARK_MIN] = min_pages;
Linus Torvalds's avatar
Linus Torvalds committed
5724
		} else {
Nick Piggin's avatar
Nick Piggin committed
5725 5726
			/*
			 * If it's a lowmem zone, reserve a number of pages
Linus Torvalds's avatar
Linus Torvalds committed
5727 5728
			 * proportionate to the zone's size.
			 */
5729
			zone->_watermark[WMARK_MIN] = tmp;
Linus Torvalds's avatar
Linus Torvalds committed
5730 5731
		}

5732 5733 5734 5735 5736 5737
		/*
		 * Set the kswapd watermarks distance according to the
		 * scale factor in proportion to available memory, but
		 * ensure a minimum size on small systems.
		 */
		tmp = max_t(u64, tmp >> 2,
5738
			    mult_frac(zone_managed_pages(zone),
5739 5740
				      watermark_scale_factor, 10000));

5741
		zone->watermark_boost = 0;
5742
		zone->_watermark[WMARK_LOW]  = min_wmark_pages(zone) + tmp;
5743 5744
		zone->_watermark[WMARK_HIGH] = low_wmark_pages(zone) + tmp;
		zone->_watermark[WMARK_PROMO] = high_wmark_pages(zone) + tmp;
5745

5746
		spin_unlock_irqrestore(&zone->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
5747
	}
5748 5749 5750

	/* update totalreserve_pages */
	calculate_totalreserve_pages();
Linus Torvalds's avatar
Linus Torvalds committed
5751 5752
}

5753 5754 5755 5756 5757 5758 5759 5760 5761
/**
 * setup_per_zone_wmarks - called when min_free_kbytes changes
 * or when memory is hot-{added|removed}
 *
 * Ensures that the watermark[min,low,high] values for each zone are set
 * correctly with respect to min_free_kbytes.
 */
void setup_per_zone_wmarks(void)
{
5762
	struct zone *zone;
5763 5764 5765
	static DEFINE_SPINLOCK(lock);

	spin_lock(&lock);
5766
	__setup_per_zone_wmarks();
5767
	spin_unlock(&lock);
5768 5769 5770 5771 5772 5773

	/*
	 * The watermark size have changed so update the pcpu batch
	 * and high limits or the limits may be inappropriate.
	 */
	for_each_zone(zone)
5774
		zone_pcp_update(zone, 0);
5775 5776
}

Linus Torvalds's avatar
Linus Torvalds committed
5777 5778 5779 5780
/*
 * Initialise min_free_kbytes.
 *
 * For small machines we want it small (128k min).  For large machines
5781
 * we want it large (256MB max).  But it is not linear, because network
Linus Torvalds's avatar
Linus Torvalds committed
5782 5783
 * bandwidth does not increase linearly with machine size.  We use
 *
5784
 *	min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
Linus Torvalds's avatar
Linus Torvalds committed
5785 5786 5787 5788 5789 5790 5791 5792 5793 5794 5795 5796 5797 5798 5799 5800
 *	min_free_kbytes = sqrt(lowmem_kbytes * 16)
 *
 * which yields
 *
 * 16MB:	512k
 * 32MB:	724k
 * 64MB:	1024k
 * 128MB:	1448k
 * 256MB:	2048k
 * 512MB:	2896k
 * 1024MB:	4096k
 * 2048MB:	5792k
 * 4096MB:	8192k
 * 8192MB:	11584k
 * 16384MB:	16384k
 */
5801
void calculate_min_free_kbytes(void)
Linus Torvalds's avatar
Linus Torvalds committed
5802 5803
{
	unsigned long lowmem_kbytes;
5804
	int new_min_free_kbytes;
Linus Torvalds's avatar
Linus Torvalds committed
5805 5806

	lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
5807 5808
	new_min_free_kbytes = int_sqrt(lowmem_kbytes * 16);

5809 5810 5811
	if (new_min_free_kbytes > user_min_free_kbytes)
		min_free_kbytes = clamp(new_min_free_kbytes, 128, 262144);
	else
5812 5813
		pr_warn("min_free_kbytes is not updated to %d because user defined value %d is preferred\n",
				new_min_free_kbytes, user_min_free_kbytes);
5814

5815 5816 5817 5818 5819
}

int __meminit init_per_zone_wmark_min(void)
{
	calculate_min_free_kbytes();
5820
	setup_per_zone_wmarks();
5821
	refresh_zone_stat_thresholds();
Linus Torvalds's avatar
Linus Torvalds committed
5822
	setup_per_zone_lowmem_reserve();
5823 5824 5825 5826 5827 5828

#ifdef CONFIG_NUMA
	setup_min_unmapped_ratio();
	setup_min_slab_ratio();
#endif

5829 5830
	khugepaged_min_free_kbytes_update();

Linus Torvalds's avatar
Linus Torvalds committed
5831 5832
	return 0;
}
5833
postcore_initcall(init_per_zone_wmark_min)
Linus Torvalds's avatar
Linus Torvalds committed
5834 5835

/*
5836
 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
Linus Torvalds's avatar
Linus Torvalds committed
5837 5838 5839
 *	that we can call two helper functions whenever min_free_kbytes
 *	changes.
 */
5840
static int min_free_kbytes_sysctl_handler(struct ctl_table *table, int write,
5841
		void *buffer, size_t *length, loff_t *ppos)
Linus Torvalds's avatar
Linus Torvalds committed
5842
{
5843 5844 5845 5846 5847 5848
	int rc;

	rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
	if (rc)
		return rc;

5849 5850
	if (write) {
		user_min_free_kbytes = min_free_kbytes;
5851
		setup_per_zone_wmarks();
5852
	}
Linus Torvalds's avatar
Linus Torvalds committed
5853 5854 5855
	return 0;
}

5856
static int watermark_scale_factor_sysctl_handler(struct ctl_table *table, int write,
5857
		void *buffer, size_t *length, loff_t *ppos)
5858 5859 5860 5861 5862 5863 5864 5865 5866 5867 5868 5869 5870
{
	int rc;

	rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
	if (rc)
		return rc;

	if (write)
		setup_per_zone_wmarks();

	return 0;
}

5871
#ifdef CONFIG_NUMA
5872
static void setup_min_unmapped_ratio(void)
5873
{
5874
	pg_data_t *pgdat;
5875 5876
	struct zone *zone;

5877
	for_each_online_pgdat(pgdat)
5878
		pgdat->min_unmapped_pages = 0;
5879

5880
	for_each_zone(zone)
5881 5882
		zone->zone_pgdat->min_unmapped_pages += (zone_managed_pages(zone) *
						         sysctl_min_unmapped_ratio) / 100;
5883
}
5884

5885

5886
static int sysctl_min_unmapped_ratio_sysctl_handler(struct ctl_table *table, int write,
5887
		void *buffer, size_t *length, loff_t *ppos)
5888 5889 5890
{
	int rc;

5891
	rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
5892 5893 5894
	if (rc)
		return rc;

5895 5896 5897 5898 5899 5900 5901 5902 5903 5904
	setup_min_unmapped_ratio();

	return 0;
}

static void setup_min_slab_ratio(void)
{
	pg_data_t *pgdat;
	struct zone *zone;

5905 5906 5907
	for_each_online_pgdat(pgdat)
		pgdat->min_slab_pages = 0;

5908
	for_each_zone(zone)
5909 5910
		zone->zone_pgdat->min_slab_pages += (zone_managed_pages(zone) *
						     sysctl_min_slab_ratio) / 100;
5911 5912
}

5913
static int sysctl_min_slab_ratio_sysctl_handler(struct ctl_table *table, int write,
5914
		void *buffer, size_t *length, loff_t *ppos)
5915 5916 5917 5918 5919 5920 5921 5922 5923
{
	int rc;

	rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
	if (rc)
		return rc;

	setup_min_slab_ratio();

5924 5925
	return 0;
}
5926 5927
#endif

Linus Torvalds's avatar
Linus Torvalds committed
5928 5929 5930 5931 5932 5933
/*
 * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
 *	proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
 *	whenever sysctl_lowmem_reserve_ratio changes.
 *
 * The reserve ratio obviously has absolutely no relation with the
5934
 * minimum watermarks. The lowmem reserve ratio can only make sense
Linus Torvalds's avatar
Linus Torvalds committed
5935 5936
 * if in function of the boot time zone sizes.
 */
5937 5938
static int lowmem_reserve_ratio_sysctl_handler(struct ctl_table *table,
		int write, void *buffer, size_t *length, loff_t *ppos)
Linus Torvalds's avatar
Linus Torvalds committed
5939
{
5940 5941
	int i;

5942
	proc_dointvec_minmax(table, write, buffer, length, ppos);
5943 5944 5945 5946 5947 5948

	for (i = 0; i < MAX_NR_ZONES; i++) {
		if (sysctl_lowmem_reserve_ratio[i] < 1)
			sysctl_lowmem_reserve_ratio[i] = 0;
	}

Linus Torvalds's avatar
Linus Torvalds committed
5949 5950 5951 5952
	setup_per_zone_lowmem_reserve();
	return 0;
}

5953
/*
5954 5955
 * percpu_pagelist_high_fraction - changes the pcp->high for each zone on each
 * cpu. It is the fraction of total pages in each zone that a hot per cpu
5956
 * pagelist can have before it gets flushed back to buddy allocator.
5957
 */
5958
static int percpu_pagelist_high_fraction_sysctl_handler(struct ctl_table *table,
5959
		int write, void *buffer, size_t *length, loff_t *ppos)
5960 5961
{
	struct zone *zone;
5962
	int old_percpu_pagelist_high_fraction;
5963 5964
	int ret;

5965
	mutex_lock(&pcp_batch_high_lock);
5966
	old_percpu_pagelist_high_fraction = percpu_pagelist_high_fraction;
5967

5968
	ret = proc_dointvec_minmax(table, write, buffer, length, ppos);
5969 5970 5971 5972
	if (!write || ret < 0)
		goto out;

	/* Sanity checking to avoid pcp imbalance */
5973 5974 5975
	if (percpu_pagelist_high_fraction &&
	    percpu_pagelist_high_fraction < MIN_PERCPU_PAGELIST_HIGH_FRACTION) {
		percpu_pagelist_high_fraction = old_percpu_pagelist_high_fraction;
5976 5977 5978 5979 5980
		ret = -EINVAL;
		goto out;
	}

	/* No change? */
5981
	if (percpu_pagelist_high_fraction == old_percpu_pagelist_high_fraction)
5982
		goto out;
5983

5984
	for_each_populated_zone(zone)
5985
		zone_set_pageset_high_and_batch(zone, 0);
5986
out:
5987
	mutex_unlock(&pcp_batch_high_lock);
5988
	return ret;
5989 5990
}

5991 5992 5993 5994 5995 5996 5997 5998 5999 6000 6001 6002 6003 6004 6005 6006 6007 6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020 6021 6022 6023 6024 6025 6026 6027 6028 6029 6030 6031 6032 6033 6034 6035 6036 6037 6038 6039 6040 6041 6042 6043 6044 6045 6046 6047 6048 6049 6050 6051 6052 6053 6054 6055 6056 6057 6058 6059 6060 6061 6062 6063 6064 6065 6066
static struct ctl_table page_alloc_sysctl_table[] = {
	{
		.procname	= "min_free_kbytes",
		.data		= &min_free_kbytes,
		.maxlen		= sizeof(min_free_kbytes),
		.mode		= 0644,
		.proc_handler	= min_free_kbytes_sysctl_handler,
		.extra1		= SYSCTL_ZERO,
	},
	{
		.procname	= "watermark_boost_factor",
		.data		= &watermark_boost_factor,
		.maxlen		= sizeof(watermark_boost_factor),
		.mode		= 0644,
		.proc_handler	= proc_dointvec_minmax,
		.extra1		= SYSCTL_ZERO,
	},
	{
		.procname	= "watermark_scale_factor",
		.data		= &watermark_scale_factor,
		.maxlen		= sizeof(watermark_scale_factor),
		.mode		= 0644,
		.proc_handler	= watermark_scale_factor_sysctl_handler,
		.extra1		= SYSCTL_ONE,
		.extra2		= SYSCTL_THREE_THOUSAND,
	},
	{
		.procname	= "percpu_pagelist_high_fraction",
		.data		= &percpu_pagelist_high_fraction,
		.maxlen		= sizeof(percpu_pagelist_high_fraction),
		.mode		= 0644,
		.proc_handler	= percpu_pagelist_high_fraction_sysctl_handler,
		.extra1		= SYSCTL_ZERO,
	},
	{
		.procname	= "lowmem_reserve_ratio",
		.data		= &sysctl_lowmem_reserve_ratio,
		.maxlen		= sizeof(sysctl_lowmem_reserve_ratio),
		.mode		= 0644,
		.proc_handler	= lowmem_reserve_ratio_sysctl_handler,
	},
#ifdef CONFIG_NUMA
	{
		.procname	= "numa_zonelist_order",
		.data		= &numa_zonelist_order,
		.maxlen		= NUMA_ZONELIST_ORDER_LEN,
		.mode		= 0644,
		.proc_handler	= numa_zonelist_order_handler,
	},
	{
		.procname	= "min_unmapped_ratio",
		.data		= &sysctl_min_unmapped_ratio,
		.maxlen		= sizeof(sysctl_min_unmapped_ratio),
		.mode		= 0644,
		.proc_handler	= sysctl_min_unmapped_ratio_sysctl_handler,
		.extra1		= SYSCTL_ZERO,
		.extra2		= SYSCTL_ONE_HUNDRED,
	},
	{
		.procname	= "min_slab_ratio",
		.data		= &sysctl_min_slab_ratio,
		.maxlen		= sizeof(sysctl_min_slab_ratio),
		.mode		= 0644,
		.proc_handler	= sysctl_min_slab_ratio_sysctl_handler,
		.extra1		= SYSCTL_ZERO,
		.extra2		= SYSCTL_ONE_HUNDRED,
	},
#endif
	{}
};

void __init page_alloc_sysctl_init(void)
{
	register_sysctl_init("vm", page_alloc_sysctl_table);
}

6067
#ifdef CONFIG_CONTIG_ALLOC
6068 6069 6070 6071 6072 6073 6074 6075 6076 6077 6078 6079 6080 6081
/* Usage: See admin-guide/dynamic-debug-howto.rst */
static void alloc_contig_dump_pages(struct list_head *page_list)
{
	DEFINE_DYNAMIC_DEBUG_METADATA(descriptor, "migrate failure");

	if (DYNAMIC_DEBUG_BRANCH(descriptor)) {
		struct page *page;

		dump_stack();
		list_for_each_entry(page, page_list, lru)
			dump_page(page, "migration failure");
	}
}

6082
/* [start, end) must belong to a single zone. */
6083
int __alloc_contig_migrate_range(struct compact_control *cc,
6084
					unsigned long start, unsigned long end)
6085 6086
{
	/* This function is based on compact_zone() from compaction.c. */
6087
	unsigned int nr_reclaimed;
6088 6089 6090
	unsigned long pfn = start;
	unsigned int tries = 0;
	int ret = 0;
6091 6092 6093 6094
	struct migration_target_control mtc = {
		.nid = zone_to_nid(cc->zone),
		.gfp_mask = GFP_USER | __GFP_MOVABLE | __GFP_RETRY_MAYFAIL,
	};
6095

6096
	lru_cache_disable();
6097

6098
	while (pfn < end || !list_empty(&cc->migratepages)) {
6099 6100 6101 6102 6103
		if (fatal_signal_pending(current)) {
			ret = -EINTR;
			break;
		}

6104 6105
		if (list_empty(&cc->migratepages)) {
			cc->nr_migratepages = 0;
6106 6107
			ret = isolate_migratepages_range(cc, pfn, end);
			if (ret && ret != -EAGAIN)
6108
				break;
6109
			pfn = cc->migrate_pfn;
6110 6111
			tries = 0;
		} else if (++tries == 5) {
6112
			ret = -EBUSY;
6113 6114 6115
			break;
		}

6116 6117 6118
		nr_reclaimed = reclaim_clean_pages_from_list(cc->zone,
							&cc->migratepages);
		cc->nr_migratepages -= nr_reclaimed;
6119

6120
		ret = migrate_pages(&cc->migratepages, alloc_migration_target,
6121
			NULL, (unsigned long)&mtc, cc->mode, MR_CONTIG_RANGE, NULL);
6122 6123 6124 6125 6126 6127 6128

		/*
		 * On -ENOMEM, migrate_pages() bails out right away. It is pointless
		 * to retry again over this error, so do the same here.
		 */
		if (ret == -ENOMEM)
			break;
6129
	}
6130

6131
	lru_cache_enable();
6132
	if (ret < 0) {
6133
		if (!(cc->gfp_mask & __GFP_NOWARN) && ret == -EBUSY)
6134
			alloc_contig_dump_pages(&cc->migratepages);
6135 6136 6137 6138
		putback_movable_pages(&cc->migratepages);
		return ret;
	}
	return 0;
6139 6140 6141 6142 6143 6144
}

/**
 * alloc_contig_range() -- tries to allocate given range of pages
 * @start:	start PFN to allocate
 * @end:	one-past-the-last PFN to allocate
Ingo Molnar's avatar
Ingo Molnar committed
6145
 * @migratetype:	migratetype of the underlying pageblocks (either
6146 6147 6148
 *			#MIGRATE_MOVABLE or #MIGRATE_CMA).  All pageblocks
 *			in range must have the same migratetype and it must
 *			be either of the two.
6149
 * @gfp_mask:	GFP mask to use during compaction
6150
 *
6151 6152
 * The PFN range does not have to be pageblock aligned. The PFN range must
 * belong to a single zone.
6153
 *
6154 6155 6156
 * The first thing this routine does is attempt to MIGRATE_ISOLATE all
 * pageblocks in the range.  Once isolated, the pageblocks should not
 * be modified by others.
6157
 *
6158
 * Return: zero on success or negative error code.  On success all
6159 6160 6161
 * pages which PFN is in [start, end) are allocated for the caller and
 * need to be freed with free_contig_range().
 */
6162
int alloc_contig_range(unsigned long start, unsigned long end,
6163
		       unsigned migratetype, gfp_t gfp_mask)
6164 6165
{
	unsigned long outer_start, outer_end;
6166
	int order;
6167
	int ret = 0;
6168

6169 6170 6171 6172
	struct compact_control cc = {
		.nr_migratepages = 0,
		.order = -1,
		.zone = page_zone(pfn_to_page(start)),
6173
		.mode = MIGRATE_SYNC,
6174
		.ignore_skip_hint = true,
6175
		.no_set_skip_hint = true,
6176
		.gfp_mask = current_gfp_context(gfp_mask),
6177
		.alloc_contig = true,
6178 6179 6180
	};
	INIT_LIST_HEAD(&cc.migratepages);

6181 6182 6183 6184
	/*
	 * What we do here is we mark all pageblocks in range as
	 * MIGRATE_ISOLATE.  Because pageblock and max order pages may
	 * have different sizes, and due to the way page allocator
6185
	 * work, start_isolate_page_range() has special handlings for this.
6186 6187 6188
	 *
	 * Once the pageblocks are marked as MIGRATE_ISOLATE, we
	 * migrate the pages from an unaligned range (ie. pages that
6189
	 * we are interested in). This will put all the pages in
6190 6191 6192 6193 6194 6195 6196 6197 6198 6199 6200 6201
	 * range back to page allocator as MIGRATE_ISOLATE.
	 *
	 * When this is done, we take the pages in range from page
	 * allocator removing them from the buddy system.  This way
	 * page allocator will never consider using them.
	 *
	 * This lets us mark the pageblocks back as
	 * MIGRATE_CMA/MIGRATE_MOVABLE so that free pages in the
	 * aligned range but not in the unaligned, original range are
	 * put back to page allocator so that buddy can use them.
	 */

6202
	ret = start_isolate_page_range(start, end, migratetype, 0, gfp_mask);
6203
	if (ret)
6204
		goto done;
6205

6206 6207
	drain_all_pages(cc.zone);

6208 6209
	/*
	 * In case of -EBUSY, we'd like to know which page causes problem.
6210 6211 6212 6213 6214 6215 6216
	 * So, just fall through. test_pages_isolated() has a tracepoint
	 * which will report the busy page.
	 *
	 * It is possible that busy pages could become available before
	 * the call to test_pages_isolated, and the range will actually be
	 * allocated.  So, if we fall through be sure to clear ret so that
	 * -EBUSY is not accidentally used or returned to caller.
6217
	 */
6218
	ret = __alloc_contig_migrate_range(&cc, start, end);
6219
	if (ret && ret != -EBUSY)
6220
		goto done;
6221
	ret = 0;
6222 6223

	/*
6224
	 * Pages from [start, end) are within a pageblock_nr_pages
6225 6226 6227 6228 6229 6230 6231 6232 6233 6234 6235 6236 6237 6238 6239 6240 6241 6242
	 * aligned blocks that are marked as MIGRATE_ISOLATE.  What's
	 * more, all pages in [start, end) are free in page allocator.
	 * What we are going to do is to allocate all pages from
	 * [start, end) (that is remove them from page allocator).
	 *
	 * The only problem is that pages at the beginning and at the
	 * end of interesting range may be not aligned with pages that
	 * page allocator holds, ie. they can be part of higher order
	 * pages.  Because of this, we reserve the bigger range and
	 * once this is done free the pages we are not interested in.
	 *
	 * We don't have to hold zone->lock here because the pages are
	 * isolated thus they won't get removed from buddy.
	 */

	order = 0;
	outer_start = start;
	while (!PageBuddy(pfn_to_page(outer_start))) {
6243
		if (++order > MAX_ORDER) {
6244 6245
			outer_start = start;
			break;
6246 6247 6248 6249
		}
		outer_start &= ~0UL << order;
	}

6250
	if (outer_start != start) {
6251
		order = buddy_order(pfn_to_page(outer_start));
6252 6253 6254 6255 6256 6257 6258 6259 6260 6261 6262

		/*
		 * outer_start page could be small order buddy page and
		 * it doesn't include start page. Adjust outer_start
		 * in this case to report failed page properly
		 * on tracepoint in test_pages_isolated()
		 */
		if (outer_start + (1UL << order) <= start)
			outer_start = start;
	}

6263
	/* Make sure the range is really isolated. */
6264
	if (test_pages_isolated(outer_start, end, 0)) {
6265 6266 6267 6268
		ret = -EBUSY;
		goto done;
	}

6269
	/* Grab isolated pages from freelists. */
6270
	outer_end = isolate_freepages_range(&cc, outer_start, end);
6271 6272 6273 6274 6275 6276 6277 6278 6279 6280 6281 6282
	if (!outer_end) {
		ret = -EBUSY;
		goto done;
	}

	/* Free head and tail (if any) */
	if (start != outer_start)
		free_contig_range(outer_start, start - outer_start);
	if (end != outer_end)
		free_contig_range(end, outer_end - end);

done:
6283
	undo_isolate_page_range(start, end, migratetype);
6284 6285
	return ret;
}
6286
EXPORT_SYMBOL(alloc_contig_range);
6287 6288 6289 6290 6291 6292 6293 6294 6295 6296 6297 6298 6299 6300 6301 6302 6303 6304 6305 6306 6307 6308 6309 6310 6311

static int __alloc_contig_pages(unsigned long start_pfn,
				unsigned long nr_pages, gfp_t gfp_mask)
{
	unsigned long end_pfn = start_pfn + nr_pages;

	return alloc_contig_range(start_pfn, end_pfn, MIGRATE_MOVABLE,
				  gfp_mask);
}

static bool pfn_range_valid_contig(struct zone *z, unsigned long start_pfn,
				   unsigned long nr_pages)
{
	unsigned long i, end_pfn = start_pfn + nr_pages;
	struct page *page;

	for (i = start_pfn; i < end_pfn; i++) {
		page = pfn_to_online_page(i);
		if (!page)
			return false;

		if (page_zone(page) != z)
			return false;

		if (PageReserved(page))
6312 6313 6314
			return false;

		if (PageHuge(page))
6315 6316 6317 6318 6319 6320 6321 6322 6323 6324 6325 6326 6327 6328 6329 6330 6331 6332 6333 6334 6335 6336 6337 6338 6339 6340
			return false;
	}
	return true;
}

static bool zone_spans_last_pfn(const struct zone *zone,
				unsigned long start_pfn, unsigned long nr_pages)
{
	unsigned long last_pfn = start_pfn + nr_pages - 1;

	return zone_spans_pfn(zone, last_pfn);
}

/**
 * alloc_contig_pages() -- tries to find and allocate contiguous range of pages
 * @nr_pages:	Number of contiguous pages to allocate
 * @gfp_mask:	GFP mask to limit search and used during compaction
 * @nid:	Target node
 * @nodemask:	Mask for other possible nodes
 *
 * This routine is a wrapper around alloc_contig_range(). It scans over zones
 * on an applicable zonelist to find a contiguous pfn range which can then be
 * tried for allocation with alloc_contig_range(). This routine is intended
 * for allocation requests which can not be fulfilled with the buddy allocator.
 *
 * The allocated memory is always aligned to a page boundary. If nr_pages is a
6341 6342
 * power of two, then allocated range is also guaranteed to be aligned to same
 * nr_pages (e.g. 1GB request would be aligned to 1GB).
6343 6344 6345 6346 6347 6348 6349 6350 6351 6352 6353 6354 6355 6356 6357 6358 6359 6360 6361 6362 6363 6364 6365 6366 6367 6368 6369 6370 6371 6372 6373 6374 6375 6376 6377 6378 6379 6380 6381 6382 6383 6384
 *
 * Allocated pages can be freed with free_contig_range() or by manually calling
 * __free_page() on each allocated page.
 *
 * Return: pointer to contiguous pages on success, or NULL if not successful.
 */
struct page *alloc_contig_pages(unsigned long nr_pages, gfp_t gfp_mask,
				int nid, nodemask_t *nodemask)
{
	unsigned long ret, pfn, flags;
	struct zonelist *zonelist;
	struct zone *zone;
	struct zoneref *z;

	zonelist = node_zonelist(nid, gfp_mask);
	for_each_zone_zonelist_nodemask(zone, z, zonelist,
					gfp_zone(gfp_mask), nodemask) {
		spin_lock_irqsave(&zone->lock, flags);

		pfn = ALIGN(zone->zone_start_pfn, nr_pages);
		while (zone_spans_last_pfn(zone, pfn, nr_pages)) {
			if (pfn_range_valid_contig(zone, pfn, nr_pages)) {
				/*
				 * We release the zone lock here because
				 * alloc_contig_range() will also lock the zone
				 * at some point. If there's an allocation
				 * spinning on this lock, it may win the race
				 * and cause alloc_contig_range() to fail...
				 */
				spin_unlock_irqrestore(&zone->lock, flags);
				ret = __alloc_contig_pages(pfn, nr_pages,
							gfp_mask);
				if (!ret)
					return pfn_to_page(pfn);
				spin_lock_irqsave(&zone->lock, flags);
			}
			pfn += nr_pages;
		}
		spin_unlock_irqrestore(&zone->lock, flags);
	}
	return NULL;
}
6385
#endif /* CONFIG_CONTIG_ALLOC */
6386

6387
void free_contig_range(unsigned long pfn, unsigned long nr_pages)
6388
{
6389
	unsigned long count = 0;
6390 6391 6392 6393 6394 6395 6396

	for (; nr_pages--; pfn++) {
		struct page *page = pfn_to_page(pfn);

		count += page_count(page) != 1;
		__free_page(page);
	}
6397
	WARN(count != 0, "%lu pages are still in use!\n", count);
6398
}
6399
EXPORT_SYMBOL(free_contig_range);
6400

6401 6402 6403 6404 6405 6406 6407 6408 6409 6410 6411 6412 6413 6414 6415 6416 6417 6418 6419 6420 6421
/*
 * Effectively disable pcplists for the zone by setting the high limit to 0
 * and draining all cpus. A concurrent page freeing on another CPU that's about
 * to put the page on pcplist will either finish before the drain and the page
 * will be drained, or observe the new high limit and skip the pcplist.
 *
 * Must be paired with a call to zone_pcp_enable().
 */
void zone_pcp_disable(struct zone *zone)
{
	mutex_lock(&pcp_batch_high_lock);
	__zone_set_pageset_high_and_batch(zone, 0, 1);
	__drain_all_pages(zone, true);
}

void zone_pcp_enable(struct zone *zone)
{
	__zone_set_pageset_high_and_batch(zone, zone->pageset_high, zone->pageset_batch);
	mutex_unlock(&pcp_batch_high_lock);
}

6422 6423
void zone_pcp_reset(struct zone *zone)
{
6424
	int cpu;
6425
	struct per_cpu_zonestat *pzstats;
6426

6427
	if (zone->per_cpu_pageset != &boot_pageset) {
6428
		for_each_online_cpu(cpu) {
6429 6430
			pzstats = per_cpu_ptr(zone->per_cpu_zonestats, cpu);
			drain_zonestat(zone, pzstats);
6431
		}
6432 6433
		free_percpu(zone->per_cpu_pageset);
		zone->per_cpu_pageset = &boot_pageset;
6434 6435 6436 6437
		if (zone->per_cpu_zonestats != &boot_zonestats) {
			free_percpu(zone->per_cpu_zonestats);
			zone->per_cpu_zonestats = &boot_zonestats;
		}
6438 6439 6440
	}
}

6441
#ifdef CONFIG_MEMORY_HOTREMOVE
6442
/*
6443 6444
 * All pages in the range must be in a single zone, must not contain holes,
 * must span full sections, and must be isolated before calling this function.
6445
 */
6446
void __offline_isolated_pages(unsigned long start_pfn, unsigned long end_pfn)
6447
{
6448
	unsigned long pfn = start_pfn;
6449 6450
	struct page *page;
	struct zone *zone;
6451
	unsigned int order;
6452
	unsigned long flags;
6453

6454
	offline_mem_sections(pfn, end_pfn);
6455 6456 6457 6458
	zone = page_zone(pfn_to_page(pfn));
	spin_lock_irqsave(&zone->lock, flags);
	while (pfn < end_pfn) {
		page = pfn_to_page(pfn);
6459 6460 6461 6462 6463 6464 6465 6466
		/*
		 * The HWPoisoned page may be not in buddy system, and
		 * page_count() is not 0.
		 */
		if (unlikely(!PageBuddy(page) && PageHWPoison(page))) {
			pfn++;
			continue;
		}
6467 6468 6469 6470 6471 6472 6473 6474 6475 6476
		/*
		 * At this point all remaining PageOffline() pages have a
		 * reference count of 0 and can simply be skipped.
		 */
		if (PageOffline(page)) {
			BUG_ON(page_count(page));
			BUG_ON(PageBuddy(page));
			pfn++;
			continue;
		}
6477

6478 6479
		BUG_ON(page_count(page));
		BUG_ON(!PageBuddy(page));
6480
		order = buddy_order(page);
6481
		del_page_from_free_list(page, zone, order);
6482 6483 6484 6485 6486
		pfn += (1 << order);
	}
	spin_unlock_irqrestore(&zone->lock, flags);
}
#endif
6487

6488 6489 6490
/*
 * This function returns a stable result only if called under zone lock.
 */
6491 6492 6493
bool is_free_buddy_page(struct page *page)
{
	unsigned long pfn = page_to_pfn(page);
6494
	unsigned int order;
6495

6496
	for (order = 0; order <= MAX_ORDER; order++) {
6497 6498
		struct page *page_head = page - (pfn & ((1 << order) - 1));

6499 6500
		if (PageBuddy(page_head) &&
		    buddy_order_unsafe(page_head) >= order)
6501 6502 6503
			break;
	}

6504
	return order <= MAX_ORDER;
6505
}
6506
EXPORT_SYMBOL(is_free_buddy_page);
6507 6508 6509

#ifdef CONFIG_MEMORY_FAILURE
/*
6510 6511
 * Break down a higher-order page in sub-pages, and keep our target out of
 * buddy allocator.
6512
 */
6513 6514 6515 6516 6517 6518 6519 6520 6521 6522 6523 6524 6525 6526 6527 6528 6529 6530 6531 6532 6533 6534 6535 6536
static void break_down_buddy_pages(struct zone *zone, struct page *page,
				   struct page *target, int low, int high,
				   int migratetype)
{
	unsigned long size = 1 << high;
	struct page *current_buddy, *next_page;

	while (high > low) {
		high--;
		size >>= 1;

		if (target >= &page[size]) {
			next_page = page + size;
			current_buddy = page;
		} else {
			next_page = page;
			current_buddy = page + size;
		}

		if (set_page_guard(zone, current_buddy, high, migratetype))
			continue;

		if (current_buddy != target) {
			add_to_free_list(current_buddy, zone, high, migratetype);
6537
			set_buddy_order(current_buddy, high);
6538 6539 6540 6541 6542 6543 6544 6545 6546
			page = next_page;
		}
	}
}

/*
 * Take a page that will be marked as poisoned off the buddy allocator.
 */
bool take_page_off_buddy(struct page *page)
6547 6548 6549 6550 6551
{
	struct zone *zone = page_zone(page);
	unsigned long pfn = page_to_pfn(page);
	unsigned long flags;
	unsigned int order;
6552
	bool ret = false;
6553 6554

	spin_lock_irqsave(&zone->lock, flags);
6555
	for (order = 0; order <= MAX_ORDER; order++) {
6556
		struct page *page_head = page - (pfn & ((1 << order) - 1));
6557
		int page_order = buddy_order(page_head);
6558

6559
		if (PageBuddy(page_head) && page_order >= order) {
6560 6561 6562 6563
			unsigned long pfn_head = page_to_pfn(page_head);
			int migratetype = get_pfnblock_migratetype(page_head,
								   pfn_head);

6564
			del_page_from_free_list(page_head, zone, page_order);
6565
			break_down_buddy_pages(zone, page_head, page, 0,
6566
						page_order, migratetype);
6567
			SetPageHWPoisonTakenOff(page);
6568 6569
			if (!is_migrate_isolate(migratetype))
				__mod_zone_freepage_state(zone, -1, migratetype);
6570
			ret = true;
6571 6572
			break;
		}
6573 6574
		if (page_count(page_head) > 0)
			break;
6575 6576
	}
	spin_unlock_irqrestore(&zone->lock, flags);
6577
	return ret;
6578
}
6579 6580 6581 6582 6583 6584 6585 6586 6587 6588 6589 6590 6591 6592 6593 6594 6595 6596 6597 6598 6599 6600 6601 6602

/*
 * Cancel takeoff done by take_page_off_buddy().
 */
bool put_page_back_buddy(struct page *page)
{
	struct zone *zone = page_zone(page);
	unsigned long pfn = page_to_pfn(page);
	unsigned long flags;
	int migratetype = get_pfnblock_migratetype(page, pfn);
	bool ret = false;

	spin_lock_irqsave(&zone->lock, flags);
	if (put_page_testzero(page)) {
		ClearPageHWPoisonTakenOff(page);
		__free_one_page(page, pfn, zone, 0, migratetype, FPI_NONE);
		if (TestClearPageHWPoison(page)) {
			ret = true;
		}
	}
	spin_unlock_irqrestore(&zone->lock, flags);

	return ret;
}
6603
#endif
6604 6605 6606 6607 6608 6609 6610 6611 6612 6613 6614 6615 6616 6617 6618

#ifdef CONFIG_ZONE_DMA
bool has_managed_dma(void)
{
	struct pglist_data *pgdat;

	for_each_online_pgdat(pgdat) {
		struct zone *zone = &pgdat->node_zones[ZONE_DMA];

		if (managed_zone(zone))
			return true;
	}
	return false;
}
#endif /* CONFIG_ZONE_DMA */
6619 6620 6621 6622 6623 6624 6625 6626 6627 6628 6629 6630 6631 6632 6633 6634 6635 6636 6637 6638 6639 6640 6641 6642 6643 6644 6645 6646 6647 6648 6649 6650 6651 6652 6653 6654 6655 6656 6657 6658 6659 6660 6661 6662 6663 6664 6665 6666 6667 6668 6669 6670 6671 6672 6673 6674 6675 6676 6677 6678 6679 6680 6681 6682 6683 6684 6685 6686 6687 6688 6689 6690 6691 6692 6693 6694 6695 6696 6697 6698 6699 6700 6701 6702 6703 6704 6705 6706 6707 6708 6709 6710 6711 6712 6713 6714 6715 6716 6717 6718 6719 6720 6721 6722 6723 6724 6725 6726 6727 6728 6729 6730 6731 6732 6733 6734 6735 6736 6737 6738 6739 6740 6741 6742 6743 6744 6745 6746 6747 6748 6749 6750 6751 6752 6753 6754 6755 6756 6757 6758 6759 6760 6761 6762 6763 6764 6765

#ifdef CONFIG_UNACCEPTED_MEMORY

/* Counts number of zones with unaccepted pages. */
static DEFINE_STATIC_KEY_FALSE(zones_with_unaccepted_pages);

static bool lazy_accept = true;

static int __init accept_memory_parse(char *p)
{
	if (!strcmp(p, "lazy")) {
		lazy_accept = true;
		return 0;
	} else if (!strcmp(p, "eager")) {
		lazy_accept = false;
		return 0;
	} else {
		return -EINVAL;
	}
}
early_param("accept_memory", accept_memory_parse);

static bool page_contains_unaccepted(struct page *page, unsigned int order)
{
	phys_addr_t start = page_to_phys(page);
	phys_addr_t end = start + (PAGE_SIZE << order);

	return range_contains_unaccepted_memory(start, end);
}

static void accept_page(struct page *page, unsigned int order)
{
	phys_addr_t start = page_to_phys(page);

	accept_memory(start, start + (PAGE_SIZE << order));
}

static bool try_to_accept_memory_one(struct zone *zone)
{
	unsigned long flags;
	struct page *page;
	bool last;

	if (list_empty(&zone->unaccepted_pages))
		return false;

	spin_lock_irqsave(&zone->lock, flags);
	page = list_first_entry_or_null(&zone->unaccepted_pages,
					struct page, lru);
	if (!page) {
		spin_unlock_irqrestore(&zone->lock, flags);
		return false;
	}

	list_del(&page->lru);
	last = list_empty(&zone->unaccepted_pages);

	__mod_zone_freepage_state(zone, -MAX_ORDER_NR_PAGES, MIGRATE_MOVABLE);
	__mod_zone_page_state(zone, NR_UNACCEPTED, -MAX_ORDER_NR_PAGES);
	spin_unlock_irqrestore(&zone->lock, flags);

	accept_page(page, MAX_ORDER);

	__free_pages_ok(page, MAX_ORDER, FPI_TO_TAIL);

	if (last)
		static_branch_dec(&zones_with_unaccepted_pages);

	return true;
}

static bool try_to_accept_memory(struct zone *zone, unsigned int order)
{
	long to_accept;
	int ret = false;

	/* How much to accept to get to high watermark? */
	to_accept = high_wmark_pages(zone) -
		    (zone_page_state(zone, NR_FREE_PAGES) -
		    __zone_watermark_unusable_free(zone, order, 0));

	/* Accept at least one page */
	do {
		if (!try_to_accept_memory_one(zone))
			break;
		ret = true;
		to_accept -= MAX_ORDER_NR_PAGES;
	} while (to_accept > 0);

	return ret;
}

static inline bool has_unaccepted_memory(void)
{
	return static_branch_unlikely(&zones_with_unaccepted_pages);
}

static bool __free_unaccepted(struct page *page)
{
	struct zone *zone = page_zone(page);
	unsigned long flags;
	bool first = false;

	if (!lazy_accept)
		return false;

	spin_lock_irqsave(&zone->lock, flags);
	first = list_empty(&zone->unaccepted_pages);
	list_add_tail(&page->lru, &zone->unaccepted_pages);
	__mod_zone_freepage_state(zone, MAX_ORDER_NR_PAGES, MIGRATE_MOVABLE);
	__mod_zone_page_state(zone, NR_UNACCEPTED, MAX_ORDER_NR_PAGES);
	spin_unlock_irqrestore(&zone->lock, flags);

	if (first)
		static_branch_inc(&zones_with_unaccepted_pages);

	return true;
}

#else

static bool page_contains_unaccepted(struct page *page, unsigned int order)
{
	return false;
}

static void accept_page(struct page *page, unsigned int order)
{
}

static bool try_to_accept_memory(struct zone *zone, unsigned int order)
{
	return false;
}

static inline bool has_unaccepted_memory(void)
{
	return false;
}

static bool __free_unaccepted(struct page *page)
{
	BUILD_BUG();
	return false;
}

#endif /* CONFIG_UNACCEPTED_MEMORY */