compaction.c 29.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/*
 * linux/mm/compaction.c
 *
 * Memory compaction for the reduction of external fragmentation. Note that
 * this heavily depends upon page migration to do all the real heavy
 * lifting
 *
 * Copyright IBM Corp. 2007-2010 Mel Gorman <mel@csn.ul.ie>
 */
#include <linux/swap.h>
#include <linux/migrate.h>
#include <linux/compaction.h>
#include <linux/mm_inline.h>
#include <linux/backing-dev.h>
15
#include <linux/sysctl.h>
16
#include <linux/sysfs.h>
17 18
#include "internal.h"

19 20
#if defined CONFIG_COMPACTION || defined CONFIG_CMA

21 22 23
#define CREATE_TRACE_POINTS
#include <trace/events/compaction.h>

24 25 26 27 28 29 30 31 32 33 34 35 36 37
static unsigned long release_freepages(struct list_head *freelist)
{
	struct page *page, *next;
	unsigned long count = 0;

	list_for_each_entry_safe(page, next, freelist, lru) {
		list_del(&page->lru);
		__free_page(page);
		count++;
	}

	return count;
}

38 39 40 41 42 43 44 45 46 47
static void map_pages(struct list_head *list)
{
	struct page *page;

	list_for_each_entry(page, list, lru) {
		arch_alloc_page(page, 0);
		kernel_map_pages(page, 1, 1);
	}
}

48 49 50 51 52
static inline bool migrate_async_suitable(int migratetype)
{
	return is_migrate_cma(migratetype) || migratetype == MIGRATE_MOVABLE;
}

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
/*
 * Compaction requires the taking of some coarse locks that are potentially
 * very heavily contended. Check if the process needs to be scheduled or
 * if the lock is contended. For async compaction, back out in the event
 * if contention is severe. For sync compaction, schedule.
 *
 * Returns true if the lock is held.
 * Returns false if the lock is released and compaction should abort
 */
static bool compact_checklock_irqsave(spinlock_t *lock, unsigned long *flags,
				      bool locked, struct compact_control *cc)
{
	if (need_resched() || spin_is_contended(lock)) {
		if (locked) {
			spin_unlock_irqrestore(lock, *flags);
			locked = false;
		}

		/* async aborts if taking too long or contended */
		if (!cc->sync) {
73
			cc->contended = true;
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
			return false;
		}

		cond_resched();
	}

	if (!locked)
		spin_lock_irqsave(lock, *flags);
	return true;
}

static inline bool compact_trylock_irqsave(spinlock_t *lock,
			unsigned long *flags, struct compact_control *cc)
{
	return compact_checklock_irqsave(lock, flags, false, cc);
}

91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
static void compact_capture_page(struct compact_control *cc)
{
	unsigned long flags;
	int mtype, mtype_low, mtype_high;

	if (!cc->page || *cc->page)
		return;

	/*
	 * For MIGRATE_MOVABLE allocations we capture a suitable page ASAP
	 * regardless of the migratetype of the freelist is is captured from.
	 * This is fine because the order for a high-order MIGRATE_MOVABLE
	 * allocation is typically at least a pageblock size and overall
	 * fragmentation is not impaired. Other allocation types must
	 * capture pages from their own migratelist because otherwise they
	 * could pollute other pageblocks like MIGRATE_MOVABLE with
	 * difficult to move pages and making fragmentation worse overall.
	 */
	if (cc->migratetype == MIGRATE_MOVABLE) {
		mtype_low = 0;
		mtype_high = MIGRATE_PCPTYPES;
	} else {
		mtype_low = cc->migratetype;
		mtype_high = cc->migratetype + 1;
	}

	/* Speculatively examine the free lists without zone lock */
	for (mtype = mtype_low; mtype < mtype_high; mtype++) {
		int order;
		for (order = cc->order; order < MAX_ORDER; order++) {
			struct page *page;
			struct free_area *area;
			area = &(cc->zone->free_area[order]);
			if (list_empty(&area->free_list[mtype]))
				continue;

			/* Take the lock and attempt capture of the page */
			if (!compact_trylock_irqsave(&cc->zone->lock, &flags, cc))
				return;
			if (!list_empty(&area->free_list[mtype])) {
				page = list_entry(area->free_list[mtype].next,
							struct page, lru);
				if (capture_free_page(page, cc->order, mtype)) {
					spin_unlock_irqrestore(&cc->zone->lock,
									flags);
					*cc->page = page;
					return;
				}
			}
			spin_unlock_irqrestore(&cc->zone->lock, flags);
		}
	}
}

145 146 147 148 149 150 151 152 153 154
/*
 * Isolate free pages onto a private freelist. Caller must hold zone->lock.
 * If @strict is true, will abort returning 0 on any invalid PFNs or non-free
 * pages inside of the pageblock (even though it may still end up isolating
 * some pages).
 */
