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
};

Linus Torvalds's avatar
Linus Torvalds committed
287
int min_free_kbytes = 1024;
288
int user_min_free_kbytes = -1;
289 290
static int watermark_boost_factor __read_mostly = 15000;
static int watermark_scale_factor = 10;
Tejun Heo's avatar
Tejun Heo committed
291 292 293 294

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

296
#if MAX_NUMNODES > 1
297
unsigned int nr_node_ids __read_mostly = MAX_NUMNODES;
298
unsigned int nr_online_nodes __read_mostly = 1;
299
EXPORT_SYMBOL(nr_node_ids);
300
EXPORT_SYMBOL(nr_online_nodes);
301 302
#endif

303 304 305 306 307 308
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);

309 310
int page_group_by_mobility_disabled __read_mostly;

311
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
312 313 314 315 316
/*
 * 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.
 */
317
DEFINE_STATIC_KEY_TRUE(deferred_pages);
318

319
static inline bool deferred_pages_enabled(void)
320
{
321
	return static_branch_unlikely(&deferred_pages);
322 323
}

324
/*
325 326 327 328
 * 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.
329
 */
330 331
static bool __ref
_deferred_grow_zone(struct zone *zone, unsigned int order)
332
{
333
       return deferred_grow_zone(zone, order);
334 335
}
#else
336
static inline bool deferred_pages_enabled(void)
337
{
338
	return false;
339
}
340
#endif /* CONFIG_DEFERRED_STRUCT_PAGE_INIT */
341

342
/* Return a pointer to the bitmap storing bits affecting a block of pages */
343
static inline unsigned long *get_pageblock_bitmap(const struct page *page,
344 345 346
							unsigned long pfn)
{
#ifdef CONFIG_SPARSEMEM
347
	return section_to_usemap(__pfn_to_section(pfn));
348 349 350 351 352
#else
	return page_zone(page)->pageblock_flags;
#endif /* CONFIG_SPARSEMEM */
}

353
static inline int pfn_to_bitidx(const struct page *page, unsigned long pfn)
354 355 356 357
{
#ifdef CONFIG_SPARSEMEM
	pfn &= (PAGES_PER_SECTION-1);
#else
358
	pfn = pfn - pageblock_start_pfn(page_zone(page)->zone_start_pfn);
359
#endif /* CONFIG_SPARSEMEM */
360
	return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
361 362
}

363 364 365 366 367 368 369 370 371 372
/**
 * 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
 */
unsigned long get_pfnblock_flags_mask(const struct page *page,
					unsigned long pfn, unsigned long mask)
373 374 375 376 377 378 379 380 381
{
	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);
382 383 384 385 386 387
	/*
	 * 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]);
388
	return (word >> bitidx) & mask;
389 390
}

391 392
static __always_inline int get_pfnblock_migratetype(const struct page *page,
					unsigned long pfn)
393
{
394
	return get_pfnblock_flags_mask(page, pfn, MIGRATETYPE_MASK);
395 396 397 398 399 400 401 402 403 404 405 406 407 408 409
}

/**
 * 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;
410
	unsigned long word;
411 412

	BUILD_BUG_ON(NR_PAGEBLOCK_BITS != 4);
413
	BUILD_BUG_ON(MIGRATE_TYPES > (1 << PB_migratetype_bits));
414 415 416 417 418 419 420 421

	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);

422 423
	mask <<= bitidx;
	flags <<= bitidx;
424 425

	word = READ_ONCE(bitmap[word_bitidx]);
426 427
	do {
	} while (!try_cmpxchg(&bitmap[word_bitidx], &word, (word & ~mask) | flags));
428
}
429

430
void set_pageblock_migratetype(struct page *page, int migratetype)
431
{
432 433
	if (unlikely(page_group_by_mobility_disabled &&
		     migratetype < MIGRATE_PCPTYPES))
434 435
		migratetype = MIGRATE_UNMOVABLE;

436
	set_pfnblock_flags_mask(page, (unsigned long)migratetype,
437
				page_to_pfn(page), MIGRATETYPE_MASK);
438 439
}

Nick Piggin's avatar
Nick Piggin committed
440
#ifdef CONFIG_DEBUG_VM
441
static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
442
{
443
	int ret;
444 445
	unsigned seq;
	unsigned long pfn = page_to_pfn(page);
446
	unsigned long sp, start_pfn;
447

448 449
	do {
		seq = zone_span_seqbegin(zone);
450 451
		start_pfn = zone->zone_start_pfn;
		sp = zone->spanned_pages;
452
		ret = !zone_spans_pfn(zone, pfn);
453 454
	} while (zone_span_seqretry(zone, seq));

455
	if (ret)
456 457 458
		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);
459

460
	return ret;
461 462 463 464 465
}

/*
 * Temporary debugging check for pages not lying within a given zone.
 */
466
static int __maybe_unused bad_range(struct zone *zone, struct page *page)
467 468
{
	if (page_outside_zone_boundaries(zone, page))
Linus Torvalds's avatar
Linus Torvalds committed
469
		return 1;
470
	if (zone != page_zone(page))
471 472
		return 1;

Linus Torvalds's avatar
Linus Torvalds committed
473 474
	return 0;
}
Nick Piggin's avatar
Nick Piggin committed
475
#else
476
static inline int __maybe_unused bad_range(struct zone *zone, struct page *page)
Nick Piggin's avatar
Nick Piggin committed
477 478 479 480 481
{
	return 0;
}
#endif

482
static void bad_page(struct page *page, const char *reason)
Linus Torvalds's avatar
Linus Torvalds committed
483
{
484 485 486 487 488 489 490 491 492 493 494 495 496 497
	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) {
498
			pr_alert(
499
			      "BUG: Bad page state: %lu messages suppressed\n",
500 501 502 503 504 505 506 507
				nr_unshown);
			nr_unshown = 0;
		}
		nr_shown = 0;
	}
	if (nr_shown++ == 0)
		resume = jiffies + 60 * HZ;

508
	pr_alert("BUG: Bad page state in process %s  pfn:%05lx\n",
509
		current->comm, page_to_pfn(page));
510
	dump_page(page, reason);
511

512
	print_modules();
Linus Torvalds's avatar
Linus Torvalds committed
513
	dump_stack();
514
out:
515
	/* Leave bad fields for debug, except PageBuddy could make trouble */
516
	page_mapcount_reset(page); /* remove PageBuddy */
517
	add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE);
Linus Torvalds's avatar
Linus Torvalds committed
518 519
}

520 521 522 523 524
static inline unsigned int order_to_pindex(int migratetype, int order)
{
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
	if (order > PAGE_ALLOC_COSTLY_ORDER) {
		VM_BUG_ON(order != pageblock_order);
525
		return NR_LOWORDER_PCP_LISTS;
526 527 528 529 530
	}
#else
	VM_BUG_ON(order > PAGE_ALLOC_COSTLY_ORDER);
#endif

531
	return (MIGRATE_PCPTYPES * order) + migratetype;
532 533 534 535 536 537 538
}

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

#ifdef CONFIG_TRANSPARENT_HUGEPAGE
539
	if (pindex == NR_LOWORDER_PCP_LISTS)
540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558
		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;
}

559 560
static inline void free_the_page(struct page *page, unsigned int order)
{
561 562
	if (pcp_allowed_order(order))		/* Via pcp? */
		free_unref_page(page, order);
563 564 565 566
	else
		__free_pages_ok(page, order, FPI_NONE);
}

Linus Torvalds's avatar
Linus Torvalds committed
567 568 569
/*
 * Higher-order pages are called "compound pages".  They are structured thusly:
 *
570
 * The first PAGE_SIZE page is called the "head page" and have PG_head set.
Linus Torvalds's avatar
Linus Torvalds committed
571
 *
572 573
 * 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
574
 *
575 576
 * The first tail page's ->compound_dtor describes how to destroy the
 * compound page.
Linus Torvalds's avatar
Linus Torvalds committed
577
 *
578
 * The first tail page's ->compound_order holds the order of allocation.
579
 * This usage means that zero-order pages may not be compound.
Linus Torvalds's avatar
Linus Torvalds committed
580
 */
581

582
void prep_compound_page(struct page *page, unsigned int order)
583 584 585 586 587
{
	int i;
	int nr_pages = 1 << order;

	__SetPageHead(page);
588 589
	for (i = 1; i < nr_pages; i++)
		prep_compound_tail(page, i);
590

591
	prep_compound_head(page, order);
592 593
}

594 595
void destroy_large_folio(struct folio *folio)
{
596
	enum compound_dtor_id dtor = folio->_folio_dtor;
597 598

	if (folio_test_hugetlb(folio)) {
599
		free_huge_folio(folio);
600 601
		return;
	}
602

603
	if (folio_test_transhuge(folio) && dtor == TRANSHUGE_PAGE_DTOR)
604
		folio_undo_large_rmappable(folio);
605

606 607
	mem_cgroup_uncharge(folio);
	free_the_page(&folio->page, folio_order(folio));
608 609
}

610
static inline void set_buddy_order(struct page *page, unsigned int order)
611
{
612
	set_page_private(page, order);
613
	__SetPageBuddy(page);
Linus Torvalds's avatar
Linus Torvalds committed
614 615
}

616 617 618 619 620
#ifdef CONFIG_COMPACTION
static inline struct capture_control *task_capc(struct zone *zone)
{
	struct capture_control *capc = current->capture_control;

621
	return unlikely(capc) &&
622 623
		!(current->flags & PF_KTHREAD) &&
		!capc->page &&
624
		capc->cc->zone == zone ? capc : NULL;
625 626 627 628 629 630 631 632 633 634 635 636 637 638 639
}

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
640
	 * Do not let lower order allocations pollute a movable pageblock.
641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665
	 * 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 */

666 667 668 669 670 671
/* 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];

672
	list_add(&page->buddy_list, &area->free_list[migratetype]);
673 674 675 676 677 678 679 680 681
	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];

682
	list_add_tail(&page->buddy_list, &area->free_list[migratetype]);
683 684 685
	area->nr_free++;
}

686 687 688 689 690
/*
 * 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).
 */
691 692 693 694 695
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];

696
	list_move_tail(&page->buddy_list, &area->free_list[migratetype]);
697 698 699 700 701
}

static inline void del_page_from_free_list(struct page *page, struct zone *zone,
					   unsigned int order)
{
702 703 704 705
	/* clear reported state and update reported page count */
	if (page_reported(page))
		__ClearPageReported(page);

706
	list_del(&page->buddy_list);
707 708 709 710 711
	__ClearPageBuddy(page);
	set_page_private(page, 0);
	zone->free_area[order].nr_free--;
}

712 713 714 715
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],
716
					struct page, buddy_list);
717 718
}

719 720 721 722 723 724 725 726 727 728 729 730
/*
 * 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)
{
731 732
	unsigned long higher_page_pfn;
	struct page *higher_page;
733

734
	if (order >= MAX_ORDER - 1)
735 736
		return false;

737 738
	higher_page_pfn = buddy_pfn & pfn;
	higher_page = page + (higher_page_pfn - pfn);
739

740 741
	return find_buddy_page_pfn(higher_page, higher_page_pfn, order + 1,
			NULL) != NULL;
742 743
}

Linus Torvalds's avatar
Linus Torvalds committed
744 745 746 747 748 749 750 751 752 753 754 755 756
/*
 * 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
757 758
 * 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
759
 * So when we are allocating or freeing one, we can derive the state of the
760 761
 * 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
762
 * If a block is freed, and its buddy is also free, then this
763
 * triggers coalescing into a block of larger size.
Linus Torvalds's avatar
Linus Torvalds committed
764
 *
765
 * -- nyc
Linus Torvalds's avatar
Linus Torvalds committed
766 767
 */

Nick Piggin's avatar
Nick Piggin committed
768
static inline void __free_one_page(struct page *page,
769
		unsigned long pfn,
770
		struct zone *zone, unsigned int order,
771
		int migratetype, fpi_t fpi_flags)
Linus Torvalds's avatar
Linus Torvalds committed
772
{
773
	struct capture_control *capc = task_capc(zone);
774
	unsigned long buddy_pfn = 0;
775 776 777
	unsigned long combined_pfn;
	struct page *buddy;
	bool to_tail;
778

779
	VM_BUG_ON(!zone_is_initialized(zone));
780
	VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);
Linus Torvalds's avatar
Linus Torvalds committed
781

782
	VM_BUG_ON(migratetype == -1);
783
	if (likely(!is_migrate_isolate(migratetype)))
784
		__mod_zone_freepage_state(zone, 1 << order, migratetype);
785

786
	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
787
	VM_BUG_ON_PAGE(bad_range(zone, page), page);
Linus Torvalds's avatar
Linus Torvalds committed
788

789
	while (order < MAX_ORDER) {
790 791 792 793 794
		if (compaction_capture(capc, page, order, migratetype)) {
			__mod_zone_freepage_state(zone, -(1 << order),
								migratetype);
			return;
		}
795

796 797
		buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn);
		if (!buddy)
798
			goto done_merging;
799 800 801 802 803 804 805 806

		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.
			 */
807
			int buddy_mt = get_pfnblock_migratetype(buddy, buddy_pfn);
808 809 810 811 812 813 814

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

815 816 817 818
		/*
		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
		 * merge with it and move up one order.
		 */
819
		if (page_is_guard(buddy))
820
			clear_page_guard(zone, buddy, order, migratetype);
821
		else
822
			del_page_from_free_list(buddy, zone, order);
823 824 825
		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
Linus Torvalds's avatar
Linus Torvalds committed
826 827
		order++;
	}
828 829

done_merging:
830
	set_buddy_order(page, order);
831

832 833 834
	if (fpi_flags & FPI_TO_TAIL)
		to_tail = true;
	else if (is_shuffle_order(order))
835
		to_tail = shuffle_pick_tail();
836
	else
837
		to_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);
838

839
	if (to_tail)
840
		add_to_free_list_tail(page, zone, order, migratetype);
841
	else
842
		add_to_free_list(page, zone, order, migratetype);
843 844

	/* Notify page reporting subsystem of freed page */
845
	if (!(fpi_flags & FPI_SKIP_REPORT_NOTIFY))
846
		page_reporting_notify_free(order);
Linus Torvalds's avatar
Linus Torvalds committed
847 848
}

849 850 851 852 853 854
/**
 * 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
 *
855 856
 * Return -ENOENT if the free page is changed, otherwise 0
 *
857 858 859 860 861
 * 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.
 */
862 863
int split_free_page(struct page *free_page,
			unsigned int order, unsigned long split_pfn_offset)
864 865 866 867 868 869
{
	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;
870 871
	int mt;
	int ret = 0;
872

873
	if (split_pfn_offset == 0)
874
		return ret;
875

876
	spin_lock_irqsave(&zone->lock, flags);
877 878 879 880 881 882

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

883
	mt = get_pfnblock_migratetype(free_page, free_page_pfn);
884 885 886
	if (likely(!is_migrate_isolate(mt)))
		__mod_zone_freepage_state(zone, -(1UL << order), mt);

887 888 889 890 891
	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);

892
		free_page_order = min_t(unsigned int,
893 894
					pfn ? __ffs(pfn) : order,
					__fls(split_pfn_offset));
895 896 897 898 899 900 901 902
		__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);
	}
903
out:
904
	spin_unlock_irqrestore(&zone->lock, flags);
905
	return ret;
906
}
907 908 909 910 911 912 913 914 915 916 917 918 919 920
/*
 * 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
921
			page->memcg_data |
922 923 924 925 926 927 928
#endif
			(page->flags & check_flags)))
		return false;

	return true;
}

929
static const char *page_bad_reason(struct page *page, unsigned long flags)
Linus Torvalds's avatar
Linus Torvalds committed
930
{
931
	const char *bad_reason = NULL;
932

933
	if (unlikely(atomic_read(&page->_mapcount) != -1))
934 935 936
		bad_reason = "nonzero mapcount";
	if (unlikely(page->mapping != NULL))
		bad_reason = "non-NULL mapping";
937
	if (unlikely(page_ref_count(page) != 0))
938
		bad_reason = "nonzero _refcount";
939 940 941 942 943
	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";
944
	}
945
#ifdef CONFIG_MEMCG
946
	if (unlikely(page->memcg_data))
947 948
		bad_reason = "page still charged to cgroup";
#endif
949 950 951
	return bad_reason;
}

952
static void free_page_is_bad_report(struct page *page)
953 954 955
{
	bad_page(page,
		 page_bad_reason(page, PAGE_FLAGS_CHECK_AT_FREE));
956 957
}

958
static inline bool free_page_is_bad(struct page *page)
959
{
960
	if (likely(page_expected_state(page, PAGE_FLAGS_CHECK_AT_FREE)))
961
		return false;
962 963

	/* Something has gone sideways, find it */
964 965
	free_page_is_bad_report(page);
	return true;
Linus Torvalds's avatar
Linus Torvalds committed
966 967
}

968 969 970 971 972
static inline bool is_check_pages_enabled(void)
{
	return static_branch_unlikely(&check_pages_enabled);
}

973
static int free_tail_page_prepare(struct page *head_page, struct page *page)
974
{
975
	struct folio *folio = (struct folio *)head_page;
976 977 978 979 980 981 982 983
	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);

984
	if (!is_check_pages_enabled()) {
985 986 987 988 989
		ret = 0;
		goto out;
	}
	switch (page - head_page) {
	case 1:
990
		/* the first tail page: these may be in place of ->mapping */
991 992
		if (unlikely(folio_entire_mapcount(folio))) {
			bad_page(page, "nonzero entire_mapcount");
993 994
			goto out;
		}
995 996
		if (unlikely(atomic_read(&folio->_nr_pages_mapped))) {
			bad_page(page, "nonzero nr_pages_mapped");
997 998
			goto out;
		}
999 1000
		if (unlikely(atomic_read(&folio->_pincount))) {
			bad_page(page, "nonzero pincount");
1001 1002
			goto out;
		}
1003 1004 1005 1006
		break;
	case 2:
		/*
		 * the second tail page: ->mapping is
1007
		 * deferred_list.next -- ignore value.
1008 1009 1010 1011
		 */
		break;
	default:
		if (page->mapping != TAIL_MAPPING) {
1012
			bad_page(page, "corrupted mapping in tail page");
1013 1014 1015 1016 1017
			goto out;
		}
		break;
	}
	if (unlikely(!PageTail(page))) {
1018
		bad_page(page, "PageTail not set");
1019 1020 1021
		goto out;
	}
	if (unlikely(compound_head(page) != head_page)) {
1022
		bad_page(page, "compound_head not consistent");
1023 1024 1025 1026 1027 1028 1029 1030 1031
		goto out;
	}
	ret = 0;
out:
	page->mapping = NULL;
	clear_compound_head(page);
	return ret;
}

1032 1033 1034
/*
 * Skip KASAN memory poisoning when either:
 *
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
 * 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,
1048
 *    see the call to kasan_unpoison_pages.
1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062
 *
 * 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)
{
1063 1064 1065 1066
	if (IS_ENABLED(CONFIG_KASAN_GENERIC))
		return deferred_pages_enabled();

	return page_kasan_tag(page) == 0xff;
1067 1068
}

1069
static void kernel_init_pages(struct page *page, int numpages)
1070 1071 1072
{
	int i;

1073 1074
	/* s390's use of memset() could override KASAN redzones. */
	kasan_disable_current();
1075 1076
	for (i = 0; i < numpages; i++)
		clear_highpage_kasan_tagged(page + i);
1077
	kasan_enable_current();
1078 1079
}

1080
static __always_inline bool free_pages_prepare(struct page *page,
1081
			unsigned int order, fpi_t fpi_flags)
