workingset.c 18.1 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
2 3 4 5 6 7 8 9
/*
 * Workingset detection
 *
 * Copyright (C) 2013 Red Hat, Inc., Johannes Weiner
 */

#include <linux/memcontrol.h>
#include <linux/writeback.h>
10
#include <linux/shmem_fs.h>
11 12 13 14
#include <linux/pagemap.h>
#include <linux/atomic.h>
#include <linux/module.h>
#include <linux/swap.h>
15
#include <linux/dax.h>
16 17 18 19 20 21
#include <linux/fs.h>
#include <linux/mm.h>

/*
 *		Double CLOCK lists
 *
22
 * Per node, two clock lists are maintained for file pages: the
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
 * inactive and the active list.  Freshly faulted pages start out at
 * the head of the inactive list and page reclaim scans pages from the
 * tail.  Pages that are accessed multiple times on the inactive list
 * are promoted to the active list, to protect them from reclaim,
 * whereas active pages are demoted to the inactive list when the
 * active list grows too big.
 *
 *   fault ------------------------+
 *                                 |
 *              +--------------+   |            +-------------+
 *   reclaim <- |   inactive   | <-+-- demotion |    active   | <--+
 *              +--------------+                +-------------+    |
 *                     |                                           |
 *                     +-------------- promotion ------------------+
 *
 *
 *		Access frequency and refault distance
 *
 * A workload is thrashing when its pages are frequently used but they
 * are evicted from the inactive list every time before another access
 * would have promoted them to the active list.
 *
 * In cases where the average access distance between thrashing pages
 * is bigger than the size of memory there is nothing that can be
 * done - the thrashing set could never fit into memory under any
 * circumstance.
 *
 * However, the average access distance could be bigger than the
 * inactive list, yet smaller than the size of memory.  In this case,
 * the set could fit into memory if it weren't for the currently
 * active pages - which may be used more, hopefully less frequently:
 *
 *      +-memory available to cache-+
 *      |                           |
 *      +-inactive------+-active----+
 *  a b | c d e f g h i | J K L M N |
 *      +---------------+-----------+
 *
 * It is prohibitively expensive to accurately track access frequency
 * of pages.  But a reasonable approximation can be made to measure
 * thrashing on the inactive list, after which refaulting pages can be
 * activated optimistically to compete with the existing active pages.
 *
 * Approximating inactive page access frequency - Observations:
 *
 * 1. When a page is accessed for the first time, it is added to the
 *    head of the inactive list, slides every existing inactive page
 *    towards the tail by one slot, and pushes the current tail page
 *    out of memory.
 *
 * 2. When a page is accessed for the second time, it is promoted to
 *    the active list, shrinking the inactive list by one slot.  This
 *    also slides all inactive pages that were faulted into the cache
 *    more recently than the activated page towards the tail of the
 *    inactive list.
 *
 * Thus:
 *
 * 1. The sum of evictions and activations between any two points in
 *    time indicate the minimum number of inactive pages accessed in
 *    between.
 *
 * 2. Moving one inactive page N page slots towards the tail of the
 *    list requires at least N inactive page accesses.
 *
 * Combining these:
 *
 * 1. When a page is finally evicted from memory, the number of
 *    inactive pages accessed while the page was in cache is at least
 *    the number of page slots on the inactive list.
 *
 * 2. In addition, measuring the sum of evictions and activations (E)
 *    at the time of a page's eviction, and comparing it to another
 *    reading (R) at the time the page faults back into memory tells
 *    the minimum number of accesses while the page was not cached.
 *    This is called the refault distance.
 *
 * Because the first access of the page was the fault and the second
 * access the refault, we combine the in-cache distance with the
 * out-of-cache distance to get the complete minimum access distance
 * of this page:
 *
 *      NR_inactive + (R - E)
 *
 * And knowing the minimum access distance of a page, we can easily
 * tell if the page would be able to stay in cache assuming all page
 * slots in the cache were available:
 *
 *   NR_inactive + (R - E) <= NR_inactive + NR_active
 *
 * which can be further simplified to
 *
 *   (R - E) <= NR_active
 *
 * Put into words, the refault distance (out-of-cache) can be seen as
 * a deficit in inactive list space (in-cache).  If the inactive list
 * had (R - E) more page slots, the page would not have been evicted
 * in between accesses, but activated instead.  And on a full system,
 * the only thing eating into inactive list space is active pages.
 *
 *
 *		Activating refaulting pages
 *
 * All that is known about the active list is that the pages have been
 * accessed more than once in the past.  This means that at any given
 * time there is actually a good chance that pages on the active list
 * are no longer in active use.
 *
 * So when a refault distance of (R - E) is observed and there are at
 * least (R - E) active pages, the refaulting page is activated
 * optimistically in the hope that (R - E) active pages are actually
 * used less frequently than the refaulting page - or even not used at
 * all anymore.
 *
 * If this is wrong and demotion kicks in, the pages which are truly
 * used more frequently will be reactivated while the less frequently
 * used once will be evicted from memory.
 *
 * But if this is right, the stale pages will be pushed out of memory
 * and the used pages get to stay in cache.
 *
 *
 *		Implementation
 *
147 148
 * For each node's file LRU lists, a counter for inactive evictions
 * and activations is maintained (node->inactive_age).
149 150
 *
 * On eviction, a snapshot of this counter (along with some bits to
151
 * identify the node) is stored in the now empty page cache radix tree
152 153 154 155 156 157
 * slot of the evicted page.  This is called a shadow entry.
 *
 * On cache misses for which there are shadow entries, an eligible
 * refault distance will immediately activate the refaulting page.
 */