static unsigned long isolate_freepages_block(unsigned long blockpfn,
				unsigned long end_pfn,
				struct list_head *freelist,
				bool strict)
155
{
156
	int nr_scanned = 0, total_isolated = 0;
157 158 159 160 161 162 163 164 165
	struct page *cursor;

	cursor = pfn_to_page(blockpfn);

	/* Isolate free pages. This assumes the block is valid */
	for (; blockpfn < end_pfn; blockpfn++, cursor++) {
		int isolated, i;
		struct page *page = cursor;

166 167 168
		if (!pfn_valid_within(blockpfn)) {
			if (strict)
				return 0;
169
			continue;
170
		}
171
		nr_scanned++;
172

173 174 175
		if (!PageBuddy(page)) {
			if (strict)
				return 0;
176
			continue;
177
		}
178 179 180

		/* Found a free page, break it into order-0 pages */
		isolated = split_free_page(page);
181 182
		if (!isolated && strict)
			return 0;
183 184 185 186 187 188 189 190 191 192 193 194 195
		total_isolated += isolated;
		for (i = 0; i < isolated; i++) {
			list_add(&page->lru, freelist);
			page++;
		}

		/* If a page was split, advance to the end of it */
		if (isolated) {
			blockpfn += isolated - 1;
			cursor += isolated - 1;
		}
	}

196
	trace_mm_compaction_isolate_freepages(nr_scanned, total_isolated);
197 198 199
	return total_isolated;
}

200 201 202 203 204 205 206 207 208 209 210 211 212
/**
 * isolate_freepages_range() - isolate free pages.
 * @start_pfn: The first PFN to start isolating.
 * @end_pfn:   The one-past-last PFN.
 *
 * Non-free pages, invalid PFNs, or zone boundaries within the
 * [start_pfn, end_pfn) range are considered errors, cause function to
 * undo its actions and return zero.
 *
 * Otherwise, function returns one-past-the-last PFN of isolated page
 * (which may be greater then end_pfn if end fell in a middle of
 * a free page).
 */
213
unsigned long
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266
isolate_freepages_range(unsigned long start_pfn, unsigned long end_pfn)
{
	unsigned long isolated, pfn, block_end_pfn, flags;
	struct zone *zone = NULL;
	LIST_HEAD(freelist);

	if (pfn_valid(start_pfn))
		zone = page_zone(pfn_to_page(start_pfn));

	for (pfn = start_pfn; pfn < end_pfn; pfn += isolated) {
		if (!pfn_valid(pfn) || zone != page_zone(pfn_to_page(pfn)))
			break;

		/*
		 * On subsequent iterations ALIGN() is actually not needed,
		 * but we keep it that we not to complicate the code.
		 */
		block_end_pfn = ALIGN(pfn + 1, pageblock_nr_pages);
		block_end_pfn = min(block_end_pfn, end_pfn);

		spin_lock_irqsave(&zone->lock, flags);
		isolated = isolate_freepages_block(pfn, block_end_pfn,
						   &freelist, true);
		spin_unlock_irqrestore(&zone->lock, flags);

		/*
		 * In strict mode, isolate_freepages_block() returns 0 if
		 * there are any holes in the block (ie. invalid PFNs or
		 * non-free pages).
		 */
		if (!isolated)
			break;

		/*
		 * If we managed to isolate pages, it is always (1 << n) *
		 * pageblock_nr_pages for some non-negative n.  (Max order
		 * page may span two pageblocks).
		 */
	}

	/* split_free_page does not map the pages */
	map_pages(&freelist);

	if (pfn < end_pfn) {
		/* Loop terminated early, cleanup. */
		release_freepages(&freelist);
		return 0;
	}

	/* We don't use freelists for anything. */
	return pfn;
}

267
/* Update the number of anon and file isolated pages in the zone */
268
static void acct_isolated(struct zone *zone, bool locked, struct compact_control *cc)
269 270
{
	struct page *page;
271
	unsigned int count[2] = { 0, };
272

273 274
	list_for_each_entry(page, &cc->migratepages, lru)
		count[!!page_is_file_cache(page)]++;
275

276 277 278 279 280 281 282 283
	/* If locked we can use the interrupt unsafe versions */
	if (locked) {
		__mod_zone_page_state(zone, NR_ISOLATED_ANON, count[0]);
		__mod_zone_page_state(zone, NR_ISOLATED_FILE, count[1]);
	} else {
		mod_zone_page_state(zone, NR_ISOLATED_ANON, count[0]);
		mod_zone_page_state(zone, NR_ISOLATED_FILE, count[1]);
	}
284 285 286 287 288
}