1082
{
1083
	int bad = 0;
1084
	bool skip_kasan_poison = should_skip_kasan_poison(page, fpi_flags);
1085
	bool init = want_init_on_free();
1086 1087 1088

	VM_BUG_ON_PAGE(PageTail(page), page);

1089
	trace_mm_page_free(page, order);
1090
	kmsan_free_page(page, order);
1091

1092 1093 1094 1095 1096
	if (unlikely(PageHWPoison(page)) && !order) {
		/*
		 * Do not let hwpoison pages hit pcplists/buddy
		 * Untie memcg state and reset page's owner
		 */
1097
		if (memcg_kmem_online() && PageMemcgKmem(page))
1098 1099
			__memcg_kmem_uncharge_page(page, order);
		reset_page_owner(page, order);
Pasha Tatashin's avatar
Pasha Tatashin committed
1100
		page_table_check_free(page, order);
1101 1102 1103
		return false;
	}

1104 1105 1106 1107 1108 1109 1110 1111 1112
	/*
	 * 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);
1113

1114
		if (compound)
1115
			page[1].flags &= ~PAGE_FLAGS_SECOND;
1116 1117
		for (i = 1; i < (1 << order); i++) {
			if (compound)
1118
				bad += free_tail_page_prepare(page, page + i);
1119
			if (is_check_pages_enabled()) {
1120
				if (free_page_is_bad(page + i)) {
1121 1122 1123
					bad++;
					continue;
				}
1124 1125 1126 1127
			}
			(page + i)->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
		}
	}
1128
	if (PageMappingFlags(page))
1129
		page->mapping = NULL;
1130
	if (memcg_kmem_online() && PageMemcgKmem(page))
1131
		__memcg_kmem_uncharge_page(page, order);
1132
	if (is_check_pages_enabled()) {
1133 1134 1135 1136 1137
		if (free_page_is_bad(page))
			bad++;
		if (bad)
			return false;
	}
1138

1139 1140 1141
	page_cpupid_reset_last(page);
	page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
	reset_page_owner(page, order);
Pasha Tatashin's avatar
Pasha Tatashin committed
1142
	page_table_check_free(page, order);
1143 1144 1145

	if (!PageHighMem(page)) {
		debug_check_no_locks_freed(page_address(page),
1146
					   PAGE_SIZE << order);
1147
		debug_check_no_obj_freed(page_address(page),
1148
					   PAGE_SIZE << order);
1149
	}
1150

1151 1152
	kernel_poison_pages(page, 1 << order);

1153
	/*
1154
	 * As memory initialization might be integrated into KASAN,
1155
	 * KASAN poisoning and memory initialization code must be
1156 1157
	 * kept together to avoid discrepancies in behavior.
	 *
1158 1159 1160
	 * With hardware tag-based KASAN, memory tags must be set before the
	 * page becomes unavailable via debug_pagealloc or arch_free_page.
	 */
1161
	if (!skip_kasan_poison) {
1162
		kasan_poison_pages(page, order, init);
1163

1164 1165 1166 1167 1168
		/* Memory is already initialized if KASAN did it internally. */
		if (kasan_has_integrated_init())
			init = false;
	}
	if (init)
1169
		kernel_init_pages(page, 1 << order);
1170

1171 1172 1173 1174 1175 1176 1177
	/*
	 * 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);

1178
	debug_pagealloc_unmap_pages(page, 1 << order);
1179

1180 1181 1182
	return true;
}

Linus Torvalds's avatar
Linus Torvalds committed
1183
/*
1184
 * Frees a number of pages from the PCP lists
1185
 * Assumes all pages on list are in same zone.
1186
 * count is the number of pages to free.
Linus Torvalds's avatar
Linus Torvalds committed
1187
 */
1188
static void free_pcppages_bulk(struct zone *zone, int count,
1189 1190
					struct per_cpu_pages *pcp,
					int pindex)
Linus Torvalds's avatar
Linus Torvalds committed
1191
{
1192
	unsigned long flags;
1193
	unsigned int order;
1194
	bool isolated_pageblocks;
1195
	struct page *page;
1196

1197 1198 1199 1200 1201
	/*
	 * Ensure proper count is passed which otherwise would stuck in the
	 * below while (list_empty(list)) loop.
	 */
	count = min(pcp->count, count);
1202 1203 1204 1205

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

1206
	spin_lock_irqsave(&zone->lock, flags);
1207 1208
	isolated_pageblocks = has_isolate_pageblock(zone);

1209
	while (count > 0) {
1210
		struct list_head *list;
1211
		int nr_pages;
1212

1213
		/* Remove pages from lists in a round-robin fashion. */
1214
		do {
1215 1216
			if (++pindex > NR_PCP_LISTS - 1)
				pindex = 0;
1217
			list = &pcp->lists[pindex];
1218
		} while (list_empty(list));
Nick Piggin's avatar
Nick Piggin committed
1219

1220
		order = pindex_to_order(pindex);
1221
		nr_pages = 1 << order;
1222
		do {
1223 1224
			int mt;

1225
			page = list_last_entry(list, struct page, pcp_list);
1226 1227
			mt = get_pcppage_migratetype(page);

1228
			/* must delete to avoid corrupting pcp list */
1229
			list_del(&page->pcp_list);
1230 1231
			count -= nr_pages;
			pcp->count -= nr_pages;
1232

1233 1234 1235 1236 1237
			/* 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);
1238

1239 1240 1241
			__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));
1242
	}
1243

1244
	spin_unlock_irqrestore(&zone->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
1245 1246
}

1247 1248
static void free_one_page(struct zone *zone,
				struct page *page, unsigned long pfn,
1249
				unsigned int order,
1250
				int migratetype, fpi_t fpi_flags)
Linus Torvalds's avatar
Linus Torvalds committed
1251
{
1252 1253 1254
	unsigned long flags;

	spin_lock_irqsave(&zone->lock, flags);
1255 1256 1257 1258
	if (unlikely(has_isolate_pageblock(zone) ||
		is_migrate_isolate(migratetype))) {
		migratetype = get_pfnblock_migratetype(page, pfn);
	}
1259
	__free_one_page(page, pfn, zone, order, migratetype, fpi_flags);
1260
	spin_unlock_irqrestore(&zone->lock, flags);
Nick Piggin's avatar
Nick Piggin committed
1261 1262
}

1263 1264
static void __free_pages_ok(struct page *page, unsigned int order,
			    fpi_t fpi_flags)
1265
{
1266
	unsigned long flags;
1267
	int migratetype;
1268
	unsigned long pfn = page_to_pfn(page);
1269
	struct zone *zone = page_zone(page);
1270

1271
	if (!free_pages_prepare(page, order, fpi_flags))
1272 1273
		return;

1274 1275 1276 1277 1278
	/*
	 * 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.
	 */
1279
	migratetype = get_pfnblock_migratetype(page, pfn);
1280

1281 1282 1283 1284 1285 1286 1287
	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);
1288

1289
	__count_vm_events(PGFREE, 1 << order);
Linus Torvalds's avatar
Linus Torvalds committed
1290 1291
}

1292
void __free_pages_core(struct page *page, unsigned int order)
1293
{
1294
	unsigned int nr_pages = 1 << order;
1295
	struct page *p = page;
1296
	unsigned int loop;
1297

1298 1299 1300 1301 1302
	/*
	 * 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.
	 */
1303 1304 1305
	prefetchw(p);
	for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
		prefetchw(p + 1);
1306 1307
		__ClearPageReserved(p);
		set_page_count(p, 0);
1308
	}
1309 1310
	__ClearPageReserved(p);
	set_page_count(p, 0);
1311

1312
	atomic_long_add(nr_pages, &page_zone(page)->managed_pages);
1313

1314 1315 1316 1317 1318 1319 1320
	if (page_contains_unaccepted(page, order)) {
		if (order == MAX_ORDER && __free_unaccepted(page))
			return;

		accept_page(page, order);
	}

1321 1322 1323 1324
	/*
	 * Bypass PCP and place fresh pages right to the tail, primarily
	 * relevant for memory onlining.
	 */
1325
	__free_pages_ok(page, order, FPI_TO_TAIL);
1326 1327
}

1328 1329 1330
/*
 * 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
1331
 * with the migration of free compaction scanner.
1332 1333 1334 1335 1336 1337 1338 1339 1340 1341
 *
 * 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.
1342 1343 1344 1345 1346 1347 1348 1349 1350
 *
 * 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.
1351 1352 1353 1354 1355 1356 1357 1358 1359 1360
 */
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--;

1361
	if (!pfn_valid(end_pfn))
1362 1363
		return NULL;

1364 1365 1366
	start_page = pfn_to_online_page(start_pfn);
	if (!start_page)
		return NULL;
1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379

	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;
}

1380
/*
1381 1382 1383 1384 1385 1386 1387 1388 1389 1390
 * 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.
1391
 *
1392
 * -- nyc
1393
 */
1394 1395
static inline void expand(struct zone *zone, struct page *page,
	int low, int high, int migratetype)
1396
{
1397
	unsigned long size = 1 << high;
1398

1399 1400 1401 1402
	while (high > low) {
		high--;
		size >>= 1;
		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);
1403

1404 1405 1406 1407 1408 1409 1410
		/*
		 * 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))
1411
			continue;
1412 1413 1414

		add_to_free_list(&page[size], zone, high, migratetype);
		set_buddy_order(&page[size], high);
1415 1416 1417
	}
}

1418
static void check_new_page_bad(struct page *page)
1419
{
1420 1421 1422 1423
	if (unlikely(page->flags & __PG_HWPOISON)) {
		/* Don't complain about hwpoisoned pages */
		page_mapcount_reset(page); /* remove PageBuddy */
		return;
1424 1425
	}

1426 1427
	bad_page(page,
		 page_bad_reason(page, PAGE_FLAGS_CHECK_AT_PREP));
1428 1429 1430
}

/*
1431
 * This page is about to be returned from the page allocator
1432
 */
1433
static int check_new_page(struct page *page)
1434
{
1435 1436 1437
	if (likely(page_expected_state(page,
				PAGE_FLAGS_CHECK_AT_PREP|__PG_HWPOISON)))
		return 0;
1438

1439 1440 1441
	check_new_page_bad(page);
	return 1;
}
1442

1443 1444 1445 1446 1447
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;
1448

1449
			if (check_new_page(p))
1450
				return true;
1451 1452 1453
		}
	}

1454
	return false;
1455 1456
}

1457
static inline bool should_skip_kasan_unpoison(gfp_t flags)
1458
{
1459 1460 1461 1462
	/* Don't skip if a software KASAN mode is enabled. */
	if (IS_ENABLED(CONFIG_KASAN_GENERIC) ||
	    IS_ENABLED(CONFIG_KASAN_SW_TAGS))
		return false;
1463

1464 1465 1466
	/* Skip, if hardware tag-based KASAN is not enabled. */
	if (!kasan_hw_tags_enabled())
		return true;
1467 1468

	/*
1469 1470
	 * With hardware tag-based KASAN enabled, skip if this has been
	 * requested via __GFP_SKIP_KASAN.
1471
	 */
1472
	return flags & __GFP_SKIP_KASAN;
1473 1474
}

1475
static inline bool should_skip_init(gfp_t flags)
1476
{
1477 1478 1479 1480 1481 1482
	/* 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);
1483 1484
}

1485 1486
inline void post_alloc_hook(struct page *page, unsigned int order,
				gfp_t gfp_flags)
1487
{
1488 1489 1490 1491 1492 1493 1494
	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);
1495

1496 1497
	arch_alloc_page(page, order);
	debug_pagealloc_map_pages(page, 1 << order);
1498

1499
	/*
1500 1501 1502
	 * 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.
1503
	 */
1504
	kernel_unpoison_pages(page, 1 << order);
1505

1506 1507
	/*
	 * As memory initialization might be integrated into KASAN,
1508
	 * KASAN unpoisoning and memory initializion code must be
1509 1510
	 * kept together to avoid discrepancies in behavior.
	 */
1511 1512

	/*
1513 1514
	 * If memory tags should be zeroed
	 * (which happens only when memory should be initialized as well).
1515
	 */
1516
	if (zero_tags) {
1517
		/* Initialize both memory and memory tags. */
1518 1519 1520
		for (i = 0; i != 1 << order; ++i)
			tag_clear_highpage(page + i);

1521
		/* Take note that memory was initialized by the loop above. */
1522 1523
		init = false;
	}
1524 1525 1526 1527 1528 1529 1530 1531 1532 1533
	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.
		 */
1534 1535
		for (i = 0; i != 1 << order; ++i)
			page_kasan_tag_reset(page + i);
1536
	}
1537
	/* If memory is still not initialized, initialize it now. */
1538
	if (init)
1539
		kernel_init_pages(page, 1 << order);
1540 1541

	set_page_owner(page, order, gfp_flags);
Pasha Tatashin's avatar
Pasha Tatashin committed
1542
	page_table_check_alloc(page, order);
1543 1544
}

1545
static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags,
1546
							unsigned int alloc_flags)
1547
{
1548
	post_alloc_hook(page, order, gfp_flags);
1549 1550 1551 1552

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

1553
	/*
1554
	 * page is set pfmemalloc when ALLOC_NO_WATERMARKS was necessary to
1555 1556 1557 1558
	 * 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.
	 */
1559 1560 1561 1562
	if (alloc_flags & ALLOC_NO_WATERMARKS)
		set_page_pfmemalloc(page);
	else
		clear_page_pfmemalloc(page);
Linus Torvalds's avatar
Linus Torvalds committed
1563 1564
}

1565 1566 1567 1568
/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
1569
static __always_inline
1570
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
1571 1572 1573
						int migratetype)
{
	unsigned int current_order;
1574
	struct free_area *area;
1575 1576 1577
	struct page *page;

	/* Find a page of the appropriate size in the preferred list */
1578
	for (current_order = order; current_order <= MAX_ORDER; ++current_order) {
1579
		area = &(zone->free_area[current_order]);
1580
		page = get_page_from_free_area(area, migratetype);
1581 1582
		if (!page)
			continue;
1583 1584
		del_page_from_free_list(page, zone, current_order);
		expand(zone, page, order, current_order, migratetype);
1585
		set_pcppage_migratetype(page, migratetype);
1586 1587 1588
		trace_mm_page_alloc_zone_locked(page, order, migratetype,
				pcp_allowed_order(order) &&
				migratetype < MIGRATE_PCPTYPES);
1589 1590 1591 1592 1593 1594 1595
		return page;
	}

	return NULL;
}


1596 1597 1598
/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
1599 1600
 *
 * The other migratetypes do not have fallbacks.
1601
 */
1602 1603 1604 1605
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   },
1606 1607
};

1608
#ifdef CONFIG_CMA
1609
static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
1610 1611 1612 1613 1614 1615 1616 1617 1618
					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

1619
/*
1620
 * Move the free pages in a range to the freelist tail of the requested type.
1621
 * Note that start_page and end_pages are not aligned on a pageblock
1622 1623
 * boundary. If alignment is required, use move_freepages_block()
 */
1624
static int move_freepages(struct zone *zone,
1625
			  unsigned long start_pfn, unsigned long end_pfn,
1626
			  int migratetype, int *num_movable)
1627 1628
{
	struct page *page;
1629
	unsigned long pfn;
1630
	unsigned int order;
1631
	int pages_moved = 0;
1632

1633 1634
	for (pfn = start_pfn; pfn <= end_pfn;) {
		page = pfn_to_page(pfn);
1635
		if (!PageBuddy(page)) {
1636 1637 1638 1639 1640 1641 1642 1643
			/*
			 * 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)++;
1644
			pfn++;
1645 1646 1647
			continue;
		}

1648 1649 1650 1651
		/* 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);

1652
		order = buddy_order(page);
1653
		move_to_free_list(page, zone, order, migratetype);
1654
		pfn += 1 << order;
1655
		pages_moved += 1 << order;
1656 1657
	}

1658
	return pages_moved;
1659 1660
}

1661
int move_freepages_block(struct zone *zone, struct page *page,
1662
				int migratetype, int *num_movable)
1663
{
1664
	unsigned long start_pfn, end_pfn, pfn;
1665

1666 1667 1668
	if (num_movable)
		*num_movable = 0;

1669
	pfn = page_to_pfn(page);
1670 1671
	start_pfn = pageblock_start_pfn(pfn);
	end_pfn = pageblock_end_pfn(pfn) - 1;
1672 1673

	/* Do not cross zone boundaries */
1674
	if (!zone_spans_pfn(zone, start_pfn))
1675
		start_pfn = pfn;
1676
	if (!zone_spans_pfn(zone, end_pfn))
1677 1678
		return 0;

1679
	return move_freepages(zone, start_pfn, end_pfn, migratetype,
1680
								num_movable);
1681 1682
}

1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693
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;
	}
}

1694
/*
1695 1696 1697 1698 1699 1700 1701 1702 1703 1704
 * 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.
1705
 */
1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726
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;
}

