1 // SPDX-License-Identifier: GPL-2.0
25  * inactive and the active list.  Freshly faulted pages start out at
28  * are promoted to the active list, to protect them from reclaim,
29  * whereas active pages are demoted to the inactive list when the
30  * active list grows too big.
32  *   fault ------------------------+
34  *              +--------------+   |            +-------------+
35  *   reclaim <- |   inactive   | <-+-- demotion |    active   | <--+
36  *              +--------------+                +-------------+    |
38  *                     +-------------- promotion ------------------+
45  * would have promoted them to the active list.
49  * done - the thrashing set could never fit into memory under any
55  * active pages - which may be used more, hopefully less frequently:
57  *      +-memory available to cache-+
59  *      +-inactive------+-active----+
61  *      +---------------+-----------+
66  * activated optimistically to compete with the existing active pages.
68  * Approximating inactive page access frequency - Observations:
76  *    the active list, shrinking the inactive list by one slot.  This
103  * access the refault, we combine the in-cache distance with the
104  * out-of-cache distance to get the complete minimum access distance
107  *      NR_inactive + (R - E)
113  *   NR_inactive + (R - E) <= NR_inactive + NR_active
118  *   NR_inactive_file + (R - E) <= NR_inactive_file + NR_active_file
121  *   NR_inactive_anon + (R - E) <= NR_inactive_anon + NR_active_anon
126  *   (R - E) <= NR_active_file + NR_inactive_anon + NR_active_anon
128  *   (R - E) <= NR_active_anon + NR_inactive_file + NR_active_file
130  * Put into words, the refault distance (out-of-cache) can be seen as
131  * a deficit in inactive list space (in-cache).  If the inactive list
132  * had (R - E) more page slots, the page would not have been evicted
134  * the only thing eating into inactive list space is active pages.
139  * All that is known about the active list is that the pages have been
141  * time there is actually a good chance that pages on the active list
142  * are no longer in active use.
144  * So when a refault distance of (R - E) is observed and there are at
145  * least (R - E) pages in the userspace workingset, the refaulting page
146  * is activated optimistically in the hope that (R - E) pages are actually
147  * used less frequently than the refaulting page - or even not used at
161  *		Refaulting active pages
164  * deactivated, it means that the active list is no longer protecting
173  * activations is maintained (node->nonresident_age).
184 #define EVICTION_SHIFT	((BITS_PER_LONG - BITS_PER_XA_VALUE) +	\
204 	eviction = (eviction << NODES_SHIFT) | pgdat->node_id;  in pack_shadow()
217 	workingset = entry & ((1UL << WORKINGSET_SHIFT) - 1);  in unpack_shadow()
219 	nid = entry & ((1UL << NODES_SHIFT) - 1);  in unpack_shadow()
221 	memcgid = entry & ((1UL << MEM_CGROUP_ID_SHIFT) - 1);  in unpack_shadow()
247 	BUILD_BUG_ON(LRU_GEN_WIDTH + LRU_REFS_WIDTH > BITS_PER_LONG - EVICTION_SHIFT);  in lru_gen_eviction()
250 	lrugen = &lruvec->lrugen;  in lru_gen_eviction()
251 	min_seq = READ_ONCE(lrugen->min_seq[type]);  in lru_gen_eviction()
252 	token = (min_seq << LRU_REFS_WIDTH) | max(refs - 1, 0);  in lru_gen_eviction()
255 	atomic_long_add(delta, &lrugen->evicted[hist][type][tier]);  in lru_gen_eviction()
277 	max_seq = READ_ONCE((*lruvec)->lrugen.max_seq);  in lru_gen_test_recent()
305 	lrugen = &lruvec->lrugen;  in lru_gen_refault()
307 	hist = lru_hist_from_seq(READ_ONCE(lrugen->min_seq[type]));  in lru_gen_refault()
308 	refs = (token & (BIT(LRU_REFS_WIDTH) - 1)) + 1;  in lru_gen_refault()
311 	atomic_long_add(delta, &lrugen->refaulted[hist][type][tier]);  in lru_gen_refault()
321 		set_mask_bits(&folio->flags, LRU_REFS_MASK, (refs - 1UL) << LRU_REFS_PGOFF);  in lru_gen_refault()
346  * workingset_age_nonresident - age non-resident entries as LRU ages
350  * As in-memory pages are aged, non-resident pages need to be aged as
352  * to the in-memory dimensions. This function allows reclaim and LRU
353  * operations to drive the non-resident aging along in parallel.
359 	 * round-robin fashion. That means that each cgroup has an LRU  in workingset_age_nonresident()
369 		atomic_long_add(nr_pages, &lruvec->nonresident_age);  in workingset_age_nonresident()
374  * workingset_eviction - note the eviction of a folio from memory
378  * Return: a shadow entry to be stored in @folio->mapping->i_pages in place
399 	eviction = atomic_long_read(&lruvec->nonresident_age);  in workingset_eviction()
407  * workingset_test_recent - tests if the shadow entry is for a folio that was
453 	 * for the active cache.  in workingset_test_recent()
470 	 * section (for e.g, in cachestat) - these callers need to skip flushing  in workingset_test_recent()
473 	 * XXX: With per-memcg flushing and thresholding, is ratelimiting  in workingset_test_recent()
480 	refault = atomic_long_read(&eviction_lruvec->nonresident_age);  in workingset_test_recent()
496 	 * leading to pressure on the active list is not a problem.  in workingset_test_recent()
498 	refault_distance = (refault - eviction) & EVICTION_MASK;  in workingset_test_recent()
526  * workingset_refault - Evaluate the refault of a previously evicted folio.
573 	/* Folio was active prior to eviction */  in workingset_refault()
586  * workingset_activation - note a page activation
592 	 * Filter non-memcg pages here, e.g. unmap can call  in workingset_activation()
619 	 * Track non-empty nodes that contain only shadow entries;  in workingset_update_node()
624 	 * as node->private_list is protected by the i_pages lock.  in workingset_update_node()
626 	mapping = container_of(node->array, struct address_space, i_pages);  in workingset_update_node()
627 	lockdep_assert_held(&mapping->i_pages.xa_lock);  in workingset_update_node()
629 	if (node->count && node->count == node->nr_values) {  in workingset_update_node()
630 		if (list_empty(&node->private_list)) {  in workingset_update_node()
631 			list_lru_add_obj(&shadow_nodes, &node->private_list);  in workingset_update_node()
635 		if (!list_empty(&node->private_list)) {  in workingset_update_node()
636 			list_lru_del_obj(&shadow_nodes, &node->private_list);  in workingset_update_node()
656 	 * shadow entries than possible pages on the active list,  in count_shadow_nodes()
659 	 * The size of the active list converges toward 100% of  in count_shadow_nodes()
666 	 * worst-case density of 1/8th. Below that, not all eligible  in count_shadow_nodes()
669 	 * On 64-bit with 7 xa_nodes per page and 64 slots  in count_shadow_nodes()
676 	if (sc->memcg) {  in count_shadow_nodes()
680 		mem_cgroup_flush_stats_ratelimited(sc->memcg);  in count_shadow_nodes()
681 		lruvec = mem_cgroup_lruvec(sc->memcg, NODE_DATA(sc->nid));  in count_shadow_nodes()
691 		pages = node_present_pages(sc->nid);  in count_shadow_nodes()
693 	max_nodes = pages >> (XA_CHUNK_SHIFT - 3);  in count_shadow_nodes()
697 	return nodes - max_nodes;  in count_shadow_nodes()
702 					  void *arg) __must_hold(lru->lock)  in shadow_lru_isolate()
711 	 * &lru->lock. Because the page cache tree is emptied before  in shadow_lru_isolate()
712 	 * the inode can be destroyed, holding the &lru->lock pins any  in shadow_lru_isolate()
717 	 * to reclaim, take the node off-LRU, and drop the &lru->lock.  in shadow_lru_isolate()
720 	mapping = container_of(node->array, struct address_space, i_pages);  in shadow_lru_isolate()
723 	if (!xa_trylock(&mapping->i_pages)) {  in shadow_lru_isolate()
724 		spin_unlock_irq(&lru->lock);  in shadow_lru_isolate()
730 	if (mapping->host != NULL) {  in shadow_lru_isolate()
731 		if (!spin_trylock(&mapping->host->i_lock)) {  in shadow_lru_isolate()
732 			xa_unlock(&mapping->i_pages);  in shadow_lru_isolate()
733 			spin_unlock_irq(&lru->lock);  in shadow_lru_isolate()
742 	spin_unlock(&lru->lock);  in shadow_lru_isolate()
749 	if (WARN_ON_ONCE(!node->nr_values))  in shadow_lru_isolate()
751 	if (WARN_ON_ONCE(node->count != node->nr_values))  in shadow_lru_isolate()
757 	xa_unlock_irq(&mapping->i_pages);  in shadow_lru_isolate()
758 	if (mapping->host != NULL) {  in shadow_lru_isolate()
760 			inode_add_lru(mapping->host);  in shadow_lru_isolate()
761 		spin_unlock(&mapping->host->i_lock);  in shadow_lru_isolate()
772 	/* list_lru lock nests inside the IRQ-safe i_pages lock */  in scan_shadow_nodes()
778  * Our list_lru->lock is IRQ-safe as it nests inside the IRQ-safe
788 	int ret = -ENOMEM;  in workingset_init()
796 	 * double the initial memory by using totalram_pages as-is.  in workingset_init()
798 	timestamp_bits = BITS_PER_LONG - EVICTION_SHIFT;  in workingset_init()
799 	max_order = fls_long(totalram_pages() - 1);  in workingset_init()
801 		bucket_order = max_order - timestamp_bits;  in workingset_init()
807 						    "mm-shadow");  in workingset_init()
816 	workingset_shadow_shrinker->count_objects = count_shadow_nodes;  in workingset_init()
817 	workingset_shadow_shrinker->scan_objects = scan_shadow_nodes;  in workingset_init()
818 	/* ->count reports only fully expendable nodes */  in workingset_init()
819 	workingset_shadow_shrinker->seeks = 0;  in workingset_init()