/* Similar to reclaim, but different enough that they don't share logic */
static bool too_many_isolated(struct zone *zone)
{
289
	unsigned long active, inactive, isolated;
290 291 292

	inactive = zone_page_state(zone, NR_INACTIVE_FILE) +
					zone_page_state(zone, NR_INACTIVE_ANON);
293 294
	active = zone_page_state(zone, NR_ACTIVE_FILE) +
					zone_page_state(zone, NR_ACTIVE_ANON);
295 296 297
	isolated = zone_page_state(zone, NR_ISOLATED_FILE) +
					zone_page_state(zone, NR_ISOLATED_ANON);

298
	return isolated > (inactive + active) / 2;
299 300
}

301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318
/**
 * isolate_migratepages_range() - isolate all migrate-able pages in range.
 * @zone:	Zone pages are in.
 * @cc:		Compaction control structure.
 * @low_pfn:	The first PFN of the range.
 * @end_pfn:	The one-past-the-last PFN of the range.
 *
 * Isolate all pages that can be migrated from the range specified by
 * [low_pfn, end_pfn).  Returns zero if there is a fatal signal
 * pending), otherwise PFN of the first page that was not scanned
 * (which may be both less, equal to or more then end_pfn).
 *
 * Assumes that cc->migratepages is empty and cc->nr_migratepages is
 * zero.
 *
 * Apart from cc->migratepages and cc->nr_migratetypes this function
 * does not modify any cc's fields, in particular it does not modify
 * (or read for that matter) cc->migrate_pfn.
319
 */
320
unsigned long
321 322
isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
			   unsigned long low_pfn, unsigned long end_pfn)
323
{
324
	unsigned long last_pageblock_nr = 0, pageblock_nr;
325
	unsigned long nr_scanned = 0, nr_isolated = 0;
326
	struct list_head *migratelist = &cc->migratepages;
327
	isolate_mode_t mode = 0;
328
	struct lruvec *lruvec;
329 330
	unsigned long flags;
	bool locked;
331 332 333 334 335 336 337

	/*
	 * Ensure that there are not too many pages isolated from the LRU
	 * list by either parallel reclaimers or compaction. If there are,
	 * delay for some time until fewer pages are isolated
	 */
	while (unlikely(too_many_isolated(zone))) {
338
		/* async migration should just abort */
339
		if (!cc->sync)
340
			return 0;
341

342 343 344
		congestion_wait(BLK_RW_ASYNC, HZ/10);

		if (fatal_signal_pending(current))
345
			return 0;
346 347 348
	}

	/* Time to isolate some pages for migration */
349
	cond_resched();
350 351
	spin_lock_irqsave(&zone->lru_lock, flags);
	locked = true;
352 353
	for (; low_pfn < end_pfn; low_pfn++) {
		struct page *page;
354 355 356

		/* give a chance to irqs before checking need_resched() */
		if (!((low_pfn+1) % SWAP_CLUSTER_MAX)) {
357
			spin_unlock_irqrestore(&zone->lru_lock, flags);
358 359
			locked = false;
		}
360 361 362 363

		/* Check if it is ok to still hold the lock */
		locked = compact_checklock_irqsave(&zone->lru_lock, &flags,
								locked, cc);
364
		if (!locked || fatal_signal_pending(current))
365
			break;
366

367 368 369 370 371 372 373 374 375 376 377 378 379
		/*
		 * migrate_pfn does not necessarily start aligned to a
		 * pageblock. Ensure that pfn_valid is called when moving
		 * into a new MAX_ORDER_NR_PAGES range in case of large
		 * memory holes within the zone
		 */
		if ((low_pfn & (MAX_ORDER_NR_PAGES - 1)) == 0) {
			if (!pfn_valid(low_pfn)) {
				low_pfn += MAX_ORDER_NR_PAGES - 1;
				continue;
			}
		}

380 381
		if (!pfn_valid_within(low_pfn))
			continue;
382
		nr_scanned++;
383

384 385 386 387 388 389
		/*
		 * Get the page and ensure the page is within the same zone.
		 * See the comment in isolate_freepages about overlapping
		 * nodes. It is deliberate that the new zone lock is not taken
		 * as memory compaction should not move pages between nodes.
		 */
390
		page = pfn_to_page(low_pfn);
391 392 393 394
		if (page_zone(page) != zone)
			continue;

		/* Skip if free */
395 396 397
		if (PageBuddy(page))
			continue;

398 399 400 401 402 403
		/*
		 * For async migration, also only scan in MOVABLE blocks. Async
		 * migration is optimistic to see if the minimum amount of work
		 * satisfies the allocation
		 */
		pageblock_nr = low_pfn >> pageblock_order;
404
		if (!cc->sync && last_pageblock_nr != pageblock_nr &&
405
		    !migrate_async_suitable(get_pageblock_migratetype(page))) {
406 407 408 409 410 411
			low_pfn += pageblock_nr_pages;
			low_pfn = ALIGN(low_pfn, pageblock_nr_pages) - 1;
			last_pageblock_nr = pageblock_nr;
			continue;
		}

412 413 414 415 416 417 418 419 420 421 422 423 424
		if (!PageLRU(page))
			continue;

		/*
		 * PageLRU is set, and lru_lock excludes isolation,
		 * splitting and collapsing (collapsing has already
		 * happened if PageLRU is set).
		 */
		if (PageTransHuge(page)) {
			low_pfn += (1 << compound_order(page)) - 1;
			continue;
		}

425
		if (!cc->sync)
426 427
			mode |= ISOLATE_ASYNC_MIGRATE;

428 429
		lruvec = mem_cgroup_page_lruvec(page, zone);

430
		/* Try isolate the page */
431
		if (__isolate_lru_page(page, mode) != 0)
432 433
			continue;

434 435
		VM_BUG_ON(PageTransCompound(page));

436
		/* Successfully isolated */
437
		del_page_from_lru_list(page, lruvec, page_lru(page));
438 439
		list_add(&page->lru, migratelist);
		cc->nr_migratepages++;
440
		nr_isolated++;
441 442

		/* Avoid isolating too much */
443 444
		if (cc->nr_migratepages == COMPACT_CLUSTER_MAX) {
			++low_pfn;
445
			break;
446
		}
447 448
	}

449
	acct_isolated(zone, locked, cc);
450

451 452
	if (locked)
		spin_unlock_irqrestore(&zone->lru_lock, flags);
453

454 455
	trace_mm_compaction_isolate_migratepages(nr_scanned, nr_isolated);

456 457 458
	return low_pfn;
}

