dm-vdo/indexer/delta-index.c

28  * memory managed by the delta_zone structure. The delta_zone can move the data around within its
55  * some bytes beyond the end of the bit field, so a delta_zone memory allocation is guarded by two
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
154 static void rebalance_delta_zone(const struct delta_zone *delta_zone, u32 first,
162 		delta_list = &delta_zone->delta_lists[first];
163 		new_start = delta_zone->new_offsets[first];
171 			memmove(delta_zone->memory + destination,
172 				delta_zone->memory + source,
183 		delta_list = &delta_zone->delta_lists[middle];
184 		new_start = delta_zone->new_offsets[middle];
191 			rebalance_delta_zone(delta_zone, middle + 1, last);
192 			rebalance_delta_zone(delta_zone, first, middle);
194 			rebalance_delta_zone(delta_zone, first, middle);
195 			rebalance_delta_zone(delta_zone, middle + 1, last);
222 		struct delta_zone *zone = &delta_index->delta_zones[z];
308 static int initialize_delta_zone(struct delta_zone *delta_zone, size_t size,
314 	result = vdo_allocate(size, u8, "delta list", &delta_zone->memory);
319 			      &delta_zone->new_offsets);
325 			      &delta_zone->delta_lists);
329 	compute_coding_constants(mean_delta, &delta_zone->min_bits,
330 				 &delta_zone->min_keys, &delta_zone->incr_keys);
331 	delta_zone->value_bits = payload_bits;
332 	delta_zone->buffered_writer = NULL;
333 	delta_zone->size = size;
334 	delta_zone->rebalance_time = 0;
335 	delta_zone->rebalance_count = 0;
336 	delta_zone->record_count = 0;
337 	delta_zone->collision_count = 0;
338 	delta_zone->discard_count = 0;
339 	delta_zone->overflow_count = 0;
340 	delta_zone->first_list = first_list;
341 	delta_zone->list_count = list_count;
342 	delta_zone->tag = tag;
355 	result = vdo_allocate(zone_count, struct delta_zone, "Delta Index Zones",
395 			(sizeof(struct delta_zone) + zone_memory +
502 	struct delta_zone *delta_zone = &delta_index_page->delta_zone;
530 	delta_index_page->delta_index.delta_zones = delta_zone;
540 	compute_coding_constants(mean_delta, &delta_zone->min_bits,
541 				 &delta_zone->min_keys, &delta_zone->incr_keys);
542 	delta_zone->value_bits = payload_bits;
543 	delta_zone->memory = memory;
544 	delta_zone->delta_lists = NULL;
545 	delta_zone->new_offsets = NULL;
546 	delta_zone->buffered_writer = NULL;
547 	delta_zone->size = memory_size;
548 	delta_zone->rebalance_time = 0;
549 	delta_zone->rebalance_count = 0;
550 	delta_zone->record_count = 0;
551 	delta_zone->collision_count = 0;
552 	delta_zone->discard_count = 0;
553 	delta_zone->overflow_count = 0;
554 	delta_zone->first_list = 0;
555 	delta_zone->list_count = list_count;
556 	delta_zone->tag = 'p';
711 	const struct delta_zone *delta_zone;
721 	delta_zone = &delta_index->delta_zones[0];
722 	delta_lists = &delta_zone->delta_lists[first_list + 1];
769 		move_bits(delta_zone->memory, delta_lists[i].start, memory,
780 static void compute_new_list_offsets(struct delta_zone *delta_zone, u32 growing_index,
785 	struct delta_list *delta_lists = delta_zone->delta_lists;
786 	u32 tail_guard_index = delta_zone->list_count + 1;
788 	spacing = (delta_zone->size - used_space) / delta_zone->list_count;
789 	delta_zone->new_offsets[0] = 0;
790 	for (i = 0; i <= delta_zone->list_count; i++) {
791 		delta_zone->new_offsets[i + 1] =
792 			(delta_zone->new_offsets[i] +
794 		delta_zone->new_offsets[i] *= BITS_PER_BYTE;
795 		delta_zone->new_offsets[i] += delta_lists[i].start % BITS_PER_BYTE;
797 			delta_zone->new_offsets[i + 1] -= spacing / 2;
799 			delta_zone->new_offsets[i + 1] += growing_size;
802 	delta_zone->new_offsets[tail_guard_index] =
803 		(delta_zone->size * BITS_PER_BYTE - delta_lists[tail_guard_index].size);
806 static void rebalance_lists(struct delta_zone *delta_zone)
813 	delta_lists = delta_zone->delta_lists;
814 	for (i = 0; i <= delta_zone->list_count + 1; i++)
817 	compute_new_list_offsets(delta_zone, 0, 0, used_space);
818 	for (i = 1; i <= delta_zone->list_count + 1; i++)
819 		delta_lists[i].start = delta_zone->new_offsets[i];
835 	const struct delta_zone *delta_zone;
940 			delta_zone = &delta_index->delta_zones[zone_number];
941 			list_number -= delta_zone->first_list;
942 			delta_zone->delta_lists[list_number + 1].size = delta_list_size;
953 static int restore_delta_list_to_zone(struct delta_zone *delta_zone,
960 	u32 list_number = save_info->index - delta_zone->first_list;
962 	if (list_number >= delta_zone->list_count) {
965 						save_info->index, delta_zone->first_list,
966 						delta_zone->first_list + delta_zone->list_count);
969 	delta_list = &delta_zone->delta_lists[list_number + 1];
984 	move_bits(data, save_info->bit_offset, delta_zone->memory, delta_list->start,
1089 static int flush_delta_list(struct delta_zone *zone, u32 flush_index)
1125 	struct delta_zone *delta_zone;
1129 	delta_zone = &delta_index->delta_zones[zone_number];
1134 	encode_u32_le(buffer, &offset, delta_zone->first_list);
1135 	encode_u32_le(buffer, &offset, delta_zone->list_count);
1136 	encode_u64_le(buffer, &offset, delta_zone->record_count);
1137 	encode_u64_le(buffer, &offset, delta_zone->collision_count);
1150 	for (i = 0; i < delta_zone->list_count; i++) {
1154 		delta_list = &delta_zone->delta_lists[i + 1];
1163 	delta_zone->buffered_writer = buffered_writer;
1173 	struct delta_zone *delta_zone;
1176 	delta_zone = &delta_index->delta_zones[zone_number];
1177 	for (i = 0; i < delta_zone->list_count; i++) {
1178 		delta_list = &delta_zone->delta_lists[i + 1];
1180 			result = flush_delta_list(delta_zone, i);
1186 	delta_zone->buffered_writer = NULL;
1236 	struct delta_zone *delta_zone;
1246 	delta_zone = &delta_index->delta_zones[zone_number];
1247 	list_number -= delta_zone->first_list;
1248 	result = VDO_ASSERT((list_number < delta_zone->list_count),
1250 			    list_number, delta_zone->list_count, zone_number);
1255 		delta_list = &delta_zone->delta_lists[list_number + 1];
1264 		delta_list->start = get_immutable_start(delta_zone->memory, list_number);
1265 		end_offset = get_immutable_start(delta_zone->memory, list_number + 1);
1282 			uds_prefetch_range(&delta_zone->memory[delta_list->start / BITS_PER_BYTE],
1288 	delta_entry->delta_zone = delta_zone;
1294 	delta_entry->value_bits = delta_zone->value_bits;
1312 	const struct delta_zone *delta_zone = delta_entry->delta_zone;
1313 	const u8 *memory = delta_zone->memory;
1320 	key_bits = delta_zone->min_bits;
1322 	if (delta >= delta_zone->min_keys) {
1332 		delta += ((key_bits - delta_zone->min_bits - 1) * delta_zone->incr_keys);
1404 	const struct delta_zone *delta_zone = delta_entry->delta_zone;
1405 	u32 key_bits = (delta_zone->min_bits +
1406 			((delta_zone->incr_keys - delta_zone->min_keys + delta) /
1407 			 delta_zone->incr_keys));
1416 	const u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE;
1427 	u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE;
1503 	return get_field(delta_entry->delta_zone->memory,
1536 	set_field(value, delta_entry->delta_zone->memory,
1545 static int extend_delta_zone(struct delta_zone *delta_zone, u32 growing_index,
1557 	delta_lists = delta_zone->delta_lists;
1559 	for (i = 0; i <= delta_zone->list_count + 1; i++)
1562 	if (delta_zone->size < used_space)
1566 	compute_new_list_offsets(delta_zone, growing_index, growing_size, used_space);
1572 	rebalance_delta_zone(delta_zone, 1, delta_zone->list_count + 1);
1574 	delta_zone->rebalance_count++;
1575 	delta_zone->rebalance_time += ktime_sub(end_time, start_time);
1588 	struct delta_zone *delta_zone = delta_entry->delta_zone;
1597 		delta_zone->overflow_count++;
1635 		result = extend_delta_zone(delta_zone, growing_index,
1653 	memory = delta_zone->memory;
1664 	const struct delta_zone *delta_zone = delta_entry->delta_zone;
1665 	u8 *memory = delta_zone->memory;
1668 	if (delta_entry->delta < delta_zone->min_keys) {
1669 		set_field(delta_entry->delta, memory, offset, delta_zone->min_bits);
1673 	temp = delta_entry->delta - delta_zone->min_keys;
1674 	t1 = (temp % delta_zone->incr_keys) + delta_zone->min_keys;
1675 	t2 = temp / delta_zone->incr_keys;
1676 	set_field(t1, memory, offset, delta_zone->min_bits);
1677 	set_zero(memory, offset + delta_zone->min_bits, t2);
1678 	set_field(1, memory, offset + delta_zone->min_bits + t2, 1);
1684 	u8 *memory = delta_entry->delta_zone->memory;
1701 	struct delta_zone *delta_zone;
1794 	delta_zone = delta_entry->delta_zone;
1795 	delta_zone->record_count++;
1796 	delta_zone->collision_count += delta_entry->is_collision ? 1 : 0;
1807 	u8 *memory = delta_entry->delta_zone->memory;
1850 	struct delta_zone *delta_zone;
1862 	delta_zone = delta_entry->delta_zone;
1868 		delta_zone->collision_count -= 1;
1881 			delta_zone->collision_count -= 1;
1891 	delta_zone->record_count--;
1892 	delta_zone->discard_count++;
1909 	const struct delta_zone *delta_zone;
1913 		delta_zone = &delta_index->delta_zones[z];
1914 		stats->rebalance_time += delta_zone->rebalance_time;
1915 		stats->rebalance_count += delta_zone->rebalance_count;
1916 		stats->record_count += delta_zone->record_count;
1917 		stats->collision_count += delta_zone->collision_count;
1918 		stats->discard_count += delta_zone->discard_count;
1919 		stats->overflow_count += delta_zone->overflow_count;
1920 		stats->list_count += delta_zone->list_count;