158
#define EVICTION_SHIFT	(RADIX_TREE_EXCEPTIONAL_ENTRY + \
159
			 NODES_SHIFT +	\
160
			 MEM_CGROUP_ID_SHIFT)
161 162
#define EVICTION_MASK	(~0UL >> EVICTION_SHIFT)

163 164 165 166 167 168 169 170 171 172
/*
 * Eviction timestamps need to be able to cover the full range of
 * actionable refaults. However, bits are tight in the radix tree
 * entry, and after storing the identifier for the lruvec there might
 * not be enough left to represent every single actionable refault. In
 * that case, we have to sacrifice granularity for distance, and group
 * evictions into coarser buckets by shaving off lower timestamp bits.
 */
static unsigned int bucket_order __read_mostly;

173
static void *pack_shadow(int memcgid, pg_data_t *pgdat, unsigned long eviction)
174
{
175
	eviction >>= bucket_order;
176
	eviction = (eviction << MEM_CGROUP_ID_SHIFT) | memcgid;
177
	eviction = (eviction << NODES_SHIFT) | pgdat->node_id;
178 179 180 181 182
	eviction = (eviction << RADIX_TREE_EXCEPTIONAL_SHIFT);

	return (void *)(eviction | RADIX_TREE_EXCEPTIONAL_ENTRY);
}

183
static void unpack_shadow(void *shadow, int *memcgidp, pg_data_t **pgdat,
184
			  unsigned long *evictionp)
185 186
{
	unsigned long entry = (unsigned long)shadow;
187
	int memcgid, nid;
188 189 190 191

	entry >>= RADIX_TREE_EXCEPTIONAL_SHIFT;
	nid = entry & ((1UL << NODES_SHIFT) - 1);
	entry >>= NODES_SHIFT;
192 193
	memcgid = entry & ((1UL << MEM_CGROUP_ID_SHIFT) - 1);
	entry >>= MEM_CGROUP_ID_SHIFT;
194

195
	*memcgidp = memcgid;
196
	*pgdat = NODE_DATA(nid);
197
	*evictionp = entry << bucket_order;
198 199 200 201 202 203 204
}

/**
 * workingset_eviction - note the eviction of a page from memory
 * @mapping: address space the page was backing
 * @page: the page being evicted
 *
Matthew Wilcox's avatar
Matthew Wilcox committed
205
 * Returns a shadow entry to be stored in @mapping->i_pages in place
206 207 208 209
 * of the evicted @page so that a later refault can be detected.
 */
void *workingset_eviction(struct address_space *mapping, struct page *page)
{
210
	struct mem_cgroup *memcg = page_memcg(page);
211
	struct pglist_data *pgdat = page_pgdat(page);
212
	int memcgid = mem_cgroup_id(memcg);
213
	unsigned long eviction;
214
	struct lruvec *lruvec;
215

216 217 218 219 220
	/* Page is fully exclusive and pins page->mem_cgroup */
	VM_BUG_ON_PAGE(PageLRU(page), page);
	VM_BUG_ON_PAGE(page_count(page), page);
	VM_BUG_ON_PAGE(!PageLocked(page), page);

221
	lruvec = mem_cgroup_lruvec(pgdat, memcg);
222
	eviction = atomic_long_inc_return(&lruvec->inactive_age);
223
	return pack_shadow(memcgid, pgdat, eviction);
224 225 226 227 228 229 230
}