459 460 461
#endif /* CONFIG_COMPACTION || CONFIG_CMA */
#ifdef CONFIG_COMPACTION

462 463
/* Returns true if the page is within a block suitable for migration to */
static bool suitable_migration_target(struct page *page)
464 465 466 467 468 469
{

	int migratetype = get_pageblock_migratetype(page);

	/* Don't interfere with memory hot-remove or the min_free_kbytes blocks */
	if (migratetype == MIGRATE_ISOLATE || migratetype == MIGRATE_RESERVE)
470
		return false;
471 472 473

	/* If the page is a large free page, then allow migration */
	if (PageBuddy(page) && page_order(page) >= pageblock_order)
474
		return true;
475

476
	/* If the block is MIGRATE_MOVABLE or MIGRATE_CMA, allow migration */
477 478
	if (migrate_async_suitable(migratetype))
		return true;
479 480

	/* Otherwise skip the block */
481
	return false;
482 483
}

484 485 486 487 488 489 490 491 492 493 494 495 496 497
/*
 * Returns the start pfn of the last page block in a zone.  This is the starting
 * point for full compaction of a zone.  Compaction searches for free pages from
 * the end of each zone, while isolate_freepages_block scans forward inside each
 * page block.
 */
static unsigned long start_free_pfn(struct zone *zone)
{
	unsigned long free_pfn;
	free_pfn = zone->zone_start_pfn + zone->spanned_pages;
	free_pfn &= ~(pageblock_nr_pages-1);
	return free_pfn;
}

498
/*
499 500
 * Based on information in the current compact_control, find blocks
 * suitable for isolating free pages from and then isolate them.
501
 */
502 503
static void isolate_freepages(struct zone *zone,
				struct compact_control *cc)
