xref: /openbmc/linux/mm/compaction.c (revision 4cfb9080)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * linux/mm/compaction.c
4  *
5  * Memory compaction for the reduction of external fragmentation. Note that
6  * this heavily depends upon page migration to do all the real heavy
7  * lifting
8  *
9  * Copyright IBM Corp. 2007-2010 Mel Gorman <mel@csn.ul.ie>
10  */
11 #include <linux/cpu.h>
12 #include <linux/swap.h>
13 #include <linux/migrate.h>
14 #include <linux/compaction.h>
15 #include <linux/mm_inline.h>
16 #include <linux/sched/signal.h>
17 #include <linux/backing-dev.h>
18 #include <linux/sysctl.h>
19 #include <linux/sysfs.h>
20 #include <linux/page-isolation.h>
21 #include <linux/kasan.h>
22 #include <linux/kthread.h>
23 #include <linux/freezer.h>
24 #include <linux/page_owner.h>
25 #include <linux/psi.h>
26 #include "internal.h"
27 
28 #ifdef CONFIG_COMPACTION
29 /*
30  * Fragmentation score check interval for proactive compaction purposes.
31  */
32 #define HPAGE_FRAG_CHECK_INTERVAL_MSEC	(500)
33 
34 static inline void count_compact_event(enum vm_event_item item)
35 {
36 	count_vm_event(item);
37 }
38 
39 static inline void count_compact_events(enum vm_event_item item, long delta)
40 {
41 	count_vm_events(item, delta);
42 }
43 #else
44 #define count_compact_event(item) do { } while (0)
45 #define count_compact_events(item, delta) do { } while (0)
46 #endif
47 
48 #if defined CONFIG_COMPACTION || defined CONFIG_CMA
49 
50 #define CREATE_TRACE_POINTS
51 #include <trace/events/compaction.h>
52 
53 #define block_start_pfn(pfn, order)	round_down(pfn, 1UL << (order))
54 #define block_end_pfn(pfn, order)	ALIGN((pfn) + 1, 1UL << (order))
55 
56 /*
57  * Page order with-respect-to which proactive compaction
58  * calculates external fragmentation, which is used as
59  * the "fragmentation score" of a node/zone.
60  */
61 #if defined CONFIG_TRANSPARENT_HUGEPAGE
62 #define COMPACTION_HPAGE_ORDER	HPAGE_PMD_ORDER
63 #elif defined CONFIG_HUGETLBFS
64 #define COMPACTION_HPAGE_ORDER	HUGETLB_PAGE_ORDER
65 #else
66 #define COMPACTION_HPAGE_ORDER	(PMD_SHIFT - PAGE_SHIFT)
67 #endif
68 
69 static unsigned long release_freepages(struct list_head *freelist)
70 {
71 	struct page *page, *next;
72 	unsigned long high_pfn = 0;
73 
74 	list_for_each_entry_safe(page, next, freelist, lru) {
75 		unsigned long pfn = page_to_pfn(page);
76 		list_del(&page->lru);
77 		__free_page(page);
78 		if (pfn > high_pfn)
79 			high_pfn = pfn;
80 	}
81 
82 	return high_pfn;
83 }
84 
85 static void split_map_pages(struct list_head *list)
86 {
87 	unsigned int i, order, nr_pages;
88 	struct page *page, *next;
89 	LIST_HEAD(tmp_list);
90 
91 	list_for_each_entry_safe(page, next, list, lru) {
92 		list_del(&page->lru);
93 
94 		order = page_private(page);
95 		nr_pages = 1 << order;
96 
97 		post_alloc_hook(page, order, __GFP_MOVABLE);
98 		if (order)
99 			split_page(page, order);
100 
101 		for (i = 0; i < nr_pages; i++) {
102 			list_add(&page->lru, &tmp_list);
103 			page++;
104 		}
105 	}
106 
107 	list_splice(&tmp_list, list);
108 }
109 
110 #ifdef CONFIG_COMPACTION
111 bool PageMovable(struct page *page)
112 {
113 	const struct movable_operations *mops;
114 
115 	VM_BUG_ON_PAGE(!PageLocked(page), page);
116 	if (!__PageMovable(page))
117 		return false;
118 
119 	mops = page_movable_ops(page);
120 	if (mops)
121 		return true;
122 
123 	return false;
124 }
125 
126 void __SetPageMovable(struct page *page, const struct movable_operations *mops)
127 {
128 	VM_BUG_ON_PAGE(!PageLocked(page), page);
129 	VM_BUG_ON_PAGE((unsigned long)mops & PAGE_MAPPING_MOVABLE, page);
130 	page->mapping = (void *)((unsigned long)mops | PAGE_MAPPING_MOVABLE);
131 }
132 EXPORT_SYMBOL(__SetPageMovable);
133 
134 void __ClearPageMovable(struct page *page)
135 {
136 	VM_BUG_ON_PAGE(!PageMovable(page), page);
137 	/*
138 	 * This page still has the type of a movable page, but it's
139 	 * actually not movable any more.
140 	 */
141 	page->mapping = (void *)PAGE_MAPPING_MOVABLE;
142 }
143 EXPORT_SYMBOL(__ClearPageMovable);
144 
145 /* Do not skip compaction more than 64 times */
146 #define COMPACT_MAX_DEFER_SHIFT 6
147 
148 /*
149  * Compaction is deferred when compaction fails to result in a page
150  * allocation success. 1 << compact_defer_shift, compactions are skipped up
151  * to a limit of 1 << COMPACT_MAX_DEFER_SHIFT
152  */
153 static void defer_compaction(struct zone *zone, int order)
154 {
155 	zone->compact_considered = 0;
156 	zone->compact_defer_shift++;
157 
158 	if (order < zone->compact_order_failed)
159 		zone->compact_order_failed = order;
160 
161 	if (zone->compact_defer_shift > COMPACT_MAX_DEFER_SHIFT)
162 		zone->compact_defer_shift = COMPACT_MAX_DEFER_SHIFT;
163 
164 	trace_mm_compaction_defer_compaction(zone, order);
165 }
166 
167 /* Returns true if compaction should be skipped this time */
168 static bool compaction_deferred(struct zone *zone, int order)
169 {
170 	unsigned long defer_limit = 1UL << zone->compact_defer_shift;
171 
172 	if (order < zone->compact_order_failed)
173 		return false;
174 
175 	/* Avoid possible overflow */
176 	if (++zone->compact_considered >= defer_limit) {
177 		zone->compact_considered = defer_limit;
178 		return false;
179 	}
180 
181 	trace_mm_compaction_deferred(zone, order);
182 
183 	return true;
184 }
185 
186 /*
187  * Update defer tracking counters after successful compaction of given order,
188  * which means an allocation either succeeded (alloc_success == true) or is
189  * expected to succeed.
190  */
191 void compaction_defer_reset(struct zone *zone, int order,
192 		bool alloc_success)
193 {
194 	if (alloc_success) {
195 		zone->compact_considered = 0;
196 		zone->compact_defer_shift = 0;
197 	}
198 	if (order >= zone->compact_order_failed)
199 		zone->compact_order_failed = order + 1;
200 
201 	trace_mm_compaction_defer_reset(zone, order);
202 }
203 
204 /* Returns true if restarting compaction after many failures */
205 static bool compaction_restarting(struct zone *zone, int order)
206 {
207 	if (order < zone->compact_order_failed)
208 		return false;
209 
210 	return zone->compact_defer_shift == COMPACT_MAX_DEFER_SHIFT &&
211 		zone->compact_considered >= 1UL << zone->compact_defer_shift;
212 }
213 
214 /* Returns true if the pageblock should be scanned for pages to isolate. */
215 static inline bool isolation_suitable(struct compact_control *cc,
216 					struct page *page)
217 {
218 	if (cc->ignore_skip_hint)
219 		return true;
220 
221 	return !get_pageblock_skip(page);
222 }
223 
224 static void reset_cached_positions(struct zone *zone)
225 {
226 	zone->compact_cached_migrate_pfn[0] = zone->zone_start_pfn;
227 	zone->compact_cached_migrate_pfn[1] = zone->zone_start_pfn;
228 	zone->compact_cached_free_pfn =
229 				pageblock_start_pfn(zone_end_pfn(zone) - 1);
230 }
231 
232 #ifdef CONFIG_SPARSEMEM
233 /*
234  * If the PFN falls into an offline section, return the start PFN of the
235  * next online section. If the PFN falls into an online section or if
236  * there is no next online section, return 0.
237  */
238 static unsigned long skip_offline_sections(unsigned long start_pfn)
239 {
240 	unsigned long start_nr = pfn_to_section_nr(start_pfn);
241 
242 	if (online_section_nr(start_nr))
243 		return 0;
244 
245 	while (++start_nr <= __highest_present_section_nr) {
246 		if (online_section_nr(start_nr))
247 			return section_nr_to_pfn(start_nr);
248 	}
249 
250 	return 0;
251 }
252 #else
253 static unsigned long skip_offline_sections(unsigned long start_pfn)
254 {
255 	return 0;
256 }
257 #endif
258 
259 /*
260  * Compound pages of >= pageblock_order should consistently be skipped until
261  * released. It is always pointless to compact pages of such order (if they are
262  * migratable), and the pageblocks they occupy cannot contain any free pages.
263  */
264 static bool pageblock_skip_persistent(struct page *page)
265 {
266 	if (!PageCompound(page))
267 		return false;
268 
269 	page = compound_head(page);
270 
271 	if (compound_order(page) >= pageblock_order)
272 		return true;
273 
274 	return false;
275 }
276 
277 static bool
278 __reset_isolation_pfn(struct zone *zone, unsigned long pfn, bool check_source,
279 							bool check_target)
280 {
281 	struct page *page = pfn_to_online_page(pfn);
282 	struct page *block_page;
283 	struct page *end_page;
284 	unsigned long block_pfn;
285 
286 	if (!page)
287 		return false;
288 	if (zone != page_zone(page))
289 		return false;
290 	if (pageblock_skip_persistent(page))
291 		return false;
292 
293 	/*
294 	 * If skip is already cleared do no further checking once the
295 	 * restart points have been set.
296 	 */
297 	if (check_source && check_target && !get_pageblock_skip(page))
298 		return true;
299 
300 	/*
301 	 * If clearing skip for the target scanner, do not select a
302 	 * non-movable pageblock as the starting point.
303 	 */
304 	if (!check_source && check_target &&
305 	    get_pageblock_migratetype(page) != MIGRATE_MOVABLE)
306 		return false;
307 
308 	/* Ensure the start of the pageblock or zone is online and valid */
309 	block_pfn = pageblock_start_pfn(pfn);
310 	block_pfn = max(block_pfn, zone->zone_start_pfn);
311 	block_page = pfn_to_online_page(block_pfn);
312 	if (block_page) {
313 		page = block_page;
314 		pfn = block_pfn;
315 	}
316 
317 	/* Ensure the end of the pageblock or zone is online and valid */
318 	block_pfn = pageblock_end_pfn(pfn) - 1;
319 	block_pfn = min(block_pfn, zone_end_pfn(zone) - 1);
320 	end_page = pfn_to_online_page(block_pfn);
321 	if (!end_page)
322 		return false;
323 
324 	/*
325 	 * Only clear the hint if a sample indicates there is either a
326 	 * free page or an LRU page in the block. One or other condition
327 	 * is necessary for the block to be a migration source/target.
328 	 */
329 	do {
330 		if (check_source && PageLRU(page)) {
331 			clear_pageblock_skip(page);
332 			return true;
333 		}
334 
335 		if (check_target && PageBuddy(page)) {
336 			clear_pageblock_skip(page);
337 			return true;
338 		}
339 
340 		page += (1 << PAGE_ALLOC_COSTLY_ORDER);
341 	} while (page <= end_page);
342 
343 	return false;
344 }
345 
346 /*
347  * This function is called to clear all cached information on pageblocks that
348  * should be skipped for page isolation when the migrate and free page scanner
349  * meet.
350  */
351 static void __reset_isolation_suitable(struct zone *zone)
352 {
353 	unsigned long migrate_pfn = zone->zone_start_pfn;
354 	unsigned long free_pfn = zone_end_pfn(zone) - 1;
355 	unsigned long reset_migrate = free_pfn;
356 	unsigned long reset_free = migrate_pfn;
357 	bool source_set = false;
358 	bool free_set = false;
359 
360 	if (!zone->compact_blockskip_flush)
361 		return;
362 
363 	zone->compact_blockskip_flush = false;
364 
365 	/*
366 	 * Walk the zone and update pageblock skip information. Source looks
367 	 * for PageLRU while target looks for PageBuddy. When the scanner
368 	 * is found, both PageBuddy and PageLRU are checked as the pageblock
369 	 * is suitable as both source and target.
370 	 */
371 	for (; migrate_pfn < free_pfn; migrate_pfn += pageblock_nr_pages,
372 					free_pfn -= pageblock_nr_pages) {
373 		cond_resched();
374 
375 		/* Update the migrate PFN */
376 		if (__reset_isolation_pfn(zone, migrate_pfn, true, source_set) &&
377 		    migrate_pfn < reset_migrate) {
378 			source_set = true;
379 			reset_migrate = migrate_pfn;
380 			zone->compact_init_migrate_pfn = reset_migrate;
381 			zone->compact_cached_migrate_pfn[0] = reset_migrate;
382 			zone->compact_cached_migrate_pfn[1] = reset_migrate;
383 		}
384 
385 		/* Update the free PFN */
386 		if (__reset_isolation_pfn(zone, free_pfn, free_set, true) &&
387 		    free_pfn > reset_free) {
388 			free_set = true;
389 			reset_free = free_pfn;
390 			zone->compact_init_free_pfn = reset_free;
391 			zone->compact_cached_free_pfn = reset_free;
392 		}
393 	}
394 
395 	/* Leave no distance if no suitable block was reset */
396 	if (reset_migrate >= reset_free) {
397 		zone->compact_cached_migrate_pfn[0] = migrate_pfn;
398 		zone->compact_cached_migrate_pfn[1] = migrate_pfn;
399 		zone->compact_cached_free_pfn = free_pfn;
400 	}
401 }
402 
403 void reset_isolation_suitable(pg_data_t *pgdat)
404 {
405 	int zoneid;
406 
407 	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
408 		struct zone *zone = &pgdat->node_zones[zoneid];
409 		if (!populated_zone(zone))
410 			continue;
411 
412 		/* Only flush if a full compaction finished recently */
413 		if (zone->compact_blockskip_flush)
414 			__reset_isolation_suitable(zone);
415 	}
416 }
417 
418 /*
419  * Sets the pageblock skip bit if it was clear. Note that this is a hint as
420  * locks are not required for read/writers. Returns true if it was already set.
421  */
422 static bool test_and_set_skip(struct compact_control *cc, struct page *page)
423 {
424 	bool skip;
425 
426 	/* Do not update if skip hint is being ignored */
427 	if (cc->ignore_skip_hint)
428 		return false;
429 
430 	skip = get_pageblock_skip(page);
431 	if (!skip && !cc->no_set_skip_hint)
432 		set_pageblock_skip(page);
433 
434 	return skip;
435 }
436 
437 static void update_cached_migrate(struct compact_control *cc, unsigned long pfn)
438 {
439 	struct zone *zone = cc->zone;
440 
441 	pfn = pageblock_end_pfn(pfn);
442 
443 	/* Set for isolation rather than compaction */
444 	if (cc->no_set_skip_hint)
445 		return;
446 
447 	if (pfn > zone->compact_cached_migrate_pfn[0])
448 		zone->compact_cached_migrate_pfn[0] = pfn;
449 	if (cc->mode != MIGRATE_ASYNC &&
450 	    pfn > zone->compact_cached_migrate_pfn[1])
451 		zone->compact_cached_migrate_pfn[1] = pfn;
452 }
453 
454 /*
455  * If no pages were isolated then mark this pageblock to be skipped in the
456  * future. The information is later cleared by __reset_isolation_suitable().
457  */
458 static void update_pageblock_skip(struct compact_control *cc,
459 			struct page *page, unsigned long pfn)
460 {
461 	struct zone *zone = cc->zone;
462 
463 	if (cc->no_set_skip_hint)
464 		return;
465 
466 	set_pageblock_skip(page);
467 
468 	/* Update where async and sync compaction should restart */
469 	if (pfn < zone->compact_cached_free_pfn)
470 		zone->compact_cached_free_pfn = pfn;
471 }
472 #else
473 static inline bool isolation_suitable(struct compact_control *cc,
474 					struct page *page)
475 {
476 	return true;
477 }
478 
479 static inline bool pageblock_skip_persistent(struct page *page)
480 {
481 	return false;
482 }
483 
484 static inline void update_pageblock_skip(struct compact_control *cc,
485 			struct page *page, unsigned long pfn)
486 {
487 }
488 
489 static void update_cached_migrate(struct compact_control *cc, unsigned long pfn)
490 {
491 }
492 
493 static bool test_and_set_skip(struct compact_control *cc, struct page *page)
494 {
495 	return false;
496 }
497 #endif /* CONFIG_COMPACTION */
498 
499 /*
500  * Compaction requires the taking of some coarse locks that are potentially
501  * very heavily contended. For async compaction, trylock and record if the
502  * lock is contended. The lock will still be acquired but compaction will
503  * abort when the current block is finished regardless of success rate.
504  * Sync compaction acquires the lock.
505  *
506  * Always returns true which makes it easier to track lock state in callers.
507  */
508 static bool compact_lock_irqsave(spinlock_t *lock, unsigned long *flags,
509 						struct compact_control *cc)
510 	__acquires(lock)
511 {
512 	/* Track if the lock is contended in async mode */
513 	if (cc->mode == MIGRATE_ASYNC && !cc->contended) {
514 		if (spin_trylock_irqsave(lock, *flags))
515 			return true;
516 
517 		cc->contended = true;
518 	}
519 
520 	spin_lock_irqsave(lock, *flags);
521 	return true;
522 }
523 
524 /*
525  * Compaction requires the taking of some coarse locks that are potentially
526  * very heavily contended. The lock should be periodically unlocked to avoid
527  * having disabled IRQs for a long time, even when there is nobody waiting on
528  * the lock. It might also be that allowing the IRQs will result in
529  * need_resched() becoming true. If scheduling is needed, compaction schedules.
530  * Either compaction type will also abort if a fatal signal is pending.
531  * In either case if the lock was locked, it is dropped and not regained.
532  *
533  * Returns true if compaction should abort due to fatal signal pending.
534  * Returns false when compaction can continue.
535  */
536 static bool compact_unlock_should_abort(spinlock_t *lock,
537 		unsigned long flags, bool *locked, struct compact_control *cc)
538 {
539 	if (*locked) {
540 		spin_unlock_irqrestore(lock, flags);
541 		*locked = false;
542 	}
543 
544 	if (fatal_signal_pending(current)) {
545 		cc->contended = true;
546 		return true;
547 	}
548 
549 	cond_resched();
550 
551 	return false;
552 }
553 
554 /*
555  * Isolate free pages onto a private freelist. If @strict is true, will abort
556  * returning 0 on any invalid PFNs or non-free pages inside of the pageblock
557  * (even though it may still end up isolating some pages).
558  */
559 static unsigned long isolate_freepages_block(struct compact_control *cc,
560 				unsigned long *start_pfn,
561 				unsigned long end_pfn,
562 				struct list_head *freelist,
563 				unsigned int stride,
564 				bool strict)
565 {
566 	int nr_scanned = 0, total_isolated = 0;
567 	struct page *cursor;
568 	unsigned long flags = 0;
569 	bool locked = false;
570 	unsigned long blockpfn = *start_pfn;
571 	unsigned int order;
572 
573 	/* Strict mode is for isolation, speed is secondary */
574 	if (strict)
575 		stride = 1;
576 
577 	cursor = pfn_to_page(blockpfn);
578 
579 	/* Isolate free pages. */
580 	for (; blockpfn < end_pfn; blockpfn += stride, cursor += stride) {
581 		int isolated;
582 		struct page *page = cursor;
583 
584 		/*
585 		 * Periodically drop the lock (if held) regardless of its
586 		 * contention, to give chance to IRQs. Abort if fatal signal
587 		 * pending.
588 		 */
589 		if (!(blockpfn % COMPACT_CLUSTER_MAX)
590 		    && compact_unlock_should_abort(&cc->zone->lock, flags,
591 								&locked, cc))
592 			break;
593 
594 		nr_scanned++;
595 
596 		/*
597 		 * For compound pages such as THP and hugetlbfs, we can save
598 		 * potentially a lot of iterations if we skip them at once.
599 		 * The check is racy, but we can consider only valid values
600 		 * and the only danger is skipping too much.
601 		 */
602 		if (PageCompound(page)) {
603 			const unsigned int order = compound_order(page);
604 
605 			if (likely(order <= MAX_ORDER)) {
606 				blockpfn += (1UL << order) - 1;
607 				cursor += (1UL << order) - 1;
608 				nr_scanned += (1UL << order) - 1;
609 			}
610 			goto isolate_fail;
611 		}
612 
613 		if (!PageBuddy(page))
614 			goto isolate_fail;
615 
616 		/* If we already hold the lock, we can skip some rechecking. */
617 		if (!locked) {
618 			locked = compact_lock_irqsave(&cc->zone->lock,
619 								&flags, cc);
620 
621 			/* Recheck this is a buddy page under lock */
622 			if (!PageBuddy(page))
623 				goto isolate_fail;
624 		}
625 
626 		/* Found a free page, will break it into order-0 pages */
627 		order = buddy_order(page);
628 		isolated = __isolate_free_page(page, order);
629 		if (!isolated)
630 			break;
631 		set_page_private(page, order);
632 
633 		nr_scanned += isolated - 1;
634 		total_isolated += isolated;
635 		cc->nr_freepages += isolated;
636 		list_add_tail(&page->lru, freelist);
637 
638 		if (!strict && cc->nr_migratepages <= cc->nr_freepages) {
639 			blockpfn += isolated;
640 			break;
641 		}
642 		/* Advance to the end of split page */
643 		blockpfn += isolated - 1;
644 		cursor += isolated - 1;
645 		continue;
646 
647 isolate_fail:
648 		if (strict)
649 			break;
650 		else
651 			continue;
652 
653 	}
654 
655 	if (locked)
656 		spin_unlock_irqrestore(&cc->zone->lock, flags);
657 
658 	/*
659 	 * There is a tiny chance that we have read bogus compound_order(),
660 	 * so be careful to not go outside of the pageblock.
661 	 */
662 	if (unlikely(blockpfn > end_pfn))
663 		blockpfn = end_pfn;
664 
665 	trace_mm_compaction_isolate_freepages(*start_pfn, blockpfn,
666 					nr_scanned, total_isolated);
667 
668 	/* Record how far we have got within the block */
669 	*start_pfn = blockpfn;
670 
671 	/*
672 	 * If strict isolation is requested by CMA then check that all the
673 	 * pages requested were isolated. If there were any failures, 0 is
674 	 * returned and CMA will fail.
675 	 */
676 	if (strict && blockpfn < end_pfn)
677 		total_isolated = 0;
678 
679 	cc->total_free_scanned += nr_scanned;
680 	if (total_isolated)
681 		count_compact_events(COMPACTISOLATED, total_isolated);
682 	return total_isolated;
683 }
684 
685 /**
686  * isolate_freepages_range() - isolate free pages.
687  * @cc:        Compaction control structure.
688  * @start_pfn: The first PFN to start isolating.
689  * @end_pfn:   The one-past-last PFN.
690  *
691  * Non-free pages, invalid PFNs, or zone boundaries within the
692  * [start_pfn, end_pfn) range are considered errors, cause function to
693  * undo its actions and return zero.
694  *
695  * Otherwise, function returns one-past-the-last PFN of isolated page
696  * (which may be greater then end_pfn if end fell in a middle of
697  * a free page).
698  */
699 unsigned long
700 isolate_freepages_range(struct compact_control *cc,
701 			unsigned long start_pfn, unsigned long end_pfn)
702 {
703 	unsigned long isolated, pfn, block_start_pfn, block_end_pfn;
704 	LIST_HEAD(freelist);
705 
706 	pfn = start_pfn;
707 	block_start_pfn = pageblock_start_pfn(pfn);
708 	if (block_start_pfn < cc->zone->zone_start_pfn)
709 		block_start_pfn = cc->zone->zone_start_pfn;
710 	block_end_pfn = pageblock_end_pfn(pfn);
711 
712 	for (; pfn < end_pfn; pfn += isolated,
713 				block_start_pfn = block_end_pfn,
714 				block_end_pfn += pageblock_nr_pages) {
715 		/* Protect pfn from changing by isolate_freepages_block */
716 		unsigned long isolate_start_pfn = pfn;
717 
718 		block_end_pfn = min(block_end_pfn, end_pfn);
719 
720 		/*
721 		 * pfn could pass the block_end_pfn if isolated freepage
722 		 * is more than pageblock order. In this case, we adjust
723 		 * scanning range to right one.
724 		 */
725 		if (pfn >= block_end_pfn) {
726 			block_start_pfn = pageblock_start_pfn(pfn);
727 			block_end_pfn = pageblock_end_pfn(pfn);
728 			block_end_pfn = min(block_end_pfn, end_pfn);
729 		}
730 
731 		if (!pageblock_pfn_to_page(block_start_pfn,
732 					block_end_pfn, cc->zone))
733 			break;
734 
735 		isolated = isolate_freepages_block(cc, &isolate_start_pfn,
736 					block_end_pfn, &freelist, 0, true);
737 
738 		/*
739 		 * In strict mode, isolate_freepages_block() returns 0 if
740 		 * there are any holes in the block (ie. invalid PFNs or
741 		 * non-free pages).
742 		 */
743 		if (!isolated)
744 			break;
745 
746 		/*
747 		 * If we managed to isolate pages, it is always (1 << n) *
748 		 * pageblock_nr_pages for some non-negative n.  (Max order
749 		 * page may span two pageblocks).
750 		 */
751 	}
752 
753 	/* __isolate_free_page() does not map the pages */
754 	split_map_pages(&freelist);
755 
756 	if (pfn < end_pfn) {
757 		/* Loop terminated early, cleanup. */
758 		release_freepages(&freelist);
759 		return 0;
760 	}
761 
762 	/* We don't use freelists for anything. */
763 	return pfn;
764 }
765 
766 /* Similar to reclaim, but different enough that they don't share logic */
767 static bool too_many_isolated(struct compact_control *cc)
768 {
769 	pg_data_t *pgdat = cc->zone->zone_pgdat;
770 	bool too_many;
771 
772 	unsigned long active, inactive, isolated;
773 
774 	inactive = node_page_state(pgdat, NR_INACTIVE_FILE) +
775 			node_page_state(pgdat, NR_INACTIVE_ANON);
776 	active = node_page_state(pgdat, NR_ACTIVE_FILE) +
777 			node_page_state(pgdat, NR_ACTIVE_ANON);
778 	isolated = node_page_state(pgdat, NR_ISOLATED_FILE) +
779 			node_page_state(pgdat, NR_ISOLATED_ANON);
780 
781 	/*
782 	 * Allow GFP_NOFS to isolate past the limit set for regular
783 	 * compaction runs. This prevents an ABBA deadlock when other
784 	 * compactors have already isolated to the limit, but are
785 	 * blocked on filesystem locks held by the GFP_NOFS thread.
786 	 */
787 	if (cc->gfp_mask & __GFP_FS) {
788 		inactive >>= 3;
789 		active >>= 3;
790 	}
791 
792 	too_many = isolated > (inactive + active) / 2;
793 	if (!too_many)
794 		wake_throttle_isolated(pgdat);
795 
796 	return too_many;
797 }
798 
799 /**
800  * isolate_migratepages_block() - isolate all migrate-able pages within
801  *				  a single pageblock
802  * @cc:		Compaction control structure.
803  * @low_pfn:	The first PFN to isolate
804  * @end_pfn:	The one-past-the-last PFN to isolate, within same pageblock
805  * @mode:	Isolation mode to be used.
806  *
807  * Isolate all pages that can be migrated from the range specified by
808  * [low_pfn, end_pfn). The range is expected to be within same pageblock.
809  * Returns errno, like -EAGAIN or -EINTR in case e.g signal pending or congestion,
810  * -ENOMEM in case we could not allocate a page, or 0.
811  * cc->migrate_pfn will contain the next pfn to scan.
812  *
813  * The pages are isolated on cc->migratepages list (not required to be empty),
814  * and cc->nr_migratepages is updated accordingly.
815  */
816 static int
817 isolate_migratepages_block(struct compact_control *cc, unsigned long low_pfn,
818 			unsigned long end_pfn, isolate_mode_t mode)
819 {
820 	pg_data_t *pgdat = cc->zone->zone_pgdat;
821 	unsigned long nr_scanned = 0, nr_isolated = 0;
822 	struct lruvec *lruvec;
823 	unsigned long flags = 0;
824 	struct lruvec *locked = NULL;
825 	struct folio *folio = NULL;
826 	struct page *page = NULL, *valid_page = NULL;
827 	struct address_space *mapping;
828 	unsigned long start_pfn = low_pfn;
829 	bool skip_on_failure = false;
830 	unsigned long next_skip_pfn = 0;
831 	bool skip_updated = false;
832 	int ret = 0;
833 
834 	cc->migrate_pfn = low_pfn;
835 
836 	/*
837 	 * Ensure that there are not too many pages isolated from the LRU
838 	 * list by either parallel reclaimers or compaction. If there are,
839 	 * delay for some time until fewer pages are isolated
840 	 */
841 	while (unlikely(too_many_isolated(cc))) {
842 		/* stop isolation if there are still pages not migrated */
843 		if (cc->nr_migratepages)
844 			return -EAGAIN;
845 
846 		/* async migration should just abort */
847 		if (cc->mode == MIGRATE_ASYNC)
848 			return -EAGAIN;
849 
850 		reclaim_throttle(pgdat, VMSCAN_THROTTLE_ISOLATED);
851 
852 		if (fatal_signal_pending(current))
853 			return -EINTR;
854 	}
855 
856 	cond_resched();
857 
858 	if (cc->direct_compaction && (cc->mode == MIGRATE_ASYNC)) {
859 		skip_on_failure = true;
860 		next_skip_pfn = block_end_pfn(low_pfn, cc->order);
861 	}
862 
863 	/* Time to isolate some pages for migration */
864 	for (; low_pfn < end_pfn; low_pfn++) {
865 
866 		if (skip_on_failure && low_pfn >= next_skip_pfn) {
867 			/*
868 			 * We have isolated all migration candidates in the
869 			 * previous order-aligned block, and did not skip it due
870 			 * to failure. We should migrate the pages now and
871 			 * hopefully succeed compaction.
872 			 */
873 			if (nr_isolated)
874 				break;
875 
876 			/*
877 			 * We failed to isolate in the previous order-aligned
878 			 * block. Set the new boundary to the end of the
879 			 * current block. Note we can't simply increase
880 			 * next_skip_pfn by 1 << order, as low_pfn might have
881 			 * been incremented by a higher number due to skipping
882 			 * a compound or a high-order buddy page in the
883 			 * previous loop iteration.
884 			 */
885 			next_skip_pfn = block_end_pfn(low_pfn, cc->order);
886 		}
887 
888 		/*
889 		 * Periodically drop the lock (if held) regardless of its
890 		 * contention, to give chance to IRQs. Abort completely if
891 		 * a fatal signal is pending.
892 		 */
893 		if (!(low_pfn % COMPACT_CLUSTER_MAX)) {
894 			if (locked) {
895 				unlock_page_lruvec_irqrestore(locked, flags);
896 				locked = NULL;
897 			}
898 
899 			if (fatal_signal_pending(current)) {
900 				cc->contended = true;
901 				ret = -EINTR;
902 
903 				goto fatal_pending;
904 			}
905 
906 			cond_resched();
907 		}
908 
909 		nr_scanned++;
910 
911 		page = pfn_to_page(low_pfn);
912 
913 		/*
914 		 * Check if the pageblock has already been marked skipped.
915 		 * Only the first PFN is checked as the caller isolates
916 		 * COMPACT_CLUSTER_MAX at a time so the second call must
917 		 * not falsely conclude that the block should be skipped.
918 		 */
919 		if (!valid_page && (pageblock_aligned(low_pfn) ||
920 				    low_pfn == cc->zone->zone_start_pfn)) {
921 			if (!isolation_suitable(cc, page)) {
922 				low_pfn = end_pfn;
923 				folio = NULL;
924 				goto isolate_abort;
925 			}
926 			valid_page = page;
927 		}
928 
929 		if (PageHuge(page) && cc->alloc_contig) {
930 			if (locked) {
931 				unlock_page_lruvec_irqrestore(locked, flags);
932 				locked = NULL;
933 			}
934 
935 			ret = isolate_or_dissolve_huge_page(page, &cc->migratepages);
936 
937 			/*
938 			 * Fail isolation in case isolate_or_dissolve_huge_page()
939 			 * reports an error. In case of -ENOMEM, abort right away.
940 			 */
941 			if (ret < 0) {
942 				 /* Do not report -EBUSY down the chain */
943 				if (ret == -EBUSY)
944 					ret = 0;
945 				low_pfn += compound_nr(page) - 1;
946 				nr_scanned += compound_nr(page) - 1;
947 				goto isolate_fail;
948 			}
949 
950 			if (PageHuge(page)) {
951 				/*
952 				 * Hugepage was successfully isolated and placed
953 				 * on the cc->migratepages list.
954 				 */
955 				folio = page_folio(page);
956 				low_pfn += folio_nr_pages(folio) - 1;
957 				goto isolate_success_no_list;
958 			}
959 
960 			/*
961 			 * Ok, the hugepage was dissolved. Now these pages are
962 			 * Buddy and cannot be re-allocated because they are
963 			 * isolated. Fall-through as the check below handles
964 			 * Buddy pages.
965 			 */
966 		}
967 
968 		/*
969 		 * Skip if free. We read page order here without zone lock
970 		 * which is generally unsafe, but the race window is small and
971 		 * the worst thing that can happen is that we skip some
972 		 * potential isolation targets.
973 		 */
974 		if (PageBuddy(page)) {
975 			unsigned long freepage_order = buddy_order_unsafe(page);
976 
977 			/*
978 			 * Without lock, we cannot be sure that what we got is
979 			 * a valid page order. Consider only values in the
980 			 * valid order range to prevent low_pfn overflow.
981 			 */
982 			if (freepage_order > 0 && freepage_order <= MAX_ORDER) {
983 				low_pfn += (1UL << freepage_order) - 1;
984 				nr_scanned += (1UL << freepage_order) - 1;
985 			}
986 			continue;
987 		}
988 
989 		/*
990 		 * Regardless of being on LRU, compound pages such as THP and
991 		 * hugetlbfs are not to be compacted unless we are attempting
992 		 * an allocation much larger than the huge page size (eg CMA).
993 		 * We can potentially save a lot of iterations if we skip them
994 		 * at once. The check is racy, but we can consider only valid
995 		 * values and the only danger is skipping too much.
996 		 */
997 		if (PageCompound(page) && !cc->alloc_contig) {
998 			const unsigned int order = compound_order(page);
999 
1000 			if (likely(order <= MAX_ORDER)) {
1001 				low_pfn += (1UL << order) - 1;
1002 				nr_scanned += (1UL << order) - 1;
1003 			}
1004 			goto isolate_fail;
1005 		}
1006 
1007 		/*
1008 		 * Check may be lockless but that's ok as we recheck later.
1009 		 * It's possible to migrate LRU and non-lru movable pages.
1010 		 * Skip any other type of page
1011 		 */
1012 		if (!PageLRU(page)) {
1013 			/*
1014 			 * __PageMovable can return false positive so we need
1015 			 * to verify it under page_lock.
1016 			 */
1017 			if (unlikely(__PageMovable(page)) &&
1018 					!PageIsolated(page)) {
1019 				if (locked) {
1020 					unlock_page_lruvec_irqrestore(locked, flags);
1021 					locked = NULL;
1022 				}
1023 
1024 				if (isolate_movable_page(page, mode)) {
1025 					folio = page_folio(page);
1026 					goto isolate_success;
1027 				}
1028 			}
1029 
1030 			goto isolate_fail;
1031 		}
1032 
1033 		/*
1034 		 * Be careful not to clear PageLRU until after we're
1035 		 * sure the page is not being freed elsewhere -- the
1036 		 * page release code relies on it.
1037 		 */
1038 		folio = folio_get_nontail_page(page);
1039 		if (unlikely(!folio))
1040 			goto isolate_fail;
1041 
1042 		/*
1043 		 * Migration will fail if an anonymous page is pinned in memory,
1044 		 * so avoid taking lru_lock and isolating it unnecessarily in an
1045 		 * admittedly racy check.
1046 		 */
1047 		mapping = folio_mapping(folio);
1048 		if (!mapping && (folio_ref_count(folio) - 1) > folio_mapcount(folio))
1049 			goto isolate_fail_put;
1050 
1051 		/*
1052 		 * Only allow to migrate anonymous pages in GFP_NOFS context
1053 		 * because those do not depend on fs locks.
1054 		 */
1055 		if (!(cc->gfp_mask & __GFP_FS) && mapping)
1056 			goto isolate_fail_put;
1057 
1058 		/* Only take pages on LRU: a check now makes later tests safe */
1059 		if (!folio_test_lru(folio))
1060 			goto isolate_fail_put;
1061 
1062 		/* Compaction might skip unevictable pages but CMA takes them */
1063 		if (!(mode & ISOLATE_UNEVICTABLE) && folio_test_unevictable(folio))
1064 			goto isolate_fail_put;
1065 
1066 		/*
1067 		 * To minimise LRU disruption, the caller can indicate with
1068 		 * ISOLATE_ASYNC_MIGRATE that it only wants to isolate pages
1069 		 * it will be able to migrate without blocking - clean pages
1070 		 * for the most part.  PageWriteback would require blocking.
1071 		 */
1072 		if ((mode & ISOLATE_ASYNC_MIGRATE) && folio_test_writeback(folio))
1073 			goto isolate_fail_put;
1074 
1075 		if ((mode & ISOLATE_ASYNC_MIGRATE) && folio_test_dirty(folio)) {
1076 			bool migrate_dirty;
1077 
1078 			/*
1079 			 * Only pages without mappings or that have a
1080 			 * ->migrate_folio callback are possible to migrate
1081 			 * without blocking. However, we can be racing with
1082 			 * truncation so it's necessary to lock the page
1083 			 * to stabilise the mapping as truncation holds
1084 			 * the page lock until after the page is removed
1085 			 * from the page cache.
1086 			 */
1087 			if (!folio_trylock(folio))
1088 				goto isolate_fail_put;
1089 
1090 			mapping = folio_mapping(folio);
1091 			migrate_dirty = !mapping ||
1092 					mapping->a_ops->migrate_folio;
1093 			folio_unlock(folio);
1094 			if (!migrate_dirty)
1095 				goto isolate_fail_put;
1096 		}
1097 
1098 		/* Try isolate the folio */
1099 		if (!folio_test_clear_lru(folio))
1100 			goto isolate_fail_put;
1101 
1102 		lruvec = folio_lruvec(folio);
1103 
1104 		/* If we already hold the lock, we can skip some rechecking */
1105 		if (lruvec != locked) {
1106 			if (locked)
1107 				unlock_page_lruvec_irqrestore(locked, flags);
1108 
1109 			compact_lock_irqsave(&lruvec->lru_lock, &flags, cc);
1110 			locked = lruvec;
1111 
1112 			lruvec_memcg_debug(lruvec, folio);
1113 
1114 			/*
1115 			 * Try get exclusive access under lock. If marked for
1116 			 * skip, the scan is aborted unless the current context
1117 			 * is a rescan to reach the end of the pageblock.
1118 			 */
1119 			if (!skip_updated && valid_page) {
1120 				skip_updated = true;
1121 				if (test_and_set_skip(cc, valid_page) &&
1122 				    !cc->finish_pageblock) {
1123 					goto isolate_abort;
1124 				}
1125 			}
1126 
1127 			/*
1128 			 * folio become large since the non-locked check,
1129 			 * and it's on LRU.
1130 			 */
1131 			if (unlikely(folio_test_large(folio) && !cc->alloc_contig)) {
1132 				low_pfn += folio_nr_pages(folio) - 1;
1133 				nr_scanned += folio_nr_pages(folio) - 1;
1134 				folio_set_lru(folio);
1135 				goto isolate_fail_put;
1136 			}
1137 		}
1138 
1139 		/* The folio is taken off the LRU */
1140 		if (folio_test_large(folio))
1141 			low_pfn += folio_nr_pages(folio) - 1;
1142 
1143 		/* Successfully isolated */
1144 		lruvec_del_folio(lruvec, folio);
1145 		node_stat_mod_folio(folio,
1146 				NR_ISOLATED_ANON + folio_is_file_lru(folio),
1147 				folio_nr_pages(folio));
1148 
1149 isolate_success:
1150 		list_add(&folio->lru, &cc->migratepages);
1151 isolate_success_no_list:
1152 		cc->nr_migratepages += folio_nr_pages(folio);
1153 		nr_isolated += folio_nr_pages(folio);
1154 		nr_scanned += folio_nr_pages(folio) - 1;
1155 
1156 		/*
1157 		 * Avoid isolating too much unless this block is being
1158 		 * fully scanned (e.g. dirty/writeback pages, parallel allocation)
1159 		 * or a lock is contended. For contention, isolate quickly to
1160 		 * potentially remove one source of contention.
1161 		 */
1162 		if (cc->nr_migratepages >= COMPACT_CLUSTER_MAX &&
1163 		    !cc->finish_pageblock && !cc->contended) {
1164 			++low_pfn;
1165 			break;
1166 		}
1167 
1168 		continue;
1169 
1170 isolate_fail_put:
1171 		/* Avoid potential deadlock in freeing page under lru_lock */
1172 		if (locked) {
1173 			unlock_page_lruvec_irqrestore(locked, flags);
1174 			locked = NULL;
1175 		}
1176 		folio_put(folio);
1177 
1178 isolate_fail:
1179 		if (!skip_on_failure && ret != -ENOMEM)
1180 			continue;
1181 
1182 		/*
1183 		 * We have isolated some pages, but then failed. Release them
1184 		 * instead of migrating, as we cannot form the cc->order buddy
1185 		 * page anyway.
1186 		 */
1187 		if (nr_isolated) {
1188 			if (locked) {
1189 				unlock_page_lruvec_irqrestore(locked, flags);
1190 				locked = NULL;
1191 			}
1192 			putback_movable_pages(&cc->migratepages);
1193 			cc->nr_migratepages = 0;
1194 			nr_isolated = 0;
1195 		}
1196 
1197 		if (low_pfn < next_skip_pfn) {
1198 			low_pfn = next_skip_pfn - 1;
1199 			/*
1200 			 * The check near the loop beginning would have updated
1201 			 * next_skip_pfn too, but this is a bit simpler.
1202 			 */
1203 			next_skip_pfn += 1UL << cc->order;
1204 		}
1205 
1206 		if (ret == -ENOMEM)
1207 			break;
1208 	}
1209 
1210 	/*
1211 	 * The PageBuddy() check could have potentially brought us outside
1212 	 * the range to be scanned.
1213 	 */
1214 	if (unlikely(low_pfn > end_pfn))
1215 		low_pfn = end_pfn;
1216 
1217 	folio = NULL;
1218 
1219 isolate_abort:
1220 	if (locked)
1221 		unlock_page_lruvec_irqrestore(locked, flags);
1222 	if (folio) {
1223 		folio_set_lru(folio);
1224 		folio_put(folio);
1225 	}
1226 
1227 	/*
1228 	 * Update the cached scanner pfn once the pageblock has been scanned.
1229 	 * Pages will either be migrated in which case there is no point
1230 	 * scanning in the near future or migration failed in which case the
1231 	 * failure reason may persist. The block is marked for skipping if
1232 	 * there were no pages isolated in the block or if the block is
1233 	 * rescanned twice in a row.
1234 	 */
1235 	if (low_pfn == end_pfn && (!nr_isolated || cc->finish_pageblock)) {
1236 		if (!cc->no_set_skip_hint && valid_page && !skip_updated)
1237 			set_pageblock_skip(valid_page);
1238 		update_cached_migrate(cc, low_pfn);
1239 	}
1240 
1241 	trace_mm_compaction_isolate_migratepages(start_pfn, low_pfn,
1242 						nr_scanned, nr_isolated);
1243 
1244 fatal_pending:
1245 	cc->total_migrate_scanned += nr_scanned;
1246 	if (nr_isolated)
1247 		count_compact_events(COMPACTISOLATED, nr_isolated);
1248 
1249 	cc->migrate_pfn = low_pfn;
1250 
1251 	return ret;
1252 }
1253 
1254 /**
1255  * isolate_migratepages_range() - isolate migrate-able pages in a PFN range
1256  * @cc:        Compaction control structure.
1257  * @start_pfn: The first PFN to start isolating.
1258  * @end_pfn:   The one-past-last PFN.
1259  *
1260  * Returns -EAGAIN when contented, -EINTR in case of a signal pending, -ENOMEM
1261  * in case we could not allocate a page, or 0.
1262  */
1263 int
1264 isolate_migratepages_range(struct compact_control *cc, unsigned long start_pfn,
1265 							unsigned long end_pfn)
1266 {
1267 	unsigned long pfn, block_start_pfn, block_end_pfn;
1268 	int ret = 0;
1269 
1270 	/* Scan block by block. First and last block may be incomplete */
1271 	pfn = start_pfn;
1272 	block_start_pfn = pageblock_start_pfn(pfn);
1273 	if (block_start_pfn < cc->zone->zone_start_pfn)
1274 		block_start_pfn = cc->zone->zone_start_pfn;
1275 	block_end_pfn = pageblock_end_pfn(pfn);
1276 
1277 	for (; pfn < end_pfn; pfn = block_end_pfn,
1278 				block_start_pfn = block_end_pfn,
1279 				block_end_pfn += pageblock_nr_pages) {
1280 
1281 		block_end_pfn = min(block_end_pfn, end_pfn);
1282 
1283 		if (!pageblock_pfn_to_page(block_start_pfn,
1284 					block_end_pfn, cc->zone))
1285 			continue;
1286 
1287 		ret = isolate_migratepages_block(cc, pfn, block_end_pfn,
1288 						 ISOLATE_UNEVICTABLE);
1289 
1290 		if (ret)
1291 			break;
1292 
1293 		if (cc->nr_migratepages >= COMPACT_CLUSTER_MAX)
1294 			break;
1295 	}
1296 
1297 	return ret;
1298 }
1299 
1300 #endif /* CONFIG_COMPACTION || CONFIG_CMA */
1301 #ifdef CONFIG_COMPACTION
1302 
1303 static bool suitable_migration_source(struct compact_control *cc,
1304 							struct page *page)
1305 {
1306 	int block_mt;
1307 
1308 	if (pageblock_skip_persistent(page))
1309 		return false;
1310 
1311 	if ((cc->mode != MIGRATE_ASYNC) || !cc->direct_compaction)
1312 		return true;
1313 
1314 	block_mt = get_pageblock_migratetype(page);
1315 
1316 	if (cc->migratetype == MIGRATE_MOVABLE)
1317 		return is_migrate_movable(block_mt);
1318 	else
1319 		return block_mt == cc->migratetype;
1320 }
1321 
1322 /* Returns true if the page is within a block suitable for migration to */
1323 static bool suitable_migration_target(struct compact_control *cc,
1324 							struct page *page)
1325 {
1326 	/* If the page is a large free page, then disallow migration */
1327 	if (PageBuddy(page)) {
1328 		/*
1329 		 * We are checking page_order without zone->lock taken. But
1330 		 * the only small danger is that we skip a potentially suitable
1331 		 * pageblock, so it's not worth to check order for valid range.
1332 		 */
1333 		if (buddy_order_unsafe(page) >= pageblock_order)
1334 			return false;
1335 	}
1336 
1337 	if (cc->ignore_block_suitable)
1338 		return true;
1339 
1340 	/* If the block is MIGRATE_MOVABLE or MIGRATE_CMA, allow migration */
1341 	if (is_migrate_movable(get_pageblock_migratetype(page)))
1342 		return true;
1343 
1344 	/* Otherwise skip the block */
1345 	return false;
1346 }
1347 
1348 static inline unsigned int
1349 freelist_scan_limit(struct compact_control *cc)
1350 {
1351 	unsigned short shift = BITS_PER_LONG - 1;
1352 
1353 	return (COMPACT_CLUSTER_MAX >> min(shift, cc->fast_search_fail)) + 1;
1354 }
1355 
1356 /*
1357  * Test whether the free scanner has reached the same or lower pageblock than
1358  * the migration scanner, and compaction should thus terminate.
1359  */
1360 static inline bool compact_scanners_met(struct compact_control *cc)
1361 {
1362 	return (cc->free_pfn >> pageblock_order)
1363 		<= (cc->migrate_pfn >> pageblock_order);
1364 }
1365 
1366 /*
1367  * Used when scanning for a suitable migration target which scans freelists
1368  * in reverse. Reorders the list such as the unscanned pages are scanned
1369  * first on the next iteration of the free scanner
1370  */
1371 static void
1372 move_freelist_head(struct list_head *freelist, struct page *freepage)
1373 {
1374 	LIST_HEAD(sublist);
1375 
1376 	if (!list_is_last(freelist, &freepage->lru)) {
1377 		list_cut_before(&sublist, freelist, &freepage->lru);
1378 		list_splice_tail(&sublist, freelist);
1379 	}
1380 }
1381 
1382 /*
1383  * Similar to move_freelist_head except used by the migration scanner
1384  * when scanning forward. It's possible for these list operations to
1385  * move against each other if they search the free list exactly in
1386  * lockstep.
1387  */
1388 static void
1389 move_freelist_tail(struct list_head *freelist, struct page *freepage)
1390 {
1391 	LIST_HEAD(sublist);
1392 
1393 	if (!list_is_first(freelist, &freepage->lru)) {
1394 		list_cut_position(&sublist, freelist, &freepage->lru);
1395 		list_splice_tail(&sublist, freelist);
1396 	}
1397 }
1398 
1399 static void
1400 fast_isolate_around(struct compact_control *cc, unsigned long pfn)
1401 {
1402 	unsigned long start_pfn, end_pfn;
1403 	struct page *page;
1404 
1405 	/* Do not search around if there are enough pages already */
1406 	if (cc->nr_freepages >= cc->nr_migratepages)
1407 		return;
1408 
1409 	/* Minimise scanning during async compaction */
1410 	if (cc->direct_compaction && cc->mode == MIGRATE_ASYNC)
1411 		return;
1412 
1413 	/* Pageblock boundaries */
1414 	start_pfn = max(pageblock_start_pfn(pfn), cc->zone->zone_start_pfn);
1415 	end_pfn = min(pageblock_end_pfn(pfn), zone_end_pfn(cc->zone));
1416 
1417 	page = pageblock_pfn_to_page(start_pfn, end_pfn, cc->zone);
1418 	if (!page)
1419 		return;
1420 
1421 	isolate_freepages_block(cc, &start_pfn, end_pfn, &cc->freepages, 1, false);
1422 
1423 	/* Skip this pageblock in the future as it's full or nearly full */
1424 	if (start_pfn == end_pfn)
1425 		set_pageblock_skip(page);
1426 
1427 	return;
1428 }
1429 
1430 /* Search orders in round-robin fashion */
1431 static int next_search_order(struct compact_control *cc, int order)
1432 {
1433 	order--;
1434 	if (order < 0)
1435 		order = cc->order - 1;
1436 
1437 	/* Search wrapped around? */
1438 	if (order == cc->search_order) {
1439 		cc->search_order--;
1440 		if (cc->search_order < 0)
1441 			cc->search_order = cc->order - 1;
1442 		return -1;
1443 	}
1444 
1445 	return order;
1446 }
1447 
1448 static void fast_isolate_freepages(struct compact_control *cc)
1449 {
1450 	unsigned int limit = max(1U, freelist_scan_limit(cc) >> 1);
1451 	unsigned int nr_scanned = 0, total_isolated = 0;
1452 	unsigned long low_pfn, min_pfn, highest = 0;
1453 	unsigned long nr_isolated = 0;
1454 	unsigned long distance;
1455 	struct page *page = NULL;
1456 	bool scan_start = false;
1457 	int order;
1458 
1459 	/* Full compaction passes in a negative order */
1460 	if (cc->order <= 0)
1461 		return;
1462 
1463 	/*
1464 	 * If starting the scan, use a deeper search and use the highest
1465 	 * PFN found if a suitable one is not found.
1466 	 */
1467 	if (cc->free_pfn >= cc->zone->compact_init_free_pfn) {
1468 		limit = pageblock_nr_pages >> 1;
1469 		scan_start = true;
1470 	}
1471 
1472 	/*
1473 	 * Preferred point is in the top quarter of the scan space but take
1474 	 * a pfn from the top half if the search is problematic.
1475 	 */
1476 	distance = (cc->free_pfn - cc->migrate_pfn);
1477 	low_pfn = pageblock_start_pfn(cc->free_pfn - (distance >> 2));
1478 	min_pfn = pageblock_start_pfn(cc->free_pfn - (distance >> 1));
1479 
1480 	if (WARN_ON_ONCE(min_pfn > low_pfn))
1481 		low_pfn = min_pfn;
1482 
1483 	/*
1484 	 * Search starts from the last successful isolation order or the next
1485 	 * order to search after a previous failure
1486 	 */
1487 	cc->search_order = min_t(unsigned int, cc->order - 1, cc->search_order);
1488 
1489 	for (order = cc->search_order;
1490 	     !page && order >= 0;
1491 	     order = next_search_order(cc, order)) {
1492 		struct free_area *area = &cc->zone->free_area[order];
1493 		struct list_head *freelist;
1494 		struct page *freepage;
1495 		unsigned long flags;
1496 		unsigned int order_scanned = 0;
1497 		unsigned long high_pfn = 0;
1498 
1499 		if (!area->nr_free)
1500 			continue;
1501 
1502 		spin_lock_irqsave(&cc->zone->lock, flags);
1503 		freelist = &area->free_list[MIGRATE_MOVABLE];
1504 		list_for_each_entry_reverse(freepage, freelist, lru) {
1505 			unsigned long pfn;
1506 
1507 			order_scanned++;
1508 			nr_scanned++;
1509 			pfn = page_to_pfn(freepage);
1510 
1511 			if (pfn >= highest)
1512 				highest = max(pageblock_start_pfn(pfn),
1513 					      cc->zone->zone_start_pfn);
1514 
1515 			if (pfn >= low_pfn) {
1516 				cc->fast_search_fail = 0;
1517 				cc->search_order = order;
1518 				page = freepage;
1519 				break;
1520 			}
1521 
1522 			if (pfn >= min_pfn && pfn > high_pfn) {
1523 				high_pfn = pfn;
1524 
1525 				/* Shorten the scan if a candidate is found */
1526 				limit >>= 1;
1527 			}
1528 
1529 			if (order_scanned >= limit)
1530 				break;
1531 		}
1532 
1533 		/* Use a minimum pfn if a preferred one was not found */
1534 		if (!page && high_pfn) {
1535 			page = pfn_to_page(high_pfn);
1536 
1537 			/* Update freepage for the list reorder below */
1538 			freepage = page;
1539 		}
1540 
1541 		/* Reorder to so a future search skips recent pages */
1542 		move_freelist_head(freelist, freepage);
1543 
1544 		/* Isolate the page if available */
1545 		if (page) {
1546 			if (__isolate_free_page(page, order)) {
1547 				set_page_private(page, order);
1548 				nr_isolated = 1 << order;
1549 				nr_scanned += nr_isolated - 1;
1550 				total_isolated += nr_isolated;
1551 				cc->nr_freepages += nr_isolated;
1552 				list_add_tail(&page->lru, &cc->freepages);
1553 				count_compact_events(COMPACTISOLATED, nr_isolated);
1554 			} else {
1555 				/* If isolation fails, abort the search */
1556 				order = cc->search_order + 1;
1557 				page = NULL;
1558 			}
1559 		}
1560 
1561 		spin_unlock_irqrestore(&cc->zone->lock, flags);
1562 
1563 		/* Skip fast search if enough freepages isolated */
1564 		if (cc->nr_freepages >= cc->nr_migratepages)
1565 			break;
1566 
1567 		/*
1568 		 * Smaller scan on next order so the total scan is related
1569 		 * to freelist_scan_limit.
1570 		 */
1571 		if (order_scanned >= limit)
1572 			limit = max(1U, limit >> 1);
1573 	}
1574 
1575 	trace_mm_compaction_fast_isolate_freepages(min_pfn, cc->free_pfn,
1576 						   nr_scanned, total_isolated);
1577 
1578 	if (!page) {
1579 		cc->fast_search_fail++;
1580 		if (scan_start) {
1581 			/*
1582 			 * Use the highest PFN found above min. If one was
1583 			 * not found, be pessimistic for direct compaction
1584 			 * and use the min mark.
1585 			 */
1586 			if (highest >= min_pfn) {
1587 				page = pfn_to_page(highest);
1588 				cc->free_pfn = highest;
1589 			} else {
1590 				if (cc->direct_compaction && pfn_valid(min_pfn)) {
1591 					page = pageblock_pfn_to_page(min_pfn,
1592 						min(pageblock_end_pfn(min_pfn),
1593 						    zone_end_pfn(cc->zone)),
1594 						cc->zone);
1595 					cc->free_pfn = min_pfn;
1596 				}
1597 			}
1598 		}
1599 	}
1600 
1601 	if (highest && highest >= cc->zone->compact_cached_free_pfn) {
1602 		highest -= pageblock_nr_pages;
1603 		cc->zone->compact_cached_free_pfn = highest;
1604 	}
1605 
1606 	cc->total_free_scanned += nr_scanned;
1607 	if (!page)
1608 		return;
1609 
1610 	low_pfn = page_to_pfn(page);
1611 	fast_isolate_around(cc, low_pfn);
1612 }
1613 
1614 /*
1615  * Based on information in the current compact_control, find blocks
1616  * suitable for isolating free pages from and then isolate them.
1617  */
1618 static void isolate_freepages(struct compact_control *cc)
1619 {
1620 	struct zone *zone = cc->zone;
1621 	struct page *page;
1622 	unsigned long block_start_pfn;	/* start of current pageblock */
1623 	unsigned long isolate_start_pfn; /* exact pfn we start at */
1624 	unsigned long block_end_pfn;	/* end of current pageblock */
1625 	unsigned long low_pfn;	     /* lowest pfn scanner is able to scan */
1626 	struct list_head *freelist = &cc->freepages;
1627 	unsigned int stride;
1628 
1629 	/* Try a small search of the free lists for a candidate */
1630 	fast_isolate_freepages(cc);
1631 	if (cc->nr_freepages)
1632 		goto splitmap;
1633 
1634 	/*
1635 	 * Initialise the free scanner. The starting point is where we last
1636 	 * successfully isolated from, zone-cached value, or the end of the
1637 	 * zone when isolating for the first time. For looping we also need
1638 	 * this pfn aligned down to the pageblock boundary, because we do
1639 	 * block_start_pfn -= pageblock_nr_pages in the for loop.
1640 	 * For ending point, take care when isolating in last pageblock of a
1641 	 * zone which ends in the middle of a pageblock.
1642 	 * The low boundary is the end of the pageblock the migration scanner
1643 	 * is using.
1644 	 */
1645 	isolate_start_pfn = cc->free_pfn;
1646 	block_start_pfn = pageblock_start_pfn(isolate_start_pfn);
1647 	block_end_pfn = min(block_start_pfn + pageblock_nr_pages,
1648 						zone_end_pfn(zone));
1649 	low_pfn = pageblock_end_pfn(cc->migrate_pfn);
1650 	stride = cc->mode == MIGRATE_ASYNC ? COMPACT_CLUSTER_MAX : 1;
1651 
1652 	/*
1653 	 * Isolate free pages until enough are available to migrate the
1654 	 * pages on cc->migratepages. We stop searching if the migrate
1655 	 * and free page scanners meet or enough free pages are isolated.
1656 	 */
1657 	for (; block_start_pfn >= low_pfn;
1658 				block_end_pfn = block_start_pfn,
1659 				block_start_pfn -= pageblock_nr_pages,
1660 				isolate_start_pfn = block_start_pfn) {
1661 		unsigned long nr_isolated;
1662 
1663 		/*
1664 		 * This can iterate a massively long zone without finding any
1665 		 * suitable migration targets, so periodically check resched.
1666 		 */
1667 		if (!(block_start_pfn % (COMPACT_CLUSTER_MAX * pageblock_nr_pages)))
1668 			cond_resched();
1669 
1670 		page = pageblock_pfn_to_page(block_start_pfn, block_end_pfn,
1671 									zone);
1672 		if (!page)
1673 			continue;
1674 
1675 		/* Check the block is suitable for migration */
1676 		if (!suitable_migration_target(cc, page))
1677 			continue;
1678 
1679 		/* If isolation recently failed, do not retry */
1680 		if (!isolation_suitable(cc, page))
1681 			continue;
1682 
1683 		/* Found a block suitable for isolating free pages from. */
1684 		nr_isolated = isolate_freepages_block(cc, &isolate_start_pfn,
1685 					block_end_pfn, freelist, stride, false);
1686 
1687 		/* Update the skip hint if the full pageblock was scanned */
1688 		if (isolate_start_pfn == block_end_pfn)
1689 			update_pageblock_skip(cc, page, block_start_pfn);
1690 
1691 		/* Are enough freepages isolated? */
1692 		if (cc->nr_freepages >= cc->nr_migratepages) {
1693 			if (isolate_start_pfn >= block_end_pfn) {
1694 				/*
1695 				 * Restart at previous pageblock if more
1696 				 * freepages can be isolated next time.
1697 				 */
1698 				isolate_start_pfn =
1699 					block_start_pfn - pageblock_nr_pages;
1700 			}
1701 			break;
1702 		} else if (isolate_start_pfn < block_end_pfn) {
1703 			/*
1704 			 * If isolation failed early, do not continue
1705 			 * needlessly.
1706 			 */
1707 			break;
1708 		}
1709 
1710 		/* Adjust stride depending on isolation */
1711 		if (nr_isolated) {
1712 			stride = 1;
1713 			continue;
1714 		}
1715 		stride = min_t(unsigned int, COMPACT_CLUSTER_MAX, stride << 1);
1716 	}
1717 
1718 	/*
1719 	 * Record where the free scanner will restart next time. Either we
1720 	 * broke from the loop and set isolate_start_pfn based on the last
1721 	 * call to isolate_freepages_block(), or we met the migration scanner
1722 	 * and the loop terminated due to isolate_start_pfn < low_pfn
1723 	 */
1724 	cc->free_pfn = isolate_start_pfn;
1725 
1726 splitmap:
1727 	/* __isolate_free_page() does not map the pages */
1728 	split_map_pages(freelist);
1729 }
1730 
1731 /*
1732  * This is a migrate-callback that "allocates" freepages by taking pages
1733  * from the isolated freelists in the block we are migrating to.
1734  */
1735 static struct folio *compaction_alloc(struct folio *src, unsigned long data)
1736 {
1737 	struct compact_control *cc = (struct compact_control *)data;
1738 	struct folio *dst;
1739 
1740 	if (list_empty(&cc->freepages)) {
1741 		isolate_freepages(cc);
1742 
1743 		if (list_empty(&cc->freepages))
1744 			return NULL;
1745 	}
1746 
1747 	dst = list_entry(cc->freepages.next, struct folio, lru);
1748 	list_del(&dst->lru);
1749 	cc->nr_freepages--;
1750 
1751 	return dst;
1752 }
1753 
1754 /*
1755  * This is a migrate-callback that "frees" freepages back to the isolated
1756  * freelist.  All pages on the freelist are from the same zone, so there is no
1757  * special handling needed for NUMA.
1758  */
1759 static void compaction_free(struct folio *dst, unsigned long data)
1760 {
1761 	struct compact_control *cc = (struct compact_control *)data;
1762 
1763 	list_add(&dst->lru, &cc->freepages);
1764 	cc->nr_freepages++;
1765 }
1766 
1767 /* possible outcome of isolate_migratepages */
1768 typedef enum {
1769 	ISOLATE_ABORT,		/* Abort compaction now */
1770 	ISOLATE_NONE,		/* No pages isolated, continue scanning */
1771 	ISOLATE_SUCCESS,	/* Pages isolated, migrate */
1772 } isolate_migrate_t;
1773 
1774 /*
1775  * Allow userspace to control policy on scanning the unevictable LRU for
1776  * compactable pages.
1777  */
1778 static int sysctl_compact_unevictable_allowed __read_mostly = CONFIG_COMPACT_UNEVICTABLE_DEFAULT;
1779 /*
1780  * Tunable for proactive compaction. It determines how
1781  * aggressively the kernel should compact memory in the
1782  * background. It takes values in the range [0, 100].
1783  */
1784 static unsigned int __read_mostly sysctl_compaction_proactiveness = 20;
1785 static int sysctl_extfrag_threshold = 500;
1786 static int __read_mostly sysctl_compact_memory;
1787 
1788 static inline void
1789 update_fast_start_pfn(struct compact_control *cc, unsigned long pfn)
1790 {
1791 	if (cc->fast_start_pfn == ULONG_MAX)
1792 		return;
1793 
1794 	if (!cc->fast_start_pfn)
1795 		cc->fast_start_pfn = pfn;
1796 
1797 	cc->fast_start_pfn = min(cc->fast_start_pfn, pfn);
1798 }
1799 
1800 static inline unsigned long
1801 reinit_migrate_pfn(struct compact_control *cc)
1802 {
1803 	if (!cc->fast_start_pfn || cc->fast_start_pfn == ULONG_MAX)
1804 		return cc->migrate_pfn;
1805 
1806 	cc->migrate_pfn = cc->fast_start_pfn;
1807 	cc->fast_start_pfn = ULONG_MAX;
1808 
1809 	return cc->migrate_pfn;
1810 }
1811 
1812 /*
1813  * Briefly search the free lists for a migration source that already has
1814  * some free pages to reduce the number of pages that need migration
1815  * before a pageblock is free.
1816  */
1817 static unsigned long fast_find_migrateblock(struct compact_control *cc)
1818 {
1819 	unsigned int limit = freelist_scan_limit(cc);
1820 	unsigned int nr_scanned = 0;
1821 	unsigned long distance;
1822 	unsigned long pfn = cc->migrate_pfn;
1823 	unsigned long high_pfn;
1824 	int order;
1825 	bool found_block = false;
1826 
1827 	/* Skip hints are relied on to avoid repeats on the fast search */
1828 	if (cc->ignore_skip_hint)
1829 		return pfn;
1830 
1831 	/*
1832 	 * If the pageblock should be finished then do not select a different
1833 	 * pageblock.
1834 	 */
1835 	if (cc->finish_pageblock)
1836 		return pfn;
1837 
1838 	/*
1839 	 * If the migrate_pfn is not at the start of a zone or the start
1840 	 * of a pageblock then assume this is a continuation of a previous
1841 	 * scan restarted due to COMPACT_CLUSTER_MAX.
1842 	 */
1843 	if (pfn != cc->zone->zone_start_pfn && pfn != pageblock_start_pfn(pfn))
1844 		return pfn;
1845 
1846 	/*
1847 	 * For smaller orders, just linearly scan as the number of pages
1848 	 * to migrate should be relatively small and does not necessarily
1849 	 * justify freeing up a large block for a small allocation.
1850 	 */
1851 	if (cc->order <= PAGE_ALLOC_COSTLY_ORDER)
1852 		return pfn;
1853 
1854 	/*
1855 	 * Only allow kcompactd and direct requests for movable pages to
1856 	 * quickly clear out a MOVABLE pageblock for allocation. This
1857 	 * reduces the risk that a large movable pageblock is freed for
1858 	 * an unmovable/reclaimable small allocation.
1859 	 */
1860 	if (cc->direct_compaction && cc->migratetype != MIGRATE_MOVABLE)
1861 		return pfn;
1862 
1863 	/*
1864 	 * When starting the migration scanner, pick any pageblock within the
1865 	 * first half of the search space. Otherwise try and pick a pageblock
1866 	 * within the first eighth to reduce the chances that a migration
1867 	 * target later becomes a source.
1868 	 */
1869 	distance = (cc->free_pfn - cc->migrate_pfn) >> 1;
1870 	if (cc->migrate_pfn != cc->zone->zone_start_pfn)
1871 		distance >>= 2;
1872 	high_pfn = pageblock_start_pfn(cc->migrate_pfn + distance);
1873 
1874 	for (order = cc->order - 1;
1875 	     order >= PAGE_ALLOC_COSTLY_ORDER && !found_block && nr_scanned < limit;
1876 	     order--) {
1877 		struct free_area *area = &cc->zone->free_area[order];
1878 		struct list_head *freelist;
1879 		unsigned long flags;
1880 		struct page *freepage;
1881 
1882 		if (!area->nr_free)
1883 			continue;
1884 
1885 		spin_lock_irqsave(&cc->zone->lock, flags);
1886 		freelist = &area->free_list[MIGRATE_MOVABLE];
1887 		list_for_each_entry(freepage, freelist, lru) {
1888 			unsigned long free_pfn;
1889 
1890 			if (nr_scanned++ >= limit) {
1891 				move_freelist_tail(freelist, freepage);
1892 				break;
1893 			}
1894 
1895 			free_pfn = page_to_pfn(freepage);
1896 			if (free_pfn < high_pfn) {
1897 				/*
1898 				 * Avoid if skipped recently. Ideally it would
1899 				 * move to the tail but even safe iteration of
1900 				 * the list assumes an entry is deleted, not
1901 				 * reordered.
1902 				 */
1903 				if (get_pageblock_skip(freepage))
1904 					continue;
1905 
1906 				/* Reorder to so a future search skips recent pages */
1907 				move_freelist_tail(freelist, freepage);
1908 
1909 				update_fast_start_pfn(cc, free_pfn);
1910 				pfn = pageblock_start_pfn(free_pfn);
1911 				if (pfn < cc->zone->zone_start_pfn)
1912 					pfn = cc->zone->zone_start_pfn;
1913 				cc->fast_search_fail = 0;
1914 				found_block = true;
1915 				break;
1916 			}
1917 		}
1918 		spin_unlock_irqrestore(&cc->zone->lock, flags);
1919 	}
1920 
1921 	cc->total_migrate_scanned += nr_scanned;
1922 
1923 	/*
1924 	 * If fast scanning failed then use a cached entry for a page block
1925 	 * that had free pages as the basis for starting a linear scan.
1926 	 */
1927 	if (!found_block) {
1928 		cc->fast_search_fail++;
1929 		pfn = reinit_migrate_pfn(cc);
1930 	}
1931 	return pfn;
1932 }
1933 
1934 /*
1935  * Isolate all pages that can be migrated from the first suitable block,
1936  * starting at the block pointed to by the migrate scanner pfn within
1937  * compact_control.
1938  */
1939 static isolate_migrate_t isolate_migratepages(struct compact_control *cc)
1940 {
1941 	unsigned long block_start_pfn;
1942 	unsigned long block_end_pfn;
1943 	unsigned long low_pfn;
1944 	struct page *page;
1945 	const isolate_mode_t isolate_mode =
1946 		(sysctl_compact_unevictable_allowed ? ISOLATE_UNEVICTABLE : 0) |
1947 		(cc->mode != MIGRATE_SYNC ? ISOLATE_ASYNC_MIGRATE : 0);
1948 	bool fast_find_block;
1949 
1950 	/*
1951 	 * Start at where we last stopped, or beginning of the zone as
1952 	 * initialized by compact_zone(). The first failure will use
1953 	 * the lowest PFN as the starting point for linear scanning.
1954 	 */
1955 	low_pfn = fast_find_migrateblock(cc);
1956 	block_start_pfn = pageblock_start_pfn(low_pfn);
1957 	if (block_start_pfn < cc->zone->zone_start_pfn)
1958 		block_start_pfn = cc->zone->zone_start_pfn;
1959 
1960 	/*
1961 	 * fast_find_migrateblock marks a pageblock skipped so to avoid
1962 	 * the isolation_suitable check below, check whether the fast
1963 	 * search was successful.
1964 	 */
1965 	fast_find_block = low_pfn != cc->migrate_pfn && !cc->fast_search_fail;
1966 
1967 	/* Only scan within a pageblock boundary */
1968 	block_end_pfn = pageblock_end_pfn(low_pfn);
1969 
1970 	/*
1971 	 * Iterate over whole pageblocks until we find the first suitable.
1972 	 * Do not cross the free scanner.
1973 	 */
1974 	for (; block_end_pfn <= cc->free_pfn;
1975 			fast_find_block = false,
1976 			cc->migrate_pfn = low_pfn = block_end_pfn,
1977 			block_start_pfn = block_end_pfn,
1978 			block_end_pfn += pageblock_nr_pages) {
1979 
1980 		/*
1981 		 * This can potentially iterate a massively long zone with
1982 		 * many pageblocks unsuitable, so periodically check if we
1983 		 * need to schedule.
1984 		 */
1985 		if (!(low_pfn % (COMPACT_CLUSTER_MAX * pageblock_nr_pages)))
1986 			cond_resched();
1987 
1988 		page = pageblock_pfn_to_page(block_start_pfn,
1989 						block_end_pfn, cc->zone);
1990 		if (!page) {
1991 			unsigned long next_pfn;
1992 
1993 			next_pfn = skip_offline_sections(block_start_pfn);
1994 			if (next_pfn)
1995 				block_end_pfn = min(next_pfn, cc->free_pfn);
1996 			continue;
1997 		}
1998 
1999 		/*
2000 		 * If isolation recently failed, do not retry. Only check the
2001 		 * pageblock once. COMPACT_CLUSTER_MAX causes a pageblock
2002 		 * to be visited multiple times. Assume skip was checked
2003 		 * before making it "skip" so other compaction instances do
2004 		 * not scan the same block.
2005 		 */
2006 		if ((pageblock_aligned(low_pfn) ||
2007 		     low_pfn == cc->zone->zone_start_pfn) &&
2008 		    !fast_find_block && !isolation_suitable(cc, page))
2009 			continue;
2010 
2011 		/*
2012 		 * For async direct compaction, only scan the pageblocks of the
2013 		 * same migratetype without huge pages. Async direct compaction
2014 		 * is optimistic to see if the minimum amount of work satisfies
2015 		 * the allocation. The cached PFN is updated as it's possible
2016 		 * that all remaining blocks between source and target are
2017 		 * unsuitable and the compaction scanners fail to meet.
2018 		 */
2019 		if (!suitable_migration_source(cc, page)) {
2020 			update_cached_migrate(cc, block_end_pfn);
2021 			continue;
2022 		}
2023 
2024 		/* Perform the isolation */
2025 		if (isolate_migratepages_block(cc, low_pfn, block_end_pfn,
2026 						isolate_mode))
2027 			return ISOLATE_ABORT;
2028 
2029 		/*
2030 		 * Either we isolated something and proceed with migration. Or
2031 		 * we failed and compact_zone should decide if we should
2032 		 * continue or not.
2033 		 */
2034 		break;
2035 	}
2036 
2037 	return cc->nr_migratepages ? ISOLATE_SUCCESS : ISOLATE_NONE;
2038 }
2039 
2040 /*
2041  * order == -1 is expected when compacting via
2042  * /proc/sys/vm/compact_memory
2043  */
2044 static inline bool is_via_compact_memory(int order)
2045 {
2046 	return order == -1;
2047 }
2048 
2049 /*
2050  * Determine whether kswapd is (or recently was!) running on this node.
2051  *
2052  * pgdat_kswapd_lock() pins pgdat->kswapd, so a concurrent kswapd_stop() can't
2053  * zero it.
2054  */
2055 static bool kswapd_is_running(pg_data_t *pgdat)
2056 {
2057 	bool running;
2058 
2059 	pgdat_kswapd_lock(pgdat);
2060 	running = pgdat->kswapd && task_is_running(pgdat->kswapd);
2061 	pgdat_kswapd_unlock(pgdat);
2062 
2063 	return running;
2064 }
2065 
2066 /*
2067  * A zone's fragmentation score is the external fragmentation wrt to the
2068  * COMPACTION_HPAGE_ORDER. It returns a value in the range [0, 100].
2069  */
2070 static unsigned int fragmentation_score_zone(struct zone *zone)
2071 {
2072 	return extfrag_for_order(zone, COMPACTION_HPAGE_ORDER);
2073 }
2074 
2075 /*
2076  * A weighted zone's fragmentation score is the external fragmentation
2077  * wrt to the COMPACTION_HPAGE_ORDER scaled by the zone's size. It
2078  * returns a value in the range [0, 100].
2079  *
2080  * The scaling factor ensures that proactive compaction focuses on larger
2081  * zones like ZONE_NORMAL, rather than smaller, specialized zones like
2082  * ZONE_DMA32. For smaller zones, the score value remains close to zero,
2083  * and thus never exceeds the high threshold for proactive compaction.
2084  */
2085 static unsigned int fragmentation_score_zone_weighted(struct zone *zone)
2086 {
2087 	unsigned long score;
2088 
2089 	score = zone->present_pages * fragmentation_score_zone(zone);
2090 	return div64_ul(score, zone->zone_pgdat->node_present_pages + 1);
2091 }
2092 
2093 /*
2094  * The per-node proactive (background) compaction process is started by its
2095  * corresponding kcompactd thread when the node's fragmentation score
2096  * exceeds the high threshold. The compaction process remains active till
2097  * the node's score falls below the low threshold, or one of the back-off
2098  * conditions is met.
2099  */
2100 static unsigned int fragmentation_score_node(pg_data_t *pgdat)
2101 {
2102 	unsigned int score = 0;
2103 	int zoneid;
2104 
2105 	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
2106 		struct zone *zone;
2107 
2108 		zone = &pgdat->node_zones[zoneid];
2109 		if (!populated_zone(zone))
2110 			continue;
2111 		score += fragmentation_score_zone_weighted(zone);
2112 	}
2113 
2114 	return score;
2115 }
2116 
2117 static unsigned int fragmentation_score_wmark(pg_data_t *pgdat, bool low)
2118 {
2119 	unsigned int wmark_low;
2120 
2121 	/*
2122 	 * Cap the low watermark to avoid excessive compaction
2123 	 * activity in case a user sets the proactiveness tunable
2124 	 * close to 100 (maximum).
2125 	 */
2126 	wmark_low = max(100U - sysctl_compaction_proactiveness, 5U);
2127 	return low ? wmark_low : min(wmark_low + 10, 100U);
2128 }
2129 
2130 static bool should_proactive_compact_node(pg_data_t *pgdat)
2131 {
2132 	int wmark_high;
2133 
2134 	if (!sysctl_compaction_proactiveness || kswapd_is_running(pgdat))
2135 		return false;
2136 
2137 	wmark_high = fragmentation_score_wmark(pgdat, false);
2138 	return fragmentation_score_node(pgdat) > wmark_high;
2139 }
2140 
2141 static enum compact_result __compact_finished(struct compact_control *cc)
2142 {
2143 	unsigned int order;
2144 	const int migratetype = cc->migratetype;
2145 	int ret;
2146 
2147 	/* Compaction run completes if the migrate and free scanner meet */
2148 	if (compact_scanners_met(cc)) {
2149 		/* Let the next compaction start anew. */
2150 		reset_cached_positions(cc->zone);
2151 
2152 		/*
2153 		 * Mark that the PG_migrate_skip information should be cleared
2154 		 * by kswapd when it goes to sleep. kcompactd does not set the
2155 		 * flag itself as the decision to be clear should be directly
2156 		 * based on an allocation request.
2157 		 */
2158 		if (cc->direct_compaction)
2159 			cc->zone->compact_blockskip_flush = true;
2160 
2161 		if (cc->whole_zone)
2162 			return COMPACT_COMPLETE;
2163 		else
2164 			return COMPACT_PARTIAL_SKIPPED;
2165 	}
2166 
2167 	if (cc->proactive_compaction) {
2168 		int score, wmark_low;
2169 		pg_data_t *pgdat;
2170 
2171 		pgdat = cc->zone->zone_pgdat;
2172 		if (kswapd_is_running(pgdat))
2173 			return COMPACT_PARTIAL_SKIPPED;
2174 
2175 		score = fragmentation_score_zone(cc->zone);
2176 		wmark_low = fragmentation_score_wmark(pgdat, true);
2177 
2178 		if (score > wmark_low)
2179 			ret = COMPACT_CONTINUE;
2180 		else
2181 			ret = COMPACT_SUCCESS;
2182 
2183 		goto out;
2184 	}
2185 
2186 	if (is_via_compact_memory(cc->order))
2187 		return COMPACT_CONTINUE;
2188 
2189 	/*
2190 	 * Always finish scanning a pageblock to reduce the possibility of
2191 	 * fallbacks in the future. This is particularly important when
2192 	 * migration source is unmovable/reclaimable but it's not worth
2193 	 * special casing.
2194 	 */
2195 	if (!pageblock_aligned(cc->migrate_pfn))
2196 		return COMPACT_CONTINUE;
2197 
2198 	/* Direct compactor: Is a suitable page free? */
2199 	ret = COMPACT_NO_SUITABLE_PAGE;
2200 	for (order = cc->order; order <= MAX_ORDER; order++) {
2201 		struct free_area *area = &cc->zone->free_area[order];
2202 		bool can_steal;
2203 
2204 		/* Job done if page is free of the right migratetype */
2205 		if (!free_area_empty(area, migratetype))
2206 			return COMPACT_SUCCESS;
2207 
2208 #ifdef CONFIG_CMA
2209 		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
2210 		if (migratetype == MIGRATE_MOVABLE &&
2211 			!free_area_empty(area, MIGRATE_CMA))
2212 			return COMPACT_SUCCESS;
2213 #endif
2214 		/*
2215 		 * Job done if allocation would steal freepages from
2216 		 * other migratetype buddy lists.
2217 		 */
2218 		if (find_suitable_fallback(area, order, migratetype,
2219 						true, &can_steal) != -1)
2220 			/*
2221 			 * Movable pages are OK in any pageblock. If we are
2222 			 * stealing for a non-movable allocation, make sure
2223 			 * we finish compacting the current pageblock first
2224 			 * (which is assured by the above migrate_pfn align
2225 			 * check) so it is as free as possible and we won't
2226 			 * have to steal another one soon.
2227 			 */
2228 			return COMPACT_SUCCESS;
2229 	}
2230 
2231 out:
2232 	if (cc->contended || fatal_signal_pending(current))
2233 		ret = COMPACT_CONTENDED;
2234 
2235 	return ret;
2236 }
2237 
2238 static enum compact_result compact_finished(struct compact_control *cc)
2239 {
2240 	int ret;
2241 
2242 	ret = __compact_finished(cc);
2243 	trace_mm_compaction_finished(cc->zone, cc->order, ret);
2244 	if (ret == COMPACT_NO_SUITABLE_PAGE)
2245 		ret = COMPACT_CONTINUE;
2246 
2247 	return ret;
2248 }
2249 
2250 static bool __compaction_suitable(struct zone *zone, int order,
2251 				  int highest_zoneidx,
2252 				  unsigned long wmark_target)
2253 {
2254 	unsigned long watermark;
2255 	/*
2256 	 * Watermarks for order-0 must be met for compaction to be able to
2257 	 * isolate free pages for migration targets. This means that the
2258 	 * watermark and alloc_flags have to match, or be more pessimistic than
2259 	 * the check in __isolate_free_page(). We don't use the direct
2260 	 * compactor's alloc_flags, as they are not relevant for freepage
2261 	 * isolation. We however do use the direct compactor's highest_zoneidx
2262 	 * to skip over zones where lowmem reserves would prevent allocation
2263 	 * even if compaction succeeds.
2264 	 * For costly orders, we require low watermark instead of min for
2265 	 * compaction to proceed to increase its chances.
2266 	 * ALLOC_CMA is used, as pages in CMA pageblocks are considered
2267 	 * suitable migration targets
2268 	 */
2269 	watermark = (order > PAGE_ALLOC_COSTLY_ORDER) ?
2270 				low_wmark_pages(zone) : min_wmark_pages(zone);
2271 	watermark += compact_gap(order);
2272 	return __zone_watermark_ok(zone, 0, watermark, highest_zoneidx,
2273 				   ALLOC_CMA, wmark_target);
2274 }
2275 
2276 /*
2277  * compaction_suitable: Is this suitable to run compaction on this zone now?
2278  */
2279 bool compaction_suitable(struct zone *zone, int order, int highest_zoneidx)
2280 {
2281 	enum compact_result compact_result;
2282 	bool suitable;
2283 
2284 	suitable = __compaction_suitable(zone, order, highest_zoneidx,
2285 					 zone_page_state(zone, NR_FREE_PAGES));
2286 	/*
2287 	 * fragmentation index determines if allocation failures are due to
2288 	 * low memory or external fragmentation
2289 	 *
2290 	 * index of -1000 would imply allocations might succeed depending on
2291 	 * watermarks, but we already failed the high-order watermark check
2292 	 * index towards 0 implies failure is due to lack of memory
2293 	 * index towards 1000 implies failure is due to fragmentation
2294 	 *
2295 	 * Only compact if a failure would be due to fragmentation. Also
2296 	 * ignore fragindex for non-costly orders where the alternative to
2297 	 * a successful reclaim/compaction is OOM. Fragindex and the
2298 	 * vm.extfrag_threshold sysctl is meant as a heuristic to prevent
2299 	 * excessive compaction for costly orders, but it should not be at the
2300 	 * expense of system stability.
2301 	 */
2302 	if (suitable) {
2303 		compact_result = COMPACT_CONTINUE;
2304 		if (order > PAGE_ALLOC_COSTLY_ORDER) {
2305 			int fragindex = fragmentation_index(zone, order);
2306 
2307 			if (fragindex >= 0 &&
2308 			    fragindex <= sysctl_extfrag_threshold) {
2309 				suitable = false;
2310 				compact_result = COMPACT_NOT_SUITABLE_ZONE;
2311 			}
2312 		}
2313 	} else {
2314 		compact_result = COMPACT_SKIPPED;
2315 	}
2316 
2317 	trace_mm_compaction_suitable(zone, order, compact_result);
2318 
2319 	return suitable;
2320 }
2321 
2322 bool compaction_zonelist_suitable(struct alloc_context *ac, int order,
2323 		int alloc_flags)
2324 {
2325 	struct zone *zone;
2326 	struct zoneref *z;
2327 
2328 	/*
2329 	 * Make sure at least one zone would pass __compaction_suitable if we continue
2330 	 * retrying the reclaim.
2331 	 */
2332 	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
2333 				ac->highest_zoneidx, ac->nodemask) {
2334 		unsigned long available;
2335 
2336 		/*
2337 		 * Do not consider all the reclaimable memory because we do not
2338 		 * want to trash just for a single high order allocation which
2339 		 * is even not guaranteed to appear even if __compaction_suitable
2340 		 * is happy about the watermark check.
2341 		 */
2342 		available = zone_reclaimable_pages(zone) / order;
2343 		available += zone_page_state_snapshot(zone, NR_FREE_PAGES);
2344 		if (__compaction_suitable(zone, order, ac->highest_zoneidx,
2345 					  available))
2346 			return true;
2347 	}
2348 
2349 	return false;
2350 }
2351 
2352 static enum compact_result
2353 compact_zone(struct compact_control *cc, struct capture_control *capc)
2354 {
2355 	enum compact_result ret;
2356 	unsigned long start_pfn = cc->zone->zone_start_pfn;
2357 	unsigned long end_pfn = zone_end_pfn(cc->zone);
2358 	unsigned long last_migrated_pfn;
2359 	const bool sync = cc->mode != MIGRATE_ASYNC;
2360 	bool update_cached;
2361 	unsigned int nr_succeeded = 0;
2362 
2363 	/*
2364 	 * These counters track activities during zone compaction.  Initialize
2365 	 * them before compacting a new zone.
2366 	 */
2367 	cc->total_migrate_scanned = 0;
2368 	cc->total_free_scanned = 0;
2369 	cc->nr_migratepages = 0;
2370 	cc->nr_freepages = 0;
2371 	INIT_LIST_HEAD(&cc->freepages);
2372 	INIT_LIST_HEAD(&cc->migratepages);
2373 
2374 	cc->migratetype = gfp_migratetype(cc->gfp_mask);
2375 
2376 	if (!is_via_compact_memory(cc->order)) {
2377 		unsigned long watermark;
2378 
2379 		/* Allocation can already succeed, nothing to do */
2380 		watermark = wmark_pages(cc->zone,
2381 					cc->alloc_flags & ALLOC_WMARK_MASK);
2382 		if (zone_watermark_ok(cc->zone, cc->order, watermark,
2383 				      cc->highest_zoneidx, cc->alloc_flags))
2384 			return COMPACT_SUCCESS;
2385 
2386 		/* Compaction is likely to fail */
2387 		if (!compaction_suitable(cc->zone, cc->order,
2388 					 cc->highest_zoneidx))
2389 			return COMPACT_SKIPPED;
2390 	}
2391 
2392 	/*
2393 	 * Clear pageblock skip if there were failures recently and compaction
2394 	 * is about to be retried after being deferred.
2395 	 */
2396 	if (compaction_restarting(cc->zone, cc->order))
2397 		__reset_isolation_suitable(cc->zone);
2398 
2399 	/*
2400 	 * Setup to move all movable pages to the end of the zone. Used cached
2401 	 * information on where the scanners should start (unless we explicitly
2402 	 * want to compact the whole zone), but check that it is initialised
2403 	 * by ensuring the values are within zone boundaries.
2404 	 */
2405 	cc->fast_start_pfn = 0;
2406 	if (cc->whole_zone) {
2407 		cc->migrate_pfn = start_pfn;
2408 		cc->free_pfn = pageblock_start_pfn(end_pfn - 1);
2409 	} else {
2410 		cc->migrate_pfn = cc->zone->compact_cached_migrate_pfn[sync];
2411 		cc->free_pfn = cc->zone->compact_cached_free_pfn;
2412 		if (cc->free_pfn < start_pfn || cc->free_pfn >= end_pfn) {
2413 			cc->free_pfn = pageblock_start_pfn(end_pfn - 1);
2414 			cc->zone->compact_cached_free_pfn = cc->free_pfn;
2415 		}
2416 		if (cc->migrate_pfn < start_pfn || cc->migrate_pfn >= end_pfn) {
2417 			cc->migrate_pfn = start_pfn;
2418 			cc->zone->compact_cached_migrate_pfn[0] = cc->migrate_pfn;
2419 			cc->zone->compact_cached_migrate_pfn[1] = cc->migrate_pfn;
2420 		}
2421 
2422 		if (cc->migrate_pfn <= cc->zone->compact_init_migrate_pfn)
2423 			cc->whole_zone = true;
2424 	}
2425 
2426 	last_migrated_pfn = 0;
2427 
2428 	/*
2429 	 * Migrate has separate cached PFNs for ASYNC and SYNC* migration on
2430 	 * the basis that some migrations will fail in ASYNC mode. However,
2431 	 * if the cached PFNs match and pageblocks are skipped due to having
2432 	 * no isolation candidates, then the sync state does not matter.
2433 	 * Until a pageblock with isolation candidates is found, keep the
2434 	 * cached PFNs in sync to avoid revisiting the same blocks.
2435 	 */
2436 	update_cached = !sync &&
2437 		cc->zone->compact_cached_migrate_pfn[0] == cc->zone->compact_cached_migrate_pfn[1];
2438 
2439 	trace_mm_compaction_begin(cc, start_pfn, end_pfn, sync);
2440 
2441 	/* lru_add_drain_all could be expensive with involving other CPUs */
2442 	lru_add_drain();
2443 
2444 	while ((ret = compact_finished(cc)) == COMPACT_CONTINUE) {
2445 		int err;
2446 		unsigned long iteration_start_pfn = cc->migrate_pfn;
2447 
2448 		/*
2449 		 * Avoid multiple rescans of the same pageblock which can
2450 		 * happen if a page cannot be isolated (dirty/writeback in
2451 		 * async mode) or if the migrated pages are being allocated
2452 		 * before the pageblock is cleared.  The first rescan will
2453 		 * capture the entire pageblock for migration. If it fails,
2454 		 * it'll be marked skip and scanning will proceed as normal.
2455 		 */
2456 		cc->finish_pageblock = false;
2457 		if (pageblock_start_pfn(last_migrated_pfn) ==
2458 		    pageblock_start_pfn(iteration_start_pfn)) {
2459 			cc->finish_pageblock = true;
2460 		}
2461 
2462 rescan:
2463 		switch (isolate_migratepages(cc)) {
2464 		case ISOLATE_ABORT:
2465 			ret = COMPACT_CONTENDED;
2466 			putback_movable_pages(&cc->migratepages);
2467 			cc->nr_migratepages = 0;
2468 			goto out;
2469 		case ISOLATE_NONE:
2470 			if (update_cached) {
2471 				cc->zone->compact_cached_migrate_pfn[1] =
2472 					cc->zone->compact_cached_migrate_pfn[0];
2473 			}
2474 
2475 			/*
2476 			 * We haven't isolated and migrated anything, but
2477 			 * there might still be unflushed migrations from
2478 			 * previous cc->order aligned block.
2479 			 */
2480 			goto check_drain;
2481 		case ISOLATE_SUCCESS:
2482 			update_cached = false;
2483 			last_migrated_pfn = iteration_start_pfn;
2484 		}
2485 
2486 		err = migrate_pages(&cc->migratepages, compaction_alloc,
2487 				compaction_free, (unsigned long)cc, cc->mode,
2488 				MR_COMPACTION, &nr_succeeded);
2489 
2490 		trace_mm_compaction_migratepages(cc, nr_succeeded);
2491 
2492 		/* All pages were either migrated or will be released */
2493 		cc->nr_migratepages = 0;
2494 		if (err) {
2495 			putback_movable_pages(&cc->migratepages);
2496 			/*
2497 			 * migrate_pages() may return -ENOMEM when scanners meet
2498 			 * and we want compact_finished() to detect it
2499 			 */
2500 			if (err == -ENOMEM && !compact_scanners_met(cc)) {
2501 				ret = COMPACT_CONTENDED;
2502 				goto out;
2503 			}
2504 			/*
2505 			 * If an ASYNC or SYNC_LIGHT fails to migrate a page
2506 			 * within the current order-aligned block and
2507 			 * fast_find_migrateblock may be used then scan the
2508 			 * remainder of the pageblock. This will mark the
2509 			 * pageblock "skip" to avoid rescanning in the near
2510 			 * future. This will isolate more pages than necessary
2511 			 * for the request but avoid loops due to
2512 			 * fast_find_migrateblock revisiting blocks that were
2513 			 * recently partially scanned.
2514 			 */
2515 			if (!pageblock_aligned(cc->migrate_pfn) &&
2516 			    !cc->ignore_skip_hint && !cc->finish_pageblock &&
2517 			    (cc->mode < MIGRATE_SYNC)) {
2518 				cc->finish_pageblock = true;
2519 
2520 				/*
2521 				 * Draining pcplists does not help THP if
2522 				 * any page failed to migrate. Even after
2523 				 * drain, the pageblock will not be free.
2524 				 */
2525 				if (cc->order == COMPACTION_HPAGE_ORDER)
2526 					last_migrated_pfn = 0;
2527 
2528 				goto rescan;
2529 			}
2530 		}
2531 
2532 		/* Stop if a page has been captured */
2533 		if (capc && capc->page) {
2534 			ret = COMPACT_SUCCESS;
2535 			break;
2536 		}
2537 
2538 check_drain:
2539 		/*
2540 		 * Has the migration scanner moved away from the previous
2541 		 * cc->order aligned block where we migrated from? If yes,
2542 		 * flush the pages that were freed, so that they can merge and
2543 		 * compact_finished() can detect immediately if allocation
2544 		 * would succeed.
2545 		 */
2546 		if (cc->order > 0 && last_migrated_pfn) {
2547 			unsigned long current_block_start =
2548 				block_start_pfn(cc->migrate_pfn, cc->order);
2549 
2550 			if (last_migrated_pfn < current_block_start) {
2551 				lru_add_drain_cpu_zone(cc->zone);
2552 				/* No more flushing until we migrate again */
2553 				last_migrated_pfn = 0;
2554 			}
2555 		}
2556 	}
2557 
2558 out:
2559 	/*
2560 	 * Release free pages and update where the free scanner should restart,
2561 	 * so we don't leave any returned pages behind in the next attempt.
2562 	 */
2563 	if (cc->nr_freepages > 0) {
2564 		unsigned long free_pfn = release_freepages(&cc->freepages);
2565 
2566 		cc->nr_freepages = 0;
2567 		VM_BUG_ON(free_pfn == 0);
2568 		/* The cached pfn is always the first in a pageblock */
2569 		free_pfn = pageblock_start_pfn(free_pfn);
2570 		/*
2571 		 * Only go back, not forward. The cached pfn might have been
2572 		 * already reset to zone end in compact_finished()
2573 		 */
2574 		if (free_pfn > cc->zone->compact_cached_free_pfn)
2575 			cc->zone->compact_cached_free_pfn = free_pfn;
2576 	}
2577 
2578 	count_compact_events(COMPACTMIGRATE_SCANNED, cc->total_migrate_scanned);
2579 	count_compact_events(COMPACTFREE_SCANNED, cc->total_free_scanned);
2580 
2581 	trace_mm_compaction_end(cc, start_pfn, end_pfn, sync, ret);
2582 
2583 	VM_BUG_ON(!list_empty(&cc->freepages));
2584 	VM_BUG_ON(!list_empty(&cc->migratepages));
2585 
2586 	return ret;
2587 }
2588 
2589 static enum compact_result compact_zone_order(struct zone *zone, int order,
2590 		gfp_t gfp_mask, enum compact_priority prio,
2591 		unsigned int alloc_flags, int highest_zoneidx,
2592 		struct page **capture)
2593 {
2594 	enum compact_result ret;
2595 	struct compact_control cc = {
2596 		.order = order,
2597 		.search_order = order,
2598 		.gfp_mask = gfp_mask,
2599 		.zone = zone,
2600 		.mode = (prio == COMPACT_PRIO_ASYNC) ?
2601 					MIGRATE_ASYNC :	MIGRATE_SYNC_LIGHT,
2602 		.alloc_flags = alloc_flags,
2603 		.highest_zoneidx = highest_zoneidx,
2604 		.direct_compaction = true,
2605 		.whole_zone = (prio == MIN_COMPACT_PRIORITY),
2606 		.ignore_skip_hint = (prio == MIN_COMPACT_PRIORITY),
2607 		.ignore_block_suitable = (prio == MIN_COMPACT_PRIORITY)
2608 	};
2609 	struct capture_control capc = {
2610 		.cc = &cc,
2611 		.page = NULL,
2612 	};
2613 
2614 	/*
2615 	 * Make sure the structs are really initialized before we expose the
2616 	 * capture control, in case we are interrupted and the interrupt handler
2617 	 * frees a page.
2618 	 */
2619 	barrier();
2620 	WRITE_ONCE(current->capture_control, &capc);
2621 
2622 	ret = compact_zone(&cc, &capc);
2623 
2624 	/*
2625 	 * Make sure we hide capture control first before we read the captured
2626 	 * page pointer, otherwise an interrupt could free and capture a page
2627 	 * and we would leak it.
2628 	 */
2629 	WRITE_ONCE(current->capture_control, NULL);
2630 	*capture = READ_ONCE(capc.page);
2631 	/*
2632 	 * Technically, it is also possible that compaction is skipped but
2633 	 * the page is still captured out of luck(IRQ came and freed the page).
2634 	 * Returning COMPACT_SUCCESS in such cases helps in properly accounting
2635 	 * the COMPACT[STALL|FAIL] when compaction is skipped.
2636 	 */
2637 	if (*capture)
2638 		ret = COMPACT_SUCCESS;
2639 
2640 	return ret;
2641 }
2642 
2643 /**
2644  * try_to_compact_pages - Direct compact to satisfy a high-order allocation
2645  * @gfp_mask: The GFP mask of the current allocation
2646  * @order: The order of the current allocation
2647  * @alloc_flags: The allocation flags of the current allocation
2648  * @ac: The context of current allocation
2649  * @prio: Determines how hard direct compaction should try to succeed
2650  * @capture: Pointer to free page created by compaction will be stored here
2651  *
2652  * This is the main entry point for direct page compaction.
2653  */
2654 enum compact_result try_to_compact_pages(gfp_t gfp_mask, unsigned int order,
2655 		unsigned int alloc_flags, const struct alloc_context *ac,
2656 		enum compact_priority prio, struct page **capture)
2657 {
2658 	int may_perform_io = (__force int)(gfp_mask & __GFP_IO);
2659 	struct zoneref *z;
2660 	struct zone *zone;
2661 	enum compact_result rc = COMPACT_SKIPPED;
2662 
2663 	/*
2664 	 * Check if the GFP flags allow compaction - GFP_NOIO is really
2665 	 * tricky context because the migration might require IO
2666 	 */
2667 	if (!may_perform_io)
2668 		return COMPACT_SKIPPED;
2669 
2670 	trace_mm_compaction_try_to_compact_pages(order, gfp_mask, prio);
2671 
2672 	/* Compact each zone in the list */
2673 	for_each_zone_zonelist_nodemask(zone, z, ac->zonelist,
2674 					ac->highest_zoneidx, ac->nodemask) {
2675 		enum compact_result status;
2676 
2677 		if (prio > MIN_COMPACT_PRIORITY
2678 					&& compaction_deferred(zone, order)) {
2679 			rc = max_t(enum compact_result, COMPACT_DEFERRED, rc);
2680 			continue;
2681 		}
2682 
2683 		status = compact_zone_order(zone, order, gfp_mask, prio,
2684 				alloc_flags, ac->highest_zoneidx, capture);
2685 		rc = max(status, rc);
2686 
2687 		/* The allocation should succeed, stop compacting */
2688 		if (status == COMPACT_SUCCESS) {
2689 			/*
2690 			 * We think the allocation will succeed in this zone,
2691 			 * but it is not certain, hence the false. The caller
2692 			 * will repeat this with true if allocation indeed
2693 			 * succeeds in this zone.
2694 			 */
2695 			compaction_defer_reset(zone, order, false);
2696 
2697 			break;
2698 		}
2699 
2700 		if (prio != COMPACT_PRIO_ASYNC && (status == COMPACT_COMPLETE ||
2701 					status == COMPACT_PARTIAL_SKIPPED))
2702 			/*
2703 			 * We think that allocation won't succeed in this zone
2704 			 * so we defer compaction there. If it ends up
2705 			 * succeeding after all, it will be reset.
2706 			 */
2707 			defer_compaction(zone, order);
2708 
2709 		/*
2710 		 * We might have stopped compacting due to need_resched() in
2711 		 * async compaction, or due to a fatal signal detected. In that
2712 		 * case do not try further zones
2713 		 */
2714 		if ((prio == COMPACT_PRIO_ASYNC && need_resched())
2715 					|| fatal_signal_pending(current))
2716 			break;
2717 	}
2718 
2719 	return rc;
2720 }
2721 
2722 /*
2723  * Compact all zones within a node till each zone's fragmentation score
2724  * reaches within proactive compaction thresholds (as determined by the
2725  * proactiveness tunable).
2726  *
2727  * It is possible that the function returns before reaching score targets
2728  * due to various back-off conditions, such as, contention on per-node or
2729  * per-zone locks.
2730  */
2731 static void proactive_compact_node(pg_data_t *pgdat)
2732 {
2733 	int zoneid;
2734 	struct zone *zone;
2735 	struct compact_control cc = {
2736 		.order = -1,
2737 		.mode = MIGRATE_SYNC_LIGHT,
2738 		.ignore_skip_hint = true,
2739 		.whole_zone = true,
2740 		.gfp_mask = GFP_KERNEL,
2741 		.proactive_compaction = true,
2742 	};
2743 
2744 	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
2745 		zone = &pgdat->node_zones[zoneid];
2746 		if (!populated_zone(zone))
2747 			continue;
2748 
2749 		cc.zone = zone;
2750 
2751 		compact_zone(&cc, NULL);
2752 
2753 		count_compact_events(KCOMPACTD_MIGRATE_SCANNED,
2754 				     cc.total_migrate_scanned);
2755 		count_compact_events(KCOMPACTD_FREE_SCANNED,
2756 				     cc.total_free_scanned);
2757 	}
2758 }
2759 
2760 /* Compact all zones within a node */
2761 static void compact_node(int nid)
2762 {
2763 	pg_data_t *pgdat = NODE_DATA(nid);
2764 	int zoneid;
2765 	struct zone *zone;
2766 	struct compact_control cc = {
2767 		.order = -1,
2768 		.mode = MIGRATE_SYNC,
2769 		.ignore_skip_hint = true,
2770 		.whole_zone = true,
2771 		.gfp_mask = GFP_KERNEL,
2772 	};
2773 
2774 
2775 	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
2776 
2777 		zone = &pgdat->node_zones[zoneid];
2778 		if (!populated_zone(zone))
2779 			continue;
2780 
2781 		cc.zone = zone;
2782 
2783 		compact_zone(&cc, NULL);
2784 	}
2785 }
2786 
2787 /* Compact all nodes in the system */
2788 static void compact_nodes(void)
2789 {
2790 	int nid;
2791 
2792 	/* Flush pending updates to the LRU lists */
2793 	lru_add_drain_all();
2794 
2795 	for_each_online_node(nid)
2796 		compact_node(nid);
2797 }
2798 
2799 static int compaction_proactiveness_sysctl_handler(struct ctl_table *table, int write,
2800 		void *buffer, size_t *length, loff_t *ppos)
2801 {
2802 	int rc, nid;
2803 
2804 	rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
2805 	if (rc)
2806 		return rc;
2807 
2808 	if (write && sysctl_compaction_proactiveness) {
2809 		for_each_online_node(nid) {
2810 			pg_data_t *pgdat = NODE_DATA(nid);
2811 
2812 			if (pgdat->proactive_compact_trigger)
2813 				continue;
2814 
2815 			pgdat->proactive_compact_trigger = true;
2816 			trace_mm_compaction_wakeup_kcompactd(pgdat->node_id, -1,
2817 							     pgdat->nr_zones - 1);
2818 			wake_up_interruptible(&pgdat->kcompactd_wait);
2819 		}
2820 	}
2821 
2822 	return 0;
2823 }
2824 
2825 /*
2826  * This is the entry point for compacting all nodes via
2827  * /proc/sys/vm/compact_memory
2828  */
2829 static int sysctl_compaction_handler(struct ctl_table *table, int write,
2830 			void *buffer, size_t *length, loff_t *ppos)
2831 {
2832 	int ret;
2833 
2834 	ret = proc_dointvec(table, write, buffer, length, ppos);
2835 	if (ret)
2836 		return ret;
2837 
2838 	if (sysctl_compact_memory != 1)
2839 		return -EINVAL;
2840 
2841 	if (write)
2842 		compact_nodes();
2843 
2844 	return 0;
2845 }
2846 
2847 #if defined(CONFIG_SYSFS) && defined(CONFIG_NUMA)
2848 static ssize_t compact_store(struct device *dev,
2849 			     struct device_attribute *attr,
2850 			     const char *buf, size_t count)
2851 {
2852 	int nid = dev->id;
2853 
2854 	if (nid >= 0 && nid < nr_node_ids && node_online(nid)) {
2855 		/* Flush pending updates to the LRU lists */
2856 		lru_add_drain_all();
2857 
2858 		compact_node(nid);
2859 	}
2860 
2861 	return count;
2862 }
2863 static DEVICE_ATTR_WO(compact);
2864 
2865 int compaction_register_node(struct node *node)
2866 {
2867 	return device_create_file(&node->dev, &dev_attr_compact);
2868 }
2869 
2870 void compaction_unregister_node(struct node *node)
2871 {
2872 	return device_remove_file(&node->dev, &dev_attr_compact);
2873 }
2874 #endif /* CONFIG_SYSFS && CONFIG_NUMA */
2875 
2876 static inline bool kcompactd_work_requested(pg_data_t *pgdat)
2877 {
2878 	return pgdat->kcompactd_max_order > 0 || kthread_should_stop() ||
2879 		pgdat->proactive_compact_trigger;
2880 }
2881 
2882 static bool kcompactd_node_suitable(pg_data_t *pgdat)
2883 {
2884 	int zoneid;
2885 	struct zone *zone;
2886 	enum zone_type highest_zoneidx = pgdat->kcompactd_highest_zoneidx;
2887 
2888 	for (zoneid = 0; zoneid <= highest_zoneidx; zoneid++) {
2889 		zone = &pgdat->node_zones[zoneid];
2890 
2891 		if (!populated_zone(zone))
2892 			continue;
2893 
2894 		/* Allocation can already succeed, check other zones */
2895 		if (zone_watermark_ok(zone, pgdat->kcompactd_max_order,
2896 				      min_wmark_pages(zone),
2897 				      highest_zoneidx, 0))
2898 			continue;
2899 
2900 		if (compaction_suitable(zone, pgdat->kcompactd_max_order,
2901 					highest_zoneidx))
2902 			return true;
2903 	}
2904 
2905 	return false;
2906 }
2907 
2908 static void kcompactd_do_work(pg_data_t *pgdat)
2909 {
2910 	/*
2911 	 * With no special task, compact all zones so that a page of requested
2912 	 * order is allocatable.
2913 	 */
2914 	int zoneid;
2915 	struct zone *zone;
2916 	struct compact_control cc = {
2917 		.order = pgdat->kcompactd_max_order,
2918 		.search_order = pgdat->kcompactd_max_order,
2919 		.highest_zoneidx = pgdat->kcompactd_highest_zoneidx,
2920 		.mode = MIGRATE_SYNC_LIGHT,
2921 		.ignore_skip_hint = false,
2922 		.gfp_mask = GFP_KERNEL,
2923 	};
2924 	trace_mm_compaction_kcompactd_wake(pgdat->node_id, cc.order,
2925 							cc.highest_zoneidx);
2926 	count_compact_event(KCOMPACTD_WAKE);
2927 
2928 	for (zoneid = 0; zoneid <= cc.highest_zoneidx; zoneid++) {
2929 		int status;
2930 
2931 		zone = &pgdat->node_zones[zoneid];
2932 		if (!populated_zone(zone))
2933 			continue;
2934 
2935 		if (compaction_deferred(zone, cc.order))
2936 			continue;
2937 
2938 		/* Allocation can already succeed, nothing to do */
2939 		if (zone_watermark_ok(zone, cc.order,
2940 				      min_wmark_pages(zone), zoneid, 0))
2941 			continue;
2942 
2943 		if (!compaction_suitable(zone, cc.order, zoneid))
2944 			continue;
2945 
2946 		if (kthread_should_stop())
2947 			return;
2948 
2949 		cc.zone = zone;
2950 		status = compact_zone(&cc, NULL);
2951 
2952 		if (status == COMPACT_SUCCESS) {
2953 			compaction_defer_reset(zone, cc.order, false);
2954 		} else if (status == COMPACT_PARTIAL_SKIPPED || status == COMPACT_COMPLETE) {
2955 			/*
2956 			 * Buddy pages may become stranded on pcps that could
2957 			 * otherwise coalesce on the zone's free area for
2958 			 * order >= cc.order.  This is ratelimited by the
2959 			 * upcoming deferral.
2960 			 */
2961 			drain_all_pages(zone);
2962 
2963 			/*
2964 			 * We use sync migration mode here, so we defer like
2965 			 * sync direct compaction does.
2966 			 */
2967 			defer_compaction(zone, cc.order);
2968 		}
2969 
2970 		count_compact_events(KCOMPACTD_MIGRATE_SCANNED,
2971 				     cc.total_migrate_scanned);
2972 		count_compact_events(KCOMPACTD_FREE_SCANNED,
2973 				     cc.total_free_scanned);
2974 	}
2975 
2976 	/*
2977 	 * Regardless of success, we are done until woken up next. But remember
2978 	 * the requested order/highest_zoneidx in case it was higher/tighter
2979 	 * than our current ones
2980 	 */
2981 	if (pgdat->kcompactd_max_order <= cc.order)
2982 		pgdat->kcompactd_max_order = 0;
2983 	if (pgdat->kcompactd_highest_zoneidx >= cc.highest_zoneidx)
2984 		pgdat->kcompactd_highest_zoneidx = pgdat->nr_zones - 1;
2985 }
2986 
2987 void wakeup_kcompactd(pg_data_t *pgdat, int order, int highest_zoneidx)
2988 {
2989 	if (!order)
2990 		return;
2991 
2992 	if (pgdat->kcompactd_max_order < order)
2993 		pgdat->kcompactd_max_order = order;
2994 
2995 	if (pgdat->kcompactd_highest_zoneidx > highest_zoneidx)
2996 		pgdat->kcompactd_highest_zoneidx = highest_zoneidx;
2997 
2998 	/*
2999 	 * Pairs with implicit barrier in wait_event_freezable()
3000 	 * such that wakeups are not missed.
3001 	 */
3002 	if (!wq_has_sleeper(&pgdat->kcompactd_wait))
3003 		return;
3004 
3005 	if (!kcompactd_node_suitable(pgdat))
3006 		return;
3007 
3008 	trace_mm_compaction_wakeup_kcompactd(pgdat->node_id, order,
3009 							highest_zoneidx);
3010 	wake_up_interruptible(&pgdat->kcompactd_wait);
3011 }
3012 
3013 /*
3014  * The background compaction daemon, started as a kernel thread
3015  * from the init process.
3016  */
3017 static int kcompactd(void *p)
3018 {
3019 	pg_data_t *pgdat = (pg_data_t *)p;
3020 	struct task_struct *tsk = current;
3021 	long default_timeout = msecs_to_jiffies(HPAGE_FRAG_CHECK_INTERVAL_MSEC);
3022 	long timeout = default_timeout;
3023 
3024 	const struct cpumask *cpumask = cpumask_of_node(pgdat->node_id);
3025 
3026 	if (!cpumask_empty(cpumask))
3027 		set_cpus_allowed_ptr(tsk, cpumask);
3028 
3029 	set_freezable();
3030 
3031 	pgdat->kcompactd_max_order = 0;
3032 	pgdat->kcompactd_highest_zoneidx = pgdat->nr_zones - 1;
3033 
3034 	while (!kthread_should_stop()) {
3035 		unsigned long pflags;
3036 
3037 		/*
3038 		 * Avoid the unnecessary wakeup for proactive compaction
3039 		 * when it is disabled.
3040 		 */
3041 		if (!sysctl_compaction_proactiveness)
3042 			timeout = MAX_SCHEDULE_TIMEOUT;
3043 		trace_mm_compaction_kcompactd_sleep(pgdat->node_id);
3044 		if (wait_event_freezable_timeout(pgdat->kcompactd_wait,
3045 			kcompactd_work_requested(pgdat), timeout) &&
3046 			!pgdat->proactive_compact_trigger) {
3047 
3048 			psi_memstall_enter(&pflags);
3049 			kcompactd_do_work(pgdat);
3050 			psi_memstall_leave(&pflags);
3051 			/*
3052 			 * Reset the timeout value. The defer timeout from
3053 			 * proactive compaction is lost here but that is fine
3054 			 * as the condition of the zone changing substantionally
3055 			 * then carrying on with the previous defer interval is
3056 			 * not useful.
3057 			 */
3058 			timeout = default_timeout;
3059 			continue;
3060 		}
3061 
3062 		/*
3063 		 * Start the proactive work with default timeout. Based
3064 		 * on the fragmentation score, this timeout is updated.
3065 		 */
3066 		timeout = default_timeout;
3067 		if (should_proactive_compact_node(pgdat)) {
3068 			unsigned int prev_score, score;
3069 
3070 			prev_score = fragmentation_score_node(pgdat);
3071 			proactive_compact_node(pgdat);
3072 			score = fragmentation_score_node(pgdat);
3073 			/*
3074 			 * Defer proactive compaction if the fragmentation
3075 			 * score did not go down i.e. no progress made.
3076 			 */
3077 			if (unlikely(score >= prev_score))
3078 				timeout =
3079 				   default_timeout << COMPACT_MAX_DEFER_SHIFT;
3080 		}
3081 		if (unlikely(pgdat->proactive_compact_trigger))
3082 			pgdat->proactive_compact_trigger = false;
3083 	}
3084 
3085 	return 0;
3086 }
3087 
3088 /*
3089  * This kcompactd start function will be called by init and node-hot-add.
3090  * On node-hot-add, kcompactd will moved to proper cpus if cpus are hot-added.
3091  */
3092 void __meminit kcompactd_run(int nid)
3093 {
3094 	pg_data_t *pgdat = NODE_DATA(nid);
3095 
3096 	if (pgdat->kcompactd)
3097 		return;
3098 
3099 	pgdat->kcompactd = kthread_run(kcompactd, pgdat, "kcompactd%d", nid);
3100 	if (IS_ERR(pgdat->kcompactd)) {
3101 		pr_err("Failed to start kcompactd on node %d\n", nid);
3102 		pgdat->kcompactd = NULL;
3103 	}
3104 }
3105 
3106 /*
3107  * Called by memory hotplug when all memory in a node is offlined. Caller must
3108  * be holding mem_hotplug_begin/done().
3109  */
3110 void __meminit kcompactd_stop(int nid)
3111 {
3112 	struct task_struct *kcompactd = NODE_DATA(nid)->kcompactd;
3113 
3114 	if (kcompactd) {
3115 		kthread_stop(kcompactd);
3116 		NODE_DATA(nid)->kcompactd = NULL;
3117 	}
3118 }
3119 
3120 /*
3121  * It's optimal to keep kcompactd on the same CPUs as their memory, but
3122  * not required for correctness. So if the last cpu in a node goes
3123  * away, we get changed to run anywhere: as the first one comes back,
3124  * restore their cpu bindings.
3125  */
3126 static int kcompactd_cpu_online(unsigned int cpu)
3127 {
3128 	int nid;
3129 
3130 	for_each_node_state(nid, N_MEMORY) {
3131 		pg_data_t *pgdat = NODE_DATA(nid);
3132 		const struct cpumask *mask;
3133 
3134 		mask = cpumask_of_node(pgdat->node_id);
3135 
3136 		if (cpumask_any_and(cpu_online_mask, mask) < nr_cpu_ids)
3137 			/* One of our CPUs online: restore mask */
3138 			if (pgdat->kcompactd)
3139 				set_cpus_allowed_ptr(pgdat->kcompactd, mask);
3140 	}
3141 	return 0;
3142 }
3143 
3144 static int proc_dointvec_minmax_warn_RT_change(struct ctl_table *table,
3145 		int write, void *buffer, size_t *lenp, loff_t *ppos)
3146 {
3147 	int ret, old;
3148 
3149 	if (!IS_ENABLED(CONFIG_PREEMPT_RT) || !write)
3150 		return proc_dointvec_minmax(table, write, buffer, lenp, ppos);
3151 
3152 	old = *(int *)table->data;
3153 	ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
3154 	if (ret)
3155 		return ret;
3156 	if (old != *(int *)table->data)
3157 		pr_warn_once("sysctl attribute %s changed by %s[%d]\n",
3158 			     table->procname, current->comm,
3159 			     task_pid_nr(current));
3160 	return ret;
3161 }
3162 
3163 static struct ctl_table vm_compaction[] = {
3164 	{
3165 		.procname	= "compact_memory",
3166 		.data		= &sysctl_compact_memory,
3167 		.maxlen		= sizeof(int),
3168 		.mode		= 0200,
3169 		.proc_handler	= sysctl_compaction_handler,
3170 	},
3171 	{
3172 		.procname	= "compaction_proactiveness",
3173 		.data		= &sysctl_compaction_proactiveness,
3174 		.maxlen		= sizeof(sysctl_compaction_proactiveness),
3175 		.mode		= 0644,
3176 		.proc_handler	= compaction_proactiveness_sysctl_handler,
3177 		.extra1		= SYSCTL_ZERO,
3178 		.extra2		= SYSCTL_ONE_HUNDRED,
3179 	},
3180 	{
3181 		.procname	= "extfrag_threshold",
3182 		.data		= &sysctl_extfrag_threshold,
3183 		.maxlen		= sizeof(int),
3184 		.mode		= 0644,
3185 		.proc_handler	= proc_dointvec_minmax,
3186 		.extra1		= SYSCTL_ZERO,
3187 		.extra2		= SYSCTL_ONE_THOUSAND,
3188 	},
3189 	{
3190 		.procname	= "compact_unevictable_allowed",
3191 		.data		= &sysctl_compact_unevictable_allowed,
3192 		.maxlen		= sizeof(int),
3193 		.mode		= 0644,
3194 		.proc_handler	= proc_dointvec_minmax_warn_RT_change,
3195 		.extra1		= SYSCTL_ZERO,
3196 		.extra2		= SYSCTL_ONE,
3197 	},
3198 	{ }
3199 };
3200 
3201 static int __init kcompactd_init(void)
3202 {
3203 	int nid;
3204 	int ret;
3205 
3206 	ret = cpuhp_setup_state_nocalls(CPUHP_AP_ONLINE_DYN,
3207 					"mm/compaction:online",
3208 					kcompactd_cpu_online, NULL);
3209 	if (ret < 0) {
3210 		pr_err("kcompactd: failed to register hotplug callbacks.\n");
3211 		return ret;
3212 	}
3213 
3214 	for_each_node_state(nid, N_MEMORY)
3215 		kcompactd_run(nid);
3216 	register_sysctl_init("vm", vm_compaction);
3217 	return 0;
3218 }
3219 subsys_initcall(kcompactd_init)
3220 
3221 #endif /* CONFIG_COMPACTION */
3222