19 #include "chapter-index.h"
31  * volume storage acts as a circular log of the most recent chapters, with each new chapter
34  * When a new chapter is filled and closed, the records from that chapter are sorted and
37  * is also updated to indicate which delta lists fall on each chapter index page. This means that
39  * rather than search the entire chapter. These index and record pages are written to storage, and
41  * written chapter is likely to be accessed again soon.
43  * When reading a record, the volume index will indicate which chapter should contain it. The
44  * volume uses the index page map to determine which chapter index page needs to be loaded, and
45  * then reads the relevant record page number from the chapter index. Both index and record pages
58  * When an index rebuild is necessary, the volume reads each stored chapter to determine which
101 static u32 map_to_physical_page(const struct index_geometry *geometry, u32 chapter, u32 page)  in map_to_physical_page()  argument
103 	/* Page zero is the header page, so the first chapter index page is page one. */  in map_to_physical_page()
104 	return HEADER_PAGES_PER_VOLUME + (geometry->pages_per_chapter * chapter) + page;  in map_to_physical_page()
358 	/* Mark the page as queued, so that chapter invalidation knows to cancel a read. */  in enqueue_page_read()
418 				   u32 chapter, u32 index_page_number,  in init_chapter_index_page()  argument
435 					      "Reading chapter index page for chapter %u page %u",  in init_chapter_index_page()
436 					      chapter, index_page_number);  in init_chapter_index_page()
439 	uds_get_list_number_bounds(volume->index_page_map, chapter, index_page_number,  in init_chapter_index_page()
443 	if ((chapter == ci_chapter) &&  in init_chapter_index_page()
450 …vdo_log_warning("Page map expects that chapter %u page %u has range %u to %u, but chapter index pa…  in init_chapter_index_page()
451 			chapter, index_page_number, lowest_list, highest_list,  in init_chapter_index_page()
456 				      "index page map mismatch with chapter index");  in init_chapter_index_page()
462 	u32 chapter = map_to_chapter_number(volume->geometry, physical_page);  in initialize_index_page()  local
466 				       chapter, index_page_number, &page->index_page);  in initialize_index_page()
577 			vdo_log_warning("Error initializing chapter index page");  in process_entry()
806 static int get_volume_page(struct volume *volume, u32 chapter, u32 page_number,  in get_volume_page()  argument
810 	u32 physical_page = map_to_physical_page(volume->geometry, chapter, page_number);  in get_volume_page()
818 int uds_get_volume_record_page(struct volume *volume, u32 chapter, u32 page_number,  in uds_get_volume_record_page()  argument
824 	result = get_volume_page(volume, chapter, page_number, &page);  in uds_get_volume_record_page()
830 int uds_get_volume_index_page(struct volume *volume, u32 chapter, u32 page_number,  in uds_get_volume_index_page()  argument
836 	result = get_volume_page(volume, chapter, page_number, &page);  in uds_get_volume_index_page()
847 				    u32 chapter, u32 index_page_number,  in search_cached_index_page()  argument
852 	u32 physical_page = map_to_physical_page(volume->geometry, chapter,  in search_cached_index_page()
881 				  u32 chapter, u16 record_page_number, bool *found)  in uds_search_cached_record_page()  argument
900 	physical_page = map_to_physical_page(volume->geometry, chapter, page_number);  in uds_search_cached_record_page()
924 void uds_prefetch_volume_chapter(const struct volume *volume, u32 chapter)  in uds_prefetch_volume_chapter()  argument
927 	u32 physical_page = map_to_physical_page(geometry, chapter, 0);  in uds_prefetch_volume_chapter()
1054 	vdo_log_debug("forgetting chapter %llu", (unsigned long long) virtual_chapter);  in uds_forget_chapter()
1062  * Donate an index pages from a newly written chapter to the page cache since it is likely to be
1080 		vdo_log_warning("Error initialize chapter index page");  in donate_index_page_locked()
1132 			vdo_log_debug("no delta lists packed on chapter %u page %u",  in write_index_pages()
1262 		vdo_log_error_strerror(result, "cannot sync chapter to volume");  in uds_write_chapter()
1289 			vdo_log_error("corrupt index page in chapter %u",  in probe_chapter()
1297 			vdo_log_error("inconsistent chapter %u index page %u: expected vcn %llu, got vcn %llu",  in probe_chapter()
1304 …vdo_log_error("inconsistent chapter %u index page %u: expected list number %u, got list number %u",  in probe_chapter()
1317 		vdo_log_error("chapter %u vcn %llu is out of phase (%u)", chapter_number,  in probe_chapter()
1325 /* Find the last valid physical chapter in the volume. */
1332 		u32 chapter = (span > limit) ? 0 : limit - span;  in find_real_end_of_volume()  local
1335 		probe_chapter(volume, chapter, &vcn);  in find_real_end_of_volume()
1337 			limit = chapter;  in find_real_end_of_volume()
1376 	 * chapter numbers; bad spots are treated as a span of BAD_CHAPTER values. In effect we're  in find_chapter_limits()
1378 	 * the end it means that chapter 0 has the lowest vcn.  in find_chapter_limits()
1380 	 * If a virtual chapter is out-of-order, it will be the one moved by conversion. Always  in find_chapter_limits()
1381 	 * skip over the moved chapter when searching, adding it to the range at the end if  in find_chapter_limits()
1397 		u32 chapter = (left_chapter + right_chapter) / 2;  in find_chapter_limits()  local
1399 		if (chapter == moved_chapter)  in find_chapter_limits()
1400 			chapter--;  in find_chapter_limits()
1402 		probe_chapter(volume, chapter, &probe_vcn);  in find_chapter_limits()
1404 			left_chapter = chapter + 1;  in find_chapter_limits()
1408 			right_chapter = chapter;  in find_chapter_limits()
1412 	/* If left_chapter goes off the end, chapter 0 has the lowest virtual chapter number.*/  in find_chapter_limits()
1416 	/* At this point, left_chapter is the chapter with the lowest virtual chapter number. */  in find_chapter_limits()
1419 	/* The moved chapter might be the lowest in the range. */  in find_chapter_limits()
1425 	 * which is the chapter with the highest vcn.  in find_chapter_limits()
1447  * virtual chapter numbers. This is used by rebuild.
1564 	 * Reserve a buffer for each entry in the page cache, one for the chapter writer, and one  in uds_make_volume()