5 #include "delta-index.h"
26  * The entries in a delta index could be stored in a single delta list, but to reduce search times
27  * and update costs it uses multiple delta lists. These lists are stored in a single chunk of
29  * memory, so the location of each delta list is recorded as a bit offset into the memory. Because
30  * the volume index can contain over a million delta lists, we want to be efficient with the size
31  * of the delta list header information. This information is encoded into 16 bytes per list. The
32  * volume index delta list memory can easily exceed 4 gigabits, so a 64 bit value is needed to
33  * address the memory. The volume index delta lists average around 6 kilobits, so 16 bits are
34  * sufficient to store the size of a delta list.
36  * Each delta list is stored as a bit stream. Within the delta list encoding, bits and bytes are
42  * A standard delta list entry is stored as a fixed length payload (the value) followed by a
43  * variable length key (the delta). A collision entry is used when two block names have the same
44  * delta list address. A collision entry always follows a standard entry for the hash with which it
45  * collides, and is encoded with DELTA == 0 with an additional 256 bits field at the end,
46  * containing the full block name. An entry with a delta of 0 at the beginning of a delta list
49  * The delta in each entry is encoded with a variable-length Huffman code to minimize the memory
51  * from the desired mean delta when the index is full. (See compute_coding_constants() for
54  * The bit field utilities used to read and write delta entries assume that it is possible to read
56  * invalid delta lists to prevent reading outside the delta_zone memory. The valid delta lists are
59  * delta list could cause this step to run off the end of the delta_zone memory, so as extra
65  * cached) chapter index pages. The immutable form does not allocate delta list headers or
93  * The maximum size of a single delta list in bytes. We count guard bytes in this value because a
104  * Immutable delta lists are packed into pages containing a header that encodes the delta list
110  * Constants and structures for the saved delta index. "DI" is for delta_index, and -##### is a
128  * Header data used for immutable delta index pages. This data is followed by the delta list offset
136 	/* Index of the first delta list on the page */
138 	/* Number of delta lists on the page */
213 	 * Initialize all delta lists to be empty. We keep 2 extra delta list descriptors, one  in uds_reset_delta_index()
225 		/* Zeroing the delta list headers initializes the head guard list correctly. */  in uds_reset_delta_index()
236 		/* Evenly space out the real delta lists by setting regular offsets. */  in uds_reset_delta_index()
251 /* Compute the Huffman coding parameters for the given mean delta. The Huffman code is specified by
314 	result = vdo_allocate(size, u8, "delta list", &delta_zone->memory);  in initialize_delta_zone()
318 	result = vdo_allocate(list_count + 2, u64, "delta list temp",  in initialize_delta_zone()
323 	/* Allocate the delta lists. */  in initialize_delta_zone()
324 	result = vdo_allocate(list_count + 2, struct delta_list, "delta lists",  in initialize_delta_zone()
355 	result = vdo_allocate(zone_count, struct delta_zone, "Delta Index Zones",  in uds_initialize_delta_index()
379 							      "%u delta lists not enough for %u zones",  in uds_initialize_delta_index()
423 /* Get the bit offset to the immutable delta list header. */
430 /* Get the bit offset to the start of the immutable delta list bit stream. */
437 /* Set the bit offset to the start of the immutable delta list bit stream. */
456 	/* Verify that the number of delta lists can fit in the page. */  in verify_delta_index_page()
462 	 * Verify that the first delta list is immediately after the last delta  in verify_delta_index_page()
492 /* Initialize a delta index page to refer to a supplied page. */
702  * Pack delta lists from a mutable delta index into an immutable delta index page. A range of delta
703  * lists (starting with a specified list index) is copied from the mutable delta index into a
727 	 * delta list offset, and the guard bytes from the page size to determine how much space is  in uds_pack_delta_index_page()
728 	 * available for delta lists.  in uds_pack_delta_index_page()
734 		/* This page is too small to store any delta lists. */  in uds_pack_delta_index_page()
741 		/* Each list requires a delta list offset and the list data. */  in uds_pack_delta_index_page()
759 	/* Construct the delta list offset table. */  in uds_pack_delta_index_page()
767 	/* Copy the delta list data onto the memory page. */  in uds_pack_delta_index_page()
779 /* Compute the new offsets of the delta lists. */
812 	/* Extend and balance memory to receive the delta lists */  in rebalance_lists()
822 /* Start restoring a delta index from multiple input streams. */
847 							"failed to read delta index header");  in uds_start_restoring_delta_index()
864 							"failed to read delta index header");  in uds_start_restoring_delta_index()
869 							"delta index file has bad magic number");  in uds_start_restoring_delta_index()
874 							"delta index files contain mismatched zone counts (%u,%u)",  in uds_start_restoring_delta_index()
880 							"delta index zone %u found in slot %u",  in uds_start_restoring_delta_index()
891 							"delta index file for zone %u starts with list %u instead of list %u",  in uds_start_restoring_delta_index()
900 						"delta index files contain %u delta lists instead of %u delta lists",  in uds_start_restoring_delta_index()
906 						"delta index files contain %llu collisions and %llu records",  in uds_start_restoring_delta_index()
915 	/* Read the delta lists and distribute them to the proper zones. */  in uds_start_restoring_delta_index()
931 								"failed to read delta index size");  in uds_start_restoring_delta_index()
946 	/* Prepare each zone to start receiving the delta list data. */  in uds_start_restoring_delta_index()
964 						"invalid delta list number %u not in range [%u,%u)",  in restore_delta_list_to_zone()
972 						"unexpected delta list number %u",  in restore_delta_list_to_zone()
980 						"unexpected delta list size %u != %u",  in restore_delta_list_to_zone()
1000 						"failed to read delta list data");  in restore_delta_list_data()
1013 						"corrupt delta list data");  in restore_delta_list_data()
1016 	/* Make sure the data is intended for this delta index. */  in restore_delta_list_data()
1022 						"invalid delta list number %u of %u",  in restore_delta_list_data()
1031 						"failed to read delta list data");  in restore_delta_list_data()
1040 /* Restore delta lists from saved data. */
1105 		vdo_log_warning_strerror(result, "failed to write delta list memory");  in flush_delta_list()
1113 		vdo_log_warning_strerror(result, "failed to write delta list memory");  in flush_delta_list()
1118 /* Start saving a delta index zone to a buffered output stream. */
1148 						"failed to write delta index header");  in uds_start_saving_delta_index()
1160 							"failed to write delta list size");  in uds_start_saving_delta_index()
1200 		vdo_log_warning_strerror(result, "failed to write guard delta list");  in uds_write_guard_delta_list()
1216 				"operation is invalid because the list entry is at the end of the delta list");  in assert_not_at_end()
1224  * Prepare to search for an entry in the specified delta list.
1226  * This is always the first function to be called when dealing with delta index entries. It is
1227  * always followed by calls to uds_next_delta_index_entry() to iterate through a delta list. The
1240 			    "Delta list number (%u) is out of range (%u)", list_number,  in uds_start_delta_index_search()
1249 			    "Delta list number (%u) is out of range (%u) for zone (%u)",  in uds_start_delta_index_search()
1260 		 * Translate the immutable delta list header into a temporary  in uds_start_delta_index_search()
1261 		 * full delta list header.  in uds_start_delta_index_search()
1279 			 * This usually means we're about to walk the entire delta list, so get all  in uds_start_delta_index_search()
1304  * Decode a delta index entry delta value. The delta_index_entry basically describes the previous
1311 	u32 delta;  in decode_delta()  local
1321 	delta = data & ((1 << key_bits) - 1);  in decode_delta()
1322 	if (delta >= delta_zone->min_keys) {  in decode_delta()
1332 		delta += ((key_bits - delta_zone->min_bits - 1) * delta_zone->incr_keys);  in decode_delta()
1334 	delta_entry->delta = delta;  in decode_delta()
1335 	delta_entry->key += delta;  in decode_delta()
1337 	/* Check for a collision, a delta of zero after the start. */  in decode_delta()
1338 	if (unlikely((delta == 0) && (delta_entry->offset > 0))) {  in decode_delta()
1363 		delta_entry->delta = 0;  in uds_next_delta_index_entry()
1366 				    "next offset past end of delta list");  in uds_next_delta_index_entry()
1381 		vdo_log_warning("Decoded past the end of the delta list");  in uds_next_delta_index_entry()
1397 	delta_list->save_key = delta_entry->key - delta_entry->delta;  in uds_remember_delta_index_offset()
1402 static void set_delta(struct delta_index_entry *delta_entry, u32 delta)  in set_delta()  argument
1406 			((delta_zone->incr_keys - delta_zone->min_keys + delta) /  in set_delta()
1409 	delta_entry->delta = delta;  in set_delta()
1493 			    "Cannot get full block name from a non-collision delta index entry");  in uds_get_delta_entry_collision()
1510 			        "delta index is mutable");  in assert_mutable_entry()
1531 			    "Value (%u) being set in a delta index is too large (must fit in %u bits)",  in uds_set_delta_entry_value()
1542  * Extend the memory used by the delta lists by adding growing_size bytes before the list indicated
1565 	/* Compute the new offsets of the delta lists. */  in extend_delta_zone()
1569 	 * When we rebalance the delta list, we will include the end guard list in the rebalancing.  in extend_delta_zone()
1601 	/* Compute bits available before and after the delta list. */  in insert_bits()
1626 		 * and/or rebalance the delta list memory choosing to move the least amount of  in insert_bits()
1668 	if (delta_entry->delta < delta_zone->min_keys) {  in encode_delta()
1669 		set_field(delta_entry->delta, memory, offset, delta_zone->min_bits);  in encode_delta()
1673 	temp = delta_entry->delta - delta_zone->min_keys;  in encode_delta()
1694  * Create a new entry in the delta index. If the entry is a collision, the full 256 bit name must
1744 		/* Insert a new entry at the end of the delta list. */  in uds_put_delta_index_entry()
1760 		 * Insert a new entry which requires the delta in the following entry to be  in uds_put_delta_index_entry()
1768 		result = VDO_ASSERT((key >= delta_entry->key - delta_entry->delta),  in uds_put_delta_index_entry()
1769 				    "key effects following entry's delta");  in uds_put_delta_index_entry()
1776 		set_delta(delta_entry, key - (delta_entry->key - delta_entry->delta));  in uds_put_delta_index_entry()
1814 	 * Determine whether to add to the available space either before or after the delta list.  in delete_bits()
1872 		next_entry.key -= delta_entry->delta;  in uds_remove_delta_index_entry()
1875 		/* The delta in the next entry needs to be updated. */  in uds_remove_delta_index_entry()
1884 		set_delta(&next_entry, delta_entry->delta + next_entry.delta);  in uds_remove_delta_index_entry()
1931 	/* On average, each delta is encoded into about min_bits + 1.5 bits. */  in uds_compute_delta_index_size()
1947 	/* Add in the immutable delta list headers. */  in uds_get_delta_index_page_count()
1952 	 * Reduce the bits per page by one immutable delta list header and one delta list to  in uds_get_delta_index_page_count()