1727
static inline bool boost_watermark(struct zone *zone)
1728 1729 1730 1731
{
	unsigned long max_boost;

	if (!watermark_boost_factor)
1732
		return false;
1733 1734 1735 1736 1737 1738 1739
	/*
	 * 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))
1740
		return false;
1741 1742 1743

	max_boost = mult_frac(zone->_watermark[WMARK_HIGH],
			watermark_boost_factor, 10000);
1744 1745 1746 1747 1748 1749 1750 1751 1752 1753

	/*
	 * 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)
1754
		return false;
1755

1756 1757 1758 1759
	max_boost = max(pageblock_nr_pages, max_boost);

	zone->watermark_boost = min(zone->watermark_boost + pageblock_nr_pages,
		max_boost);
1760 1761

	return true;
1762 1763
}

1764 1765 1766
/*
 * This function implements actual steal behaviour. If order is large enough,
 * we can steal whole pageblock. If not, we first move freepages in this
1767 1768 1769 1770
 * 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.
1771 1772
 */
static void steal_suitable_fallback(struct zone *zone, struct page *page,
1773
		unsigned int alloc_flags, int start_type, bool whole_block)
1774
{
1775
	unsigned int current_order = buddy_order(page);
1776 1777 1778 1779
	int free_pages, movable_pages, alike_pages;
	int old_block_type;

	old_block_type = get_pageblock_migratetype(page);
1780

1781 1782 1783 1784
	/*
	 * This can happen due to races and we want to prevent broken
	 * highatomic accounting.
	 */
1785
	if (is_migrate_highatomic(old_block_type))
1786 1787
		goto single_page;

1788 1789 1790
	/* Take ownership for orders >= pageblock_order */
	if (current_order >= pageblock_order) {
		change_pageblock_range(page, current_order, start_type);
1791
		goto single_page;
1792 1793
	}

1794 1795 1796 1797 1798
	/*
	 * 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.
	 */
1799
	if (boost_watermark(zone) && (alloc_flags & ALLOC_KSWAPD))
1800
		set_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
1801

1802 1803 1804 1805
	/* We are not allowed to try stealing from the whole block */
	if (!whole_block)
		goto single_page;

1806 1807
	free_pages = move_freepages_block(zone, page, start_type,
						&movable_pages);
1808 1809 1810 1811
	/* moving whole block can fail due to zone boundary conditions */
	if (!free_pages)
		goto single_page;

1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834
	/*
	 * 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;
	}
	/*
	 * If a sufficient number of pages in the block are either free or of
1835
	 * compatible migratability as our allocation, claim the whole block.
1836 1837
	 */
	if (free_pages + alike_pages >= (1 << (pageblock_order-1)) ||
1838 1839
			page_group_by_mobility_disabled)
		set_pageblock_migratetype(page, start_type);
1840 1841 1842 1843

	return;

single_page:
1844
	move_to_free_list(page, zone, current_order, start_type);
1845 1846
}

1847 1848 1849 1850 1851 1852 1853 1854
/*
 * 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)
1855 1856 1857 1858 1859 1860 1861 1862
{
	int i;
	int fallback_mt;

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

	*can_steal = false;
1863
	for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
1864
		fallback_mt = fallbacks[migratetype][i];
1865
		if (free_area_empty(area, fallback_mt))
1866
			continue;
1867

1868 1869 1870
		if (can_steal_fallback(order, migratetype))
			*can_steal = true;

1871 1872 1873 1874 1875
		if (!only_stealable)
			return fallback_mt;

		if (*can_steal)
			return fallback_mt;
1876
	}
1877 1878

	return -1;
1879 1880
}

1881 1882 1883 1884
/*
 * 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
 */
1885
static void reserve_highatomic_pageblock(struct page *page, struct zone *zone)
1886 1887 1888 1889 1890 1891 1892 1893
{
	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.
	 */
1894
	max_managed = (zone_managed_pages(zone) / 100) + pageblock_nr_pages;
1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905
	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);
1906 1907
	/* Only reserve normal pageblocks (i.e., they can merge with others) */
	if (migratetype_is_mergeable(mt)) {
1908 1909
		zone->nr_reserved_highatomic += pageblock_nr_pages;
		set_pageblock_migratetype(page, MIGRATE_HIGHATOMIC);
1910
		move_freepages_block(zone, page, MIGRATE_HIGHATOMIC, NULL);
1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921
	}

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.
1922 1923 1924
 *
 * If @force is true, try to unreserve a pageblock even though highatomic
 * pageblock is exhausted.
1925
 */
1926 1927
static bool unreserve_highatomic_pageblock(const struct alloc_context *ac,
						bool force)
1928 1929 1930 1931 1932 1933 1934
{
	struct zonelist *zonelist = ac->zonelist;
	unsigned long flags;
	struct zoneref *z;
	struct zone *zone;
	struct page *page;
	int order;
1935
	bool ret;
1936

1937
	for_each_zone_zonelist_nodemask(zone, z, zonelist, ac->highest_zoneidx,
1938
								ac->nodemask) {
1939 1940 1941 1942 1943 1944
		/*
		 * Preserve at least one pageblock unless memory pressure
		 * is really high.
		 */
		if (!force && zone->nr_reserved_highatomic <=
					pageblock_nr_pages)
1945 1946 1947
			continue;

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

1951
			page = get_page_from_free_area(area, MIGRATE_HIGHATOMIC);
1952
			if (!page)
1953 1954 1955
				continue;

			/*
1956 1957
			 * 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
1958
			 * in this loop although we changed the pageblock type
1959 1960
			 * from highatomic to ac->migratetype. So we should
			 * adjust the count once.
1961
			 */
1962
			if (is_migrate_highatomic_page(page)) {
1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973
				/*
				 * 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);
			}
1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984

			/*
			 * 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);
1985 1986
			ret = move_freepages_block(zone, page, ac->migratetype,
									NULL);
1987 1988 1989 1990
			if (ret) {
				spin_unlock_irqrestore(&zone->lock, flags);
				return ret;
			}
1991 1992 1993
		}
		spin_unlock_irqrestore(&zone->lock, flags);
	}
1994 1995

	return false;
1996 1997
}

1998 1999 2000 2001 2002
/*
 * 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.
2003 2004 2005 2006
 *
 * 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.
2007
 */
2008
static __always_inline bool
2009 2010
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype,
						unsigned int alloc_flags)
2011
{
2012
	struct free_area *area;
2013
	int current_order;
2014
	int min_order = order;
2015
	struct page *page;
2016 2017
	int fallback_mt;
	bool can_steal;
2018

2019 2020 2021 2022 2023
	/*
	 * 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.
	 */
2024
	if (order < pageblock_order && alloc_flags & ALLOC_NOFRAGMENT)
2025 2026
		min_order = pageblock_order;

2027 2028 2029 2030 2031
	/*
	 * 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.
	 */
2032
	for (current_order = MAX_ORDER; current_order >= min_order;
2033
				--current_order) {
2034 2035
		area = &(zone->free_area[current_order]);
		fallback_mt = find_suitable_fallback(area, current_order,
2036
				start_migratetype, false, &can_steal);
2037 2038
		if (fallback_mt == -1)
			continue;
2039

2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050
		/*
		 * 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;
2051

2052 2053
		goto do_steal;
	}
2054

2055
	return false;
2056

2057
find_smallest:
2058
	for (current_order = order; current_order <= MAX_ORDER;
2059 2060 2061 2062 2063 2064
							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;
2065 2066
	}

2067 2068 2069 2070
	/*
	 * This should not happen - we already found a suitable fallback
	 * when looking for the largest page.
	 */
2071
	VM_BUG_ON(current_order > MAX_ORDER);
2072 2073

do_steal:
2074
	page = get_page_from_free_area(area, fallback_mt);
2075

2076 2077
	steal_suitable_fallback(zone, page, alloc_flags, start_migratetype,
								can_steal);
2078 2079 2080 2081 2082 2083

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

	return true;

2084 2085
}

2086
/*
Linus Torvalds's avatar
Linus Torvalds committed
2087 2088 2089
 * Do the hard work of removing an element from the buddy allocator.
 * Call me with the zone->lock already held.
 */
2090
static __always_inline struct page *
2091 2092
__rmqueue(struct zone *zone, unsigned int order, int migratetype,
						unsigned int alloc_flags)
Linus Torvalds's avatar
Linus Torvalds committed
2093 2094 2095
{
	struct page *page;

2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106
	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)
2107
				return page;
2108
		}
2109
	}
2110
retry:
2111
	page = __rmqueue_smallest(zone, order, migratetype);
2112
	if (unlikely(!page)) {
2113
		if (alloc_flags & ALLOC_CMA)
2114 2115
			page = __rmqueue_cma_fallback(zone, order);

2116 2117
		if (!page && __rmqueue_fallback(zone, order, migratetype,
								alloc_flags))
2118
			goto retry;
2119
	}
2120
	return page;
Linus Torvalds's avatar
Linus Torvalds committed
2121 2122
}

2123
/*
Linus Torvalds's avatar
Linus Torvalds committed
2124 2125 2126 2127
 * 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.
 */
2128
static int rmqueue_bulk(struct zone *zone, unsigned int order,
2129
			unsigned long count, struct list_head *list,
2130
			int migratetype, unsigned int alloc_flags)
Linus Torvalds's avatar
Linus Torvalds committed
2131
{
2132
	unsigned long flags;
2133
	int i;
2134

2135
	spin_lock_irqsave(&zone->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
2136
	for (i = 0; i < count; ++i) {
2137 2138
		struct page *page = __rmqueue(zone, order, migratetype,
								alloc_flags);
2139
		if (unlikely(page == NULL))
Linus Torvalds's avatar
Linus Torvalds committed
2140
			break;
2141 2142

		/*
2143 2144 2145 2146 2147 2148 2149 2150
		 * 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.
2151
		 */
2152
		list_add_tail(&page->pcp_list, list);
2153
		if (is_migrate_cma(get_pcppage_migratetype(page)))
2154 2155
			__mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
					      -(1 << order));
Linus Torvalds's avatar
Linus Torvalds committed
2156
	}
2157

2158
	__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
2159
	spin_unlock_irqrestore(&zone->lock, flags);
2160

2161
	return i;
Linus Torvalds's avatar
Linus Torvalds committed
2162 2163
}

2164
#ifdef CONFIG_NUMA
2165
/*
2166 2167 2168
 * Called from the vmstat counter updater to drain pagesets of this
 * currently executing processor on remote nodes after they have
 * expired.
2169
 */
2170
void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
2171
{
2172
	int to_drain, batch;
2173

2174
	batch = READ_ONCE(pcp->batch);
2175
	to_drain = min(pcp->count, batch);
2176
	if (to_drain > 0) {
2177
		spin_lock(&pcp->lock);
2178
		free_pcppages_bulk(zone, to_drain, pcp, 0);
2179
		spin_unlock(&pcp->lock);
2180
	}
2181 2182 2183
}
#endif

2184
/*
2185
 * Drain pcplists of the indicated processor and zone.
2186
 */
2187
static void drain_pages_zone(unsigned int cpu, struct zone *zone)
Linus Torvalds's avatar
Linus Torvalds committed
2188
{
2189
	struct per_cpu_pages *pcp;
Linus Torvalds's avatar
Linus Torvalds committed
2190

2191
	pcp = per_cpu_ptr(zone->per_cpu_pageset, cpu);
2192
	if (pcp->count) {
2193
		spin_lock(&pcp->lock);
2194
		free_pcppages_bulk(zone, pcp->count, pcp, 0);
2195
		spin_unlock(&pcp->lock);
2196
	}
2197
}
2198

2199 2200 2201 2202 2203 2204 2205 2206 2207
/*
 * 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
2208 2209 2210
	}
}

2211 2212 2213
/*
 * Spill all of this CPU's per-cpu pages back into the buddy allocator.
 */
2214
void drain_local_pages(struct zone *zone)
2215
{
2216 2217 2218 2219 2220 2221
	int cpu = smp_processor_id();

	if (zone)
		drain_pages_zone(cpu, zone);
	else
		drain_pages(cpu);
2222 2223 2224
}

/*
2225 2226
 * The implementation of drain_all_pages(), exposing an extra parameter to
 * drain on all cpus.
2227
 *
2228 2229 2230 2231 2232
 * 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.
2233
 */
2234
static void __drain_all_pages(struct zone *zone, bool force_all_cpus)
2235
{
2236 2237 2238
	int cpu;

	/*
Zhen Lei's avatar
Zhen Lei committed
2239
	 * Allocate in the BSS so we won't require allocation in
2240 2241 2242 2243
	 * direct reclaim path for CONFIG_CPUMASK_OFFSTACK=y
	 */
	static cpumask_t cpus_with_pcps;

2244 2245 2246 2247 2248 2249 2250 2251 2252 2253
	/*
	 * 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);
	}
2254

2255 2256 2257 2258 2259 2260 2261
	/*
	 * 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) {
2262
		struct per_cpu_pages *pcp;
2263
		struct zone *z;
2264
		bool has_pcps = false;
2265

2266 2267 2268 2269 2270 2271 2272
		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) {
2273 2274
			pcp = per_cpu_ptr(zone->per_cpu_pageset, cpu);
			if (pcp->count)
2275
				has_pcps = true;
2276 2277
		} else {
			for_each_populated_zone(z) {
2278 2279
				pcp = per_cpu_ptr(z->per_cpu_pageset, cpu);
				if (pcp->count) {
2280 2281 2282
					has_pcps = true;
					break;
				}
2283 2284
			}
		}
2285

2286 2287 2288 2289 2290
		if (has_pcps)
			cpumask_set_cpu(cpu, &cpus_with_pcps);
		else
			cpumask_clear_cpu(cpu, &cpus_with_pcps);
	}
2291

2292
	for_each_cpu(cpu, &cpus_with_pcps) {
2293 2294 2295 2296
		if (zone)
			drain_pages_zone(cpu, zone);
		else
			drain_pages(cpu);
2297
	}
2298 2299

	mutex_unlock(&pcpu_drain_mutex);
2300 2301
}

2302 2303 2304 2305 2306 2307 2308 2309 2310 2311
/*
 * 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);
}

2312 2313
static bool free_unref_page_prepare(struct page *page, unsigned long pfn,
							unsigned int order)
Linus Torvalds's avatar
Linus Torvalds committed
2314
{
2315
	int migratetype;
Linus Torvalds's avatar
Linus Torvalds committed
2316

2317
	if (!free_pages_prepare(page, order, FPI_NONE))
2318
		return false;
2319

2320
	migratetype = get_pfnblock_migratetype(page, pfn);
2321
	set_pcppage_migratetype(page, migratetype);
2322 2323 2324
	return true;
}

2325
static int nr_pcp_free(struct per_cpu_pages *pcp, int high, bool free_high)
2326 2327
{
	int min_nr_free, max_nr_free;
2328
	int batch = READ_ONCE(pcp->batch);
2329

2330 2331 2332 2333
	/* Free everything if batch freeing high-order pages. */
	if (unlikely(free_high))
		return pcp->count;

2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353
	/* 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;
}

2354 2355
static int nr_pcp_high(struct per_cpu_pages *pcp, struct zone *zone,
		       bool free_high)
2356 2357 2358
{
	int high = READ_ONCE(pcp->high);

2359
	if (unlikely(!high || free_high))
2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371
		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);
}

2372 2373
static void free_unref_page_commit(struct zone *zone, struct per_cpu_pages *pcp,
				   struct page *page, int migratetype,
2374
				   unsigned int order)
2375
{
2376
	int high;
2377
	int pindex;
2378
	bool free_high;
2379

2380
	__count_vm_events(PGFREE, 1 << order);
2381
	pindex = order_to_pindex(migratetype, order);
2382
	list_add(&page->pcp_list, &pcp->lists[pindex]);
2383
	pcp->count += 1 << order;
2384 2385 2386 2387 2388 2389 2390 2391 2392 2393

	/*
	 * 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);
2394
	if (pcp->count >= high) {
2395
		free_pcppages_bulk(zone, nr_pcp_free(pcp, high, free_high), pcp, pindex);
2396
	}
2397
}
2398

2399
/*
2400
 * Free a pcp page
2401
 */
2402
void free_unref_page(struct page *page, unsigned int order)
2403
{
2404 2405 2406
	unsigned long __maybe_unused UP_flags;
	struct per_cpu_pages *pcp;
	struct zone *zone;
2407
	unsigned long pfn = page_to_pfn(page);
2408
	int migratetype;
2409

2410
	if (!free_unref_page_prepare(page, pfn, order))
2411
		return;
2412

2413 2414
	/*
	 * We only track unmovable, reclaimable and movable on pcp lists.
2415
	 * Place ISOLATE pages on the isolated list because they are being
2416
	 * offlined but treat HIGHATOMIC as movable pages so we can get those
2417 2418 2419
	 * areas back if necessary. Otherwise, we may have to free
	 * excessively into the page allocator
	 */
2420 2421
	migratetype = get_pcppage_migratetype(page);
	if (unlikely(migratetype >= MIGRATE_PCPTYPES)) {
2422
		if (unlikely(is_migrate_isolate(migratetype))) {
2423
			free_one_page(page_zone(page), page, pfn, order, migratetype, FPI_NONE);
2424
			return;
2425 2426 2427 2428
		}
		migratetype = MIGRATE_MOVABLE;
	}

2429 2430
	zone = page_zone(page);
	pcp_trylock_prepare(UP_flags);
2431
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
2432
	if (pcp) {
2433
		free_unref_page_commit(zone, pcp, page, migratetype, order);
2434
		pcp_spin_unlock(pcp);
2435 2436 2437 2438
	} else {
		free_one_page(zone, page, pfn, order, migratetype, FPI_NONE);
	}
	pcp_trylock_finish(UP_flags);
Linus Torvalds's avatar
Linus Torvalds committed
2439 2440
}

2441 2442 2443
/*
 * Free a list of 0-order pages
 */
2444
void free_unref_page_list(struct list_head *list)
2445
{
2446
	unsigned long __maybe_unused UP_flags;
2447
	struct page *page, *next;
2448 2449
	struct per_cpu_pages *pcp = NULL;
	struct zone *locked_zone = NULL;
2450
	int batch_count = 0;
2451
	int migratetype;
2452 2453 2454

	/* Prepare pages for freeing */
	list_for_each_entry_safe(page, next, list, lru) {
2455
		unsigned long pfn = page_to_pfn(page);
2456
		if (!free_unref_page_prepare(page, pfn, 0)) {
2457
			list_del(&page->lru);
2458 2459
			continue;
		}
2460 2461 2462 2463 2464 2465

		/*
		 * Free isolated pages directly to the allocator, see
		 * comment in free_unref_page.
		 */
		migratetype = get_pcppage_migratetype(page);
2466 2467 2468 2469
		if (unlikely(is_migrate_isolate(migratetype))) {
			list_del(&page->lru);
			free_one_page(page_zone(page), page, pfn, 0, migratetype, FPI_NONE);
			continue;
2470
		}
2471
	}
2472 2473

	list_for_each_entry_safe(page, next, list, lru) {
2474 2475
		struct zone *zone = page_zone(page);

2476
		list_del(&page->lru);
2477
		migratetype = get_pcppage_migratetype(page);
2478

2479 2480 2481 2482 2483 2484
		/*
		 * 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) {
2485 2486 2487 2488
			if (pcp) {
				pcp_spin_unlock(pcp);
				pcp_trylock_finish(UP_flags);
			}
2489

2490 2491
			batch_count = 0;

2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504
			/*
			 * 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;
			}
2505 2506 2507
			locked_zone = zone;
		}

2508 2509 2510 2511 2512 2513 2514
		/*
		 * Non-isolated types over MIGRATE_PCPTYPES get added
		 * to the MIGRATE_MOVABLE pcp list.
		 */
		if (unlikely(migratetype >= MIGRATE_PCPTYPES))
			migratetype = MIGRATE_MOVABLE;

2515
		trace_mm_page_free_batched(page);
2516
		free_unref_page_commit(zone, pcp, page, migratetype, 0);
2517
		batch_count++;
2518
	}
2519

2520 2521 2522 2523
	if (pcp) {
		pcp_spin_unlock(pcp);
		pcp_trylock_finish(UP_flags);
	}
2524 2525
}

2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537
/*
 * 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;

2538 2539
	VM_BUG_ON_PAGE(PageCompound(page), page);
	VM_BUG_ON_PAGE(!page_count(page), page);
2540

2541
	for (i = 1; i < (1 << order); i++)
2542
		set_page_refcounted(page + i);
2543
	split_page_owner(page, 1 << order);
2544
	split_page_memcg(page, 1 << order);
2545
}
K. Y. Srinivasan's avatar
K. Y. Srinivasan committed
2546
EXPORT_SYMBOL_GPL(split_page);
2547

2548
int __isolate_free_page(struct page *page, unsigned int order)
2549
{
2550 2551
	struct zone *zone = page_zone(page);
	int mt = get_pageblock_migratetype(page);
2552

2553
	if (!is_migrate_isolate(mt)) {
2554
		unsigned long watermark;
2555 2556 2557 2558 2559 2560
		/*
		 * 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.
		 */
2561
		watermark = zone->_watermark[WMARK_MIN] + (1UL << order);
2562
		if (!zone_watermark_ok(zone, 0, watermark, 0, ALLOC_CMA))
2563 2564
			return 0;

2565
		__mod_zone_freepage_state(zone, -(1UL << order), mt);
2566
	}
2567

2568
	del_page_from_free_list(page, zone, order);
2569

2570 2571 2572 2573
	/*
	 * Set the pageblock if the isolated page is at least half of a
	 * pageblock
	 */
2574 2575
	if (order >= pageblock_order - 1) {
		struct page *endpage = page + (1 << order) - 1;
2576 2577
		for (; page < endpage; page += pageblock_nr_pages) {
			int mt = get_pageblock_migratetype(page);
2578 2579 2580 2581 2582
			/*
			 * Only change normal pageblocks (i.e., they can merge
			 * with others)
			 */
			if (migratetype_is_mergeable(mt))
2583 2584 2585
				set_pageblock_migratetype(page,
							  MIGRATE_MOVABLE);
		}
2586 2587
	}

2588
	return 1UL << order;
2589 2590
}

2591 2592 2593 2594
/**
 * __putback_isolated_page - Return a now-isolated page back where we got it
 * @page: Page that was isolated
 * @order: Order of the isolated page
2595
 * @mt: The page's pageblock's migratetype
2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607
 *
 * 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. */
2608
	__free_one_page(page, page_to_pfn(page), zone, order, mt,
2609
			FPI_SKIP_REPORT_NOTIFY | FPI_TO_TAIL);
2610 2611
}

2612 2613 2614
/*
 * Update NUMA hit/miss statistics
 */
2615 2616
static inline void zone_statistics(struct zone *preferred_zone, struct zone *z,
				   long nr_account)
2617 2618
{
#ifdef CONFIG_NUMA
2619
	enum numa_stat_item local_stat = NUMA_LOCAL;
2620

2621 2622 2623 2624
	/* skip numa counters update if numa stats is disabled */
	if (!static_branch_likely(&vm_numa_stat_key))
		return;

2625
	if (zone_to_nid(z) != numa_node_id())
2626 2627
		local_stat = NUMA_OTHER;

2628
	if (zone_to_nid(z) == zone_to_nid(preferred_zone))
2629
		__count_numa_events(z, NUMA_HIT, nr_account);
2630
	else {
2631 2632
		__count_numa_events(z, NUMA_MISS, nr_account);
		__count_numa_events(preferred_zone, NUMA_FOREIGN, nr_account);
2633
	}
2634
	__count_numa_events(z, local_stat, nr_account);
2635 2636 2637
#endif
}

2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654
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.
		 */
2655
		if (alloc_flags & ALLOC_HIGHATOMIC)
2656 2657 2658
			page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
		if (!page) {
			page = __rmqueue(zone, order, migratetype, alloc_flags);
2659 2660 2661 2662 2663 2664 2665 2666 2667 2668

			/*
			 * 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);

2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684
			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;
}

2685
/* Remove page from the per-cpu list, caller must protect the list */
2686
static inline
2687 2688
struct page *__rmqueue_pcplist(struct zone *zone, unsigned int order,
			int migratetype,
2689
			unsigned int alloc_flags,
Mel Gorman's avatar
Mel Gorman committed
2690
			struct per_cpu_pages *pcp,
2691 2692 2693 2694 2695 2696
			struct list_head *list)
{
	struct page *page;

	do {
		if (list_empty(list)) {
2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710
			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,
2711
					migratetype, alloc_flags);
2712 2713

			pcp->count += alloced << order;
2714 2715 2716 2717
			if (unlikely(list_empty(list)))
				return NULL;
		}

2718 2719
		page = list_first_entry(list, struct page, pcp_list);
		list_del(&page->pcp_list);
2720
		pcp->count -= 1 << order;
2721
	} while (check_new_pages(page, order));
2722 2723 2724 2725 2726 2727

	return page;
}

/* Lock and remove page from the per-cpu list */
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
2728
			struct zone *zone, unsigned int order,
2729
			int migratetype, unsigned int alloc_flags)
