1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Workingset detection 4 * 5 * Copyright (C) 2013 Red Hat, Inc., Johannes Weiner 6 */ 7 8 #include <linux/memcontrol.h> 9 #include <linux/mm_inline.h> 10 #include <linux/writeback.h> 11 #include <linux/shmem_fs.h> 12 #include <linux/pagemap.h> 13 #include <linux/atomic.h> 14 #include <linux/module.h> 15 #include <linux/swap.h> 16 #include <linux/dax.h> 17 #include <linux/fs.h> 18 #include <linux/mm.h> 19 20 /* 21 * Double CLOCK lists 22 * 23 * Per node, two clock lists are maintained for file pages: the 24 * inactive and the active list. Freshly faulted pages start out at 25 * the head of the inactive list and page reclaim scans pages from the 26 * tail. Pages that are accessed multiple times on the inactive list 27 * are promoted to the active list, to protect them from reclaim, 28 * whereas active pages are demoted to the inactive list when the 29 * active list grows too big. 30 * 31 * fault ------------------------+ 32 * | 33 * +--------------+ | +-------------+ 34 * reclaim <- | inactive | <-+-- demotion | active | <--+ 35 * +--------------+ +-------------+ | 36 * | | 37 * +-------------- promotion ------------------+ 38 * 39 * 40 * Access frequency and refault distance 41 * 42 * A workload is thrashing when its pages are frequently used but they 43 * are evicted from the inactive list every time before another access 44 * would have promoted them to the active list. 45 * 46 * In cases where the average access distance between thrashing pages 47 * is bigger than the size of memory there is nothing that can be 48 * done - the thrashing set could never fit into memory under any 49 * circumstance. 50 * 51 * However, the average access distance could be bigger than the 52 * inactive list, yet smaller than the size of memory. In this case, 53 * the set could fit into memory if it weren't for the currently 54 * active pages - which may be used more, hopefully less frequently: 55 * 56 * +-memory available to cache-+ 57 * | | 58 * +-inactive------+-active----+ 59 * a b | c d e f g h i | J K L M N | 60 * +---------------+-----------+ 61 * 62 * It is prohibitively expensive to accurately track access frequency 63 * of pages. But a reasonable approximation can be made to measure 64 * thrashing on the inactive list, after which refaulting pages can be 65 * activated optimistically to compete with the existing active pages. 66 * 67 * Approximating inactive page access frequency - Observations: 68 * 69 * 1. When a page is accessed for the first time, it is added to the 70 * head of the inactive list, slides every existing inactive page 71 * towards the tail by one slot, and pushes the current tail page 72 * out of memory. 73 * 74 * 2. When a page is accessed for the second time, it is promoted to 75 * the active list, shrinking the inactive list by one slot. This 76 * also slides all inactive pages that were faulted into the cache 77 * more recently than the activated page towards the tail of the 78 * inactive list. 79 * 80 * Thus: 81 * 82 * 1. The sum of evictions and activations between any two points in 83 * time indicate the minimum number of inactive pages accessed in 84 * between. 85 * 86 * 2. Moving one inactive page N page slots towards the tail of the 87 * list requires at least N inactive page accesses. 88 * 89 * Combining these: 90 * 91 * 1. When a page is finally evicted from memory, the number of 92 * inactive pages accessed while the page was in cache is at least 93 * the number of page slots on the inactive list. 94 * 95 * 2. In addition, measuring the sum of evictions and activations (E) 96 * at the time of a page's eviction, and comparing it to another 97 * reading (R) at the time the page faults back into memory tells 98 * the minimum number of accesses while the page was not cached. 99 * This is called the refault distance. 100 * 101 * Because the first access of the page was the fault and the second 102 * access the refault, we combine the in-cache distance with the 103 * out-of-cache distance to get the complete minimum access distance 104 * of this page: 105 * 106 * NR_inactive + (R - E) 107 * 108 * And knowing the minimum access distance of a page, we can easily 109 * tell if the page would be able to stay in cache assuming all page 110 * slots in the cache were available: 111 * 112 * NR_inactive + (R - E) <= NR_inactive + NR_active 113 * 114 * which can be further simplified to 115 * 116 * (R - E) <= NR_active 117 * 118 * Put into words, the refault distance (out-of-cache) can be seen as 119 * a deficit in inactive list space (in-cache). If the inactive list 120 * had (R - E) more page slots, the page would not have been evicted 121 * in between accesses, but activated instead. And on a full system, 122 * the only thing eating into inactive list space is active pages. 123 * 124 * 125 * Refaulting inactive pages 126 * 127 * All that is known about the active list is that the pages have been 128 * accessed more than once in the past. This means that at any given 129 * time there is actually a good chance that pages on the active list 130 * are no longer in active use. 131 * 132 * So when a refault distance of (R - E) is observed and there are at 133 * least (R - E) active pages, the refaulting page is activated 134 * optimistically in the hope that (R - E) active pages are actually 135 * used less frequently than the refaulting page - or even not used at 136 * all anymore. 137 * 138 * That means if inactive cache is refaulting with a suitable refault 139 * distance, we assume the cache workingset is transitioning and put 140 * pressure on the current active list. 141 * 142 * If this is wrong and demotion kicks in, the pages which are truly 143 * used more frequently will be reactivated while the less frequently 144 * used once will be evicted from memory. 145 * 146 * But if this is right, the stale pages will be pushed out of memory 147 * and the used pages get to stay in cache. 148 * 149 * Refaulting active pages 150 * 151 * If on the other hand the refaulting pages have recently been 152 * deactivated, it means that the active list is no longer protecting 153 * actively used cache from reclaim. The cache is NOT transitioning to 154 * a different workingset; the existing workingset is thrashing in the 155 * space allocated to the page cache. 156 * 157 * 158 * Implementation 159 * 160 * For each node's LRU lists, a counter for inactive evictions and 161 * activations is maintained (node->nonresident_age). 162 * 163 * On eviction, a snapshot of this counter (along with some bits to 164 * identify the node) is stored in the now empty page cache 165 * slot of the evicted page. This is called a shadow entry. 166 * 167 * On cache misses for which there are shadow entries, an eligible 168 * refault distance will immediately activate the refaulting page. 169 */ 170 171 #define WORKINGSET_SHIFT 1 172 #define EVICTION_SHIFT ((BITS_PER_LONG - BITS_PER_XA_VALUE) + \ 173 WORKINGSET_SHIFT + NODES_SHIFT + \ 174 MEM_CGROUP_ID_SHIFT) 175 #define EVICTION_MASK (~0UL >> EVICTION_SHIFT) 176 177 /* 178 * Eviction timestamps need to be able to cover the full range of 179 * actionable refaults. However, bits are tight in the xarray 180 * entry, and after storing the identifier for the lruvec there might 181 * not be enough left to represent every single actionable refault. In 182 * that case, we have to sacrifice granularity for distance, and group 183 * evictions into coarser buckets by shaving off lower timestamp bits. 184 */ 185 static unsigned int bucket_order __read_mostly; 186 187 static void *pack_shadow(int memcgid, pg_data_t *pgdat, unsigned long eviction, 188 bool workingset) 189 { 190 eviction &= EVICTION_MASK; 191 eviction = (eviction << MEM_CGROUP_ID_SHIFT) | memcgid; 192 eviction = (eviction << NODES_SHIFT) | pgdat->node_id; 193 eviction = (eviction << WORKINGSET_SHIFT) | workingset; 194 195 return xa_mk_value(eviction); 196 } 197 198 static void unpack_shadow(void *shadow, int *memcgidp, pg_data_t **pgdat, 199 unsigned long *evictionp, bool *workingsetp) 200 { 201 unsigned long entry = xa_to_value(shadow); 202 int memcgid, nid; 203 bool workingset; 204 205 workingset = entry & ((1UL << WORKINGSET_SHIFT) - 1); 206 entry >>= WORKINGSET_SHIFT; 207 nid = entry & ((1UL << NODES_SHIFT) - 1); 208 entry >>= NODES_SHIFT; 209 memcgid = entry & ((1UL << MEM_CGROUP_ID_SHIFT) - 1); 210 entry >>= MEM_CGROUP_ID_SHIFT; 211 212 *memcgidp = memcgid; 213 *pgdat = NODE_DATA(nid); 214 *evictionp = entry; 215 *workingsetp = workingset; 216 } 217 218 #ifdef CONFIG_LRU_GEN 219 220 static void *lru_gen_eviction(struct folio *folio) 221 { 222 int hist; 223 unsigned long token; 224 unsigned long min_seq; 225 struct lruvec *lruvec; 226 struct lru_gen_struct *lrugen; 227 int type = folio_is_file_lru(folio); 228 int delta = folio_nr_pages(folio); 229 int refs = folio_lru_refs(folio); 230 int tier = lru_tier_from_refs(refs); 231 struct mem_cgroup *memcg = folio_memcg(folio); 232 struct pglist_data *pgdat = folio_pgdat(folio); 233 234 BUILD_BUG_ON(LRU_GEN_WIDTH + LRU_REFS_WIDTH > BITS_PER_LONG - EVICTION_SHIFT); 235 236 lruvec = mem_cgroup_lruvec(memcg, pgdat); 237 lrugen = &lruvec->lrugen; 238 min_seq = READ_ONCE(lrugen->min_seq[type]); 239 token = (min_seq << LRU_REFS_WIDTH) | max(refs - 1, 0); 240 241 hist = lru_hist_from_seq(min_seq); 242 atomic_long_add(delta, &lrugen->evicted[hist][type][tier]); 243 244 return pack_shadow(mem_cgroup_id(memcg), pgdat, token, refs); 245 } 246 247 static void lru_gen_refault(struct folio *folio, void *shadow) 248 { 249 int hist, tier, refs; 250 int memcg_id; 251 bool workingset; 252 unsigned long token; 253 unsigned long min_seq; 254 struct lruvec *lruvec; 255 struct lru_gen_struct *lrugen; 256 struct mem_cgroup *memcg; 257 struct pglist_data *pgdat; 258 int type = folio_is_file_lru(folio); 259 int delta = folio_nr_pages(folio); 260 261 unpack_shadow(shadow, &memcg_id, &pgdat, &token, &workingset); 262 263 if (pgdat != folio_pgdat(folio)) 264 return; 265 266 rcu_read_lock(); 267 268 memcg = folio_memcg_rcu(folio); 269 if (memcg_id != mem_cgroup_id(memcg)) 270 goto unlock; 271 272 lruvec = mem_cgroup_lruvec(memcg, pgdat); 273 lrugen = &lruvec->lrugen; 274 275 min_seq = READ_ONCE(lrugen->min_seq[type]); 276 if ((token >> LRU_REFS_WIDTH) != (min_seq & (EVICTION_MASK >> LRU_REFS_WIDTH))) 277 goto unlock; 278 279 hist = lru_hist_from_seq(min_seq); 280 /* see the comment in folio_lru_refs() */ 281 refs = (token & (BIT(LRU_REFS_WIDTH) - 1)) + workingset; 282 tier = lru_tier_from_refs(refs); 283 284 atomic_long_add(delta, &lrugen->refaulted[hist][type][tier]); 285 mod_lruvec_state(lruvec, WORKINGSET_REFAULT_BASE + type, delta); 286 287 /* 288 * Count the following two cases as stalls: 289 * 1. For pages accessed through page tables, hotter pages pushed out 290 * hot pages which refaulted immediately. 291 * 2. For pages accessed multiple times through file descriptors, 292 * numbers of accesses might have been out of the range. 293 */ 294 if (lru_gen_in_fault() || refs == BIT(LRU_REFS_WIDTH)) { 295 folio_set_workingset(folio); 296 mod_lruvec_state(lruvec, WORKINGSET_RESTORE_BASE + type, delta); 297 } 298 unlock: 299 rcu_read_unlock(); 300 } 301 302 #else /* !CONFIG_LRU_GEN */ 303 304 static void *lru_gen_eviction(struct folio *folio) 305 { 306 return NULL; 307 } 308 309 static void lru_gen_refault(struct folio *folio, void *shadow) 310 { 311 } 312 313 #endif /* CONFIG_LRU_GEN */ 314 315 /** 316 * workingset_age_nonresident - age non-resident entries as LRU ages 317 * @lruvec: the lruvec that was aged 318 * @nr_pages: the number of pages to count 319 * 320 * As in-memory pages are aged, non-resident pages need to be aged as 321 * well, in order for the refault distances later on to be comparable 322 * to the in-memory dimensions. This function allows reclaim and LRU 323 * operations to drive the non-resident aging along in parallel. 324 */ 325 void workingset_age_nonresident(struct lruvec *lruvec, unsigned long nr_pages) 326 { 327 /* 328 * Reclaiming a cgroup means reclaiming all its children in a 329 * round-robin fashion. That means that each cgroup has an LRU 330 * order that is composed of the LRU orders of its child 331 * cgroups; and every page has an LRU position not just in the 332 * cgroup that owns it, but in all of that group's ancestors. 333 * 334 * So when the physical inactive list of a leaf cgroup ages, 335 * the virtual inactive lists of all its parents, including 336 * the root cgroup's, age as well. 337 */ 338 do { 339 atomic_long_add(nr_pages, &lruvec->nonresident_age); 340 } while ((lruvec = parent_lruvec(lruvec))); 341 } 342 343 /** 344 * workingset_eviction - note the eviction of a folio from memory 345 * @target_memcg: the cgroup that is causing the reclaim 346 * @folio: the folio being evicted 347 * 348 * Return: a shadow entry to be stored in @folio->mapping->i_pages in place 349 * of the evicted @folio so that a later refault can be detected. 350 */ 351 void *workingset_eviction(struct folio *folio, struct mem_cgroup *target_memcg) 352 { 353 struct pglist_data *pgdat = folio_pgdat(folio); 354 unsigned long eviction; 355 struct lruvec *lruvec; 356 int memcgid; 357 358 /* Folio is fully exclusive and pins folio's memory cgroup pointer */ 359 VM_BUG_ON_FOLIO(folio_test_lru(folio), folio); 360 VM_BUG_ON_FOLIO(folio_ref_count(folio), folio); 361 VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio); 362 363 if (lru_gen_enabled()) 364 return lru_gen_eviction(folio); 365 366 lruvec = mem_cgroup_lruvec(target_memcg, pgdat); 367 /* XXX: target_memcg can be NULL, go through lruvec */ 368 memcgid = mem_cgroup_id(lruvec_memcg(lruvec)); 369 eviction = atomic_long_read(&lruvec->nonresident_age); 370 eviction >>= bucket_order; 371 workingset_age_nonresident(lruvec, folio_nr_pages(folio)); 372 return pack_shadow(memcgid, pgdat, eviction, 373 folio_test_workingset(folio)); 374 } 375 376 /** 377 * workingset_refault - Evaluate the refault of a previously evicted folio. 378 * @folio: The freshly allocated replacement folio. 379 * @shadow: Shadow entry of the evicted folio. 380 * 381 * Calculates and evaluates the refault distance of the previously 382 * evicted folio in the context of the node and the memcg whose memory 383 * pressure caused the eviction. 384 */ 385 void workingset_refault(struct folio *folio, void *shadow) 386 { 387 bool file = folio_is_file_lru(folio); 388 struct mem_cgroup *eviction_memcg; 389 struct lruvec *eviction_lruvec; 390 unsigned long refault_distance; 391 unsigned long workingset_size; 392 struct pglist_data *pgdat; 393 struct mem_cgroup *memcg; 394 unsigned long eviction; 395 struct lruvec *lruvec; 396 unsigned long refault; 397 bool workingset; 398 int memcgid; 399 long nr; 400 401 if (lru_gen_enabled()) { 402 lru_gen_refault(folio, shadow); 403 return; 404 } 405 406 unpack_shadow(shadow, &memcgid, &pgdat, &eviction, &workingset); 407 eviction <<= bucket_order; 408 409 rcu_read_lock(); 410 /* 411 * Look up the memcg associated with the stored ID. It might 412 * have been deleted since the folio's eviction. 413 * 414 * Note that in rare events the ID could have been recycled 415 * for a new cgroup that refaults a shared folio. This is 416 * impossible to tell from the available data. However, this 417 * should be a rare and limited disturbance, and activations 418 * are always speculative anyway. Ultimately, it's the aging 419 * algorithm's job to shake out the minimum access frequency 420 * for the active cache. 421 * 422 * XXX: On !CONFIG_MEMCG, this will always return NULL; it 423 * would be better if the root_mem_cgroup existed in all 424 * configurations instead. 425 */ 426 eviction_memcg = mem_cgroup_from_id(memcgid); 427 if (!mem_cgroup_disabled() && !eviction_memcg) 428 goto out; 429 eviction_lruvec = mem_cgroup_lruvec(eviction_memcg, pgdat); 430 refault = atomic_long_read(&eviction_lruvec->nonresident_age); 431 432 /* 433 * Calculate the refault distance 434 * 435 * The unsigned subtraction here gives an accurate distance 436 * across nonresident_age overflows in most cases. There is a 437 * special case: usually, shadow entries have a short lifetime 438 * and are either refaulted or reclaimed along with the inode 439 * before they get too old. But it is not impossible for the 440 * nonresident_age to lap a shadow entry in the field, which 441 * can then result in a false small refault distance, leading 442 * to a false activation should this old entry actually 443 * refault again. However, earlier kernels used to deactivate 444 * unconditionally with *every* reclaim invocation for the 445 * longest time, so the occasional inappropriate activation 446 * leading to pressure on the active list is not a problem. 447 */ 448 refault_distance = (refault - eviction) & EVICTION_MASK; 449 450 /* 451 * The activation decision for this folio is made at the level 452 * where the eviction occurred, as that is where the LRU order 453 * during folio reclaim is being determined. 454 * 455 * However, the cgroup that will own the folio is the one that 456 * is actually experiencing the refault event. 457 */ 458 nr = folio_nr_pages(folio); 459 memcg = folio_memcg(folio); 460 lruvec = mem_cgroup_lruvec(memcg, pgdat); 461 462 mod_lruvec_state(lruvec, WORKINGSET_REFAULT_BASE + file, nr); 463 464 mem_cgroup_flush_stats_delayed(); 465 /* 466 * Compare the distance to the existing workingset size. We 467 * don't activate pages that couldn't stay resident even if 468 * all the memory was available to the workingset. Whether 469 * workingset competition needs to consider anon or not depends 470 * on having swap. 471 */ 472 workingset_size = lruvec_page_state(eviction_lruvec, NR_ACTIVE_FILE); 473 if (!file) { 474 workingset_size += lruvec_page_state(eviction_lruvec, 475 NR_INACTIVE_FILE); 476 } 477 if (mem_cgroup_get_nr_swap_pages(memcg) > 0) { 478 workingset_size += lruvec_page_state(eviction_lruvec, 479 NR_ACTIVE_ANON); 480 if (file) { 481 workingset_size += lruvec_page_state(eviction_lruvec, 482 NR_INACTIVE_ANON); 483 } 484 } 485 if (refault_distance > workingset_size) 486 goto out; 487 488 folio_set_active(folio); 489 workingset_age_nonresident(lruvec, nr); 490 mod_lruvec_state(lruvec, WORKINGSET_ACTIVATE_BASE + file, nr); 491 492 /* Folio was active prior to eviction */ 493 if (workingset) { 494 folio_set_workingset(folio); 495 /* XXX: Move to lru_cache_add() when it supports new vs putback */ 496 lru_note_cost_folio(folio); 497 mod_lruvec_state(lruvec, WORKINGSET_RESTORE_BASE + file, nr); 498 } 499 out: 500 rcu_read_unlock(); 501 } 502 503 /** 504 * workingset_activation - note a page activation 505 * @folio: Folio that is being activated. 506 */ 507 void workingset_activation(struct folio *folio) 508 { 509 struct mem_cgroup *memcg; 510 511 rcu_read_lock(); 512 /* 513 * Filter non-memcg pages here, e.g. unmap can call 514 * mark_page_accessed() on VDSO pages. 515 * 516 * XXX: See workingset_refault() - this should return 517 * root_mem_cgroup even for !CONFIG_MEMCG. 518 */ 519 memcg = folio_memcg_rcu(folio); 520 if (!mem_cgroup_disabled() && !memcg) 521 goto out; 522 workingset_age_nonresident(folio_lruvec(folio), folio_nr_pages(folio)); 523 out: 524 rcu_read_unlock(); 525 } 526 527 /* 528 * Shadow entries reflect the share of the working set that does not 529 * fit into memory, so their number depends on the access pattern of 530 * the workload. In most cases, they will refault or get reclaimed 531 * along with the inode, but a (malicious) workload that streams 532 * through files with a total size several times that of available 533 * memory, while preventing the inodes from being reclaimed, can 534 * create excessive amounts of shadow nodes. To keep a lid on this, 535 * track shadow nodes and reclaim them when they grow way past the 536 * point where they would still be useful. 537 */ 538 539 struct list_lru shadow_nodes; 540 541 void workingset_update_node(struct xa_node *node) 542 { 543 struct address_space *mapping; 544 545 /* 546 * Track non-empty nodes that contain only shadow entries; 547 * unlink those that contain pages or are being freed. 548 * 549 * Avoid acquiring the list_lru lock when the nodes are 550 * already where they should be. The list_empty() test is safe 551 * as node->private_list is protected by the i_pages lock. 552 */ 553 mapping = container_of(node->array, struct address_space, i_pages); 554 lockdep_assert_held(&mapping->i_pages.xa_lock); 555 556 if (node->count && node->count == node->nr_values) { 557 if (list_empty(&node->private_list)) { 558 list_lru_add(&shadow_nodes, &node->private_list); 559 __inc_lruvec_kmem_state(node, WORKINGSET_NODES); 560 } 561 } else { 562 if (!list_empty(&node->private_list)) { 563 list_lru_del(&shadow_nodes, &node->private_list); 564 __dec_lruvec_kmem_state(node, WORKINGSET_NODES); 565 } 566 } 567 } 568 569 static unsigned long count_shadow_nodes(struct shrinker *shrinker, 570 struct shrink_control *sc) 571 { 572 unsigned long max_nodes; 573 unsigned long nodes; 574 unsigned long pages; 575 576 nodes = list_lru_shrink_count(&shadow_nodes, sc); 577 if (!nodes) 578 return SHRINK_EMPTY; 579 580 /* 581 * Approximate a reasonable limit for the nodes 582 * containing shadow entries. We don't need to keep more 583 * shadow entries than possible pages on the active list, 584 * since refault distances bigger than that are dismissed. 585 * 586 * The size of the active list converges toward 100% of 587 * overall page cache as memory grows, with only a tiny 588 * inactive list. Assume the total cache size for that. 589 * 590 * Nodes might be sparsely populated, with only one shadow 591 * entry in the extreme case. Obviously, we cannot keep one 592 * node for every eligible shadow entry, so compromise on a 593 * worst-case density of 1/8th. Below that, not all eligible 594 * refaults can be detected anymore. 595 * 596 * On 64-bit with 7 xa_nodes per page and 64 slots 597 * each, this will reclaim shadow entries when they consume 598 * ~1.8% of available memory: 599 * 600 * PAGE_SIZE / xa_nodes / node_entries * 8 / PAGE_SIZE 601 */ 602 #ifdef CONFIG_MEMCG 603 if (sc->memcg) { 604 struct lruvec *lruvec; 605 int i; 606 607 lruvec = mem_cgroup_lruvec(sc->memcg, NODE_DATA(sc->nid)); 608 for (pages = 0, i = 0; i < NR_LRU_LISTS; i++) 609 pages += lruvec_page_state_local(lruvec, 610 NR_LRU_BASE + i); 611 pages += lruvec_page_state_local( 612 lruvec, NR_SLAB_RECLAIMABLE_B) >> PAGE_SHIFT; 613 pages += lruvec_page_state_local( 614 lruvec, NR_SLAB_UNRECLAIMABLE_B) >> PAGE_SHIFT; 615 } else 616 #endif 617 pages = node_present_pages(sc->nid); 618 619 max_nodes = pages >> (XA_CHUNK_SHIFT - 3); 620 621 if (nodes <= max_nodes) 622 return 0; 623 return nodes - max_nodes; 624 } 625 626 static enum lru_status shadow_lru_isolate(struct list_head *item, 627 struct list_lru_one *lru, 628 spinlock_t *lru_lock, 629 void *arg) __must_hold(lru_lock) 630 { 631 struct xa_node *node = container_of(item, struct xa_node, private_list); 632 struct address_space *mapping; 633 int ret; 634 635 /* 636 * Page cache insertions and deletions synchronously maintain 637 * the shadow node LRU under the i_pages lock and the 638 * lru_lock. Because the page cache tree is emptied before 639 * the inode can be destroyed, holding the lru_lock pins any 640 * address_space that has nodes on the LRU. 641 * 642 * We can then safely transition to the i_pages lock to 643 * pin only the address_space of the particular node we want 644 * to reclaim, take the node off-LRU, and drop the lru_lock. 645 */ 646 647 mapping = container_of(node->array, struct address_space, i_pages); 648 649 /* Coming from the list, invert the lock order */ 650 if (!xa_trylock(&mapping->i_pages)) { 651 spin_unlock_irq(lru_lock); 652 ret = LRU_RETRY; 653 goto out; 654 } 655 656 if (!spin_trylock(&mapping->host->i_lock)) { 657 xa_unlock(&mapping->i_pages); 658 spin_unlock_irq(lru_lock); 659 ret = LRU_RETRY; 660 goto out; 661 } 662 663 list_lru_isolate(lru, item); 664 __dec_lruvec_kmem_state(node, WORKINGSET_NODES); 665 666 spin_unlock(lru_lock); 667 668 /* 669 * The nodes should only contain one or more shadow entries, 670 * no pages, so we expect to be able to remove them all and 671 * delete and free the empty node afterwards. 672 */ 673 if (WARN_ON_ONCE(!node->nr_values)) 674 goto out_invalid; 675 if (WARN_ON_ONCE(node->count != node->nr_values)) 676 goto out_invalid; 677 xa_delete_node(node, workingset_update_node); 678 __inc_lruvec_kmem_state(node, WORKINGSET_NODERECLAIM); 679 680 out_invalid: 681 xa_unlock_irq(&mapping->i_pages); 682 if (mapping_shrinkable(mapping)) 683 inode_add_lru(mapping->host); 684 spin_unlock(&mapping->host->i_lock); 685 ret = LRU_REMOVED_RETRY; 686 out: 687 cond_resched(); 688 spin_lock_irq(lru_lock); 689 return ret; 690 } 691 692 static unsigned long scan_shadow_nodes(struct shrinker *shrinker, 693 struct shrink_control *sc) 694 { 695 /* list_lru lock nests inside the IRQ-safe i_pages lock */ 696 return list_lru_shrink_walk_irq(&shadow_nodes, sc, shadow_lru_isolate, 697 NULL); 698 } 699 700 static struct shrinker workingset_shadow_shrinker = { 701 .count_objects = count_shadow_nodes, 702 .scan_objects = scan_shadow_nodes, 703 .seeks = 0, /* ->count reports only fully expendable nodes */ 704 .flags = SHRINKER_NUMA_AWARE | SHRINKER_MEMCG_AWARE, 705 }; 706 707 /* 708 * Our list_lru->lock is IRQ-safe as it nests inside the IRQ-safe 709 * i_pages lock. 710 */ 711 static struct lock_class_key shadow_nodes_key; 712 713 static int __init workingset_init(void) 714 { 715 unsigned int timestamp_bits; 716 unsigned int max_order; 717 int ret; 718 719 BUILD_BUG_ON(BITS_PER_LONG < EVICTION_SHIFT); 720 /* 721 * Calculate the eviction bucket size to cover the longest 722 * actionable refault distance, which is currently half of 723 * memory (totalram_pages/2). However, memory hotplug may add 724 * some more pages at runtime, so keep working with up to 725 * double the initial memory by using totalram_pages as-is. 726 */ 727 timestamp_bits = BITS_PER_LONG - EVICTION_SHIFT; 728 max_order = fls_long(totalram_pages() - 1); 729 if (max_order > timestamp_bits) 730 bucket_order = max_order - timestamp_bits; 731 pr_info("workingset: timestamp_bits=%d max_order=%d bucket_order=%u\n", 732 timestamp_bits, max_order, bucket_order); 733 734 ret = prealloc_shrinker(&workingset_shadow_shrinker, "mm-shadow"); 735 if (ret) 736 goto err; 737 ret = __list_lru_init(&shadow_nodes, true, &shadow_nodes_key, 738 &workingset_shadow_shrinker); 739 if (ret) 740 goto err_list_lru; 741 register_shrinker_prepared(&workingset_shadow_shrinker); 742 return 0; 743 err_list_lru: 744 free_prealloced_shrinker(&workingset_shadow_shrinker); 745 err: 746 return ret; 747 } 748 module_init(workingset_init); 749