page_alloc.c 220 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 *  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>
#include <linux/swap.h>
#include <linux/interrupt.h>
#include <linux/pagemap.h>
22
#include <linux/jiffies.h>
Linus Torvalds's avatar
Linus Torvalds committed
23
#include <linux/bootmem.h>
24
#include <linux/memblock.h>
Linus Torvalds's avatar
Linus Torvalds committed
25
#include <linux/compiler.h>
26
#include <linux/kernel.h>
27
#include <linux/kasan.h>
Linus Torvalds's avatar
Linus Torvalds committed
28
29
30
31
32
#include <linux/module.h>
#include <linux/suspend.h>
#include <linux/pagevec.h>
#include <linux/blkdev.h>
#include <linux/slab.h>
33
#include <linux/ratelimit.h>
34
#include <linux/oom.h>
Linus Torvalds's avatar
Linus Torvalds committed
35
36
37
38
39
#include <linux/notifier.h>
#include <linux/topology.h>
#include <linux/sysctl.h>
#include <linux/cpu.h>
#include <linux/cpuset.h>
40
#include <linux/memory_hotplug.h>
Linus Torvalds's avatar
Linus Torvalds committed
41
42
#include <linux/nodemask.h>
#include <linux/vmalloc.h>
43
#include <linux/vmstat.h>
44
#include <linux/mempolicy.h>
45
#include <linux/memremap.h>
46
#include <linux/stop_machine.h>
47
48
#include <linux/sort.h>
#include <linux/pfn.h>
49
#include <linux/backing-dev.h>
50
#include <linux/fault-inject.h>
51
#include <linux/page-isolation.h>
52
#include <linux/page_ext.h>
53
#include <linux/debugobjects.h>
54
#include <linux/kmemleak.h>
55
#include <linux/compaction.h>
56
#include <trace/events/kmem.h>
57
#include <trace/events/oom.h>
58
#include <linux/prefetch.h>
59
#include <linux/mm_inline.h>
60
#include <linux/migrate.h>
61
#include <linux/hugetlb.h>
62
#include <linux/sched/rt.h>
63
#include <linux/sched/mm.h>
64
#include <linux/page_owner.h>
65
#include <linux/kthread.h>
66
#include <linux/memcontrol.h>
67
#include <linux/ftrace.h>
68
#include <linux/lockdep.h>
69
#include <linux/nmi.h>
Linus Torvalds's avatar
Linus Torvalds committed
70

71
#include <asm/sections.h>
Linus Torvalds's avatar
Linus Torvalds committed
72
#include <asm/tlbflush.h>
73
#include <asm/div64.h>
Linus Torvalds's avatar
Linus Torvalds committed
74
75
#include "internal.h"

76
77
/* prevent >1 _updater_ of zone percpu pageset ->high and ->batch fields */
static DEFINE_MUTEX(pcp_batch_high_lock);
78
#define MIN_PERCPU_PAGELIST_FRACTION	(8)
79

80
81
82
83
84
#ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
DEFINE_PER_CPU(int, numa_node);
EXPORT_PER_CPU_SYMBOL(numa_node);
#endif

85
86
DEFINE_STATIC_KEY_TRUE(vm_numa_stat_key);

87
88
89
90
91
92
93
94
95
#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_);
96
int _node_numa_mem_[MAX_NUMNODES];
97
98
#endif

99
100
101
102
/* work_structs for global per-cpu drains */
DEFINE_MUTEX(pcpu_drain_mutex);
DEFINE_PER_CPU(struct work_struct, pcpu_drain);

103
#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
104
volatile unsigned long latent_entropy __latent_entropy;
105
106
107
EXPORT_SYMBOL(latent_entropy);
#endif

Linus Torvalds's avatar
Linus Torvalds committed
108
/*
109
 * Array of node states.
Linus Torvalds's avatar
Linus Torvalds committed
110
 */
111
112
113
114
115
116
117
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 } },
118
119
#endif
	[N_MEMORY] = { { [0] = 1UL } },
