drivers/md/dm-vdo/index-layout.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #include "index-layout.h"
   7
   8 #include <linux/random.h>
   9
  10 #include "config.h"
  11 #include "logger.h"
  12 #include "memory-alloc.h"
  13 #include "murmurhash3.h"
  14 #include "numeric.h"
  15 #include "open-chapter.h"
  16 #include "time-utils.h"
  17 #include "volume-index.h"
  18
  19 /*
  20  * The UDS layout on storage media is divided into a number of fixed-size regions, the sizes of
  21  * which are computed when the index is created. Every header and region begins on 4K block
  22  * boundary. Save regions are further sub-divided into regions of their own.
  23  *
  24  * Each region has a kind and an instance number. Some kinds only have one instance and therefore
  25  * use RL_SOLE_INSTANCE (-1) as the instance number. The RL_KIND_INDEX used to use instances to
  26  * represent sub-indices; now, however there is only ever one sub-index and therefore one instance.
  27  * The RL_KIND_VOLUME_INDEX uses instances to record which zone is being saved.
  28  *
  29  * Every region header has a type and version.
  30  *
  31  *     +-+-+---------+--------+--------+-+
  32  *     | | |   I N D E X  0   101, 0   | |
  33  *     |H|C+---------+--------+--------+S|
  34  *     |D|f| Volume  | Save   | Save   |e|
  35  *     |R|g| Region  | Region | Region |a|
  36  *     | | | 201, -1 | 202, 0 | 202, 1 |l|
  37  *     +-+-+--------+---------+--------+-+
  38  *
  39  * The header contains the encoded region layout table as well as some index configuration data.
  40  * The sub-index region and its subdivisions are maintained in the same table.
  41  *
  42  * There are two save regions to preserve the old state in case saving the new state is incomplete.
  43  * They are used in alternation. Each save region is further divided into sub-regions.
  44  *
  45  *     +-+-----+------+------+-----+-----+
  46  *     |H| IPM | MI   | MI   |     | OC  |
  47  *     |D|     | zone | zone | ... |     |
  48  *     |R| 301 | 302  | 302  |     | 303 |
  49  *     | | -1  |  0   |  1   |     | -1  |
  50  *     +-+-----+------+------+-----+-----+
  51  *
  52  * The header contains the encoded region layout table as well as index state data for that save.
  53  * Each save also has a unique nonce.
  54  */
  55
  56 enum {
  57         MAGIC_SIZE = 32,
  58         NONCE_INFO_SIZE = 32,
  59         MAX_SAVES = 2,
  60 };
  61
  62 enum region_kind {
  63         RL_KIND_EMPTY = 0,
  64         RL_KIND_HEADER = 1,
  65         RL_KIND_CONFIG = 100,
  66         RL_KIND_INDEX = 101,
  67         RL_KIND_SEAL = 102,
  68         RL_KIND_VOLUME = 201,
  69         RL_KIND_SAVE = 202,
  70         RL_KIND_INDEX_PAGE_MAP = 301,
  71         RL_KIND_VOLUME_INDEX = 302,
  72         RL_KIND_OPEN_CHAPTER = 303,
  73 };
  74
  75 /* Some region types are historical and are no longer used. */
  76 enum region_type {
  77         RH_TYPE_FREE = 0, /* unused */
  78         RH_TYPE_SUPER = 1,
  79         RH_TYPE_SAVE = 2,
  80         RH_TYPE_CHECKPOINT = 3, /* unused */
  81         RH_TYPE_UNSAVED = 4,
  82 };
  83
  84 enum {
  85         RL_SOLE_INSTANCE = 65535,
  86 };
  87
  88 /*
  89  * Super block version 2 is the first released version.
  90  *
  91  * Super block version 3 is the normal version used from RHEL 8.2 onwards.
  92  *
  93  * Super block versions 4 through 6 were incremental development versions and
  94  * are not supported.
  95  *
  96  * Super block version 7 is used for volumes which have been reduced in size by one chapter in
  97  * order to make room to prepend LVM metadata to a volume originally created without lvm. This
  98  * allows the index to retain most its deduplication records.
  99  */
 100 enum {
 101         SUPER_VERSION_MINIMUM = 3,
 102         SUPER_VERSION_CURRENT = 3,
 103         SUPER_VERSION_MAXIMUM = 7,
 104 };
 105
 106 static const u8 LAYOUT_MAGIC[MAGIC_SIZE] = "*ALBIREO*SINGLE*FILE*LAYOUT*001*";
 107 static const u64 REGION_MAGIC = 0x416c6252676e3031; /* 'AlbRgn01' */
 108
 109 struct region_header {
 110         u64 magic;
 111         u64 region_blocks;
 112         u16 type;
 113         /* Currently always version 1 */
 114         u16 version;
 115         u16 region_count;
 116         u16 payload;
 117 };
 118
 119 struct layout_region {
 120         u64 start_block;
 121         u64 block_count;
 122         u32 __unused;
 123         u16 kind;
 124         u16 instance;
 125 };
 126
 127 struct region_table {
 128         size_t encoded_size;
 129         struct region_header header;
 130         struct layout_region regions[];
 131 };
 132
 133 struct index_save_data {
 134         u64 timestamp;
 135         u64 nonce;
 136         /* Currently always version 1 */
 137         u32 version;
 138         u32 unused__;
 139 };
 140
 141 struct index_state_version {
 142         s32 signature;
 143         s32 version_id;
 144 };
 145
 146 static const struct index_state_version INDEX_STATE_VERSION_301 = {
 147         .signature  = -1,
 148         .version_id = 301,
 149 };
 150
 151 struct index_state_data301 {
 152         struct index_state_version version;
 153         u64 newest_chapter;
 154         u64 oldest_chapter;
 155         u64 last_save;
 156         u32 unused;
 157         u32 padding;
 158 };
 159
 160 struct index_save_layout {
 161         unsigned int zone_count;
 162         struct layout_region index_save;
 163         struct layout_region header;
 164         struct layout_region index_page_map;
 165         struct layout_region free_space;
 166         struct layout_region volume_index_zones[MAX_ZONES];
 167         struct layout_region open_chapter;
 168         struct index_save_data save_data;
 169         struct index_state_data301 state_data;
 170 };
 171
 172 struct sub_index_layout {
 173         u64 nonce;
 174         struct layout_region sub_index;
 175         struct layout_region volume;
 176         struct index_save_layout *saves;
 177 };
 178
 179 struct super_block_data {
 180         u8 magic_label[MAGIC_SIZE];
 181         u8 nonce_info[NONCE_INFO_SIZE];
 182         u64 nonce;
 183         u32 version;
 184         u32 block_size;
 185         u16 index_count;
 186         u16 max_saves;
 187         /* Padding reflects a blank field on permanent storage */
 188         u8 padding[4];
 189         u64 open_chapter_blocks;
 190         u64 page_map_blocks;
 191         u64 volume_offset;
 192         u64 start_offset;
 193 };
 194
 195 struct index_layout {
 196         struct io_factory *factory;
 197         size_t factory_size;
 198         off_t offset;
 199         struct super_block_data super;
 200         struct layout_region header;
 201         struct layout_region config;
 202         struct sub_index_layout index;
 203         struct layout_region seal;
 204         u64 total_blocks;
 205 };
 206
 207 struct save_layout_sizes {
 208         unsigned int save_count;
 209         size_t block_size;
 210         u64 volume_blocks;
 211         u64 volume_index_blocks;
 212         u64 page_map_blocks;
 213         u64 open_chapter_blocks;
 214         u64 save_blocks;
 215         u64 sub_index_blocks;
 216         u64 total_blocks;
 217         size_t total_size;
 218 };
 219
 220 static inline bool is_converted_super_block(struct super_block_data *super)
 221 {
 222         return super->version == 7;
 223 }
 224
 225 static int __must_check compute_sizes(const struct uds_configuration *config,
 226                                       struct save_layout_sizes *sls)
 227 {
 228         int result;
 229         struct index_geometry *geometry = config->geometry;
 230
 231         memset(sls, 0, sizeof(*sls));
 232         sls->save_count = MAX_SAVES;
 233         sls->block_size = UDS_BLOCK_SIZE;
 234         sls->volume_blocks = geometry->bytes_per_volume / sls->block_size;
 235
 236         result = uds_compute_volume_index_save_blocks(config, sls->block_size,
 237                                                       &sls->volume_index_blocks);
 238         if (result != UDS_SUCCESS)
 239                 return uds_log_error_strerror(result, "cannot compute index save size");
 240
 241         sls->page_map_blocks =
 242                 DIV_ROUND_UP(uds_compute_index_page_map_save_size(geometry),
 243                              sls->block_size);
 244         sls->open_chapter_blocks =
 245                 DIV_ROUND_UP(uds_compute_saved_open_chapter_size(geometry),
 246                              sls->block_size);
 247         sls->save_blocks =
 248                 1 + (sls->volume_index_blocks + sls->page_map_blocks + sls->open_chapter_blocks);
 249         sls->sub_index_blocks = sls->volume_blocks + (sls->save_count * sls->save_blocks);
 250         sls->total_blocks = 3 + sls->sub_index_blocks;
 251         sls->total_size = sls->total_blocks * sls->block_size;
 252
 253         return UDS_SUCCESS;
 254 }
 255
 256 int uds_compute_index_size(const struct uds_parameters *parameters, u64 *index_size)
 257 {
 258         int result;
 259         struct uds_configuration *index_config;
 260         struct save_layout_sizes sizes;
 261
 262         if (index_size == NULL) {
 263                 uds_log_error("Missing output size pointer");
 264                 return -EINVAL;
 265         }
 266
 267         result = uds_make_configuration(parameters, &index_config);
 268         if (result != UDS_SUCCESS) {
 269                 uds_log_error_strerror(result, "cannot compute index size");
 270                 return uds_status_to_errno(result);
 271         }
 272
 273         result = compute_sizes(index_config, &sizes);
 274         uds_free_configuration(index_config);
 275         if (result != UDS_SUCCESS)
 276                 return uds_status_to_errno(result);
 277
 278         *index_size = sizes.total_size;
 279         return UDS_SUCCESS;
 280 }
 281
 282 /* Create unique data using the current time and a pseudorandom number. */
 283 static void create_unique_nonce_data(u8 *buffer)
 284 {
 285         ktime_t now = current_time_ns(CLOCK_REALTIME);
 286         u32 rand;
 287         size_t offset = 0;
 288
 289         get_random_bytes(&rand, sizeof(u32));
 290         memcpy(buffer + offset, &now, sizeof(now));
 291         offset += sizeof(now);
 292         memcpy(buffer + offset, &rand, sizeof(rand));
 293         offset += sizeof(rand);
 294         while (offset < NONCE_INFO_SIZE) {
 295                 size_t len = min(NONCE_INFO_SIZE - offset, offset);
 296
 297                 memcpy(buffer + offset, buffer, len);
 298                 offset += len;
 299         }
 300 }
 301
 302 static u64 hash_stuff(u64 start, const void *data, size_t len)
 303 {
 304         u32 seed = start ^ (start >> 27);
 305         u8 hash_buffer[16];
 306
 307         murmurhash3_128(data, len, seed, hash_buffer);
 308         return get_unaligned_le64(hash_buffer + 4);
 309 }
 310
 311 /* Generate a primary nonce from the provided data. */
 312 static u64 generate_primary_nonce(const void *data, size_t len)
 313 {
 314         return hash_stuff(0xa1b1e0fc, data, len);
 315 }
 316
 317 /*
 318  * Deterministically generate a secondary nonce from an existing nonce and some arbitrary data by
 319  * hashing the original nonce and the data to produce a new nonce.
 320  */
 321 static u64 generate_secondary_nonce(u64 nonce, const void *data, size_t len)
 322 {
 323         return hash_stuff(nonce + 1, data, len);
 324 }
 325
 326 static int __must_check open_layout_reader(struct index_layout *layout,
 327                                            struct layout_region *lr, off_t offset,
 328                                            struct buffered_reader **reader_ptr)
 329 {
 330         return uds_make_buffered_reader(layout->factory, lr->start_block + offset,
 331                                         lr->block_count, reader_ptr);
 332 }
 333
 334 static int open_region_reader(struct index_layout *layout, struct layout_region *region,
 335                               struct buffered_reader **reader_ptr)
 336 {
 337         return open_layout_reader(layout, region, -layout->super.start_offset,
 338                                   reader_ptr);
 339 }
 340
 341 static int __must_check open_layout_writer(struct index_layout *layout,
 342                                            struct layout_region *lr, off_t offset,
 343                                            struct buffered_writer **writer_ptr)
 344 {
 345         return uds_make_buffered_writer(layout->factory, lr->start_block + offset,
 346                                         lr->block_count, writer_ptr);
 347 }
 348
 349 static int open_region_writer(struct index_layout *layout, struct layout_region *region,
 350                               struct buffered_writer **writer_ptr)
 351 {
 352         return open_layout_writer(layout, region, -layout->super.start_offset,
 353                                   writer_ptr);
 354 }
 355
 356 static void generate_super_block_data(struct save_layout_sizes *sls,
 357                                       struct super_block_data *super)
 358 {
 359         memset(super, 0, sizeof(*super));
 360         memcpy(super->magic_label, LAYOUT_MAGIC, MAGIC_SIZE);
 361         create_unique_nonce_data(super->nonce_info);
 362
 363         super->nonce = generate_primary_nonce(super->nonce_info,
 364                                               sizeof(super->nonce_info));
 365         super->version = SUPER_VERSION_CURRENT;
 366         super->block_size = sls->block_size;
 367         super->index_count = 1;
 368         super->max_saves = sls->save_count;
 369         super->open_chapter_blocks = sls->open_chapter_blocks;
 370         super->page_map_blocks = sls->page_map_blocks;
 371         super->volume_offset = 0;
 372         super->start_offset = 0;
 373 }
 374
 375 static void define_sub_index_nonce(struct index_layout *layout)
 376 {
 377         struct sub_index_nonce_data {
 378                 u64 offset;
 379                 u16 index_id;
 380         };
 381         struct sub_index_layout *sil = &layout->index;
 382         u64 primary_nonce = layout->super.nonce;
 383         u8 buffer[sizeof(struct sub_index_nonce_data)] = { 0 };
 384         size_t offset = 0;
 385
 386         encode_u64_le(buffer, &offset, sil->sub_index.start_block);
 387         encode_u16_le(buffer, &offset, 0);
 388         sil->nonce = generate_secondary_nonce(primary_nonce, buffer, sizeof(buffer));
 389         if (sil->nonce == 0) {
 390                 sil->nonce = generate_secondary_nonce(~primary_nonce + 1, buffer,
 391                                                       sizeof(buffer));
 392         }
 393 }
 394
 395 static void setup_sub_index(struct index_layout *layout, u64 start_block,
 396                             struct save_layout_sizes *sls)
 397 {
 398         struct sub_index_layout *sil = &layout->index;
 399         u64 next_block = start_block;
 400         unsigned int i;
 401
 402         sil->sub_index = (struct layout_region) {
 403                 .start_block = start_block,
 404                 .block_count = sls->sub_index_blocks,
 405                 .kind = RL_KIND_INDEX,
 406                 .instance = 0,
 407         };
 408
 409         sil->volume = (struct layout_region) {
 410                 .start_block = next_block,
 411                 .block_count = sls->volume_blocks,
 412                 .kind = RL_KIND_VOLUME,
 413                 .instance = RL_SOLE_INSTANCE,
 414         };
 415
 416         next_block += sls->volume_blocks;
 417
 418         for (i = 0; i < sls->save_count; i++) {
 419                 sil->saves[i].index_save = (struct layout_region) {
 420                         .start_block = next_block,
 421                         .block_count = sls->save_blocks,
 422                         .kind = RL_KIND_SAVE,
 423                         .instance = i,
 424                 };
 425
 426                 next_block += sls->save_blocks;
 427         }
 428
 429         define_sub_index_nonce(layout);
 430 }
 431
 432 static void initialize_layout(struct index_layout *layout, struct save_layout_sizes *sls)
 433 {
 434         u64 next_block = layout->offset / sls->block_size;
 435
 436         layout->total_blocks = sls->total_blocks;
 437         generate_super_block_data(sls, &layout->super);
 438         layout->header = (struct layout_region) {
 439                 .start_block = next_block++,
 440                 .block_count = 1,
 441                 .kind = RL_KIND_HEADER,
 442                 .instance = RL_SOLE_INSTANCE,
 443         };
 444
 445         layout->config = (struct layout_region) {
 446                 .start_block = next_block++,
 447                 .block_count = 1,
 448                 .kind = RL_KIND_CONFIG,
 449                 .instance = RL_SOLE_INSTANCE,
 450         };
 451
 452         setup_sub_index(layout, next_block, sls);
 453         next_block += sls->sub_index_blocks;
 454
 455         layout->seal = (struct layout_region) {
 456                 .start_block = next_block,
 457                 .block_count = 1,
 458                 .kind = RL_KIND_SEAL,
 459                 .instance = RL_SOLE_INSTANCE,
 460         };
 461 }
 462
 463 static int __must_check make_index_save_region_table(struct index_save_layout *isl,
 464                                                      struct region_table **table_ptr)
 465 {
 466         int result;
 467         unsigned int z;
 468         struct region_table *table;
 469         struct layout_region *lr;
 470         u16 region_count;
 471         size_t payload;
 472         size_t type;
 473
 474         if (isl->zone_count > 0) {
 475                 /*
 476                  * Normal save regions: header, page map, volume index zones,
 477                  * open chapter, and possibly free space.
 478                  */
 479                 region_count = 3 + isl->zone_count;
 480                 if (isl->free_space.block_count > 0)
 481                         region_count++;
 482
 483                 payload = sizeof(isl->save_data) + sizeof(isl->state_data);
 484                 type = RH_TYPE_SAVE;
 485         } else {
 486                 /* Empty save regions: header, page map, free space. */
 487                 region_count = 3;
 488                 payload = sizeof(isl->save_data);
 489                 type = RH_TYPE_UNSAVED;
 490         }
 491
 492         result = uds_allocate_extended(struct region_table, region_count,
 493                                        struct layout_region,
 494                                        "layout region table for ISL", &table);
 495         if (result != UDS_SUCCESS)
 496                 return result;
 497
 498         lr = &table->regions[0];
 499         *lr++ = isl->header;
 500         *lr++ = isl->index_page_map;
 501         for (z = 0; z < isl->zone_count; z++)
 502                 *lr++ = isl->volume_index_zones[z];
 503
 504         if (isl->zone_count > 0)
 505                 *lr++ = isl->open_chapter;
 506
 507         if (isl->free_space.block_count > 0)
 508                 *lr++ = isl->free_space;
 509
 510         table->header = (struct region_header) {
 511                 .magic = REGION_MAGIC,
 512                 .region_blocks = isl->index_save.block_count,
 513                 .type = type,
 514                 .version = 1,
 515                 .region_count = region_count,
 516                 .payload = payload,
 517         };
 518
 519         table->encoded_size = (sizeof(struct region_header) + payload +
 520                                region_count * sizeof(struct layout_region));
 521         *table_ptr = table;
 522         return UDS_SUCCESS;
 523 }
 524
 525 static void encode_region_table(u8 *buffer, size_t *offset, struct region_table *table)
 526 {
 527         unsigned int i;
 528
 529         encode_u64_le(buffer, offset, REGION_MAGIC);
 530         encode_u64_le(buffer, offset, table->header.region_blocks);
 531         encode_u16_le(buffer, offset, table->header.type);
 532         encode_u16_le(buffer, offset, table->header.version);
 533         encode_u16_le(buffer, offset, table->header.region_count);
 534         encode_u16_le(buffer, offset, table->header.payload);
 535
 536         for (i = 0; i < table->header.region_count; i++) {
 537                 encode_u64_le(buffer, offset, table->regions[i].start_block);
 538                 encode_u64_le(buffer, offset, table->regions[i].block_count);
 539                 encode_u32_le(buffer, offset, 0);
 540                 encode_u16_le(buffer, offset, table->regions[i].kind);
 541                 encode_u16_le(buffer, offset, table->regions[i].instance);
 542         }
 543 }
 544
 545 static int __must_check write_index_save_header(struct index_save_layout *isl,
 546                                                 struct region_table *table,
 547                                                 struct buffered_writer *writer)
 548 {
 549         int result;
 550         u8 *buffer;
 551         size_t offset = 0;
 552
 553         result = uds_allocate(table->encoded_size, u8, "index save data", &buffer);
 554         if (result != UDS_SUCCESS)
 555                 return result;
 556
 557         encode_region_table(buffer, &offset, table);
 558         encode_u64_le(buffer, &offset, isl->save_data.timestamp);
 559         encode_u64_le(buffer, &offset, isl->save_data.nonce);
 560         encode_u32_le(buffer, &offset, isl->save_data.version);
 561         encode_u32_le(buffer, &offset, 0);
 562         if (isl->zone_count > 0) {
 563                 encode_u32_le(buffer, &offset, INDEX_STATE_VERSION_301.signature);
 564                 encode_u32_le(buffer, &offset, INDEX_STATE_VERSION_301.version_id);
 565                 encode_u64_le(buffer, &offset, isl->state_data.newest_chapter);
 566                 encode_u64_le(buffer, &offset, isl->state_data.oldest_chapter);
 567                 encode_u64_le(buffer, &offset, isl->state_data.last_save);
 568                 encode_u64_le(buffer, &offset, 0);
 569         }
 570
 571         result = uds_write_to_buffered_writer(writer, buffer, offset);
 572         uds_free(buffer);
 573         if (result != UDS_SUCCESS)
 574                 return result;
 575
 576         return uds_flush_buffered_writer(writer);
 577 }
 578
 579 static int write_index_save_layout(struct index_layout *layout,
 580                                    struct index_save_layout *isl)
 581 {
 582         int result;
 583         struct region_table *table;
 584         struct buffered_writer *writer;
 585
 586         result = make_index_save_region_table(isl, &table);
 587         if (result != UDS_SUCCESS)
 588                 return result;
 589
 590         result = open_region_writer(layout, &isl->header, &writer);
 591         if (result != UDS_SUCCESS) {
 592                 uds_free(table);
 593                 return result;
 594         }
 595
 596         result = write_index_save_header(isl, table, writer);
 597         uds_free(table);
 598         uds_free_buffered_writer(writer);
 599
 600         return result;
 601 }
 602
 603 static void reset_index_save_layout(struct index_save_layout *isl, u64 page_map_blocks)
 604 {
 605         u64 free_blocks;
 606         u64 next_block = isl->index_save.start_block;
 607
 608         isl->zone_count = 0;
 609         memset(&isl->save_data, 0, sizeof(isl->save_data));
 610
 611         isl->header = (struct layout_region) {
 612                 .start_block = next_block++,
 613                 .block_count = 1,
 614                 .kind = RL_KIND_HEADER,
 615                 .instance = RL_SOLE_INSTANCE,
 616         };
 617
 618         isl->index_page_map = (struct layout_region) {
 619                 .start_block = next_block,
 620                 .block_count = page_map_blocks,
 621                 .kind = RL_KIND_INDEX_PAGE_MAP,
 622                 .instance = RL_SOLE_INSTANCE,
 623         };
 624
 625         next_block += page_map_blocks;
 626
 627         free_blocks = isl->index_save.block_count - page_map_blocks - 1;
 628         isl->free_space = (struct layout_region) {
 629                 .start_block = next_block,
 630                 .block_count = free_blocks,
 631                 .kind = RL_KIND_EMPTY,
 632                 .instance = RL_SOLE_INSTANCE,
 633         };
 634 }
 635
 636 static int __must_check invalidate_old_save(struct index_layout *layout,
 637                                             struct index_save_layout *isl)
 638 {
 639         reset_index_save_layout(isl, layout->super.page_map_blocks);
 640         return write_index_save_layout(layout, isl);
 641 }
 642
 643 static int discard_index_state_data(struct index_layout *layout)
 644 {
 645         int result;
 646         int saved_result = UDS_SUCCESS;
 647         unsigned int i;
 648
 649         for (i = 0; i < layout->super.max_saves; i++) {
 650                 result = invalidate_old_save(layout, &layout->index.saves[i]);
 651                 if (result != UDS_SUCCESS)
 652                         saved_result = result;
 653         }
 654
 655         if (saved_result != UDS_SUCCESS) {
 656                 return uds_log_error_strerror(result,
 657                                               "%s: cannot destroy all index saves",
 658                                               __func__);
 659         }
 660
 661         return UDS_SUCCESS;
 662 }
 663
 664 static int __must_check make_layout_region_table(struct index_layout *layout,
 665                                                  struct region_table **table_ptr)
 666 {
 667         int result;
 668         unsigned int i;
 669         /* Regions: header, config, index, volume, saves, seal */
 670         u16 region_count = 5 + layout->super.max_saves;
 671         u16 payload;
 672         struct region_table *table;
 673         struct layout_region *lr;
 674
 675         result = uds_allocate_extended(struct region_table, region_count,
 676                                        struct layout_region, "layout region table",
 677                                        &table);
 678         if (result != UDS_SUCCESS)
 679                 return result;
 680
 681         lr = &table->regions[0];
 682         *lr++ = layout->header;
 683         *lr++ = layout->config;
 684         *lr++ = layout->index.sub_index;
 685         *lr++ = layout->index.volume;
 686
 687         for (i = 0; i < layout->super.max_saves; i++)
 688                 *lr++ = layout->index.saves[i].index_save;
 689
 690         *lr++ = layout->seal;
 691
 692         if (is_converted_super_block(&layout->super)) {
 693                 payload = sizeof(struct super_block_data);
 694         } else {
 695                 payload = (sizeof(struct super_block_data) -
 696                            sizeof(layout->super.volume_offset) -
 697                            sizeof(layout->super.start_offset));
 698         }
 699
 700         table->header = (struct region_header) {
 701                 .magic = REGION_MAGIC,
 702                 .region_blocks = layout->total_blocks,
 703                 .type = RH_TYPE_SUPER,
 704                 .version = 1,
 705                 .region_count = region_count,
 706                 .payload = payload,
 707         };
 708
 709         table->encoded_size = (sizeof(struct region_header) + payload +
 710                                region_count * sizeof(struct layout_region));
 711         *table_ptr = table;
 712         return UDS_SUCCESS;
 713 }
 714
 715 static int __must_check write_layout_header(struct index_layout *layout,
 716                                             struct region_table *table,
 717                                             struct buffered_writer *writer)
 718 {
 719         int result;
 720         u8 *buffer;
 721         size_t offset = 0;
 722
 723         result = uds_allocate(table->encoded_size, u8, "layout data", &buffer);
 724         if (result != UDS_SUCCESS)
 725                 return result;
 726
 727         encode_region_table(buffer, &offset, table);
 728         memcpy(buffer + offset, &layout->super.magic_label, MAGIC_SIZE);
 729         offset += MAGIC_SIZE;
 730         memcpy(buffer + offset, &layout->super.nonce_info, NONCE_INFO_SIZE);
 731         offset += NONCE_INFO_SIZE;
 732         encode_u64_le(buffer, &offset, layout->super.nonce);
 733         encode_u32_le(buffer, &offset, layout->super.version);
 734         encode_u32_le(buffer, &offset, layout->super.block_size);
 735         encode_u16_le(buffer, &offset, layout->super.index_count);
 736         encode_u16_le(buffer, &offset, layout->super.max_saves);
 737         encode_u32_le(buffer, &offset, 0);
 738         encode_u64_le(buffer, &offset, layout->super.open_chapter_blocks);
 739         encode_u64_le(buffer, &offset, layout->super.page_map_blocks);
 740
 741         if (is_converted_super_block(&layout->super)) {
 742                 encode_u64_le(buffer, &offset, layout->super.volume_offset);
 743                 encode_u64_le(buffer, &offset, layout->super.start_offset);
 744         }
 745
 746         result = uds_write_to_buffered_writer(writer, buffer, offset);
 747         uds_free(buffer);
 748         if (result != UDS_SUCCESS)
 749                 return result;
 750
 751         return uds_flush_buffered_writer(writer);
 752 }
 753
 754 static int __must_check write_uds_index_config(struct index_layout *layout,
 755                                                struct uds_configuration *config,
 756                                                off_t offset)
 757 {
 758         int result;
 759         struct buffered_writer *writer = NULL;
 760
 761         result = open_layout_writer(layout, &layout->config, offset, &writer);
 762         if (result != UDS_SUCCESS)
 763                 return uds_log_error_strerror(result, "failed to open config region");
 764
 765         result = uds_write_config_contents(writer, config, layout->super.version);
 766         if (result != UDS_SUCCESS) {
 767                 uds_free_buffered_writer(writer);
 768                 return uds_log_error_strerror(result, "failed to write config region");
 769         }
 770
 771         result = uds_flush_buffered_writer(writer);
 772         if (result != UDS_SUCCESS) {
 773                 uds_free_buffered_writer(writer);
 774                 return uds_log_error_strerror(result, "cannot flush config writer");
 775         }
 776
 777         uds_free_buffered_writer(writer);
 778         return UDS_SUCCESS;
 779 }
 780
 781 static int __must_check save_layout(struct index_layout *layout, off_t offset)
 782 {
 783         int result;
 784         struct buffered_writer *writer = NULL;
 785         struct region_table *table;
 786
 787         result = make_layout_region_table(layout, &table);
 788         if (result != UDS_SUCCESS)
 789                 return result;
 790
 791         result = open_layout_writer(layout, &layout->header, offset, &writer);
 792         if (result != UDS_SUCCESS) {
 793                 uds_free(table);
 794                 return result;
 795         }
 796
 797         result = write_layout_header(layout, table, writer);
 798         uds_free(table);
 799         uds_free_buffered_writer(writer);
 800
 801         return result;
 802 }
 803
 804 static int create_index_layout(struct index_layout *layout, struct uds_configuration *config)
 805 {
 806         int result;
 807         struct save_layout_sizes sizes;
 808
 809         result = compute_sizes(config, &sizes);
 810         if (result != UDS_SUCCESS)
 811                 return result;
 812
 813         result = uds_allocate(sizes.save_count, struct index_save_layout, __func__,
 814                               &layout->index.saves);
 815         if (result != UDS_SUCCESS)
 816                 return result;
 817
 818         initialize_layout(layout, &sizes);
 819
 820         result = discard_index_state_data(layout);
 821         if (result != UDS_SUCCESS)
 822                 return result;
 823
 824         result = write_uds_index_config(layout, config, 0);
 825         if (result != UDS_SUCCESS)
 826                 return result;
 827
 828         return save_layout(layout, 0);
 829 }
 830
 831 static u64 generate_index_save_nonce(u64 volume_nonce, struct index_save_layout *isl)
 832 {
 833         struct save_nonce_data {
 834                 struct index_save_data data;
 835                 u64 offset;
 836         } nonce_data;
 837         u8 buffer[sizeof(nonce_data)];
 838         size_t offset = 0;
 839
 840         encode_u64_le(buffer, &offset, isl->save_data.timestamp);
 841         encode_u64_le(buffer, &offset, 0);
 842         encode_u32_le(buffer, &offset, isl->save_data.version);
 843         encode_u32_le(buffer, &offset, 0U);
 844         encode_u64_le(buffer, &offset, isl->index_save.start_block);
 845         ASSERT_LOG_ONLY(offset == sizeof(nonce_data),
 846                         "%zu bytes encoded of %zu expected", offset, sizeof(nonce_data));
 847         return generate_secondary_nonce(volume_nonce, buffer, sizeof(buffer));
 848 }
 849
 850 static u64 validate_index_save_layout(struct index_save_layout *isl, u64 volume_nonce)
 851 {
 852         if ((isl->zone_count == 0) || (isl->save_data.timestamp == 0))
 853                 return 0;
 854
 855         if (isl->save_data.nonce != generate_index_save_nonce(volume_nonce, isl))
 856                 return 0;
 857
 858         return isl->save_data.timestamp;
 859 }
 860
 861 static int find_latest_uds_index_save_slot(struct index_layout *layout,
 862                                            struct index_save_layout **isl_ptr)
 863 {
 864         struct index_save_layout *latest = NULL;
 865         struct index_save_layout *isl;
 866         unsigned int i;
 867         u64 save_time = 0;
 868         u64 latest_time = 0;
 869
 870         for (i = 0; i < layout->super.max_saves; i++) {
 871                 isl = &layout->index.saves[i];
 872                 save_time = validate_index_save_layout(isl, layout->index.nonce);
 873                 if (save_time > latest_time) {
 874                         latest = isl;
 875                         latest_time = save_time;
 876                 }
 877         }
 878
 879         if (latest == NULL) {
 880                 uds_log_error("No valid index save found");
 881                 return UDS_INDEX_NOT_SAVED_CLEANLY;
 882         }
 883
 884         *isl_ptr = latest;
 885         return UDS_SUCCESS;
 886 }
 887
 888 int uds_discard_open_chapter(struct index_layout *layout)
 889 {
 890         int result;
 891         struct index_save_layout *isl;
 892         struct buffered_writer *writer;
 893
 894         result = find_latest_uds_index_save_slot(layout, &isl);
 895         if (result != UDS_SUCCESS)
 896                 return result;
 897
 898         result = open_region_writer(layout, &isl->open_chapter, &writer);
 899         if (result != UDS_SUCCESS)
 900                 return result;
 901
 902         result = uds_write_to_buffered_writer(writer, NULL, UDS_BLOCK_SIZE);
 903         if (result != UDS_SUCCESS) {
 904                 uds_free_buffered_writer(writer);
 905                 return result;
 906         }
 907
 908         result = uds_flush_buffered_writer(writer);
 909         uds_free_buffered_writer(writer);
 910         return result;
 911 }
 912
 913 int uds_load_index_state(struct index_layout *layout, struct uds_index *index)
 914 {
 915         int result;
 916         unsigned int zone;
 917         struct index_save_layout *isl;
 918         struct buffered_reader *readers[MAX_ZONES];
 919
 920         result = find_latest_uds_index_save_slot(layout, &isl);
 921         if (result != UDS_SUCCESS)
 922                 return result;
 923
 924         index->newest_virtual_chapter = isl->state_data.newest_chapter;
 925         index->oldest_virtual_chapter = isl->state_data.oldest_chapter;
 926         index->last_save = isl->state_data.last_save;
 927
 928         result = open_region_reader(layout, &isl->open_chapter, &readers[0]);
 929         if (result != UDS_SUCCESS)
 930                 return result;
 931
 932         result = uds_load_open_chapter(index, readers[0]);
 933         uds_free_buffered_reader(readers[0]);
 934         if (result != UDS_SUCCESS)
 935                 return result;
 936
 937         for (zone = 0; zone < isl->zone_count; zone++) {
 938                 result = open_region_reader(layout, &isl->volume_index_zones[zone],
 939                                             &readers[zone]);
 940                 if (result != UDS_SUCCESS) {
 941                         for (; zone > 0; zone--)
 942                                 uds_free_buffered_reader(readers[zone - 1]);
 943
 944                         return result;
 945                 }
 946         }
 947
 948         result = uds_load_volume_index(index->volume_index, readers, isl->zone_count);
 949         for (zone = 0; zone < isl->zone_count; zone++)
 950                 uds_free_buffered_reader(readers[zone]);
 951         if (result != UDS_SUCCESS)
 952                 return result;
 953
 954         result = open_region_reader(layout, &isl->index_page_map, &readers[0]);
 955         if (result != UDS_SUCCESS)
 956                 return result;
 957
 958         result = uds_read_index_page_map(index->volume->index_page_map, readers[0]);
 959         uds_free_buffered_reader(readers[0]);
 960
 961         return result;
 962 }
 963
 964 static struct index_save_layout *select_oldest_index_save_layout(struct index_layout *layout)
 965 {
 966         struct index_save_layout *oldest = NULL;
 967         struct index_save_layout *isl;
 968         unsigned int i;
 969         u64 save_time = 0;
 970         u64 oldest_time = 0;
 971
 972         for (i = 0; i < layout->super.max_saves; i++) {
 973                 isl = &layout->index.saves[i];
 974                 save_time = validate_index_save_layout(isl, layout->index.nonce);
 975                 if (oldest == NULL || save_time < oldest_time) {
 976                         oldest = isl;
 977                         oldest_time = save_time;
 978                 }
 979         }
 980
 981         return oldest;
 982 }
 983
 984 static void instantiate_index_save_layout(struct index_save_layout *isl,
 985                                           struct super_block_data *super,
 986                                           u64 volume_nonce, unsigned int zone_count)
 987 {
 988         unsigned int z;
 989         u64 next_block;
 990         u64 free_blocks;
 991         u64 volume_index_blocks;
 992
 993         isl->zone_count = zone_count;
 994         memset(&isl->save_data, 0, sizeof(isl->save_data));
 995         isl->save_data.timestamp = ktime_to_ms(current_time_ns(CLOCK_REALTIME));
 996         isl->save_data.version = 1;
 997         isl->save_data.nonce = generate_index_save_nonce(volume_nonce, isl);
 998
 999         next_block = isl->index_save.start_block;
1000         isl->header = (struct layout_region) {
1001                 .start_block = next_block++,
1002                 .block_count = 1,
1003                 .kind = RL_KIND_HEADER,
1004                 .instance = RL_SOLE_INSTANCE,
1005         };
1006
1007         isl->index_page_map = (struct layout_region) {
1008                 .start_block = next_block,
1009                 .block_count = super->page_map_blocks,
1010                 .kind = RL_KIND_INDEX_PAGE_MAP,
1011                 .instance = RL_SOLE_INSTANCE,
1012         };
1013         next_block += super->page_map_blocks;
1014
1015         free_blocks = (isl->index_save.block_count - 1 -
1016                        super->page_map_blocks -
1017                        super->open_chapter_blocks);
1018         volume_index_blocks = free_blocks / isl->zone_count;
1019         for (z = 0; z < isl->zone_count; z++) {
1020                 isl->volume_index_zones[z] = (struct layout_region) {
1021                         .start_block = next_block,
1022                         .block_count = volume_index_blocks,
1023                         .kind = RL_KIND_VOLUME_INDEX,
1024                         .instance = z,
1025                 };
1026
1027                 next_block += volume_index_blocks;
1028                 free_blocks -= volume_index_blocks;
1029         }
1030
1031         isl->open_chapter = (struct layout_region) {
1032                 .start_block = next_block,
1033                 .block_count = super->open_chapter_blocks,
1034                 .kind = RL_KIND_OPEN_CHAPTER,
1035                 .instance = RL_SOLE_INSTANCE,
1036         };
1037
1038         next_block += super->open_chapter_blocks;
1039
1040         isl->free_space = (struct layout_region) {
1041                 .start_block = next_block,
1042                 .block_count = free_blocks,
1043                 .kind = RL_KIND_EMPTY,
1044                 .instance = RL_SOLE_INSTANCE,
1045         };
1046 }
1047
1048 static int setup_uds_index_save_slot(struct index_layout *layout,
1049                                      unsigned int zone_count,
1050                                      struct index_save_layout **isl_ptr)
1051 {
1052         int result;
1053         struct index_save_layout *isl;
1054
1055         isl = select_oldest_index_save_layout(layout);
1056         result = invalidate_old_save(layout, isl);
1057         if (result != UDS_SUCCESS)
1058                 return result;
1059
1060         instantiate_index_save_layout(isl, &layout->super, layout->index.nonce,
1061                                       zone_count);
1062
1063         *isl_ptr = isl;
1064         return UDS_SUCCESS;
1065 }
1066
1067 static void cancel_uds_index_save(struct index_save_layout *isl)
1068 {
1069         memset(&isl->save_data, 0, sizeof(isl->save_data));
1070         memset(&isl->state_data, 0, sizeof(isl->state_data));
1071         isl->zone_count = 0;
1072 }
1073
1074 int uds_save_index_state(struct index_layout *layout, struct uds_index *index)
1075 {
1076         int result;
1077         unsigned int zone;
1078         struct index_save_layout *isl;
1079         struct buffered_writer *writers[MAX_ZONES];
1080
1081         result = setup_uds_index_save_slot(layout, index->zone_count, &isl);
1082         if (result != UDS_SUCCESS)
1083                 return result;
1084
1085         isl->state_data = (struct index_state_data301) {
1086                 .newest_chapter = index->newest_virtual_chapter,
1087                 .oldest_chapter = index->oldest_virtual_chapter,
1088                 .last_save = index->last_save,
1089         };
1090
1091         result = open_region_writer(layout, &isl->open_chapter, &writers[0]);
1092         if (result != UDS_SUCCESS) {
1093                 cancel_uds_index_save(isl);
1094                 return result;
1095         }
1096
1097         result = uds_save_open_chapter(index, writers[0]);
1098         uds_free_buffered_writer(writers[0]);
1099         if (result != UDS_SUCCESS) {
1100                 cancel_uds_index_save(isl);
1101                 return result;
1102         }
1103
1104         for (zone = 0; zone < index->zone_count; zone++) {
1105                 result = open_region_writer(layout, &isl->volume_index_zones[zone],
1106                                             &writers[zone]);
1107                 if (result != UDS_SUCCESS) {
1108                         for (; zone > 0; zone--)
1109                                 uds_free_buffered_writer(writers[zone - 1]);
1110
1111                         cancel_uds_index_save(isl);
1112                         return result;
1113                 }
1114         }
1115
1116         result = uds_save_volume_index(index->volume_index, writers, index->zone_count);
1117         for (zone = 0; zone < index->zone_count; zone++)
1118                 uds_free_buffered_writer(writers[zone]);
1119         if (result != UDS_SUCCESS) {
1120                 cancel_uds_index_save(isl);
1121                 return result;
1122         }
1123
1124         result = open_region_writer(layout, &isl->index_page_map, &writers[0]);
1125         if (result != UDS_SUCCESS) {
1126                 cancel_uds_index_save(isl);
1127                 return result;
1128         }
1129
1130         result = uds_write_index_page_map(index->volume->index_page_map, writers[0]);
1131         uds_free_buffered_writer(writers[0]);
1132         if (result != UDS_SUCCESS) {
1133                 cancel_uds_index_save(isl);
1134                 return result;
1135         }
1136
1137         return write_index_save_layout(layout, isl);
1138 }
1139
1140 static int __must_check load_region_table(struct buffered_reader *reader,
1141                                           struct region_table **table_ptr)
1142 {
1143         int result;
1144         unsigned int i;
1145         struct region_header header;
1146         struct region_table *table;
1147         u8 buffer[sizeof(struct region_header)];
1148         size_t offset = 0;
1149
1150         result = uds_read_from_buffered_reader(reader, buffer, sizeof(buffer));
1151         if (result != UDS_SUCCESS)
1152                 return uds_log_error_strerror(result, "cannot read region table header");
1153
1154         decode_u64_le(buffer, &offset, &header.magic);
1155         decode_u64_le(buffer, &offset, &header.region_blocks);
1156         decode_u16_le(buffer, &offset, &header.type);
1157         decode_u16_le(buffer, &offset, &header.version);
1158         decode_u16_le(buffer, &offset, &header.region_count);
1159         decode_u16_le(buffer, &offset, &header.payload);
1160
1161         if (header.magic != REGION_MAGIC)
1162                 return UDS_NO_INDEX;
1163
1164         if (header.version != 1) {
1165                 return uds_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1166                                               "unknown region table version %hu",
1167                                               header.version);
1168         }
1169
1170         result = uds_allocate_extended(struct region_table, header.region_count,
1171                                        struct layout_region,
1172                                        "single file layout region table", &table);
1173         if (result != UDS_SUCCESS)
1174                 return result;
1175
1176         table->header = header;
1177         for (i = 0; i < header.region_count; i++) {
1178                 u8 region_buffer[sizeof(struct layout_region)];
1179
1180                 offset = 0;
1181                 result = uds_read_from_buffered_reader(reader, region_buffer,
1182                                                        sizeof(region_buffer));
1183                 if (result != UDS_SUCCESS) {
1184                         uds_free(table);
1185                         return uds_log_error_strerror(UDS_CORRUPT_DATA,
1186                                                       "cannot read region table layouts");
1187                 }
1188
1189                 decode_u64_le(region_buffer, &offset, &table->regions[i].start_block);
1190                 decode_u64_le(region_buffer, &offset, &table->regions[i].block_count);
1191                 offset += sizeof(u32);
1192                 decode_u16_le(region_buffer, &offset, &table->regions[i].kind);
1193                 decode_u16_le(region_buffer, &offset, &table->regions[i].instance);
1194         }
1195
1196         *table_ptr = table;
1197         return UDS_SUCCESS;
1198 }
1199
1200 static int __must_check read_super_block_data(struct buffered_reader *reader,
1201                                               struct index_layout *layout,
1202                                               size_t saved_size)
1203 {
1204         int result;
1205         struct super_block_data *super = &layout->super;
1206         u8 *buffer;
1207         size_t offset = 0;
1208
1209         result = uds_allocate(saved_size, u8, "super block data", &buffer);
1210         if (result != UDS_SUCCESS)
1211                 return result;
1212
1213         result = uds_read_from_buffered_reader(reader, buffer, saved_size);
1214         if (result != UDS_SUCCESS) {
1215                 uds_free(buffer);
1216                 return uds_log_error_strerror(result, "cannot read region table header");
1217         }
1218
1219         memcpy(&super->magic_label, buffer, MAGIC_SIZE);
1220         offset += MAGIC_SIZE;
1221         memcpy(&super->nonce_info, buffer + offset, NONCE_INFO_SIZE);
1222         offset += NONCE_INFO_SIZE;
1223         decode_u64_le(buffer, &offset, &super->nonce);
1224         decode_u32_le(buffer, &offset, &super->version);
1225         decode_u32_le(buffer, &offset, &super->block_size);
1226         decode_u16_le(buffer, &offset, &super->index_count);
1227         decode_u16_le(buffer, &offset, &super->max_saves);
1228         offset += sizeof(u32);
1229         decode_u64_le(buffer, &offset, &super->open_chapter_blocks);
1230         decode_u64_le(buffer, &offset, &super->page_map_blocks);
1231
1232         if (is_converted_super_block(super)) {
1233                 decode_u64_le(buffer, &offset, &super->volume_offset);
1234                 decode_u64_le(buffer, &offset, &super->start_offset);
1235         } else {
1236                 super->volume_offset = 0;
1237                 super->start_offset = 0;
1238         }
1239
1240         uds_free(buffer);
1241
1242         if (memcmp(super->magic_label, LAYOUT_MAGIC, MAGIC_SIZE) != 0)
1243                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1244                                               "unknown superblock magic label");
1245
1246         if ((super->version < SUPER_VERSION_MINIMUM) ||
1247             (super->version == 4) || (super->version == 5) || (super->version == 6) ||
1248             (super->version > SUPER_VERSION_MAXIMUM)) {
1249                 return uds_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1250                                               "unknown superblock version number %u",
1251                                               super->version);
1252         }
1253
1254         if (super->volume_offset < super->start_offset) {
1255                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1256                                               "inconsistent offsets (start %llu, volume %llu)",
1257                                               (unsigned long long) super->start_offset,
1258                                               (unsigned long long) super->volume_offset);
1259         }
1260
1261         /* Sub-indexes are no longer used but the layout retains this field. */
1262         if (super->index_count != 1) {
1263                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1264                                               "invalid subindex count %u",
1265                                               super->index_count);
1266         }
1267
1268         if (generate_primary_nonce(super->nonce_info, sizeof(super->nonce_info)) != super->nonce) {
1269                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1270                                               "inconsistent superblock nonce");
1271         }
1272
1273         return UDS_SUCCESS;
1274 }
1275
1276 static int __must_check verify_region(struct layout_region *lr, u64 start_block,
1277                                       enum region_kind kind, unsigned int instance)
1278 {
1279         if (lr->start_block != start_block)
1280                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1281                                               "incorrect layout region offset");
1282
1283         if (lr->kind != kind)
1284                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1285                                               "incorrect layout region kind");
1286
1287         if (lr->instance != instance) {
1288                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1289                                               "incorrect layout region instance");
1290         }
1291
1292         return UDS_SUCCESS;
1293 }
1294
1295 static int __must_check verify_sub_index(struct index_layout *layout, u64 start_block,
1296                                          struct region_table *table)
1297 {
1298         int result;
1299         unsigned int i;
1300         struct sub_index_layout *sil = &layout->index;
1301         u64 next_block = start_block;
1302
1303         sil->sub_index = table->regions[2];
1304         result = verify_region(&sil->sub_index, next_block, RL_KIND_INDEX, 0);
1305         if (result != UDS_SUCCESS)
1306                 return result;
1307
1308         define_sub_index_nonce(layout);
1309
1310         sil->volume = table->regions[3];
1311         result = verify_region(&sil->volume, next_block, RL_KIND_VOLUME,
1312                                RL_SOLE_INSTANCE);
1313         if (result != UDS_SUCCESS)
1314                 return result;
1315
1316         next_block += sil->volume.block_count + layout->super.volume_offset;
1317
1318         for (i = 0; i < layout->super.max_saves; i++) {
1319                 sil->saves[i].index_save = table->regions[i + 4];
1320                 result = verify_region(&sil->saves[i].index_save, next_block,
1321                                        RL_KIND_SAVE, i);
1322                 if (result != UDS_SUCCESS)
1323                         return result;
1324
1325                 next_block += sil->saves[i].index_save.block_count;
1326         }
1327
1328         next_block -= layout->super.volume_offset;
1329         if (next_block != start_block + sil->sub_index.block_count) {
1330                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1331                                               "sub index region does not span all saves");
1332         }
1333
1334         return UDS_SUCCESS;
1335 }
1336
1337 static int __must_check reconstitute_layout(struct index_layout *layout,
1338                                             struct region_table *table, u64 first_block)
1339 {
1340         int result;
1341         u64 next_block = first_block;
1342
1343         result = uds_allocate(layout->super.max_saves, struct index_save_layout,
1344                               __func__, &layout->index.saves);
1345         if (result != UDS_SUCCESS)
1346                 return result;
1347
1348         layout->total_blocks = table->header.region_blocks;
1349
1350         layout->header = table->regions[0];
1351         result = verify_region(&layout->header, next_block++, RL_KIND_HEADER,
1352                                RL_SOLE_INSTANCE);
1353         if (result != UDS_SUCCESS)
1354                 return result;
1355
1356         layout->config = table->regions[1];
1357         result = verify_region(&layout->config, next_block++, RL_KIND_CONFIG,
1358                                RL_SOLE_INSTANCE);
1359         if (result != UDS_SUCCESS)
1360                 return result;
1361
1362         result = verify_sub_index(layout, next_block, table);
1363         if (result != UDS_SUCCESS)
1364                 return result;
1365
1366         next_block += layout->index.sub_index.block_count;
1367
1368         layout->seal = table->regions[table->header.region_count - 1];
1369         result = verify_region(&layout->seal, next_block + layout->super.volume_offset,
1370                                RL_KIND_SEAL, RL_SOLE_INSTANCE);
1371         if (result != UDS_SUCCESS)
1372                 return result;
1373
1374         if (++next_block != (first_block + layout->total_blocks)) {
1375                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1376                                               "layout table does not span total blocks");
1377         }
1378
1379         return UDS_SUCCESS;
1380 }
1381
1382 static int __must_check load_super_block(struct index_layout *layout, size_t block_size,
1383                                          u64 first_block, struct buffered_reader *reader)
1384 {
1385         int result;
1386         struct region_table *table = NULL;
1387         struct super_block_data *super = &layout->super;
1388
1389         result = load_region_table(reader, &table);
1390         if (result != UDS_SUCCESS)
1391                 return result;
1392
1393         if (table->header.type != RH_TYPE_SUPER) {
1394                 uds_free(table);
1395                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1396                                               "not a superblock region table");
1397         }
1398
1399         result = read_super_block_data(reader, layout, table->header.payload);
1400         if (result != UDS_SUCCESS) {
1401                 uds_free(table);
1402                 return uds_log_error_strerror(result, "unknown superblock format");
1403         }
1404
1405         if (super->block_size != block_size) {
1406                 uds_free(table);
1407                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1408                                               "superblock saved block_size %u differs from supplied block_size %zu",
1409                                               super->block_size, block_size);
1410         }
1411
1412         first_block -= (super->volume_offset - super->start_offset);
1413         result = reconstitute_layout(layout, table, first_block);
1414         uds_free(table);
1415         return result;
1416 }
1417
1418 static int __must_check read_index_save_data(struct buffered_reader *reader,
1419                                              struct index_save_layout *isl,
1420                                              size_t saved_size)
1421 {
1422         int result;
1423         struct index_state_version file_version;
1424         u8 buffer[sizeof(struct index_save_data) + sizeof(struct index_state_data301)];
1425         size_t offset = 0;
1426
1427         if (saved_size != sizeof(buffer)) {
1428                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1429                                               "unexpected index save data size %zu",
1430                                               saved_size);
1431         }
1432
1433         result = uds_read_from_buffered_reader(reader, buffer, sizeof(buffer));
1434         if (result != UDS_SUCCESS)
1435                 return uds_log_error_strerror(result, "cannot read index save data");
1436
1437         decode_u64_le(buffer, &offset, &isl->save_data.timestamp);
1438         decode_u64_le(buffer, &offset, &isl->save_data.nonce);
1439         decode_u32_le(buffer, &offset, &isl->save_data.version);
1440         offset += sizeof(u32);
1441
1442         if (isl->save_data.version > 1) {
1443                 return uds_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1444                                               "unknown index save version number %u",
1445                                               isl->save_data.version);
1446         }
1447
1448         decode_s32_le(buffer, &offset, &file_version.signature);
1449         decode_s32_le(buffer, &offset, &file_version.version_id);
1450
1451         if ((file_version.signature != INDEX_STATE_VERSION_301.signature) ||
1452             (file_version.version_id != INDEX_STATE_VERSION_301.version_id)) {
1453                 return uds_log_error_strerror(UDS_UNSUPPORTED_VERSION,
1454                                               "index state version %d,%d is unsupported",
1455                                               file_version.signature,
1456                                               file_version.version_id);
1457         }
1458
1459         decode_u64_le(buffer, &offset, &isl->state_data.newest_chapter);
1460         decode_u64_le(buffer, &offset, &isl->state_data.oldest_chapter);
1461         decode_u64_le(buffer, &offset, &isl->state_data.last_save);
1462         /* Skip past some historical fields that are now unused */
1463         offset += sizeof(u32) + sizeof(u32);
1464         return UDS_SUCCESS;
1465 }
1466
1467 static int __must_check reconstruct_index_save(struct index_save_layout *isl,
1468                                                struct region_table *table)
1469 {
1470         int result;
1471         unsigned int z;
1472         struct layout_region *last_region;
1473         u64 next_block = isl->index_save.start_block;
1474         u64 last_block = next_block + isl->index_save.block_count;
1475
1476         isl->zone_count = table->header.region_count - 3;
1477
1478         last_region = &table->regions[table->header.region_count - 1];
1479         if (last_region->kind == RL_KIND_EMPTY) {
1480                 isl->free_space = *last_region;
1481                 isl->zone_count--;
1482         } else {
1483                 isl->free_space = (struct layout_region) {
1484                         .start_block = last_block,
1485                         .block_count = 0,
1486                         .kind = RL_KIND_EMPTY,
1487                         .instance = RL_SOLE_INSTANCE,
1488                 };
1489         }
1490
1491         isl->header = table->regions[0];
1492         result = verify_region(&isl->header, next_block++, RL_KIND_HEADER,
1493                                RL_SOLE_INSTANCE);
1494         if (result != UDS_SUCCESS)
1495                 return result;
1496
1497         isl->index_page_map = table->regions[1];
1498         result = verify_region(&isl->index_page_map, next_block, RL_KIND_INDEX_PAGE_MAP,
1499                                RL_SOLE_INSTANCE);
1500         if (result != UDS_SUCCESS)
1501                 return result;
1502
1503         next_block += isl->index_page_map.block_count;
1504
1505         for (z = 0; z < isl->zone_count; z++) {
1506                 isl->volume_index_zones[z] = table->regions[z + 2];
1507                 result = verify_region(&isl->volume_index_zones[z], next_block,
1508                                        RL_KIND_VOLUME_INDEX, z);
1509                 if (result != UDS_SUCCESS)
1510                         return result;
1511
1512                 next_block += isl->volume_index_zones[z].block_count;
1513         }
1514
1515         isl->open_chapter = table->regions[isl->zone_count + 2];
1516         result = verify_region(&isl->open_chapter, next_block, RL_KIND_OPEN_CHAPTER,
1517                                RL_SOLE_INSTANCE);
1518         if (result != UDS_SUCCESS)
1519                 return result;
1520
1521         next_block += isl->open_chapter.block_count;
1522
1523         result = verify_region(&isl->free_space, next_block, RL_KIND_EMPTY,
1524                                RL_SOLE_INSTANCE);
1525         if (result != UDS_SUCCESS)
1526                 return result;
1527
1528         next_block += isl->free_space.block_count;
1529         if (next_block != last_block) {
1530                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1531                                               "index save layout table incomplete");
1532         }
1533
1534         return UDS_SUCCESS;
1535 }
1536
1537 static int __must_check load_index_save(struct index_save_layout *isl,
1538                                         struct buffered_reader *reader,
1539                                         unsigned int instance)
1540 {
1541         int result;
1542         struct region_table *table = NULL;
1543
1544         result = load_region_table(reader, &table);
1545         if (result != UDS_SUCCESS) {
1546                 return uds_log_error_strerror(result, "cannot read index save %u header",
1547                                               instance);
1548         }
1549
1550         if (table->header.region_blocks != isl->index_save.block_count) {
1551                 u64 region_blocks = table->header.region_blocks;
1552
1553                 uds_free(table);
1554                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1555                                               "unexpected index save %u region block count %llu",
1556                                               instance,
1557                                               (unsigned long long) region_blocks);
1558         }
1559
1560         if (table->header.type == RH_TYPE_UNSAVED) {
1561                 uds_free(table);
1562                 reset_index_save_layout(isl, 0);
1563                 return UDS_SUCCESS;
1564         }
1565
1566
1567         if (table->header.type != RH_TYPE_SAVE) {
1568                 uds_free(table);
1569                 return uds_log_error_strerror(UDS_CORRUPT_DATA,
1570                                               "unexpected index save %u header type %u",
1571                                               instance, table->header.type);
1572         }
1573
1574         result = read_index_save_data(reader, isl, table->header.payload);
1575         if (result != UDS_SUCCESS) {
1576                 uds_free(table);
1577                 return uds_log_error_strerror(result,
1578                                               "unknown index save %u data format",
1579                                               instance);
1580         }
1581
1582         result = reconstruct_index_save(isl, table);
1583         uds_free(table);
1584         if (result != UDS_SUCCESS) {
1585                 return uds_log_error_strerror(result, "cannot reconstruct index save %u",
1586                                               instance);
1587         }
1588
1589         return UDS_SUCCESS;
1590 }
1591
1592 static int __must_check load_sub_index_regions(struct index_layout *layout)
1593 {
1594         int result;
1595         unsigned int j;
1596         struct index_save_layout *isl;
1597         struct buffered_reader *reader;
1598
1599         for (j = 0; j < layout->super.max_saves; j++) {
1600                 isl = &layout->index.saves[j];
1601                 result = open_region_reader(layout, &isl->index_save, &reader);
1602
1603                 if (result != UDS_SUCCESS) {
1604                         uds_log_error_strerror(result,
1605                                                "cannot get reader for index 0 save %u",
1606                                                j);
1607                         return result;
1608                 }
1609
1610                 result = load_index_save(isl, reader, j);
1611                 uds_free_buffered_reader(reader);
1612                 if (result != UDS_SUCCESS) {
1613                         /* Another save slot might be valid. */
1614                         reset_index_save_layout(isl, 0);
1615                         continue;
1616                 }
1617         }
1618
1619         return UDS_SUCCESS;
1620 }
1621
1622 static int __must_check verify_uds_index_config(struct index_layout *layout,
1623                                                 struct uds_configuration *config)
1624 {
1625         int result;
1626         struct buffered_reader *reader = NULL;
1627         u64 offset;
1628
1629         offset = layout->super.volume_offset - layout->super.start_offset;
1630         result = open_layout_reader(layout, &layout->config, offset, &reader);
1631         if (result != UDS_SUCCESS)
1632                 return uds_log_error_strerror(result, "failed to open config reader");
1633
1634         result = uds_validate_config_contents(reader, config);
1635         if (result != UDS_SUCCESS) {
1636                 uds_free_buffered_reader(reader);
1637                 return uds_log_error_strerror(result, "failed to read config region");
1638         }
1639
1640         uds_free_buffered_reader(reader);
1641         return UDS_SUCCESS;
1642 }
1643
1644 static int load_index_layout(struct index_layout *layout, struct uds_configuration *config)
1645 {
1646         int result;
1647         struct buffered_reader *reader;
1648
1649         result = uds_make_buffered_reader(layout->factory,
1650                                           layout->offset / UDS_BLOCK_SIZE, 1, &reader);
1651         if (result != UDS_SUCCESS)
1652                 return uds_log_error_strerror(result, "unable to read superblock");
1653
1654         result = load_super_block(layout, UDS_BLOCK_SIZE,
1655                                   layout->offset / UDS_BLOCK_SIZE, reader);
1656         uds_free_buffered_reader(reader);
1657         if (result != UDS_SUCCESS)
1658                 return result;
1659
1660         result = verify_uds_index_config(layout, config);
1661         if (result != UDS_SUCCESS)
1662                 return result;
1663
1664         return load_sub_index_regions(layout);
1665 }
1666
1667 static int create_layout_factory(struct index_layout *layout,
1668                                  const struct uds_configuration *config)
1669 {
1670         int result;
1671         size_t writable_size;
1672         struct io_factory *factory = NULL;
1673
1674         result = uds_make_io_factory(config->bdev, &factory);
1675         if (result != UDS_SUCCESS)
1676                 return result;
1677
1678         writable_size = uds_get_writable_size(factory) & -UDS_BLOCK_SIZE;
1679         if (writable_size < config->size + config->offset) {
1680                 uds_put_io_factory(factory);
1681                 uds_log_error("index storage (%zu) is smaller than the requested size %zu",
1682                               writable_size, config->size + config->offset);
1683                 return -ENOSPC;
1684         }
1685
1686         layout->factory = factory;
1687         layout->factory_size = (config->size > 0) ? config->size : writable_size;
1688         layout->offset = config->offset;
1689         return UDS_SUCCESS;
1690 }
1691
1692 int uds_make_index_layout(struct uds_configuration *config, bool new_layout,
1693                           struct index_layout **layout_ptr)
1694 {
1695         int result;
1696         struct index_layout *layout = NULL;
1697         struct save_layout_sizes sizes;
1698
1699         result = compute_sizes(config, &sizes);
1700         if (result != UDS_SUCCESS)
1701                 return result;
1702
1703         result = uds_allocate(1, struct index_layout, __func__, &layout);
1704         if (result != UDS_SUCCESS)
1705                 return result;
1706
1707         result = create_layout_factory(layout, config);
1708         if (result != UDS_SUCCESS) {
1709                 uds_free_index_layout(layout);
1710                 return result;
1711         }
1712
1713         if (layout->factory_size < sizes.total_size) {
1714                 uds_log_error("index storage (%zu) is smaller than the required size %llu",
1715                               layout->factory_size,
1716                               (unsigned long long) sizes.total_size);
1717                 uds_free_index_layout(layout);
1718                 return -ENOSPC;
1719         }
1720
1721         if (new_layout)
1722                 result = create_index_layout(layout, config);
1723         else
1724                 result = load_index_layout(layout, config);
1725         if (result != UDS_SUCCESS) {
1726                 uds_free_index_layout(layout);
1727                 return result;
1728         }
1729
1730         *layout_ptr = layout;
1731         return UDS_SUCCESS;
1732 }
1733
1734 void uds_free_index_layout(struct index_layout *layout)
1735 {
1736         if (layout == NULL)
1737                 return;
1738
1739         uds_free(layout->index.saves);
1740         if (layout->factory != NULL)
1741                 uds_put_io_factory(layout->factory);
1742
1743         uds_free(layout);
1744 }
1745
1746 int uds_replace_index_layout_storage(struct index_layout *layout,
1747                                      struct block_device *bdev)
1748 {
1749         return uds_replace_storage(layout->factory, bdev);
1750 }
1751
1752 /* Obtain a dm_bufio_client for the volume region. */
1753 int uds_open_volume_bufio(struct index_layout *layout, size_t block_size,
1754                           unsigned int reserved_buffers,
1755                           struct dm_bufio_client **client_ptr)
1756 {
1757         off_t offset = (layout->index.volume.start_block +
1758                         layout->super.volume_offset -
1759                         layout->super.start_offset);
1760
1761         return uds_make_bufio(layout->factory, offset, block_size, reserved_buffers,
1762                               client_ptr);
1763 }
1764
1765 u64 uds_get_volume_nonce(struct index_layout *layout)
1766 {
1767         return layout->index.nonce;
1768 }