20  * searches the chapter index for the relevant chapter. If the chapter has been fully committed to
21  * storage, the chapter pages are loaded into the page cache. If the chapter has not yet been
22  * committed (either the open chapter or a recently closed one), the index searches the in-memory
23  * representation of the chapter. Finally, if the volume index does not find a record and the index
26  * The index send two kinds of messages to coordinate between zones: chapter close messages for the
27  * chapter writer, and sparse cache barrier messages for the sparse cache.
29  * The chapter writer is responsible for committing chapters of records to storage. Since zones can
31  * its available space in a chapter, it informs the chapter writer that the chapter is complete,
32  * and also informs all other zones that it has closed the chapter. Each other zone will then close
33  * the chapter immediately, regardless of how full it is, in order to minimize skew between zones.
34  * Once every zone has closed the chapter, the chapter writer will commit that chapter to storage.
36  * The last zone to close the chapter also removes the oldest chapter from the volume index.
37  * Although that chapter is invalid for zones that have moved on, the existence of the open chapter
39  * than one chapter ahead of any other. If a zone is so far ahead that it tries to close another
40  * chapter before the previous one has been closed by all zones, it is forced to wait.
42  * The sparse cache relies on having the same set of chapter indexes available to all zones. When a
43  * request wants to add a chapter to the sparse cache, it sends a barrier message to each zone
66 	/* The number of bytes allocated by the chapter writer */
68 	/* The number of zones which have submitted a chapter for writing */
70 	/* Open chapter index used by uds_close_open_chapter() */
122  * chapter number to add.
139 	 * FIXME: Optimize for a common case by remembering the chapter from the most recent  in triage_index_request()
140 	 * barrier message and skipping this chapter if is it the same.  in triage_index_request()
192 					      "Writing of previous open chapter failed");  in finish_previous_chapter()
210  * Inform the chapter writer that this zone is done with this chapter. The chapter won't start
215 					  struct open_chapter_zone *chapter)  in start_closing_chapter()  argument
222 	writer->chapters[zone_number] = chapter;  in start_closing_chapter()
258 	vdo_log_debug("closing chapter %llu of zone %u after %u entries (%u short)",  in open_next_chapter()
347 	u32 chapter;  in search_sparse_cache_in_zone()  local
356 	chapter = uds_map_to_physical_chapter(volume->geometry, virtual_chapter);  in search_sparse_cache_in_zone()
357 	return uds_search_cached_record_page(volume, request, chapter,  in search_sparse_cache_in_zone()
417 	u64 chapter;  in search_index_zone()  local
438 	 * If a record has overflowed a chapter index in more than one chapter (or overflowed in  in search_index_zone()
439 	 * one chapter and collided with an existing record), it will exist as a collision record  in search_index_zone()
444 	chapter = zone->newest_virtual_chapter;  in search_index_zone()
452 		if (record.virtual_chapter != chapter) {  in search_index_zone()
454 			 * Update the volume index to reference the new chapter for the block. If  in search_index_zone()
455 			 * the record had been deleted or dropped from the chapter index, it will  in search_index_zone()
458 			result = uds_set_volume_index_record_chapter(&record, chapter);  in search_index_zone()
460 			/* The record is already in the open chapter. */  in search_index_zone()
466 		 * name is in a cached sparse chapter. If we found the name on  in search_index_zone()
492 		 * Add a new entry to the volume index referencing the open chapter. This needs to  in search_index_zone()
495 		result = uds_put_volume_index_record(&record, chapter);  in search_index_zone()
501 		 * logged. We will go on without adding the record to the open chapter.  in search_index_zone()
513 		/* Move the existing record to the open chapter. */  in search_index_zone()
538 		/* Non-collision records are hints, so resolve the name in the chapter. */  in remove_from_index_zone()
559 	 * later return stale advice if there is a colliding name in the same chapter, but it's a  in remove_from_index_zone()
567 	 * If the record is in the open chapter, we must remove it or mark it deleted to avoid  in remove_from_index_zone()
671 /* This is the driver function for the chapter writer thread. */
678 	vdo_log_debug("chapter writer starting");  in close_chapters()
685 				 * open chapter, so we can exit now.  in close_chapters()
688 				vdo_log_debug("chapter writer stopping");  in close_chapters()
695 		 * Release the lock while closing a chapter. We probably don't need to do this, but  in close_chapters()
696 		 * it seems safer in principle. It's OK to access the chapter and chapter_number  in close_chapters()
703 			 * Remove the saved open chapter the first time we close an open chapter  in close_chapters()
705 			 * lack of the saved open chapter will indicate that a recovery is  in close_chapters()
711 				vdo_log_debug("Discarding saved open chapter");  in close_chapters()
768 				       struct open_chapter_zone *, "Chapter Writer",  in make_chapter_writer()
818 	vdo_log_info("loaded index from chapter %llu through chapter %llu",  in load_index()
830 	u32 chapter = uds_map_to_physical_chapter(geometry, vcn);  in rebuild_index_page_map()  local
839 		result = uds_get_volume_index_page(index->volume, chapter,  in rebuild_index_page_map()
844 						      "failed to read index page %u in chapter %u",  in rebuild_index_page_map()
845 						      index_page_number, chapter);  in rebuild_index_page_map()
852 						      "chapter %u index page %u is corrupt",  in rebuild_index_page_map()
853 						      chapter, index_page_number);  in rebuild_index_page_map()
856 		uds_update_index_page_map(index->volume->index_page_map, vcn, chapter,  in rebuild_index_page_map()
874 		 * This entry will be in a sparse chapter after the rebuild completes, and it is  in replay_record()
894 			 * There is a volume index entry pointing to the current chapter, but we  in replay_record()
898 			 * record in the current chapter.  in replay_record()
906 			 * entry in the volume index that has a different chapter. In this case, we  in replay_record()
907 			 * need to search that chapter to determine if the volume index entry was  in replay_record()
923 		 * Update the volume index to reference the new chapter for the block. If the  in replay_record()
924 		 * record had been deleted or dropped from the chapter index, it will be back.  in replay_record()
929 		 * Add a new entry to the volume index referencing the open chapter. This should be  in replay_record()
980 		vdo_log_info("Replay interrupted by index shutdown at chapter %llu",  in replay_chapter()
993 					      "could not rebuild index page map for chapter %u",  in replay_chapter()
1034 	vdo_log_info("Replaying volume from chapter %llu through chapter %llu",  in replay_volume()
1042 	 * Go through each record page of each chapter and add the records back to the volume  in replay_volume()
1043 	 * index. This should not cause anything to be written to either the open chapter or the  in replay_volume()
1044 	 * on-disk volume. Also skip the on-disk chapter corresponding to upto_virtual, as this  in replay_volume()
1045 	 * would have already been purged from the volume index when the chapter was opened.  in replay_volume()
1047 	 * Also, go through each index page for each chapter and rebuild the index page map.  in replay_volume()
1059 	/* Also reap the chapter being replaced by the open chapter. */  in replay_volume()
1085 					      "cannot rebuild index: unknown volume chapter boundaries");  in rebuild_index()
1099 		/* Skip the chapter shadowed by the open chapter. */  in rebuild_index()
1297 /* Wait for the chapter writer to complete any outstanding writes. */