120
121
122
123
124
	[N_CPU] = { { [0] = 1UL } },
#endif	/* NUMA */
};
EXPORT_SYMBOL(node_states);

125
126
127
/* Protect totalram_pages and zone->managed_pages */
static DEFINE_SPINLOCK(managed_page_count_lock);

128
unsigned long totalram_pages __read_mostly;
129
unsigned long totalreserve_pages __read_mostly;
130
unsigned long totalcma_pages __read_mostly;
131

132
int percpu_pagelist_fraction;
133
gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
Linus Torvalds's avatar
Linus Torvalds committed
134

135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/*
 * 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;
}

153
154
155
156
157
158
159
160
161
#ifdef CONFIG_PM_SLEEP
/*
 * The following functions are used by the suspend/hibernate code to temporarily
 * change gfp_allowed_mask in order to avoid using I/O during memory allocations
 * while devices are suspended.  To avoid races with the suspend/hibernate code,
 * they should always be called with pm_mutex held (gfp_allowed_mask also should
 * only be modified with pm_mutex held, unless the suspend/hibernate code is
 * guaranteed not to run in parallel with that modification).
 */
162
163
164
165

static gfp_t saved_gfp_mask;

void pm_restore_gfp_mask(void)
166
167
{
	WARN_ON(!mutex_is_locked(&pm_mutex));
168
169
170
171
	if (saved_gfp_mask) {
		gfp_allowed_mask = saved_gfp_mask;
		saved_gfp_mask = 0;
	}
172
173
}

174
void pm_restrict_gfp_mask(void)
175
176
{
	WARN_ON(!mutex_is_locked(&pm_mutex));
177
178
	WARN_ON(saved_gfp_mask);
	saved_gfp_mask = gfp_allowed_mask;
179
	gfp_allowed_mask &= ~(__GFP_IO | __GFP_FS);
180
}
181
182
183

bool pm_suspended_storage(void)
{
184
	if ((gfp_allowed_mask & (__GFP_IO | __GFP_FS)) == (__GFP_IO | __GFP_FS))
185
186
187
		return false;
	return true;
}
188
189
#endif /* CONFIG_PM_SLEEP */

190
#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
191
unsigned int pageblock_order __read_mostly;
192
193
#endif

194
static void __free_pages_ok(struct page *page, unsigned int order);
195

Linus Torvalds's avatar
Linus Torvalds committed
196
197
198
199
200
201
/*
 * 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
202
 *	HIGHMEM allocation will leave (224M+784M)/256 of ram reserved in ZONE_DMA
203
204
205
 *
 * 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
206
 */
207
int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES] = {
208
#ifdef CONFIG_ZONE_DMA
209
	[ZONE_DMA] = 256,
210
#endif
211
#ifdef CONFIG_ZONE_DMA32
212
	[ZONE_DMA32] = 256,
213
#endif
214
	[ZONE_NORMAL] = 32,
215
#ifdef CONFIG_HIGHMEM
216
	[ZONE_HIGHMEM] = 0,
217
#endif
218
	[ZONE_MOVABLE] = 0,
219
};
Linus Torvalds's avatar
Linus Torvalds committed
220
221
222

EXPORT_SYMBOL(totalram_pages);

223
static char * const zone_names[MAX_NR_ZONES] = {
224
#ifdef CONFIG_ZONE_DMA
225
	 "DMA",
226
#endif
227
#ifdef CONFIG_ZONE_DMA32
228
	 "DMA32",
229
#endif
230
	 "Normal",
231
#ifdef CONFIG_HIGHMEM
Mel Gorman's avatar
Mel Gorman committed
232
	 "HighMem",
233
#endif
Mel Gorman's avatar
Mel Gorman committed
234
	 "Movable",
235
236
237
#ifdef CONFIG_ZONE_DEVICE
	 "Device",
#endif
238
239
};

