1 // SPDX-License-Identifier: GPL-2.0-only
6 #include "sparse-cache.h"
10 #include <linux/dm-bufio.h>
13 #include "memory-alloc.h"
16 #include "chapter-index.h"
23  * least-recently-used (LRU). Again, the small size of the cache allows the LRU order to be
46  * All fields that might be frequently updated by that thread are kept in separate cache-aligned
75  * clear the skip_search flag, once again allowing the non-hook searches to use that cache entry.
84  * These counters are essentially fields of the struct cached_chapter_index, but are segregated
118 	 * The cache-aligned counters change often and are placed at the end of the structure to  in __aligned()
121 	struct cached_index_counters counters;  in __aligned()  local
172 	sema_init(&barrier->lock, 1);  in initialize_threads_barrier()
173 	barrier->arrived = 0;  in initialize_threads_barrier()
174 	barrier->thread_count = thread_count;  in initialize_threads_barrier()
175 	sema_init(&barrier->wait, 0);  in initialize_threads_barrier()
181 	 * Do not use down(semaphore). Instead use down_interruptible so that  in __down()
186 		 * If we're called from a user-mode process (e.g., "dmsetup  in __down()
201 	__down(&barrier->lock);  in enter_threads_barrier()
202 	if (++barrier->arrived == barrier->thread_count) {  in enter_threads_barrier()
206 		for (i = 1; i < barrier->thread_count; i++)  in enter_threads_barrier()
207 			up(&barrier->wait);  in enter_threads_barrier()
209 		barrier->arrived = 0;  in enter_threads_barrier()
210 		up(&barrier->lock);  in enter_threads_barrier()
212 		up(&barrier->lock);  in enter_threads_barrier()
213 		__down(&barrier->wait);  in enter_threads_barrier()
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()
243 		 (cache->capacity * sizeof(struct cached_chapter_index *)));  in make_search_list()
248 	list->capacity = cache->capacity;  in make_search_list()
249 	list->first_dead_entry = 0;  in make_search_list()
251 	for (i = 0; i < list->capacity; i++)  in make_search_list()
252 		list->entries[i] = &cache->chapters[i];  in make_search_list()
271 	cache->geometry = geometry;  in uds_make_sparse_cache()
272 	cache->capacity = capacity;  in uds_make_sparse_cache()
273 	cache->zone_count = zone_count;  in uds_make_sparse_cache()
276 	 * Scale down the skip threshold since the cache only counts cache misses in zone zero, but  in uds_make_sparse_cache()
279 	cache->skip_threshold = (SKIP_SEARCH_THRESHOLD / zone_count);  in uds_make_sparse_cache()
281 	initialize_threads_barrier(&cache->begin_update_barrier, zone_count);  in uds_make_sparse_cache()
282 	initialize_threads_barrier(&cache->end_update_barrier, zone_count);  in uds_make_sparse_cache()
285 		result = initialize_cached_chapter_index(&cache->chapters[i], geometry);  in uds_make_sparse_cache()
291 		result = make_search_list(cache, &cache->search_lists[i]);  in uds_make_sparse_cache()
298 			      "scratch entries", &cache->scratch_entries);  in uds_make_sparse_cache()
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()
319 	chapter->counters.consecutive_misses = 0;  in score_search_hit()
326 	chapter->counters.consecutive_misses++;  in score_search_miss()
327 	if (chapter->counters.consecutive_misses > cache->skip_threshold)  in score_search_miss()
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()
352 	vdo_free(cache->scratch_entries);  in uds_free_sparse_cache()
354 	for (i = 0; i < cache->zone_count; i++)  in uds_free_sparse_cache()
355 		vdo_free(cache->search_lists[i]);  in uds_free_sparse_cache()
357 	for (i = 0; i < cache->capacity; i++) {  in uds_free_sparse_cache()
358 		release_cached_chapter_index(&cache->chapters[i]);  in uds_free_sparse_cache()
359 		vdo_free(cache->chapters[i].index_pages);  in uds_free_sparse_cache()
360 		vdo_free(cache->chapters[i].page_buffers);  in uds_free_sparse_cache()
368  * previously before it back down the list.
375 		newest = search_list->entries[index];  in set_newest_entry()
376 		memmove(&search_list->entries[1], &search_list->entries[0],  in set_newest_entry()
378 		search_list->entries[0] = newest;  in set_newest_entry()
385 	if (search_list->first_dead_entry <= index)  in set_newest_entry()
386 		search_list->first_dead_entry++;  in set_newest_entry()
403 	search_list = cache->search_lists[zone_number];  in uds_sparse_cache_contains()
404 	for (i = 0; i < search_list->first_dead_entry; i++) {  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()
420  * Re-sort cache entries into three sets (active, skippable, and dead) while maintaining the LRU
436 	entries = &search_list->entries[0];  in purge_search_list()
437 	skipped = &cache->scratch_entries[0];  in purge_search_list()
438 	dead = &cache->scratch_entries[search_list->capacity];  in purge_search_list()
440 	for (i = 0; i < search_list->first_dead_entry; i++) {  in purge_search_list()
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()
445 		else if (chapter->skip_search)  in purge_search_list()
455 	search_list->first_dead_entry = next_alive + next_skipped;  in purge_search_list()
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()
483 	memcpy(target->entries, source->entries,  in copy_search_list()
484 	       source->capacity * sizeof(struct cached_chapter_index *));  in copy_search_list()
495 	const struct uds_index *index = zone->index;  in uds_update_sparse_cache()
496 	struct sparse_cache *cache = index->volume->sparse_cache;  in uds_update_sparse_cache()
498 	if (uds_sparse_cache_contains(cache, virtual_chapter, zone->id))  in uds_update_sparse_cache()
505 	enter_threads_barrier(&cache->begin_update_barrier);  in uds_update_sparse_cache()
514 	if (zone->id == ZONE_ZERO) {  in uds_update_sparse_cache()
516 		struct search_list *list = cache->search_lists[ZONE_ZERO];  in uds_update_sparse_cache()
518 		purge_search_list(list, cache, zone->oldest_virtual_chapter);  in uds_update_sparse_cache()
520 		if (virtual_chapter >= index->oldest_virtual_chapter) {  in uds_update_sparse_cache()
521 			set_newest_entry(list, list->capacity - 1);  in uds_update_sparse_cache()
522 			result = cache_chapter_index(list->entries[0], virtual_chapter,  in uds_update_sparse_cache()
523 						     index->volume);  in uds_update_sparse_cache()
526 		for (z = 1; z < cache->zone_count; z++)  in uds_update_sparse_cache()
527 			copy_search_list(list, cache->search_lists[z]);  in uds_update_sparse_cache()
533 	enter_threads_barrier(&cache->end_update_barrier);  in uds_update_sparse_cache()
541 	for (i = 0; i < cache->capacity; i++)  in uds_invalidate_sparse_cache()
542 		release_cached_chapter_index(&cache->chapters[i]);  in uds_invalidate_sparse_cache()
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()
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()
579 	struct volume *volume = zone->index->volume;  in uds_search_sparse_cache()
580 	struct sparse_cache *cache = volume->sparse_cache;  in uds_search_sparse_cache()
588 	search_list = cache->search_lists[zone->id];  in uds_search_sparse_cache()
589 	for (i = 0; i < search_list->first_dead_entry; i++) {  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()
597 						     volume->index_page_map, name,  in uds_search_sparse_cache()
609 			if (zone->id == ZONE_ZERO)  in uds_search_sparse_cache()
612 			*virtual_chapter_ptr = chapter->virtual_chapter;  in uds_search_sparse_cache()
616 		if (zone->id == ZONE_ZERO)  in uds_search_sparse_cache()