504
{
505 506 507 508 509
	struct page *page;
	unsigned long high_pfn, low_pfn, pfn, zone_end_pfn, end_pfn;
	unsigned long flags;
	int nr_freepages = cc->nr_freepages;
	struct list_head *freelist = &cc->freepages;
510

511 512 513 514 515 516 517
	/*
	 * Initialise the free scanner. The starting point is where we last
	 * scanned from (or the end of the zone if starting). The low point
	 * is the end of the pageblock the migration scanner is using.
	 */
	pfn = cc->free_pfn;
	low_pfn = cc->migrate_pfn + pageblock_nr_pages;
518

519 520 521 522 523 524
	/*
	 * Take care that if the migration scanner is at the end of the zone
	 * that the free scanner does not accidentally move to the next zone
	 * in the next isolation cycle.
	 */
	high_pfn = min(low_pfn, pfn);
525

526
	zone_end_pfn = zone->zone_start_pfn + zone->spanned_pages;
527

528 529 530 531 532 533 534 535
	/*
	 * Isolate free pages until enough are available to migrate the
	 * pages on cc->migratepages. We stop searching if the migrate
	 * and free page scanners meet or enough free pages are isolated.
	 */
	for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages;
					pfn -= pageblock_nr_pages) {
		unsigned long isolated;
536

537 538
		if (!pfn_valid(pfn))
			continue;
539

540 541 542 543 544 545 546 547 548 549 550 551
		/*
		 * Check for overlapping nodes/zones. 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.
		 */
		page = pfn_to_page(pfn);
		if (page_zone(page) != zone)
			continue;

		/* Check the block is suitable for migration */
552
		if (!suitable_migration_target(page))
553
			continue;
554

555 556 557 558 559 560 561
		/*
		 * Found a block suitable for isolating free pages from. Now
		 * we disabled interrupts, double check things are ok and
		 * isolate the pages. This is to minimise the time IRQs
		 * are disabled
		 */
		isolated = 0;
562 563 564 565 566 567 568 569 570 571

		/*
		 * The zone lock must be held to isolate freepages. This
		 * unfortunately this is a very coarse lock and can be
		 * heavily contended if there are parallel allocations
		 * or parallel compactions. For async compaction do not
		 * spin on the lock
		 */
		if (!compact_trylock_irqsave(&zone->lock, &flags, cc))
			break;
572
		if (suitable_migration_target(page)) {
573 574 575 576
			end_pfn = min(pfn + pageblock_nr_pages, zone_end_pfn);
			isolated = isolate_freepages_block(pfn, end_pfn,
							   freelist, false);
			nr_freepages += isolated;
577
		}
578 579 580 581 582 583 584
		spin_unlock_irqrestore(&zone->lock, flags);

		/*
		 * Record the highest PFN we isolated pages from. When next
		 * looking for free pages, the search will restart here as
		 * page migration may have returned some pages to the allocator
		 */
585
		if (isolated) {
586
			high_pfn = max(high_pfn, pfn);
587 588 589 590 591 592 593 594 595

			/*
			 * If the free scanner has wrapped, update
			 * compact_cached_free_pfn to point to the highest
			 * pageblock with free pages. This reduces excessive
			 * scanning of full pageblocks near the end of the
			 * zone
			 */
			if (cc->order > 0 && cc->wrapped)
596 597
				zone->compact_cached_free_pfn = high_pfn;
		}
598 599 600 601 602 603 604
	}

	/* split_free_page does not map the pages */
	map_pages(freelist);

	cc->free_pfn = high_pfn;
	cc->nr_freepages = nr_freepages;
605 606 607 608 609

	/* If compact_cached_free_pfn is reset then set it now */
	if (cc->order > 0 && !cc->wrapped &&
			zone->compact_cached_free_pfn == start_free_pfn(zone))
		zone->compact_cached_free_pfn = high_pfn;
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657
}

/*
 * This is a migrate-callback that "allocates" freepages by taking pages
 * from the isolated freelists in the block we are migrating to.
 */
static struct page *compaction_alloc(struct page *migratepage,
					unsigned long data,
					int **result)
{
	struct compact_control *cc = (struct compact_control *)data;
	struct page *freepage;

	/* Isolate free pages if necessary */
	if (list_empty(&cc->freepages)) {
		isolate_freepages(cc->zone, cc);

		if (list_empty(&cc->freepages))
			return NULL;
	}

	freepage = list_entry(cc->freepages.next, struct page, lru);
	list_del(&freepage->lru);
	cc->nr_freepages--;

	return freepage;
}

/*
 * We cannot control nr_migratepages and nr_freepages fully when migration is
 * running as migrate_pages() has no knowledge of compact_control. When
 * migration is complete, we count the number of pages on the lists by hand.
 */
static void update_nr_listpages(struct compact_control *cc)
{
	int nr_migratepages = 0;
	int nr_freepages = 0;
	struct page *page;

	list_for_each_entry(page, &cc->migratepages, lru)
		nr_migratepages++;
	list_for_each_entry(page, &cc->freepages, lru)
		nr_freepages++;

	cc->nr_migratepages = nr_migratepages;
	cc->nr_freepages = nr_freepages;
}

658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
/* possible outcome of isolate_migratepages */
typedef enum {
	ISOLATE_ABORT,		/* Abort compaction now */
	ISOLATE_NONE,		/* No pages isolated, continue scanning */
	ISOLATE_SUCCESS,	/* Pages isolated, migrate */
} isolate_migrate_t;

/*
 * Isolate all pages that can be migrated from the block pointed to by
 * the migrate scanner within compact_control.
 */
static isolate_migrate_t isolate_migratepages(struct zone *zone,
					struct compact_control *cc)
{
	unsigned long low_pfn, end_pfn;

	/* Do not scan outside zone boundaries */
	low_pfn = max(cc->migrate_pfn, zone->zone_start_pfn);

	/* Only scan within a pageblock boundary */
	end_pfn = ALIGN(low_pfn + pageblock_nr_pages, pageblock_nr_pages);

	/* Do not cross the free scanner or scan within a memory hole */
	if (end_pfn > cc->free_pfn || !pfn_valid(low_pfn)) {
		cc->migrate_pfn = end_pfn;
		return ISOLATE_NONE;
	}

	/* Perform the isolation */
	low_pfn = isolate_migratepages_range(zone, cc, low_pfn, end_pfn);
688
	if (!low_pfn || cc->contended)
689 690 691 692 693 694 695
		return ISOLATE_ABORT;