240
241
242
243
244
245
246
247
248
249
250
251
252
char * const migratetype_names[MIGRATE_TYPES] = {
	"Unmovable",
	"Movable",
	"Reclaimable",
	"HighAtomic",
#ifdef CONFIG_CMA
	"CMA",
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	"Isolate",
#endif
};

253
254
255
256
257
258
compound_page_dtor * const compound_page_dtors[] = {
	NULL,
	free_compound_page,
#ifdef CONFIG_HUGETLB_PAGE
	free_huge_page,
#endif
259
260
261
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
	free_transhuge_page,
#endif
262
263
};

Linus Torvalds's avatar
Linus Torvalds committed
264
int min_free_kbytes = 1024;
265
int user_min_free_kbytes = -1;
266
int watermark_scale_factor = 10;
Linus Torvalds's avatar
Linus Torvalds committed
267

268
269
270
static unsigned long nr_kernel_pages __meminitdata;
static unsigned long nr_all_pages __meminitdata;
static unsigned long dma_reserve __meminitdata;
Linus Torvalds's avatar
Linus Torvalds committed
271

Tejun Heo's avatar
Tejun Heo committed
272
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
273
274
275
static unsigned long arch_zone_lowest_possible_pfn[MAX_NR_ZONES] __meminitdata;
static unsigned long arch_zone_highest_possible_pfn[MAX_NR_ZONES] __meminitdata;
static unsigned long required_kernelcore __initdata;
276
static unsigned long required_kernelcore_percent __initdata;
277
static unsigned long required_movablecore __initdata;
278
static unsigned long required_movablecore_percent __initdata;
279
280
static unsigned long zone_movable_pfn[MAX_NUMNODES] __meminitdata;
static bool mirrored_kernelcore __meminitdata;
Tejun Heo's avatar
Tejun Heo committed
281
282
283
284
285

/* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
int movable_zone;
EXPORT_SYMBOL(movable_zone);
#endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
286

Miklos Szeredi's avatar
Miklos Szeredi committed
287
288
#if MAX_NUMNODES > 1
int nr_node_ids __read_mostly = MAX_NUMNODES;
289
int nr_online_nodes __read_mostly = 1;
Miklos Szeredi's avatar
Miklos Szeredi committed
290
EXPORT_SYMBOL(nr_node_ids);
291
EXPORT_SYMBOL(nr_online_nodes);
Miklos Szeredi's avatar
Miklos Szeredi committed
292
293
#endif

294
295
int page_group_by_mobility_disabled __read_mostly;

296
297
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
/* Returns true if the struct page for the pfn is uninitialised */
298
static inline bool __meminit early_page_uninitialised(unsigned long pfn)
299
{
300
301
302
	int nid = early_pfn_to_nid(pfn);

	if (node_online(nid) && pfn >= NODE_DATA(nid)->first_deferred_pfn)
303
304
305
306
307
308
309
310
311
312
313
314
315
		return true;

	return false;
}

/*
 * Returns false when the remaining initialisation should be deferred until
 * later in the boot cycle when it can be parallelised.
 */
static inline bool update_defer_init(pg_data_t *pgdat,
				unsigned long pfn, unsigned long zone_end,
				unsigned long *nr_initialised)
{
316
	/* Always populate low zones for address-constrained allocations */
317
318
319
	if (zone_end < pgdat_end_pfn(pgdat))
		return true;
	(*nr_initialised)++;
320
	if ((*nr_initialised > pgdat->static_init_pgcnt) &&
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
	    (pfn & (PAGES_PER_SECTION - 1)) == 0) {
		pgdat->first_deferred_pfn = pfn;
		return false;
	}

	return true;
}
#else
static inline bool early_page_uninitialised(unsigned long pfn)
{
	return false;
}

static inline bool update_defer_init(pg_data_t *pgdat,
				unsigned long pfn, unsigned long zone_end,
				unsigned long *nr_initialised)
{
	return true;
}
#endif

