1971 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright 2023 Red Hat4 */5#include "delta-index.h"6 7#include <linux/bitops.h>8#include <linux/bits.h>9#include <linux/compiler.h>10#include <linux/limits.h>11#include <linux/log2.h>12 13#include "cpu.h"14#include "errors.h"15#include "logger.h"16#include "memory-alloc.h"17#include "numeric.h"18#include "permassert.h"19#include "string-utils.h"20#include "time-utils.h"21 22#include "config.h"23#include "indexer.h"24 25/*26 * The entries in a delta index could be stored in a single delta list, but to reduce search times27 * and update costs it uses multiple delta lists. These lists are stored in a single chunk of28 * memory managed by the delta_zone structure. The delta_zone can move the data around within its29 * memory, so the location of each delta list is recorded as a bit offset into the memory. Because30 * the volume index can contain over a million delta lists, we want to be efficient with the size31 * of the delta list header information. This information is encoded into 16 bytes per list. The32 * volume index delta list memory can easily exceed 4 gigabits, so a 64 bit value is needed to33 * address the memory. The volume index delta lists average around 6 kilobits, so 16 bits are34 * sufficient to store the size of a delta list.35 *36 * Each delta list is stored as a bit stream. Within the delta list encoding, bits and bytes are37 * numbered in little endian order. Within a byte, bit 0 is the least significant bit (0x1), and38 * bit 7 is the most significant bit (0x80). Within a bit stream, bit 7 is the most significant bit39 * of byte 0, and bit 8 is the least significant bit of byte 1. Within a byte array, a byte's40 * number corresponds to its index in the array.41 *42 * A standard delta list entry is stored as a fixed length payload (the value) followed by a43 * variable length key (the delta). A collision entry is used when two block names have the same44 * delta list address. A collision entry always follows a standard entry for the hash with which it45 * 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 list47 * indicates a normal entry.48 *49 * The delta in each entry is encoded with a variable-length Huffman code to minimize the memory50 * used by small deltas. The Huffman code is specified by three parameters, which can be computed51 * from the desired mean delta when the index is full. (See compute_coding_constants() for52 * details.)53 *54 * The bit field utilities used to read and write delta entries assume that it is possible to read55 * some bytes beyond the end of the bit field, so a delta_zone memory allocation is guarded by two56 * invalid delta lists to prevent reading outside the delta_zone memory. The valid delta lists are57 * numbered 1 to N, and the guard lists are numbered 0 and N+1. The function to decode the bit58 * stream include a step that skips over bits set to 0 until the first 1 bit is found. A corrupted59 * delta list could cause this step to run off the end of the delta_zone memory, so as extra60 * protection against this happening, the tail guard list is set to all ones.61 *62 * The delta_index supports two different forms. The mutable form is created by63 * uds_initialize_delta_index(), and is used for the volume index and for open chapter indexes. The64 * immutable form is created by uds_initialize_delta_index_page(), and is used for closed (and65 * cached) chapter index pages. The immutable form does not allocate delta list headers or66 * temporary offsets, and thus is somewhat more memory efficient.67 */68 69/*70 * This is the largest field size supported by get_field() and set_field(). Any field that is71 * larger is not guaranteed to fit in a single byte-aligned u32.72 */73#define MAX_FIELD_BITS ((sizeof(u32) - 1) * BITS_PER_BYTE + 1)74 75/*76 * This is the largest field size supported by get_big_field() and set_big_field(). Any field that77 * is larger is not guaranteed to fit in a single byte-aligned u64.78 */79#define MAX_BIG_FIELD_BITS ((sizeof(u64) - 1) * BITS_PER_BYTE + 1)80 81/*82 * This is the number of guard bytes needed at the end of the memory byte array when using the bit83 * utilities. These utilities call get_big_field() and set_big_field(), which can access up to 784 * bytes beyond the end of the desired field. The definition is written to make it clear how this85 * value is derived.86 */87#define POST_FIELD_GUARD_BYTES (sizeof(u64) - 1)88 89/* The number of guard bits that are needed in the tail guard list */90#define GUARD_BITS (POST_FIELD_GUARD_BYTES * BITS_PER_BYTE)91 92/*93 * The maximum size of a single delta list in bytes. We count guard bytes in this value because a94 * buffer of this size can be used with move_bits().95 */96#define DELTA_LIST_MAX_BYTE_COUNT \97 ((U16_MAX + BITS_PER_BYTE) / BITS_PER_BYTE + POST_FIELD_GUARD_BYTES)98 99/* The number of extra bytes and bits needed to store a collision entry */100#define COLLISION_BYTES UDS_RECORD_NAME_SIZE101#define COLLISION_BITS (COLLISION_BYTES * BITS_PER_BYTE)102 103/*104 * Immutable delta lists are packed into pages containing a header that encodes the delta list105 * information into 19 bits per list (64KB bit offset).106 */107#define IMMUTABLE_HEADER_SIZE 19108 109/*110 * Constants and structures for the saved delta index. "DI" is for delta_index, and -##### is a111 * number to increment when the format of the data changes.112 */113#define MAGIC_SIZE 8114 115static const char DELTA_INDEX_MAGIC[] = "DI-00002";116 117struct delta_index_header {118 char magic[MAGIC_SIZE];119 u32 zone_number;120 u32 zone_count;121 u32 first_list;122 u32 list_count;123 u64 record_count;124 u64 collision_count;125};126 127/*128 * Header data used for immutable delta index pages. This data is followed by the delta list offset129 * table.130 */131struct delta_page_header {132 /* Externally-defined nonce */133 u64 nonce;134 /* The virtual chapter number */135 u64 virtual_chapter_number;136 /* Index of the first delta list on the page */137 u16 first_list;138 /* Number of delta lists on the page */139 u16 list_count;140} __packed;141 142static inline u64 get_delta_list_byte_start(const struct delta_list *delta_list)143{144 return delta_list->start / BITS_PER_BYTE;145}146 147static inline u16 get_delta_list_byte_size(const struct delta_list *delta_list)148{149 unsigned int bit_offset = delta_list->start % BITS_PER_BYTE;150 151 return BITS_TO_BYTES(bit_offset + delta_list->size);152}153 154static void rebalance_delta_zone(const struct delta_zone *delta_zone, u32 first,155 u32 last)156{157 struct delta_list *delta_list;158 u64 new_start;159 160 if (first == last) {161 /* Only one list is moving, and we know there is space. */162 delta_list = &delta_zone->delta_lists[first];163 new_start = delta_zone->new_offsets[first];164 if (delta_list->start != new_start) {165 u64 source;166 u64 destination;167 168 source = get_delta_list_byte_start(delta_list);169 delta_list->start = new_start;170 destination = get_delta_list_byte_start(delta_list);171 memmove(delta_zone->memory + destination,172 delta_zone->memory + source,173 get_delta_list_byte_size(delta_list));174 }175 } else {176 /*177 * There is more than one list. Divide the problem in half, and use recursive calls178 * to process each half. Note that after this computation, first <= middle, and179 * middle < last.180 */181 u32 middle = (first + last) / 2;182 183 delta_list = &delta_zone->delta_lists[middle];184 new_start = delta_zone->new_offsets[middle];185 186 /*187 * The direction that our middle list is moving determines which half of the188 * problem must be processed first.189 */190 if (new_start > delta_list->start) {191 rebalance_delta_zone(delta_zone, middle + 1, last);192 rebalance_delta_zone(delta_zone, first, middle);193 } else {194 rebalance_delta_zone(delta_zone, first, middle);195 rebalance_delta_zone(delta_zone, middle + 1, last);196 }197 }198}199 200static inline size_t get_zone_memory_size(unsigned int zone_count, size_t memory_size)201{202 /* Round up so that each zone is a multiple of 64K in size. */203 size_t ALLOC_BOUNDARY = 64 * 1024;204 205 return (memory_size / zone_count + ALLOC_BOUNDARY - 1) & -ALLOC_BOUNDARY;206}207 208void uds_reset_delta_index(const struct delta_index *delta_index)209{210 unsigned int z;211 212 /*213 * Initialize all delta lists to be empty. We keep 2 extra delta list descriptors, one214 * before the first real entry and one after so that we don't need to bounds check the215 * array access when calculating preceding and following gap sizes.216 */217 for (z = 0; z < delta_index->zone_count; z++) {218 u64 list_bits;219 u64 spacing;220 u64 offset;221 unsigned int i;222 struct delta_zone *zone = &delta_index->delta_zones[z];223 struct delta_list *delta_lists = zone->delta_lists;224 225 /* Zeroing the delta list headers initializes the head guard list correctly. */226 memset(delta_lists, 0,227 (zone->list_count + 2) * sizeof(struct delta_list));228 229 /* Set all the bits in the end guard list. */230 list_bits = (u64) zone->size * BITS_PER_BYTE - GUARD_BITS;231 delta_lists[zone->list_count + 1].start = list_bits;232 delta_lists[zone->list_count + 1].size = GUARD_BITS;233 memset(zone->memory + (list_bits / BITS_PER_BYTE), ~0,234 POST_FIELD_GUARD_BYTES);235 236 /* Evenly space out the real delta lists by setting regular offsets. */237 spacing = list_bits / zone->list_count;238 offset = spacing / 2;239 for (i = 1; i <= zone->list_count; i++) {240 delta_lists[i].start = offset;241 offset += spacing;242 }243 244 /* Update the statistics. */245 zone->discard_count += zone->record_count;246 zone->record_count = 0;247 zone->collision_count = 0;248 }249}250 251/* Compute the Huffman coding parameters for the given mean delta. The Huffman code is specified by252 * three parameters:253 *254 * MINBITS The number of bits in the smallest code255 * BASE The number of values coded using a code of length MINBITS256 * INCR The number of values coded by using one additional bit257 *258 * These parameters are related by this equation:259 *260 * BASE + INCR == 1 << MINBITS261 *262 * The math for the Huffman code of an exponential distribution says that263 *264 * INCR = log(2) * MEAN_DELTA265 *266 * Then use the smallest MINBITS value so that267 *268 * (1 << MINBITS) > INCR269 *270 * And then271 *272 * BASE = (1 << MINBITS) - INCR273 *274 * Now the index can generate a code such that275 * - 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).279 */280static void compute_coding_constants(u32 mean_delta, u16 *min_bits, u32 *min_keys, u32 *incr_keys)281{282 /*283 * We want to compute the rounded value of log(2) * mean_delta. Since we cannot always use284 * floating point, use a really good integer approximation.285 */286 *incr_keys = (836158UL * mean_delta + 603160UL) / 1206321UL;287 *min_bits = bits_per(*incr_keys + 1);288 *min_keys = (1 << *min_bits) - *incr_keys;289}290 291void uds_uninitialize_delta_index(struct delta_index *delta_index)292{293 unsigned int z;294 295 if (delta_index->delta_zones == NULL)296 return;297 298 for (z = 0; z < delta_index->zone_count; z++) {299 vdo_free(vdo_forget(delta_index->delta_zones[z].new_offsets));300 vdo_free(vdo_forget(delta_index->delta_zones[z].delta_lists));301 vdo_free(vdo_forget(delta_index->delta_zones[z].memory));302 }303 304 vdo_free(delta_index->delta_zones);305 memset(delta_index, 0, sizeof(struct delta_index));306}307 308static int initialize_delta_zone(struct delta_zone *delta_zone, size_t size,309 u32 first_list, u32 list_count, u32 mean_delta,310 u32 payload_bits, u8 tag)311{312 int result;313 314 result = vdo_allocate(size, u8, "delta list", &delta_zone->memory);315 if (result != VDO_SUCCESS)316 return result;317 318 result = vdo_allocate(list_count + 2, u64, "delta list temp",319 &delta_zone->new_offsets);320 if (result != VDO_SUCCESS)321 return result;322 323 /* Allocate the delta lists. */324 result = vdo_allocate(list_count + 2, struct delta_list, "delta lists",325 &delta_zone->delta_lists);326 if (result != VDO_SUCCESS)327 return result;328 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;343 344 return UDS_SUCCESS;345}346 347int uds_initialize_delta_index(struct delta_index *delta_index, unsigned int zone_count,348 u32 list_count, u32 mean_delta, u32 payload_bits,349 size_t memory_size, u8 tag)350{351 int result;352 unsigned int z;353 size_t zone_memory;354 355 result = vdo_allocate(zone_count, struct delta_zone, "Delta Index Zones",356 &delta_index->delta_zones);357 if (result != VDO_SUCCESS)358 return result;359 360 delta_index->zone_count = zone_count;361 delta_index->list_count = list_count;362 delta_index->lists_per_zone = DIV_ROUND_UP(list_count, zone_count);363 delta_index->memory_size = 0;364 delta_index->mutable = true;365 delta_index->tag = tag;366 367 for (z = 0; z < zone_count; z++) {368 u32 lists_in_zone = delta_index->lists_per_zone;369 u32 first_list_in_zone = z * lists_in_zone;370 371 if (z == zone_count - 1) {372 /*373 * The last zone gets fewer lists if zone_count doesn't evenly divide374 * list_count. We'll have an underflow if the assertion below doesn't hold.375 */376 if (delta_index->list_count <= first_list_in_zone) {377 uds_uninitialize_delta_index(delta_index);378 return vdo_log_error_strerror(UDS_INVALID_ARGUMENT,379 "%u delta lists not enough for %u zones",380 list_count, zone_count);381 }382 lists_in_zone = delta_index->list_count - first_list_in_zone;383 }384 385 zone_memory = get_zone_memory_size(zone_count, memory_size);386 result = initialize_delta_zone(&delta_index->delta_zones[z], zone_memory,387 first_list_in_zone, lists_in_zone,388 mean_delta, payload_bits, tag);389 if (result != UDS_SUCCESS) {390 uds_uninitialize_delta_index(delta_index);391 return result;392 }393 394 delta_index->memory_size +=395 (sizeof(struct delta_zone) + zone_memory +396 (lists_in_zone + 2) * (sizeof(struct delta_list) + sizeof(u64)));397 }398 399 uds_reset_delta_index(delta_index);400 return UDS_SUCCESS;401}402 403/* Read a bit field from an arbitrary bit boundary. */404static inline u32 get_field(const u8 *memory, u64 offset, u8 size)405{406 const void *addr = memory + offset / BITS_PER_BYTE;407 408 return (get_unaligned_le32(addr) >> (offset % BITS_PER_BYTE)) & ((1 << size) - 1);409}410 411/* Write a bit field to an arbitrary bit boundary. */412static inline void set_field(u32 value, u8 *memory, u64 offset, u8 size)413{414 void *addr = memory + offset / BITS_PER_BYTE;415 int shift = offset % BITS_PER_BYTE;416 u32 data = get_unaligned_le32(addr);417 418 data &= ~(((1 << size) - 1) << shift);419 data |= value << shift;420 put_unaligned_le32(data, addr);421}422 423/* Get the bit offset to the immutable delta list header. */424static inline u32 get_immutable_header_offset(u32 list_number)425{426 return sizeof(struct delta_page_header) * BITS_PER_BYTE +427 list_number * IMMUTABLE_HEADER_SIZE;428}429 430/* Get the bit offset to the start of the immutable delta list bit stream. */431static inline u32 get_immutable_start(const u8 *memory, u32 list_number)432{433 return get_field(memory, get_immutable_header_offset(list_number),434 IMMUTABLE_HEADER_SIZE);435}436 437/* Set the bit offset to the start of the immutable delta list bit stream. */438static inline void set_immutable_start(u8 *memory, u32 list_number, u32 start)439{440 set_field(start, memory, get_immutable_header_offset(list_number),441 IMMUTABLE_HEADER_SIZE);442}443 444static bool verify_delta_index_page(u64 nonce, u16 list_count, u64 expected_nonce,445 u8 *memory, size_t memory_size)446{447 unsigned int i;448 449 /*450 * Verify the nonce. A mismatch can happen here during rebuild if we haven't written the451 * entire volume at least once.452 */453 if (nonce != expected_nonce)454 return false;455 456 /* Verify that the number of delta lists can fit in the page. */457 if (list_count > ((memory_size - sizeof(struct delta_page_header)) *458 BITS_PER_BYTE / IMMUTABLE_HEADER_SIZE))459 return false;460 461 /*462 * Verify that the first delta list is immediately after the last delta463 * list header.464 */465 if (get_immutable_start(memory, 0) != get_immutable_header_offset(list_count + 1))466 return false;467 468 /* Verify that the lists are in the correct order. */469 for (i = 0; i < list_count; i++) {470 if (get_immutable_start(memory, i) > get_immutable_start(memory, i + 1))471 return false;472 }473 474 /*475 * Verify that the last list ends on the page, and that there is room476 * for the post-field guard bits.477 */478 if (get_immutable_start(memory, list_count) >479 (memory_size - POST_FIELD_GUARD_BYTES) * BITS_PER_BYTE)480 return false;481 482 /* Verify that the guard bytes are correctly set to all ones. */483 for (i = 0; i < POST_FIELD_GUARD_BYTES; i++) {484 if (memory[memory_size - POST_FIELD_GUARD_BYTES + i] != (u8) ~0)485 return false;486 }487 488 /* All verifications passed. */489 return true;490}491 492/* Initialize a delta index page to refer to a supplied page. */493int uds_initialize_delta_index_page(struct delta_index_page *delta_index_page,494 u64 expected_nonce, u32 mean_delta, u32 payload_bits,495 u8 *memory, size_t memory_size)496{497 u64 nonce;498 u64 vcn;499 u64 first_list;500 u64 list_count;501 struct delta_page_header *header = (struct delta_page_header *) memory;502 struct delta_zone *delta_zone = &delta_index_page->delta_zone;503 const u8 *nonce_addr = (const u8 *) &header->nonce;504 const u8 *vcn_addr = (const u8 *) &header->virtual_chapter_number;505 const u8 *first_list_addr = (const u8 *) &header->first_list;506 const u8 *list_count_addr = (const u8 *) &header->list_count;507 508 /* First assume that the header is little endian. */509 nonce = get_unaligned_le64(nonce_addr);510 vcn = get_unaligned_le64(vcn_addr);511 first_list = get_unaligned_le16(first_list_addr);512 list_count = get_unaligned_le16(list_count_addr);513 if (!verify_delta_index_page(nonce, list_count, expected_nonce, memory,514 memory_size)) {515 /* If that fails, try big endian. */516 nonce = get_unaligned_be64(nonce_addr);517 vcn = get_unaligned_be64(vcn_addr);518 first_list = get_unaligned_be16(first_list_addr);519 list_count = get_unaligned_be16(list_count_addr);520 if (!verify_delta_index_page(nonce, list_count, expected_nonce, memory,521 memory_size)) {522 /*523 * Both attempts failed. Do not log this as an error, because it can happen524 * during a rebuild if we haven't written the entire volume at least once.525 */526 return UDS_CORRUPT_DATA;527 }528 }529 530 delta_index_page->delta_index.delta_zones = delta_zone;531 delta_index_page->delta_index.zone_count = 1;532 delta_index_page->delta_index.list_count = list_count;533 delta_index_page->delta_index.lists_per_zone = list_count;534 delta_index_page->delta_index.mutable = false;535 delta_index_page->delta_index.tag = 'p';536 delta_index_page->virtual_chapter_number = vcn;537 delta_index_page->lowest_list_number = first_list;538 delta_index_page->highest_list_number = first_list + list_count - 1;539 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';557 558 return UDS_SUCCESS;559}560 561/* Read a large bit field from an arbitrary bit boundary. */562static inline u64 get_big_field(const u8 *memory, u64 offset, u8 size)563{564 const void *addr = memory + offset / BITS_PER_BYTE;565 566 return (get_unaligned_le64(addr) >> (offset % BITS_PER_BYTE)) & ((1UL << size) - 1);567}568 569/* Write a large bit field to an arbitrary bit boundary. */570static inline void set_big_field(u64 value, u8 *memory, u64 offset, u8 size)571{572 void *addr = memory + offset / BITS_PER_BYTE;573 u8 shift = offset % BITS_PER_BYTE;574 u64 data = get_unaligned_le64(addr);575 576 data &= ~(((1UL << size) - 1) << shift);577 data |= value << shift;578 put_unaligned_le64(data, addr);579}580 581/* Set a sequence of bits to all zeros. */582static inline void set_zero(u8 *memory, u64 offset, u32 size)583{584 if (size > 0) {585 u8 *addr = memory + offset / BITS_PER_BYTE;586 u8 shift = offset % BITS_PER_BYTE;587 u32 count = size + shift > BITS_PER_BYTE ? (u32) BITS_PER_BYTE - shift : size;588 589 *addr++ &= ~(((1 << count) - 1) << shift);590 for (size -= count; size > BITS_PER_BYTE; size -= BITS_PER_BYTE)591 *addr++ = 0;592 593 if (size > 0)594 *addr &= 0xFF << size;595 }596}597 598/*599 * Move several bits from a higher to a lower address, moving the lower addressed bits first. The600 * size and memory offsets are measured in bits.601 */602static void move_bits_down(const u8 *from, u64 from_offset, u8 *to, u64 to_offset, u32 size)603{604 const u8 *source;605 u8 *destination;606 u8 offset;607 u8 count;608 u64 field;609 610 /* Start by moving one field that ends on a to int boundary. */611 count = (MAX_BIG_FIELD_BITS - ((to_offset + MAX_BIG_FIELD_BITS) % BITS_PER_TYPE(u32)));612 field = get_big_field(from, from_offset, count);613 set_big_field(field, to, to_offset, count);614 from_offset += count;615 to_offset += count;616 size -= count;617 618 /* Now do the main loop to copy 32 bit chunks that are int-aligned at the destination. */619 offset = from_offset % BITS_PER_TYPE(u32);620 source = from + (from_offset - offset) / BITS_PER_BYTE;621 destination = to + to_offset / BITS_PER_BYTE;622 while (size > MAX_BIG_FIELD_BITS) {623 put_unaligned_le32(get_unaligned_le64(source) >> offset, destination);624 source += sizeof(u32);625 destination += sizeof(u32);626 from_offset += BITS_PER_TYPE(u32);627 to_offset += BITS_PER_TYPE(u32);628 size -= BITS_PER_TYPE(u32);629 }630 631 /* Finish up by moving any remaining bits. */632 if (size > 0) {633 field = get_big_field(from, from_offset, size);634 set_big_field(field, to, to_offset, size);635 }636}637 638/*639 * Move several bits from a lower to a higher address, moving the higher addressed bits first. The640 * size and memory offsets are measured in bits.641 */642static void move_bits_up(const u8 *from, u64 from_offset, u8 *to, u64 to_offset, u32 size)643{644 const u8 *source;645 u8 *destination;646 u8 offset;647 u8 count;648 u64 field;649 650 /* Start by moving one field that begins on a destination int boundary. */651 count = (to_offset + size) % BITS_PER_TYPE(u32);652 if (count > 0) {653 size -= count;654 field = get_big_field(from, from_offset + size, count);655 set_big_field(field, to, to_offset + size, count);656 }657 658 /* Now do the main loop to copy 32 bit chunks that are int-aligned at the destination. */659 offset = (from_offset + size) % BITS_PER_TYPE(u32);660 source = from + (from_offset + size - offset) / BITS_PER_BYTE;661 destination = to + (to_offset + size) / BITS_PER_BYTE;662 while (size > MAX_BIG_FIELD_BITS) {663 source -= sizeof(u32);664 destination -= sizeof(u32);665 size -= BITS_PER_TYPE(u32);666 put_unaligned_le32(get_unaligned_le64(source) >> offset, destination);667 }668 669 /* Finish up by moving any remaining bits. */670 if (size > 0) {671 field = get_big_field(from, from_offset, size);672 set_big_field(field, to, to_offset, size);673 }674}675 676/*677 * Move bits from one field to another. When the fields overlap, behave as if we first move all the678 * bits from the source to a temporary value, and then move all the bits from the temporary value679 * to the destination. The size and memory offsets are measured in bits.680 */681static void move_bits(const u8 *from, u64 from_offset, u8 *to, u64 to_offset, u32 size)682{683 u64 field;684 685 /* A small move doesn't require special handling. */686 if (size <= MAX_BIG_FIELD_BITS) {687 if (size > 0) {688 field = get_big_field(from, from_offset, size);689 set_big_field(field, to, to_offset, size);690 }691 692 return;693 }694 695 if (from_offset > to_offset)696 move_bits_down(from, from_offset, to, to_offset, size);697 else698 move_bits_up(from, from_offset, to, to_offset, size);699}700 701/*702 * Pack delta lists from a mutable delta index into an immutable delta index page. A range of delta703 * lists (starting with a specified list index) is copied from the mutable delta index into a704 * memory page used in the immutable index. The number of lists copied onto the page is returned in705 * list_count.706 */707int uds_pack_delta_index_page(const struct delta_index *delta_index, u64 header_nonce,708 u8 *memory, size_t memory_size, u64 virtual_chapter_number,709 u32 first_list, u32 *list_count)710{711 const struct delta_zone *delta_zone;712 struct delta_list *delta_lists;713 u32 max_lists;714 u32 n_lists = 0;715 u32 offset;716 u32 i;717 int free_bits;718 int bits;719 struct delta_page_header *header;720 721 delta_zone = &delta_index->delta_zones[0];722 delta_lists = &delta_zone->delta_lists[first_list + 1];723 max_lists = delta_index->list_count - first_list;724 725 /*726 * Compute how many lists will fit on the page. Subtract the size of the fixed header, one727 * delta list offset, and the guard bytes from the page size to determine how much space is728 * available for delta lists.729 */730 free_bits = memory_size * BITS_PER_BYTE;731 free_bits -= get_immutable_header_offset(1);732 free_bits -= GUARD_BITS;733 if (free_bits < IMMUTABLE_HEADER_SIZE) {734 /* This page is too small to store any delta lists. */735 return vdo_log_error_strerror(UDS_OVERFLOW,736 "Chapter Index Page of %zu bytes is too small",737 memory_size);738 }739 740 while (n_lists < max_lists) {741 /* Each list requires a delta list offset and the list data. */742 bits = IMMUTABLE_HEADER_SIZE + delta_lists[n_lists].size;743 if (bits > free_bits)744 break;745 746 n_lists++;747 free_bits -= bits;748 }749 750 *list_count = n_lists;751 752 header = (struct delta_page_header *) memory;753 put_unaligned_le64(header_nonce, (u8 *) &header->nonce);754 put_unaligned_le64(virtual_chapter_number,755 (u8 *) &header->virtual_chapter_number);756 put_unaligned_le16(first_list, (u8 *) &header->first_list);757 put_unaligned_le16(n_lists, (u8 *) &header->list_count);758 759 /* Construct the delta list offset table. */760 offset = get_immutable_header_offset(n_lists + 1);761 set_immutable_start(memory, 0, offset);762 for (i = 0; i < n_lists; i++) {763 offset += delta_lists[i].size;764 set_immutable_start(memory, i + 1, offset);765 }766 767 /* Copy the delta list data onto the memory page. */768 for (i = 0; i < n_lists; i++) {769 move_bits(delta_zone->memory, delta_lists[i].start, memory,770 get_immutable_start(memory, i), delta_lists[i].size);771 }772 773 /* Set all the bits in the guard bytes. */774 memset(memory + memory_size - POST_FIELD_GUARD_BYTES, ~0,775 POST_FIELD_GUARD_BYTES);776 return UDS_SUCCESS;777}778 779/* Compute the new offsets of the delta lists. */780static void compute_new_list_offsets(struct delta_zone *delta_zone, u32 growing_index,781 size_t growing_size, size_t used_space)782{783 size_t spacing;784 u32 i;785 struct delta_list *delta_lists = delta_zone->delta_lists;786 u32 tail_guard_index = delta_zone->list_count + 1;787 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] +793 get_delta_list_byte_size(&delta_lists[i]) + spacing);794 delta_zone->new_offsets[i] *= BITS_PER_BYTE;795 delta_zone->new_offsets[i] += delta_lists[i].start % BITS_PER_BYTE;796 if (i == 0)797 delta_zone->new_offsets[i + 1] -= spacing / 2;798 if (i + 1 == growing_index)799 delta_zone->new_offsets[i + 1] += growing_size;800 }801 802 delta_zone->new_offsets[tail_guard_index] =803 (delta_zone->size * BITS_PER_BYTE - delta_lists[tail_guard_index].size);804}805 806static void rebalance_lists(struct delta_zone *delta_zone)807{808 struct delta_list *delta_lists;809 u32 i;810 size_t used_space = 0;811 812 /* Extend and balance memory to receive the delta lists */813 delta_lists = delta_zone->delta_lists;814 for (i = 0; i <= delta_zone->list_count + 1; i++)815 used_space += get_delta_list_byte_size(&delta_lists[i]);816 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];820}821 822/* Start restoring a delta index from multiple input streams. */823int uds_start_restoring_delta_index(struct delta_index *delta_index,824 struct buffered_reader **buffered_readers,825 unsigned int reader_count)826{827 int result;828 unsigned int zone_count = reader_count;829 u64 record_count = 0;830 u64 collision_count = 0;831 u32 first_list[MAX_ZONES];832 u32 list_count[MAX_ZONES];833 unsigned int z;834 u32 list_next = 0;835 const struct delta_zone *delta_zone;836 837 /* Read and validate each header. */838 for (z = 0; z < zone_count; z++) {839 struct delta_index_header header;840 u8 buffer[sizeof(struct delta_index_header)];841 size_t offset = 0;842 843 result = uds_read_from_buffered_reader(buffered_readers[z], buffer,844 sizeof(buffer));845 if (result != UDS_SUCCESS) {846 return vdo_log_warning_strerror(result,847 "failed to read delta index header");848 }849 850 memcpy(&header.magic, buffer, MAGIC_SIZE);851 offset += MAGIC_SIZE;852 decode_u32_le(buffer, &offset, &header.zone_number);853 decode_u32_le(buffer, &offset, &header.zone_count);854 decode_u32_le(buffer, &offset, &header.first_list);855 decode_u32_le(buffer, &offset, &header.list_count);856 decode_u64_le(buffer, &offset, &header.record_count);857 decode_u64_le(buffer, &offset, &header.collision_count);858 859 result = VDO_ASSERT(offset == sizeof(struct delta_index_header),860 "%zu bytes decoded of %zu expected", offset,861 sizeof(struct delta_index_header));862 if (result != VDO_SUCCESS) {863 return vdo_log_warning_strerror(result,864 "failed to read delta index header");865 }866 867 if (memcmp(header.magic, DELTA_INDEX_MAGIC, MAGIC_SIZE) != 0) {868 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,869 "delta index file has bad magic number");870 }871 872 if (zone_count != header.zone_count) {873 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,874 "delta index files contain mismatched zone counts (%u,%u)",875 zone_count, header.zone_count);876 }877 878 if (header.zone_number != z) {879 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,880 "delta index zone %u found in slot %u",881 header.zone_number, z);882 }883 884 first_list[z] = header.first_list;885 list_count[z] = header.list_count;886 record_count += header.record_count;887 collision_count += header.collision_count;888 889 if (first_list[z] != list_next) {890 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,891 "delta index file for zone %u starts with list %u instead of list %u",892 z, first_list[z], list_next);893 }894 895 list_next += list_count[z];896 }897 898 if (list_next != delta_index->list_count) {899 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,900 "delta index files contain %u delta lists instead of %u delta lists",901 list_next, delta_index->list_count);902 }903 904 if (collision_count > record_count) {905 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,906 "delta index files contain %llu collisions and %llu records",907 (unsigned long long) collision_count,908 (unsigned long long) record_count);909 }910 911 uds_reset_delta_index(delta_index);912 delta_index->delta_zones[0].record_count = record_count;913 delta_index->delta_zones[0].collision_count = collision_count;914 915 /* Read the delta lists and distribute them to the proper zones. */916 for (z = 0; z < zone_count; z++) {917 u32 i;918 919 delta_index->load_lists[z] = 0;920 for (i = 0; i < list_count[z]; i++) {921 u16 delta_list_size;922 u32 list_number;923 unsigned int zone_number;924 u8 size_data[sizeof(u16)];925 926 result = uds_read_from_buffered_reader(buffered_readers[z],927 size_data,928 sizeof(size_data));929 if (result != UDS_SUCCESS) {930 return vdo_log_warning_strerror(result,931 "failed to read delta index size");932 }933 934 delta_list_size = get_unaligned_le16(size_data);935 if (delta_list_size > 0)936 delta_index->load_lists[z] += 1;937 938 list_number = first_list[z] + i;939 zone_number = list_number / delta_index->lists_per_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;943 }944 }945 946 /* Prepare each zone to start receiving the delta list data. */947 for (z = 0; z < delta_index->zone_count; z++)948 rebalance_lists(&delta_index->delta_zones[z]);949 950 return UDS_SUCCESS;951}952 953static int restore_delta_list_to_zone(struct delta_zone *delta_zone,954 const struct delta_list_save_info *save_info,955 const u8 *data)956{957 struct delta_list *delta_list;958 u16 bit_count;959 u16 byte_count;960 u32 list_number = save_info->index - delta_zone->first_list;961 962 if (list_number >= delta_zone->list_count) {963 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,964 "invalid delta list number %u not in range [%u,%u)",965 save_info->index, delta_zone->first_list,966 delta_zone->first_list + delta_zone->list_count);967 }968 969 delta_list = &delta_zone->delta_lists[list_number + 1];970 if (delta_list->size == 0) {971 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,972 "unexpected delta list number %u",973 save_info->index);974 }975 976 bit_count = delta_list->size + save_info->bit_offset;977 byte_count = BITS_TO_BYTES(bit_count);978 if (save_info->byte_count != byte_count) {979 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,980 "unexpected delta list size %u != %u",981 save_info->byte_count, byte_count);982 }983 984 move_bits(data, save_info->bit_offset, delta_zone->memory, delta_list->start,985 delta_list->size);986 return UDS_SUCCESS;987}988 989static int restore_delta_list_data(struct delta_index *delta_index, unsigned int load_zone,990 struct buffered_reader *buffered_reader, u8 *data)991{992 int result;993 struct delta_list_save_info save_info;994 u8 buffer[sizeof(struct delta_list_save_info)];995 unsigned int new_zone;996 997 result = uds_read_from_buffered_reader(buffered_reader, buffer, sizeof(buffer));998 if (result != UDS_SUCCESS) {999 return vdo_log_warning_strerror(result,1000 "failed to read delta list data");1001 }1002 1003 save_info = (struct delta_list_save_info) {1004 .tag = buffer[0],1005 .bit_offset = buffer[1],1006 .byte_count = get_unaligned_le16(&buffer[2]),1007 .index = get_unaligned_le32(&buffer[4]),1008 };1009 1010 if ((save_info.bit_offset >= BITS_PER_BYTE) ||1011 (save_info.byte_count > DELTA_LIST_MAX_BYTE_COUNT)) {1012 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,1013 "corrupt delta list data");1014 }1015 1016 /* Make sure the data is intended for this delta index. */1017 if (save_info.tag != delta_index->tag)1018 return UDS_CORRUPT_DATA;1019 1020 if (save_info.index >= delta_index->list_count) {1021 return vdo_log_warning_strerror(UDS_CORRUPT_DATA,1022 "invalid delta list number %u of %u",1023 save_info.index,1024 delta_index->list_count);1025 }1026 1027 result = uds_read_from_buffered_reader(buffered_reader, data,1028 save_info.byte_count);1029 if (result != UDS_SUCCESS) {1030 return vdo_log_warning_strerror(result,1031 "failed to read delta list data");1032 }1033 1034 delta_index->load_lists[load_zone] -= 1;1035 new_zone = save_info.index / delta_index->lists_per_zone;1036 return restore_delta_list_to_zone(&delta_index->delta_zones[new_zone],1037 &save_info, data);1038}1039 1040/* Restore delta lists from saved data. */1041int uds_finish_restoring_delta_index(struct delta_index *delta_index,1042 struct buffered_reader **buffered_readers,1043 unsigned int reader_count)1044{1045 int result;1046 int saved_result = UDS_SUCCESS;1047 unsigned int z;1048 u8 *data;1049 1050 result = vdo_allocate(DELTA_LIST_MAX_BYTE_COUNT, u8, __func__, &data);1051 if (result != VDO_SUCCESS)1052 return result;1053 1054 for (z = 0; z < reader_count; z++) {1055 while (delta_index->load_lists[z] > 0) {1056 result = restore_delta_list_data(delta_index, z,1057 buffered_readers[z], data);1058 if (result != UDS_SUCCESS) {1059 saved_result = result;1060 break;1061 }1062 }1063 }1064 1065 vdo_free(data);1066 return saved_result;1067}1068 1069int uds_check_guard_delta_lists(struct buffered_reader **buffered_readers,1070 unsigned int reader_count)1071{1072 int result;1073 unsigned int z;1074 u8 buffer[sizeof(struct delta_list_save_info)];1075 1076 for (z = 0; z < reader_count; z++) {1077 result = uds_read_from_buffered_reader(buffered_readers[z], buffer,1078 sizeof(buffer));1079 if (result != UDS_SUCCESS)1080 return result;1081 1082 if (buffer[0] != 'z')1083 return UDS_CORRUPT_DATA;1084 }1085 1086 return UDS_SUCCESS;1087}1088 1089static int flush_delta_list(struct delta_zone *zone, u32 flush_index)1090{1091 struct delta_list *delta_list;1092 u8 buffer[sizeof(struct delta_list_save_info)];1093 int result;1094 1095 delta_list = &zone->delta_lists[flush_index + 1];1096 1097 buffer[0] = zone->tag;1098 buffer[1] = delta_list->start % BITS_PER_BYTE;1099 put_unaligned_le16(get_delta_list_byte_size(delta_list), &buffer[2]);1100 put_unaligned_le32(zone->first_list + flush_index, &buffer[4]);1101 1102 result = uds_write_to_buffered_writer(zone->buffered_writer, buffer,1103 sizeof(buffer));1104 if (result != UDS_SUCCESS) {1105 vdo_log_warning_strerror(result, "failed to write delta list memory");1106 return result;1107 }1108 1109 result = uds_write_to_buffered_writer(zone->buffered_writer,1110 zone->memory + get_delta_list_byte_start(delta_list),1111 get_delta_list_byte_size(delta_list));1112 if (result != UDS_SUCCESS)1113 vdo_log_warning_strerror(result, "failed to write delta list memory");1114 1115 return result;1116}1117 1118/* Start saving a delta index zone to a buffered output stream. */1119int uds_start_saving_delta_index(const struct delta_index *delta_index,1120 unsigned int zone_number,1121 struct buffered_writer *buffered_writer)1122{1123 int result;1124 u32 i;1125 struct delta_zone *delta_zone;1126 u8 buffer[sizeof(struct delta_index_header)];1127 size_t offset = 0;1128 1129 delta_zone = &delta_index->delta_zones[zone_number];1130 memcpy(buffer, DELTA_INDEX_MAGIC, MAGIC_SIZE);1131 offset += MAGIC_SIZE;1132 encode_u32_le(buffer, &offset, zone_number);1133 encode_u32_le(buffer, &offset, delta_index->zone_count);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);1138 1139 result = VDO_ASSERT(offset == sizeof(struct delta_index_header),1140 "%zu bytes encoded of %zu expected", offset,1141 sizeof(struct delta_index_header));1142 if (result != VDO_SUCCESS)1143 return result;1144 1145 result = uds_write_to_buffered_writer(buffered_writer, buffer, offset);1146 if (result != UDS_SUCCESS)1147 return vdo_log_warning_strerror(result,1148 "failed to write delta index header");1149 1150 for (i = 0; i < delta_zone->list_count; i++) {1151 u8 data[sizeof(u16)];1152 struct delta_list *delta_list;1153 1154 delta_list = &delta_zone->delta_lists[i + 1];1155 put_unaligned_le16(delta_list->size, data);1156 result = uds_write_to_buffered_writer(buffered_writer, data,1157 sizeof(data));1158 if (result != UDS_SUCCESS)1159 return vdo_log_warning_strerror(result,1160 "failed to write delta list size");1161 }1162 1163 delta_zone->buffered_writer = buffered_writer;1164 return UDS_SUCCESS;1165}1166 1167int uds_finish_saving_delta_index(const struct delta_index *delta_index,1168 unsigned int zone_number)1169{1170 int result;1171 int first_error = UDS_SUCCESS;1172 u32 i;1173 struct delta_zone *delta_zone;1174 struct delta_list *delta_list;1175 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];1179 if (delta_list->size > 0) {1180 result = flush_delta_list(delta_zone, i);1181 if ((result != UDS_SUCCESS) && (first_error == UDS_SUCCESS))1182 first_error = result;1183 }1184 }1185 1186 delta_zone->buffered_writer = NULL;1187 return first_error;1188}1189 1190int uds_write_guard_delta_list(struct buffered_writer *buffered_writer)1191{1192 int result;1193 u8 buffer[sizeof(struct delta_list_save_info)];1194 1195 memset(buffer, 0, sizeof(struct delta_list_save_info));1196 buffer[0] = 'z';1197 1198 result = uds_write_to_buffered_writer(buffered_writer, buffer, sizeof(buffer));1199 if (result != UDS_SUCCESS)1200 vdo_log_warning_strerror(result, "failed to write guard delta list");1201 1202 return UDS_SUCCESS;1203}1204 1205size_t uds_compute_delta_index_save_bytes(u32 list_count, size_t memory_size)1206{1207 /* One zone will use at least as much memory as other zone counts. */1208 return (sizeof(struct delta_index_header) +1209 list_count * (sizeof(struct delta_list_save_info) + 1) +1210 get_zone_memory_size(1, memory_size));1211}1212 1213static int assert_not_at_end(const struct delta_index_entry *delta_entry)1214{1215 int result = VDO_ASSERT(!delta_entry->at_end,1216 "operation is invalid because the list entry is at the end of the delta list");1217 if (result != VDO_SUCCESS)1218 result = UDS_BAD_STATE;1219 1220 return result;1221}1222 1223/*1224 * Prepare to search for an entry in the specified delta list.1225 *1226 * This is always the first function to be called when dealing with delta index entries. It is1227 * always followed by calls to uds_next_delta_index_entry() to iterate through a delta list. The1228 * fields of the delta_index_entry argument will be set up for iteration, but will not contain an1229 * entry from the list.1230 */1231int uds_start_delta_index_search(const struct delta_index *delta_index, u32 list_number,1232 u32 key, struct delta_index_entry *delta_entry)1233{1234 int result;1235 unsigned int zone_number;1236 struct delta_zone *delta_zone;1237 struct delta_list *delta_list;1238 1239 result = VDO_ASSERT((list_number < delta_index->list_count),1240 "Delta list number (%u) is out of range (%u)", list_number,1241 delta_index->list_count);1242 if (result != VDO_SUCCESS)1243 return UDS_CORRUPT_DATA;1244 1245 zone_number = list_number / delta_index->lists_per_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),1249 "Delta list number (%u) is out of range (%u) for zone (%u)",1250 list_number, delta_zone->list_count, zone_number);1251 if (result != VDO_SUCCESS)1252 return UDS_CORRUPT_DATA;1253 1254 if (delta_index->mutable) {1255 delta_list = &delta_zone->delta_lists[list_number + 1];1256 } else {1257 u32 end_offset;1258 1259 /*1260 * Translate the immutable delta list header into a temporary1261 * full delta list header.1262 */1263 delta_list = &delta_entry->temp_delta_list;1264 delta_list->start = get_immutable_start(delta_zone->memory, list_number);1265 end_offset = get_immutable_start(delta_zone->memory, list_number + 1);1266 delta_list->size = end_offset - delta_list->start;1267 delta_list->save_key = 0;1268 delta_list->save_offset = 0;1269 }1270 1271 if (key > delta_list->save_key) {1272 delta_entry->key = delta_list->save_key;1273 delta_entry->offset = delta_list->save_offset;1274 } else {1275 delta_entry->key = 0;1276 delta_entry->offset = 0;1277 if (key == 0) {1278 /*1279 * This usually means we're about to walk the entire delta list, so get all1280 * of it into the CPU cache.1281 */1282 uds_prefetch_range(&delta_zone->memory[delta_list->start / BITS_PER_BYTE],1283 delta_list->size / BITS_PER_BYTE, false);1284 }1285 }1286 1287 delta_entry->at_end = false;1288 delta_entry->delta_zone = delta_zone;1289 delta_entry->delta_list = delta_list;1290 delta_entry->entry_bits = 0;1291 delta_entry->is_collision = false;1292 delta_entry->list_number = list_number;1293 delta_entry->list_overflow = false;1294 delta_entry->value_bits = delta_zone->value_bits;1295 return UDS_SUCCESS;1296}1297 1298static inline u64 get_delta_entry_offset(const struct delta_index_entry *delta_entry)1299{1300 return delta_entry->delta_list->start + delta_entry->offset;1301}1302 1303/*1304 * Decode a delta index entry delta value. The delta_index_entry basically describes the previous1305 * list entry, and has had its offset field changed to point to the subsequent entry. We decode the1306 * bit stream and update the delta_list_entry to describe the entry.1307 */1308static inline void decode_delta(struct delta_index_entry *delta_entry)1309{1310 int key_bits;1311 u32 delta;1312 const struct delta_zone *delta_zone = delta_entry->delta_zone;1313 const u8 *memory = delta_zone->memory;1314 u64 delta_offset = get_delta_entry_offset(delta_entry) + delta_entry->value_bits;1315 const u8 *addr = memory + delta_offset / BITS_PER_BYTE;1316 int offset = delta_offset % BITS_PER_BYTE;1317 u32 data = get_unaligned_le32(addr) >> offset;1318 1319 addr += sizeof(u32);1320 key_bits = delta_zone->min_bits;1321 delta = data & ((1 << key_bits) - 1);1322 if (delta >= delta_zone->min_keys) {1323 data >>= key_bits;1324 if (data == 0) {1325 key_bits = sizeof(u32) * BITS_PER_BYTE - offset;1326 while ((data = get_unaligned_le32(addr)) == 0) {1327 addr += sizeof(u32);1328 key_bits += sizeof(u32) * BITS_PER_BYTE;1329 }1330 }1331 key_bits += ffs(data);1332 delta += ((key_bits - delta_zone->min_bits - 1) * delta_zone->incr_keys);1333 }1334 delta_entry->delta = delta;1335 delta_entry->key += delta;1336 1337 /* Check for a collision, a delta of zero after the start. */1338 if (unlikely((delta == 0) && (delta_entry->offset > 0))) {1339 delta_entry->is_collision = true;1340 delta_entry->entry_bits = delta_entry->value_bits + key_bits + COLLISION_BITS;1341 } else {1342 delta_entry->is_collision = false;1343 delta_entry->entry_bits = delta_entry->value_bits + key_bits;1344 }1345}1346 1347noinline int uds_next_delta_index_entry(struct delta_index_entry *delta_entry)1348{1349 int result;1350 const struct delta_list *delta_list;1351 u32 next_offset;1352 u16 size;1353 1354 result = assert_not_at_end(delta_entry);1355 if (result != UDS_SUCCESS)1356 return result;1357 1358 delta_list = delta_entry->delta_list;1359 delta_entry->offset += delta_entry->entry_bits;1360 size = delta_list->size;1361 if (unlikely(delta_entry->offset >= size)) {1362 delta_entry->at_end = true;1363 delta_entry->delta = 0;1364 delta_entry->is_collision = false;1365 result = VDO_ASSERT((delta_entry->offset == size),1366 "next offset past end of delta list");1367 if (result != VDO_SUCCESS)1368 result = UDS_CORRUPT_DATA;1369 1370 return result;1371 }1372 1373 decode_delta(delta_entry);1374 1375 next_offset = delta_entry->offset + delta_entry->entry_bits;1376 if (next_offset > size) {1377 /*1378 * This is not an assertion because uds_validate_chapter_index_page() wants to1379 * handle this error.1380 */1381 vdo_log_warning("Decoded past the end of the delta list");1382 return UDS_CORRUPT_DATA;1383 }1384 1385 return UDS_SUCCESS;1386}1387 1388int uds_remember_delta_index_offset(const struct delta_index_entry *delta_entry)1389{1390 int result;1391 struct delta_list *delta_list = delta_entry->delta_list;1392 1393 result = VDO_ASSERT(!delta_entry->is_collision, "entry is not a collision");1394 if (result != VDO_SUCCESS)1395 return result;1396 1397 delta_list->save_key = delta_entry->key - delta_entry->delta;1398 delta_list->save_offset = delta_entry->offset;1399 return UDS_SUCCESS;1400}1401 1402static void set_delta(struct delta_index_entry *delta_entry, u32 delta)1403{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));1408 1409 delta_entry->delta = delta;1410 delta_entry->entry_bits = delta_entry->value_bits + key_bits;1411}1412 1413static void get_collision_name(const struct delta_index_entry *entry, u8 *name)1414{1415 u64 offset = get_delta_entry_offset(entry) + entry->entry_bits - COLLISION_BITS;1416 const u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE;1417 int size = COLLISION_BYTES;1418 int shift = offset % BITS_PER_BYTE;1419 1420 while (--size >= 0)1421 *name++ = get_unaligned_le16(addr++) >> shift;1422}1423 1424static void set_collision_name(const struct delta_index_entry *entry, const u8 *name)1425{1426 u64 offset = get_delta_entry_offset(entry) + entry->entry_bits - COLLISION_BITS;1427 u8 *addr = entry->delta_zone->memory + offset / BITS_PER_BYTE;1428 int size = COLLISION_BYTES;1429 int shift = offset % BITS_PER_BYTE;1430 u16 mask = ~((u16) 0xFF << shift);1431 u16 data;1432 1433 while (--size >= 0) {1434 data = (get_unaligned_le16(addr) & mask) | (*name++ << shift);1435 put_unaligned_le16(data, addr++);1436 }1437}1438 1439int uds_get_delta_index_entry(const struct delta_index *delta_index, u32 list_number,1440 u32 key, const u8 *name,1441 struct delta_index_entry *delta_entry)1442{1443 int result;1444 1445 result = uds_start_delta_index_search(delta_index, list_number, key,1446 delta_entry);1447 if (result != UDS_SUCCESS)1448 return result;1449 1450 do {1451 result = uds_next_delta_index_entry(delta_entry);1452 if (result != UDS_SUCCESS)1453 return result;1454 } while (!delta_entry->at_end && (key > delta_entry->key));1455 1456 result = uds_remember_delta_index_offset(delta_entry);1457 if (result != UDS_SUCCESS)1458 return result;1459 1460 if (!delta_entry->at_end && (key == delta_entry->key)) {1461 struct delta_index_entry collision_entry = *delta_entry;1462 1463 for (;;) {1464 u8 full_name[COLLISION_BYTES];1465 1466 result = uds_next_delta_index_entry(&collision_entry);1467 if (result != UDS_SUCCESS)1468 return result;1469 1470 if (collision_entry.at_end || !collision_entry.is_collision)1471 break;1472 1473 get_collision_name(&collision_entry, full_name);1474 if (memcmp(full_name, name, COLLISION_BYTES) == 0) {1475 *delta_entry = collision_entry;1476 break;1477 }1478 }1479 }1480 1481 return UDS_SUCCESS;1482}1483 1484int uds_get_delta_entry_collision(const struct delta_index_entry *delta_entry, u8 *name)1485{1486 int result;1487 1488 result = assert_not_at_end(delta_entry);1489 if (result != UDS_SUCCESS)1490 return result;1491 1492 result = VDO_ASSERT(delta_entry->is_collision,1493 "Cannot get full block name from a non-collision delta index entry");1494 if (result != VDO_SUCCESS)1495 return UDS_BAD_STATE;1496 1497 get_collision_name(delta_entry, name);1498 return UDS_SUCCESS;1499}1500 1501u32 uds_get_delta_entry_value(const struct delta_index_entry *delta_entry)1502{1503 return get_field(delta_entry->delta_zone->memory,1504 get_delta_entry_offset(delta_entry), delta_entry->value_bits);1505}1506 1507static int assert_mutable_entry(const struct delta_index_entry *delta_entry)1508{1509 int result = VDO_ASSERT((delta_entry->delta_list != &delta_entry->temp_delta_list),1510 "delta index is mutable");1511 if (result != VDO_SUCCESS)1512 result = UDS_BAD_STATE;1513 1514 return result;1515}1516 1517int uds_set_delta_entry_value(const struct delta_index_entry *delta_entry, u32 value)1518{1519 int result;1520 u32 value_mask = (1 << delta_entry->value_bits) - 1;1521 1522 result = assert_mutable_entry(delta_entry);1523 if (result != UDS_SUCCESS)1524 return result;1525 1526 result = assert_not_at_end(delta_entry);1527 if (result != UDS_SUCCESS)1528 return result;1529 1530 result = VDO_ASSERT((value & value_mask) == value,1531 "Value (%u) being set in a delta index is too large (must fit in %u bits)",1532 value, delta_entry->value_bits);1533 if (result != VDO_SUCCESS)1534 return UDS_INVALID_ARGUMENT;1535 1536 set_field(value, delta_entry->delta_zone->memory,1537 get_delta_entry_offset(delta_entry), delta_entry->value_bits);1538 return UDS_SUCCESS;1539}1540 1541/*1542 * Extend the memory used by the delta lists by adding growing_size bytes before the list indicated1543 * by growing_index, then rebalancing the lists in the new chunk.1544 */1545static int extend_delta_zone(struct delta_zone *delta_zone, u32 growing_index,1546 size_t growing_size)1547{1548 ktime_t start_time;1549 ktime_t end_time;1550 struct delta_list *delta_lists;1551 u32 i;1552 size_t used_space;1553 1554 1555 /* Calculate the amount of space that is or will be in use. */1556 start_time = current_time_ns(CLOCK_MONOTONIC);1557 delta_lists = delta_zone->delta_lists;1558 used_space = growing_size;1559 for (i = 0; i <= delta_zone->list_count + 1; i++)1560 used_space += get_delta_list_byte_size(&delta_lists[i]);1561 1562 if (delta_zone->size < used_space)1563 return UDS_OVERFLOW;1564 1565 /* Compute the new offsets of the delta lists. */1566 compute_new_list_offsets(delta_zone, growing_index, growing_size, used_space);1567 1568 /*1569 * When we rebalance the delta list, we will include the end guard list in the rebalancing.1570 * It contains the end guard data, which must be copied.1571 */1572 rebalance_delta_zone(delta_zone, 1, delta_zone->list_count + 1);1573 end_time = current_time_ns(CLOCK_MONOTONIC);1574 delta_zone->rebalance_count++;1575 delta_zone->rebalance_time += ktime_sub(end_time, start_time);1576 return UDS_SUCCESS;1577}1578 1579static int insert_bits(struct delta_index_entry *delta_entry, u16 size)1580{1581 u64 free_before;1582 u64 free_after;1583 u64 source;1584 u64 destination;1585 u32 count;1586 bool before_flag;1587 u8 *memory;1588 struct delta_zone *delta_zone = delta_entry->delta_zone;1589 struct delta_list *delta_list = delta_entry->delta_list;1590 /* Compute bits in use before and after the inserted bits. */1591 u32 total_size = delta_list->size;1592 u32 before_size = delta_entry->offset;1593 u32 after_size = total_size - delta_entry->offset;1594 1595 if (total_size + size > U16_MAX) {1596 delta_entry->list_overflow = true;1597 delta_zone->overflow_count++;1598 return UDS_OVERFLOW;1599 }1600 1601 /* Compute bits available before and after the delta list. */1602 free_before = (delta_list[0].start - (delta_list[-1].start + delta_list[-1].size));1603 free_after = (delta_list[1].start - (delta_list[0].start + delta_list[0].size));1604 1605 if ((size <= free_before) && (size <= free_after)) {1606 /*1607 * We have enough space to use either before or after the list. Select the smaller1608 * amount of data. If it is exactly the same, try to take from the larger amount of1609 * free space.1610 */1611 if (before_size < after_size)1612 before_flag = true;1613 else if (after_size < before_size)1614 before_flag = false;1615 else1616 before_flag = free_before > free_after;1617 } else if (size <= free_before) {1618 /* There is space before but not after. */1619 before_flag = true;1620 } else if (size <= free_after) {1621 /* There is space after but not before. */1622 before_flag = false;1623 } else {1624 /*1625 * Neither of the surrounding spaces is large enough for this request. Extend1626 * and/or rebalance the delta list memory choosing to move the least amount of1627 * data.1628 */1629 int result;1630 u32 growing_index = delta_entry->list_number + 1;1631 1632 before_flag = before_size < after_size;1633 if (!before_flag)1634 growing_index++;1635 result = extend_delta_zone(delta_zone, growing_index,1636 BITS_TO_BYTES(size));1637 if (result != UDS_SUCCESS)1638 return result;1639 }1640 1641 delta_list->size += size;1642 if (before_flag) {1643 source = delta_list->start;1644 destination = source - size;1645 delta_list->start -= size;1646 count = before_size;1647 } else {1648 source = delta_list->start + delta_entry->offset;1649 destination = source + size;1650 count = after_size;1651 }1652 1653 memory = delta_zone->memory;1654 move_bits(memory, source, memory, destination, count);1655 return UDS_SUCCESS;1656}1657 1658static void encode_delta(const struct delta_index_entry *delta_entry)1659{1660 u32 temp;1661 u32 t1;1662 u32 t2;1663 u64 offset;1664 const struct delta_zone *delta_zone = delta_entry->delta_zone;1665 u8 *memory = delta_zone->memory;1666 1667 offset = get_delta_entry_offset(delta_entry) + delta_entry->value_bits;1668 if (delta_entry->delta < delta_zone->min_keys) {1669 set_field(delta_entry->delta, memory, offset, delta_zone->min_bits);1670 return;1671 }1672 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);1679}1680 1681static void encode_entry(const struct delta_index_entry *delta_entry, u32 value,1682 const u8 *name)1683{1684 u8 *memory = delta_entry->delta_zone->memory;1685 u64 offset = get_delta_entry_offset(delta_entry);1686 1687 set_field(value, memory, offset, delta_entry->value_bits);1688 encode_delta(delta_entry);1689 if (name != NULL)1690 set_collision_name(delta_entry, name);1691}1692 1693/*1694 * Create a new entry in the delta index. If the entry is a collision, the full 256 bit name must1695 * be provided.1696 */1697int uds_put_delta_index_entry(struct delta_index_entry *delta_entry, u32 key, u32 value,1698 const u8 *name)1699{1700 int result;1701 struct delta_zone *delta_zone;1702 1703 result = assert_mutable_entry(delta_entry);1704 if (result != UDS_SUCCESS)1705 return result;1706 1707 if (delta_entry->is_collision) {1708 /*1709 * The caller wants us to insert a collision entry onto a collision entry. This1710 * happens when we find a collision and attempt to add the name again to the index.1711 * This is normally a fatal error unless we are replaying a closed chapter while we1712 * are rebuilding a volume index.1713 */1714 return UDS_DUPLICATE_NAME;1715 }1716 1717 if (delta_entry->offset < delta_entry->delta_list->save_offset) {1718 /*1719 * The saved entry offset is after the new entry and will no longer be valid, so1720 * replace it with the insertion point.1721 */1722 result = uds_remember_delta_index_offset(delta_entry);1723 if (result != UDS_SUCCESS)1724 return result;1725 }1726 1727 if (name != NULL) {1728 /* Insert a collision entry which is placed after this entry. */1729 result = assert_not_at_end(delta_entry);1730 if (result != UDS_SUCCESS)1731 return result;1732 1733 result = VDO_ASSERT((key == delta_entry->key),1734 "incorrect key for collision entry");1735 if (result != VDO_SUCCESS)1736 return result;1737 1738 delta_entry->offset += delta_entry->entry_bits;1739 set_delta(delta_entry, 0);1740 delta_entry->is_collision = true;1741 delta_entry->entry_bits += COLLISION_BITS;1742 result = insert_bits(delta_entry, delta_entry->entry_bits);1743 } else if (delta_entry->at_end) {1744 /* Insert a new entry at the end of the delta list. */1745 result = VDO_ASSERT((key >= delta_entry->key), "key past end of list");1746 if (result != VDO_SUCCESS)1747 return result;1748 1749 set_delta(delta_entry, key - delta_entry->key);1750 delta_entry->key = key;1751 delta_entry->at_end = false;1752 result = insert_bits(delta_entry, delta_entry->entry_bits);1753 } else {1754 u16 old_entry_size;1755 u16 additional_size;1756 struct delta_index_entry next_entry;1757 u32 next_value;1758 1759 /*1760 * Insert a new entry which requires the delta in the following entry to be1761 * updated.1762 */1763 result = VDO_ASSERT((key < delta_entry->key),1764 "key precedes following entry");1765 if (result != VDO_SUCCESS)1766 return result;1767 1768 result = VDO_ASSERT((key >= delta_entry->key - delta_entry->delta),1769 "key effects following entry's delta");1770 if (result != VDO_SUCCESS)1771 return result;1772 1773 old_entry_size = delta_entry->entry_bits;1774 next_entry = *delta_entry;1775 next_value = uds_get_delta_entry_value(&next_entry);1776 set_delta(delta_entry, key - (delta_entry->key - delta_entry->delta));1777 delta_entry->key = key;1778 set_delta(&next_entry, next_entry.key - key);1779 next_entry.offset += delta_entry->entry_bits;1780 /* The two new entries are always bigger than the single entry being replaced. */1781 additional_size = (delta_entry->entry_bits +1782 next_entry.entry_bits - old_entry_size);1783 result = insert_bits(delta_entry, additional_size);1784 if (result != UDS_SUCCESS)1785 return result;1786 1787 encode_entry(&next_entry, next_value, NULL);1788 }1789 1790 if (result != UDS_SUCCESS)1791 return result;1792 1793 encode_entry(delta_entry, value, name);1794 delta_zone = delta_entry->delta_zone;1795 delta_zone->record_count++;1796 delta_zone->collision_count += delta_entry->is_collision ? 1 : 0;1797 return UDS_SUCCESS;1798}1799 1800static void delete_bits(const struct delta_index_entry *delta_entry, int size)1801{1802 u64 source;1803 u64 destination;1804 u32 count;1805 bool before_flag;1806 struct delta_list *delta_list = delta_entry->delta_list;1807 u8 *memory = delta_entry->delta_zone->memory;1808 /* Compute bits retained before and after the deleted bits. */1809 u32 total_size = delta_list->size;1810 u32 before_size = delta_entry->offset;1811 u32 after_size = total_size - delta_entry->offset - size;1812 1813 /*1814 * Determine whether to add to the available space either before or after the delta list.1815 * We prefer to move the least amount of data. If it is exactly the same, try to add to the1816 * smaller amount of free space.1817 */1818 if (before_size < after_size) {1819 before_flag = true;1820 } else if (after_size < before_size) {1821 before_flag = false;1822 } else {1823 u64 free_before =1824 (delta_list[0].start - (delta_list[-1].start + delta_list[-1].size));1825 u64 free_after =1826 (delta_list[1].start - (delta_list[0].start + delta_list[0].size));1827 1828 before_flag = (free_before < free_after);1829 }1830 1831 delta_list->size -= size;1832 if (before_flag) {1833 source = delta_list->start;1834 destination = source + size;1835 delta_list->start += size;1836 count = before_size;1837 } else {1838 destination = delta_list->start + delta_entry->offset;1839 source = destination + size;1840 count = after_size;1841 }1842 1843 move_bits(memory, source, memory, destination, count);1844}1845 1846int uds_remove_delta_index_entry(struct delta_index_entry *delta_entry)1847{1848 int result;1849 struct delta_index_entry next_entry;1850 struct delta_zone *delta_zone;1851 struct delta_list *delta_list;1852 1853 result = assert_mutable_entry(delta_entry);1854 if (result != UDS_SUCCESS)1855 return result;1856 1857 next_entry = *delta_entry;1858 result = uds_next_delta_index_entry(&next_entry);1859 if (result != UDS_SUCCESS)1860 return result;1861 1862 delta_zone = delta_entry->delta_zone;1863 1864 if (delta_entry->is_collision) {1865 /* This is a collision entry, so just remove it. */1866 delete_bits(delta_entry, delta_entry->entry_bits);1867 next_entry.offset = delta_entry->offset;1868 delta_zone->collision_count -= 1;1869 } else if (next_entry.at_end) {1870 /* This entry is at the end of the list, so just remove it. */1871 delete_bits(delta_entry, delta_entry->entry_bits);1872 next_entry.key -= delta_entry->delta;1873 next_entry.offset = delta_entry->offset;1874 } else {1875 /* The delta in the next entry needs to be updated. */1876 u32 next_value = uds_get_delta_entry_value(&next_entry);1877 u16 old_size = delta_entry->entry_bits + next_entry.entry_bits;1878 1879 if (next_entry.is_collision) {1880 next_entry.is_collision = false;1881 delta_zone->collision_count -= 1;1882 }1883 1884 set_delta(&next_entry, delta_entry->delta + next_entry.delta);1885 next_entry.offset = delta_entry->offset;1886 /* The one new entry is always smaller than the two entries being replaced. */1887 delete_bits(delta_entry, old_size - next_entry.entry_bits);1888 encode_entry(&next_entry, next_value, NULL);1889 }1890 1891 delta_zone->record_count--;1892 delta_zone->discard_count++;1893 *delta_entry = next_entry;1894 1895 delta_list = delta_entry->delta_list;1896 if (delta_entry->offset < delta_list->save_offset) {1897 /* The saved entry offset is no longer valid. */1898 delta_list->save_key = 0;1899 delta_list->save_offset = 0;1900 }1901 1902 return UDS_SUCCESS;1903}1904 1905void uds_get_delta_index_stats(const struct delta_index *delta_index,1906 struct delta_index_stats *stats)1907{1908 unsigned int z;1909 const struct delta_zone *delta_zone;1910 1911 memset(stats, 0, sizeof(struct delta_index_stats));1912 for (z = 0; z < delta_index->zone_count; z++) {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;1921 }1922}1923 1924size_t uds_compute_delta_index_size(u32 entry_count, u32 mean_delta, u32 payload_bits)1925{1926 u16 min_bits;1927 u32 incr_keys;1928 u32 min_keys;1929 1930 compute_coding_constants(mean_delta, &min_bits, &min_keys, &incr_keys);1931 /* On average, each delta is encoded into about min_bits + 1.5 bits. */1932 return entry_count * (payload_bits + min_bits + 1) + entry_count / 2;1933}1934 1935u32 uds_get_delta_index_page_count(u32 entry_count, u32 list_count, u32 mean_delta,1936 u32 payload_bits, size_t bytes_per_page)1937{1938 unsigned int bits_per_delta_list;1939 unsigned int bits_per_page;1940 size_t bits_per_index;1941 1942 /* Compute the expected number of bits needed for all the entries. */1943 bits_per_index = uds_compute_delta_index_size(entry_count, mean_delta,1944 payload_bits);1945 bits_per_delta_list = bits_per_index / list_count;1946 1947 /* Add in the immutable delta list headers. */1948 bits_per_index += list_count * IMMUTABLE_HEADER_SIZE;1949 /* Compute the number of usable bits on an immutable index page. */1950 bits_per_page = ((bytes_per_page - sizeof(struct delta_page_header)) * BITS_PER_BYTE);1951 /*1952 * Reduce the bits per page by one immutable delta list header and one delta list to1953 * account for internal fragmentation.1954 */1955 bits_per_page -= IMMUTABLE_HEADER_SIZE + bits_per_delta_list;1956 /* Now compute the number of pages needed. */1957 return DIV_ROUND_UP(bits_per_index, bits_per_page);1958}1959 1960void uds_log_delta_index_entry(struct delta_index_entry *delta_entry)1961{1962 vdo_log_ratelimit(vdo_log_info,1963 "List 0x%X Key 0x%X Offset 0x%X%s%s List_size 0x%X%s",1964 delta_entry->list_number, delta_entry->key,1965 delta_entry->offset, delta_entry->at_end ? " end" : "",1966 delta_entry->is_collision ? " collision" : "",1967 delta_entry->delta_list->size,1968 delta_entry->list_overflow ? " overflow" : "");1969 delta_entry->list_overflow = false;1970}1971