16 #include "chapter-index.h"
22  * specific virtual chapter is implemented as a linear search. The cache replacement policy is
30  * receive the same results for every virtual chapter number. To ensure that critical invariant,
31  * state changes such as "that virtual chapter is no longer in the volume" and "skip searching that
32  * chapter because it has had too many cache misses" are represented separately from the cache
33  * membership information (the virtual chapter number).
36  * uds_update_sparse_cache() once and exactly once to request a chapter that is not in the cache,
38  * request the same chapter number. This means the only synchronization we need can be provided by
45  * Chapter statistics must only be modified by a single thread, which is also the zone zero thread.
51  * searching and cache membership queries. The zone zero list is used to decide which chapter to
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
57  * undefined chapter number. When present in the virtual chapter number field of a
61  * uds_sparse_cache_contains() will always return true for any virtual chapter number that appears
64  * A chapter index that is a member of the cache may be excluded from searches between calls to
65  * uds_update_sparse_cache() in two different ways. First, when a chapter falls off the end of the
66  * volume, its virtual chapter number will be less that the oldest virtual chapter number. Since
67  * that chapter is no longer part of the volume, there's no point in continuing to search that
68  * chapter index. Once invalidated, that virtual chapter will still be considered a member of the
72  * misses in a given chapter index. Once that count exceeds a threshold, the skip_search flag will
73  * be set to true, causing the chapter to be skipped when searching the entire cache, but still
74  * allowing it to be found when searching for a hook in that specific chapter. Finding a hook will
76  * Again, regardless of the state of the skip_search flag, the virtual chapter must still
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  in __aligned()
111 	 * If set, skip the chapter when searching the entire cache. This flag is just a  in __aligned()
125  * A search_list represents an ordering of the sparse chapter index cache entry array, from most
217 static int __must_check initialize_cached_chapter_index(struct cached_chapter_index *chapter,  in initialize_cached_chapter_index()  argument
222 	chapter->virtual_chapter = NO_CHAPTER;  in initialize_cached_chapter_index()
223 	chapter->index_pages_count = geometry->index_pages_per_chapter;  in initialize_cached_chapter_index()
225 	result = vdo_allocate(chapter->index_pages_count, struct delta_index_page,  in initialize_cached_chapter_index()
226 			      __func__, &chapter->index_pages);  in initialize_cached_chapter_index()
230 	return vdo_allocate(chapter->index_pages_count, struct dm_buffer *,  in initialize_cached_chapter_index()
231 			    "sparse index volume pages", &chapter->page_buffers);  in initialize_cached_chapter_index()
309 static inline void set_skip_search(struct cached_chapter_index *chapter,  in set_skip_search()  argument
313 	if (READ_ONCE(chapter->skip_search) != skip_search)  in set_skip_search()
314 		WRITE_ONCE(chapter->skip_search, skip_search);  in set_skip_search()
317 static void score_search_hit(struct cached_chapter_index *chapter)  in score_search_hit()  argument
319 	chapter->counters.consecutive_misses = 0;  in score_search_hit()
320 	set_skip_search(chapter, false);  in score_search_hit()
324 			      struct cached_chapter_index *chapter)  in score_search_miss()  argument
326 	chapter->counters.consecutive_misses++;  in score_search_miss()
327 	if (chapter->counters.consecutive_misses > cache->skip_threshold)  in score_search_miss()
328 		set_skip_search(chapter, true);  in score_search_miss()
331 static void release_cached_chapter_index(struct cached_chapter_index *chapter)  in release_cached_chapter_index()  argument
335 	chapter->virtual_chapter = NO_CHAPTER;  in release_cached_chapter_index()
336 	if (chapter->page_buffers == NULL)  in release_cached_chapter_index()
339 	for (i = 0; i < chapter->index_pages_count; i++) {  in release_cached_chapter_index()
340 		if (chapter->page_buffers[i] != NULL)  in release_cached_chapter_index()
341 			dm_bufio_release(vdo_forget(chapter->page_buffers[i]));  in release_cached_chapter_index()
382 	 * This function may have moved a dead chapter to the front of the list for reuse, in which  in set_newest_entry()
393 	struct cached_chapter_index *chapter;  in uds_sparse_cache_contains()  local
399 	 * for a given chapter must be identical across zones. That invariant must be maintained  in uds_sparse_cache_contains()
400 	 * even if the chapter falls off the end of the volume, or if searching it is disabled  in uds_sparse_cache_contains()
405 		chapter = search_list->entries[i];  in uds_sparse_cache_contains()
407 		if (virtual_chapter == chapter->virtual_chapter) {  in uds_sparse_cache_contains()
409 				score_search_hit(chapter);  in uds_sparse_cache_contains()
430 	struct cached_chapter_index *chapter;  in purge_search_list()  local
441 		chapter = search_list->entries[i];  in purge_search_list()
442 		if ((chapter->virtual_chapter < oldest_virtual_chapter) ||  in purge_search_list()
443 		    (chapter->virtual_chapter == NO_CHAPTER))  in purge_search_list()
444 			dead[next_dead++] = chapter;  in purge_search_list()
445 		else if (chapter->skip_search)  in purge_search_list()
446 			skipped[next_skipped++] = chapter;  in purge_search_list()
448 			entries[next_alive++] = chapter;  in purge_search_list()
458 static int __must_check cache_chapter_index(struct cached_chapter_index *chapter,  in cache_chapter_index()  argument
464 	release_cached_chapter_index(chapter);  in cache_chapter_index()
467 						    chapter->page_buffers,  in cache_chapter_index()
468 						    chapter->index_pages);  in cache_chapter_index()
472 	chapter->counters.consecutive_misses = 0;  in cache_chapter_index()
473 	chapter->virtual_chapter = virtual_chapter;  in cache_chapter_index()
474 	chapter->skip_search = false;  in cache_chapter_index()
488  * Update the sparse cache to contain a chapter index. This function must be called by all the zone
489  * threads with the same chapter number to correctly enter the thread barriers used to synchronize
545 static inline bool should_skip_chapter(struct cached_chapter_index *chapter,  in should_skip_chapter()  argument
548 	if ((chapter->virtual_chapter == NO_CHAPTER) ||  in should_skip_chapter()
549 	    (chapter->virtual_chapter < oldest_chapter))  in should_skip_chapter()
553 		return requested_chapter != chapter->virtual_chapter;  in should_skip_chapter()
555 		return READ_ONCE(chapter->skip_search);  in should_skip_chapter()
558 static int __must_check search_cached_chapter_index(struct cached_chapter_index *chapter,  in search_cached_chapter_index()  argument
565 		uds_map_to_physical_chapter(geometry, chapter->virtual_chapter);  in search_cached_chapter_index()
569 		&chapter->index_pages[index_page_number];  in search_cached_chapter_index()
581 	struct cached_chapter_index *chapter;  in uds_search_sparse_cache()  local
584 	/* Search the entire cache unless a specific chapter was requested. */  in uds_search_sparse_cache()
590 		chapter = search_list->entries[i];  in uds_search_sparse_cache()
592 		if (should_skip_chapter(chapter, zone->oldest_virtual_chapter,  in uds_search_sparse_cache()
596 		result = search_cached_chapter_index(chapter, cache->geometry,  in uds_search_sparse_cache()
605 			 * another chapter, but that's a very rare case and not worth the extra  in uds_search_sparse_cache()
610 				score_search_hit(chapter);  in uds_search_sparse_cache()
612 			*virtual_chapter_ptr = chapter->virtual_chapter;  in uds_search_sparse_cache()
617 			score_search_miss(cache, chapter);  in uds_search_sparse_cache()