342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
/* Return a pointer to the bitmap storing bits affecting a block of pages */
static inline unsigned long *get_pageblock_bitmap(struct page *page,
							unsigned long pfn)
{
#ifdef CONFIG_SPARSEMEM
	return __pfn_to_section(pfn)->pageblock_flags;
#else
	return page_zone(page)->pageblock_flags;
#endif /* CONFIG_SPARSEMEM */
}

static inline int pfn_to_bitidx(struct page *page, unsigned long pfn)
{
#ifdef CONFIG_SPARSEMEM
	pfn &= (PAGES_PER_SECTION-1);
	return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
#else
	pfn = pfn - round_down(page_zone(page)->zone_start_pfn, pageblock_nr_pages);
	return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
#endif /* CONFIG_SPARSEMEM */
}

/**
 * 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
 * @end_bitidx: The last bit of interest to retrieve
 * @mask: mask of bits that the caller is interested in
 *
 * Return: pageblock_bits flags
 */
static __always_inline unsigned long __get_pfnblock_flags_mask(struct page *page,
					unsigned long pfn,
					unsigned long end_bitidx,
					unsigned long mask)
{
	unsigned long *bitmap;
	unsigned long bitidx, word_bitidx;
	unsigned long word;

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

	word = bitmap[word_bitidx];
	bitidx += end_bitidx;
	return (word >> (BITS_PER_LONG - bitidx - 1)) & mask;
}

unsigned long get_pfnblock_flags_mask(struct page *page, unsigned long pfn,
					unsigned long end_bitidx,
					unsigned long mask)
{
	return __get_pfnblock_flags_mask(page, pfn, end_bitidx, mask);
}

static __always_inline int get_pfnblock_migratetype(struct page *page, unsigned long pfn)
{
	return __get_pfnblock_flags_mask(page, pfn, PB_migrate_end, MIGRATETYPE_MASK);
}

/**
 * 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
 * @end_bitidx: The last bit of interest
 * @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 end_bitidx,
					unsigned long mask)
{
	unsigned long *bitmap;
	unsigned long bitidx, word_bitidx;
	unsigned long old_word, word;

	BUILD_BUG_ON(NR_PAGEBLOCK_BITS != 4);

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

	bitidx += end_bitidx;
	mask <<= (BITS_PER_LONG - bitidx - 1);
	flags <<= (BITS_PER_LONG - bitidx - 1);

	word = READ_ONCE(bitmap[word_bitidx]);
	for (;;) {
		old_word = cmpxchg(&bitmap[word_bitidx], word, (word & ~mask) | flags);
		if (word == old_word)
			break;
		word = old_word;
	}
}
442

443
void set_pageblock_migratetype(struct page *page, int migratetype)
444
{
445
446
	if (unlikely(page_group_by_mobility_disabled &&
		     migratetype < MIGRATE_PCPTYPES))
447
448
		migratetype = MIGRATE_UNMOVABLE;

449
450
451
452
	set_pageblock_flags_group(page, (unsigned long)migratetype,
					PB_migrate, PB_migrate_end);
}

Nick Piggin's avatar
Nick Piggin committed
453
#ifdef CONFIG_DEBUG_VM
454
static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
455
{
456
457
458
	int ret = 0;
	unsigned seq;
	unsigned long pfn = page_to_pfn(page);
459
	unsigned long sp, start_pfn;
460

461
462
	do {
		seq = zone_span_seqbegin(zone);
463
464
		start_pfn = zone->zone_start_pfn;
		sp = zone->spanned_pages;
465
		if (!zone_spans_pfn(zone, pfn))
466
467
468
			ret = 1;
	} while (zone_span_seqretry(zone, seq));

469
	if (ret)
470
471
472
		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);
473

474
	return ret;
475
476
477
478
}

static int page_is_consistent(struct zone *zone, struct page *page)
{
479
	if (!pfn_valid_within(page_to_pfn(page)))
480
		return 0;
Linus Torvalds's avatar
Linus Torvalds committed
481
	if (zone != page_zone(page))
482
483
484
485
486
487
488
		return 0;

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

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

505
506
static void bad_page(struct page *page, const char *reason,
		unsigned long bad_flags)
Linus Torvalds's avatar
Linus Torvalds committed
507
{
508
509
510
511
512
513
514
515
516
517
518
519
520
521
	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) {
522
			pr_alert(
523
			      "BUG: Bad page state: %lu messages suppressed\n",
524
525
526
527
528
529
530
531
				nr_unshown);
			nr_unshown = 0;
		}
		nr_shown = 0;
	}
	if (nr_shown++ == 0)
		resume = jiffies + 60 * HZ;

532
	pr_alert("BUG: Bad page state in process %s  pfn:%05lx\n",
533
		current->comm, page_to_pfn(page));
534
535
536
537
538
	__dump_page(page, reason);
	bad_flags &= page->flags;
	if (bad_flags)
		pr_alert("bad because of flags: %#lx(%pGp)\n",
						bad_flags, &bad_flags);
539
	dump_page_owner(page);
540

541
	print_modules();
Linus Torvalds's avatar
Linus Torvalds committed
542
	dump_stack();
543
out:
544
	/* Leave bad fields for debug, except PageBuddy could make trouble */
