xref: /openbmc/linux/mm/compaction.c (revision e23feb16)
1 /*
2  * linux/mm/compaction.c
3  *
4  * Memory compaction for the reduction of external fragmentation. Note that
5  * this heavily depends upon page migration to do all the real heavy
6  * lifting
7  *
8  * Copyright IBM Corp. 2007-2010 Mel Gorman <mel@csn.ul.ie>
9  */
10 #include <linux/swap.h>
11 #include <linux/migrate.h>
12 #include <linux/compaction.h>
13 #include <linux/mm_inline.h>
14 #include <linux/backing-dev.h>
15 #include <linux/sysctl.h>
16 #include <linux/sysfs.h>
17 #include <linux/balloon_compaction.h>
18 #include <linux/page-isolation.h>
19 #include "internal.h"
20 
21 #ifdef CONFIG_COMPACTION
22 static inline void count_compact_event(enum vm_event_item item)
23 {
24 	count_vm_event(item);
25 }
26 
27 static inline void count_compact_events(enum vm_event_item item, long delta)
28 {
29 	count_vm_events(item, delta);
30 }
31 #else
32 #define count_compact_event(item) do { } while (0)
33 #define count_compact_events(item, delta) do { } while (0)
34 #endif
35 
36 #if defined CONFIG_COMPACTION || defined CONFIG_CMA
37 
38 #define CREATE_TRACE_POINTS
39 #include <trace/events/compaction.h>
40 
41 static unsigned long release_freepages(struct list_head *freelist)
42 {
43 	struct page *page, *next;
44 	unsigned long count = 0;
45 
46 	list_for_each_entry_safe(page, next, freelist, lru) {
47 		list_del(&page->lru);
48 		__free_page(page);
49 		count++;
50 	}
51 
52 	return count;
53 }
54 
55 static void map_pages(struct list_head *list)
56 {
57 	struct page *page;
58 
59 	list_for_each_entry(page, list, lru) {
60 		arch_alloc_page(page, 0);
61 		kernel_map_pages(page, 1, 1);
62 	}
63 }
64 
65 static inline bool migrate_async_suitable(int migratetype)
66 {
67 	return is_migrate_cma(migratetype) || migratetype == MIGRATE_MOVABLE;
68 }
69 
70 #ifdef CONFIG_COMPACTION
71 /* Returns true if the pageblock should be scanned for pages to isolate. */
72 static inline bool isolation_suitable(struct compact_control *cc,
73 					struct page *page)
74 {
75 	if (cc->ignore_skip_hint)
76 		return true;
77 
78 	return !get_pageblock_skip(page);
79 }
80 
81 /*
82  * This function is called to clear all cached information on pageblocks that
83  * should be skipped for page isolation when the migrate and free page scanner
84  * meet.
85  */
86 static void __reset_isolation_suitable(struct zone *zone)
87 {
88 	unsigned long start_pfn = zone->zone_start_pfn;
89 	unsigned long end_pfn = zone_end_pfn(zone);
90 	unsigned long pfn;
91 
92 	zone->compact_cached_migrate_pfn = start_pfn;
93 	zone->compact_cached_free_pfn = end_pfn;
94 	zone->compact_blockskip_flush = false;
95 
96 	/* Walk the zone and mark every pageblock as suitable for isolation */
97 	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
98 		struct page *page;
99 
100 		cond_resched();
101 
102 		if (!pfn_valid(pfn))
103 			continue;
104 
105 		page = pfn_to_page(pfn);
106 		if (zone != page_zone(page))
107 			continue;
108 
109 		clear_pageblock_skip(page);
110 	}
111 }
112 
113 void reset_isolation_suitable(pg_data_t *pgdat)
114 {
115 	int zoneid;
116 
117 	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
118 		struct zone *zone = &pgdat->node_zones[zoneid];
119 		if (!populated_zone(zone))
120 			continue;
121 
122 		/* Only flush if a full compaction finished recently */
123 		if (zone->compact_blockskip_flush)
124 			__reset_isolation_suitable(zone);
125 	}
126 }
127 
128 /*
129  * If no pages were isolated then mark this pageblock to be skipped in the
130  * future. The information is later cleared by __reset_isolation_suitable().
131  */
132 static void update_pageblock_skip(struct compact_control *cc,
133 			struct page *page, unsigned long nr_isolated,
134 			bool migrate_scanner)
135 {
136 	struct zone *zone = cc->zone;
137 	if (!page)
138 		return;
139 
140 	if (!nr_isolated) {
141 		unsigned long pfn = page_to_pfn(page);
142 		set_pageblock_skip(page);
143 
144 		/* Update where compaction should restart */
145 		if (migrate_scanner) {
146 			if (!cc->finished_update_migrate &&
147 			    pfn > zone->compact_cached_migrate_pfn)
148 				zone->compact_cached_migrate_pfn = pfn;
149 		} else {
150 			if (!cc->finished_update_free &&
151 			    pfn < zone->compact_cached_free_pfn)
152 				zone->compact_cached_free_pfn = pfn;
153 		}
154 	}
155 }
156 #else
157 static inline bool isolation_suitable(struct compact_control *cc,
158 					struct page *page)
159 {
160 	return true;
161 }
162 
163 static void update_pageblock_skip(struct compact_control *cc,
164 			struct page *page, unsigned long nr_isolated,
165 			bool migrate_scanner)
166 {
167 }
168 #endif /* CONFIG_COMPACTION */
169 
170 static inline bool should_release_lock(spinlock_t *lock)
171 {
172 	return need_resched() || spin_is_contended(lock);
173 }
174 
175 /*
176  * Compaction requires the taking of some coarse locks that are potentially
177  * very heavily contended. Check if the process needs to be scheduled or
178  * if the lock is contended. For async compaction, back out in the event
179  * if contention is severe. For sync compaction, schedule.
180  *
181  * Returns true if the lock is held.
182  * Returns false if the lock is released and compaction should abort
183  */
184 static bool compact_checklock_irqsave(spinlock_t *lock, unsigned long *flags,
185 				      bool locked, struct compact_control *cc)
186 {
187 	if (should_release_lock(lock)) {
188 		if (locked) {
189 			spin_unlock_irqrestore(lock, *flags);
190 			locked = false;
191 		}
192 
193 		/* async aborts if taking too long or contended */
194 		if (!cc->sync) {
195 			cc->contended = true;
196 			return false;
197 		}
198 
199 		cond_resched();
200 	}
201 
202 	if (!locked)
203 		spin_lock_irqsave(lock, *flags);
204 	return true;
205 }
206 
207 static inline bool compact_trylock_irqsave(spinlock_t *lock,
208 			unsigned long *flags, struct compact_control *cc)
209 {
210 	return compact_checklock_irqsave(lock, flags, false, cc);
211 }
212 
213 /* Returns true if the page is within a block suitable for migration to */
214 static bool suitable_migration_target(struct page *page)
215 {
216 	int migratetype = get_pageblock_migratetype(page);
217 
218 	/* Don't interfere with memory hot-remove or the min_free_kbytes blocks */
219 	if (migratetype == MIGRATE_RESERVE)
220 		return false;
221 
222 	if (is_migrate_isolate(migratetype))
223 		return false;
224 
225 	/* If the page is a large free page, then allow migration */
226 	if (PageBuddy(page) && page_order(page) >= pageblock_order)
227 		return true;
228 
229 	/* If the block is MIGRATE_MOVABLE or MIGRATE_CMA, allow migration */
230 	if (migrate_async_suitable(migratetype))
231 		return true;
232 
233 	/* Otherwise skip the block */
234 	return false;
235 }
236 
237 /*
238  * Isolate free pages onto a private freelist. Caller must hold zone->lock.
239  * If @strict is true, will abort returning 0 on any invalid PFNs or non-free
240  * pages inside of the pageblock (even though it may still end up isolating
241  * some pages).
242  */
243 static unsigned long isolate_freepages_block(struct compact_control *cc,
244 				unsigned long blockpfn,
245 				unsigned long end_pfn,
246 				struct list_head *freelist,
247 				bool strict)
248 {
249 	int nr_scanned = 0, total_isolated = 0;
250 	struct page *cursor, *valid_page = NULL;
251 	unsigned long nr_strict_required = end_pfn - blockpfn;
252 	unsigned long flags;
253 	bool locked = false;
254 
255 	cursor = pfn_to_page(blockpfn);
256 
257 	/* Isolate free pages. */
258 	for (; blockpfn < end_pfn; blockpfn++, cursor++) {
259 		int isolated, i;
260 		struct page *page = cursor;
261 
262 		nr_scanned++;
263 		if (!pfn_valid_within(blockpfn))
264 			continue;
265 		if (!valid_page)
266 			valid_page = page;
267 		if (!PageBuddy(page))
268 			continue;
269 
270 		/*
271 		 * The zone lock must be held to isolate freepages.
272 		 * Unfortunately this is a very coarse lock and can be
273 		 * heavily contended if there are parallel allocations
274 		 * or parallel compactions. For async compaction do not
275 		 * spin on the lock and we acquire the lock as late as
276 		 * possible.
277 		 */
278 		locked = compact_checklock_irqsave(&cc->zone->lock, &flags,
279 								locked, cc);
280 		if (!locked)
281 			break;
282 
283 		/* Recheck this is a suitable migration target under lock */
284 		if (!strict && !suitable_migration_target(page))
285 			break;
286 
287 		/* Recheck this is a buddy page under lock */
288 		if (!PageBuddy(page))
289 			continue;
290 
291 		/* Found a free page, break it into order-0 pages */
292 		isolated = split_free_page(page);
293 		if (!isolated && strict)
294 			break;
295 		total_isolated += isolated;
296 		for (i = 0; i < isolated; i++) {
297 			list_add(&page->lru, freelist);
298 			page++;
299 		}
300 
301 		/* If a page was split, advance to the end of it */
302 		if (isolated) {
303 			blockpfn += isolated - 1;
304 			cursor += isolated - 1;
305 		}
306 	}
307 
308 	trace_mm_compaction_isolate_freepages(nr_scanned, total_isolated);
309 
310 	/*
311 	 * If strict isolation is requested by CMA then check that all the
312 	 * pages requested were isolated. If there were any failures, 0 is
313 	 * returned and CMA will fail.
314 	 */
315 	if (strict && nr_strict_required > total_isolated)
316 		total_isolated = 0;
317 
318 	if (locked)
319 		spin_unlock_irqrestore(&cc->zone->lock, flags);
320 
321 	/* Update the pageblock-skip if the whole pageblock was scanned */
322 	if (blockpfn == end_pfn)
323 		update_pageblock_skip(cc, valid_page, total_isolated, false);
324 
325 	count_compact_events(COMPACTFREE_SCANNED, nr_scanned);
326 	if (total_isolated)
327 		count_compact_events(COMPACTISOLATED, total_isolated);
328 	return total_isolated;
329 }
330 
331 /**
332  * isolate_freepages_range() - isolate free pages.
333  * @start_pfn: The first PFN to start isolating.
334  * @end_pfn:   The one-past-last PFN.
335  *
336  * Non-free pages, invalid PFNs, or zone boundaries within the
337  * [start_pfn, end_pfn) range are considered errors, cause function to
338  * undo its actions and return zero.
339  *
340  * Otherwise, function returns one-past-the-last PFN of isolated page
341  * (which may be greater then end_pfn if end fell in a middle of
342  * a free page).
343  */
344 unsigned long
345 isolate_freepages_range(struct compact_control *cc,
346 			unsigned long start_pfn, unsigned long end_pfn)
347 {
348 	unsigned long isolated, pfn, block_end_pfn;
349 	LIST_HEAD(freelist);
350 
351 	for (pfn = start_pfn; pfn < end_pfn; pfn += isolated) {
352 		if (!pfn_valid(pfn) || cc->zone != page_zone(pfn_to_page(pfn)))
353 			break;
354 
355 		/*
356 		 * On subsequent iterations ALIGN() is actually not needed,
357 		 * but we keep it that we not to complicate the code.
358 		 */
359 		block_end_pfn = ALIGN(pfn + 1, pageblock_nr_pages);
360 		block_end_pfn = min(block_end_pfn, end_pfn);
361 
362 		isolated = isolate_freepages_block(cc, pfn, block_end_pfn,
363 						   &freelist, true);
364 
365 		/*
366 		 * In strict mode, isolate_freepages_block() returns 0 if
367 		 * there are any holes in the block (ie. invalid PFNs or
368 		 * non-free pages).
369 		 */
370 		if (!isolated)
371 			break;
372 
373 		/*
374 		 * If we managed to isolate pages, it is always (1 << n) *
375 		 * pageblock_nr_pages for some non-negative n.  (Max order
376 		 * page may span two pageblocks).
377 		 */
378 	}
379 
380 	/* split_free_page does not map the pages */
381 	map_pages(&freelist);
382 
383 	if (pfn < end_pfn) {
384 		/* Loop terminated early, cleanup. */
385 		release_freepages(&freelist);
386 		return 0;
387 	}
388 
389 	/* We don't use freelists for anything. */
390 	return pfn;
391 }
392 
393 /* Update the number of anon and file isolated pages in the zone */
394 static void acct_isolated(struct zone *zone, bool locked, struct compact_control *cc)
395 {
396 	struct page *page;
397 	unsigned int count[2] = { 0, };
398 
399 	list_for_each_entry(page, &cc->migratepages, lru)
400 		count[!!page_is_file_cache(page)]++;
401 
402 	/* If locked we can use the interrupt unsafe versions */
403 	if (locked) {
404 		__mod_zone_page_state(zone, NR_ISOLATED_ANON, count[0]);
405 		__mod_zone_page_state(zone, NR_ISOLATED_FILE, count[1]);
406 	} else {
407 		mod_zone_page_state(zone, NR_ISOLATED_ANON, count[0]);
408 		mod_zone_page_state(zone, NR_ISOLATED_FILE, count[1]);
409 	}
410 }
411 
412 /* Similar to reclaim, but different enough that they don't share logic */
413 static bool too_many_isolated(struct zone *zone)
414 {
415 	unsigned long active, inactive, isolated;
416 
417 	inactive = zone_page_state(zone, NR_INACTIVE_FILE) +
418 					zone_page_state(zone, NR_INACTIVE_ANON);
419 	active = zone_page_state(zone, NR_ACTIVE_FILE) +
420 					zone_page_state(zone, NR_ACTIVE_ANON);
421 	isolated = zone_page_state(zone, NR_ISOLATED_FILE) +
422 					zone_page_state(zone, NR_ISOLATED_ANON);
423 
424 	return isolated > (inactive + active) / 2;
425 }
426 
427 /**
428  * isolate_migratepages_range() - isolate all migrate-able pages in range.
429  * @zone:	Zone pages are in.
430  * @cc:		Compaction control structure.
431  * @low_pfn:	The first PFN of the range.
432  * @end_pfn:	The one-past-the-last PFN of the range.
433  * @unevictable: true if it allows to isolate unevictable pages
434  *
435  * Isolate all pages that can be migrated from the range specified by
436  * [low_pfn, end_pfn).  Returns zero if there is a fatal signal
437  * pending), otherwise PFN of the first page that was not scanned
438  * (which may be both less, equal to or more then end_pfn).
439  *
440  * Assumes that cc->migratepages is empty and cc->nr_migratepages is
441  * zero.
442  *
443  * Apart from cc->migratepages and cc->nr_migratetypes this function
444  * does not modify any cc's fields, in particular it does not modify
445  * (or read for that matter) cc->migrate_pfn.
446  */
447 unsigned long
448 isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
449 		unsigned long low_pfn, unsigned long end_pfn, bool unevictable)
450 {
451 	unsigned long last_pageblock_nr = 0, pageblock_nr;
452 	unsigned long nr_scanned = 0, nr_isolated = 0;
453 	struct list_head *migratelist = &cc->migratepages;
454 	isolate_mode_t mode = 0;
455 	struct lruvec *lruvec;
456 	unsigned long flags;
457 	bool locked = false;
458 	struct page *page = NULL, *valid_page = NULL;
459 
460 	/*
461 	 * Ensure that there are not too many pages isolated from the LRU
462 	 * list by either parallel reclaimers or compaction. If there are,
463 	 * delay for some time until fewer pages are isolated
464 	 */
465 	while (unlikely(too_many_isolated(zone))) {
466 		/* async migration should just abort */
467 		if (!cc->sync)
468 			return 0;
469 
470 		congestion_wait(BLK_RW_ASYNC, HZ/10);
471 
472 		if (fatal_signal_pending(current))
473 			return 0;
474 	}
475 
476 	/* Time to isolate some pages for migration */
477 	cond_resched();
478 	for (; low_pfn < end_pfn; low_pfn++) {
479 		/* give a chance to irqs before checking need_resched() */
480 		if (locked && !((low_pfn+1) % SWAP_CLUSTER_MAX)) {
481 			if (should_release_lock(&zone->lru_lock)) {
482 				spin_unlock_irqrestore(&zone->lru_lock, flags);
483 				locked = false;
484 			}
485 		}
486 
487 		/*
488 		 * migrate_pfn does not necessarily start aligned to a
489 		 * pageblock. Ensure that pfn_valid is called when moving
490 		 * into a new MAX_ORDER_NR_PAGES range in case of large
491 		 * memory holes within the zone
492 		 */
493 		if ((low_pfn & (MAX_ORDER_NR_PAGES - 1)) == 0) {
494 			if (!pfn_valid(low_pfn)) {
495 				low_pfn += MAX_ORDER_NR_PAGES - 1;
496 				continue;
497 			}
498 		}
499 
500 		if (!pfn_valid_within(low_pfn))
501 			continue;
502 		nr_scanned++;
503 
504 		/*
505 		 * Get the page and ensure the page is within the same zone.
506 		 * See the comment in isolate_freepages about overlapping
507 		 * nodes. It is deliberate that the new zone lock is not taken
508 		 * as memory compaction should not move pages between nodes.
509 		 */
510 		page = pfn_to_page(low_pfn);
511 		if (page_zone(page) != zone)
512 			continue;
513 
514 		if (!valid_page)
515 			valid_page = page;
516 
517 		/* If isolation recently failed, do not retry */
518 		pageblock_nr = low_pfn >> pageblock_order;
519 		if (!isolation_suitable(cc, page))
520 			goto next_pageblock;
521 
522 		/* Skip if free */
523 		if (PageBuddy(page))
524 			continue;
525 
526 		/*
527 		 * For async migration, also only scan in MOVABLE blocks. Async
528 		 * migration is optimistic to see if the minimum amount of work
529 		 * satisfies the allocation
530 		 */
531 		if (!cc->sync && last_pageblock_nr != pageblock_nr &&
532 		    !migrate_async_suitable(get_pageblock_migratetype(page))) {
533 			cc->finished_update_migrate = true;
534 			goto next_pageblock;
535 		}
536 
537 		/*
538 		 * Check may be lockless but that's ok as we recheck later.
539 		 * It's possible to migrate LRU pages and balloon pages
540 		 * Skip any other type of page
541 		 */
542 		if (!PageLRU(page)) {
543 			if (unlikely(balloon_page_movable(page))) {
544 				if (locked && balloon_page_isolate(page)) {
545 					/* Successfully isolated */
546 					cc->finished_update_migrate = true;
547 					list_add(&page->lru, migratelist);
548 					cc->nr_migratepages++;
549 					nr_isolated++;
550 					goto check_compact_cluster;
551 				}
552 			}
553 			continue;
554 		}
555 
556 		/*
557 		 * PageLRU is set. lru_lock normally excludes isolation
558 		 * splitting and collapsing (collapsing has already happened
559 		 * if PageLRU is set) but the lock is not necessarily taken
560 		 * here and it is wasteful to take it just to check transhuge.
561 		 * Check TransHuge without lock and skip the whole pageblock if
562 		 * it's either a transhuge or hugetlbfs page, as calling
563 		 * compound_order() without preventing THP from splitting the
564 		 * page underneath us may return surprising results.
565 		 */
566 		if (PageTransHuge(page)) {
567 			if (!locked)
568 				goto next_pageblock;
569 			low_pfn += (1 << compound_order(page)) - 1;
570 			continue;
571 		}
572 
573 		/* Check if it is ok to still hold the lock */
574 		locked = compact_checklock_irqsave(&zone->lru_lock, &flags,
575 								locked, cc);
576 		if (!locked || fatal_signal_pending(current))
577 			break;
578 
579 		/* Recheck PageLRU and PageTransHuge under lock */
580 		if (!PageLRU(page))
581 			continue;
582 		if (PageTransHuge(page)) {
583 			low_pfn += (1 << compound_order(page)) - 1;
584 			continue;
585 		}
586 
587 		if (!cc->sync)
588 			mode |= ISOLATE_ASYNC_MIGRATE;
589 
590 		if (unevictable)
591 			mode |= ISOLATE_UNEVICTABLE;
592 
593 		lruvec = mem_cgroup_page_lruvec(page, zone);
594 
595 		/* Try isolate the page */
596 		if (__isolate_lru_page(page, mode) != 0)
597 			continue;
598 
599 		VM_BUG_ON(PageTransCompound(page));
600 
601 		/* Successfully isolated */
602 		cc->finished_update_migrate = true;
603 		del_page_from_lru_list(page, lruvec, page_lru(page));
604 		list_add(&page->lru, migratelist);
605 		cc->nr_migratepages++;
606 		nr_isolated++;
607 
608 check_compact_cluster:
609 		/* Avoid isolating too much */
610 		if (cc->nr_migratepages == COMPACT_CLUSTER_MAX) {
611 			++low_pfn;
612 			break;
613 		}
614 
615 		continue;
616 
617 next_pageblock:
618 		low_pfn = ALIGN(low_pfn + 1, pageblock_nr_pages) - 1;
619 		last_pageblock_nr = pageblock_nr;
620 	}
621 
622 	acct_isolated(zone, locked, cc);
623 
624 	if (locked)
625 		spin_unlock_irqrestore(&zone->lru_lock, flags);
626 
627 	/* Update the pageblock-skip if the whole pageblock was scanned */
628 	if (low_pfn == end_pfn)
629 		update_pageblock_skip(cc, valid_page, nr_isolated, true);
630 
631 	trace_mm_compaction_isolate_migratepages(nr_scanned, nr_isolated);
632 
633 	count_compact_events(COMPACTMIGRATE_SCANNED, nr_scanned);
634 	if (nr_isolated)
635 		count_compact_events(COMPACTISOLATED, nr_isolated);
636 
637 	return low_pfn;
638 }
639 
640 #endif /* CONFIG_COMPACTION || CONFIG_CMA */
641 #ifdef CONFIG_COMPACTION
642 /*
643  * Based on information in the current compact_control, find blocks
644  * suitable for isolating free pages from and then isolate them.
645  */
646 static void isolate_freepages(struct zone *zone,
647 				struct compact_control *cc)
648 {
649 	struct page *page;
650 	unsigned long high_pfn, low_pfn, pfn, z_end_pfn, end_pfn;
651 	int nr_freepages = cc->nr_freepages;
652 	struct list_head *freelist = &cc->freepages;
653 
654 	/*
655 	 * Initialise the free scanner. The starting point is where we last
656 	 * scanned from (or the end of the zone if starting). The low point
657 	 * is the end of the pageblock the migration scanner is using.
658 	 */
659 	pfn = cc->free_pfn;
660 	low_pfn = cc->migrate_pfn + pageblock_nr_pages;
661 
662 	/*
663 	 * Take care that if the migration scanner is at the end of the zone
664 	 * that the free scanner does not accidentally move to the next zone
665 	 * in the next isolation cycle.
666 	 */
667 	high_pfn = min(low_pfn, pfn);
668 
669 	z_end_pfn = zone_end_pfn(zone);
670 
671 	/*
672 	 * Isolate free pages until enough are available to migrate the
673 	 * pages on cc->migratepages. We stop searching if the migrate
674 	 * and free page scanners meet or enough free pages are isolated.
675 	 */
676 	for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages;
677 					pfn -= pageblock_nr_pages) {
678 		unsigned long isolated;
679 
680 		/*
681 		 * This can iterate a massively long zone without finding any
682 		 * suitable migration targets, so periodically check if we need
683 		 * to schedule.
684 		 */
685 		cond_resched();
686 
687 		if (!pfn_valid(pfn))
688 			continue;
689 
690 		/*
691 		 * Check for overlapping nodes/zones. It's possible on some
692 		 * configurations to have a setup like
693 		 * node0 node1 node0
694 		 * i.e. it's possible that all pages within a zones range of
695 		 * pages do not belong to a single zone.
696 		 */
697 		page = pfn_to_page(pfn);
698 		if (page_zone(page) != zone)
699 			continue;
700 
701 		/* Check the block is suitable for migration */
702 		if (!suitable_migration_target(page))
703 			continue;
704 
705 		/* If isolation recently failed, do not retry */
706 		if (!isolation_suitable(cc, page))
707 			continue;
708 
709 		/* Found a block suitable for isolating free pages from */
710 		isolated = 0;
711 
712 		/*
713 		 * As pfn may not start aligned, pfn+pageblock_nr_page
714 		 * may cross a MAX_ORDER_NR_PAGES boundary and miss
715 		 * a pfn_valid check. Ensure isolate_freepages_block()
716 		 * only scans within a pageblock
717 		 */
718 		end_pfn = ALIGN(pfn + 1, pageblock_nr_pages);
719 		end_pfn = min(end_pfn, z_end_pfn);
720 		isolated = isolate_freepages_block(cc, pfn, end_pfn,
721 						   freelist, false);
722 		nr_freepages += isolated;
723 
724 		/*
725 		 * Record the highest PFN we isolated pages from. When next
726 		 * looking for free pages, the search will restart here as
727 		 * page migration may have returned some pages to the allocator
728 		 */
729 		if (isolated) {
730 			cc->finished_update_free = true;
731 			high_pfn = max(high_pfn, pfn);
732 		}
733 	}
734 
735 	/* split_free_page does not map the pages */
736 	map_pages(freelist);
737 
738 	cc->free_pfn = high_pfn;
739 	cc->nr_freepages = nr_freepages;
740 }
741 
742 /*
743  * This is a migrate-callback that "allocates" freepages by taking pages
744  * from the isolated freelists in the block we are migrating to.
745  */
746 static struct page *compaction_alloc(struct page *migratepage,
747 					unsigned long data,
748 					int **result)
749 {
750 	struct compact_control *cc = (struct compact_control *)data;
751 	struct page *freepage;
752 
753 	/* Isolate free pages if necessary */
754 	if (list_empty(&cc->freepages)) {
755 		isolate_freepages(cc->zone, cc);
756 
757 		if (list_empty(&cc->freepages))
758 			return NULL;
759 	}
760 
761 	freepage = list_entry(cc->freepages.next, struct page, lru);
762 	list_del(&freepage->lru);
763 	cc->nr_freepages--;
764 
765 	return freepage;
766 }
767 
768 /*
769  * We cannot control nr_migratepages and nr_freepages fully when migration is
770  * running as migrate_pages() has no knowledge of compact_control. When
771  * migration is complete, we count the number of pages on the lists by hand.
772  */
773 static void update_nr_listpages(struct compact_control *cc)
774 {
775 	int nr_migratepages = 0;
776 	int nr_freepages = 0;
777 	struct page *page;
778 
779 	list_for_each_entry(page, &cc->migratepages, lru)
780 		nr_migratepages++;
781 	list_for_each_entry(page, &cc->freepages, lru)
782 		nr_freepages++;
783 
784 	cc->nr_migratepages = nr_migratepages;
785 	cc->nr_freepages = nr_freepages;
786 }
787 
788 /* possible outcome of isolate_migratepages */
789 typedef enum {
790 	ISOLATE_ABORT,		/* Abort compaction now */
791 	ISOLATE_NONE,		/* No pages isolated, continue scanning */
792 	ISOLATE_SUCCESS,	/* Pages isolated, migrate */
793 } isolate_migrate_t;
794 
795 /*
796  * Isolate all pages that can be migrated from the block pointed to by
797  * the migrate scanner within compact_control.
798  */
799 static isolate_migrate_t isolate_migratepages(struct zone *zone,
800 					struct compact_control *cc)
801 {
802 	unsigned long low_pfn, end_pfn;
803 
804 	/* Do not scan outside zone boundaries */
805 	low_pfn = max(cc->migrate_pfn, zone->zone_start_pfn);
806 
807 	/* Only scan within a pageblock boundary */
808 	end_pfn = ALIGN(low_pfn + 1, pageblock_nr_pages);
809 
810 	/* Do not cross the free scanner or scan within a memory hole */
811 	if (end_pfn > cc->free_pfn || !pfn_valid(low_pfn)) {
812 		cc->migrate_pfn = end_pfn;
813 		return ISOLATE_NONE;
814 	}
815 
816 	/* Perform the isolation */
817 	low_pfn = isolate_migratepages_range(zone, cc, low_pfn, end_pfn, false);
818 	if (!low_pfn || cc->contended)
819 		return ISOLATE_ABORT;
820 
821 	cc->migrate_pfn = low_pfn;
822 
823 	return ISOLATE_SUCCESS;
824 }
825 
826 static int compact_finished(struct zone *zone,
827 			    struct compact_control *cc)
828 {
829 	unsigned int order;
830 	unsigned long watermark;
831 
832 	if (fatal_signal_pending(current))
833 		return COMPACT_PARTIAL;
834 
835 	/* Compaction run completes if the migrate and free scanner meet */
836 	if (cc->free_pfn <= cc->migrate_pfn) {
837 		/*
838 		 * Mark that the PG_migrate_skip information should be cleared
839 		 * by kswapd when it goes to sleep. kswapd does not set the
840 		 * flag itself as the decision to be clear should be directly
841 		 * based on an allocation request.
842 		 */
843 		if (!current_is_kswapd())
844 			zone->compact_blockskip_flush = true;
845 
846 		return COMPACT_COMPLETE;
847 	}
848 
849 	/*
850 	 * order == -1 is expected when compacting via
851 	 * /proc/sys/vm/compact_memory
852 	 */
853 	if (cc->order == -1)
854 		return COMPACT_CONTINUE;
855 
856 	/* Compaction run is not finished if the watermark is not met */
857 	watermark = low_wmark_pages(zone);
858 	watermark += (1 << cc->order);
859 
860 	if (!zone_watermark_ok(zone, cc->order, watermark, 0, 0))
861 		return COMPACT_CONTINUE;
862 
863 	/* Direct compactor: Is a suitable page free? */
864 	for (order = cc->order; order < MAX_ORDER; order++) {
865 		struct free_area *area = &zone->free_area[order];
866 
867 		/* Job done if page is free of the right migratetype */
868 		if (!list_empty(&area->free_list[cc->migratetype]))
869 			return COMPACT_PARTIAL;
870 
871 		/* Job done if allocation would set block type */
872 		if (cc->order >= pageblock_order && area->nr_free)
873 			return COMPACT_PARTIAL;
874 	}
875 
876 	return COMPACT_CONTINUE;
877 }
878 
879 /*
880  * compaction_suitable: Is this suitable to run compaction on this zone now?
881  * Returns
882  *   COMPACT_SKIPPED  - If there are too few free pages for compaction
883  *   COMPACT_PARTIAL  - If the allocation would succeed without compaction
884  *   COMPACT_CONTINUE - If compaction should run now
885  */
886 unsigned long compaction_suitable(struct zone *zone, int order)
887 {
888 	int fragindex;
889 	unsigned long watermark;
890 
891 	/*
892 	 * order == -1 is expected when compacting via
893 	 * /proc/sys/vm/compact_memory
894 	 */
895 	if (order == -1)
896 		return COMPACT_CONTINUE;
897 
898 	/*
899 	 * Watermarks for order-0 must be met for compaction. Note the 2UL.
900 	 * This is because during migration, copies of pages need to be
901 	 * allocated and for a short time, the footprint is higher
902 	 */
903 	watermark = low_wmark_pages(zone) + (2UL << order);
904 	if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
905 		return COMPACT_SKIPPED;
906 
907 	/*
908 	 * fragmentation index determines if allocation failures are due to
909 	 * low memory or external fragmentation
910 	 *
911 	 * index of -1000 implies allocations might succeed depending on
912 	 * watermarks
913 	 * index towards 0 implies failure is due to lack of memory
914 	 * index towards 1000 implies failure is due to fragmentation
915 	 *
916 	 * Only compact if a failure would be due to fragmentation.
917 	 */
918 	fragindex = fragmentation_index(zone, order);
919 	if (fragindex >= 0 && fragindex <= sysctl_extfrag_threshold)
920 		return COMPACT_SKIPPED;
921 
922 	if (fragindex == -1000 && zone_watermark_ok(zone, order, watermark,
923 	    0, 0))
924 		return COMPACT_PARTIAL;
925 
926 	return COMPACT_CONTINUE;
927 }
928 
929 static int compact_zone(struct zone *zone, struct compact_control *cc)
930 {
931 	int ret;
932 	unsigned long start_pfn = zone->zone_start_pfn;
933 	unsigned long end_pfn = zone_end_pfn(zone);
934 
935 	ret = compaction_suitable(zone, cc->order);
936 	switch (ret) {
937 	case COMPACT_PARTIAL:
938 	case COMPACT_SKIPPED:
939 		/* Compaction is likely to fail */
940 		return ret;
941 	case COMPACT_CONTINUE:
942 		/* Fall through to compaction */
943 		;
944 	}
945 
946 	/*
947 	 * Setup to move all movable pages to the end of the zone. Used cached
948 	 * information on where the scanners should start but check that it
949 	 * is initialised by ensuring the values are within zone boundaries.
950 	 */
951 	cc->migrate_pfn = zone->compact_cached_migrate_pfn;
952 	cc->free_pfn = zone->compact_cached_free_pfn;
953 	if (cc->free_pfn < start_pfn || cc->free_pfn > end_pfn) {
954 		cc->free_pfn = end_pfn & ~(pageblock_nr_pages-1);
955 		zone->compact_cached_free_pfn = cc->free_pfn;
956 	}
957 	if (cc->migrate_pfn < start_pfn || cc->migrate_pfn > end_pfn) {
958 		cc->migrate_pfn = start_pfn;
959 		zone->compact_cached_migrate_pfn = cc->migrate_pfn;
960 	}
961 
962 	/*
963 	 * Clear pageblock skip if there were failures recently and compaction
964 	 * is about to be retried after being deferred. kswapd does not do
965 	 * this reset as it'll reset the cached information when going to sleep.
966 	 */
967 	if (compaction_restarting(zone, cc->order) && !current_is_kswapd())
968 		__reset_isolation_suitable(zone);
969 
970 	migrate_prep_local();
971 
972 	while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) {
973 		unsigned long nr_migrate, nr_remaining;
974 		int err;
975 
976 		switch (isolate_migratepages(zone, cc)) {
977 		case ISOLATE_ABORT:
978 			ret = COMPACT_PARTIAL;
979 			putback_movable_pages(&cc->migratepages);
980 			cc->nr_migratepages = 0;
981 			goto out;
982 		case ISOLATE_NONE:
983 			continue;
984 		case ISOLATE_SUCCESS:
985 			;
986 		}
987 
988 		nr_migrate = cc->nr_migratepages;
989 		err = migrate_pages(&cc->migratepages, compaction_alloc,
990 				(unsigned long)cc,
991 				cc->sync ? MIGRATE_SYNC_LIGHT : MIGRATE_ASYNC,
992 				MR_COMPACTION);
993 		update_nr_listpages(cc);
994 		nr_remaining = cc->nr_migratepages;
995 
996 		trace_mm_compaction_migratepages(nr_migrate - nr_remaining,
997 						nr_remaining);
998 
999 		/* Release isolated pages not migrated */
1000 		if (err) {
1001 			putback_movable_pages(&cc->migratepages);
1002 			cc->nr_migratepages = 0;
1003 			if (err == -ENOMEM) {
1004 				ret = COMPACT_PARTIAL;
1005 				goto out;
1006 			}
1007 		}
1008 	}
1009 
1010 out:
1011 	/* Release free pages and check accounting */
1012 	cc->nr_freepages -= release_freepages(&cc->freepages);
1013 	VM_BUG_ON(cc->nr_freepages != 0);
1014 
1015 	return ret;
1016 }
1017 
1018 static unsigned long compact_zone_order(struct zone *zone,
1019 				 int order, gfp_t gfp_mask,
1020 				 bool sync, bool *contended)
1021 {
1022 	unsigned long ret;
1023 	struct compact_control cc = {
1024 		.nr_freepages = 0,
1025 		.nr_migratepages = 0,
1026 		.order = order,
1027 		.migratetype = allocflags_to_migratetype(gfp_mask),
1028 		.zone = zone,
1029 		.sync = sync,
1030 	};
1031 	INIT_LIST_HEAD(&cc.freepages);
1032 	INIT_LIST_HEAD(&cc.migratepages);
1033 
1034 	ret = compact_zone(zone, &cc);
1035 
1036 	VM_BUG_ON(!list_empty(&cc.freepages));
1037 	VM_BUG_ON(!list_empty(&cc.migratepages));
1038 
1039 	*contended = cc.contended;
1040 	return ret;
1041 }
1042 
1043 int sysctl_extfrag_threshold = 500;
1044 
1045 /**
1046  * try_to_compact_pages - Direct compact to satisfy a high-order allocation
1047  * @zonelist: The zonelist used for the current allocation
1048  * @order: The order of the current allocation
1049  * @gfp_mask: The GFP mask of the current allocation
1050  * @nodemask: The allowed nodes to allocate from
1051  * @sync: Whether migration is synchronous or not
1052  * @contended: Return value that is true if compaction was aborted due to lock contention
1053  * @page: Optionally capture a free page of the requested order during compaction
1054  *
1055  * This is the main entry point for direct page compaction.
1056  */
1057 unsigned long try_to_compact_pages(struct zonelist *zonelist,
1058 			int order, gfp_t gfp_mask, nodemask_t *nodemask,
1059 			bool sync, bool *contended)
1060 {
1061 	enum zone_type high_zoneidx = gfp_zone(gfp_mask);
1062 	int may_enter_fs = gfp_mask & __GFP_FS;
1063 	int may_perform_io = gfp_mask & __GFP_IO;
1064 	struct zoneref *z;
1065 	struct zone *zone;
1066 	int rc = COMPACT_SKIPPED;
1067 	int alloc_flags = 0;
1068 
1069 	/* Check if the GFP flags allow compaction */
1070 	if (!order || !may_enter_fs || !may_perform_io)
1071 		return rc;
1072 
1073 	count_compact_event(COMPACTSTALL);
1074 
1075 #ifdef CONFIG_CMA
1076 	if (allocflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
1077 		alloc_flags |= ALLOC_CMA;
1078 #endif
1079 	/* Compact each zone in the list */
1080 	for_each_zone_zonelist_nodemask(zone, z, zonelist, high_zoneidx,
1081 								nodemask) {
1082 		int status;
1083 
1084 		status = compact_zone_order(zone, order, gfp_mask, sync,
1085 						contended);
1086 		rc = max(status, rc);
1087 
1088 		/* If a normal allocation would succeed, stop compacting */
1089 		if (zone_watermark_ok(zone, order, low_wmark_pages(zone), 0,
1090 				      alloc_flags))
1091 			break;
1092 	}
1093 
1094 	return rc;
1095 }
1096 
1097 
1098 /* Compact all zones within a node */
1099 static void __compact_pgdat(pg_data_t *pgdat, struct compact_control *cc)
1100 {
1101 	int zoneid;
1102 	struct zone *zone;
1103 
1104 	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
1105 
1106 		zone = &pgdat->node_zones[zoneid];
1107 		if (!populated_zone(zone))
1108 			continue;
1109 
1110 		cc->nr_freepages = 0;
1111 		cc->nr_migratepages = 0;
1112 		cc->zone = zone;
1113 		INIT_LIST_HEAD(&cc->freepages);
1114 		INIT_LIST_HEAD(&cc->migratepages);
1115 
1116 		if (cc->order == -1 || !compaction_deferred(zone, cc->order))
1117 			compact_zone(zone, cc);
1118 
1119 		if (cc->order > 0) {
1120 			int ok = zone_watermark_ok(zone, cc->order,
1121 						low_wmark_pages(zone), 0, 0);
1122 			if (ok && cc->order >= zone->compact_order_failed)
1123 				zone->compact_order_failed = cc->order + 1;
1124 			/* Currently async compaction is never deferred. */
1125 			else if (!ok && cc->sync)
1126 				defer_compaction(zone, cc->order);
1127 		}
1128 
1129 		VM_BUG_ON(!list_empty(&cc->freepages));
1130 		VM_BUG_ON(!list_empty(&cc->migratepages));
1131 	}
1132 }
1133 
1134 void compact_pgdat(pg_data_t *pgdat, int order)
1135 {
1136 	struct compact_control cc = {
1137 		.order = order,
1138 		.sync = false,
1139 	};
1140 
1141 	if (!order)
1142 		return;
1143 
1144 	__compact_pgdat(pgdat, &cc);
1145 }
1146 
1147 static void compact_node(int nid)
1148 {
1149 	struct compact_control cc = {
1150 		.order = -1,
1151 		.sync = true,
1152 	};
1153 
1154 	__compact_pgdat(NODE_DATA(nid), &cc);
1155 }
1156 
1157 /* Compact all nodes in the system */
1158 static void compact_nodes(void)
1159 {
1160 	int nid;
1161 
1162 	/* Flush pending updates to the LRU lists */
1163 	lru_add_drain_all();
1164 
1165 	for_each_online_node(nid)
1166 		compact_node(nid);
1167 }
1168 
1169 /* The written value is actually unused, all memory is compacted */
1170 int sysctl_compact_memory;
1171 
1172 /* This is the entry point for compacting all nodes via /proc/sys/vm */
1173 int sysctl_compaction_handler(struct ctl_table *table, int write,
1174 			void __user *buffer, size_t *length, loff_t *ppos)
1175 {
1176 	if (write)
1177 		compact_nodes();
1178 
1179 	return 0;
1180 }
1181 
1182 int sysctl_extfrag_handler(struct ctl_table *table, int write,
1183 			void __user *buffer, size_t *length, loff_t *ppos)
1184 {
1185 	proc_dointvec_minmax(table, write, buffer, length, ppos);
1186 
1187 	return 0;
1188 }
1189 
1190 #if defined(CONFIG_SYSFS) && defined(CONFIG_NUMA)
1191 ssize_t sysfs_compact_node(struct device *dev,
1192 			struct device_attribute *attr,
1193 			const char *buf, size_t count)
1194 {
1195 	int nid = dev->id;
1196 
1197 	if (nid >= 0 && nid < nr_node_ids && node_online(nid)) {
1198 		/* Flush pending updates to the LRU lists */
1199 		lru_add_drain_all();
1200 
1201 		compact_node(nid);
1202 	}
1203 
1204 	return count;
1205 }
1206 static DEVICE_ATTR(compact, S_IWUSR, NULL, sysfs_compact_node);
1207 
1208 int compaction_register_node(struct node *node)
1209 {
1210 	return device_create_file(&node->dev, &dev_attr_compact);
1211 }
1212 
1213 void compaction_unregister_node(struct node *node)
1214 {
1215 	return device_remove_file(&node->dev, &dev_attr_compact);
1216 }
1217 #endif /* CONFIG_SYSFS && CONFIG_NUMA */
1218 
1219 #endif /* CONFIG_COMPACTION */
1220