Lines Matching refs:delta_zone
154 static void rebalance_delta_zone(const struct delta_zone *delta_zone, u32 first, in rebalance_delta_zone() argument
162 delta_list = &delta_zone->delta_lists[first]; in rebalance_delta_zone()
163 new_start = delta_zone->new_offsets[first]; 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()
191 rebalance_delta_zone(delta_zone, middle + 1, last); in rebalance_delta_zone()
192 rebalance_delta_zone(delta_zone, first, middle); in rebalance_delta_zone()
194 rebalance_delta_zone(delta_zone, first, middle); in rebalance_delta_zone()
195 rebalance_delta_zone(delta_zone, middle + 1, last); in rebalance_delta_zone()
222 struct delta_zone *zone = &delta_index->delta_zones[z]; in uds_reset_delta_index()
308 static int initialize_delta_zone(struct delta_zone *delta_zone, size_t size, in initialize_delta_zone() argument
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()
355 result = vdo_allocate(zone_count, struct delta_zone, "Delta Index Zones", in uds_initialize_delta_index()
395 (sizeof(struct delta_zone) + zone_memory + in uds_initialize_delta_index()
502 struct delta_zone *delta_zone = &delta_index_page->delta_zone; in uds_initialize_delta_index_page() local
530 delta_index_page->delta_index.delta_zones = delta_zone; 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()
711 const struct delta_zone *delta_zone; in uds_pack_delta_index_page() local
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()
769 move_bits(delta_zone->memory, delta_lists[i].start, memory, in uds_pack_delta_index_page()
780 static void compute_new_list_offsets(struct delta_zone *delta_zone, u32 growing_index, in compute_new_list_offsets() argument
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()
806 static void rebalance_lists(struct delta_zone *delta_zone) in rebalance_lists() argument
813 delta_lists = delta_zone->delta_lists; in rebalance_lists()
814 for (i = 0; i <= delta_zone->list_count + 1; i++) in rebalance_lists()
817 compute_new_list_offsets(delta_zone, 0, 0, used_space); 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()
835 const struct delta_zone *delta_zone; in uds_start_restoring_delta_index() local
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()
953 static int restore_delta_list_to_zone(struct delta_zone *delta_zone, in restore_delta_list_to_zone() argument
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()
984 move_bits(data, save_info->bit_offset, delta_zone->memory, delta_list->start, in restore_delta_list_to_zone()
1089 static int flush_delta_list(struct delta_zone *zone, u32 flush_index) in flush_delta_list()
1125 struct delta_zone *delta_zone; in uds_start_saving_delta_index() local
1129 delta_zone = &delta_index->delta_zones[zone_number]; 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()
1163 delta_zone->buffered_writer = buffered_writer; in uds_start_saving_delta_index()
1173 struct delta_zone *delta_zone; in uds_finish_saving_delta_index() local
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()
1180 result = flush_delta_list(delta_zone, i); in uds_finish_saving_delta_index()
1186 delta_zone->buffered_writer = NULL; in uds_finish_saving_delta_index()
1236 struct delta_zone *delta_zone; in uds_start_delta_index_search() local
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()
1255 delta_list = &delta_zone->delta_lists[list_number + 1]; 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()
1282 uds_prefetch_range(&delta_zone->memory[delta_list->start / BITS_PER_BYTE], in uds_start_delta_index_search()
1288 delta_entry->delta_zone = delta_zone; in uds_start_delta_index_search()
1294 delta_entry->value_bits = delta_zone->value_bits; in uds_start_delta_index_search()
1312 const struct delta_zone *delta_zone = delta_entry->delta_zone; in decode_delta() local
1313 const u8 *memory = delta_zone->memory; in decode_delta()
1320 key_bits = delta_zone->min_bits; 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()
1404 const struct delta_zone *delta_zone = delta_entry->delta_zone; in set_delta() local
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()
1416 const u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE; in get_collision_name()
1427 u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE; in set_collision_name()
1503 return get_field(delta_entry->delta_zone->memory, in uds_get_delta_entry_value()
1536 set_field(value, delta_entry->delta_zone->memory, in uds_set_delta_entry_value()
1545 static int extend_delta_zone(struct delta_zone *delta_zone, u32 growing_index, in extend_delta_zone() argument
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()
1566 compute_new_list_offsets(delta_zone, growing_index, growing_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() local
1597 delta_zone->overflow_count++; in insert_bits()
1635 result = extend_delta_zone(delta_zone, growing_index, 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() local
1665 u8 *memory = delta_zone->memory; 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()
1701 struct delta_zone *delta_zone; in uds_put_delta_index_entry() local
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()
1807 u8 *memory = delta_entry->delta_zone->memory; in delete_bits()
1850 struct delta_zone *delta_zone; in uds_remove_delta_index_entry() local
1862 delta_zone = delta_entry->delta_zone; in uds_remove_delta_index_entry()
1868 delta_zone->collision_count -= 1; in uds_remove_delta_index_entry()
1881 delta_zone->collision_count -= 1; 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()
1909 const struct delta_zone *delta_zone; in uds_get_delta_index_stats() local
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()