2730 2731 2732 2733
{
	struct per_cpu_pages *pcp;
	struct list_head *list;
	struct page *page;
2734
	unsigned long __maybe_unused UP_flags;
2735

2736
	/* spin_trylock may fail due to a parallel drain or IRQ reentrancy. */
2737
	pcp_trylock_prepare(UP_flags);
2738
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
2739
	if (!pcp) {
2740 2741 2742
		pcp_trylock_finish(UP_flags);
		return NULL;
	}
2743 2744 2745 2746 2747 2748 2749

	/*
	 * 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;
2750 2751
	list = &pcp->lists[order_to_pindex(migratetype, order)];
	page = __rmqueue_pcplist(zone, order, migratetype, alloc_flags, pcp, list);
2752
	pcp_spin_unlock(pcp);
2753
	pcp_trylock_finish(UP_flags);
2754
	if (page) {
2755
		__count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
2756
		zone_statistics(preferred_zone, zone, 1);
2757 2758 2759 2760
	}
	return page;
}

Linus Torvalds's avatar
Linus Torvalds committed
2761
/*
2762 2763
 * Allocate a page from the given zone.
 * Use pcplists for THP or "cheap" high-order allocations.
Linus Torvalds's avatar
Linus Torvalds committed
2764
 */
2765 2766 2767 2768 2769 2770

/*
 * 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
2771
 */
2772
__no_sanitize_memory
2773
static inline
2774
struct page *rmqueue(struct zone *preferred_zone,
2775
			struct zone *zone, unsigned int order,
2776 2777
			gfp_t gfp_flags, unsigned int alloc_flags,
			int migratetype)
Linus Torvalds's avatar
Linus Torvalds committed
2778
{
2779
	struct page *page;
Linus Torvalds's avatar
Linus Torvalds committed
2780

2781 2782 2783 2784 2785 2786
	/*
	 * 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));

2787
	if (likely(pcp_allowed_order(order))) {
2788 2789 2790 2791 2792 2793
		/*
		 * 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) {
2794
			page = rmqueue_pcplist(preferred_zone, zone, order,
2795
					migratetype, alloc_flags);
2796 2797
			if (likely(page))
				goto out;
2798
		}
2799
	}
2800

2801 2802
	page = rmqueue_buddy(preferred_zone, zone, order, alloc_flags,
							migratetype);
Linus Torvalds's avatar
Linus Torvalds committed
2803

2804
out:
2805
	/* Separate test+clear to avoid unnecessary atomics */
2806 2807
	if ((alloc_flags & ALLOC_KSWAPD) &&
	    unlikely(test_bit(ZONE_BOOSTED_WATERMARK, &zone->flags))) {
2808 2809 2810 2811
		clear_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
		wakeup_kswapd(zone, 0, 0, zone_idx(zone));
	}

2812
	VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
Linus Torvalds's avatar
Linus Torvalds committed
2813 2814 2815
	return page;
}

2816
noinline bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
2817 2818 2819 2820 2821
{
	return __should_fail_alloc_page(gfp_mask, order);
}
ALLOW_ERROR_INJECTION(should_fail_alloc_page, TRUE);

2822 2823 2824 2825 2826 2827
static inline long __zone_watermark_unusable_free(struct zone *z,
				unsigned int order, unsigned int alloc_flags)
{
	long unusable_free = (1 << order) - 1;

	/*
2828 2829 2830
	 * 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.
2831
	 */
2832
	if (likely(!(alloc_flags & ALLOC_RESERVES)))
2833 2834 2835 2836 2837 2838 2839
		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
2840 2841 2842
#ifdef CONFIG_UNACCEPTED_MEMORY
	unusable_free += zone_page_state(z, NR_UNACCEPTED);
#endif
2843 2844 2845 2846

	return unusable_free;
}

Linus Torvalds's avatar
Linus Torvalds committed
2847
/*
2848 2849 2850 2851
 * 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
2852
 */
2853
bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
2854
			 int highest_zoneidx, unsigned int alloc_flags,
2855
			 long free_pages)
Linus Torvalds's avatar
Linus Torvalds committed
2856
{
2857
	long min = mark;
Linus Torvalds's avatar
Linus Torvalds committed
2858 2859
	int o;

2860
	/* free_pages may go negative - that's OK */
2861
	free_pages -= __zone_watermark_unusable_free(z, order, alloc_flags);
2862

2863 2864 2865 2866 2867
	if (unlikely(alloc_flags & ALLOC_RESERVES)) {
		/*
		 * __GFP_HIGH allows access to 50% of the min reserve as well
		 * as OOM.
		 */
2868
		if (alloc_flags & ALLOC_MIN_RESERVE) {
2869
			min -= min / 2;
2870

2871 2872 2873 2874 2875 2876 2877 2878 2879 2880
			/*
			 * 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;
		}
2881

2882
		/*
2883
		 * OOM victims can try even harder than the normal reserve
2884 2885 2886 2887 2888 2889 2890 2891
		 * 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;
	}

2892 2893 2894 2895 2896
	/*
	 * 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.
	 */
2897
	if (free_pages <= min + z->lowmem_reserve[highest_zoneidx])
2898
		return false;
Linus Torvalds's avatar
Linus Torvalds committed
2899

2900 2901 2902 2903 2904
	/* 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 */
2905
	for (o = order; o <= MAX_ORDER; o++) {
2906 2907 2908 2909 2910 2911 2912
		struct free_area *area = &z->free_area[o];
		int mt;

		if (!area->nr_free)
			continue;

		for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
2913
			if (!free_area_empty(area, mt))
2914 2915 2916 2917
				return true;
		}

#ifdef CONFIG_CMA
2918
		if ((alloc_flags & ALLOC_CMA) &&
2919
		    !free_area_empty(area, MIGRATE_CMA)) {
2920
			return true;
2921
		}
2922
#endif
2923 2924
		if ((alloc_flags & (ALLOC_HIGHATOMIC|ALLOC_OOM)) &&
		    !free_area_empty(area, MIGRATE_HIGHATOMIC)) {
2925
			return true;
2926
		}
Linus Torvalds's avatar
Linus Torvalds committed
2927
	}
2928
	return false;
2929 2930
}

2931
bool zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
2932
		      int highest_zoneidx, unsigned int alloc_flags)
2933
{
2934
	return __zone_watermark_ok(z, order, mark, highest_zoneidx, alloc_flags,
2935 2936 2937
					zone_page_state(z, NR_FREE_PAGES));
}

2938
static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
2939
				unsigned long mark, int highest_zoneidx,
2940
				unsigned int alloc_flags, gfp_t gfp_mask)
2941
{
2942
	long free_pages;
2943

2944
	free_pages = zone_page_state(z, NR_FREE_PAGES);
2945 2946 2947

	/*
	 * Fast check for order-0 only. If this fails then the reserves
2948
	 * need to be calculated.
2949
	 */
2950
	if (!order) {
2951 2952
		long usable_free;
		long reserved;
2953

2954 2955 2956 2957 2958 2959
		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])
2960 2961
			return true;
	}
2962

2963 2964 2965
	if (__zone_watermark_ok(z, order, mark, highest_zoneidx, alloc_flags,
					free_pages))
		return true;
NeilBrown's avatar
NeilBrown committed
2966

2967
	/*
NeilBrown's avatar
NeilBrown committed
2968
	 * Ignore watermark boosting for __GFP_HIGH order-0 allocations
2969 2970 2971 2972
	 * 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
2973
	if (unlikely(!order && (alloc_flags & ALLOC_MIN_RESERVE) && z->watermark_boost
2974 2975 2976 2977 2978 2979 2980
		&& ((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;
2981 2982
}

2983
bool zone_watermark_ok_safe(struct zone *z, unsigned int order,
2984
			unsigned long mark, int highest_zoneidx)
2985 2986 2987 2988 2989 2990
{
	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);

2991
	return __zone_watermark_ok(z, order, mark, highest_zoneidx, 0,
2992
								free_pages);
Linus Torvalds's avatar
Linus Torvalds committed
2993 2994
}

2995
#ifdef CONFIG_NUMA
2996 2997
int __read_mostly node_reclaim_distance = RECLAIM_DISTANCE;

2998 2999
static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
{
3000
	return node_distance(zone_to_nid(local_zone), zone_to_nid(zone)) <=
3001
				node_reclaim_distance;
3002
}
3003
#else	/* CONFIG_NUMA */
3004 3005 3006 3007
static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
{
	return true;
}
3008 3009
#endif	/* CONFIG_NUMA */

3010 3011 3012 3013 3014 3015 3016 3017 3018
/*
 * 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
3019
alloc_flags_nofragment(struct zone *zone, gfp_t gfp_mask)
3020
{
3021
	unsigned int alloc_flags;
3022

3023 3024 3025 3026 3027
	/*
	 * __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);
3028 3029

#ifdef CONFIG_ZONE_DMA32
3030 3031 3032
	if (!zone)
		return alloc_flags;

3033
	if (zone_idx(zone) != ZONE_NORMAL)
3034
		return alloc_flags;
3035 3036 3037 3038 3039 3040 3041 3042

	/*
	 * 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))
3043
		return alloc_flags;
3044

3045
	alloc_flags |= ALLOC_NOFRAGMENT;
3046 3047
#endif /* CONFIG_ZONE_DMA32 */
	return alloc_flags;
3048 3049
}

3050 3051 3052
/* 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)
3053 3054
{
#ifdef CONFIG_CMA
3055
	if (gfp_migratetype(gfp_mask) == MIGRATE_MOVABLE)
3056 3057 3058 3059 3060
		alloc_flags |= ALLOC_CMA;
#endif
	return alloc_flags;
}

3061
/*
3062
 * get_page_from_freelist goes through the zonelist trying to allocate
3063 3064 3065
 * a page.
 */
static struct page *
3066 3067
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
						const struct alloc_context *ac)
3068
{
3069
	struct zoneref *z;
3070
	struct zone *zone;
3071 3072
	struct pglist_data *last_pgdat = NULL;
	bool last_pgdat_dirty_ok = false;
3073
	bool no_fallback;
3074

3075
retry:
3076
	/*
3077
	 * Scan zonelist, looking for a zone with enough free.
3078
	 * See also cpuset_node_allowed() comment in kernel/cgroup/cpuset.c.
3079
	 */
3080 3081
	no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
	z = ac->preferred_zoneref;
3082 3083
	for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
					ac->nodemask) {
3084
		struct page *page;
3085 3086
		unsigned long mark;

3087 3088
		if (cpusets_enabled() &&
			(alloc_flags & ALLOC_CPUSET) &&
3089
			!__cpuset_zone_allowed(zone, gfp_mask))
3090
				continue;
3091 3092
		/*
		 * When allocating a page cache page for writing, we
3093 3094
		 * want to get it from a node that is within its dirty
		 * limit, such that no single node holds more than its
3095
		 * proportional share of globally allowed dirty pages.
3096
		 * The dirty limits take into account the node's
3097 3098 3099 3100 3101
		 * 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
3102
		 * exceed the per-node dirty limit in the slowpath
3103
		 * (spread_dirty_pages unset) before going into reclaim,
3104
		 * which is important when on a NUMA setup the allowed
3105
		 * nodes are together not big enough to reach the
3106
		 * global limit.  The proper fix for these situations
3107
		 * will require awareness of nodes in the
3108 3109
		 * dirty-throttling and the flusher threads.
		 */
3110
		if (ac->spread_dirty_pages) {
3111 3112 3113 3114
			if (last_pgdat != zone->zone_pgdat) {
				last_pgdat = zone->zone_pgdat;
				last_pgdat_dirty_ok = node_dirty_ok(zone->zone_pgdat);
			}
3115

3116
			if (!last_pgdat_dirty_ok)
3117 3118
				continue;
		}
3119

3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135
		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;
			}
		}

3136
		mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);
3137
		if (!zone_watermark_fast(zone, order, mark,
3138 3139
				       ac->highest_zoneidx, alloc_flags,
				       gfp_mask)) {
3140 3141
			int ret;

3142 3143 3144 3145 3146
			if (has_unaccepted_memory()) {
				if (try_to_accept_memory(zone, order))
					goto try_this_zone;
			}

3147 3148 3149 3150 3151
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/*
			 * Watermark failed for this zone, but see if we can
			 * grow this zone if it contains deferred pages.
			 */
3152
			if (deferred_pages_enabled()) {
3153 3154 3155 3156
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
3157 3158 3159 3160 3161
			/* 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;

3162
			if (!node_reclaim_enabled() ||
3163
			    !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
3164 3165
				continue;

3166
			ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
3167
			switch (ret) {
3168
			case NODE_RECLAIM_NOSCAN:
3169
				/* did not scan */
3170
				continue;
3171
			case NODE_RECLAIM_FULL:
3172
				/* scanned but unreclaimable */
3173
				continue;
3174 3175
			default:
				/* did we reclaim enough */
3176
				if (zone_watermark_ok(zone, order, mark,
3177
					ac->highest_zoneidx, alloc_flags))
3178 3179 3180
					goto try_this_zone;

				continue;
3181
			}
3182 3183
		}

3184
try_this_zone:
3185
		page = rmqueue(ac->preferred_zoneref->zone, zone, order,
3186
				gfp_mask, alloc_flags, ac->migratetype);
3187
		if (page) {
3188
			prep_new_page(page, order, gfp_mask, alloc_flags);
3189 3190 3191 3192 3193

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

3197
			return page;
3198
		} else {
3199 3200 3201 3202 3203
			if (has_unaccepted_memory()) {
				if (try_to_accept_memory(zone, order))
					goto try_this_zone;
			}

3204 3205
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/* Try again if zone has deferred pages */
3206
			if (deferred_pages_enabled()) {
3207 3208 3209 3210
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
3211
		}
3212
	}
3213

3214 3215 3216 3217 3218 3219 3220 3221 3222
	/*
	 * 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;
	}

3223
	return NULL;
3224 3225
}

3226
static void warn_alloc_show_mem(gfp_t gfp_mask, nodemask_t *nodemask)
3227 3228 3229 3230 3231 3232 3233 3234 3235
{
	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))
3236
		if (tsk_is_oom_victim(current) ||
3237 3238
		    (current->flags & (PF_MEMALLOC | PF_EXITING)))
			filter &= ~SHOW_MEM_FILTER_NODES;
3239
	if (!in_task() || !(gfp_mask & __GFP_DIRECT_RECLAIM))
3240 3241
		filter &= ~SHOW_MEM_FILTER_NODES;

3242
	__show_mem(filter, nodemask, gfp_zone(gfp_mask));
3243 3244
}

3245
void warn_alloc(gfp_t gfp_mask, nodemask_t *nodemask, const char *fmt, ...)
3246 3247 3248
{
	struct va_format vaf;
	va_list args;
3249
	static DEFINE_RATELIMIT_STATE(nopage_rs, 10*HZ, 1);
3250

3251 3252 3253
	if ((gfp_mask & __GFP_NOWARN) ||
	     !__ratelimit(&nopage_rs) ||
	     ((gfp_mask & __GFP_DMA) && !has_managed_dma()))
3254 3255
		return;

3256 3257 3258
	va_start(args, fmt);
	vaf.fmt = fmt;
	vaf.va = &args;
3259
	pr_warn("%s: %pV, mode:%#x(%pGg), nodemask=%*pbl",
3260 3261
			current->comm, &vaf, gfp_mask, &gfp_mask,
			nodemask_pr_args(nodemask));
3262
	va_end(args);
Joe Perches's avatar
Joe Perches committed
3263

3264
	cpuset_print_current_mems_allowed();
3265
	pr_cont("\n");
3266
	dump_stack();
3267
	warn_alloc_show_mem(gfp_mask, nodemask);
3268 3269
}

3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289
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;
}

3290 3291
static inline struct page *
__alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
3292
	const struct alloc_context *ac, unsigned long *did_some_progress)
3293
{
3294 3295 3296
	struct oom_control oc = {
		.zonelist = ac->zonelist,
		.nodemask = ac->nodemask,
3297
		.memcg = NULL,
3298 3299 3300
		.gfp_mask = gfp_mask,
		.order = order,
	};
3301 3302
	struct page *page;

3303 3304 3305
	*did_some_progress = 0;

	/*
3306 3307
	 * Acquire the oom lock.  If that fails, somebody else is
	 * making progress for us.
3308
	 */
3309
	if (!mutex_trylock(&oom_lock)) {
3310
		*did_some_progress = 1;
3311
		schedule_timeout_uninterruptible(1);
Linus Torvalds's avatar
Linus Torvalds committed
3312 3313
		return NULL;
	}
3314

3315 3316 3317
	/*
	 * 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
3318 3319 3320
	 * 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.
3321
	 */
3322 3323 3324
	page = get_page_from_freelist((gfp_mask | __GFP_HARDWALL) &
				      ~__GFP_DIRECT_RECLAIM, order,
				      ALLOC_WMARK_HIGH|ALLOC_CPUSET, ac);
3325
	if (page)
3326 3327
		goto out;

3328 3329 3330 3331 3332 3333
	/* 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;
3334 3335 3336 3337 3338
	/*
	 * 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.
3339 3340
	 *
	 * The OOM killer may not free memory on a specific node.
3341
	 */
3342
	if (gfp_mask & (__GFP_RETRY_MAYFAIL | __GFP_THISNODE))
3343
		goto out;
3344
	/* The OOM killer does not needlessly kill tasks for lowmem */
3345
	if (ac->highest_zoneidx < ZONE_NORMAL)
3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358
		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.
	 */

3359
	/* Exhausted what can be done so it's blame time */
3360 3361
	if (out_of_memory(&oc) ||
	    WARN_ON_ONCE_GFP(gfp_mask & __GFP_NOFAIL, gfp_mask)) {
3362
		*did_some_progress = 1;
3363

3364 3365 3366 3367 3368 3369
		/*
		 * Help non-failing allocations by giving them access to memory
		 * reserves
		 */
		if (gfp_mask & __GFP_NOFAIL)
			page = __alloc_pages_cpuset_fallback(gfp_mask, order,
3370 3371
					ALLOC_NO_WATERMARKS, ac);
	}
3372
out:
3373
	mutex_unlock(&oom_lock);
3374 3375 3376
	return page;
}

3377
/*
Lu Jialin's avatar
Lu Jialin committed
3378
 * Maximum number of compaction retries with a progress before OOM
3379 3380 3381 3382
 * killer is consider as the only way to move forward.
 */
#define MAX_COMPACT_RETRIES 16

3383 3384 3385 3386
#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,
3387
		unsigned int alloc_flags, const struct alloc_context *ac,
3388
		enum compact_priority prio, enum compact_result *compact_result)
3389
{
3390
	struct page *page = NULL;
3391
	unsigned long pflags;
3392
	unsigned int noreclaim_flag;
3393 3394

	if (!order)
3395 3396
		return NULL;

3397
	psi_memstall_enter(&pflags);
3398
	delayacct_compact_start();
3399
	noreclaim_flag = memalloc_noreclaim_save();
3400

3401
	*compact_result = try_to_compact_pages(gfp_mask, order, alloc_flags, ac,
3402
								prio, &page);
3403

3404
	memalloc_noreclaim_restore(noreclaim_flag);
3405
	psi_memstall_leave(&pflags);
3406
	delayacct_compact_end();
3407

3408 3409
	if (*compact_result == COMPACT_SKIPPED)
		return NULL;
3410 3411 3412 3413 3414
	/*
	 * At least in one zone compaction wasn't deferred or skipped, so let's
	 * count a compaction stall
	 */
	count_vm_event(COMPACTSTALL);
3415

3416 3417 3418 3419 3420 3421 3422
	/* 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);
3423

3424 3425
	if (page) {
		struct zone *zone = page_zone(page);
3426

3427 3428 3429 3430 3431
		zone->compact_blockskip_flush = false;
		compaction_defer_reset(zone, order, true);
		count_vm_event(COMPACTSUCCESS);
		return page;
	}
3432

3433 3434 3435 3436 3437
	/*
	 * 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);
3438

3439
	cond_resched();
3440 3441 3442

	return NULL;
}
3443

3444 3445 3446 3447
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,
3448
		     int *compaction_retries)
3449 3450
{
	int max_retries = MAX_COMPACT_RETRIES;
3451
	int min_priority;
3452 3453 3454
	bool ret = false;
	int retries = *compaction_retries;
	enum compact_priority priority = *compact_priority;
3455 3456 3457 3458

	if (!order)
		return false;

3459 3460 3461
	if (fatal_signal_pending(current))
		return false;

3462
	/*
3463 3464
	 * Compaction was skipped due to a lack of free order-0
	 * migration targets. Continue if reclaim can help.
3465
	 */
3466
	if (compact_result == COMPACT_SKIPPED) {
3467 3468 3469 3470
		ret = compaction_zonelist_suitable(ac, order, alloc_flags);
		goto out;
	}

3471
	/*
3472 3473
	 * Compaction managed to coalesce some page blocks, but the
	 * allocation failed presumably due to a race. Retry some.
3474
	 */
3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486
	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;
3487

3488 3489 3490 3491
		if (++(*compaction_retries) <= max_retries) {
			ret = true;
			goto out;
		}
3492
	}