545
	page_mapcount_reset(page); /* remove PageBuddy */
546
	add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE);
Linus Torvalds's avatar
Linus Torvalds committed
547
548
549
550
551
}

/*
 * Higher-order pages are called "compound pages".  They are structured thusly:
 *
552
 * The first PAGE_SIZE page is called the "head page" and have PG_head set.
Linus Torvalds's avatar
Linus Torvalds committed
553
 *
554
555
 * 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
556
 *
557
558
 * The first tail page's ->compound_dtor holds the offset in array of compound
 * page destructors. See compound_page_dtors.
Linus Torvalds's avatar
Linus Torvalds committed
559
 *
560
 * The first tail page's ->compound_order holds the order of allocation.
561
 * This usage means that zero-order pages may not be compound.
Linus Torvalds's avatar
Linus Torvalds committed
562
 */
563

564
void free_compound_page(struct page *page)
565
{
566
	__free_pages_ok(page, compound_order(page));
567
568
}

569
void prep_compound_page(struct page *page, unsigned int order)
570
571
572
573
{
	int i;
	int nr_pages = 1 << order;

574
	set_compound_page_dtor(page, COMPOUND_PAGE_DTOR);
575
576
577
578
	set_compound_order(page, order);
	__SetPageHead(page);
	for (i = 1; i < nr_pages; i++) {
		struct page *p = page + i;
579
		set_page_count(p, 0);
580
		p->mapping = TAIL_MAPPING;
581
		set_compound_head(p, page);
582
	}
583
	atomic_set(compound_mapcount_ptr(page), -1);
584
585
}

586
587
#ifdef CONFIG_DEBUG_PAGEALLOC
unsigned int _debug_guardpage_minorder;
588
589
bool _debug_pagealloc_enabled __read_mostly
			= IS_ENABLED(CONFIG_DEBUG_PAGEALLOC_ENABLE_DEFAULT);
590
EXPORT_SYMBOL(_debug_pagealloc_enabled);
591
592
bool _debug_guardpage_enabled __read_mostly;

593
594
595
596
static int __init early_debug_pagealloc(char *buf)
{
	if (!buf)
		return -EINVAL;
597
	return kstrtobool(buf, &_debug_pagealloc_enabled);
598
599
600
}
early_param("debug_pagealloc", early_debug_pagealloc);

601
602
static bool need_debug_guardpage(void)
{
603
604
605
606
	/* If we don't use debug_pagealloc, we don't need guard page */
	if (!debug_pagealloc_enabled())
		return false;

607
608
609
	if (!debug_guardpage_minorder())
		return false;

610
611
612
613
614
	return true;
}

static void init_debug_guardpage(void)
{
615
616
617
	if (!debug_pagealloc_enabled())
		return;

618
619
620
	if (!debug_guardpage_minorder())
		return;

621
622
623
624
625
626
627
	_debug_guardpage_enabled = true;
}

