1 // SPDX-License-Identifier: GPL-2.0
5 * Copyright (C) 2013 Red Hat, Inc., Johannes Weiner
8 #include <linux/memcontrol.h>
9 #include <linux/writeback.h>
10 #include <linux/shmem_fs.h>
11 #include <linux/pagemap.h>
12 #include <linux/atomic.h>
13 #include <linux/module.h>
14 #include <linux/swap.h>
15 #include <linux/dax.h>
22 * Per node, two clock lists are maintained for file pages: the
23 * inactive and the active list. Freshly faulted pages start out at
24 * the head of the inactive list and page reclaim scans pages from the
25 * tail. Pages that are accessed multiple times on the inactive list
26 * are promoted to the active list, to protect them from reclaim,
27 * whereas active pages are demoted to the inactive list when the
28 * active list grows too big.
30 * fault ------------------------+
32 * +--------------+ | +-------------+
33 * reclaim <- | inactive | <-+-- demotion | active | <--+
34 * +--------------+ +-------------+ |
36 * +-------------- promotion ------------------+
39 * Access frequency and refault distance
41 * A workload is thrashing when its pages are frequently used but they
42 * are evicted from the inactive list every time before another access
43 * would have promoted them to the active list.
45 * In cases where the average access distance between thrashing pages
46 * is bigger than the size of memory there is nothing that can be
47 * done - the thrashing set could never fit into memory under any
50 * However, the average access distance could be bigger than the
51 * inactive list, yet smaller than the size of memory. In this case,
52 * the set could fit into memory if it weren't for the currently
53 * active pages - which may be used more, hopefully less frequently:
55 * +-memory available to cache-+
57 * +-inactive------+-active----+
58 * a b | c d e f g h i | J K L M N |
59 * +---------------+-----------+
61 * It is prohibitively expensive to accurately track access frequency
62 * of pages. But a reasonable approximation can be made to measure
63 * thrashing on the inactive list, after which refaulting pages can be
64 * activated optimistically to compete with the existing active pages.
66 * Approximating inactive page access frequency - Observations:
68 * 1. When a page is accessed for the first time, it is added to the
69 * head of the inactive list, slides every existing inactive page
70 * towards the tail by one slot, and pushes the current tail page
73 * 2. When a page is accessed for the second time, it is promoted to
74 * the active list, shrinking the inactive list by one slot. This
75 * also slides all inactive pages that were faulted into the cache
76 * more recently than the activated page towards the tail of the
81 * 1. The sum of evictions and activations between any two points in
82 * time indicate the minimum number of inactive pages accessed in
85 * 2. Moving one inactive page N page slots towards the tail of the
86 * list requires at least N inactive page accesses.
90 * 1. When a page is finally evicted from memory, the number of
91 * inactive pages accessed while the page was in cache is at least
92 * the number of page slots on the inactive list.
94 * 2. In addition, measuring the sum of evictions and activations (E)
95 * at the time of a page's eviction, and comparing it to another
96 * reading (R) at the time the page faults back into memory tells
97 * the minimum number of accesses while the page was not cached.
98 * This is called the refault distance.
100 * Because the first access of the page was the fault and the second
101 * access the refault, we combine the in-cache distance with the
102 * out-of-cache distance to get the complete minimum access distance
105 * NR_inactive + (R - E)
107 * And knowing the minimum access distance of a page, we can easily
108 * tell if the page would be able to stay in cache assuming all page
109 * slots in the cache were available:
111 * NR_inactive + (R - E) <= NR_inactive + NR_active
113 * which can be further simplified to
115 * (R - E) <= NR_active
117 * Put into words, the refault distance (out-of-cache) can be seen as
118 * a deficit in inactive list space (in-cache). If the inactive list
119 * had (R - E) more page slots, the page would not have been evicted
120 * in between accesses, but activated instead. And on a full system,
121 * the only thing eating into inactive list space is active pages.
124 * Refaulting inactive pages
126 * All that is known about the active list is that the pages have been
127 * accessed more than once in the past. This means that at any given
128 * time there is actually a good chance that pages on the active list
129 * are no longer in active use.
131 * So when a refault distance of (R - E) is observed and there are at
132 * least (R - E) active pages, the refaulting page is activated
133 * optimistically in the hope that (R - E) active pages are actually
134 * used less frequently than the refaulting page - or even not used at
137 * That means if inactive cache is refaulting with a suitable refault
138 * distance, we assume the cache workingset is transitioning and put
139 * pressure on the current active list.
141 * If this is wrong and demotion kicks in, the pages which are truly
142 * used more frequently will be reactivated while the less frequently
143 * used once will be evicted from memory.
145 * But if this is right, the stale pages will be pushed out of memory
146 * and the used pages get to stay in cache.
148 * Refaulting active pages
150 * If on the other hand the refaulting pages have recently been
151 * deactivated, it means that the active list is no longer protecting
152 * actively used cache from reclaim. The cache is NOT transitioning to
153 * a different workingset; the existing workingset is thrashing in the
154 * space allocated to the page cache.
159 * For each node's file LRU lists, a counter for inactive evictions
160 * and activations is maintained (node->inactive_age).
162 * On eviction, a snapshot of this counter (along with some bits to
163 * identify the node) is stored in the now empty page cache radix tree
164 * slot of the evicted page. This is called a shadow entry.
166 * On cache misses for which there are shadow entries, an eligible
167 * refault distance will immediately activate the refaulting page.
170 #define EVICTION_SHIFT (RADIX_TREE_EXCEPTIONAL_ENTRY + \
171 1 + NODES_SHIFT + MEM_CGROUP_ID_SHIFT)
172 #define EVICTION_MASK (~0UL >> EVICTION_SHIFT)
175 * Eviction timestamps need to be able to cover the full range of
176 * actionable refaults. However, bits are tight in the radix tree
177 * entry, and after storing the identifier for the lruvec there might
178 * not be enough left to represent every single actionable refault. In
179 * that case, we have to sacrifice granularity for distance, and group
180 * evictions into coarser buckets by shaving off lower timestamp bits.
182 static unsigned int bucket_order __read_mostly
;
184 static void *pack_shadow(int memcgid
, pg_data_t
*pgdat
, unsigned long eviction
,
187 eviction
>>= bucket_order
;
188 eviction
= (eviction
<< MEM_CGROUP_ID_SHIFT
) | memcgid
;
189 eviction
= (eviction
<< NODES_SHIFT
) | pgdat
->node_id
;
190 eviction
= (eviction
<< 1) | workingset
;
191 eviction
= (eviction
<< RADIX_TREE_EXCEPTIONAL_SHIFT
);
193 return (void *)(eviction
| RADIX_TREE_EXCEPTIONAL_ENTRY
);
196 static void unpack_shadow(void *shadow
, int *memcgidp
, pg_data_t
**pgdat
,
197 unsigned long *evictionp
, bool *workingsetp
)
199 unsigned long entry
= (unsigned long)shadow
;
203 entry
>>= RADIX_TREE_EXCEPTIONAL_SHIFT
;
204 workingset
= entry
& 1;
206 nid
= entry
& ((1UL << NODES_SHIFT
) - 1);
207 entry
>>= NODES_SHIFT
;
208 memcgid
= entry
& ((1UL << MEM_CGROUP_ID_SHIFT
) - 1);
209 entry
>>= MEM_CGROUP_ID_SHIFT
;
212 *pgdat
= NODE_DATA(nid
);
213 *evictionp
= entry
<< bucket_order
;
214 *workingsetp
= workingset
;
218 * workingset_eviction - note the eviction of a page from memory
219 * @mapping: address space the page was backing
220 * @page: the page being evicted
222 * Returns a shadow entry to be stored in @mapping->page_tree in place
223 * of the evicted @page so that a later refault can be detected.
225 void *workingset_eviction(struct address_space
*mapping
, struct page
*page
)
227 struct pglist_data
*pgdat
= page_pgdat(page
);
228 struct mem_cgroup
*memcg
= page_memcg(page
);
229 int memcgid
= mem_cgroup_id(memcg
);
230 unsigned long eviction
;
231 struct lruvec
*lruvec
;
233 /* Page is fully exclusive and pins page->mem_cgroup */
234 VM_BUG_ON_PAGE(PageLRU(page
), page
);
235 VM_BUG_ON_PAGE(page_count(page
), page
);
236 VM_BUG_ON_PAGE(!PageLocked(page
), page
);
238 lruvec
= mem_cgroup_lruvec(pgdat
, memcg
);
239 eviction
= atomic_long_inc_return(&lruvec
->inactive_age
);
240 return pack_shadow(memcgid
, pgdat
, eviction
, PageWorkingset(page
));
244 * workingset_refault - evaluate the refault of a previously evicted page
245 * @page: the freshly allocated replacement page
246 * @shadow: shadow entry of the evicted page
248 * Calculates and evaluates the refault distance of the previously
249 * evicted page in the context of the node it was allocated in.
251 void workingset_refault(struct page
*page
, void *shadow
)
253 unsigned long refault_distance
;
254 struct pglist_data
*pgdat
;
255 unsigned long active_file
;
256 struct mem_cgroup
*memcg
;
257 unsigned long eviction
;
258 struct lruvec
*lruvec
;
259 unsigned long refault
;
263 unpack_shadow(shadow
, &memcgid
, &pgdat
, &eviction
, &workingset
);
267 * Look up the memcg associated with the stored ID. It might
268 * have been deleted since the page's eviction.
270 * Note that in rare events the ID could have been recycled
271 * for a new cgroup that refaults a shared page. This is
272 * impossible to tell from the available data. However, this
273 * should be a rare and limited disturbance, and activations
274 * are always speculative anyway. Ultimately, it's the aging
275 * algorithm's job to shake out the minimum access frequency
276 * for the active cache.
278 * XXX: On !CONFIG_MEMCG, this will always return NULL; it
279 * would be better if the root_mem_cgroup existed in all
280 * configurations instead.
282 memcg
= mem_cgroup_from_id(memcgid
);
283 if (!mem_cgroup_disabled() && !memcg
)
285 lruvec
= mem_cgroup_lruvec(pgdat
, memcg
);
286 refault
= atomic_long_read(&lruvec
->inactive_age
);
287 active_file
= lruvec_lru_size(lruvec
, LRU_ACTIVE_FILE
, MAX_NR_ZONES
);
290 * Calculate the refault distance
292 * The unsigned subtraction here gives an accurate distance
293 * across inactive_age overflows in most cases. There is a
294 * special case: usually, shadow entries have a short lifetime
295 * and are either refaulted or reclaimed along with the inode
296 * before they get too old. But it is not impossible for the
297 * inactive_age to lap a shadow entry in the field, which can
298 * then result in a false small refault distance, leading to a
299 * false activation should this old entry actually refault
300 * again. However, earlier kernels used to deactivate
301 * unconditionally with *every* reclaim invocation for the
302 * longest time, so the occasional inappropriate activation
303 * leading to pressure on the active list is not a problem.
305 refault_distance
= (refault
- eviction
) & EVICTION_MASK
;
307 inc_lruvec_state(lruvec
, WORKINGSET_REFAULT
);
310 * Compare the distance to the existing workingset size. We
311 * don't act on pages that couldn't stay resident even if all
312 * the memory was available to the page cache.
314 if (refault_distance
> active_file
)
318 atomic_long_inc(&lruvec
->inactive_age
);
319 inc_lruvec_state(lruvec
, WORKINGSET_ACTIVATE
);
321 /* Page was active prior to eviction */
323 SetPageWorkingset(page
);
324 inc_lruvec_state(lruvec
, WORKINGSET_RESTORE
);
331 * workingset_activation - note a page activation
332 * @page: page that is being activated
334 void workingset_activation(struct page
*page
)
336 struct mem_cgroup
*memcg
;
337 struct lruvec
*lruvec
;
341 * Filter non-memcg pages here, e.g. unmap can call
342 * mark_page_accessed() on VDSO pages.
344 * XXX: See workingset_refault() - this should return
345 * root_mem_cgroup even for !CONFIG_MEMCG.
347 memcg
= page_memcg_rcu(page
);
348 if (!mem_cgroup_disabled() && !memcg
)
350 lruvec
= mem_cgroup_lruvec(page_pgdat(page
), memcg
);
351 atomic_long_inc(&lruvec
->inactive_age
);
357 * Shadow entries reflect the share of the working set that does not
358 * fit into memory, so their number depends on the access pattern of
359 * the workload. In most cases, they will refault or get reclaimed
360 * along with the inode, but a (malicious) workload that streams
361 * through files with a total size several times that of available
362 * memory, while preventing the inodes from being reclaimed, can
363 * create excessive amounts of shadow nodes. To keep a lid on this,
364 * track shadow nodes and reclaim them when they grow way past the
365 * point where they would still be useful.
368 static struct list_lru shadow_nodes
;
370 void workingset_update_node(struct radix_tree_node
*node
, void *private)
372 struct address_space
*mapping
= private;
374 /* Only regular page cache has shadow entries */
375 if (dax_mapping(mapping
) || shmem_mapping(mapping
))
379 * Track non-empty nodes that contain only shadow entries;
380 * unlink those that contain pages or are being freed.
382 * Avoid acquiring the list_lru lock when the nodes are
383 * already where they should be. The list_empty() test is safe
384 * as node->private_list is protected by &mapping->tree_lock.
386 if (node
->count
&& node
->count
== node
->exceptional
) {
387 if (list_empty(&node
->private_list
))
388 list_lru_add(&shadow_nodes
, &node
->private_list
);
390 if (!list_empty(&node
->private_list
))
391 list_lru_del(&shadow_nodes
, &node
->private_list
);
395 static unsigned long count_shadow_nodes(struct shrinker
*shrinker
,
396 struct shrink_control
*sc
)
398 unsigned long max_nodes
;
402 /* list_lru lock nests inside IRQ-safe mapping->tree_lock */
404 nodes
= list_lru_shrink_count(&shadow_nodes
, sc
);
408 * Approximate a reasonable limit for the radix tree nodes
409 * containing shadow entries. We don't need to keep more
410 * shadow entries than possible pages on the active list,
411 * since refault distances bigger than that are dismissed.
413 * The size of the active list converges toward 100% of
414 * overall page cache as memory grows, with only a tiny
415 * inactive list. Assume the total cache size for that.
417 * Nodes might be sparsely populated, with only one shadow
418 * entry in the extreme case. Obviously, we cannot keep one
419 * node for every eligible shadow entry, so compromise on a
420 * worst-case density of 1/8th. Below that, not all eligible
421 * refaults can be detected anymore.
423 * On 64-bit with 7 radix_tree_nodes per page and 64 slots
424 * each, this will reclaim shadow entries when they consume
425 * ~1.8% of available memory:
427 * PAGE_SIZE / radix_tree_nodes / node_entries * 8 / PAGE_SIZE
430 cache
= mem_cgroup_node_nr_lru_pages(sc
->memcg
, sc
->nid
,
433 cache
= node_page_state(NODE_DATA(sc
->nid
), NR_ACTIVE_FILE
) +
434 node_page_state(NODE_DATA(sc
->nid
), NR_INACTIVE_FILE
);
436 max_nodes
= cache
>> (RADIX_TREE_MAP_SHIFT
- 3);
438 if (nodes
<= max_nodes
)
440 return nodes
- max_nodes
;
443 static enum lru_status
shadow_lru_isolate(struct list_head
*item
,
444 struct list_lru_one
*lru
,
445 spinlock_t
*lru_lock
,
448 struct address_space
*mapping
;
449 struct radix_tree_node
*node
;
454 * Page cache insertions and deletions synchroneously maintain
455 * the shadow node LRU under the mapping->tree_lock and the
456 * lru_lock. Because the page cache tree is emptied before
457 * the inode can be destroyed, holding the lru_lock pins any
458 * address_space that has radix tree nodes on the LRU.
460 * We can then safely transition to the mapping->tree_lock to
461 * pin only the address_space of the particular node we want
462 * to reclaim, take the node off-LRU, and drop the lru_lock.
465 node
= container_of(item
, struct radix_tree_node
, private_list
);
466 mapping
= container_of(node
->root
, struct address_space
, page_tree
);
468 /* Coming from the list, invert the lock order */
469 if (!spin_trylock(&mapping
->tree_lock
)) {
470 spin_unlock(lru_lock
);
475 list_lru_isolate(lru
, item
);
476 spin_unlock(lru_lock
);
479 * The nodes should only contain one or more shadow entries,
480 * no pages, so we expect to be able to remove them all and
481 * delete and free the empty node afterwards.
483 if (WARN_ON_ONCE(!node
->exceptional
))
485 if (WARN_ON_ONCE(node
->count
!= node
->exceptional
))
487 for (i
= 0; i
< RADIX_TREE_MAP_SIZE
; i
++) {
488 if (node
->slots
[i
]) {
489 if (WARN_ON_ONCE(!radix_tree_exceptional_entry(node
->slots
[i
])))
491 if (WARN_ON_ONCE(!node
->exceptional
))
493 if (WARN_ON_ONCE(!mapping
->nrexceptional
))
495 node
->slots
[i
] = NULL
;
498 mapping
->nrexceptional
--;
501 if (WARN_ON_ONCE(node
->exceptional
))
503 inc_lruvec_page_state(virt_to_page(node
), WORKINGSET_NODERECLAIM
);
504 __radix_tree_delete_node(&mapping
->page_tree
, node
,
505 workingset_update_node
, mapping
);
508 spin_unlock(&mapping
->tree_lock
);
509 ret
= LRU_REMOVED_RETRY
;
518 static unsigned long scan_shadow_nodes(struct shrinker
*shrinker
,
519 struct shrink_control
*sc
)
523 /* list_lru lock nests inside IRQ-safe mapping->tree_lock */
525 ret
= list_lru_shrink_walk(&shadow_nodes
, sc
, shadow_lru_isolate
, NULL
);
530 static struct shrinker workingset_shadow_shrinker
= {
531 .count_objects
= count_shadow_nodes
,
532 .scan_objects
= scan_shadow_nodes
,
533 .seeks
= DEFAULT_SEEKS
,
534 .flags
= SHRINKER_NUMA_AWARE
| SHRINKER_MEMCG_AWARE
,
538 * Our list_lru->lock is IRQ-safe as it nests inside the IRQ-safe
539 * mapping->tree_lock.
541 static struct lock_class_key shadow_nodes_key
;
543 static int __init
workingset_init(void)
545 unsigned int timestamp_bits
;
546 unsigned int max_order
;
549 BUILD_BUG_ON(BITS_PER_LONG
< EVICTION_SHIFT
);
551 * Calculate the eviction bucket size to cover the longest
552 * actionable refault distance, which is currently half of
553 * memory (totalram_pages/2). However, memory hotplug may add
554 * some more pages at runtime, so keep working with up to
555 * double the initial memory by using totalram_pages as-is.
557 timestamp_bits
= BITS_PER_LONG
- EVICTION_SHIFT
;
558 max_order
= fls_long(totalram_pages
- 1);
559 if (max_order
> timestamp_bits
)
560 bucket_order
= max_order
- timestamp_bits
;
561 pr_info("workingset: timestamp_bits=%d max_order=%d bucket_order=%u\n",
562 timestamp_bits
, max_order
, bucket_order
);
564 ret
= __list_lru_init(&shadow_nodes
, true, &shadow_nodes_key
);
567 ret
= register_shrinker(&workingset_shadow_shrinker
);
572 list_lru_destroy(&shadow_nodes
);
576 module_init(workingset_init
);