3493

3494
	/*
3495
	 * Compaction failed. Retry with increasing priority.
3496
	 */
3497 3498
	min_priority = (order > PAGE_ALLOC_COSTLY_ORDER) ?
			MIN_COMPACT_COSTLY_PRIORITY : MIN_COMPACT_PRIORITY;
3499

3500
	if (*compact_priority > min_priority) {
3501 3502
		(*compact_priority)--;
		*compaction_retries = 0;
3503
		ret = true;
3504
	}
3505 3506 3507
out:
	trace_compact_retry(order, priority, compact_result, retries, max_retries, ret);
	return ret;
3508
}
3509 3510 3511
#else
static inline struct page *
__alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
3512
		unsigned int alloc_flags, const struct alloc_context *ac,
3513
		enum compact_priority prio, enum compact_result *compact_result)
3514
{
3515
	*compact_result = COMPACT_SKIPPED;
3516 3517
	return NULL;
}
3518 3519

static inline bool
3520 3521
should_compact_retry(struct alloc_context *ac, unsigned int order, int alloc_flags,
		     enum compact_result compact_result,
3522
		     enum compact_priority *compact_priority,
3523
		     int *compaction_retries)
3524
{
3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536
	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.
	 */
3537 3538
	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
				ac->highest_zoneidx, ac->nodemask) {
3539
		if (zone_watermark_ok(zone, 0, min_wmark_pages(zone),
3540
					ac->highest_zoneidx, alloc_flags))
3541 3542
			return true;
	}
3543 3544
	return false;
}
3545
#endif /* CONFIG_COMPACTION */
3546

3547
#ifdef CONFIG_LOCKDEP
3548
static struct lockdep_map __fs_reclaim_map =
3549 3550
	STATIC_LOCKDEP_MAP_INIT("fs_reclaim", &__fs_reclaim_map);

3551
static bool __need_reclaim(gfp_t gfp_mask)
3552 3553 3554 3555 3556 3557
{
	/* no reclaim without waiting on it */
	if (!(gfp_mask & __GFP_DIRECT_RECLAIM))
		return false;

	/* this guy won't enter reclaim */
3558
	if (current->flags & PF_MEMALLOC)
3559 3560 3561 3562 3563 3564 3565 3566
		return false;

	if (gfp_mask & __GFP_NOLOCKDEP)
		return false;

	return true;
}

3567
void __fs_reclaim_acquire(unsigned long ip)
3568
{
3569
	lock_acquire_exclusive(&__fs_reclaim_map, 0, 0, NULL, ip);
3570 3571
}

3572
void __fs_reclaim_release(unsigned long ip)
3573
{
3574
	lock_release(&__fs_reclaim_map, ip);
3575 3576
}

3577 3578
void fs_reclaim_acquire(gfp_t gfp_mask)
{
3579 3580 3581 3582
	gfp_mask = current_gfp_context(gfp_mask);

	if (__need_reclaim(gfp_mask)) {
		if (gfp_mask & __GFP_FS)
3583
			__fs_reclaim_acquire(_RET_IP_);
3584 3585 3586 3587 3588 3589 3590

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

	}
3591 3592 3593 3594 3595
}
EXPORT_SYMBOL_GPL(fs_reclaim_acquire);

void fs_reclaim_release(gfp_t gfp_mask)
{
3596 3597 3598 3599
	gfp_mask = current_gfp_context(gfp_mask);

	if (__need_reclaim(gfp_mask)) {
		if (gfp_mask & __GFP_FS)
3600
			__fs_reclaim_release(_RET_IP_);
3601
	}
3602 3603 3604 3605
}
EXPORT_SYMBOL_GPL(fs_reclaim_release);
#endif

3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629
/*
 * 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;
}

3630
/* Perform direct synchronous page reclaim */
3631
static unsigned long
3632 3633
__perform_reclaim(gfp_t gfp_mask, unsigned int order,
					const struct alloc_context *ac)
3634
{
3635
	unsigned int noreclaim_flag;
3636
	unsigned long progress;
3637 3638 3639 3640 3641

	cond_resched();

	/* We now go into synchronous reclaim */
	cpuset_memory_pressure_bump();
3642
	fs_reclaim_acquire(gfp_mask);
3643
	noreclaim_flag = memalloc_noreclaim_save();
3644

3645 3646
	progress = try_to_free_pages(ac->zonelist, order, gfp_mask,
								ac->nodemask);
3647

3648
	memalloc_noreclaim_restore(noreclaim_flag);
3649
	fs_reclaim_release(gfp_mask);
3650 3651 3652

	cond_resched();

3653 3654 3655 3656 3657 3658
	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,
3659
		unsigned int alloc_flags, const struct alloc_context *ac,
3660
		unsigned long *did_some_progress)
3661 3662
{
	struct page *page = NULL;
3663
	unsigned long pflags;
3664 3665
	bool drained = false;

3666
	psi_memstall_enter(&pflags);
3667
	*did_some_progress = __perform_reclaim(gfp_mask, order, ac);
3668
	if (unlikely(!(*did_some_progress)))
3669
		goto out;
3670

3671
retry:
3672
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
3673 3674 3675

	/*
	 * If an allocation failed after direct reclaim, it could be because
3676
	 * pages are pinned on the per-cpu lists or in high alloc reserves.
3677
	 * Shrink them and try again
3678 3679
	 */
	if (!page && !drained) {
3680
		unreserve_highatomic_pageblock(ac, false);
3681
		drain_all_pages(NULL);
3682 3683 3684
		drained = true;
		goto retry;
	}
3685 3686
out:
	psi_memstall_leave(&pflags);
3687

3688 3689 3690
	return page;
}

3691 3692
static void wake_all_kswapds(unsigned int order, gfp_t gfp_mask,
			     const struct alloc_context *ac)
3693 3694 3695
{
	struct zoneref *z;
	struct zone *zone;
3696
	pg_data_t *last_pgdat = NULL;
3697
	enum zone_type highest_zoneidx = ac->highest_zoneidx;
3698

3699
	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist, highest_zoneidx,
3700
					ac->nodemask) {
3701 3702
		if (!managed_zone(zone))
			continue;
3703
		if (last_pgdat != zone->zone_pgdat) {
3704
			wakeup_kswapd(zone, gfp_mask, order, highest_zoneidx);
3705 3706
			last_pgdat = zone->zone_pgdat;
		}
3707
	}
3708 3709
}

3710
static inline unsigned int
3711
gfp_to_alloc_flags(gfp_t gfp_mask, unsigned int order)
3712
{
3713
	unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
Linus Torvalds's avatar
Linus Torvalds committed
3714

3715
	/*
3716
	 * __GFP_HIGH is assumed to be the same as ALLOC_MIN_RESERVE
3717 3718 3719
	 * and __GFP_KSWAPD_RECLAIM is assumed to be the same as ALLOC_KSWAPD
	 * to save two branches.
	 */
3720
	BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_MIN_RESERVE);
3721
	BUILD_BUG_ON(__GFP_KSWAPD_RECLAIM != (__force gfp_t) ALLOC_KSWAPD);
3722

3723 3724 3725 3726
	/*
	 * 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
3727
	 * set both ALLOC_NON_BLOCK and ALLOC_MIN_RESERVE(__GFP_HIGH).
3728
	 */
3729 3730
	alloc_flags |= (__force int)
		(gfp_mask & (__GFP_HIGH | __GFP_KSWAPD_RECLAIM));
Linus Torvalds's avatar
Linus Torvalds committed
3731

3732
	if (!(gfp_mask & __GFP_DIRECT_RECLAIM)) {
3733
		/*
3734 3735
		 * Not worth trying to allocate harder for __GFP_NOMEMALLOC even
		 * if it can't schedule.
3736
		 */
3737
		if (!(gfp_mask & __GFP_NOMEMALLOC)) {
3738
			alloc_flags |= ALLOC_NON_BLOCK;
3739 3740 3741 3742 3743

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

3744
		/*
3745 3746
		 * Ignore cpuset mems for non-blocking __GFP_HIGH (probably
		 * GFP_ATOMIC) rather than fail, see the comment for
3747
		 * cpuset_node_allowed().
3748
		 */
3749 3750
		if (alloc_flags & ALLOC_MIN_RESERVE)
			alloc_flags &= ~ALLOC_CPUSET;
3751
	} else if (unlikely(rt_task(current)) && in_task())
3752
		alloc_flags |= ALLOC_MIN_RESERVE;
3753

3754
	alloc_flags = gfp_to_alloc_flags_cma(gfp_mask, alloc_flags);
3755

3756 3757 3758
	return alloc_flags;
}

3759
static bool oom_reserves_allowed(struct task_struct *tsk)
3760
{
3761 3762 3763 3764 3765 3766 3767 3768
	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))
3769 3770
		return false;

3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781
	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;
3782
	if (gfp_mask & __GFP_MEMALLOC)
3783
		return ALLOC_NO_WATERMARKS;
3784
	if (in_serving_softirq() && (current->flags & PF_MEMALLOC))
3785 3786 3787 3788 3789 3790 3791
		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;
	}
3792

3793 3794 3795 3796 3797 3798
	return 0;
}

bool gfp_pfmemalloc_allowed(gfp_t gfp_mask)
{
	return !!__gfp_pfmemalloc_flags(gfp_mask);
3799 3800
}

3801 3802 3803
/*
 * Checks whether it makes sense to retry the reclaim to make a forward progress
 * for the given allocation request.
3804 3805 3806 3807
 *
 * 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.
3808 3809 3810 3811 3812 3813
 *
 * 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,
3814
		     bool did_some_progress, int *no_progress_loops)
3815 3816 3817
{
	struct zone *zone;
	struct zoneref *z;
3818
	bool ret = false;
3819

3820 3821 3822 3823 3824 3825 3826 3827 3828 3829
	/*
	 * 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)++;

3830 3831 3832 3833
	/*
	 * Make sure we converge to OOM if we cannot make any progress
	 * several times in the row.
	 */
3834 3835
	if (*no_progress_loops > MAX_RECLAIM_RETRIES) {
		/* Before OOM, exhaust highatomic_reserve */
3836
		return unreserve_highatomic_pageblock(ac, true);
3837
	}
3838

3839 3840 3841 3842 3843
	/*
	 * 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.
3844
	 */
3845 3846
	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
				ac->highest_zoneidx, ac->nodemask) {
3847
		unsigned long available;
3848
		unsigned long reclaimable;
3849 3850
		unsigned long min_wmark = min_wmark_pages(zone);
		bool wmark;
3851

3852 3853
		available = reclaimable = zone_reclaimable_pages(zone);
		available += zone_page_state_snapshot(zone, NR_FREE_PAGES);
3854 3855

		/*
3856 3857
		 * Would the allocation succeed if we reclaimed all
		 * reclaimable pages?
3858
		 */
3859
		wmark = __zone_watermark_ok(zone, order, min_wmark,
3860
				ac->highest_zoneidx, alloc_flags, available);
3861 3862 3863
		trace_reclaim_retry_zone(z, order, reclaimable,
				available, min_wmark, *no_progress_loops, wmark);
		if (wmark) {
3864
			ret = true;
3865
			break;
3866 3867 3868
		}
	}

3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880
	/*
	 * 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;
3881 3882
}

3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915
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;
}

3916 3917
static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
3918
						struct alloc_context *ac)
3919
{
3920
	bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
3921
	const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
3922
	struct page *page = NULL;
3923
	unsigned int alloc_flags;
3924
	unsigned long did_some_progress;
3925
	enum compact_priority compact_priority;
3926
	enum compact_result compact_result;
3927 3928 3929
	int compaction_retries;
	int no_progress_loops;
	unsigned int cpuset_mems_cookie;
3930
	unsigned int zonelist_iter_cookie;
3931
	int reserve_flags;
Linus Torvalds's avatar
Linus Torvalds committed
3932

3933
restart:
3934 3935 3936 3937
	compaction_retries = 0;
	no_progress_loops = 0;
	compact_priority = DEF_COMPACT_PRIORITY;
	cpuset_mems_cookie = read_mems_allowed_begin();
3938
	zonelist_iter_cookie = zonelist_iter_begin();
3939 3940 3941 3942 3943 3944

	/*
	 * 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.
	 */
3945
	alloc_flags = gfp_to_alloc_flags(gfp_mask, order);
3946

3947 3948 3949 3950 3951 3952 3953
	/*
	 * 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,
3954
					ac->highest_zoneidx, ac->nodemask);
3955 3956 3957
	if (!ac->preferred_zoneref->zone)
		goto nopage;

3958 3959 3960 3961 3962 3963 3964 3965 3966 3967 3968 3969 3970
	/*
	 * 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;
	}

3971
	if (alloc_flags & ALLOC_KSWAPD)
3972
		wake_all_kswapds(order, gfp_mask, ac);
3973 3974 3975 3976 3977 3978 3979 3980 3981

	/*
	 * 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;

3982 3983
	/*
	 * For costly allocations, try direct compaction first, as it's likely
3984 3985 3986 3987 3988 3989
	 * 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.
3990
	 */
3991 3992 3993 3994
	if (can_direct_reclaim &&
			(costly_order ||
			   (order > 0 && ac->migratetype != MIGRATE_MOVABLE))
			&& !gfp_pfmemalloc_allowed(gfp_mask)) {
3995 3996
		page = __alloc_pages_direct_compact(gfp_mask, order,
						alloc_flags, ac,
3997
						INIT_COMPACT_PRIORITY,
3998 3999 4000 4001
						&compact_result);
		if (page)
			goto got_pg;

4002 4003 4004 4005 4006
		/*
		 * Checks for costly allocations with __GFP_NORETRY, which
		 * includes some THP page fault allocations
		 */
		if (costly_order && (gfp_mask & __GFP_NORETRY)) {
4007 4008 4009 4010
			/*
			 * If allocating entire pageblock(s) and compaction
			 * failed because all zones are below low watermarks
			 * or is prohibited because it recently failed at this
4011 4012
			 * order, fail immediately unless the allocator has
			 * requested compaction and reclaim retry.
4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026
			 *
			 * 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;
4027 4028

			/*
4029 4030
			 * Looks like reclaim/compaction is worth trying, but
			 * sync compaction could be very expensive, so keep
4031
			 * using async compaction.
4032
			 */
4033
			compact_priority = INIT_COMPACT_PRIORITY;
4034 4035
		}
	}
4036

4037
retry:
4038
	/* Ensure kswapd doesn't accidentally go to sleep as long as we loop */
4039
	if (alloc_flags & ALLOC_KSWAPD)
4040
		wake_all_kswapds(order, gfp_mask, ac);
4041

4042 4043
	reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
	if (reserve_flags)
4044 4045
		alloc_flags = gfp_to_alloc_flags_cma(gfp_mask, reserve_flags) |
					  (alloc_flags & ALLOC_KSWAPD);
4046

4047
	/*
4048 4049 4050
	 * Reset the nodemask and zonelist iterators if memory policies can be
	 * ignored. These allocations are high priority and system rather than
	 * user oriented.
4051
	 */
4052
	if (!(alloc_flags & ALLOC_CPUSET) || reserve_flags) {
4053
		ac->nodemask = NULL;
4054
		ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
4055
					ac->highest_zoneidx, ac->nodemask);
4056 4057
	}

4058
	/* Attempt with potentially adjusted zonelist and alloc_flags */
4059
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
4060 4061
	if (page)
		goto got_pg;
Linus Torvalds's avatar
Linus Torvalds committed
4062

4063
	/* Caller is not willing to reclaim, we can't balance anything */
4064
	if (!can_direct_reclaim)
Linus Torvalds's avatar
Linus Torvalds committed
4065 4066
		goto nopage;

4067 4068
	/* Avoid recursion of direct reclaim */
	if (current->flags & PF_MEMALLOC)
4069 4070
		goto nopage;

4071 4072 4073 4074 4075 4076 4077
	/* 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 */
4078
	page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
4079
					compact_priority, &compact_result);
4080 4081
	if (page)
		goto got_pg;
4082

4083 4084
	/* Do not loop if specifically requested */
	if (gfp_mask & __GFP_NORETRY)
4085
		goto nopage;
4086

4087 4088
	/*
	 * Do not retry costly high order allocations unless they are
4089
	 * __GFP_RETRY_MAYFAIL
4090
	 */
4091
	if (costly_order && !(gfp_mask & __GFP_RETRY_MAYFAIL))
4092
		goto nopage;
4093 4094

	if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
4095
				 did_some_progress > 0, &no_progress_loops))
4096 4097
		goto retry;

4098 4099 4100 4101 4102 4103 4104
	/*
	 * 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 &&
4105
			should_compact_retry(ac, order, alloc_flags,
4106
				compact_result, &compact_priority,
4107
				&compaction_retries))
4108 4109
		goto retry;

4110

4111 4112 4113 4114 4115 4116 4117
	/*
	 * 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;
4118

4119 4120 4121 4122 4123
	/* Reclaim has failed us, start killing things */
	page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
	if (page)
		goto got_pg;

4124
	/* Avoid allocations with no watermarks from looping endlessly */
4125
	if (tsk_is_oom_victim(current) &&
4126
	    (alloc_flags & ALLOC_OOM ||
4127
	     (gfp_mask & __GFP_NOMEMALLOC)))
4128 4129
		goto nopage;

4130
	/* Retry as long as the OOM killer is making progress */
4131 4132
	if (did_some_progress) {
		no_progress_loops = 0;
4133
		goto retry;
4134
	}
4135

Linus Torvalds's avatar
Linus Torvalds committed
4136
nopage:
4137 4138 4139 4140 4141 4142 4143
	/*
	 * 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;
4144

4145 4146 4147 4148 4149 4150 4151 4152 4153
	/*
	 * 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
		 */
4154
		if (WARN_ON_ONCE_GFP(!can_direct_reclaim, gfp_mask))
4155 4156 4157 4158 4159 4160 4161
			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
		 */
4162
		WARN_ON_ONCE_GFP(current->flags & PF_MEMALLOC, gfp_mask);
4163 4164 4165 4166 4167 4168 4169

		/*
		 * 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.
		 */
4170
		WARN_ON_ONCE_GFP(costly_order, gfp_mask);
4171

4172
		/*
4173 4174 4175
		 * 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
4176
		 * could deplete whole memory reserves which would just make
4177
		 * the situation worse.
4178
		 */
4179
		page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_MIN_RESERVE, ac);
4180 4181 4182
		if (page)
			goto got_pg;

4183 4184 4185 4186
		cond_resched();
		goto retry;
	}
fail:
4187
	warn_alloc(gfp_mask, ac->nodemask,
4188
			"page allocation failure: order:%u", order);
Linus Torvalds's avatar
Linus Torvalds committed
4189
got_pg:
4190
	return page;
Linus Torvalds's avatar
Linus Torvalds committed
4191
}
4192

4193
static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
4194
		int preferred_nid, nodemask_t *nodemask,
4195
		struct alloc_context *ac, gfp_t *alloc_gfp,
4196
		unsigned int *alloc_flags)
4197
{
4198
	ac->highest_zoneidx = gfp_zone(gfp_mask);
4199
	ac->zonelist = node_zonelist(preferred_nid, gfp_mask);
4200
	ac->nodemask = nodemask;
4201
	ac->migratetype = gfp_migratetype(gfp_mask);
4202

4203
	if (cpusets_enabled()) {
4204
		*alloc_gfp |= __GFP_HARDWALL;
4205 4206 4207 4208
		/*
		 * When we are in the interrupt context, it is irrelevant
		 * to the current task context. It means that any node ok.
		 */
4209
		if (in_task() && !ac->nodemask)
4210
			ac->nodemask = &cpuset_current_mems_allowed;
4211 4212
		else
			*alloc_flags |= ALLOC_CPUSET;
4213 4214
	}

4215
	might_alloc(gfp_mask);
4216 4217

	if (should_fail_alloc_page(gfp_mask, order))
4218
		return false;
4219

4220
	*alloc_flags = gfp_to_alloc_flags_cma(gfp_mask, *alloc_flags);
4221

4222
	/* Dirty zone balancing only done in the fast path */
4223
	ac->spread_dirty_pages = (gfp_mask & __GFP_WRITE);
4224

4225 4226 4227 4228 4229
	/*
	 * 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.
	 */
4230
	ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
4231
					ac->highest_zoneidx, ac->nodemask);
