1 // SPDX-License-Identifier: GPL-2.0
24  * inactive and the active list.  Freshly faulted pages start out at
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.
31  *   fault ------------------------+
33  *              +--------------+   |            +-------------+
34  *   reclaim <- |   inactive   | <-+-- demotion |    active   | <--+
35  *              +--------------+                +-------------+    |
37  *                     +-------------- promotion ------------------+
40  *		Access frequency and refault distance
44  * would have promoted them to the active list.
46  * In cases where the average access distance between thrashing pages
48  * done - the thrashing set could never fit into memory under any
51  * However, the average access distance could be bigger than the
54  * active pages - which may be used more, hopefully less frequently:
56  *      +-memory available to cache-+
58  *      +-inactive------+-active----+
60  *      +---------------+-----------+
65  * activated optimistically to compete with the existing active pages.
67  * Approximating inactive page access frequency - Observations:
75  *    the active list, shrinking the inactive list by one slot.  This
99  *    This is called the refault distance.
102  * access the refault, we combine the in-cache distance with the
103  * out-of-cache distance to get the complete minimum access distance
106  *      NR_inactive + (R - E)
108  * And knowing the minimum access distance of a page, we can easily
112  *   NR_inactive + (R - E) <= NR_inactive + NR_active
117  *   NR_inactive_file + (R - E) <= NR_inactive_file + NR_active_file
120  *   NR_inactive_anon + (R - E) <= NR_inactive_anon + NR_active_anon
125  *   (R - E) <= NR_active_file + NR_inactive_anon + NR_active_anon
127  *   (R - E) <= NR_active_anon + NR_inactive_file + NR_active_file
129  * Put into words, the refault distance (out-of-cache) can be seen as
130  * a deficit in inactive list space (in-cache).  If the inactive list
131  * had (R - E) more page slots, the page would not have been evicted
133  * the only thing eating into inactive list space is active pages.
138  * All that is known about the active list is that the pages have been
140  * time there is actually a good chance that pages on the active list
141  * are no longer in active use.
143  * So when a refault distance of (R - E) is observed and there are at
144  * least (R - E) pages in the userspace workingset, the refaulting page
145  * is activated optimistically in the hope that (R - E) pages are actually
146  * used less frequently than the refaulting page - or even not used at
150  * distance, we assume the cache workingset is transitioning and put
160  *		Refaulting active pages
163  * deactivated, it means that the active list is no longer protecting
172  * activations is maintained (node->nonresident_age).
179  * refault distance will immediately activate the refaulting page.
183 #define EVICTION_SHIFT	((BITS_PER_LONG - BITS_PER_XA_VALUE) +	\
193  * that case, we have to sacrifice granularity for distance, and group
203 	eviction = (eviction << NODES_SHIFT) | pgdat->node_id;  in pack_shadow()
216 	workingset = entry & ((1UL << WORKINGSET_SHIFT) - 1);  in unpack_shadow()
218 	nid = entry & ((1UL << NODES_SHIFT) - 1);  in unpack_shadow()
220 	memcgid = entry & ((1UL << MEM_CGROUP_ID_SHIFT) - 1);  in unpack_shadow()
245 	BUILD_BUG_ON(LRU_GEN_WIDTH + LRU_REFS_WIDTH > BITS_PER_LONG - EVICTION_SHIFT);  in lru_gen_eviction()
248 	lrugen = &lruvec->lrugen;  in lru_gen_eviction()
249 	min_seq = READ_ONCE(lrugen->min_seq[type]);  in lru_gen_eviction()
250 	token = (min_seq << LRU_REFS_WIDTH) | max(refs - 1, 0);  in lru_gen_eviction()
253 	atomic_long_add(delta, &lrugen->evicted[hist][type][tier]);  in lru_gen_eviction()
275 	min_seq = READ_ONCE((*lruvec)->lrugen.min_seq[file]);  in lru_gen_test_recent()
301 	lrugen = &lruvec->lrugen;  in lru_gen_refault()
303 	hist = lru_hist_from_seq(READ_ONCE(lrugen->min_seq[type]));  in lru_gen_refault()
305 	refs = (token & (BIT(LRU_REFS_WIDTH) - 1)) + workingset;  in lru_gen_refault()
308 	atomic_long_add(delta, &lrugen->refaulted[hist][type][tier]);  in lru_gen_refault()
318 	if (lru_gen_in_fault() || refs >= BIT(LRU_REFS_WIDTH) - 1) {  in lru_gen_refault()
319 		set_mask_bits(&folio->flags, 0, LRU_REFS_MASK | BIT(PG_workingset));  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()
416  * workingset_test_recent - tests if the shadow entry is for a folio that was
453 	 * for the active cache.  in workingset_test_recent()
460 	if (memcgid != -1) {  in workingset_test_recent()
472 	refault = atomic_long_read(&eviction_lruvec->nonresident_age);  in workingset_test_recent()
475 	 * Calculate the refault distance  in workingset_test_recent()
477 	 * The unsigned subtraction here gives an accurate distance  in workingset_test_recent()
483 	 * can then result in a false small refault distance, leading  in workingset_test_recent()
488 	 * leading to pressure on the active list is not a problem.  in workingset_test_recent()
490 	refault_distance = (refault - eviction) & EVICTION_MASK;  in workingset_test_recent()
493 	 * Compare the distance to the existing workingset size. We  in workingset_test_recent()
528  * workingset_refault - Evaluate the refault of a previously evicted folio.
532  * Calculates and evaluates the refault distance of the previously
596 	/* Folio was active prior to eviction */  in workingset_refault()
618  * workingset_activation - note a page activation
628 	 * Filter non-memcg pages here, e.g. unmap can call  in workingset_activation()
631 	 * XXX: See workingset_refault() - this should return  in workingset_activation()
670 	 * Track non-empty nodes that contain only shadow entries;  in workingset_update_node()
675 	 * as node->private_list is protected by the i_pages lock.  in workingset_update_node()
677 	mapping = container_of(node->array, struct address_space, i_pages);  in workingset_update_node()
678 	lockdep_assert_held(&mapping->i_pages.xa_lock);  in workingset_update_node()
680 	if (node->count && node->count == node->nr_values) {  in workingset_update_node()
681 		if (list_empty(&node->private_list)) {  in workingset_update_node()
682 			list_lru_add(&shadow_nodes, &node->private_list);  in workingset_update_node()
686 		if (!list_empty(&node->private_list)) {  in workingset_update_node()
687 			list_lru_del(&shadow_nodes, &node->private_list);  in workingset_update_node()
707 	 * shadow entries than possible pages on the active list,  in count_shadow_nodes()
710 	 * The size of the active list converges toward 100% of  in count_shadow_nodes()
717 	 * worst-case density of 1/8th. Below that, not all eligible  in count_shadow_nodes()
720 	 * On 64-bit with 7 xa_nodes per page and 64 slots  in count_shadow_nodes()
728 	if (sc->memcg) {  in count_shadow_nodes()
733 		lruvec = mem_cgroup_lruvec(sc->memcg, NODE_DATA(sc->nid));  in count_shadow_nodes()
744 		pages = node_present_pages(sc->nid);  in count_shadow_nodes()
746 	max_nodes = pages >> (XA_CHUNK_SHIFT - 3);  in count_shadow_nodes()
750 	return nodes - max_nodes;  in count_shadow_nodes()
771 	 * to reclaim, take the node off-LRU, and drop the lru_lock.  in shadow_lru_isolate()
774 	mapping = container_of(node->array, struct address_space, i_pages);  in shadow_lru_isolate()
777 	if (!xa_trylock(&mapping->i_pages)) {  in shadow_lru_isolate()
784 	if (mapping->host != NULL) {  in shadow_lru_isolate()
785 		if (!spin_trylock(&mapping->host->i_lock)) {  in shadow_lru_isolate()
786 			xa_unlock(&mapping->i_pages);  in shadow_lru_isolate()
803 	if (WARN_ON_ONCE(!node->nr_values))  in shadow_lru_isolate()
805 	if (WARN_ON_ONCE(node->count != node->nr_values))  in shadow_lru_isolate()
811 	xa_unlock_irq(&mapping->i_pages);  in shadow_lru_isolate()
812 	if (mapping->host != NULL) {  in shadow_lru_isolate()
814 			inode_add_lru(mapping->host);  in shadow_lru_isolate()
815 		spin_unlock(&mapping->host->i_lock);  in shadow_lru_isolate()
827 	/* list_lru lock nests inside the IRQ-safe i_pages lock */  in scan_shadow_nodes()
835 	.seeks = 0, /* ->count reports only fully expendable nodes */
840  * Our list_lru->lock is IRQ-safe as it nests inside the IRQ-safe
854 	 * actionable refault distance, which is currently half of  in workingset_init()
857 	 * double the initial memory by using totalram_pages as-is.  in workingset_init()
859 	timestamp_bits = BITS_PER_LONG - EVICTION_SHIFT;  in workingset_init()
860 	max_order = fls_long(totalram_pages() - 1);  in workingset_init()
862 		bucket_order = max_order - timestamp_bits;  in workingset_init()
866 	ret = prealloc_shrinker(&workingset_shadow_shrinker, "mm-shadow");  in workingset_init()