	cc->migrate_pfn = low_pfn;

	return ISOLATE_SUCCESS;
}

696
static int compact_finished(struct zone *zone,
697
			    struct compact_control *cc)
698
{
699
	unsigned long watermark;
700

701 702 703
	if (fatal_signal_pending(current))
		return COMPACT_PARTIAL;

704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723
	/*
	 * A full (order == -1) compaction run starts at the beginning and
	 * end of a zone; it completes when the migrate and free scanner meet.
	 * A partial (order > 0) compaction can start with the free scanner
	 * at a random point in the zone, and may have to restart.
	 */
	if (cc->free_pfn <= cc->migrate_pfn) {
		if (cc->order > 0 && !cc->wrapped) {
			/* We started partway through; restart at the end. */
			unsigned long free_pfn = start_free_pfn(zone);
			zone->compact_cached_free_pfn = free_pfn;
			cc->free_pfn = free_pfn;
			cc->wrapped = 1;
			return COMPACT_CONTINUE;
		}
		return COMPACT_COMPLETE;
	}

	/* We wrapped around and ended up where we started. */
	if (cc->wrapped && cc->free_pfn <= cc->start_free_pfn)
724 725
		return COMPACT_COMPLETE;

726 727 728 729
	/*
	 * order == -1 is expected when compacting via
	 * /proc/sys/vm/compact_memory
	 */
730 731 732
	if (cc->order == -1)
		return COMPACT_CONTINUE;

733 734 735 736 737 738 739
	/* Compaction run is not finished if the watermark is not met */
	watermark = low_wmark_pages(zone);
	watermark += (1 << cc->order);

	if (!zone_watermark_ok(zone, cc->order, watermark, 0, 0))
		return COMPACT_CONTINUE;

740
	/* Direct compactor: Is a suitable page free? */
741 742 743
	if (cc->page) {
		/* Was a suitable page captured? */
		if (*cc->page)
744
			return COMPACT_PARTIAL;
745 746 747 748 749 750 751 752 753 754 755 756
	} else {
		unsigned int order;
		for (order = cc->order; order < MAX_ORDER; order++) {
			struct free_area *area = &zone->free_area[cc->order];
			/* Job done if page is free of the right migratetype */
			if (!list_empty(&area->free_list[cc->migratetype]))
				return COMPACT_PARTIAL;

			/* Job done if allocation would set block type */
			if (cc->order >= pageblock_order && area->nr_free)
				return COMPACT_PARTIAL;
		}
757 758
	}

759 760 761
	return COMPACT_CONTINUE;
}

762 763 764 765 766 767 768 769 770 771 772 773
/*
 * compaction_suitable: Is this suitable to run compaction on this zone now?
 * Returns
 *   COMPACT_SKIPPED  - If there are too few free pages for compaction
 *   COMPACT_PARTIAL  - If the allocation would succeed without compaction
 *   COMPACT_CONTINUE - If compaction should run now
 */
unsigned long compaction_suitable(struct zone *zone, int order)
{
	int fragindex;
	unsigned long watermark;

774 775 776 777 778 779 780
	/*
	 * order == -1 is expected when compacting via
	 * /proc/sys/vm/compact_memory
	 */
	if (order == -1)
		return COMPACT_CONTINUE;

781 782 783 784 785 786 787 788 789 790 791 792 793
	/*
	 * Watermarks for order-0 must be met for compaction. Note the 2UL.
	 * This is because during migration, copies of pages need to be
	 * allocated and for a short time, the footprint is higher
	 */
	watermark = low_wmark_pages(zone) + (2UL << order);
	if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
		return COMPACT_SKIPPED;

	/*
	 * fragmentation index determines if allocation failures are due to
	 * low memory or external fragmentation
	 *
794 795
	 * index of -1000 implies allocations might succeed depending on
	 * watermarks
796 797 798 799 800 801 802 803 804
	 * index towards 0 implies failure is due to lack of memory
	 * index towards 1000 implies failure is due to fragmentation
	 *
	 * Only compact if a failure would be due to fragmentation.
	 */
	fragindex = fragmentation_index(zone, order);
	if (fragindex >= 0 && fragindex <= sysctl_extfrag_threshold)
		return COMPACT_SKIPPED;

805 806
	if (fragindex == -1000 && zone_watermark_ok(zone, order, watermark,
	    0, 0))
807 808 809 810 811
		return COMPACT_PARTIAL;

	return COMPACT_CONTINUE;
}