4232 4233

	return true;
4234 4235
}

4236
/*
4237
 * __alloc_pages_bulk - Allocate a number of order-0 pages to a list or array
4238 4239 4240
 * @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
4241 4242 4243
 * @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
4244 4245
 *
 * This is a batched version of the page allocator that attempts to
4246 4247
 * 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.
4248
 *
4249 4250 4251 4252 4253 4254
 * 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.
4255 4256 4257
 */
unsigned long __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
			nodemask_t *nodemask, int nr_pages,
4258 4259
			struct list_head *page_list,
			struct page **page_array)
4260 4261
{
	struct page *page;
4262
	unsigned long __maybe_unused UP_flags;
4263 4264 4265 4266 4267 4268 4269
	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;
4270
	int nr_populated = 0, nr_account = 0;
4271

4272 4273 4274 4275
	/*
	 * Skip populated array elements to determine if any pages need
	 * to be allocated before disabling IRQs.
	 */
4276
	while (page_array && nr_populated < nr_pages && page_array[nr_populated])
4277 4278
		nr_populated++;

4279 4280 4281 4282
	/* No pages requested? */
	if (unlikely(nr_pages <= 0))
		goto out;

4283 4284
	/* Already populated array? */
	if (unlikely(page_array && nr_pages - nr_populated == 0))
4285
		goto out;
4286

4287
	/* Bulk allocator does not support memcg accounting. */
4288
	if (memcg_kmem_online() && (gfp & __GFP_ACCOUNT))
4289 4290
		goto failed;

4291
	/* Use the single page allocator for one page. */
4292
	if (nr_pages - nr_populated == 1)
4293 4294
		goto failed;

4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306
#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

4307 4308 4309 4310
	/* 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))
4311
		goto out;
4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339
	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.
	 */
4340
	if (unlikely(!zone))
4341 4342
		goto failed;

4343
	/* spin_trylock may fail due to a parallel drain or IRQ reentrancy. */
4344
	pcp_trylock_prepare(UP_flags);
4345
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
4346
	if (!pcp)
4347
		goto failed_irq;
4348 4349

	/* Attempt the batch allocation */
4350
	pcp_list = &pcp->lists[order_to_pindex(ac.migratetype, 0)];
4351 4352 4353 4354 4355 4356 4357 4358
	while (nr_populated < nr_pages) {

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

4359
		page = __rmqueue_pcplist(zone, 0, ac.migratetype, alloc_flags,
4360
								pcp, pcp_list);
4361
		if (unlikely(!page)) {
4362
			/* Try and allocate at least one page */
4363
			if (!nr_account) {
4364
				pcp_spin_unlock(pcp);
4365
				goto failed_irq;
4366
			}
4367 4368
			break;
		}
4369
		nr_account++;
4370 4371

		prep_new_page(page, 0, gfp, 0);
4372 4373 4374 4375 4376
		if (page_list)
			list_add(&page->lru, page_list);
		else
			page_array[nr_populated] = page;
		nr_populated++;
4377 4378
	}

4379
	pcp_spin_unlock(pcp);
4380
	pcp_trylock_finish(UP_flags);
4381

4382 4383
	__count_zid_vm_events(PGALLOC, zone_idx(zone), nr_account);
	zone_statistics(ac.preferred_zoneref->zone, zone, nr_account);
4384

4385
out:
4386
	return nr_populated;
4387 4388

failed_irq:
4389
	pcp_trylock_finish(UP_flags);
4390 4391 4392 4393

failed:
	page = __alloc_pages(gfp, 0, preferred_nid, nodemask);
	if (page) {
4394 4395 4396 4397 4398
		if (page_list)
			list_add(&page->lru, page_list);
		else
			page_array[nr_populated] = page;
		nr_populated++;
4399 4400
	}

4401
	goto out;
4402 4403 4404
}
EXPORT_SYMBOL_GPL(__alloc_pages_bulk);

4405 4406 4407
/*
 * This is the 'heart' of the zoned buddy allocator.
 */
4408
struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid,
4409
							nodemask_t *nodemask)
4410 4411 4412
{
	struct page *page;
	unsigned int alloc_flags = ALLOC_WMARK_LOW;
4413
	gfp_t alloc_gfp; /* The gfp_t that was actually used for allocation */
4414 4415
	struct alloc_context ac = { };

4416 4417 4418 4419
	/*
	 * There are several places where we assume that the order value is sane
	 * so bail out early if the request is out of bound.
	 */
4420
	if (WARN_ON_ONCE_GFP(order > MAX_ORDER, gfp))
4421 4422
		return NULL;

4423
	gfp &= gfp_allowed_mask;
4424 4425 4426 4427
	/*
	 * 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
4428 4429
	 * memalloc_no{fs,io}_{save,restore}. And PF_MEMALLOC_PIN which ensures
	 * movable zones are not used during allocation.
4430 4431
	 */
	gfp = current_gfp_context(gfp);
4432 4433
	alloc_gfp = gfp;
	if (!prepare_alloc_pages(gfp, order, preferred_nid, nodemask, &ac,
4434
			&alloc_gfp, &alloc_flags))
4435 4436
		return NULL;

4437 4438 4439 4440
	/*
	 * Forbid the first pass from falling back to types that fragment
	 * memory until all local zones are considered.
	 */
4441
	alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp);
4442

4443
	/* First allocation attempt */
4444
	page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac);
4445 4446
	if (likely(page))
		goto out;
4447

4448
	alloc_gfp = gfp;
4449
	ac.spread_dirty_pages = false;
4450

4451 4452 4453 4454
	/*
	 * Restore the original nodemask if it was potentially replaced with
	 * &cpuset_current_mems_allowed to optimize the fast-path attempt.
	 */
4455
	ac.nodemask = nodemask;
4456

4457
	page = __alloc_pages_slowpath(alloc_gfp, order, &ac);
4458

4459
out:
4460
	if (memcg_kmem_online() && (gfp & __GFP_ACCOUNT) && page &&
4461
	    unlikely(__memcg_kmem_charge_page(page, gfp, order) != 0)) {
4462 4463
		__free_pages(page, order);
		page = NULL;
4464 4465
	}

4466
	trace_mm_page_alloc(page, order, alloc_gfp, ac.migratetype);
4467
	kmsan_alloc_page(page, order, alloc_gfp);
4468

4469
	return page;
Linus Torvalds's avatar
Linus Torvalds committed
4470
}
4471
EXPORT_SYMBOL(__alloc_pages);
Linus Torvalds's avatar
Linus Torvalds committed
4472

4473 4474 4475 4476 4477
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);
4478
	struct folio *folio = (struct folio *)page;
4479

4480 4481 4482
	if (folio && order > 1)
		folio_prep_large_rmappable(folio);
	return folio;
4483 4484 4485
}
EXPORT_SYMBOL(__folio_alloc);

Linus Torvalds's avatar
Linus Torvalds committed
4486
/*
4487 4488 4489
 * 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
4490
 */
4491
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
Linus Torvalds's avatar
Linus Torvalds committed
4492
{
4493 4494
	struct page *page;

4495
	page = alloc_pages(gfp_mask & ~__GFP_HIGHMEM, order);
Linus Torvalds's avatar
Linus Torvalds committed
4496 4497 4498 4499 4500 4501
	if (!page)
		return 0;
	return (unsigned long) page_address(page);
}
EXPORT_SYMBOL(__get_free_pages);

4502
unsigned long get_zeroed_page(gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
4503
{
4504
	return __get_free_page(gfp_mask | __GFP_ZERO);
Linus Torvalds's avatar
Linus Torvalds committed
4505 4506 4507
}
EXPORT_SYMBOL(get_zeroed_page);

4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527
/**
 * __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.
 */
4528 4529
void __free_pages(struct page *page, unsigned int order)
{
4530 4531 4532
	/* get PageHead before we drop reference */
	int head = PageHead(page);

4533 4534
	if (put_page_testzero(page))
		free_the_page(page, order);
4535
	else if (!head)
4536 4537
		while (order-- > 0)
			free_the_page(page + (1 << order), order);
4538
}
Linus Torvalds's avatar
Linus Torvalds committed
4539 4540
EXPORT_SYMBOL(__free_pages);

4541
void free_pages(unsigned long addr, unsigned int order)
Linus Torvalds's avatar
Linus Torvalds committed
4542 4543
{
	if (addr != 0) {
Nick Piggin's avatar
Nick Piggin committed
4544
		VM_BUG_ON(!virt_addr_valid((void *)addr));
Linus Torvalds's avatar
Linus Torvalds committed
4545 4546 4547 4548 4549 4550
		__free_pages(virt_to_page((void *)addr), order);
	}
}

EXPORT_SYMBOL(free_pages);

4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561
/*
 * 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.
 */
4562 4563
static struct page *__page_frag_cache_refill(struct page_frag_cache *nc,
					     gfp_t gfp_mask)
4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582
{
	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;
}

4583
void __page_frag_cache_drain(struct page *page, unsigned int count)
4584 4585 4586
{
	VM_BUG_ON_PAGE(page_ref_count(page) == 0, page);

4587 4588
	if (page_ref_sub_and_test(page, count))
		free_the_page(page, compound_order(page));
4589
}
4590
EXPORT_SYMBOL(__page_frag_cache_drain);
4591

4592 4593 4594
void *page_frag_alloc_align(struct page_frag_cache *nc,
		      unsigned int fragsz, gfp_t gfp_mask,
		      unsigned int align_mask)
4595 4596 4597 4598 4599 4600 4601
{
	unsigned int size = PAGE_SIZE;
	struct page *page;
	int offset;

	if (unlikely(!nc->va)) {
refill:
4602
		page = __page_frag_cache_refill(nc, gfp_mask);
4603 4604 4605 4606 4607 4608 4609 4610 4611 4612
		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.
		 */
4613
		page_ref_add(page, PAGE_FRAG_CACHE_MAX_SIZE);
4614 4615

		/* reset page count bias and offset to start of new frag */
4616
		nc->pfmemalloc = page_is_pfmemalloc(page);
4617
		nc->pagecnt_bias = PAGE_FRAG_CACHE_MAX_SIZE + 1;
4618 4619 4620 4621 4622 4623 4624
		nc->offset = size;
	}

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

4625
		if (!page_ref_sub_and_test(page, nc->pagecnt_bias))
4626 4627
			goto refill;

4628 4629 4630 4631 4632
		if (unlikely(nc->pfmemalloc)) {
			free_the_page(page, compound_order(page));
			goto refill;
		}

4633 4634 4635 4636 4637
#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 */
4638
		set_page_count(page, PAGE_FRAG_CACHE_MAX_SIZE + 1);
4639 4640

		/* reset page count bias and offset to start of new frag */
4641
		nc->pagecnt_bias = PAGE_FRAG_CACHE_MAX_SIZE + 1;
4642
		offset = size - fragsz;
4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654
		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;
		}
4655 4656 4657
	}

	nc->pagecnt_bias--;
4658
	offset &= align_mask;
4659 4660 4661 4662
	nc->offset = offset;

	return nc->va + offset;
}
4663
EXPORT_SYMBOL(page_frag_alloc_align);
4664 4665 4666 4667

/*
 * Frees a page fragment allocated out of either a compound or order 0 page.
 */
4668
void page_frag_free(void *addr)
4669 4670 4671
{
	struct page *page = virt_to_head_page(addr);

4672 4673
	if (unlikely(put_page_testzero(page)))
		free_the_page(page, compound_order(page));
4674
}
4675
EXPORT_SYMBOL(page_frag_free);
4676

4677 4678
static void *make_alloc_exact(unsigned long addr, unsigned int order,
		size_t size)
Andi Kleen's avatar
Andi Kleen committed
4679 4680
{
	if (addr) {
4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692
		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
4693 4694 4695 4696
	}
	return (void *)addr;
}

4697 4698 4699
/**
 * alloc_pages_exact - allocate an exact number physically-contiguous pages.
 * @size: the number of bytes to allocate
4700
 * @gfp_mask: GFP flags for the allocation, must not contain __GFP_COMP
4701 4702 4703 4704 4705 4706 4707 4708
 *
 * 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().
4709 4710
 *
 * Return: pointer to the allocated area or %NULL in case of error.
4711 4712 4713 4714 4715 4716
 */
void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
{
	unsigned int order = get_order(size);
	unsigned long addr;

4717 4718
	if (WARN_ON_ONCE(gfp_mask & (__GFP_COMP | __GFP_HIGHMEM)))
		gfp_mask &= ~(__GFP_COMP | __GFP_HIGHMEM);
4719

4720
	addr = __get_free_pages(gfp_mask, order);
Andi Kleen's avatar
Andi Kleen committed
4721
	return make_alloc_exact(addr, order, size);
4722 4723 4724
}
EXPORT_SYMBOL(alloc_pages_exact);

Andi Kleen's avatar
Andi Kleen committed
4725 4726 4727
/**
 * alloc_pages_exact_nid - allocate an exact number of physically-contiguous
 *			   pages on a node.
4728
 * @nid: the preferred node ID where memory should be allocated
Andi Kleen's avatar
Andi Kleen committed
4729
 * @size: the number of bytes to allocate
4730
 * @gfp_mask: GFP flags for the allocation, must not contain __GFP_COMP
Andi Kleen's avatar
Andi Kleen committed
4731 4732 4733
 *
 * Like alloc_pages_exact(), but try to allocate on node nid first before falling
 * back.
4734 4735
 *
 * Return: pointer to the allocated area or %NULL in case of error.
Andi Kleen's avatar
Andi Kleen committed
4736
 */
4737
void * __meminit alloc_pages_exact_nid(int nid, size_t size, gfp_t gfp_mask)
Andi Kleen's avatar
Andi Kleen committed
4738
{
4739
	unsigned int order = get_order(size);
4740 4741
	struct page *p;

4742 4743
	if (WARN_ON_ONCE(gfp_mask & (__GFP_COMP | __GFP_HIGHMEM)))
		gfp_mask &= ~(__GFP_COMP | __GFP_HIGHMEM);
4744 4745

	p = alloc_pages_node(nid, gfp_mask, order);
Andi Kleen's avatar
Andi Kleen committed
4746 4747 4748 4749 4750
	if (!p)
		return NULL;
	return make_alloc_exact((unsigned long)page_address(p), order, size);
}

4751 4752 4753 4754 4755 4756 4757 4758 4759 4760 4761 4762 4763 4764 4765 4766 4767 4768 4769
/**
 * 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);

4770 4771 4772 4773
/**
 * nr_free_zone_pages - count number of pages beyond high watermark
 * @offset: The zone index of the highest zone
 *
4774
 * nr_free_zone_pages() counts the number of pages which are beyond the
4775 4776
 * high watermark within all zones at or below a given zone index.  For each
 * zone, the number of pages is calculated as:
4777 4778
 *
 *     nr_free_zone_pages = managed_pages - high_pages
4779 4780
 *
 * Return: number of pages beyond high watermark.
4781
 */
4782
static unsigned long nr_free_zone_pages(int offset)
Linus Torvalds's avatar
Linus Torvalds committed
4783
{
4784
	struct zoneref *z;
4785 4786
	struct zone *zone;

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

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

4792
	for_each_zone_zonelist(zone, z, zonelist, offset) {
4793
		unsigned long size = zone_managed_pages(zone);
4794
		unsigned long high = high_wmark_pages(zone);
4795 4796
		if (size > high)
			sum += size - high;
Linus Torvalds's avatar
Linus Torvalds committed
4797 4798 4799 4800 4801
	}

	return sum;
}

4802 4803 4804 4805 4806
/**
 * 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.
4807 4808 4809
 *
 * Return: number of pages beyond high watermark within ZONE_DMA and
 * ZONE_NORMAL.
Linus Torvalds's avatar
Linus Torvalds committed
4810
 */
4811
unsigned long nr_free_buffer_pages(void)
Linus Torvalds's avatar
Linus Torvalds committed
4812
{
Al Viro's avatar
Al Viro committed
4813
	return nr_free_zone_pages(gfp_zone(GFP_USER));
Linus Torvalds's avatar
Linus Torvalds committed
4814
}
4815
EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
Linus Torvalds's avatar
Linus Torvalds committed
4816

4817 4818 4819 4820 4821 4822
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
4823 4824
/*
 * Builds allocation fallback zone lists.
4825 4826
 *
 * Add all populated zones of a node to the zonelist.
Linus Torvalds's avatar
Linus Torvalds committed
4827
 */
4828
static int build_zonerefs_node(pg_data_t *pgdat, struct zoneref *zonerefs)
Linus Torvalds's avatar
Linus Torvalds committed
4829
{
4830
	struct zone *zone;
4831
	enum zone_type zone_type = MAX_NR_ZONES;
4832
	int nr_zones = 0;
4833 4834

	do {
4835
		zone_type--;
4836
		zone = pgdat->node_zones + zone_type;
4837
		if (populated_zone(zone)) {
4838
			zoneref_set_zone(zone, &zonerefs[nr_zones++]);
4839
			check_highest_zone(zone_type);
Linus Torvalds's avatar
Linus Torvalds committed
4840
		}
4841
	} while (zone_type);
4842

4843
	return nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
4844 4845 4846
}

#ifdef CONFIG_NUMA
4847 4848 4849

static int __parse_numa_zonelist_order(char *s)
{
4850
	/*
Ingo Molnar's avatar
Ingo Molnar committed
4851
	 * We used to support different zonelists modes but they turned
4852 4853 4854 4855 4856 4857
	 * 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);
4858 4859 4860 4861 4862
		return -EINVAL;
	}
	return 0;
}

4863 4864
static char numa_zonelist_order[] = "Node";
#define NUMA_ZONELIST_ORDER_LEN	16
4865 4866 4867
/*
 * sysctl handler for numa_zonelist_order
 */
4868
static int numa_zonelist_order_handler(struct ctl_table *table, int write,
4869
		void *buffer, size_t *length, loff_t *ppos)
4870
{
4871 4872 4873
	if (write)
		return __parse_numa_zonelist_order(buffer);
	return proc_dostring(table, write, buffer, length, ppos);
4874 4875 4876 4877
}

static int node_load[MAX_NUMNODES];

Linus Torvalds's avatar
Linus Torvalds committed
4878
/**
4879
 * 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
4880 4881 4882 4883 4884 4885 4886 4887 4888 4889
 * @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.
4890 4891
 *
 * Return: node id of the found node or %NUMA_NO_NODE if no node is found.
Linus Torvalds's avatar
Linus Torvalds committed
4892
 */
4893
int find_next_best_node(int node, nodemask_t *used_node_mask)
Linus Torvalds's avatar
Linus Torvalds committed
4894
{
4895
	int n, val;
Linus Torvalds's avatar
Linus Torvalds committed
4896
	int min_val = INT_MAX;
David Rientjes's avatar
David Rientjes committed
4897
	int best_node = NUMA_NO_NODE;
Linus Torvalds's avatar
Linus Torvalds committed
4898

4899 4900 4901 4902 4903
	/* 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
4904

4905
	for_each_node_state(n, N_MEMORY) {
Linus Torvalds's avatar
Linus Torvalds committed
4906 4907 4908 4909 4910 4911 4912 4913

		/* 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);

4914 4915 4916
		/* Penalize nodes under us ("prefer the next node") */
		val += (n < node);

Linus Torvalds's avatar
Linus Torvalds committed
4917
		/* Give preference to headless and unused nodes */
4918
		if (!cpumask_empty(cpumask_of_node(n)))
Linus Torvalds's avatar
Linus Torvalds committed
4919 4920 4921
			val += PENALTY_FOR_NODE_WITH_CPUS;

		/* Slight preference for less loaded node */
4922
		val *= MAX_NUMNODES;
Linus Torvalds's avatar
Linus Torvalds committed
4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936
		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;
}

4937 4938 4939 4940 4941 4942

/*
 * 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.
 */
4943 4944
static void build_zonelists_in_node_order(pg_data_t *pgdat, int *node_order,
		unsigned nr_nodes)
Linus Torvalds's avatar
Linus Torvalds committed
4945
{
4946 4947 4948 4949 4950 4951 4952 4953 4954
	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]);
4955

4956 4957 4958 4959 4960
		nr_zones = build_zonerefs_node(node, zonerefs);
		zonerefs += nr_zones;
	}
	zonerefs->zone = NULL;
	zonerefs->zone_idx = 0;
4961 4962
}

4963 4964 4965 4966 4967
/*
 * Build gfp_thisnode zonelists
 */