struct page_ext_operations debug_guardpage_ops = {
	.need = need_debug_guardpage,
	.init = init_debug_guardpage,
};
628
629
630
631
632
633

static int __init debug_guardpage_minorder_setup(char *buf)
{
	unsigned long res;

	if (kstrtoul(buf, 10, &res) < 0 ||  res > MAX_ORDER / 2) {
634
		pr_err("Bad debug_guardpage_minorder value\n");
635
636
637
		return 0;
	}
	_debug_guardpage_minorder = res;
638
	pr_info("Setting debug_guardpage_minorder to %lu\n", res);
639
640
	return 0;
}
641
early_param("debug_guardpage_minorder", debug_guardpage_minorder_setup);
642

643
static inline bool set_page_guard(struct zone *zone, struct page *page,
644
				unsigned int order, int migratetype)
645
{
646
647
648
	struct page_ext *page_ext;

	if (!debug_guardpage_enabled())
649
650
651
652
		return false;

	if (order >= debug_guardpage_minorder())
		return false;
653
654

	page_ext = lookup_page_ext(page);
655
	if (unlikely(!page_ext))
656
		return false;
657

658
659
	__set_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);

660
661
662
663
	INIT_LIST_HEAD(&page->lru);
	set_page_private(page, order);
	/* Guard pages are not available for any usage */
	__mod_zone_freepage_state(zone, -(1 << order), migratetype);
664
665

	return true;
666
667
}

668
669
static inline void clear_page_guard(struct zone *zone, struct page *page,
				unsigned int order, int migratetype)
670
{
671
672
673
674
675
676
	struct page_ext *page_ext;

	if (!debug_guardpage_enabled())
		return;

	page_ext = lookup_page_ext(page);
677
678
679
	if (unlikely(!page_ext))
		return;

680
681
	__clear_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);

682
683
684
	set_page_private(page, 0);
	if (!is_migrate_isolate(migratetype))
		__mod_zone_freepage_state(zone, (1 << order), migratetype);
685
686
}
#else
687
struct page_ext_operations debug_guardpage_ops;
688
689
static inline bool set_page_guard(struct zone *zone, struct page *page,
			unsigned int order, int migratetype) { return false; }
690
691
static inline void clear_page_guard(struct zone *zone, struct page *page,
				unsigned int order, int migratetype) {}
692
693
#endif

694
static inline void set_page_order(struct page *page, unsigned int order)
695
{
696
	set_page_private(page, order);
697
	__SetPageBuddy(page);
Linus Torvalds's avatar
Linus Torvalds committed
698
699
700
701
}

static inline void rmv_page_order(struct page *page)
{
702
	__ClearPageBuddy(page);
703
	set_page_private(page, 0);
Linus Torvalds's avatar
Linus Torvalds committed
704
705
706
707
708
}

/*
 * This function checks whether a page is free && is the buddy
 * we can do coalesce a page and its buddy if
709
 * (a) the buddy is not in a hole (check before calling!) &&
710
 * (b) the buddy is in the buddy system &&
711
712
 * (c) a page and its buddy have the same order &&
 * (d) a page and its buddy are in the same zone.
713
 *
714
715
716
717
 * For recording whether a page is in the buddy system, we set ->_mapcount
 * PAGE_BUDDY_MAPCOUNT_VALUE.
 * Setting, clearing, and testing _mapcount PAGE_BUDDY_MAPCOUNT_VALUE is
 * serialized by zone->lock.
Linus Torvalds's avatar
Linus Torvalds committed
718
 *
719
 * For recording page's order, we use page_private(page).
Linus Torvalds's avatar
Linus Torvalds committed
720
 */
721
static inline int page_is_buddy(struct page *page, struct page *buddy,
722
							unsigned int order)
Linus Torvalds's avatar
Linus Torvalds committed
723
{
724
	if (page_is_guard(buddy) && page_order(buddy) == order) {
725
726
727
		if (page_zone_id(page) != page_zone_id(buddy))
			return 0;

728
729
		VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);

730
731
732
		return 1;
	}