/**
 * workingset_refault - evaluate the refault of a previously evicted page
 * @shadow: shadow entry of the evicted page
 *
 * Calculates and evaluates the refault distance of the previously
231
 * evicted page in the context of the node it was allocated in.
232 233 234 235 236 237
 *
 * Returns %true if the page should be activated, %false otherwise.
 */
bool workingset_refault(void *shadow)
{
	unsigned long refault_distance;
238 239
	unsigned long active_file;
	struct mem_cgroup *memcg;
240
	unsigned long eviction;
241
	struct lruvec *lruvec;
242
	unsigned long refault;
243
	struct pglist_data *pgdat;
244
	int memcgid;
245

246
	unpack_shadow(shadow, &memcgid, &pgdat, &eviction);
247

248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
	rcu_read_lock();
	/*
	 * Look up the memcg associated with the stored ID. It might
	 * have been deleted since the page's eviction.
	 *
	 * Note that in rare events the ID could have been recycled
	 * for a new cgroup that refaults a shared page. This is
	 * impossible to tell from the available data. However, this
	 * should be a rare and limited disturbance, and activations
	 * are always speculative anyway. Ultimately, it's the aging
	 * algorithm's job to shake out the minimum access frequency
	 * for the active cache.
	 *
	 * XXX: On !CONFIG_MEMCG, this will always return NULL; it
	 * would be better if the root_mem_cgroup existed in all
	 * configurations instead.
	 */
	memcg = mem_cgroup_from_id(memcgid);
	if (!mem_cgroup_disabled() && !memcg) {
		rcu_read_unlock();
		return false;
	}
270
	lruvec = mem_cgroup_lruvec(pgdat, memcg);
271
	refault = atomic_long_read(&lruvec->inactive_age);
272
	active_file = lruvec_lru_size(lruvec, LRU_ACTIVE_FILE, MAX_NR_ZONES);
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291

	/*
	 * The unsigned subtraction here gives an accurate distance
	 * across inactive_age overflows in most cases.
	 *
	 * There is a special case: usually, shadow entries have a
	 * short lifetime and are either refaulted or reclaimed along
	 * with the inode before they get too old.  But it is not
	 * impossible for the inactive_age to lap a shadow entry in
	 * the field, which can then can result in a false small
	 * refault distance, leading to a false activation should this
	 * old entry actually refault again.  However, earlier kernels
	 * used to deactivate unconditionally with *every* reclaim
	 * invocation for the longest time, so the occasional
	 * inappropriate activation leading to pressure on the active
	 * list is not a problem.
	 */
	refault_distance = (refault - eviction) & EVICTION_MASK;

292
	inc_lruvec_state(lruvec, WORKINGSET_REFAULT);
293

294
	if (refault_distance <= active_file) {
295
		inc_lruvec_state(lruvec, WORKINGSET_ACTIVATE);
296
		rcu_read_unlock();
297 298
		return true;
	}
299
	rcu_read_unlock();
300 301 302 303 304 305 306 307 308
	return false;
}

/**
 * workingset_activation - note a page activation
 * @page: page that is being activated
 */
void workingset_activation(struct page *page)
{
309
	struct mem_cgroup *memcg;
310 311
	struct lruvec *lruvec;

312
	rcu_read_lock();
313 314 315 316 317 318 319
	/*
	 * Filter non-memcg pages here, e.g. unmap can call
	 * mark_page_accessed() on VDSO pages.
	 *
	 * XXX: See workingset_refault() - this should return
	 * root_mem_cgroup even for !CONFIG_MEMCG.
	 */
320 321
	memcg = page_memcg_rcu(page);
	if (!mem_cgroup_disabled() && !memcg)
322
		goto out;
323
	lruvec = mem_cgroup_lruvec(page_pgdat(page), memcg);
324 325
	atomic_long_inc(&lruvec->inactive_age);
out:
326
	rcu_read_unlock();
327
}
328 329 330 331 332 333 334 335 336 337 338 339 340

/*
 * Shadow entries reflect the share of the working set that does not
 * fit into memory, so their number depends on the access pattern of
 * the workload.  In most cases, they will refault or get reclaimed
 * along with the inode, but a (malicious) workload that streams
 * through files with a total size several times that of available
 * memory, while preventing the inodes from being reclaimed, can
 * create excessive amounts of shadow nodes.  To keep a lid on this,
 * track shadow nodes and reclaim them when they grow way past the
 * point where they would still be useful.
 */

