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