733
	if (PageBuddy(buddy) && page_order(buddy) == order) {
734
735
736
737
738
739
740
741
		/*
		 * zone check is done late to avoid uselessly
		 * calculating zone/node ids for pages that could
		 * never merge.
		 */
		if (page_zone_id(page) != page_zone_id(buddy))
			return 0;

742
743
		VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);

744
		return 1;
745
	}
746
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
}

/*
 * 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
762
763
764
 * free pages of length of (1 << order) and marked with _mapcount
 * PAGE_BUDDY_MAPCOUNT_VALUE. Page's order is recorded in page_private(page)
 * field.
Linus Torvalds's avatar
Linus Torvalds committed
765
 * So when we are allocating or freeing one, we can derive the state of the
766
767
 * 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
768
 * If a block is freed, and its buddy is also free, then this
769
 * triggers coalescing into a block of larger size.
Linus Torvalds's avatar
Linus Torvalds committed
770
 *
771
 * -- nyc
Linus Torvalds's avatar
Linus Torvalds committed
772
773
 */

Nick Piggin's avatar
Nick Piggin committed
774
static inline void __free_one_page(struct page *page,
775
		unsigned long pfn,
776
777
		struct zone *zone, unsigned int order,
		int migratetype)
Linus Torvalds's avatar
Linus Torvalds committed
778
{
779
780
	unsigned long combined_pfn;
	unsigned long uninitialized_var(buddy_pfn);
781
	struct page *buddy;
782
783
784
	unsigned int max_order;

	max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
Linus Torvalds's avatar
Linus Torvalds committed
785

786
	VM_BUG_ON(!zone_is_initialized(zone));
787
	VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);
Linus Torvalds's avatar
Linus Torvalds committed
788

789
	VM_BUG_ON(migratetype == -1);
790
	if (likely(!is_migrate_isolate(migratetype)))
791
		__mod_zone_freepage_state(zone, 1 << order, migratetype);
792

793
	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
794
	VM_BUG_ON_PAGE(bad_range(zone, page), page);
Linus Torvalds's avatar
Linus Torvalds committed
795

796
continue_merging:
797
	while (order < max_order - 1) {
798
799
		buddy_pfn = __find_buddy_pfn(pfn, order);
		buddy = page + (buddy_pfn - pfn);
800
801
802

		if (!pfn_valid_within(buddy_pfn))
			goto done_merging;
803
		if (!page_is_buddy(page, buddy, order))
804
			goto done_merging;
805
806
807
808
809
		/*
		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
		 * merge with it and move up one order.
		 */
		if (page_is_guard(buddy)) {
810
			clear_page_guard(zone, buddy, order, migratetype);
811
812
813
814
815
		} else {
			list_del(&buddy->lru);
			zone->free_area[order].nr_free--;
			rmv_page_order(buddy);
		}
816
817
818
		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
Linus Torvalds's avatar
Linus Torvalds committed
819
820
		order++;
	}
821
822
823
824
825
826
827
828
829
830
831
832
	if (max_order < MAX_ORDER) {
		/* If we are here, it means order is >= pageblock_order.
		 * We want to prevent merge between freepages on isolate
		 * pageblock and normal pageblock. Without this, pageblock
		 * isolation could cause incorrect freepage or CMA accounting.
		 *
		 * We don't want to hit this code for the more frequent
		 * low-order merging.
		 */
		if (unlikely(has_isolate_pageblock(zone))) {
			int buddy_mt;

833
834
			buddy_pfn = __find_buddy_pfn(pfn, order);
			buddy = page + (buddy_pfn - pfn);
835
836
837
838
839
840
841
842
843
844
845
846
			buddy_mt = get_pageblock_migratetype(buddy);

			if (migratetype != buddy_mt
					&& (is_migrate_isolate(migratetype) ||
						is_migrate_isolate(buddy_mt)))
				goto done_merging;
		}
		max_order++;
		goto continue_merging;
	}

