dm-vdo/indexer/sparse-cache.c

6 #include "sparse-cache.h"
8 #include <linux/cache.h>
21  * Since the cache is small, it is implemented as a simple array of cache entries. Searching for a
22  * specific virtual chapter is implemented as a linear search. The cache replacement policy is
23  * least-recently-used (LRU). Again, the small size of the cache allows the LRU order to be
26  * Changing the contents of the cache requires the coordinated participation of all zone threads
28  * thread. The critical invariant for coordination is that the cache membership must not change
32  * chapter because it has had too many cache misses" are represented separately from the cache
36  * uds_update_sparse_cache() once and exactly once to request a chapter that is not in the cache,
40  * section where a single zone thread can drive the cache update while all the other zone threads
43  * exclusive lock. No other threads may access or modify the cache entries.
46  * All fields that might be frequently updated by that thread are kept in separate cache-aligned
47  * structures so they will not cause cache contention via "false sharing" with the fields that are
51  * searching and cache membership queries. The zone zero list is used to decide which chapter to
52  * evict when the cache is updated, and its search list is copied to the other threads at that
55  * The virtual chapter number field of the cache entry is the single field indicating whether a
56  * chapter is a member of the cache or not. The value NO_CHAPTER is used to represent a null or
58  * cached_chapter_index, it indicates that the cache entry is dead, and all the other fields of
59  * that entry (other than immutable pointers to cache memory) are undefined and irrelevant. Any
60  * cache entry that is not marked as dead is fully defined and a member of the cache, and
62  * in any of the cache entries.
64  * A chapter index that is a member of the cache may be excluded from searches between calls to
69  * cache, but it will no longer be searched for matching names.
73  * be set to true, causing the chapter to be skipped when searching the entire cache, but still
75  * clear the skip_search flag, once again allowing the non-hook searches to use that cache entry.
77  * considered to be a member of the cache for uds_sparse_cache_contains().
86  * them on different cache lines from the chapter fields that are accessed far more often than they
95 	 * The virtual chapter number of the cached chapter index. NO_CHAPTER means this cache
104 	 * These pointers are immutable during the life of the cache. The contents of the arrays
105 	 * change when the cache entry is replaced.
111 	 * If set, skip the chapter when searching the entire cache. This flag is just a
112 	 * performance optimization. This flag is mutable between cache updates, but it rarely
118 	 * The cache-aligned counters change often and are placed at the end of the structure to
125  * A search_list represents an ordering of the sparse chapter index cache entry array, from most
127  * searched and the reverse order in which they should be evicted from the cache.
134  * structure is allocated on a cache boundary to avoid false sharing of memory cache lines between
234 static int __must_check make_search_list(struct sparse_cache *cache,
243 		 (cache->capacity * sizeof(struct cached_chapter_index *)));
248 	list->capacity = cache->capacity;
252 		list->entries[i] = &cache->chapters[i];
263 	struct sparse_cache *cache;
267 	result = vdo_allocate_cache_aligned(bytes, "sparse cache", &cache);
271 	cache->geometry = geometry;
272 	cache->capacity = capacity;
273 	cache->zone_count = zone_count;
276 	 * Scale down the skip threshold since the cache only counts cache misses in zone zero, but
279 	cache->skip_threshold = (SKIP_SEARCH_THRESHOLD / zone_count);
281 	initialize_threads_barrier(&cache->begin_update_barrier, zone_count);
282 	initialize_threads_barrier(&cache->end_update_barrier, zone_count);
285 		result = initialize_cached_chapter_index(&cache->chapters[i], geometry);
291 		result = make_search_list(cache, &cache->search_lists[i]);
298 			      "scratch entries", &cache->scratch_entries);
302 	*cache_ptr = cache;
305 	uds_free_sparse_cache(cache);
312 	/* Check before setting to reduce cache line contention. */
323 static void score_search_miss(struct sparse_cache *cache,
327 	if (chapter->counters.consecutive_misses > cache->skip_threshold)
345 void uds_free_sparse_cache(struct sparse_cache *cache)
349 	if (cache == NULL)
352 	vdo_free(cache->scratch_entries);
354 	for (i = 0; i < cache->zone_count; i++)
355 		vdo_free(cache->search_lists[i]);
357 	for (i = 0; i < cache->capacity; i++) {
358 		release_cached_chapter_index(&cache->chapters[i]);
359 		vdo_free(cache->chapters[i].index_pages);
360 		vdo_free(cache->chapters[i].page_buffers);
363 	vdo_free(cache);
389 bool uds_sparse_cache_contains(struct sparse_cache *cache, u64 virtual_chapter,
403 	search_list = cache->search_lists[zone_number];
420  * Re-sort cache entries into three sets (active, skippable, and dead) while maintaining the LRU
425 			      struct sparse_cache *cache, u64 oldest_virtual_chapter)
437 	skipped = &cache->scratch_entries[0];
438 	dead = &cache->scratch_entries[search_list->capacity];
488  * Update the sparse cache to contain a chapter index. This function must be called by all the zone
490  * the cache updates.
496 	struct sparse_cache *cache = index->volume->sparse_cache;
498 	if (uds_sparse_cache_contains(cache, virtual_chapter, zone->id))
503 	 * function before starting to modify the cache.
505 	enter_threads_barrier(&cache->begin_update_barrier);
509 	 * holding an exclusive lock on the sparse cache. All the other zone threads must do
516 		struct search_list *list = cache->search_lists[ZONE_ZERO];
518 		purge_search_list(list, cache, zone->oldest_virtual_chapter);
526 		for (z = 1; z < cache->zone_count; z++)
527 			copy_search_list(list, cache->search_lists[z]);
531 	 * This is the end of the critical section. All cache invariants must have been restored.
533 	enter_threads_barrier(&cache->end_update_barrier);
537 void uds_invalidate_sparse_cache(struct sparse_cache *cache)
541 	for (i = 0; i < cache->capacity; i++)
542 		release_cached_chapter_index(&cache->chapters[i]);
580 	struct sparse_cache *cache = volume->sparse_cache;
584 	/* Search the entire cache unless a specific chapter was requested. */
588 	search_list = cache->search_lists[zone->id];
596 		result = search_cached_chapter_index(chapter, cache->geometry,
617 			score_search_miss(cache, chapter);