mm/compaction.c

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