341 342
static struct list_lru shadow_nodes;

343
void workingset_update_node(struct radix_tree_node *node)
344 345 346 347 348 349 350
{
	/*
	 * Track non-empty nodes that contain only shadow entries;
	 * unlink those that contain pages or are being freed.
	 *
	 * Avoid acquiring the list_lru lock when the nodes are
	 * already where they should be. The list_empty() test is safe
Matthew Wilcox's avatar
Matthew Wilcox committed
351
	 * as node->private_list is protected by the i_pages lock.
352 353
	 */
	if (node->count && node->count == node->exceptional) {
354
		if (list_empty(&node->private_list))
355 356 357 358 359 360
			list_lru_add(&shadow_nodes, &node->private_list);
	} else {
		if (!list_empty(&node->private_list))
			list_lru_del(&shadow_nodes, &node->private_list);
	}
}
361 362 363 364 365

static unsigned long count_shadow_nodes(struct shrinker *shrinker,
					struct shrink_control *sc)
{
	unsigned long max_nodes;
366
	unsigned long nodes;
367
	unsigned long cache;
368

Matthew Wilcox's avatar
Matthew Wilcox committed
369
	/* list_lru lock nests inside the IRQ-safe i_pages lock */
370
	local_irq_disable();
371
	nodes = list_lru_shrink_count(&shadow_nodes, sc);
372 373 374
	local_irq_enable();

	/*
375 376 377 378 379 380 381 382 383 384 385 386 387 388
	 * Approximate a reasonable limit for the radix tree nodes
	 * containing shadow entries. We don't need to keep more
	 * shadow entries than possible pages on the active list,
	 * since refault distances bigger than that are dismissed.
	 *
	 * The size of the active list converges toward 100% of
	 * overall page cache as memory grows, with only a tiny
	 * inactive list. Assume the total cache size for that.
	 *
	 * Nodes might be sparsely populated, with only one shadow
	 * entry in the extreme case. Obviously, we cannot keep one
	 * node for every eligible shadow entry, so compromise on a
	 * worst-case density of 1/8th. Below that, not all eligible
	 * refaults can be detected anymore.
389 390 391
	 *
	 * On 64-bit with 7 radix_tree_nodes per page and 64 slots
	 * each, this will reclaim shadow entries when they consume
392
	 * ~1.8% of available memory:
393
	 *
394
	 * PAGE_SIZE / radix_tree_nodes / node_entries * 8 / PAGE_SIZE
395
	 */
396 397 398 399 400 401 402 403
	if (sc->memcg) {
		cache = mem_cgroup_node_nr_lru_pages(sc->memcg, sc->nid,
						     LRU_ALL_FILE);
	} else {
		cache = node_page_state(NODE_DATA(sc->nid), NR_ACTIVE_FILE) +
			node_page_state(NODE_DATA(sc->nid), NR_INACTIVE_FILE);
	}
	max_nodes = cache >> (RADIX_TREE_MAP_SHIFT - 3);
404

405
	if (nodes <= max_nodes)
406
		return 0;
407
	return nodes - max_nodes;
408 409 410
}

static enum lru_status shadow_lru_isolate(struct list_head *item,
411
					  struct list_lru_one *lru,
412 413 414 415 416 417 418 419 420 421
					  spinlock_t *lru_lock,
					  void *arg)
{
	struct address_space *mapping;
	struct radix_tree_node *node;
	unsigned int i;
	int ret;

	/*
	 * Page cache insertions and deletions synchroneously maintain
Matthew Wilcox's avatar
Matthew Wilcox committed
422
	 * the shadow node LRU under the i_pages lock and the
423 424 425 426
	 * lru_lock.  Because the page cache tree is emptied before
	 * the inode can be destroyed, holding the lru_lock pins any
	 * address_space that has radix tree nodes on the LRU.
	 *
Matthew Wilcox's avatar
Matthew Wilcox committed
427
	 * We can then safely transition to the i_pages lock to
428 429 430 431 432
	 * pin only the address_space of the particular node we want
	 * to reclaim, take the node off-LRU, and drop the lru_lock.
	 */

	node = container_of(item, struct radix_tree_node, private_list);
Matthew Wilcox's avatar
Matthew Wilcox committed
433
	mapping = container_of(node->root, struct address_space, i_pages);
434 435

	/* Coming from the list, invert the lock order */
Matthew Wilcox's avatar
Matthew Wilcox committed
436
	if (!xa_trylock(&mapping->i_pages)) {
437 438 439 440 441
		spin_unlock(lru_lock);
		ret = LRU_RETRY;
		goto out;
	}

442
	list_lru_isolate(lru, item);
443 444 445 446 447 448 449
	spin_unlock(lru_lock);

	/*
	 * The nodes should only contain one or more shadow entries,
	 * no pages, so we expect to be able to remove them all and
	 * delete and free the empty node afterwards.
	 */
450
	if (WARN_ON_ONCE(!node->exceptional))
451
		goto out_invalid;
452
	if (WARN_ON_ONCE(node->count != node->exceptional))
453
		goto out_invalid;
454 455
	for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
		if (node->slots[i]) {
456 457
			if (WARN_ON_ONCE(!radix_tree_exceptional_entry(node->slots[i])))
				goto out_invalid;
458 459
			if (WARN_ON_ONCE(!node->exceptional))
				goto out_invalid;
460 461
			if (WARN_ON_ONCE(!mapping->nrexceptional))
				goto out_invalid;
462
			node->slots[i] = NULL;
463 464
			node->exceptional--;
			node->count--;
465
			mapping->nrexceptional--;
466 467
		}
	}