static void build_thisnode_zonelists(pg_data_t *pgdat)
{
4968 4969
	struct zoneref *zonerefs;
	int nr_zones;
4970

4971 4972 4973 4974 4975
	zonerefs = pgdat->node_zonelists[ZONELIST_NOFALLBACK]._zonerefs;
	nr_zones = build_zonerefs_node(pgdat, zonerefs);
	zonerefs += nr_zones;
	zonerefs->zone = NULL;
	zonerefs->zone_idx = 0;
4976 4977
}

4978 4979 4980 4981 4982 4983 4984 4985 4986
/*
 * 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)
{
4987
	static int node_order[MAX_NUMNODES];
4988
	int node, nr_nodes = 0;
4989
	nodemask_t used_mask = NODE_MASK_NONE;
4990
	int local_node, prev_node;
Linus Torvalds's avatar
Linus Torvalds committed
4991 4992 4993 4994

	/* NUMA-aware ordering of nodes */
	local_node = pgdat->node_id;
	prev_node = local_node;
4995 4996

	memset(node_order, 0, sizeof(node_order));
Linus Torvalds's avatar
Linus Torvalds committed
4997 4998 4999 5000 5001 5002
	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.
		 */
5003 5004
		if (node_distance(local_node, node) !=
		    node_distance(local_node, prev_node))
5005
			node_load[node] += 1;
5006

5007
		node_order[nr_nodes++] = node;
Linus Torvalds's avatar
Linus Torvalds committed
5008 5009
		prev_node = node;
	}
5010

5011
	build_zonelists_in_node_order(pgdat, node_order, nr_nodes);
5012
	build_thisnode_zonelists(pgdat);
5013 5014 5015 5016
	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
5017 5018
}

5019 5020 5021 5022 5023 5024 5025 5026 5027
#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)
{
5028
	struct zoneref *z;
5029

5030
	z = first_zones_zonelist(node_zonelist(node, GFP_KERNEL),
5031
				   gfp_zone(GFP_KERNEL),
5032
				   NULL);
5033
	return zone_to_nid(z->zone);
5034 5035
}
#endif
5036

5037 5038
static void setup_min_unmapped_ratio(void);
static void setup_min_slab_ratio(void);
Linus Torvalds's avatar
Linus Torvalds committed
5039 5040
#else	/* CONFIG_NUMA */

5041
static void build_zonelists(pg_data_t *pgdat)
Linus Torvalds's avatar
Linus Torvalds committed
5042
{
5043
	int node, local_node;
5044 5045
	struct zoneref *zonerefs;
	int nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
5046 5047 5048

	local_node = pgdat->node_id;

5049 5050 5051
	zonerefs = pgdat->node_zonelists[ZONELIST_FALLBACK]._zonerefs;
	nr_zones = build_zonerefs_node(pgdat, zonerefs);
	zonerefs += nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
5052

5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063
	/*
	 * 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;
5064 5065
		nr_zones = build_zonerefs_node(NODE_DATA(node), zonerefs);
		zonerefs += nr_zones;
Linus Torvalds's avatar
Linus Torvalds committed
5066
	}
5067 5068 5069
	for (node = 0; node < local_node; node++) {
		if (!node_online(node))
			continue;
5070 5071
		nr_zones = build_zonerefs_node(NODE_DATA(node), zonerefs);
		zonerefs += nr_zones;
5072 5073
	}

5074 5075
	zonerefs->zone = NULL;
	zonerefs->zone_idx = 0;
Linus Torvalds's avatar
Linus Torvalds committed
5076 5077 5078 5079
}

#endif	/* CONFIG_NUMA */

5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094
/*
 * 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.
 */
5095
static void per_cpu_pages_init(struct per_cpu_pages *pcp, struct per_cpu_zonestat *pzstats);
5096 5097 5098
/* These effectively disable the pcplists in the boot pageset completely */
#define BOOT_PAGESET_HIGH	0
#define BOOT_PAGESET_BATCH	1
5099 5100
static DEFINE_PER_CPU(struct per_cpu_pages, boot_pageset);
static DEFINE_PER_CPU(struct per_cpu_zonestat, boot_zonestats);
5101

5102
static void __build_all_zonelists(void *data)
Linus Torvalds's avatar
Linus Torvalds committed
5103
{
5104
	int nid;
5105
	int __maybe_unused cpu;
5106
	pg_data_t *self = data;
5107
	unsigned long flags;
5108

5109
	/*
5110 5111
	 * The zonelist_update_seq must be acquired with irqsave because the
	 * reader can be invoked from IRQ with GFP_ATOMIC.
5112
	 */
5113
	write_seqlock_irqsave(&zonelist_update_seq, flags);
5114
	/*
5115 5116
	 * Also disable synchronous printk() to prevent any printk() from
	 * trying to hold port->lock, for
5117 5118 5119 5120
	 * 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();
5121

5122 5123 5124
#ifdef CONFIG_NUMA
	memset(node_load, 0, sizeof(node_load));
#endif
5125

5126 5127 5128 5129
	/*
	 * This node is hotadded and no memory is yet present.   So just
	 * building zonelists is fine - no need to touch other nodes.
	 */
5130 5131
	if (self && !node_online(self->node_id)) {
		build_zonelists(self);
5132
	} else {
5133 5134 5135 5136 5137
		/*
		 * All possible nodes have pgdat preallocated
		 * in free_area_init
		 */
		for_each_node(nid) {
5138
			pg_data_t *pgdat = NODE_DATA(nid);
5139

5140 5141
			build_zonelists(pgdat);
		}
5142

5143 5144 5145 5146 5147 5148 5149 5150 5151
#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.
		 */
5152
		for_each_online_cpu(cpu)
5153
			set_cpu_numa_mem(cpu, local_memory_node(cpu_to_node(cpu)));
5154
#endif
5155
	}
5156

5157
	printk_deferred_exit();
5158
	write_sequnlock_irqrestore(&zonelist_update_seq, flags);
5159 5160
}

5161 5162 5163
static noinline void __init
build_all_zonelists_init(void)
{
5164 5165
	int cpu;

5166
	__build_all_zonelists(NULL);
5167 5168 5169 5170 5171 5172 5173 5174 5175 5176 5177 5178 5179 5180 5181

	/*
	 * 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)
5182
		per_cpu_pages_init(&per_cpu(boot_pageset, cpu), &per_cpu(boot_zonestats, cpu));
5183

5184 5185 5186 5187
	mminit_verify_zonelist();
	cpuset_init_current_mems_allowed();
}

5188 5189
/*
 * unless system_state == SYSTEM_BOOTING.
5190
 *
5191
 * __ref due to call of __init annotated helper build_all_zonelists_init
5192
 * [protected by SYSTEM_BOOTING].
5193
 */
5194
void __ref build_all_zonelists(pg_data_t *pgdat)
5195
{
5196 5197
	unsigned long vm_total_pages;

5198
	if (system_state == SYSTEM_BOOTING) {
5199
		build_all_zonelists_init();
5200
	} else {
5201
		__build_all_zonelists(pgdat);
5202 5203
		/* cpuset refresh routine should be here */
	}
5204 5205
	/* Get the number of free pages beyond high watermark in all zones. */
	vm_total_pages = nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
5206 5207 5208 5209 5210 5211 5212
	/*
	 * 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
	 */
5213
	if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
5214 5215 5216 5217
		page_group_by_mobility_disabled = 1;
	else
		page_group_by_mobility_disabled = 0;

5218
	pr_info("Built %u zonelists, mobility grouping %s.  Total pages: %ld\n",
Joe Perches's avatar
Joe Perches committed
5219 5220 5221
		nr_online_nodes,
		page_group_by_mobility_disabled ? "off" : "on",
		vm_total_pages);
5222
#ifdef CONFIG_NUMA
5223
	pr_info("Policy zone: %s\n", zone_names[policy_zone]);
5224
#endif
Linus Torvalds's avatar
Linus Torvalds committed
5225 5226
}

5227
static int zone_batchsize(struct zone *zone)
Linus Torvalds's avatar
Linus Torvalds committed
5228
{
5229 5230
#ifdef CONFIG_MMU
	int batch;
Linus Torvalds's avatar
Linus Torvalds committed
5231

5232 5233 5234 5235 5236 5237 5238 5239 5240 5241
	/*
	 * 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;
5242

5243
	/*
5244 5245 5246 5247 5248 5249 5250 5251
	 * 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.
5252
	 */
5253
	batch = rounddown_pow_of_two(batch + batch/2) - 1;
5254

5255
	return batch;
5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272

#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
5273 5274
}

5275
static int percpu_pagelist_high_fraction;
5276
static int zone_highsize(struct zone *zone, int batch, int cpu_online)
5277
{
5278 5279 5280 5281
#ifdef CONFIG_MMU
	int high;
	int nr_split_cpus;
	unsigned long total_pages;
5282

5283
	if (!percpu_pagelist_high_fraction) {
Mel Gorman's avatar
Mel Gorman committed
5284
		/*
5285 5286 5287
		 * 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
5288
		 */
5289 5290
		total_pages = low_wmark_pages(zone);
	} else {
Mel Gorman's avatar
Mel Gorman committed
5291
		/*
5292 5293 5294
		 * 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
5295
		 */
5296
		total_pages = zone_managed_pages(zone) / percpu_pagelist_high_fraction;
Mel Gorman's avatar
Mel Gorman committed
5297 5298 5299
	}

	/*
5300 5301 5302 5303 5304 5305
	 * 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
5306
	 */
5307 5308 5309 5310
	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
5311

5312 5313 5314 5315 5316
	/*
	 * Ensure high is at least batch*4. The multiple is based on the
	 * historical relationship between high and batch.
	 */
	high = max(high, batch << 2);
5317

5318 5319 5320 5321
	return high;
#else
	return 0;
#endif
5322 5323
}

5324
/*
5325 5326 5327 5328 5329 5330 5331 5332 5333 5334 5335 5336 5337 5338
 * 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).
5339
 */
5340 5341
static void pageset_update(struct per_cpu_pages *pcp, unsigned long high,
		unsigned long batch)
5342
{
5343 5344
	WRITE_ONCE(pcp->batch, batch);
	WRITE_ONCE(pcp->high, high);
5345 5346
}

5347
static void per_cpu_pages_init(struct per_cpu_pages *pcp, struct per_cpu_zonestat *pzstats)
5348
{
5349
	int pindex;
5350

5351 5352
	memset(pcp, 0, sizeof(*pcp));
	memset(pzstats, 0, sizeof(*pzstats));
5353

5354 5355 5356
	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
5357

5358 5359 5360 5361 5362 5363 5364 5365 5366 5367
	/*
	 * 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;
}
5368

5369 5370 5371 5372 5373
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
5374

5375 5376 5377
	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
5378
	}
5379
}
5380

5381 5382 5383 5384 5385 5386 5387
/*
 * 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;
5388

5389 5390
	new_batch = max(1, zone_batchsize(zone));
	new_high = zone_highsize(zone, new_batch, cpu_online);
5391

5392 5393 5394
	if (zone->pageset_high == new_high &&
	    zone->pageset_batch == new_batch)
		return;
5395

5396 5397
	zone->pageset_high = new_high;
	zone->pageset_batch = new_batch;
5398

5399
	__zone_set_pageset_high_and_batch(zone, new_high, new_batch);
5400
}
Mel Gorman's avatar
Mel Gorman committed
5401

5402
void __meminit setup_zone_pageset(struct zone *zone)
Mel Gorman's avatar
Mel Gorman committed
5403
{
5404
	int cpu;
Mel Gorman's avatar
Mel Gorman committed
5405

5406 5407 5408
	/* 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
5409

5410 5411 5412 5413
	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
5414

5415 5416 5417
		pcp = per_cpu_ptr(zone->per_cpu_pageset, cpu);
		pzstats = per_cpu_ptr(zone->per_cpu_zonestats, cpu);
		per_cpu_pages_init(pcp, pzstats);
5418
	}
5419 5420

	zone_set_pageset_high_and_batch(zone, 0);
Mel Gorman's avatar
Mel Gorman committed
5421
}
Mel Gorman's avatar
Mel Gorman committed
5422

5423
/*
5424 5425
 * The zone indicated has a new number of managed_pages; batch sizes and percpu
 * page high values need to be recalculated.
5426
 */
5427
static void zone_pcp_update(struct zone *zone, int cpu_online)
5428
{
5429 5430 5431
	mutex_lock(&pcp_batch_high_lock);
	zone_set_pageset_high_and_batch(zone, cpu_online);
	mutex_unlock(&pcp_batch_high_lock);
5432 5433 5434
}

/*
5435 5436
 * Allocate per cpu pagesets and initialize them.
 * Before this call only boot pagesets were available.
5437
 */
5438
void __init setup_per_cpu_pageset(void)
5439
{
5440 5441 5442 5443 5444 5445 5446 5447 5448 5449 5450 5451 5452 5453 5454 5455 5456 5457 5458 5459 5460 5461 5462 5463
	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);
5464 5465
}

5466 5467 5468 5469 5470 5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481
__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
5482

5483 5484
void adjust_managed_page_count(struct page *page, long count)
{
5485
	atomic_long_add(count, &page_zone(page)->managed_pages);
5486
	totalram_pages_add(count);
5487 5488
#ifdef CONFIG_HIGHMEM
	if (PageHighMem(page))
5489
		totalhigh_pages_add(count);
5490
#endif
5491
}
5492
EXPORT_SYMBOL(adjust_managed_page_count);
5493

5494
unsigned long free_reserved_area(void *start, void *end, int poison, const char *s)
5495
{
5496 5497
	void *pos;
	unsigned long pages = 0;
5498

5499 5500 5501
	start = (void *)PAGE_ALIGN((unsigned long)start);
	end = (void *)((unsigned long)end & PAGE_MASK);
	for (pos = start; pos < end; pos += PAGE_SIZE, pages++) {
5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512
		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);
5513 5514 5515 5516 5517
		/*
		 * Perform a kasan-unchecked memset() since this memory
		 * has not been initialized.
		 */
		direct_map_addr = kasan_reset_tag(direct_map_addr);
5518
		if ((unsigned int)poison <= 0xFF)
5519 5520 5521
			memset(direct_map_addr, poison, PAGE_SIZE);

		free_reserved_page(page);
5522 5523 5524
	}

	if (pages && s)
5525
		pr_info("Freeing %s memory: %ldK\n", s, K(pages));
5526 5527 5528 5529

	return pages;
}

5530
static int page_alloc_cpu_dead(unsigned int cpu)
Linus Torvalds's avatar
Linus Torvalds committed
5531
{
5532
	struct zone *zone;
Linus Torvalds's avatar
Linus Torvalds committed
5533

5534
	lru_add_drain_cpu(cpu);
5535
	mlock_drain_remote(cpu);
5536
	drain_pages(cpu);
5537

5538 5539 5540 5541 5542 5543 5544
	/*
	 * 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);
5545

5546 5547 5548 5549 5550 5551 5552 5553
	/*
	 * 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);
5554 5555 5556 5557 5558 5559 5560 5561 5562 5563 5564 5565 5566

	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);
5567
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
5568 5569
}

5570
void __init page_alloc_init_cpuhp(void)
Linus Torvalds's avatar
Linus Torvalds committed
5571
{
5572 5573
	int ret;

5574 5575 5576
	ret = cpuhp_setup_state_nocalls(CPUHP_PAGE_ALLOC,
					"mm/page_alloc:pcp",
					page_alloc_cpu_online,
5577 5578
					page_alloc_cpu_dead);
	WARN_ON(ret < 0);
Linus Torvalds's avatar
Linus Torvalds committed
5579 5580
}

5581
/*
5582
 * calculate_totalreserve_pages - called when sysctl_lowmem_reserve_ratio
5583 5584 5585 5586 5587 5588
 *	or min_free_kbytes changes.
 */
static void calculate_totalreserve_pages(void)
{
	struct pglist_data *pgdat;
	unsigned long reserve_pages = 0;
5589
	enum zone_type i, j;
5590 5591

	for_each_online_pgdat(pgdat) {
5592 5593 5594

		pgdat->totalreserve_pages = 0;

5595 5596
		for (i = 0; i < MAX_NR_ZONES; i++) {
			struct zone *zone = pgdat->node_zones + i;
5597
			long max = 0;
5598
			unsigned long managed_pages = zone_managed_pages(zone);
5599 5600 5601 5602 5603 5604 5605

			/* 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];
			}

5606 5607
			/* we treat the high watermark as reserved pages. */
			max += high_wmark_pages(zone);
5608

5609 5610
			if (max > managed_pages)
				max = managed_pages;
5611

5612
			pgdat->totalreserve_pages += max;
5613

5614 5615 5616 5617 5618 5619
			reserve_pages += max;
		}
	}
	totalreserve_pages = reserve_pages;
}

Linus Torvalds's avatar
Linus Torvalds committed
5620 5621
/*
 * setup_per_zone_lowmem_reserve - called whenever
5622
 *	sysctl_lowmem_reserve_ratio changes.  Ensures that each zone
Linus Torvalds's avatar
Linus Torvalds committed
5623 5624 5625 5626 5627 5628
 *	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;
5629
	enum zone_type i, j;
Linus Torvalds's avatar
Linus Torvalds committed
5630

5631
	for_each_online_pgdat(pgdat) {
5632 5633 5634 5635 5636 5637 5638
		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++) {
5639 5640 5641
				struct zone *upper_zone = &pgdat->node_zones[j];

				managed_pages += zone_managed_pages(upper_zone);
5642

5643 5644 5645
				if (clear)
					zone->lowmem_reserve[j] = 0;
				else
5646
					zone->lowmem_reserve[j] = managed_pages / ratio;
Linus Torvalds's avatar
Linus Torvalds committed
5647 5648 5649
			}
		}
	}
5650 5651 5652

	/* update totalreserve_pages */
	calculate_totalreserve_pages();
Linus Torvalds's avatar
Linus Torvalds committed
5653 5654
}

5655
static void __setup_per_zone_wmarks(void)
Linus Torvalds's avatar
Linus Torvalds committed
5656 5657 5658 5659 5660 5661
{
	unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
	unsigned long lowmem_pages = 0;
	struct zone *zone;
	unsigned long flags;

5662
	/* Calculate total number of !ZONE_HIGHMEM and !ZONE_MOVABLE pages */
Linus Torvalds's avatar
Linus Torvalds committed
5663
	for_each_zone(zone) {
5664
		if (!is_highmem(zone) && zone_idx(zone) != ZONE_MOVABLE)
5665
			lowmem_pages += zone_managed_pages(zone);
Linus Torvalds's avatar
Linus Torvalds committed
5666 5667 5668
	}

	for_each_zone(zone) {
5669 5670
		u64 tmp;

5671
		spin_lock_irqsave(&zone->lock, flags);
5672
		tmp = (u64)pages_min * zone_managed_pages(zone);
5673
		do_div(tmp, lowmem_pages);
5674
		if (is_highmem(zone) || zone_idx(zone) == ZONE_MOVABLE) {
Linus Torvalds's avatar
Linus Torvalds committed
5675
			/*
Nick Piggin's avatar
Nick Piggin committed
5676
			 * __GFP_HIGH and PF_MEMALLOC allocations usually don't
5677 5678
			 * need highmem and movable zones pages, so cap pages_min
			 * to a small  value here.
Nick Piggin's avatar
Nick Piggin committed
5679
			 *
5680
			 * The WMARK_HIGH-WMARK_LOW and (WMARK_LOW-WMARK_MIN)
5681
			 * deltas control async page reclaim, and so should
5682
			 * not be capped for highmem and movable zones.
Linus Torvalds's avatar
Linus Torvalds committed
5683
			 */
5684
			unsigned long min_pages;
Linus Torvalds's avatar
Linus Torvalds committed
5685

5686
			min_pages = zone_managed_pages(zone) / 1024;
5687
			min_pages = clamp(min_pages, SWAP_CLUSTER_MAX, 128UL);
5688
			zone->_watermark[WMARK_MIN] = min_pages;
Linus Torvalds's avatar
Linus Torvalds committed
5689
		} else {
Nick Piggin's avatar
Nick Piggin committed
5690 5691
			/*
			 * If it's a lowmem zone, reserve a number of pages
Linus Torvalds's avatar
Linus Torvalds committed
5692 5693
			 * proportionate to the zone's size.
			 */
5694
			zone->_watermark[WMARK_MIN] = tmp;
Linus Torvalds's avatar
Linus Torvalds committed
5695 5696
		}

5697 5698 5699 5700 5701 5702
		/*
		 * 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,
5703
			    mult_frac(zone_managed_pages(zone),
5704 5705
				      watermark_scale_factor, 10000));

5706
		zone->watermark_boost = 0;
5707
		zone->_watermark[WMARK_LOW]  = min_wmark_pages(zone) + tmp;
5708 5709
		zone->_watermark[WMARK_HIGH] = low_wmark_pages(zone) + tmp;
		zone->_watermark[WMARK_PROMO] = high_wmark_pages(zone) + tmp;
5710

5711
		spin_unlock_irqrestore(&zone->lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
5712
	}
5713 5714 5715

	/* update totalreserve_pages */
	calculate_totalreserve_pages();
Linus Torvalds's avatar
Linus Torvalds committed
5716 5717
}

5718 5719 5720 5721 5722 5723 5724 5725 5726
/**
 * 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)
{
5727
	struct zone *zone;
5728 5729 5730
	static DEFINE_SPINLOCK(lock);

	spin_lock(&lock);
5731
	__setup_per_zone_wmarks();
5732
	spin_unlock(&lock);
5733 5734 5735 5736 5737 5738

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

Linus Torvalds's avatar
Linus Torvalds committed
5742 5743 5744 5745
/*
 * Initialise min_free_kbytes.
 *
 * For small machines we want it small (128k min).  For large machines
5746
 * we want it large (256MB max).  But it is not linear, because network
Linus Torvalds's avatar
Linus Torvalds committed
5747 5748
 * bandwidth does not increase linearly with machine size.  We use
 *
5749
 *	min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
Linus Torvalds's avatar
Linus Torvalds committed
5750 5751 5752 5753 5754 5755 5756 5757 5758 5759 5760 5761 5762 5763 5764 5765
 *	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
 */
5766
void calculate_min_free_kbytes(void)
Linus Torvalds's avatar
Linus Torvalds committed
5767 5768
{
	unsigned long lowmem_kbytes;
5769
	int new_min_free_kbytes;
Linus Torvalds's avatar
Linus Torvalds committed
5770 5771

	lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
5772 5773
	new_min_free_kbytes = int_sqrt(lowmem_kbytes * 16);

5774 5775 5776
	if (new_min_free_kbytes > user_min_free_kbytes)
		min_free_kbytes = clamp(new_min_free_kbytes, 128, 262144);
	else
5777 5778
		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);
5779

5780 5781 5782 5783 5784
}

int __meminit init_per_zone_wmark_min(void)
{
	calculate_min_free_kbytes();
5785
	setup_per_zone_wmarks();
5786
	refresh_zone_stat_thresholds();
Linus Torvalds's avatar
Linus Torvalds committed
5787
	setup_per_zone_lowmem_reserve();
5788 5789 5790 5791 5792 5793

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

5794 5795
	khugepaged_min_free_kbytes_update();

Linus Torvalds's avatar
Linus Torvalds committed
5796 5797
	return 0;
}
5798
postcore_initcall(init_per_zone_wmark_min)
Linus Torvalds's avatar
Linus Torvalds committed
5799 5800

/*
5801
 * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
Linus Torvalds's avatar
Linus Torvalds committed
5802 5803 5804
 *	that we can call two helper functions whenever min_free_kbytes
 *	changes.
 */
5805
static int min_free_kbytes_sysctl_handler(struct ctl_table *table, int write,
5806
		void *buffer, size_t *length, loff_t *ppos)
Linus Torvalds's avatar
Linus Torvalds committed
5807
{
5808 5809 5810 5811 5812 5813
	int rc;

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

5814 5815
	if (write) {
		user_min_free_kbytes = min_free_kbytes;
5816
		setup_per_zone_wmarks();
5817
	}
Linus Torvalds's avatar
Linus Torvalds committed
5818 5819 5820
	return 0;
}

5821
static int watermark_scale_factor_sysctl_handler(struct ctl_table *table, int write,
5822
		void *buffer, size_t *length, loff_t *ppos)
5823 5824 5825 5826 5827 5828 5829 5830 5831 5832 5833 5834 5835
{
	int rc;

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

	if (write)
		setup_per_zone_wmarks();

	return 0;
}

5836
#ifdef CONFIG_NUMA
5837
static void setup_min_unmapped_ratio(void)
5838
{
5839
	pg_data_t *pgdat;
5840 5841
	struct zone *zone;

5842
	for_each_online_pgdat(pgdat)
5843
		pgdat->min_unmapped_pages = 0;
5844

5845
	for_each_zone(zone)
5846 5847
		zone->zone_pgdat->min_unmapped_pages += (zone_managed_pages(zone) *
						         sysctl_min_unmapped_ratio) / 100;
5848
}
5849

5850

5851
static int sysctl_min_unmapped_ratio_sysctl_handler(struct ctl_table *table, int write,
5852
		void *buffer, size_t *length, loff_t *ppos)
5853 5854 5855
{
	int rc;

5856
	rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
5857 5858 5859
	if (rc)
		return rc;

5860 5861 5862 5863 5864 5865 5866 5867 5868 5869
	setup_min_unmapped_ratio();

	return 0;
}

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

5870 5871 5872
	for_each_online_pgdat(pgdat)
		pgdat->min_slab_pages = 0;

5873
	for_each_zone(zone)
5874 5875
		zone->zone_pgdat->min_slab_pages += (zone_managed_pages(zone) *
						     sysctl_min_slab_ratio) / 100;
5876 5877
}