812 813 814 815
static int compact_zone(struct zone *zone, struct compact_control *cc)
{
	int ret;

816 817 818 819 820 821 822 823 824 825 826
	ret = compaction_suitable(zone, cc->order);
	switch (ret) {
	case COMPACT_PARTIAL:
	case COMPACT_SKIPPED:
		/* Compaction is likely to fail */
		return ret;
	case COMPACT_CONTINUE:
		/* Fall through to compaction */
		;
	}

827 828
	/* Setup to move all movable pages to the end of the zone */
	cc->migrate_pfn = zone->zone_start_pfn;
829 830 831 832 833 834 835 836 837

	if (cc->order > 0) {
		/* Incremental compaction. Start where the last one stopped. */
		cc->free_pfn = zone->compact_cached_free_pfn;
		cc->start_free_pfn = cc->free_pfn;
	} else {
		/* Order == -1 starts at the end of the zone. */
		cc->free_pfn = start_free_pfn(zone);
	}
838 839 840 841 842

	migrate_prep_local();

	while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) {
		unsigned long nr_migrate, nr_remaining;
843
		int err;
844

845 846 847
		switch (isolate_migratepages(zone, cc)) {
		case ISOLATE_ABORT:
			ret = COMPACT_PARTIAL;
848 849
			putback_lru_pages(&cc->migratepages);
			cc->nr_migratepages = 0;
850 851
			goto out;
		case ISOLATE_NONE:
852
			continue;
853 854 855
		case ISOLATE_SUCCESS:
			;
		}
856 857

		nr_migrate = cc->nr_migratepages;
858
		err = migrate_pages(&cc->migratepages, compaction_alloc,
859 860
				(unsigned long)cc, false,
				cc->sync ? MIGRATE_SYNC_LIGHT : MIGRATE_ASYNC);
861 862 863 864 865 866 867
		update_nr_listpages(cc);
		nr_remaining = cc->nr_migratepages;

		count_vm_event(COMPACTBLOCKS);
		count_vm_events(COMPACTPAGES, nr_migrate - nr_remaining);
		if (nr_remaining)
			count_vm_events(COMPACTPAGEFAILED, nr_remaining);
868 869
		trace_mm_compaction_migratepages(nr_migrate - nr_remaining,
						nr_remaining);
870 871

		/* Release LRU pages not migrated */
872
		if (err) {
873 874
			putback_lru_pages(&cc->migratepages);
			cc->nr_migratepages = 0;
875 876 877 878
			if (err == -ENOMEM) {
				ret = COMPACT_PARTIAL;
				goto out;
			}
879
		}
880 881 882

		/* Capture a page now if it is a suitable size */
		compact_capture_page(cc);
883 884
	}

885
out:
886 887 888 889 890 891
	/* Release free pages and check accounting */
	cc->nr_freepages -= release_freepages(&cc->freepages);
	VM_BUG_ON(cc->nr_freepages != 0);

	return ret;
}
892

893
static unsigned long compact_zone_order(struct zone *zone,
894
				 int order, gfp_t gfp_mask,
895 896
				 bool sync, bool *contended,
				 struct page **page)
897
{
898
	unsigned long ret;
899 900 901 902 903 904
	struct compact_control cc = {
		.nr_freepages = 0,
		.nr_migratepages = 0,
		.order = order,
		.migratetype = allocflags_to_migratetype(gfp_mask),
		.zone = zone,
905
		.sync = sync,
906
		.page = page,
907 908 909 910
	};
	INIT_LIST_HEAD(&cc.freepages);
	INIT_LIST_HEAD(&cc.migratepages);

911 912 913 914 915 916 917
	ret = compact_zone(zone, &cc);

	VM_BUG_ON(!list_empty(&cc.freepages));
	VM_BUG_ON(!list_empty(&cc.migratepages));

	*contended = cc.contended;
	return ret;
918 919
}

920 921
int sysctl_extfrag_threshold = 500;

922 923 924 925 926 927
/**
 * try_to_compact_pages - Direct compact to satisfy a high-order allocation
 * @zonelist: The zonelist used for the current allocation
 * @order: The order of the current allocation
 * @gfp_mask: The GFP mask of the current allocation
 * @nodemask: The allowed nodes to allocate from
928
 * @sync: Whether migration is synchronous or not
929 930
 * @contended: Return value that is true if compaction was aborted due to lock contention
 * @page: Optionally capture a free page of the requested order during compaction
931 932 933 934
 *
 * This is the main entry point for direct page compaction.
 */
unsigned long try_to_compact_pages(struct zonelist *zonelist,
935
			int order, gfp_t gfp_mask, nodemask_t *nodemask,
936
			bool sync, bool *contended, struct page **page)