468
	if (WARN_ON_ONCE(node->exceptional))
469
		goto out_invalid;
470
	inc_lruvec_page_state(virt_to_page(node), WORKINGSET_NODERECLAIM);
Matthew Wilcox's avatar
Matthew Wilcox committed
471
	__radix_tree_delete_node(&mapping->i_pages, node,
472
				 workingset_lookup_update(mapping));
473

474
out_invalid:
Matthew Wilcox's avatar
Matthew Wilcox committed
475
	xa_unlock(&mapping->i_pages);
476 477 478 479 480 481 482 483 484 485 486 487 488 489
	ret = LRU_REMOVED_RETRY;
out:
	local_irq_enable();
	cond_resched();
	local_irq_disable();
	spin_lock(lru_lock);
	return ret;
}

static unsigned long scan_shadow_nodes(struct shrinker *shrinker,
				       struct shrink_control *sc)
{
	unsigned long ret;

Matthew Wilcox's avatar
Matthew Wilcox committed
490
	/* list_lru lock nests inside the IRQ-safe i_pages lock */
491
	local_irq_disable();
492
	ret = list_lru_shrink_walk(&shadow_nodes, sc, shadow_lru_isolate, NULL);
493 494 495 496 497 498 499 500
	local_irq_enable();
	return ret;
}

static struct shrinker workingset_shadow_shrinker = {
	.count_objects = count_shadow_nodes,
	.scan_objects = scan_shadow_nodes,
	.seeks = DEFAULT_SEEKS,
501
	.flags = SHRINKER_NUMA_AWARE | SHRINKER_MEMCG_AWARE,
502 503 504 505
};

/*
 * Our list_lru->lock is IRQ-safe as it nests inside the IRQ-safe
Matthew Wilcox's avatar
Matthew Wilcox committed
506
 * i_pages lock.
507 508 509 510 511
 */
static struct lock_class_key shadow_nodes_key;

static int __init workingset_init(void)
{
512 513
	unsigned int timestamp_bits;
	unsigned int max_order;
514 515
	int ret;

516 517 518 519 520 521 522 523 524 525 526 527
	BUILD_BUG_ON(BITS_PER_LONG < EVICTION_SHIFT);
	/*
	 * Calculate the eviction bucket size to cover the longest
	 * actionable refault distance, which is currently half of
	 * memory (totalram_pages/2). However, memory hotplug may add
	 * some more pages at runtime, so keep working with up to
	 * double the initial memory by using totalram_pages as-is.
	 */
	timestamp_bits = BITS_PER_LONG - EVICTION_SHIFT;
	max_order = fls_long(totalram_pages - 1);
	if (max_order > timestamp_bits)
		bucket_order = max_order - timestamp_bits;
528
	pr_info("workingset: timestamp_bits=%d max_order=%d bucket_order=%u\n",
529 530
	       timestamp_bits, max_order, bucket_order);

531
	ret = __list_lru_init(&shadow_nodes, true, &shadow_nodes_key);
532 533 534 535 536 537 538
	if (ret)
		goto err;
	ret = register_shrinker(&workingset_shadow_shrinker);
	if (ret)
		goto err_list_lru;
	return 0;
err_list_lru:
539
	list_lru_destroy(&shadow_nodes);
540 541 542 543
err:
	return ret;
}
module_init(workingset_init);