Lines Matching +full:a +full:- +full:z
1 // SPDX-License-Identifier: GPL-2.0-only
5 #include "delta-index.h"
16 #include "memory-alloc.h"
19 #include "string-utils.h"
20 #include "time-utils.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
32 * volume index delta list memory can easily exceed 4 gigabits, so a 64 bit value is needed to
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
37 * numbered in little endian order. Within a byte, bit 0 is the least significant bit (0x1), and
38 * bit 7 is the most significant bit (0x80). Within a bit stream, bit 7 is the most significant bit
39 * of byte 0, and bit 8 is the least significant bit of byte 1. Within a byte array, a byte's
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
46 * containing the full block name. An entry with a delta of 0 at the beginning of a delta list
47 * indicates a normal entry.
49 * The delta in each entry is encoded with a variable-length Huffman code to minimize the memory
55 * some bytes beyond the end of the bit field, so a delta_zone memory allocation is guarded by two
58 * stream include a step that skips over bits set to 0 until the first 1 bit is found. A corrupted
71 * larger is not guaranteed to fit in a single byte-aligned u32.
73 #define MAX_FIELD_BITS ((sizeof(u32) - 1) * BITS_PER_BYTE + 1)
77 * is larger is not guaranteed to fit in a single byte-aligned u64.
79 #define MAX_BIG_FIELD_BITS ((sizeof(u64) - 1) * BITS_PER_BYTE + 1)
87 #define POST_FIELD_GUARD_BYTES (sizeof(u64) - 1)
93 * The maximum size of a single delta list in bytes. We count guard bytes in this value because a
99 /* The number of extra bytes and bits needed to store a collision entry */
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
115 static const char DELTA_INDEX_MAGIC[] = "DI-00002";
132 /* Externally-defined nonce */
144 return delta_list->start / BITS_PER_BYTE; in get_delta_list_byte_start()
149 unsigned int bit_offset = delta_list->start % BITS_PER_BYTE; in get_delta_list_byte_size()
151 return BITS_TO_BYTES(bit_offset + delta_list->size); in get_delta_list_byte_size()
162 delta_list = &delta_zone->delta_lists[first]; in rebalance_delta_zone()
163 new_start = delta_zone->new_offsets[first]; in rebalance_delta_zone()
164 if (delta_list->start != new_start) { in rebalance_delta_zone()
169 delta_list->start = new_start; in rebalance_delta_zone()
171 memmove(delta_zone->memory + destination, in rebalance_delta_zone()
172 delta_zone->memory + source, in rebalance_delta_zone()
183 delta_list = &delta_zone->delta_lists[middle]; in rebalance_delta_zone()
184 new_start = delta_zone->new_offsets[middle]; in rebalance_delta_zone()
190 if (new_start > delta_list->start) { in rebalance_delta_zone()
202 /* Round up so that each zone is a multiple of 64K in size. */ in get_zone_memory_size()
205 return (memory_size / zone_count + ALLOC_BOUNDARY - 1) & -ALLOC_BOUNDARY; in get_zone_memory_size()
210 unsigned int z; in uds_reset_delta_index() local
217 for (z = 0; z < delta_index->zone_count; z++) { in uds_reset_delta_index()
222 struct delta_zone *zone = &delta_index->delta_zones[z]; in uds_reset_delta_index()
223 struct delta_list *delta_lists = zone->delta_lists; in uds_reset_delta_index()
227 (zone->list_count + 2) * sizeof(struct delta_list)); in uds_reset_delta_index()
230 list_bits = (u64) zone->size * BITS_PER_BYTE - GUARD_BITS; in uds_reset_delta_index()
231 delta_lists[zone->list_count + 1].start = list_bits; in uds_reset_delta_index()
232 delta_lists[zone->list_count + 1].size = GUARD_BITS; in uds_reset_delta_index()
233 memset(zone->memory + (list_bits / BITS_PER_BYTE), ~0, in uds_reset_delta_index()
237 spacing = list_bits / zone->list_count; in uds_reset_delta_index()
239 for (i = 1; i <= zone->list_count; i++) { in uds_reset_delta_index()
245 zone->discard_count += zone->record_count; in uds_reset_delta_index()
246 zone->record_count = 0; in uds_reset_delta_index()
247 zone->collision_count = 0; in uds_reset_delta_index()
255 * BASE The number of values coded using a code of length MINBITS
272 * BASE = (1 << MINBITS) - INCR
274 * Now the index can generate a code such that
275 * - The first BASE values code using MINBITS bits.
276 * - The next INCR values code using MINBITS+1 bits.
277 * - The next INCR values code using MINBITS+2 bits.
278 * - (and so on).
284 * floating point, use a really good integer approximation. in compute_coding_constants()
288 *min_keys = (1 << *min_bits) - *incr_keys; in compute_coding_constants()
293 unsigned int z; in uds_uninitialize_delta_index() local
295 if (delta_index->delta_zones == NULL) in uds_uninitialize_delta_index()
298 for (z = 0; z < delta_index->zone_count; z++) { in uds_uninitialize_delta_index()
299 vdo_free(vdo_forget(delta_index->delta_zones[z].new_offsets)); in uds_uninitialize_delta_index()
300 vdo_free(vdo_forget(delta_index->delta_zones[z].delta_lists)); in uds_uninitialize_delta_index()
301 vdo_free(vdo_forget(delta_index->delta_zones[z].memory)); in uds_uninitialize_delta_index()
304 vdo_free(delta_index->delta_zones); in uds_uninitialize_delta_index()
314 result = vdo_allocate(size, u8, "delta list", &delta_zone->memory); in initialize_delta_zone()
319 &delta_zone->new_offsets); in initialize_delta_zone()
325 &delta_zone->delta_lists); in initialize_delta_zone()
329 compute_coding_constants(mean_delta, &delta_zone->min_bits, in initialize_delta_zone()
330 &delta_zone->min_keys, &delta_zone->incr_keys); in initialize_delta_zone()
331 delta_zone->value_bits = payload_bits; in initialize_delta_zone()
332 delta_zone->buffered_writer = NULL; in initialize_delta_zone()
333 delta_zone->size = size; in initialize_delta_zone()
334 delta_zone->rebalance_time = 0; in initialize_delta_zone()
335 delta_zone->rebalance_count = 0; in initialize_delta_zone()
336 delta_zone->record_count = 0; in initialize_delta_zone()
337 delta_zone->collision_count = 0; in initialize_delta_zone()
338 delta_zone->discard_count = 0; in initialize_delta_zone()
339 delta_zone->overflow_count = 0; in initialize_delta_zone()
340 delta_zone->first_list = first_list; in initialize_delta_zone()
341 delta_zone->list_count = list_count; in initialize_delta_zone()
342 delta_zone->tag = tag; in initialize_delta_zone()
352 unsigned int z; in uds_initialize_delta_index() local
356 &delta_index->delta_zones); in uds_initialize_delta_index()
360 delta_index->zone_count = zone_count; in uds_initialize_delta_index()
361 delta_index->list_count = list_count; in uds_initialize_delta_index()
362 delta_index->lists_per_zone = DIV_ROUND_UP(list_count, zone_count); in uds_initialize_delta_index()
363 delta_index->memory_size = 0; in uds_initialize_delta_index()
364 delta_index->mutable = true; in uds_initialize_delta_index()
365 delta_index->tag = tag; in uds_initialize_delta_index()
367 for (z = 0; z < zone_count; z++) { in uds_initialize_delta_index()
368 u32 lists_in_zone = delta_index->lists_per_zone; in uds_initialize_delta_index()
369 u32 first_list_in_zone = z * lists_in_zone; in uds_initialize_delta_index()
371 if (z == zone_count - 1) { in uds_initialize_delta_index()
376 if (delta_index->list_count <= first_list_in_zone) { in uds_initialize_delta_index()
382 lists_in_zone = delta_index->list_count - first_list_in_zone; in uds_initialize_delta_index()
386 result = initialize_delta_zone(&delta_index->delta_zones[z], zone_memory, in uds_initialize_delta_index()
394 delta_index->memory_size += in uds_initialize_delta_index()
403 /* Read a bit field from an arbitrary bit boundary. */
408 return (get_unaligned_le32(addr) >> (offset % BITS_PER_BYTE)) & ((1 << size) - 1); in get_field()
411 /* Write a bit field to an arbitrary bit boundary. */
418 data &= ~(((1 << size) - 1) << shift); in set_field()
450 * Verify the nonce. A mismatch can happen here during rebuild if we haven't written the in verify_delta_index_page()
457 if (list_count > ((memory_size - sizeof(struct delta_page_header)) * in verify_delta_index_page()
476 * for the post-field guard bits. in verify_delta_index_page()
479 (memory_size - POST_FIELD_GUARD_BYTES) * BITS_PER_BYTE) in verify_delta_index_page()
484 if (memory[memory_size - POST_FIELD_GUARD_BYTES + i] != (u8) ~0) in verify_delta_index_page()
492 /* Initialize a delta index page to refer to a supplied page. */
502 struct delta_zone *delta_zone = &delta_index_page->delta_zone; in uds_initialize_delta_index_page()
503 const u8 *nonce_addr = (const u8 *) &header->nonce; in uds_initialize_delta_index_page()
504 const u8 *vcn_addr = (const u8 *) &header->virtual_chapter_number; in uds_initialize_delta_index_page()
505 const u8 *first_list_addr = (const u8 *) &header->first_list; in uds_initialize_delta_index_page()
506 const u8 *list_count_addr = (const u8 *) &header->list_count; in uds_initialize_delta_index_page()
524 * during a rebuild if we haven't written the entire volume at least once. in uds_initialize_delta_index_page()
530 delta_index_page->delta_index.delta_zones = delta_zone; in uds_initialize_delta_index_page()
531 delta_index_page->delta_index.zone_count = 1; in uds_initialize_delta_index_page()
532 delta_index_page->delta_index.list_count = list_count; in uds_initialize_delta_index_page()
533 delta_index_page->delta_index.lists_per_zone = list_count; in uds_initialize_delta_index_page()
534 delta_index_page->delta_index.mutable = false; in uds_initialize_delta_index_page()
535 delta_index_page->delta_index.tag = 'p'; in uds_initialize_delta_index_page()
536 delta_index_page->virtual_chapter_number = vcn; in uds_initialize_delta_index_page()
537 delta_index_page->lowest_list_number = first_list; in uds_initialize_delta_index_page()
538 delta_index_page->highest_list_number = first_list + list_count - 1; in uds_initialize_delta_index_page()
540 compute_coding_constants(mean_delta, &delta_zone->min_bits, in uds_initialize_delta_index_page()
541 &delta_zone->min_keys, &delta_zone->incr_keys); in uds_initialize_delta_index_page()
542 delta_zone->value_bits = payload_bits; in uds_initialize_delta_index_page()
543 delta_zone->memory = memory; in uds_initialize_delta_index_page()
544 delta_zone->delta_lists = NULL; in uds_initialize_delta_index_page()
545 delta_zone->new_offsets = NULL; in uds_initialize_delta_index_page()
546 delta_zone->buffered_writer = NULL; in uds_initialize_delta_index_page()
547 delta_zone->size = memory_size; in uds_initialize_delta_index_page()
548 delta_zone->rebalance_time = 0; in uds_initialize_delta_index_page()
549 delta_zone->rebalance_count = 0; in uds_initialize_delta_index_page()
550 delta_zone->record_count = 0; in uds_initialize_delta_index_page()
551 delta_zone->collision_count = 0; in uds_initialize_delta_index_page()
552 delta_zone->discard_count = 0; in uds_initialize_delta_index_page()
553 delta_zone->overflow_count = 0; in uds_initialize_delta_index_page()
554 delta_zone->first_list = 0; in uds_initialize_delta_index_page()
555 delta_zone->list_count = list_count; in uds_initialize_delta_index_page()
556 delta_zone->tag = 'p'; in uds_initialize_delta_index_page()
561 /* Read a large bit field from an arbitrary bit boundary. */
566 return (get_unaligned_le64(addr) >> (offset % BITS_PER_BYTE)) & ((1UL << size) - 1); in get_big_field()
569 /* Write a large bit field to an arbitrary bit boundary. */
576 data &= ~(((1UL << size) - 1) << shift); in set_big_field()
581 /* Set a sequence of bits to all zeros. */
587 u32 count = size + shift > BITS_PER_BYTE ? (u32) BITS_PER_BYTE - shift : size; in set_zero()
589 *addr++ &= ~(((1 << count) - 1) << shift); in set_zero()
590 for (size -= count; size > BITS_PER_BYTE; size -= BITS_PER_BYTE) in set_zero()
599 * Move several bits from a higher to a lower address, moving the lower addressed bits first. The
610 /* Start by moving one field that ends on a to int boundary. */ in move_bits_down()
611 count = (MAX_BIG_FIELD_BITS - ((to_offset + MAX_BIG_FIELD_BITS) % BITS_PER_TYPE(u32))); in move_bits_down()
616 size -= count; in move_bits_down()
618 /* Now do the main loop to copy 32 bit chunks that are int-aligned at the destination. */ in move_bits_down()
620 source = from + (from_offset - offset) / BITS_PER_BYTE; in move_bits_down()
628 size -= BITS_PER_TYPE(u32); in move_bits_down()
639 * Move several bits from a lower to a higher address, moving the higher addressed bits first. The
650 /* Start by moving one field that begins on a destination int boundary. */ in move_bits_up()
653 size -= count; in move_bits_up()
658 /* Now do the main loop to copy 32 bit chunks that are int-aligned at the destination. */ in move_bits_up()
660 source = from + (from_offset + size - offset) / BITS_PER_BYTE; in move_bits_up()
663 source -= sizeof(u32); in move_bits_up()
664 destination -= sizeof(u32); in move_bits_up()
665 size -= BITS_PER_TYPE(u32); in move_bits_up()
678 * bits from the source to a temporary value, and then move all the bits from the temporary value
685 /* A small move doesn't require special handling. */ in move_bits()
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
721 delta_zone = &delta_index->delta_zones[0]; in uds_pack_delta_index_page()
722 delta_lists = &delta_zone->delta_lists[first_list + 1]; in uds_pack_delta_index_page()
723 max_lists = delta_index->list_count - first_list; in uds_pack_delta_index_page()
731 free_bits -= get_immutable_header_offset(1); in uds_pack_delta_index_page()
732 free_bits -= GUARD_BITS; in uds_pack_delta_index_page()
741 /* Each list requires a delta list offset and the list data. */ in uds_pack_delta_index_page()
747 free_bits -= bits; in uds_pack_delta_index_page()
753 put_unaligned_le64(header_nonce, (u8 *) &header->nonce); in uds_pack_delta_index_page()
755 (u8 *) &header->virtual_chapter_number); in uds_pack_delta_index_page()
756 put_unaligned_le16(first_list, (u8 *) &header->first_list); in uds_pack_delta_index_page()
757 put_unaligned_le16(n_lists, (u8 *) &header->list_count); in uds_pack_delta_index_page()
769 move_bits(delta_zone->memory, delta_lists[i].start, memory, in uds_pack_delta_index_page()
774 memset(memory + memory_size - POST_FIELD_GUARD_BYTES, ~0, in uds_pack_delta_index_page()
785 struct delta_list *delta_lists = delta_zone->delta_lists; in compute_new_list_offsets()
786 u32 tail_guard_index = delta_zone->list_count + 1; in compute_new_list_offsets()
788 spacing = (delta_zone->size - used_space) / delta_zone->list_count; in compute_new_list_offsets()
789 delta_zone->new_offsets[0] = 0; in compute_new_list_offsets()
790 for (i = 0; i <= delta_zone->list_count; i++) { in compute_new_list_offsets()
791 delta_zone->new_offsets[i + 1] = in compute_new_list_offsets()
792 (delta_zone->new_offsets[i] + in compute_new_list_offsets()
794 delta_zone->new_offsets[i] *= BITS_PER_BYTE; in compute_new_list_offsets()
795 delta_zone->new_offsets[i] += delta_lists[i].start % BITS_PER_BYTE; in compute_new_list_offsets()
797 delta_zone->new_offsets[i + 1] -= spacing / 2; in compute_new_list_offsets()
799 delta_zone->new_offsets[i + 1] += growing_size; in compute_new_list_offsets()
802 delta_zone->new_offsets[tail_guard_index] = in compute_new_list_offsets()
803 (delta_zone->size * BITS_PER_BYTE - delta_lists[tail_guard_index].size); in compute_new_list_offsets()
813 delta_lists = delta_zone->delta_lists; in rebalance_lists()
814 for (i = 0; i <= delta_zone->list_count + 1; i++) in rebalance_lists()
818 for (i = 1; i <= delta_zone->list_count + 1; i++) in rebalance_lists()
819 delta_lists[i].start = delta_zone->new_offsets[i]; in rebalance_lists()
822 /* Start restoring a delta index from multiple input streams. */
833 unsigned int z; in uds_start_restoring_delta_index() local
838 for (z = 0; z < zone_count; z++) { in uds_start_restoring_delta_index()
843 result = uds_read_from_buffered_reader(buffered_readers[z], buffer, in uds_start_restoring_delta_index()
878 if (header.zone_number != z) { in uds_start_restoring_delta_index()
881 header.zone_number, z); in uds_start_restoring_delta_index()
884 first_list[z] = header.first_list; in uds_start_restoring_delta_index()
885 list_count[z] = header.list_count; in uds_start_restoring_delta_index()
889 if (first_list[z] != list_next) { in uds_start_restoring_delta_index()
892 z, first_list[z], list_next); in uds_start_restoring_delta_index()
895 list_next += list_count[z]; in uds_start_restoring_delta_index()
898 if (list_next != delta_index->list_count) { in uds_start_restoring_delta_index()
901 list_next, delta_index->list_count); in uds_start_restoring_delta_index()
912 delta_index->delta_zones[0].record_count = record_count; in uds_start_restoring_delta_index()
913 delta_index->delta_zones[0].collision_count = collision_count; in uds_start_restoring_delta_index()
916 for (z = 0; z < zone_count; z++) { in uds_start_restoring_delta_index()
919 delta_index->load_lists[z] = 0; in uds_start_restoring_delta_index()
920 for (i = 0; i < list_count[z]; i++) { in uds_start_restoring_delta_index()
926 result = uds_read_from_buffered_reader(buffered_readers[z], in uds_start_restoring_delta_index()
936 delta_index->load_lists[z] += 1; in uds_start_restoring_delta_index()
938 list_number = first_list[z] + i; in uds_start_restoring_delta_index()
939 zone_number = list_number / delta_index->lists_per_zone; in uds_start_restoring_delta_index()
940 delta_zone = &delta_index->delta_zones[zone_number]; in uds_start_restoring_delta_index()
941 list_number -= delta_zone->first_list; in uds_start_restoring_delta_index()
942 delta_zone->delta_lists[list_number + 1].size = delta_list_size; in uds_start_restoring_delta_index()
947 for (z = 0; z < delta_index->zone_count; z++) in uds_start_restoring_delta_index()
948 rebalance_lists(&delta_index->delta_zones[z]); in uds_start_restoring_delta_index()
960 u32 list_number = save_info->index - delta_zone->first_list; in restore_delta_list_to_zone()
962 if (list_number >= delta_zone->list_count) { in restore_delta_list_to_zone()
965 save_info->index, delta_zone->first_list, in restore_delta_list_to_zone()
966 delta_zone->first_list + delta_zone->list_count); in restore_delta_list_to_zone()
969 delta_list = &delta_zone->delta_lists[list_number + 1]; in restore_delta_list_to_zone()
970 if (delta_list->size == 0) { in restore_delta_list_to_zone()
973 save_info->index); in restore_delta_list_to_zone()
976 bit_count = delta_list->size + save_info->bit_offset; in restore_delta_list_to_zone()
978 if (save_info->byte_count != byte_count) { in restore_delta_list_to_zone()
981 save_info->byte_count, byte_count); in restore_delta_list_to_zone()
984 move_bits(data, save_info->bit_offset, delta_zone->memory, delta_list->start, in restore_delta_list_to_zone()
985 delta_list->size); in restore_delta_list_to_zone()
1017 if (save_info.tag != delta_index->tag) in restore_delta_list_data()
1020 if (save_info.index >= delta_index->list_count) { in restore_delta_list_data()
1024 delta_index->list_count); in restore_delta_list_data()
1034 delta_index->load_lists[load_zone] -= 1; in restore_delta_list_data()
1035 new_zone = save_info.index / delta_index->lists_per_zone; in restore_delta_list_data()
1036 return restore_delta_list_to_zone(&delta_index->delta_zones[new_zone], in restore_delta_list_data()
1047 unsigned int z; in uds_finish_restoring_delta_index() local
1054 for (z = 0; z < reader_count; z++) { in uds_finish_restoring_delta_index()
1055 while (delta_index->load_lists[z] > 0) { in uds_finish_restoring_delta_index()
1056 result = restore_delta_list_data(delta_index, z, in uds_finish_restoring_delta_index()
1057 buffered_readers[z], data); in uds_finish_restoring_delta_index()
1073 unsigned int z; in uds_check_guard_delta_lists() local
1076 for (z = 0; z < reader_count; z++) { in uds_check_guard_delta_lists()
1077 result = uds_read_from_buffered_reader(buffered_readers[z], buffer, in uds_check_guard_delta_lists()
1082 if (buffer[0] != 'z') in uds_check_guard_delta_lists()
1095 delta_list = &zone->delta_lists[flush_index + 1]; in flush_delta_list()
1097 buffer[0] = zone->tag; in flush_delta_list()
1098 buffer[1] = delta_list->start % BITS_PER_BYTE; in flush_delta_list()
1100 put_unaligned_le32(zone->first_list + flush_index, &buffer[4]); in flush_delta_list()
1102 result = uds_write_to_buffered_writer(zone->buffered_writer, buffer, in flush_delta_list()
1109 result = uds_write_to_buffered_writer(zone->buffered_writer, in flush_delta_list()
1110 zone->memory + get_delta_list_byte_start(delta_list), in flush_delta_list()
1118 /* Start saving a delta index zone to a buffered output stream. */
1129 delta_zone = &delta_index->delta_zones[zone_number]; in uds_start_saving_delta_index()
1133 encode_u32_le(buffer, &offset, delta_index->zone_count); in uds_start_saving_delta_index()
1134 encode_u32_le(buffer, &offset, delta_zone->first_list); in uds_start_saving_delta_index()
1135 encode_u32_le(buffer, &offset, delta_zone->list_count); in uds_start_saving_delta_index()
1136 encode_u64_le(buffer, &offset, delta_zone->record_count); in uds_start_saving_delta_index()
1137 encode_u64_le(buffer, &offset, delta_zone->collision_count); in uds_start_saving_delta_index()
1150 for (i = 0; i < delta_zone->list_count; i++) { in uds_start_saving_delta_index()
1154 delta_list = &delta_zone->delta_lists[i + 1]; in uds_start_saving_delta_index()
1155 put_unaligned_le16(delta_list->size, data); in uds_start_saving_delta_index()
1163 delta_zone->buffered_writer = buffered_writer; in uds_start_saving_delta_index()
1176 delta_zone = &delta_index->delta_zones[zone_number]; in uds_finish_saving_delta_index()
1177 for (i = 0; i < delta_zone->list_count; i++) { in uds_finish_saving_delta_index()
1178 delta_list = &delta_zone->delta_lists[i + 1]; in uds_finish_saving_delta_index()
1179 if (delta_list->size > 0) { in uds_finish_saving_delta_index()
1186 delta_zone->buffered_writer = NULL; in uds_finish_saving_delta_index()
1196 buffer[0] = 'z'; in uds_write_guard_delta_list()
1215 int result = VDO_ASSERT(!delta_entry->at_end, in assert_not_at_end()
1227 * always followed by calls to uds_next_delta_index_entry() to iterate through a delta list. The
1239 result = VDO_ASSERT((list_number < delta_index->list_count), in uds_start_delta_index_search()
1241 delta_index->list_count); in uds_start_delta_index_search()
1245 zone_number = list_number / delta_index->lists_per_zone; in uds_start_delta_index_search()
1246 delta_zone = &delta_index->delta_zones[zone_number]; in uds_start_delta_index_search()
1247 list_number -= delta_zone->first_list; in uds_start_delta_index_search()
1248 result = VDO_ASSERT((list_number < delta_zone->list_count), in uds_start_delta_index_search()
1250 list_number, delta_zone->list_count, zone_number); in uds_start_delta_index_search()
1254 if (delta_index->mutable) { in uds_start_delta_index_search()
1255 delta_list = &delta_zone->delta_lists[list_number + 1]; in uds_start_delta_index_search()
1260 * Translate the immutable delta list header into a temporary in uds_start_delta_index_search()
1263 delta_list = &delta_entry->temp_delta_list; in uds_start_delta_index_search()
1264 delta_list->start = get_immutable_start(delta_zone->memory, list_number); in uds_start_delta_index_search()
1265 end_offset = get_immutable_start(delta_zone->memory, list_number + 1); in uds_start_delta_index_search()
1266 delta_list->size = end_offset - delta_list->start; in uds_start_delta_index_search()
1267 delta_list->save_key = 0; in uds_start_delta_index_search()
1268 delta_list->save_offset = 0; in uds_start_delta_index_search()
1271 if (key > delta_list->save_key) { in uds_start_delta_index_search()
1272 delta_entry->key = delta_list->save_key; in uds_start_delta_index_search()
1273 delta_entry->offset = delta_list->save_offset; in uds_start_delta_index_search()
1275 delta_entry->key = 0; in uds_start_delta_index_search()
1276 delta_entry->offset = 0; in uds_start_delta_index_search()
1282 uds_prefetch_range(&delta_zone->memory[delta_list->start / BITS_PER_BYTE], in uds_start_delta_index_search()
1283 delta_list->size / BITS_PER_BYTE, false); in uds_start_delta_index_search()
1287 delta_entry->at_end = false; in uds_start_delta_index_search()
1288 delta_entry->delta_zone = delta_zone; in uds_start_delta_index_search()
1289 delta_entry->delta_list = delta_list; in uds_start_delta_index_search()
1290 delta_entry->entry_bits = 0; in uds_start_delta_index_search()
1291 delta_entry->is_collision = false; in uds_start_delta_index_search()
1292 delta_entry->list_number = list_number; in uds_start_delta_index_search()
1293 delta_entry->list_overflow = false; in uds_start_delta_index_search()
1294 delta_entry->value_bits = delta_zone->value_bits; in uds_start_delta_index_search()
1300 return delta_entry->delta_list->start + delta_entry->offset; in get_delta_entry_offset()
1304 * Decode a delta index entry delta value. The delta_index_entry basically describes the previous
1312 const struct delta_zone *delta_zone = delta_entry->delta_zone; in decode_delta()
1313 const u8 *memory = delta_zone->memory; in decode_delta()
1314 u64 delta_offset = get_delta_entry_offset(delta_entry) + delta_entry->value_bits; in decode_delta()
1320 key_bits = delta_zone->min_bits; in decode_delta()
1321 delta = data & ((1 << key_bits) - 1); in decode_delta()
1322 if (delta >= delta_zone->min_keys) { in decode_delta()
1325 key_bits = sizeof(u32) * BITS_PER_BYTE - offset; 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()
1339 delta_entry->is_collision = true; in decode_delta()
1340 delta_entry->entry_bits = delta_entry->value_bits + key_bits + COLLISION_BITS; in decode_delta()
1342 delta_entry->is_collision = false; in decode_delta()
1343 delta_entry->entry_bits = delta_entry->value_bits + key_bits; in decode_delta()
1358 delta_list = delta_entry->delta_list; in uds_next_delta_index_entry()
1359 delta_entry->offset += delta_entry->entry_bits; in uds_next_delta_index_entry()
1360 size = delta_list->size; in uds_next_delta_index_entry()
1361 if (unlikely(delta_entry->offset >= size)) { in uds_next_delta_index_entry()
1362 delta_entry->at_end = true; in uds_next_delta_index_entry()
1363 delta_entry->delta = 0; in uds_next_delta_index_entry()
1364 delta_entry->is_collision = false; in uds_next_delta_index_entry()
1365 result = VDO_ASSERT((delta_entry->offset == size), in uds_next_delta_index_entry()
1375 next_offset = delta_entry->offset + delta_entry->entry_bits; in uds_next_delta_index_entry()
1391 struct delta_list *delta_list = delta_entry->delta_list; in uds_remember_delta_index_offset()
1393 result = VDO_ASSERT(!delta_entry->is_collision, "entry is not a collision"); in uds_remember_delta_index_offset()
1397 delta_list->save_key = delta_entry->key - delta_entry->delta; in uds_remember_delta_index_offset()
1398 delta_list->save_offset = delta_entry->offset; in uds_remember_delta_index_offset()
1404 const struct delta_zone *delta_zone = delta_entry->delta_zone; in set_delta()
1405 u32 key_bits = (delta_zone->min_bits + in set_delta()
1406 ((delta_zone->incr_keys - delta_zone->min_keys + delta) / in set_delta()
1407 delta_zone->incr_keys)); in set_delta()
1409 delta_entry->delta = delta; in set_delta()
1410 delta_entry->entry_bits = delta_entry->value_bits + key_bits; in set_delta()
1415 u64 offset = get_delta_entry_offset(entry) + entry->entry_bits - COLLISION_BITS; in get_collision_name()
1416 const u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE; in get_collision_name()
1420 while (--size >= 0) in get_collision_name()
1426 u64 offset = get_delta_entry_offset(entry) + entry->entry_bits - COLLISION_BITS; in set_collision_name()
1427 u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE; in set_collision_name()
1433 while (--size >= 0) { in set_collision_name()
1454 } while (!delta_entry->at_end && (key > delta_entry->key)); in uds_get_delta_index_entry()
1460 if (!delta_entry->at_end && (key == delta_entry->key)) { in uds_get_delta_index_entry()
1492 result = VDO_ASSERT(delta_entry->is_collision, in uds_get_delta_entry_collision()
1493 "Cannot get full block name from a non-collision delta index entry"); in uds_get_delta_entry_collision()
1503 return get_field(delta_entry->delta_zone->memory, in uds_get_delta_entry_value()
1504 get_delta_entry_offset(delta_entry), delta_entry->value_bits); in uds_get_delta_entry_value()
1509 int result = VDO_ASSERT((delta_entry->delta_list != &delta_entry->temp_delta_list), in assert_mutable_entry()
1520 u32 value_mask = (1 << delta_entry->value_bits) - 1; in uds_set_delta_entry_value()
1531 "Value (%u) being set in a delta index is too large (must fit in %u bits)", in uds_set_delta_entry_value()
1532 value, delta_entry->value_bits); in uds_set_delta_entry_value()
1536 set_field(value, delta_entry->delta_zone->memory, in uds_set_delta_entry_value()
1537 get_delta_entry_offset(delta_entry), delta_entry->value_bits); in uds_set_delta_entry_value()
1557 delta_lists = delta_zone->delta_lists; in extend_delta_zone()
1559 for (i = 0; i <= delta_zone->list_count + 1; i++) in extend_delta_zone()
1562 if (delta_zone->size < used_space) in extend_delta_zone()
1572 rebalance_delta_zone(delta_zone, 1, delta_zone->list_count + 1); in extend_delta_zone()
1574 delta_zone->rebalance_count++; in extend_delta_zone()
1575 delta_zone->rebalance_time += ktime_sub(end_time, start_time); in extend_delta_zone()
1588 struct delta_zone *delta_zone = delta_entry->delta_zone; in insert_bits()
1589 struct delta_list *delta_list = delta_entry->delta_list; in insert_bits()
1591 u32 total_size = delta_list->size; in insert_bits()
1592 u32 before_size = delta_entry->offset; in insert_bits()
1593 u32 after_size = total_size - delta_entry->offset; in insert_bits()
1596 delta_entry->list_overflow = true; in insert_bits()
1597 delta_zone->overflow_count++; in insert_bits()
1602 free_before = (delta_list[0].start - (delta_list[-1].start + delta_list[-1].size)); in insert_bits()
1603 free_after = (delta_list[1].start - (delta_list[0].start + delta_list[0].size)); in insert_bits()
1630 u32 growing_index = delta_entry->list_number + 1; in insert_bits()
1641 delta_list->size += size; in insert_bits()
1643 source = delta_list->start; in insert_bits()
1644 destination = source - size; in insert_bits()
1645 delta_list->start -= size; in insert_bits()
1648 source = delta_list->start + delta_entry->offset; in insert_bits()
1653 memory = delta_zone->memory; in insert_bits()
1664 const struct delta_zone *delta_zone = delta_entry->delta_zone; in encode_delta()
1665 u8 *memory = delta_zone->memory; in encode_delta()
1667 offset = get_delta_entry_offset(delta_entry) + delta_entry->value_bits; in encode_delta()
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()
1674 t1 = (temp % delta_zone->incr_keys) + delta_zone->min_keys; in encode_delta()
1675 t2 = temp / delta_zone->incr_keys; in encode_delta()
1676 set_field(t1, memory, offset, delta_zone->min_bits); in encode_delta()
1677 set_zero(memory, offset + delta_zone->min_bits, t2); in encode_delta()
1678 set_field(1, memory, offset + delta_zone->min_bits + t2, 1); in encode_delta()
1684 u8 *memory = delta_entry->delta_zone->memory; in encode_entry()
1687 set_field(value, memory, offset, delta_entry->value_bits); in encode_entry()
1694 * Create a new entry in the delta index. If the entry is a collision, the full 256 bit name must
1707 if (delta_entry->is_collision) { in uds_put_delta_index_entry()
1709 * The caller wants us to insert a collision entry onto a collision entry. This in uds_put_delta_index_entry()
1710 * happens when we find a collision and attempt to add the name again to the index. in uds_put_delta_index_entry()
1711 * This is normally a fatal error unless we are replaying a closed chapter while we in uds_put_delta_index_entry()
1712 * are rebuilding a volume index. in uds_put_delta_index_entry()
1717 if (delta_entry->offset < delta_entry->delta_list->save_offset) { in uds_put_delta_index_entry()
1728 /* Insert a collision entry which is placed after this entry. */ in uds_put_delta_index_entry()
1733 result = VDO_ASSERT((key == delta_entry->key), in uds_put_delta_index_entry()
1738 delta_entry->offset += delta_entry->entry_bits; in uds_put_delta_index_entry()
1740 delta_entry->is_collision = true; in uds_put_delta_index_entry()
1741 delta_entry->entry_bits += COLLISION_BITS; in uds_put_delta_index_entry()
1742 result = insert_bits(delta_entry, delta_entry->entry_bits); in uds_put_delta_index_entry()
1743 } else if (delta_entry->at_end) { in uds_put_delta_index_entry()
1744 /* Insert a new entry at the end of the delta list. */ in uds_put_delta_index_entry()
1745 result = VDO_ASSERT((key >= delta_entry->key), "key past end of list"); in uds_put_delta_index_entry()
1749 set_delta(delta_entry, key - delta_entry->key); in uds_put_delta_index_entry()
1750 delta_entry->key = key; in uds_put_delta_index_entry()
1751 delta_entry->at_end = false; in uds_put_delta_index_entry()
1752 result = insert_bits(delta_entry, delta_entry->entry_bits); 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()
1763 result = VDO_ASSERT((key < delta_entry->key), in uds_put_delta_index_entry()
1768 result = VDO_ASSERT((key >= delta_entry->key - delta_entry->delta), in uds_put_delta_index_entry()
1773 old_entry_size = delta_entry->entry_bits; in uds_put_delta_index_entry()
1776 set_delta(delta_entry, key - (delta_entry->key - delta_entry->delta)); in uds_put_delta_index_entry()
1777 delta_entry->key = key; in uds_put_delta_index_entry()
1778 set_delta(&next_entry, next_entry.key - key); in uds_put_delta_index_entry()
1779 next_entry.offset += delta_entry->entry_bits; in uds_put_delta_index_entry()
1781 additional_size = (delta_entry->entry_bits + in uds_put_delta_index_entry()
1782 next_entry.entry_bits - old_entry_size); in uds_put_delta_index_entry()
1794 delta_zone = delta_entry->delta_zone; in uds_put_delta_index_entry()
1795 delta_zone->record_count++; in uds_put_delta_index_entry()
1796 delta_zone->collision_count += delta_entry->is_collision ? 1 : 0; in uds_put_delta_index_entry()
1806 struct delta_list *delta_list = delta_entry->delta_list; in delete_bits()
1807 u8 *memory = delta_entry->delta_zone->memory; in delete_bits()
1809 u32 total_size = delta_list->size; in delete_bits()
1810 u32 before_size = delta_entry->offset; in delete_bits()
1811 u32 after_size = total_size - delta_entry->offset - size; in delete_bits()
1824 (delta_list[0].start - (delta_list[-1].start + delta_list[-1].size)); in delete_bits()
1826 (delta_list[1].start - (delta_list[0].start + delta_list[0].size)); in delete_bits()
1831 delta_list->size -= size; in delete_bits()
1833 source = delta_list->start; in delete_bits()
1835 delta_list->start += size; in delete_bits()
1838 destination = delta_list->start + delta_entry->offset; in delete_bits()
1862 delta_zone = delta_entry->delta_zone; in uds_remove_delta_index_entry()
1864 if (delta_entry->is_collision) { in uds_remove_delta_index_entry()
1865 /* This is a collision entry, so just remove it. */ in uds_remove_delta_index_entry()
1866 delete_bits(delta_entry, delta_entry->entry_bits); in uds_remove_delta_index_entry()
1867 next_entry.offset = delta_entry->offset; in uds_remove_delta_index_entry()
1868 delta_zone->collision_count -= 1; in uds_remove_delta_index_entry()
1871 delete_bits(delta_entry, delta_entry->entry_bits); in uds_remove_delta_index_entry()
1872 next_entry.key -= delta_entry->delta; in uds_remove_delta_index_entry()
1873 next_entry.offset = delta_entry->offset; in uds_remove_delta_index_entry()
1877 u16 old_size = delta_entry->entry_bits + next_entry.entry_bits; in uds_remove_delta_index_entry()
1881 delta_zone->collision_count -= 1; in uds_remove_delta_index_entry()
1884 set_delta(&next_entry, delta_entry->delta + next_entry.delta); in uds_remove_delta_index_entry()
1885 next_entry.offset = delta_entry->offset; in uds_remove_delta_index_entry()
1887 delete_bits(delta_entry, old_size - next_entry.entry_bits); in uds_remove_delta_index_entry()
1891 delta_zone->record_count--; in uds_remove_delta_index_entry()
1892 delta_zone->discard_count++; in uds_remove_delta_index_entry()
1895 delta_list = delta_entry->delta_list; in uds_remove_delta_index_entry()
1896 if (delta_entry->offset < delta_list->save_offset) { in uds_remove_delta_index_entry()
1898 delta_list->save_key = 0; in uds_remove_delta_index_entry()
1899 delta_list->save_offset = 0; in uds_remove_delta_index_entry()
1908 unsigned int z; in uds_get_delta_index_stats() local
1912 for (z = 0; z < delta_index->zone_count; z++) { in uds_get_delta_index_stats()
1913 delta_zone = &delta_index->delta_zones[z]; in uds_get_delta_index_stats()
1914 stats->rebalance_time += delta_zone->rebalance_time; in uds_get_delta_index_stats()
1915 stats->rebalance_count += delta_zone->rebalance_count; in uds_get_delta_index_stats()
1916 stats->record_count += delta_zone->record_count; in uds_get_delta_index_stats()
1917 stats->collision_count += delta_zone->collision_count; in uds_get_delta_index_stats()
1918 stats->discard_count += delta_zone->discard_count; in uds_get_delta_index_stats()
1919 stats->overflow_count += delta_zone->overflow_count; in uds_get_delta_index_stats()
1920 stats->list_count += delta_zone->list_count; in uds_get_delta_index_stats()
1950 bits_per_page = ((bytes_per_page - sizeof(struct delta_page_header)) * BITS_PER_BYTE); in uds_get_delta_index_page_count()
1955 bits_per_page -= IMMUTABLE_HEADER_SIZE + bits_per_delta_list; in uds_get_delta_index_page_count()
1964 delta_entry->list_number, delta_entry->key, in uds_log_delta_index_entry()
1965 delta_entry->offset, delta_entry->at_end ? " end" : "", in uds_log_delta_index_entry()
1966 delta_entry->is_collision ? " collision" : "", in uds_log_delta_index_entry()
1967 delta_entry->delta_list->size, in uds_log_delta_index_entry()
1968 delta_entry->list_overflow ? " overflow" : ""); in uds_log_delta_index_entry()
1969 delta_entry->list_overflow = false; in uds_log_delta_index_entry()