done_merging:
Linus Torvalds's avatar
Linus Torvalds committed
847
	set_page_order(page, order);
848
849
850
851
852
853
854
855
856

	/*
	 * 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
	 */
857
	if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)) {
858
		struct page *higher_page, *higher_buddy;
859
860
861
862
		combined_pfn = buddy_pfn & pfn;
		higher_page = page + (combined_pfn - pfn);
		buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
		higher_buddy = higher_page + (buddy_pfn - combined_pfn);
863
864
		if (pfn_valid_within(buddy_pfn) &&
		    page_is_buddy(higher_page, higher_buddy, order + 1)) {
865
866
867
868
869
870
871
872
			list_add_tail(&page->lru,
				&zone->free_area[order].free_list[migratetype]);
			goto out;
		}
	}

	list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
Linus Torvalds's avatar
Linus Torvalds committed
873
874
875
	zone->free_area[order].nr_free++;
}

876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
/*
 * 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
			(unsigned long)page->mem_cgroup |
#endif
			(page->flags & check_flags)))
		return false;

	return true;
}

898
static void free_pages_check_bad(struct page *page)
Linus Torvalds's avatar
Linus Torvalds committed
899
{
900
901
902
903
904
	const char *bad_reason;
	unsigned long bad_flags;

	bad_reason = NULL;
	bad_flags = 0;
905

906
	if (unlikely(atomic_read(&page->_mapcount) != -1))
907
908
909
		bad_reason = "nonzero mapcount";
	if (unlikely(page->mapping != NULL))
		bad_reason = "non-NULL mapping";
910
	if (unlikely(page_ref_count(page) != 0))
911
		bad_reason = "nonzero _refcount";
912
913
914
915
	if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_FREE)) {
		bad_reason = "PAGE_FLAGS_CHECK_AT_FREE flag(s) set";
		bad_flags = PAGE_FLAGS_CHECK_AT_FREE;
	}
916
917
918
919
#ifdef CONFIG_MEMCG
	if (unlikely(page->mem_cgroup))
		bad_reason = "page still charged to cgroup";
#endif
920
	bad_page(page, bad_reason, bad_flags);
921
922
923
924
}

static inline int free_pages_check(struct page *page)
{
925
	if (likely(page_expected_state(page, PAGE_FLAGS_CHECK_AT_FREE)))
926
927
928
929
		return 0;

	/* Something has gone sideways, find it */
	free_pages_check_bad(page);
930
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
931
932
}

933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
static int free_tail_pages_check(struct page *head_page, struct page *page)
{
	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);

	if (!IS_ENABLED(CONFIG_DEBUG_VM)) {
		ret = 0;
		goto out;
	}
	switch (page - head_page) {
	case 1:
		/* the first tail page: ->mapping is compound_mapcount() */
		if (unlikely(compound_mapcount(page))) {
			bad_page(page, "nonzero compound_mapcount", 0);
			goto out;
		}
		break;
	case 2:
		/*
		 * the second tail page: ->mapping is
		 * page_deferred_list().next -- ignore value.
		 */
		break;
	default:
		if (page->mapping != TAIL_MAPPING) {
			bad_page(page, "corrupted mapping in tail page", 0);
			goto out;
		}
		break;
	}
	if (unlikely(!PageTail(page))) {
		bad_page(page, "PageTail not set", 0);
		goto out;
	}
	if (unlikely(compound_head(page) != head_page)) {
		bad_page(page, "compound_head not consistent", 0);
		goto out;
	}
	ret = 0;
out:
	page->mapping = NULL;
	clear_compound_head(page);
	return ret;
}

983
984
static __always_inline bool free_pages_prepare(struct page *page,
					unsigned int order, bool check_free)
985
{
986
	int bad = 0;
987
988
989

	VM_BUG_ON_PAGE(PageTail(page), page);

990
991
992
993
994
995
996
997
998
999
1000
	trace_mm_page_free(page, order);

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