5878
static int sysctl_min_slab_ratio_sysctl_handler(struct ctl_table *table, int write,
5879
		void *buffer, size_t *length, loff_t *ppos)
5880 5881 5882 5883 5884 5885 5886 5887 5888
{
	int rc;

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

	setup_min_slab_ratio();

5889 5890
	return 0;
}
5891 5892
#endif

Linus Torvalds's avatar
Linus Torvalds committed
5893 5894 5895 5896 5897 5898
/*
 * 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
5899
 * minimum watermarks. The lowmem reserve ratio can only make sense
Linus Torvalds's avatar
Linus Torvalds committed
5900 5901
 * if in function of the boot time zone sizes.
 */
5902 5903
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
5904
{
5905 5906
	int i;

5907
	proc_dointvec_minmax(table, write, buffer, length, ppos);
5908 5909 5910 5911 5912 5913

	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
5914 5915 5916 5917
	setup_per_zone_lowmem_reserve();
	return 0;
}

5918
/*
5919 5920
 * 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
5921
 * pagelist can have before it gets flushed back to buddy allocator.
5922
 */
5923
static int percpu_pagelist_high_fraction_sysctl_handler(struct ctl_table *table,
5924
		int write, void *buffer, size_t *length, loff_t *ppos)
5925 5926
{
	struct zone *zone;
5927
	int old_percpu_pagelist_high_fraction;
5928 5929
	int ret;

5930
	mutex_lock(&pcp_batch_high_lock);
5931
	old_percpu_pagelist_high_fraction = percpu_pagelist_high_fraction;
5932

5933
	ret = proc_dointvec_minmax(table, write, buffer, length, ppos);
5934 5935 5936 5937
	if (!write || ret < 0)
		goto out;

	/* Sanity checking to avoid pcp imbalance */
5938 5939 5940
	if (percpu_pagelist_high_fraction &&
	    percpu_pagelist_high_fraction < MIN_PERCPU_PAGELIST_HIGH_FRACTION) {
		percpu_pagelist_high_fraction = old_percpu_pagelist_high_fraction;
5941 5942 5943 5944 5945
		ret = -EINVAL;
		goto out;
	}

	/* No change? */
5946
	if (percpu_pagelist_high_fraction == old_percpu_pagelist_high_fraction)
5947
		goto out;
5948

5949
	for_each_populated_zone(zone)
5950
		zone_set_pageset_high_and_batch(zone, 0);
5951
out:
5952
	mutex_unlock(&pcp_batch_high_lock);
5953
	return ret;
5954 5955
}

5956 5957 5958 5959 5960 5961 5962 5963 5964 5965 5966 5967 5968 5969 5970 5971 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 5985 5986 5987 5988 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
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);
}

6032
#ifdef CONFIG_CONTIG_ALLOC
6033 6034 6035 6036 6037 6038 6039 6040 6041 6042 6043 6044 6045 6046
/* 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");
	}
}

6047
/* [start, end) must belong to a single zone. */
6048
int __alloc_contig_migrate_range(struct compact_control *cc,
6049
					unsigned long start, unsigned long end)
6050 6051
{
	/* This function is based on compact_zone() from compaction.c. */
6052
	unsigned int nr_reclaimed;
6053 6054 6055
	unsigned long pfn = start;
	unsigned int tries = 0;
	int ret = 0;
6056 6057 6058 6059
	struct migration_target_control mtc = {
		.nid = zone_to_nid(cc->zone),
		.gfp_mask = GFP_USER | __GFP_MOVABLE | __GFP_RETRY_MAYFAIL,
	};
6060

6061
	lru_cache_disable();
6062

6063
	while (pfn < end || !list_empty(&cc->migratepages)) {
6064 6065 6066 6067 6068
		if (fatal_signal_pending(current)) {
			ret = -EINTR;
			break;
		}

6069 6070
		if (list_empty(&cc->migratepages)) {
			cc->nr_migratepages = 0;
6071 6072
			ret = isolate_migratepages_range(cc, pfn, end);
			if (ret && ret != -EAGAIN)
6073
				break;
6074
			pfn = cc->migrate_pfn;
6075 6076
			tries = 0;
		} else if (++tries == 5) {
6077
			ret = -EBUSY;
6078 6079 6080
			break;
		}

6081 6082 6083
		nr_reclaimed = reclaim_clean_pages_from_list(cc->zone,
							&cc->migratepages);
		cc->nr_migratepages -= nr_reclaimed;
6084

6085
		ret = migrate_pages(&cc->migratepages, alloc_migration_target,
6086
			NULL, (unsigned long)&mtc, cc->mode, MR_CONTIG_RANGE, NULL);
6087 6088 6089 6090 6091 6092 6093

		/*
		 * 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;
6094
	}
6095

6096
	lru_cache_enable();
6097
	if (ret < 0) {
6098
		if (!(cc->gfp_mask & __GFP_NOWARN) && ret == -EBUSY)
6099
			alloc_contig_dump_pages(&cc->migratepages);
6100 6101 6102 6103
		putback_movable_pages(&cc->migratepages);
		return ret;
	}
	return 0;
6104 6105 6106 6107 6108 6109
}

/**
 * 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
6110
 * @migratetype:	migratetype of the underlying pageblocks (either
6111 6112 6113
 *			#MIGRATE_MOVABLE or #MIGRATE_CMA).  All pageblocks
 *			in range must have the same migratetype and it must
 *			be either of the two.
6114
 * @gfp_mask:	GFP mask to use during compaction
6115
 *
6116 6117
 * The PFN range does not have to be pageblock aligned. The PFN range must
 * belong to a single zone.
6118
 *
6119 6120 6121
 * 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.
6122
 *
6123
 * Return: zero on success or negative error code.  On success all
6124 6125 6126
 * pages which PFN is in [start, end) are allocated for the caller and
 * need to be freed with free_contig_range().
 */
6127
int alloc_contig_range(unsigned long start, unsigned long end,
6128
		       unsigned migratetype, gfp_t gfp_mask)
6129 6130
{
	unsigned long outer_start, outer_end;
6131
	int order;
6132
	int ret = 0;
6133

6134 6135 6136 6137
	struct compact_control cc = {
		.nr_migratepages = 0,
		.order = -1,
		.zone = page_zone(pfn_to_page(start)),
6138
		.mode = MIGRATE_SYNC,
6139
		.ignore_skip_hint = true,
6140
		.no_set_skip_hint = true,
6141
		.gfp_mask = current_gfp_context(gfp_mask),
6142
		.alloc_contig = true,
6143 6144 6145
	};
	INIT_LIST_HEAD(&cc.migratepages);

6146 6147 6148 6149
	/*
	 * 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
6150
	 * work, start_isolate_page_range() has special handlings for this.
6151 6152 6153
	 *
	 * Once the pageblocks are marked as MIGRATE_ISOLATE, we
	 * migrate the pages from an unaligned range (ie. pages that
6154
	 * we are interested in). This will put all the pages in
6155 6156 6157 6158 6159 6160 6161 6162 6163 6164 6165 6166
	 * 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.
	 */

6167
	ret = start_isolate_page_range(start, end, migratetype, 0, gfp_mask);
6168
	if (ret)
6169
		goto done;
6170

6171 6172
	drain_all_pages(cc.zone);

6173 6174
	/*
	 * In case of -EBUSY, we'd like to know which page causes problem.
6175 6176 6177 6178 6179 6180 6181
	 * 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.
6182
	 */
6183
	ret = __alloc_contig_migrate_range(&cc, start, end);
6184
	if (ret && ret != -EBUSY)
6185
		goto done;
6186
	ret = 0;
6187 6188

	/*
6189
	 * Pages from [start, end) are within a pageblock_nr_pages
6190 6191 6192 6193 6194 6195 6196 6197 6198 6199 6200 6201 6202 6203 6204 6205 6206 6207
	 * 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))) {
6208
		if (++order > MAX_ORDER) {
6209 6210
			outer_start = start;
			break;
6211 6212 6213 6214
		}
		outer_start &= ~0UL << order;
	}

6215
	if (outer_start != start) {
6216
		order = buddy_order(pfn_to_page(outer_start));
6217 6218 6219 6220 6221 6222 6223 6224 6225 6226 6227

		/*
		 * 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;
	}

6228
	/* Make sure the range is really isolated. */
6229
	if (test_pages_isolated(outer_start, end, 0)) {
6230 6231 6232 6233
		ret = -EBUSY;
		goto done;
	}

6234
	/* Grab isolated pages from freelists. */
6235
	outer_end = isolate_freepages_range(&cc, outer_start, end);
6236 6237 6238 6239 6240 6241 6242 6243 6244 6245 6246 6247
	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:
6248
	undo_isolate_page_range(start, end, migratetype);
6249 6250
	return ret;
}
6251
EXPORT_SYMBOL(alloc_contig_range);
6252 6253 6254 6255 6256 6257 6258 6259 6260 6261 6262 6263 6264 6265 6266 6267 6268 6269 6270 6271 6272 6273 6274 6275 6276

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))
6277 6278 6279
			return false;

		if (PageHuge(page))
6280 6281 6282 6283 6284 6285 6286 6287 6288 6289 6290 6291 6292 6293 6294 6295 6296 6297 6298 6299 6300 6301 6302 6303 6304 6305
			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
6306 6307
 * 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).
6308 6309 6310 6311 6312 6313 6314 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 6341 6342 6343 6344 6345 6346 6347 6348 6349
 *
 * 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;
}
6350
#endif /* CONFIG_CONTIG_ALLOC */
6351

6352
void free_contig_range(unsigned long pfn, unsigned long nr_pages)
6353
{
6354
	unsigned long count = 0;
6355 6356 6357 6358 6359 6360 6361

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

		count += page_count(page) != 1;
		__free_page(page);
	}
6362
	WARN(count != 0, "%lu pages are still in use!\n", count);
6363
}
6364
EXPORT_SYMBOL(free_contig_range);
6365

6366 6367 6368 6369 6370 6371 6372 6373 6374 6375 6376 6377 6378 6379 6380 6381 6382 6383 6384 6385 6386
/*
 * 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);
}

6387 6388
void zone_pcp_reset(struct zone *zone)
{
6389
	int cpu;
6390
	struct per_cpu_zonestat *pzstats;
6391

6392
	if (zone->per_cpu_pageset != &boot_pageset) {
6393
		for_each_online_cpu(cpu) {
6394 6395
			pzstats = per_cpu_ptr(zone->per_cpu_zonestats, cpu);
			drain_zonestat(zone, pzstats);
6396
		}
6397 6398
		free_percpu(zone->per_cpu_pageset);
		zone->per_cpu_pageset = &boot_pageset;
6399 6400 6401 6402
		if (zone->per_cpu_zonestats != &boot_zonestats) {
			free_percpu(zone->per_cpu_zonestats);
			zone->per_cpu_zonestats = &boot_zonestats;
		}
6403 6404 6405
	}
}

6406
#ifdef CONFIG_MEMORY_HOTREMOVE
6407
/*
6408 6409
 * 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.
6410
 */
6411
void __offline_isolated_pages(unsigned long start_pfn, unsigned long end_pfn)
6412
{
6413
	unsigned long pfn = start_pfn;
6414 6415
	struct page *page;
	struct zone *zone;
6416
	unsigned int order;
6417
	unsigned long flags;
6418

6419
	offline_mem_sections(pfn, end_pfn);
6420 6421 6422 6423
	zone = page_zone(pfn_to_page(pfn));
	spin_lock_irqsave(&zone->lock, flags);
	while (pfn < end_pfn) {
		page = pfn_to_page(pfn);
6424 6425 6426 6427 6428 6429 6430 6431
		/*
		 * The HWPoisoned page may be not in buddy system, and
		 * page_count() is not 0.
		 */
		if (unlikely(!PageBuddy(page) && PageHWPoison(page))) {
			pfn++;
			continue;
		}
6432 6433 6434 6435 6436 6437 6438 6439 6440 6441
		/*
		 * 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;
		}
6442

6443 6444
		BUG_ON(page_count(page));
		BUG_ON(!PageBuddy(page));
6445
		order = buddy_order(page);
6446
		del_page_from_free_list(page, zone, order);
6447 6448 6449 6450 6451
		pfn += (1 << order);
	}
	spin_unlock_irqrestore(&zone->lock, flags);
}
#endif
6452

6453 6454 6455
/*
 * This function returns a stable result only if called under zone lock.
 */
6456 6457 6458
bool is_free_buddy_page(struct page *page)
{
	unsigned long pfn = page_to_pfn(page);
6459
	unsigned int order;
6460

6461
	for (order = 0; order <= MAX_ORDER; order++) {
6462 6463
		struct page *page_head = page - (pfn & ((1 << order) - 1));

6464 6465
		if (PageBuddy(page_head) &&
		    buddy_order_unsafe(page_head) >= order)
6466 6467 6468
			break;
	}

6469
	return order <= MAX_ORDER;
6470
}
6471
EXPORT_SYMBOL(is_free_buddy_page);
6472 6473 6474

#ifdef CONFIG_MEMORY_FAILURE
/*
6475 6476
 * Break down a higher-order page in sub-pages, and keep our target out of
 * buddy allocator.
6477
 */
6478 6479 6480 6481 6482 6483 6484 6485 6486 6487 6488 6489 6490 6491 6492 6493 6494 6495 6496 6497 6498 6499 6500 6501
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);
6502
			set_buddy_order(current_buddy, high);
6503 6504 6505 6506 6507 6508 6509 6510 6511
			page = next_page;
		}
	}
}

/*
 * Take a page that will be marked as poisoned off the buddy allocator.
 */
bool take_page_off_buddy(struct page *page)
6512 6513 6514 6515 6516
{
	struct zone *zone = page_zone(page);
	unsigned long pfn = page_to_pfn(page);
	unsigned long flags;
	unsigned int order;
6517
	bool ret = false;
6518 6519

	spin_lock_irqsave(&zone->lock, flags);
6520
	for (order = 0; order <= MAX_ORDER; order++) {
6521
		struct page *page_head = page - (pfn & ((1 << order) - 1));
6522
		int page_order = buddy_order(page_head);
6523

6524
		if (PageBuddy(page_head) && page_order >= order) {
6525 6526 6527 6528
			unsigned long pfn_head = page_to_pfn(page_head);
			int migratetype = get_pfnblock_migratetype(page_head,
								   pfn_head);

6529
			del_page_from_free_list(page_head, zone, page_order);
6530
			break_down_buddy_pages(zone, page_head, page, 0,
6531
						page_order, migratetype);
6532
			SetPageHWPoisonTakenOff(page);
6533 6534
			if (!is_migrate_isolate(migratetype))
				__mod_zone_freepage_state(zone, -1, migratetype);
6535
			ret = true;
6536 6537
			break;
		}
6538 6539
		if (page_count(page_head) > 0)
			break;
6540 6541
	}
	spin_unlock_irqrestore(&zone->lock, flags);
6542
	return ret;
6543
}
6544 6545 6546 6547 6548 6549 6550 6551 6552 6553 6554 6555 6556 6557 6558 6559 6560 6561 6562 6563 6564 6565 6566 6567

/*
 * 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;
}
6568
#endif
6569 6570 6571 6572 6573 6574 6575 6576 6577 6578 6579 6580 6581 6582 6583

#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 */
6584 6585 6586 6587 6588 6589 6590 6591 6592 6593 6594 6595 6596 6597 6598 6599 6600 6601 6602 6603 6604 6605 6606 6607 6608 6609 6610 6611 6612 6613 6614 6615 6616 6617 6618 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

#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 */