937 938 939 940 941 942 943
{
	enum zone_type high_zoneidx = gfp_zone(gfp_mask);
	int may_enter_fs = gfp_mask & __GFP_FS;
	int may_perform_io = gfp_mask & __GFP_IO;
	struct zoneref *z;
	struct zone *zone;
	int rc = COMPACT_SKIPPED;
944
	int alloc_flags = 0;
945

946
	/* Check if the GFP flags allow compaction */
947
	if (!order || !may_enter_fs || !may_perform_io)
948 949 950 951
		return rc;

	count_vm_event(COMPACTSTALL);

952 953 954 955
#ifdef CONFIG_CMA
	if (allocflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
		alloc_flags |= ALLOC_CMA;
#endif
956 957 958 959 960
	/* Compact each zone in the list */
	for_each_zone_zonelist_nodemask(zone, z, zonelist, high_zoneidx,
								nodemask) {
		int status;

961
		status = compact_zone_order(zone, order, gfp_mask, sync,
962
						contended, page);
963 964
		rc = max(status, rc);

965
		/* If a normal allocation would succeed, stop compacting */
966 967
		if (zone_watermark_ok(zone, order, low_wmark_pages(zone), 0,
				      alloc_flags))
968 969 970 971 972 973 974
			break;
	}

	return rc;
}


975
/* Compact all zones within a node */
976
static int __compact_pgdat(pg_data_t *pgdat, struct compact_control *cc)
977 978 979 980 981 982 983 984 985 986
{
	int zoneid;
	struct zone *zone;

	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {

		zone = &pgdat->node_zones[zoneid];
		if (!populated_zone(zone))
			continue;

987 988 989 990 991
		cc->nr_freepages = 0;
		cc->nr_migratepages = 0;
		cc->zone = zone;
		INIT_LIST_HEAD(&cc->freepages);
		INIT_LIST_HEAD(&cc->migratepages);
992

993
		if (cc->order == -1 || !compaction_deferred(zone, cc->order))
994
			compact_zone(zone, cc);
995

996 997 998
		if (cc->order > 0) {
			int ok = zone_watermark_ok(zone, cc->order,
						low_wmark_pages(zone), 0, 0);
999
			if (ok && cc->order >= zone->compact_order_failed)
1000 1001
				zone->compact_order_failed = cc->order + 1;
			/* Currently async compaction is never deferred. */
1002
			else if (!ok && cc->sync)
1003 1004 1005
				defer_compaction(zone, cc->order);
		}

1006 1007
		VM_BUG_ON(!list_empty(&cc->freepages));
		VM_BUG_ON(!list_empty(&cc->migratepages));
1008 1009 1010 1011 1012
	}

	return 0;
}

1013 1014 1015 1016
int compact_pgdat(pg_data_t *pgdat, int order)
{
	struct compact_control cc = {
		.order = order,
1017
		.sync = false,
1018
		.page = NULL,
1019 1020 1021 1022 1023 1024 1025 1026 1027
	};

	return __compact_pgdat(pgdat, &cc);
}

static int compact_node(int nid)
{
	struct compact_control cc = {
		.order = -1,
1028
		.sync = true,
1029
		.page = NULL,
1030 1031
	};

1032
	return __compact_pgdat(NODE_DATA(nid), &cc);
1033 1034
}

1035 1036 1037 1038 1039
/* Compact all nodes in the system */
static int compact_nodes(void)
{
	int nid;

1040 1041 1042
	/* Flush pending updates to the LRU lists */
	lru_add_drain_all();

1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060
	for_each_online_node(nid)
		compact_node(nid);

	return COMPACT_COMPLETE;
}

/* The written value is actually unused, all memory is compacted */
int sysctl_compact_memory;

/* This is the entry point for compacting all nodes via /proc/sys/vm */
int sysctl_compaction_handler(struct ctl_table *table, int write,
			void __user *buffer, size_t *length, loff_t *ppos)
{
	if (write)
		return compact_nodes();

	return 0;
}
1061

1062 1063 1064 1065 1066 1067 1068 1069
int sysctl_extfrag_handler(struct ctl_table *table, int write,
			void __user *buffer, size_t *length, loff_t *ppos)
{
	proc_dointvec_minmax(table, write, buffer, length, ppos);

	return 0;
}

1070
#if defined(CONFIG_SYSFS) && defined(CONFIG_NUMA)
1071 1072
ssize_t sysfs_compact_node(struct device *dev,
			struct device_attribute *attr,
1073 1074
			const char *buf, size_t count)
{
1075 1076 1077 1078 1079 1080 1081 1082
	int nid = dev->id;

	if (nid >= 0 && nid < nr_node_ids && node_online(nid)) {
		/* Flush pending updates to the LRU lists */
		lru_add_drain_all();

		compact_node(nid);
	}
1083 1084 1085

	return count;
}
1086
static DEVICE_ATTR(compact, S_IWUSR, NULL, sysfs_compact_node);
1087 1088 1089

int compaction_register_node(struct node *node)
{
1090
	return device_create_file(&node->dev, &dev_attr_compact);
1091 1092 1093 1094
}

void compaction_unregister_node(struct node *node)
{
1095
	return device_remove_file(&node->dev, &dev_attr_compact);
1096 1097
}
#endif /* CONFIG_SYSFS && CONFIG_NUMA */
1098 1099

#endif /* CONFIG_COMPACTION */