delta_zone
static int flush_delta_list(struct delta_zone *zone, u32 flush_index)
struct delta_zone *delta_zone;
delta_zone = &delta_index->delta_zones[zone_number];
encode_u32_le(buffer, &offset, delta_zone->first_list);
encode_u32_le(buffer, &offset, delta_zone->list_count);
encode_u64_le(buffer, &offset, delta_zone->record_count);
encode_u64_le(buffer, &offset, delta_zone->collision_count);
for (i = 0; i < delta_zone->list_count; i++) {
delta_list = &delta_zone->delta_lists[i + 1];
delta_zone->buffered_writer = buffered_writer;
struct delta_zone *delta_zone;
delta_zone = &delta_index->delta_zones[zone_number];
for (i = 0; i < delta_zone->list_count; i++) {
delta_list = &delta_zone->delta_lists[i + 1];
result = flush_delta_list(delta_zone, i);
delta_zone->buffered_writer = NULL;
struct delta_zone *delta_zone;
delta_zone = &delta_index->delta_zones[zone_number];
list_number -= delta_zone->first_list;
result = VDO_ASSERT((list_number < delta_zone->list_count),
list_number, delta_zone->list_count, zone_number);
delta_list = &delta_zone->delta_lists[list_number + 1];
delta_list->start = get_immutable_start(delta_zone->memory, list_number);
end_offset = get_immutable_start(delta_zone->memory, list_number + 1);
uds_prefetch_range(&delta_zone->memory[delta_list->start / BITS_PER_BYTE],
delta_entry->delta_zone = delta_zone;
delta_entry->value_bits = delta_zone->value_bits;
const struct delta_zone *delta_zone = delta_entry->delta_zone;
const u8 *memory = delta_zone->memory;
key_bits = delta_zone->min_bits;
if (delta >= delta_zone->min_keys) {
delta += ((key_bits - delta_zone->min_bits - 1) * delta_zone->incr_keys);
const struct delta_zone *delta_zone = delta_entry->delta_zone;
u32 key_bits = (delta_zone->min_bits +
((delta_zone->incr_keys - delta_zone->min_keys + delta) /
delta_zone->incr_keys));
const u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE;
u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE;
return get_field(delta_entry->delta_zone->memory,
set_field(value, delta_entry->delta_zone->memory,
static void rebalance_delta_zone(const struct delta_zone *delta_zone, u32 first,
static int extend_delta_zone(struct delta_zone *delta_zone, u32 growing_index,
delta_lists = delta_zone->delta_lists;
for (i = 0; i <= delta_zone->list_count + 1; i++)
if (delta_zone->size < used_space)
compute_new_list_offsets(delta_zone, growing_index, growing_size, used_space);
rebalance_delta_zone(delta_zone, 1, delta_zone->list_count + 1);
delta_zone->rebalance_count++;
delta_zone->rebalance_time += ktime_sub(end_time, start_time);
struct delta_zone *delta_zone = delta_entry->delta_zone;
delta_zone->overflow_count++;
delta_list = &delta_zone->delta_lists[first];
new_start = delta_zone->new_offsets[first];
result = extend_delta_zone(delta_zone, growing_index,
memory = delta_zone->memory;
const struct delta_zone *delta_zone = delta_entry->delta_zone;
u8 *memory = delta_zone->memory;
if (delta_entry->delta < delta_zone->min_keys) {
set_field(delta_entry->delta, memory, offset, delta_zone->min_bits);
temp = delta_entry->delta - delta_zone->min_keys;
t1 = (temp % delta_zone->incr_keys) + delta_zone->min_keys;
t2 = temp / delta_zone->incr_keys;
set_field(t1, memory, offset, delta_zone->min_bits);
set_zero(memory, offset + delta_zone->min_bits, t2);
set_field(1, memory, offset + delta_zone->min_bits + t2, 1);
u8 *memory = delta_entry->delta_zone->memory;
struct delta_zone *delta_zone;
memmove(delta_zone->memory + destination,
delta_zone->memory + source,
delta_zone = delta_entry->delta_zone;
delta_zone->record_count++;
delta_zone->collision_count += delta_entry->is_collision ? 1 : 0;
u8 *memory = delta_entry->delta_zone->memory;
delta_list = &delta_zone->delta_lists[middle];
new_start = delta_zone->new_offsets[middle];
struct delta_zone *delta_zone;
delta_zone = delta_entry->delta_zone;
delta_zone->collision_count -= 1;
delta_zone->collision_count -= 1;
delta_zone->record_count--;
delta_zone->discard_count++;
const struct delta_zone *delta_zone;
rebalance_delta_zone(delta_zone, middle + 1, last);
delta_zone = &delta_index->delta_zones[z];
stats->rebalance_time += delta_zone->rebalance_time;
stats->rebalance_count += delta_zone->rebalance_count;
stats->record_count += delta_zone->record_count;
stats->collision_count += delta_zone->collision_count;
stats->discard_count += delta_zone->discard_count;
stats->overflow_count += delta_zone->overflow_count;
stats->list_count += delta_zone->list_count;
rebalance_delta_zone(delta_zone, first, middle);
rebalance_delta_zone(delta_zone, first, middle);
rebalance_delta_zone(delta_zone, middle + 1, last);
struct delta_zone *zone = &delta_index->delta_zones[z];
static int initialize_delta_zone(struct delta_zone *delta_zone, size_t size,
result = vdo_allocate(size, "delta list", &delta_zone->memory);
result = vdo_allocate(list_count + 2, "delta list temp", &delta_zone->new_offsets);
result = vdo_allocate(list_count + 2, "delta lists", &delta_zone->delta_lists);
compute_coding_constants(mean_delta, &delta_zone->min_bits,
&delta_zone->min_keys, &delta_zone->incr_keys);
delta_zone->value_bits = payload_bits;
delta_zone->buffered_writer = NULL;
delta_zone->size = size;
delta_zone->rebalance_time = 0;
delta_zone->rebalance_count = 0;
delta_zone->record_count = 0;
delta_zone->collision_count = 0;
delta_zone->discard_count = 0;
delta_zone->overflow_count = 0;
delta_zone->first_list = first_list;
delta_zone->list_count = list_count;
delta_zone->tag = tag;
(sizeof(struct delta_zone) + zone_memory +
struct delta_zone *delta_zone = &delta_index_page->delta_zone;
delta_index_page->delta_index.delta_zones = delta_zone;
compute_coding_constants(mean_delta, &delta_zone->min_bits,
&delta_zone->min_keys, &delta_zone->incr_keys);
delta_zone->value_bits = payload_bits;
delta_zone->memory = memory;
delta_zone->delta_lists = NULL;
delta_zone->new_offsets = NULL;
delta_zone->buffered_writer = NULL;
delta_zone->size = memory_size;
delta_zone->rebalance_time = 0;
delta_zone->rebalance_count = 0;
delta_zone->record_count = 0;
delta_zone->collision_count = 0;
delta_zone->discard_count = 0;
delta_zone->overflow_count = 0;
delta_zone->first_list = 0;
delta_zone->list_count = list_count;
delta_zone->tag = 'p';
const struct delta_zone *delta_zone;
delta_zone = &delta_index->delta_zones[0];
delta_lists = &delta_zone->delta_lists[first_list + 1];
move_bits(delta_zone->memory, delta_lists[i].start, memory,
static void compute_new_list_offsets(struct delta_zone *delta_zone, u32 growing_index,
struct delta_list *delta_lists = delta_zone->delta_lists;
u32 tail_guard_index = delta_zone->list_count + 1;
spacing = (delta_zone->size - used_space) / delta_zone->list_count;
delta_zone->new_offsets[0] = 0;
for (i = 0; i <= delta_zone->list_count; i++) {
delta_zone->new_offsets[i + 1] =
(delta_zone->new_offsets[i] +
delta_zone->new_offsets[i] *= BITS_PER_BYTE;
delta_zone->new_offsets[i] += delta_lists[i].start % BITS_PER_BYTE;
delta_zone->new_offsets[i + 1] -= spacing / 2;
delta_zone->new_offsets[i + 1] += growing_size;
delta_zone->new_offsets[tail_guard_index] =
(delta_zone->size * BITS_PER_BYTE - delta_lists[tail_guard_index].size);
static void rebalance_lists(struct delta_zone *delta_zone)
delta_lists = delta_zone->delta_lists;
for (i = 0; i <= delta_zone->list_count + 1; i++)
compute_new_list_offsets(delta_zone, 0, 0, used_space);
for (i = 1; i <= delta_zone->list_count + 1; i++)
delta_lists[i].start = delta_zone->new_offsets[i];
const struct delta_zone *delta_zone;
delta_zone = &delta_index->delta_zones[zone_number];
list_number -= delta_zone->first_list;
delta_zone->delta_lists[list_number + 1].size = delta_list_size;
static int restore_delta_list_to_zone(struct delta_zone *delta_zone,
u32 list_number = save_info->index - delta_zone->first_list;
if (list_number >= delta_zone->list_count) {
save_info->index, delta_zone->first_list,
delta_zone->first_list + delta_zone->list_count);
delta_list = &delta_zone->delta_lists[list_number + 1];
move_bits(data, save_info->bit_offset, delta_zone->memory, delta_list->start,
struct delta_zone delta_zone;
struct delta_zone *delta_zone;
struct delta_zone *delta_zones;
struct delta_zone *delta_zone;
delta_zone = &sub_index->delta_index.delta_zones[zone_number];
for (i = 1; i <= delta_zone->list_count; i++)
used_bits += delta_zone->delta_lists[i].size;