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
116  *   (R - E) <= NR_active
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
122  * the only thing eating into inactive list space is active pages.
127  * All that is known about the active list is that the pages have been
129  * time there is actually a good chance that pages on the active list
130  * are no longer in active use.
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
139  * distance, we assume the cache workingset is transitioning and put
140  * pressure on the current active list.
149  *		Refaulting active pages
152  * deactivated, it means that the active list is no longer protecting
161  * activations is maintained (node->nonresident_age).
168  * refault distance will immediately activate the refaulting page.
171 #define EVICTION_SHIFT	((BITS_PER_LONG - BITS_PER_XA_VALUE) +	\
180  * that case, we have to sacrifice granularity for distance, and group
191 	eviction = (eviction << NODES_SHIFT) | pgdat->node_id;  in pack_shadow()
206 	nid = entry & ((1UL << NODES_SHIFT) - 1);  in unpack_shadow()
208 	memcgid = entry & ((1UL << MEM_CGROUP_ID_SHIFT) - 1);  in unpack_shadow()
218  * workingset_age_nonresident - age non-resident entries as LRU ages
222  * As in-memory pages are aged, non-resident pages need to be aged as
224  * to the in-memory dimensions. This function allows reclaim and LRU
225  * operations to drive the non-resident aging along in parallel.
231 	 * round-robin fashion. That means that each cgroup has an LRU  in workingset_age_nonresident()
241 		atomic_long_add(nr_pages, &lruvec->nonresident_age);  in workingset_age_nonresident()
246  * workingset_eviction - note the eviction of a page from memory
250  * Returns a shadow entry to be stored in @page->mapping->i_pages in place
260 	/* Page is fully exclusive and pins page->mem_cgroup */  in workingset_eviction()
278 	eviction = atomic_long_read(&lruvec->nonresident_age);  in workingset_eviction()
283  * workingset_refault - evaluate the refault of a previously evicted page
287  * Calculates and evaluates the refault distance of the previously
319 	 * for the active cache.  in workingset_refault()
326 	if (memcgid != -1) {  in workingset_refault()
337 	refault = atomic_long_read(&eviction_lruvec->nonresident_age);  in workingset_refault()
340 	 * Calculate the refault distance  in workingset_refault()
342 	 * The unsigned subtraction here gives an accurate distance  in workingset_refault()
348 	 * can then result in a false small refault distance, leading  in workingset_refault()
353 	 * leading to pressure on the active list is not a problem.  in workingset_refault()
355 	refault_distance = (refault - eviction) & EVICTION_MASK;  in workingset_refault()
378 	 * Compare the distance to the existing workingset size. We  in workingset_refault()
426 	/* Page was active prior to eviction */  in workingset_refault()
430 		spin_lock_irq(&page_pgdat(page)->lru_lock);  in workingset_refault()
432 		spin_unlock_irq(&page_pgdat(page)->lru_lock);  in workingset_refault()
447  * workingset_activation - note a page activation
457 	 * Filter non-memcg pages here, e.g. unmap can call  in workingset_activation()
460 	 * XXX: See workingset_refault() - this should return  in workingset_activation()
498 	 * Track non-empty nodes that contain only shadow entries;  in workingset_update_node()
503 	 * as node->private_list is protected by the i_pages lock.  in workingset_update_node()
507 	if (node->count && node->count == node->nr_values) {  in workingset_update_node()
508 		if (list_empty(&node->private_list)) {  in workingset_update_node()
509 			list_lru_add(&shadow_nodes, &node->private_list);  in workingset_update_node()
513 		if (!list_empty(&node->private_list)) {  in workingset_update_node()
514 			list_lru_del(&shadow_nodes, &node->private_list);  in workingset_update_node()
532 	 * shadow entries than possible pages on the active list,  in count_shadow_nodes()
535 	 * The size of the active list converges toward 100% of  in count_shadow_nodes()
542 	 * worst-case density of 1/8th. Below that, not all eligible  in count_shadow_nodes()
545 	 * On 64-bit with 7 xa_nodes per page and 64 slots  in count_shadow_nodes()
553 	if (sc->memcg) {  in count_shadow_nodes()
557 		lruvec = mem_cgroup_lruvec(sc->memcg, NODE_DATA(sc->nid));  in count_shadow_nodes()
568 		pages = node_present_pages(sc->nid);  in count_shadow_nodes()
570 	max_nodes = pages >> (XA_CHUNK_SHIFT - 3);  in count_shadow_nodes()
577 	return nodes - max_nodes;  in count_shadow_nodes()
598 	 * to reclaim, take the node off-LRU, and drop the lru_lock.  in shadow_lru_isolate()
601 	mapping = container_of(node->array, struct address_space, i_pages);  in shadow_lru_isolate()
604 	if (!xa_trylock(&mapping->i_pages)) {  in shadow_lru_isolate()
620 	if (WARN_ON_ONCE(!node->nr_values))  in shadow_lru_isolate()
622 	if (WARN_ON_ONCE(node->count != node->nr_values))  in shadow_lru_isolate()
624 	mapping->nrexceptional -= node->nr_values;  in shadow_lru_isolate()
629 	xa_unlock_irq(&mapping->i_pages);  in shadow_lru_isolate()
640 	/* list_lru lock nests inside the IRQ-safe i_pages lock */  in scan_shadow_nodes()
648 	.seeks = 0, /* ->count reports only fully expendable nodes */
653  * Our list_lru->lock is IRQ-safe as it nests inside the IRQ-safe
667 	 * actionable refault distance, which is currently half of  in workingset_init()
670 	 * double the initial memory by using totalram_pages as-is.  in workingset_init()
672 	timestamp_bits = BITS_PER_LONG - EVICTION_SHIFT;  in workingset_init()
673 	max_order = fls_long(totalram_pages() - 1);  in workingset_init()
675 		bucket_order = max_order - timestamp_bits;  in workingset_init()