1 // SPDX-License-Identifier: GPL-2.0
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
28  * whereas active pages are demoted to the inactive list when the
31  *   fault ------------------------+
33  *              +--------------+   |            +-------------+
34  *   reclaim <- |   inactive   | <-+-- demotion |    active   | <--+
35  *              +--------------+                +-------------+    |
37  *                     +-------------- promotion ------------------+
43  * are evicted from the inactive list every time before another access
48  * done - the thrashing set could never fit into memory under any
52  * inactive list, yet smaller than the size of memory.  In this case,
54  * active pages - which may be used more, hopefully less frequently:
56  *      +-memory available to cache-+
58  *      +-inactive------+-active----+
60  *      +---------------+-----------+
64  * thrashing on the inactive list, after which refaulting pages can be
67  * Approximating inactive page access frequency - Observations:
70  *    head of the inactive list, slides every existing inactive page
75  *    the active list, shrinking the inactive list by one slot.  This
76  *    also slides all inactive pages that were faulted into the cache
78  *    inactive list.
83  *    time indicate the minimum number of inactive pages accessed in
86  * 2. Moving one inactive page N page slots towards the tail of the
87  *    list requires at least N inactive page accesses.
92  *    inactive pages accessed while the page was in cache is at least
93  *    the number of page slots on the inactive list.
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)
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.
136  *		Refaulting inactive pages
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
149  * That means if inactive cache is refaulting with a suitable refault
171  * For each node's LRU lists, a counter for inactive evictions and
172  * activations is maintained (node->nonresident_age).
183 #define EVICTION_SHIFT	((BITS_PER_LONG - BITS_PER_XA_VALUE) +	\
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()
364 	 * So when the physical inactive list of a leaf cgroup ages,  in workingset_age_nonresident()
365 	 * the virtual inactive lists of all its parents, including  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
469 	 * XXX: With per-memcg flushing and thresholding, is ratelimiting  in workingset_test_recent()
475 	refault = atomic_long_read(&eviction_lruvec->nonresident_age);  in workingset_test_recent()
493 	refault_distance = (refault - eviction) & EVICTION_MASK;  in workingset_test_recent()
521  * workingset_refault - Evaluate the refault of a previously evicted folio.
580  * workingset_activation - note a page activation
589 	 * Filter non-memcg pages here, e.g. unmap can call  in workingset_activation()
592 	 * XXX: See workingset_refault() - this should return  in workingset_activation()
622 	 * Track non-empty nodes that contain only shadow entries;  in workingset_update_node()
627 	 * as node->private_list is protected by the i_pages lock.  in workingset_update_node()
629 	mapping = container_of(node->array, struct address_space, i_pages);  in workingset_update_node()
630 	lockdep_assert_held(&mapping->i_pages.xa_lock);  in workingset_update_node()
632 	if (node->count && node->count == node->nr_values) {  in workingset_update_node()
633 		if (list_empty(&node->private_list)) {  in workingset_update_node()
634 			list_lru_add_obj(&shadow_nodes, &node->private_list);  in workingset_update_node()
638 		if (!list_empty(&node->private_list)) {  in workingset_update_node()
639 			list_lru_del_obj(&shadow_nodes, &node->private_list);  in workingset_update_node()
664 	 * inactive list. Assume the total cache size for that.  in count_shadow_nodes()
669 	 * worst-case density of 1/8th. Below that, not all eligible  in count_shadow_nodes()
672 	 * On 64-bit with 7 xa_nodes per page and 64 slots  in count_shadow_nodes()
679 	if (sc->memcg) {  in count_shadow_nodes()
683 		mem_cgroup_flush_stats_ratelimited(sc->memcg);  in count_shadow_nodes()
684 		lruvec = mem_cgroup_lruvec(sc->memcg, NODE_DATA(sc->nid));  in count_shadow_nodes()
694 		pages = node_present_pages(sc->nid);  in count_shadow_nodes()
696 	max_nodes = pages >> (XA_CHUNK_SHIFT - 3);  in count_shadow_nodes()
700 	return nodes - max_nodes;  in count_shadow_nodes()
721 	 * to reclaim, take the node off-LRU, and drop the lru_lock.  in shadow_lru_isolate()
724 	mapping = container_of(node->array, struct address_space, i_pages);  in shadow_lru_isolate()
727 	if (!xa_trylock(&mapping->i_pages)) {  in shadow_lru_isolate()
734 	if (mapping->host != NULL) {  in shadow_lru_isolate()
735 		if (!spin_trylock(&mapping->host->i_lock)) {  in shadow_lru_isolate()
736 			xa_unlock(&mapping->i_pages);  in shadow_lru_isolate()
753 	if (WARN_ON_ONCE(!node->nr_values))  in shadow_lru_isolate()
755 	if (WARN_ON_ONCE(node->count != node->nr_values))  in shadow_lru_isolate()
761 	xa_unlock_irq(&mapping->i_pages);  in shadow_lru_isolate()
762 	if (mapping->host != NULL) {  in shadow_lru_isolate()
764 			inode_add_lru(mapping->host);  in shadow_lru_isolate()
765 		spin_unlock(&mapping->host->i_lock);  in shadow_lru_isolate()
777 	/* list_lru lock nests inside the IRQ-safe i_pages lock */  in scan_shadow_nodes()
783  * Our list_lru->lock is IRQ-safe as it nests inside the IRQ-safe
793 	int ret = -ENOMEM;  in workingset_init()
801 	 * double the initial memory by using totalram_pages as-is.  in workingset_init()
803 	timestamp_bits = BITS_PER_LONG - EVICTION_SHIFT;  in workingset_init()
804 	max_order = fls_long(totalram_pages() - 1);  in workingset_init()
806 		bucket_order = max_order - timestamp_bits;  in workingset_init()
812 						    "mm-shadow");  in workingset_init()
821 	workingset_shadow_shrinker->count_objects = count_shadow_nodes;  in workingset_init()
822 	workingset_shadow_shrinker->scan_objects = scan_shadow_nodes;  in workingset_init()
823 	/* ->count reports only fully expendable nodes */  in workingset_init()
824 	workingset_shadow_shrinker->seeks = 0;  in workingset_init()