// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright 2023 Red Hat
 */

#include "index-layout.h"

#include <linux/random.h>

#include "logger.h"
#include "memory-alloc.h"
#include "murmurhash3.h"
#include "numeric.h"
#include "time-utils.h"

#include "config.h"
#include "open-chapter.h"
#include "volume-index.h"

/*
 * The UDS layout on storage media is divided into a number of fixed-size regions, the sizes of
 * which are computed when the index is created. Every header and region begins on 4K block
 * boundary. Save regions are further sub-divided into regions of their own.
 *
 * Each region has a kind and an instance number. Some kinds only have one instance and therefore
 * use RL_SOLE_INSTANCE (-1) as the instance number. The RL_KIND_INDEX used to use instances to
 * represent sub-indices; now, however there is only ever one sub-index and therefore one instance.
 * The RL_KIND_VOLUME_INDEX uses instances to record which zone is being saved.
 *
 * Every region header has a type and version.
 *
 *     +-+-+---------+--------+--------+-+
 *     | | |   I N D E X  0   101, 0   | |
 *     |H|C+---------+--------+--------+S|
 *     |D|f| Volume  | Save   | Save   |e|
 *     |R|g| Region  | Region | Region |a|
 *     | | | 201, -1 | 202, 0 | 202, 1 |l|
 *     +-+-+--------+---------+--------+-+
 *
 * The header contains the encoded region layout table as well as some index configuration data.
 * The sub-index region and its subdivisions are maintained in the same table.
 *
 * There are two save regions to preserve the old state in case saving the new state is incomplete.
 * They are used in alternation. Each save region is further divided into sub-regions.
 *
 *     +-+-----+------+------+-----+-----+
 *     |H| IPM | MI   | MI   |     | OC  |
 *     |D|     | zone | zone | ... |     |
 *     |R| 301 | 302  | 302  |     | 303 |
 *     | | -1  |  0   |  1   |     | -1  |
 *     +-+-----+------+------+-----+-----+
 *
 * The header contains the encoded region layout table as well as index state data for that save.
 * Each save also has a unique nonce.
 */

#define NONCE_INFO_SIZE 32
#define MAX_SAVES 2

enum region_kind {
        RL_KIND_EMPTY = 0,
        RL_KIND_HEADER = 1,
        RL_KIND_CONFIG = 100,
        RL_KIND_INDEX = 101,
        RL_KIND_SEAL = 102,
        RL_KIND_VOLUME = 201,
        RL_KIND_SAVE = 202,
        RL_KIND_INDEX_PAGE_MAP = 301,
        RL_KIND_VOLUME_INDEX = 302,
        RL_KIND_OPEN_CHAPTER = 303,
};

/* Some region types are historical and are no longer used. */
enum region_type {
        RH_TYPE_FREE = 0, /* unused */
        RH_TYPE_SUPER = 1,
        RH_TYPE_SAVE = 2,
        RH_TYPE_CHECKPOINT = 3, /* unused */
        RH_TYPE_UNSAVED = 4,
};

#define RL_SOLE_INSTANCE 65535

/*
 * Super block version 2 is the first released version.
 *
 * Super block version 3 is the normal version used from RHEL 8.2 onwards.
 *
 * Super block versions 4 through 6 were incremental development versions and
 * are not supported.
 *
 * Super block version 7 is used for volumes which have been reduced in size by one chapter in
 * order to make room to prepend LVM metadata to a volume originally created without lvm. This
 * allows the index to retain most its deduplication records.
 */
#define SUPER_VERSION_MINIMUM 3
#define SUPER_VERSION_CURRENT 3
#define SUPER_VERSION_MAXIMUM 7

static const u8 LAYOUT_MAGIC[] = "*ALBIREO*SINGLE*FILE*LAYOUT*001*";
static const u64 REGION_MAGIC = 0x416c6252676e3031; /* 'AlbRgn01' */

#define MAGIC_SIZE (sizeof(LAYOUT_MAGIC) - 1)

struct region_header {
        u64 magic;
        u64 region_blocks;
        u16 type;
        /* Currently always version 1 */
        u16 version;
        u16 region_count;
        u16 payload;
};

struct layout_region {
        u64 start_block;
        u64 block_count;
        u32 __unused;
        u16 kind;
        u16 instance;
};

struct region_table {
        size_t encoded_size;
        struct region_header header;
        struct layout_region regions[];
};

struct index_save_data {
        u64 timestamp;
        u64 nonce;
        /* Currently always version 1 */
        u32 version;
        u32 unused__;
};

struct index_state_version {
        s32 signature;
        s32 version_id;
};

static const struct index_state_version INDEX_STATE_VERSION_301 = {
        .signature  = -1,
        .version_id = 301,
};

struct index_state_data301 {
        struct index_state_version version;
        u64 newest_chapter;
        u64 oldest_chapter;
        u64 last_save;
        u32 unused;
        u32 padding;
};

struct index_save_layout {
        unsigned int zone_count;
        struct layout_region index_save;
        struct layout_region header;
        struct layout_region index_page_map;
        struct layout_region free_space;
        struct layout_region volume_index_zones[MAX_ZONES];
        struct layout_region open_chapter;
        struct index_save_data save_data;
        struct index_state_data301 state_data;
};

struct sub_index_layout {
        u64 nonce;
        struct layout_region sub_index;
        struct layout_region volume;
        struct index_save_layout *saves;
};

struct super_block_data {
        u8 magic_label[MAGIC_SIZE];
        u8 nonce_info[NONCE_INFO_SIZE];
        u64 nonce;
        u32 version;
        u32 block_size;
        u16 index_count;
        u16 max_saves;
        /* Padding reflects a blank field on permanent storage */
        u8 padding[4];
        u64 open_chapter_blocks;
        u64 page_map_blocks;
        u64 volume_offset;
        u64 start_offset;
};

struct index_layout {
        struct io_factory *factory;
        size_t factory_size;
        off_t offset;
        struct super_block_data super;
        struct layout_region header;
        struct layout_region config;
        struct sub_index_layout index;
        struct layout_region seal;
        u64 total_blocks;
};

struct save_layout_sizes {
        unsigned int save_count;
        size_t block_size;
        u64 volume_blocks;
        u64 volume_index_blocks;
        u64 page_map_blocks;
        u64 open_chapter_blocks;
        u64 save_blocks;
        u64 sub_index_blocks;
        u64 total_blocks;
        size_t total_size;
};

static inline bool is_converted_super_block(struct super_block_data *super)
{
        return super->version == 7;
}

static int __must_check compute_sizes(const struct uds_configuration *config,
                                      struct save_layout_sizes *sls)
{
        int result;
        struct index_geometry *geometry = config->geometry;

        memset(sls, 0, sizeof(*sls));
        sls->save_count = MAX_SAVES;
        sls->block_size = UDS_BLOCK_SIZE;
        sls->volume_blocks = geometry->bytes_per_volume / sls->block_size;

        result = uds_compute_volume_index_save_blocks(config, sls->block_size,
                                                      &sls->volume_index_blocks);
        if (result != UDS_SUCCESS)
                return vdo_log_error_strerror(result, "cannot compute index save size");

        sls->page_map_blocks =
                DIV_ROUND_UP(uds_compute_index_page_map_save_size(geometry),
                             sls->block_size);
        sls->open_chapter_blocks =
                DIV_ROUND_UP(uds_compute_saved_open_chapter_size(geometry),
                             sls->block_size);
        sls->save_blocks =
                1 + (sls->volume_index_blocks + sls->page_map_blocks + sls->open_chapter_blocks);
        sls->sub_index_blocks = sls->volume_blocks + (sls->save_count * sls->save_blocks);
        sls->total_blocks = 3 + sls->sub_index_blocks;
        sls->total_size = sls->total_blocks * sls->block_size;

        return UDS_SUCCESS;
}

int uds_compute_index_size(const struct uds_parameters *parameters, u64 *index_size)
{
        int result;
        struct uds_configuration *index_config;
        struct save_layout_sizes sizes;

        if (index_size == NULL) {
                vdo_log_error("Missing output size pointer");
                return -EINVAL;
        }

        result = uds_make_configuration(parameters, &index_config);
        if (result != UDS_SUCCESS) {
                vdo_log_error_strerror(result, "cannot compute index size");
                return result;
        }

        result = compute_sizes(index_config, &sizes);
        uds_free_configuration(index_config);
        if (result != UDS_SUCCESS)
                return result;

        *index_size = sizes.total_size;
        return UDS_SUCCESS;
}

/* Create unique data using the current time and a pseudorandom number. */
static void create_unique_nonce_data(u8 *buffer)
{
        ktime_t now = current_time_ns(CLOCK_REALTIME);
        u32 rand;
        size_t offset = 0;

        rand = get_random_u32();
        memcpy(buffer + offset, &now, sizeof(now));
        offset += sizeof(now);
        memcpy(buffer + offset, &rand, sizeof(rand));
        offset += sizeof(rand);
        while (offset < NONCE_INFO_SIZE) {
                size_t len = min(NONCE_INFO_SIZE - offset, offset);

                memcpy(buffer + offset, buffer, len);
                offset += len;
        }
}

static u64 hash_stuff(u64 start, const void *data, size_t len)
{
        u32 seed = start ^ (start >> 27);
        u8 hash_buffer[16];

        murmurhash3_128(data, len, seed, hash_buffer);
        return get_unaligned_le64(hash_buffer + 4);
}

/* Generate a primary nonce from the provided data. */
static u64 generate_primary_nonce(const void *data, size_t len)
{
        return hash_stuff(0xa1b1e0fc, data, len);
}

/*
 * Deterministically generate a secondary nonce from an existing nonce and some arbitrary data by
 * hashing the original nonce and the data to produce a new nonce.
 */
static u64 generate_secondary_nonce(u64 nonce, const void *data, size_t len)
{
        return hash_stuff(nonce + 1, data, len);
}

static int __must_check open_layout_reader(struct index_layout *layout,
                                           struct layout_region *lr, off_t offset,
                                           struct buffered_reader **reader_ptr)
{
        return uds_make_buffered_reader(layout->factory, lr->start_block + offset,
                                        lr->block_count, reader_ptr);
}

static int open_region_reader(struct index_layout *layout, struct layout_region *region,
                              struct buffered_reader **reader_ptr)
{
        return open_layout_reader(layout, region, -layout->super.start_offset,
                                  reader_ptr);
}

static int __must_check open_layout_writer(struct index_layout *layout,
                                           struct layout_region *lr, off_t offset,
                                           struct buffered_writer **writer_ptr)
{
        return uds_make_buffered_writer(layout->factory, lr->start_block + offset,
                                        lr->block_count, writer_ptr);
}

static int open_region_writer(struct index_layout *layout, struct layout_region *region,
                              struct buffered_writer **writer_ptr)
{
        return open_layout_writer(layout, region, -layout->super.start_offset,
                                  writer_ptr);
}

static void generate_super_block_data(struct save_layout_sizes *sls,
                                      struct super_block_data *super)
{
        memset(super, 0, sizeof(*super));
        memcpy(super->magic_label, LAYOUT_MAGIC, MAGIC_SIZE);
        create_unique_nonce_data(super->nonce_info);

        super->nonce = generate_primary_nonce(super->nonce_info,
                                              sizeof(super->nonce_info));
        super->version = SUPER_VERSION_CURRENT;
        super->block_size = sls->block_size;
        super->index_count = 1;
        super->max_saves = sls->save_count;
        super->open_chapter_blocks = sls->open_chapter_blocks;
        super->page_map_blocks = sls->page_map_blocks;
        super->volume_offset = 0;
        super->start_offset = 0;
}

static void define_sub_index_nonce(struct index_layout *layout)
{
        struct sub_index_nonce_data {
                u64 offset;
                u16 index_id;
        };
        struct sub_index_layout *sil = &layout->index;
        u64 primary_nonce = layout->super.nonce;
        u8 buffer[sizeof(struct sub_index_nonce_data)] = { 0 };
        size_t offset = 0;

        encode_u64_le(buffer, &offset, sil->sub_index.start_block);
        encode_u16_le(buffer, &offset, 0);
        sil->nonce = generate_secondary_nonce(primary_nonce, buffer, sizeof(buffer));
        if (sil->nonce == 0) {
                sil->nonce = generate_secondary_nonce(~primary_nonce + 1, buffer,
                                                      sizeof(buffer));
        }
}

static void setup_sub_index(struct index_layout *layout, u64 start_block,
                            struct save_layout_sizes *sls)
{
        struct sub_index_layout *sil = &layout->index;
        u64 next_block = start_block;
        unsigned int i;

        sil->sub_index = (struct layout_region) {
                .start_block = start_block,
                .block_count = sls->sub_index_blocks,
                .kind = RL_KIND_INDEX,
                .instance = 0,
        };

        sil->volume = (struct layout_region) {
                .start_block = next_block,
                .block_count = sls->volume_blocks,
                .kind = RL_KIND_VOLUME,
                .instance = RL_SOLE_INSTANCE,
        };

        next_block += sls->volume_blocks;

        for (i = 0; i < sls->save_count; i++) {
                sil->saves[i].index_save = (struct layout_region) {
                        .start_block = next_block,
                        .block_count = sls->save_blocks,
                        .kind = RL_KIND_SAVE,
                        .instance = i,
                };

                next_block += sls->save_blocks;
        }

        define_sub_index_nonce(layout);
}

static void initialize_layout(struct index_layout *layout, struct save_layout_sizes *sls)
{
        u64 next_block = layout->offset / sls->block_size;

        layout->total_blocks = sls->total_blocks;
        generate_super_block_data(sls, &layout->super);
        layout->header = (struct layout_region) {
                .start_block = next_block++,
                .block_count = 1,
                .kind = RL_KIND_HEADER,
                .instance = RL_SOLE_INSTANCE,
        };

        layout->config = (struct layout_region) {
                .start_block = next_block++,
                .block_count = 1,
                .kind = RL_KIND_CONFIG,
                .instance = RL_SOLE_INSTANCE,
        };

        setup_sub_index(layout, next_block, sls);
        next_block += sls->sub_index_blocks;

        layout->seal = (struct layout_region) {
                .start_block = next_block,
                .block_count = 1,
                .kind = RL_KIND_SEAL,
                .instance = RL_SOLE_INSTANCE,
        };
}

static int __must_check make_index_save_region_table(struct index_save_layout *isl,
                                                     struct region_table **table_ptr)
{
        int result;
        unsigned int z;
        struct region_table *table;
        struct layout_region *lr;
        u16 region_count;
        size_t payload;
        size_t type;

        if (isl->zone_count > 0) {
                /*
                 * Normal save regions: header, page map, volume index zones,
                 * open chapter, and possibly free space.
                 */
                region_count = 3 + isl->zone_count;
                if (isl->free_space.block_count > 0)
                        region_count++;

                payload = sizeof(isl->save_data) + sizeof(isl->state_data);
                type = RH_TYPE_SAVE;
        } else {
                /* Empty save regions: header, page map, free space. */
                region_count = 3;
                payload = sizeof(isl->save_data);
                type = RH_TYPE_UNSAVED;
        }

        result = vdo_allocate_extended(region_count, regions,
                                       "layout region table for ISL", &table);
        if (result != VDO_SUCCESS)
                return result;

        lr = &table->regions[0];
        *lr++ = isl->header;
        *lr++ = isl->index_page_map;
        for (z = 0; z < isl->zone_count; z++)
                *lr++ = isl->volume_index_zones[z];

        if (isl->zone_count > 0)
                *lr++ = isl->open_chapter;

        if (isl->free_space.block_count > 0)
                *lr++ = isl->free_space;

        table->header = (struct region_header) {
                .magic = REGION_MAGIC,
                .region_blocks = isl->index_save.block_count,
                .type = type,
                .version = 1,
                .region_count = region_count,
                .payload = payload,
        };

        table->encoded_size = (sizeof(struct region_header) + payload +
                               region_count * sizeof(struct layout_region));
        *table_ptr = table;
        return UDS_SUCCESS;
}

static void encode_region_table(u8 *buffer, size_t *offset, struct region_table *table)
{
        unsigned int i;

        encode_u64_le(buffer, offset, REGION_MAGIC);
        encode_u64_le(buffer, offset, table->header.region_blocks);
        encode_u16_le(buffer, offset, table->header.type);
        encode_u16_le(buffer, offset, table->header.version);
        encode_u16_le(buffer, offset, table->header.region_count);
        encode_u16_le(buffer, offset, table->header.payload);

        for (i = 0; i < table->header.region_count; i++) {
                encode_u64_le(buffer, offset, table->regions[i].start_block);
                encode_u64_le(buffer, offset, table->regions[i].block_count);
                encode_u32_le(buffer, offset, 0);
                encode_u16_le(buffer, offset, table->regions[i].kind);
                encode_u16_le(buffer, offset, table->regions[i].instance);
        }
}

static int __must_check write_index_save_header(struct index_save_layout *isl,
                                                struct region_table *table,
                                                struct buffered_writer *writer)
{
        int result;
        u8 *buffer;
        size_t offset = 0;

        result = vdo_allocate(table->encoded_size, "index save data", &buffer);
        if (result != VDO_SUCCESS)
                return result;

        encode_region_table(buffer, &offset, table);
        encode_u64_le(buffer, &offset, isl->save_data.timestamp);
        encode_u64_le(buffer, &offset, isl->save_data.nonce);
        encode_u32_le(buffer, &offset, isl->save_data.version);
        encode_u32_le(buffer, &offset, 0);
        if (isl->zone_count > 0) {
                encode_u32_le(buffer, &offset, INDEX_STATE_VERSION_301.signature);
                encode_u32_le(buffer, &offset, INDEX_STATE_VERSION_301.version_id);
                encode_u64_le(buffer, &offset, isl->state_data.newest_chapter);
                encode_u64_le(buffer, &offset, isl->state_data.oldest_chapter);
                encode_u64_le(buffer, &offset, isl->state_data.last_save);
                encode_u64_le(buffer, &offset, 0);
        }

        result = uds_write_to_buffered_writer(writer, buffer, offset);
        vdo_free(buffer);
        if (result != UDS_SUCCESS)
                return result;

        return uds_flush_buffered_writer(writer);
}

static int write_index_save_layout(struct index_layout *layout,
                                   struct index_save_layout *isl)
{
        int result;
        struct region_table *table;
        struct buffered_writer *writer;

        result = make_index_save_region_table(isl, &table);
        if (result != UDS_SUCCESS)
                return result;

        result = open_region_writer(layout, &isl->header, &writer);
        if (result != UDS_SUCCESS) {
                vdo_free(table);
                return result;
        }

        result = write_index_save_header(isl, table, writer);
        vdo_free(table);
        uds_free_buffered_writer(writer);

        return result;
}

static void reset_index_save_layout(struct index_save_layout *isl, u64 page_map_blocks)
{
        u64 free_blocks;
        u64 next_block = isl->index_save.start_block;

        isl->zone_count = 0;
        memset(&isl->save_data, 0, sizeof(isl->save_data));

        isl->header = (struct layout_region) {
                .start_block = next_block++,
                .block_count = 1,
                .kind = RL_KIND_HEADER,
                .instance = RL_SOLE_INSTANCE,
        };

        isl->index_page_map = (struct layout_region) {
                .start_block = next_block,
                .block_count = page_map_blocks,
                .kind = RL_KIND_INDEX_PAGE_MAP,
                .instance = RL_SOLE_INSTANCE,
        };

        next_block += page_map_blocks;

        free_blocks = isl->index_save.block_count - page_map_blocks - 1;
        isl->free_space = (struct layout_region) {
                .start_block = next_block,
                .block_count = free_blocks,
                .kind = RL_KIND_EMPTY,
                .instance = RL_SOLE_INSTANCE,
        };
}

static int __must_check invalidate_old_save(struct index_layout *layout,
                                            struct index_save_layout *isl)
{
        reset_index_save_layout(isl, layout->super.page_map_blocks);
        return write_index_save_layout(layout, isl);
}

static int discard_index_state_data(struct index_layout *layout)
{
        int result;
        int saved_result = UDS_SUCCESS;
        unsigned int i;

        for (i = 0; i < layout->super.max_saves; i++) {
                result = invalidate_old_save(layout, &layout->index.saves[i]);
                if (result != UDS_SUCCESS)
                        saved_result = result;
        }

        if (saved_result != UDS_SUCCESS) {
                return vdo_log_error_strerror(result,
                                              "%s: cannot destroy all index saves",
                                              __func__);
        }

        return UDS_SUCCESS;
}

static int __must_check make_layout_region_table(struct index_layout *layout,
                                                 struct region_table **table_ptr)
{
        int result;
        unsigned int i;
        /* Regions: header, config, index, volume, saves, seal */
        u16 region_count = 5 + layout->super.max_saves;
        u16 payload;
        struct region_table *table;
        struct layout_region *lr;

        result = vdo_allocate_extended(region_count, regions,
                                       "layout region table", &table);
        if (result != VDO_SUCCESS)
                return result;

        lr = &table->regions[0];
        *lr++ = layout->header;
        *lr++ = layout->config;
        *lr++ = layout->index.sub_index;
        *lr++ = layout->index.volume;

        for (i = 0; i < layout->super.max_saves; i++)
                *lr++ = layout->index.saves[i].index_save;

        *lr++ = layout->seal;

        if (is_converted_super_block(&layout->super)) {
                payload = sizeof(struct super_block_data);
        } else {
                payload = (sizeof(struct super_block_data) -
                           sizeof(layout->super.volume_offset) -
                           sizeof(layout->super.start_offset));
        }

        table->header = (struct region_header) {
                .magic = REGION_MAGIC,
                .region_blocks = layout->total_blocks,
                .type = RH_TYPE_SUPER,
                .version = 1,
                .region_count = region_count,
                .payload = payload,
        };

        table->encoded_size = (sizeof(struct region_header) + payload +
                               region_count * sizeof(struct layout_region));
        *table_ptr = table;
        return UDS_SUCCESS;
}

static int __must_check write_layout_header(struct index_layout *layout,
                                            struct region_table *table,
                                            struct buffered_writer *writer)
{
        int result;
        u8 *buffer;
        size_t offset = 0;

        result = vdo_allocate(table->encoded_size, "layout data", &buffer);
        if (result != VDO_SUCCESS)
                return result;

        encode_region_table(buffer, &offset, table);
        memcpy(buffer + offset, &layout->super.magic_label, MAGIC_SIZE);
        offset += MAGIC_SIZE;
        memcpy(buffer + offset, &layout->super.nonce_info, NONCE_INFO_SIZE);
        offset += NONCE_INFO_SIZE;
        encode_u64_le(buffer, &offset, layout->super.nonce);
        encode_u32_le(buffer, &offset, layout->super.version);
        encode_u32_le(buffer, &offset, layout->super.block_size);
        encode_u16_le(buffer, &offset, layout->super.index_count);
        encode_u16_le(buffer, &offset, layout->super.max_saves);
        encode_u32_le(buffer, &offset, 0);
        encode_u64_le(buffer, &offset, layout->super.open_chapter_blocks);
        encode_u64_le(buffer, &offset, layout->super.page_map_blocks);

        if (is_converted_super_block(&layout->super)) {
                encode_u64_le(buffer, &offset, layout->super.volume_offset);
                encode_u64_le(buffer, &offset, layout->super.start_offset);
        }

        result = uds_write_to_buffered_writer(writer, buffer, offset);
        vdo_free(buffer);
        if (result != UDS_SUCCESS)
                return result;

        return uds_flush_buffered_writer(writer);
}

static int __must_check write_uds_index_config(struct index_layout *layout,
                                               struct uds_configuration *config,
                                               off_t offset)
{
        int result;
        struct buffered_writer *writer = NULL;

        result = open_layout_writer(layout, &layout->config, offset, &writer);
        if (result != UDS_SUCCESS)
                return vdo_log_error_strerror(result, "failed to open config region");

        result = uds_write_config_contents(writer, config, layout->super.version);
        if (result != UDS_SUCCESS) {
                uds_free_buffered_writer(writer);
                return vdo_log_error_strerror(result, "failed to write config region");
        }

        result = uds_flush_buffered_writer(writer);
        if (result != UDS_SUCCESS) {
                uds_free_buffered_writer(writer);
                return vdo_log_error_strerror(result, "cannot flush config writer");
        }

        uds_free_buffered_writer(writer);
        return UDS_SUCCESS;
}

static int __must_check save_layout(struct index_layout *layout, off_t offset)
{
        int result;
        struct buffered_writer *writer = NULL;
        struct region_table *table;

        result = make_layout_region_table(layout, &table);
        if (result != UDS_SUCCESS)
                return result;

        result = open_layout_writer(layout, &layout->header, offset, &writer);
        if (result != UDS_SUCCESS) {
                vdo_free(table);
                return result;
        }

        result = write_layout_header(layout, table, writer);
        vdo_free(table);
        uds_free_buffered_writer(writer);

        return result;
}

static int create_index_layout(struct index_layout *layout, struct uds_configuration *config)
{
        int result;
        struct save_layout_sizes sizes;

        result = compute_sizes(config, &sizes);
        if (result != UDS_SUCCESS)
                return result;

        result = vdo_allocate(sizes.save_count, __func__, &layout->index.saves);
        if (result != VDO_SUCCESS)
                return result;

        initialize_layout(layout, &sizes);

        result = discard_index_state_data(layout);
        if (result != UDS_SUCCESS)
                return result;

        result = write_uds_index_config(layout, config, 0);
        if (result != UDS_SUCCESS)
                return result;

        return save_layout(layout, 0);
}

static u64 generate_index_save_nonce(u64 volume_nonce, struct index_save_layout *isl)
{
        struct save_nonce_data {
                struct index_save_data data;
                u64 offset;
        } nonce_data;
        u8 buffer[sizeof(nonce_data)];
        size_t offset = 0;

        encode_u64_le(buffer, &offset, isl->save_data.timestamp);
        encode_u64_le(buffer, &offset, 0);
        encode_u32_le(buffer, &offset, isl->save_data.version);
        encode_u32_le(buffer, &offset, 0U);
        encode_u64_le(buffer, &offset, isl->index_save.start_block);
        VDO_ASSERT_LOG_ONLY(offset == sizeof(nonce_data),
                            "%zu bytes encoded of %zu expected",
                            offset, sizeof(nonce_data));
        return generate_secondary_nonce(volume_nonce, buffer, sizeof(buffer));
}

static u64 validate_index_save_layout(struct index_save_layout *isl, u64 volume_nonce)
{
        if ((isl->zone_count == 0) || (isl->save_data.timestamp == 0))
                return 0;

        if (isl->save_data.nonce != generate_index_save_nonce(volume_nonce, isl))
                return 0;

        return isl->save_data.timestamp;
}

static int find_latest_uds_index_save_slot(struct index_layout *layout,
                                           struct index_save_layout **isl_ptr)
{
        struct index_save_layout *latest = NULL;
        struct index_save_layout *isl;
        unsigned int i;
        u64 save_time = 0;
        u64 latest_time = 0;

        for (i = 0; i < layout->super.max_saves; i++) {
                isl = &layout->index.saves[i];
                save_time = validate_index_save_layout(isl, layout->index.nonce);
                if (save_time > latest_time) {
                        latest = isl;
                        latest_time = save_time;
                }
        }

        if (latest == NULL) {
                vdo_log_error("No valid index save found");
                return UDS_INDEX_NOT_SAVED_CLEANLY;
        }

        *isl_ptr = latest;
        return UDS_SUCCESS;
}

int uds_discard_open_chapter(struct index_layout *layout)
{
        int result;
        struct index_save_layout *isl;
        struct buffered_writer *writer;

        result = find_latest_uds_index_save_slot(layout, &isl);
        if (result != UDS_SUCCESS)
                return result;

        result = open_region_writer(layout, &isl->open_chapter, &writer);
        if (result != UDS_SUCCESS)
                return result;

        result = uds_write_to_buffered_writer(writer, NULL, UDS_BLOCK_SIZE);
        if (result != UDS_SUCCESS) {
                uds_free_buffered_writer(writer);
                return result;
        }

        result = uds_flush_buffered_writer(writer);
        uds_free_buffered_writer(writer);
        return result;
}

int uds_load_index_state(struct index_layout *layout, struct uds_index *index)
{
        int result;
        unsigned int zone;
        struct index_save_layout *isl;
        struct buffered_reader *readers[MAX_ZONES];

        result = find_latest_uds_index_save_slot(layout, &isl);
        if (result != UDS_SUCCESS)
                return result;

        index->newest_virtual_chapter = isl->state_data.newest_chapter;
        index->oldest_virtual_chapter = isl->state_data.oldest_chapter;
        index->last_save = isl->state_data.last_save;

        result = open_region_reader(layout, &isl->open_chapter, &readers[0]);
        if (result != UDS_SUCCESS)
                return result;

        result = uds_load_open_chapter(index, readers[0]);
        uds_free_buffered_reader(readers[0]);
        if (result != UDS_SUCCESS)
                return result;

        for (zone = 0; zone < isl->zone_count; zone++) {
                result = open_region_reader(layout, &isl->volume_index_zones[zone],
                                            &readers[zone]);
                if (result != UDS_SUCCESS) {
                        for (; zone > 0; zone--)
                                uds_free_buffered_reader(readers[zone - 1]);

                        return result;
                }
        }

        result = uds_load_volume_index(index->volume_index, readers, isl->zone_count);
        for (zone = 0; zone < isl->zone_count; zone++)
                uds_free_buffered_reader(readers[zone]);
        if (result != UDS_SUCCESS)
                return result;

        result = open_region_reader(layout, &isl->index_page_map, &readers[0]);
        if (result != UDS_SUCCESS)
                return result;

        result = uds_read_index_page_map(index->volume->index_page_map, readers[0]);
        uds_free_buffered_reader(readers[0]);

        return result;
}

static struct index_save_layout *select_oldest_index_save_layout(struct index_layout *layout)
{
        struct index_save_layout *oldest = NULL;
        struct index_save_layout *isl;
        unsigned int i;
        u64 save_time = 0;
        u64 oldest_time = 0;

        for (i = 0; i < layout->super.max_saves; i++) {
                isl = &layout->index.saves[i];
                save_time = validate_index_save_layout(isl, layout->index.nonce);
                if (oldest == NULL || save_time < oldest_time) {
                        oldest = isl;
                        oldest_time = save_time;
                }
        }

        return oldest;
}

static void instantiate_index_save_layout(struct index_save_layout *isl,
                                          struct super_block_data *super,
                                          u64 volume_nonce, unsigned int zone_count)
{
        unsigned int z;
        u64 next_block;
        u64 free_blocks;
        u64 volume_index_blocks;

        isl->zone_count = zone_count;
        memset(&isl->save_data, 0, sizeof(isl->save_data));
        isl->save_data.timestamp = ktime_to_ms(current_time_ns(CLOCK_REALTIME));
        isl->save_data.version = 1;
        isl->save_data.nonce = generate_index_save_nonce(volume_nonce, isl);

        next_block = isl->index_save.start_block;
        isl->header = (struct layout_region) {
                .start_block = next_block++,
                .block_count = 1,
                .kind = RL_KIND_HEADER,
                .instance = RL_SOLE_INSTANCE,
        };

        isl->index_page_map = (struct layout_region) {
                .start_block = next_block,
                .block_count = super->page_map_blocks,
                .kind = RL_KIND_INDEX_PAGE_MAP,
                .instance = RL_SOLE_INSTANCE,
        };
        next_block += super->page_map_blocks;

        free_blocks = (isl->index_save.block_count - 1 -
                       super->page_map_blocks -
                       super->open_chapter_blocks);
        volume_index_blocks = free_blocks / isl->zone_count;
        for (z = 0; z < isl->zone_count; z++) {
                isl->volume_index_zones[z] = (struct layout_region) {
                        .start_block = next_block,
                        .block_count = volume_index_blocks,
                        .kind = RL_KIND_VOLUME_INDEX,
                        .instance = z,
                };

                next_block += volume_index_blocks;
                free_blocks -= volume_index_blocks;
        }

        isl->open_chapter = (struct layout_region) {
                .start_block = next_block,
                .block_count = super->open_chapter_blocks,
                .kind = RL_KIND_OPEN_CHAPTER,
                .instance = RL_SOLE_INSTANCE,
        };

        next_block += super->open_chapter_blocks;

        isl->free_space = (struct layout_region) {
                .start_block = next_block,
                .block_count = free_blocks,
                .kind = RL_KIND_EMPTY,
                .instance = RL_SOLE_INSTANCE,
        };
}

static int setup_uds_index_save_slot(struct index_layout *layout,
                                     unsigned int zone_count,
                                     struct index_save_layout **isl_ptr)
{
        int result;
        struct index_save_layout *isl;

        isl = select_oldest_index_save_layout(layout);
        result = invalidate_old_save(layout, isl);
        if (result != UDS_SUCCESS)
                return result;

        instantiate_index_save_layout(isl, &layout->super, layout->index.nonce,
                                      zone_count);

        *isl_ptr = isl;
        return UDS_SUCCESS;
}

static void cancel_uds_index_save(struct index_save_layout *isl)
{
        memset(&isl->save_data, 0, sizeof(isl->save_data));
        memset(&isl->state_data, 0, sizeof(isl->state_data));
        isl->zone_count = 0;
}

int uds_save_index_state(struct index_layout *layout, struct uds_index *index)
{
        int result;
        unsigned int zone;
        struct index_save_layout *isl;
        struct buffered_writer *writers[MAX_ZONES];

        result = setup_uds_index_save_slot(layout, index->zone_count, &isl);
        if (result != UDS_SUCCESS)
                return result;

        isl->state_data = (struct index_state_data301) {
                .newest_chapter = index->newest_virtual_chapter,
                .oldest_chapter = index->oldest_virtual_chapter,
                .last_save = index->last_save,
        };

        result = open_region_writer(layout, &isl->open_chapter, &writers[0]);
        if (result != UDS_SUCCESS) {
                cancel_uds_index_save(isl);
                return result;
        }

        result = uds_save_open_chapter(index, writers[0]);
        uds_free_buffered_writer(writers[0]);
        if (result != UDS_SUCCESS) {
                cancel_uds_index_save(isl);
                return result;
        }

        for (zone = 0; zone < index->zone_count; zone++) {
                result = open_region_writer(layout, &isl->volume_index_zones[zone],
                                            &writers[zone]);
                if (result != UDS_SUCCESS) {
                        for (; zone > 0; zone--)
                                uds_free_buffered_writer(writers[zone - 1]);

                        cancel_uds_index_save(isl);
                        return result;
                }
        }

        result = uds_save_volume_index(index->volume_index, writers, index->zone_count);
        for (zone = 0; zone < index->zone_count; zone++)
                uds_free_buffered_writer(writers[zone]);
        if (result != UDS_SUCCESS) {
                cancel_uds_index_save(isl);
                return result;
        }

        result = open_region_writer(layout, &isl->index_page_map, &writers[0]);
        if (result != UDS_SUCCESS) {
                cancel_uds_index_save(isl);
                return result;
        }

        result = uds_write_index_page_map(index->volume->index_page_map, writers[0]);
        uds_free_buffered_writer(writers[0]);
        if (result != UDS_SUCCESS) {
                cancel_uds_index_save(isl);
                return result;
        }

        return write_index_save_layout(layout, isl);
}

static int __must_check load_region_table(struct buffered_reader *reader,
                                          struct region_table **table_ptr)
{
        int result;
        unsigned int i;
        struct region_header header;
        struct region_table *table;
        u8 buffer[sizeof(struct region_header)];
        size_t offset = 0;

        result = uds_read_from_buffered_reader(reader, buffer, sizeof(buffer));
        if (result != UDS_SUCCESS)
                return vdo_log_error_strerror(result, "cannot read region table header");

        decode_u64_le(buffer, &offset, &header.magic);
        decode_u64_le(buffer, &offset, &header.region_blocks);
        decode_u16_le(buffer, &offset, &header.type);
        decode_u16_le(buffer, &offset, &header.version);
        decode_u16_le(buffer, &offset, &header.region_count);
        decode_u16_le(buffer, &offset, &header.payload);

        if (header.magic != REGION_MAGIC)
                return UDS_NO_INDEX;

        if (header.version != 1) {
                return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
                                              "unknown region table version %hu",
                                              header.version);
        }

        result = vdo_allocate_extended(header.region_count, regions,
                                       "single file layout region table", &table);
        if (result != VDO_SUCCESS)
                return result;

        table->header = header;
        for (i = 0; i < header.region_count; i++) {
                u8 region_buffer[sizeof(struct layout_region)];

                offset = 0;
                result = uds_read_from_buffered_reader(reader, region_buffer,
                                                       sizeof(region_buffer));
                if (result != UDS_SUCCESS) {
                        vdo_free(table);
                        return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                                      "cannot read region table layouts");
                }

                decode_u64_le(region_buffer, &offset, &table->regions[i].start_block);
                decode_u64_le(region_buffer, &offset, &table->regions[i].block_count);
                offset += sizeof(u32);
                decode_u16_le(region_buffer, &offset, &table->regions[i].kind);
                decode_u16_le(region_buffer, &offset, &table->regions[i].instance);
        }

        *table_ptr = table;
        return UDS_SUCCESS;
}

static int __must_check read_super_block_data(struct buffered_reader *reader,
                                              struct index_layout *layout,
                                              size_t saved_size)
{
        int result;
        struct super_block_data *super = &layout->super;
        u8 *buffer;
        size_t offset = 0;

        result = vdo_allocate(saved_size, "super block data", &buffer);
        if (result != VDO_SUCCESS)
                return result;

        result = uds_read_from_buffered_reader(reader, buffer, saved_size);
        if (result != UDS_SUCCESS) {
                vdo_free(buffer);
                return vdo_log_error_strerror(result, "cannot read region table header");
        }

        memcpy(&super->magic_label, buffer, MAGIC_SIZE);
        offset += MAGIC_SIZE;
        memcpy(&super->nonce_info, buffer + offset, NONCE_INFO_SIZE);
        offset += NONCE_INFO_SIZE;
        decode_u64_le(buffer, &offset, &super->nonce);
        decode_u32_le(buffer, &offset, &super->version);
        decode_u32_le(buffer, &offset, &super->block_size);
        decode_u16_le(buffer, &offset, &super->index_count);
        decode_u16_le(buffer, &offset, &super->max_saves);
        offset += sizeof(u32);
        decode_u64_le(buffer, &offset, &super->open_chapter_blocks);
        decode_u64_le(buffer, &offset, &super->page_map_blocks);

        if (is_converted_super_block(super)) {
                decode_u64_le(buffer, &offset, &super->volume_offset);
                decode_u64_le(buffer, &offset, &super->start_offset);
        } else {
                super->volume_offset = 0;
                super->start_offset = 0;
        }

        vdo_free(buffer);

        if (memcmp(super->magic_label, LAYOUT_MAGIC, MAGIC_SIZE) != 0)
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "unknown superblock magic label");

        if ((super->version < SUPER_VERSION_MINIMUM) ||
            (super->version == 4) || (super->version == 5) || (super->version == 6) ||
            (super->version > SUPER_VERSION_MAXIMUM)) {
                return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
                                              "unknown superblock version number %u",
                                              super->version);
        }

        if (super->volume_offset < super->start_offset) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "inconsistent offsets (start %llu, volume %llu)",
                                              (unsigned long long) super->start_offset,
                                              (unsigned long long) super->volume_offset);
        }

        /* Sub-indexes are no longer used but the layout retains this field. */
        if (super->index_count != 1) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "invalid subindex count %u",
                                              super->index_count);
        }

        if (generate_primary_nonce(super->nonce_info, sizeof(super->nonce_info)) != super->nonce) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "inconsistent superblock nonce");
        }

        return UDS_SUCCESS;
}

static int __must_check verify_region(struct layout_region *lr, u64 start_block,
                                      enum region_kind kind, unsigned int instance)
{
        if (lr->start_block != start_block)
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "incorrect layout region offset");

        if (lr->kind != kind)
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "incorrect layout region kind");

        if (lr->instance != instance) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "incorrect layout region instance");
        }

        return UDS_SUCCESS;
}

static int __must_check verify_sub_index(struct index_layout *layout, u64 start_block,
                                         struct region_table *table)
{
        int result;
        unsigned int i;
        struct sub_index_layout *sil = &layout->index;
        u64 next_block = start_block;

        sil->sub_index = table->regions[2];
        result = verify_region(&sil->sub_index, next_block, RL_KIND_INDEX, 0);
        if (result != UDS_SUCCESS)
                return result;

        define_sub_index_nonce(layout);

        sil->volume = table->regions[3];
        result = verify_region(&sil->volume, next_block, RL_KIND_VOLUME,
                               RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        next_block += sil->volume.block_count + layout->super.volume_offset;

        for (i = 0; i < layout->super.max_saves; i++) {
                sil->saves[i].index_save = table->regions[i + 4];
                result = verify_region(&sil->saves[i].index_save, next_block,
                                       RL_KIND_SAVE, i);
                if (result != UDS_SUCCESS)
                        return result;

                next_block += sil->saves[i].index_save.block_count;
        }

        next_block -= layout->super.volume_offset;
        if (next_block != start_block + sil->sub_index.block_count) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "sub index region does not span all saves");
        }

        return UDS_SUCCESS;
}

static int __must_check reconstitute_layout(struct index_layout *layout,
                                            struct region_table *table, u64 first_block)
{
        int result;
        u64 next_block = first_block;

        result = vdo_allocate(layout->super.max_saves, __func__, &layout->index.saves);
        if (result != VDO_SUCCESS)
                return result;

        layout->total_blocks = table->header.region_blocks;

        layout->header = table->regions[0];
        result = verify_region(&layout->header, next_block++, RL_KIND_HEADER,
                               RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        layout->config = table->regions[1];
        result = verify_region(&layout->config, next_block++, RL_KIND_CONFIG,
                               RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        result = verify_sub_index(layout, next_block, table);
        if (result != UDS_SUCCESS)
                return result;

        next_block += layout->index.sub_index.block_count;

        layout->seal = table->regions[table->header.region_count - 1];
        result = verify_region(&layout->seal, next_block + layout->super.volume_offset,
                               RL_KIND_SEAL, RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        if (++next_block != (first_block + layout->total_blocks)) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "layout table does not span total blocks");
        }

        return UDS_SUCCESS;
}

static int __must_check load_super_block(struct index_layout *layout, size_t block_size,
                                         u64 first_block, struct buffered_reader *reader)
{
        int result;
        struct region_table *table = NULL;
        struct super_block_data *super = &layout->super;

        result = load_region_table(reader, &table);
        if (result != UDS_SUCCESS)
                return result;

        if (table->header.type != RH_TYPE_SUPER) {
                vdo_free(table);
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "not a superblock region table");
        }

        result = read_super_block_data(reader, layout, table->header.payload);
        if (result != UDS_SUCCESS) {
                vdo_free(table);
                return vdo_log_error_strerror(result, "unknown superblock format");
        }

        if (super->block_size != block_size) {
                vdo_free(table);
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "superblock saved block_size %u differs from supplied block_size %zu",
                                              super->block_size, block_size);
        }

        first_block -= (super->volume_offset - super->start_offset);
        result = reconstitute_layout(layout, table, first_block);
        vdo_free(table);
        return result;
}

static int __must_check read_index_save_data(struct buffered_reader *reader,
                                             struct index_save_layout *isl,
                                             size_t saved_size)
{
        int result;
        struct index_state_version file_version;
        u8 buffer[sizeof(struct index_save_data) + sizeof(struct index_state_data301)];
        size_t offset = 0;

        if (saved_size != sizeof(buffer)) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "unexpected index save data size %zu",
                                              saved_size);
        }

        result = uds_read_from_buffered_reader(reader, buffer, sizeof(buffer));
        if (result != UDS_SUCCESS)
                return vdo_log_error_strerror(result, "cannot read index save data");

        decode_u64_le(buffer, &offset, &isl->save_data.timestamp);
        decode_u64_le(buffer, &offset, &isl->save_data.nonce);
        decode_u32_le(buffer, &offset, &isl->save_data.version);
        offset += sizeof(u32);

        if (isl->save_data.version > 1) {
                return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
                                              "unknown index save version number %u",
                                              isl->save_data.version);
        }

        decode_s32_le(buffer, &offset, &file_version.signature);
        decode_s32_le(buffer, &offset, &file_version.version_id);

        if ((file_version.signature != INDEX_STATE_VERSION_301.signature) ||
            (file_version.version_id != INDEX_STATE_VERSION_301.version_id)) {
                return vdo_log_error_strerror(UDS_UNSUPPORTED_VERSION,
                                              "index state version %d,%d is unsupported",
                                              file_version.signature,
                                              file_version.version_id);
        }

        decode_u64_le(buffer, &offset, &isl->state_data.newest_chapter);
        decode_u64_le(buffer, &offset, &isl->state_data.oldest_chapter);
        decode_u64_le(buffer, &offset, &isl->state_data.last_save);
        /* Skip past some historical fields that are now unused */
        offset += sizeof(u32) + sizeof(u32);
        return UDS_SUCCESS;
}

static int __must_check reconstruct_index_save(struct index_save_layout *isl,
                                               struct region_table *table)
{
        int result;
        unsigned int z;
        struct layout_region *last_region;
        u64 next_block = isl->index_save.start_block;
        u64 last_block = next_block + isl->index_save.block_count;

        isl->zone_count = table->header.region_count - 3;
        if (isl->zone_count > MAX_ZONES)
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "invalid zone count");

        last_region = &table->regions[table->header.region_count - 1];
        if (last_region->kind == RL_KIND_EMPTY) {
                isl->free_space = *last_region;
                isl->zone_count--;
        } else {
                isl->free_space = (struct layout_region) {
                        .start_block = last_block,
                        .block_count = 0,
                        .kind = RL_KIND_EMPTY,
                        .instance = RL_SOLE_INSTANCE,
                };
        }

        isl->header = table->regions[0];
        result = verify_region(&isl->header, next_block++, RL_KIND_HEADER,
                               RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        isl->index_page_map = table->regions[1];
        result = verify_region(&isl->index_page_map, next_block, RL_KIND_INDEX_PAGE_MAP,
                               RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        next_block += isl->index_page_map.block_count;

        for (z = 0; z < isl->zone_count; z++) {
                isl->volume_index_zones[z] = table->regions[z + 2];
                result = verify_region(&isl->volume_index_zones[z], next_block,
                                       RL_KIND_VOLUME_INDEX, z);
                if (result != UDS_SUCCESS)
                        return result;

                next_block += isl->volume_index_zones[z].block_count;
        }

        isl->open_chapter = table->regions[isl->zone_count + 2];
        result = verify_region(&isl->open_chapter, next_block, RL_KIND_OPEN_CHAPTER,
                               RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        next_block += isl->open_chapter.block_count;

        result = verify_region(&isl->free_space, next_block, RL_KIND_EMPTY,
                               RL_SOLE_INSTANCE);
        if (result != UDS_SUCCESS)
                return result;

        next_block += isl->free_space.block_count;
        if (next_block != last_block) {
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "index save layout table incomplete");
        }

        return UDS_SUCCESS;
}

static int __must_check load_index_save(struct index_save_layout *isl,
                                        struct buffered_reader *reader,
                                        unsigned int instance)
{
        int result;
        struct region_table *table = NULL;

        result = load_region_table(reader, &table);
        if (result != UDS_SUCCESS) {
                return vdo_log_error_strerror(result, "cannot read index save %u header",
                                              instance);
        }

        if (table->header.region_blocks != isl->index_save.block_count) {
                u64 region_blocks = table->header.region_blocks;

                vdo_free(table);
                return vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                              "unexpected index save %u region block count %llu",
                                              instance,
                                              (unsigned long long) region_blocks);
        }

        if (table->header.type == RH_TYPE_UNSAVED) {
                vdo_free(table);
                reset_index_save_layout(isl, 0);
                return UDS_SUCCESS;
        }


        if (table->header.type != RH_TYPE_SAVE) {
                vdo_log_error_strerror(UDS_CORRUPT_DATA,
                                       "unexpected index save %u header type %u",
                                       instance, table->header.type);
                vdo_free(table);
                return UDS_CORRUPT_DATA;
        }

        result = read_index_save_data(reader, isl, table->header.payload);
        if (result != UDS_SUCCESS) {
                vdo_free(table);
                return vdo_log_error_strerror(result,
                                              "unknown index save %u data format",
                                              instance);
        }

        result = reconstruct_index_save(isl, table);
        vdo_free(table);
        if (result != UDS_SUCCESS) {
                return vdo_log_error_strerror(result, "cannot reconstruct index save %u",
                                              instance);
        }

        return UDS_SUCCESS;
}

static int __must_check load_sub_index_regions(struct index_layout *layout)
{
        int result;
        unsigned int j;
        struct index_save_layout *isl;
        struct buffered_reader *reader;

        for (j = 0; j < layout->super.max_saves; j++) {
                isl = &layout->index.saves[j];
                result = open_region_reader(layout, &isl->index_save, &reader);

                if (result != UDS_SUCCESS) {
                        vdo_log_error_strerror(result,
                                               "cannot get reader for index 0 save %u",
                                               j);
                        return result;
                }

                result = load_index_save(isl, reader, j);
                uds_free_buffered_reader(reader);
                if (result != UDS_SUCCESS) {
                        /* Another save slot might be valid. */
                        reset_index_save_layout(isl, 0);
                        continue;
                }
        }

        return UDS_SUCCESS;
}

static int __must_check verify_uds_index_config(struct index_layout *layout,
                                                struct uds_configuration *config)
{
        int result;
        struct buffered_reader *reader = NULL;
        u64 offset;

        offset = layout->super.volume_offset - layout->super.start_offset;
        result = open_layout_reader(layout, &layout->config, offset, &reader);
        if (result != UDS_SUCCESS)
                return vdo_log_error_strerror(result, "failed to open config reader");

        result = uds_validate_config_contents(reader, config);
        if (result != UDS_SUCCESS) {
                uds_free_buffered_reader(reader);
                return vdo_log_error_strerror(result, "failed to read config region");
        }

        uds_free_buffered_reader(reader);
        return UDS_SUCCESS;
}

static int load_index_layout(struct index_layout *layout, struct uds_configuration *config)
{
        int result;
        struct buffered_reader *reader;

        result = uds_make_buffered_reader(layout->factory,
                                          layout->offset / UDS_BLOCK_SIZE, 1, &reader);
        if (result != UDS_SUCCESS)
                return vdo_log_error_strerror(result, "unable to read superblock");

        result = load_super_block(layout, UDS_BLOCK_SIZE,
                                  layout->offset / UDS_BLOCK_SIZE, reader);
        uds_free_buffered_reader(reader);
        if (result != UDS_SUCCESS)
                return result;

        result = verify_uds_index_config(layout, config);
        if (result != UDS_SUCCESS)
                return result;

        return load_sub_index_regions(layout);
}

static int create_layout_factory(struct index_layout *layout,
                                 const struct uds_configuration *config)
{
        int result;
        size_t writable_size;
        struct io_factory *factory = NULL;

        result = uds_make_io_factory(config->bdev, &factory);
        if (result != UDS_SUCCESS)
                return result;

        writable_size = uds_get_writable_size(factory) & -UDS_BLOCK_SIZE;
        if (writable_size < config->size + config->offset) {
                uds_put_io_factory(factory);
                vdo_log_error("index storage (%zu) is smaller than the requested size %zu",
                              writable_size, config->size + config->offset);
                return -ENOSPC;
        }

        layout->factory = factory;
        layout->factory_size = (config->size > 0) ? config->size : writable_size;
        layout->offset = config->offset;
        return UDS_SUCCESS;
}

int uds_make_index_layout(struct uds_configuration *config, bool new_layout,
                          struct index_layout **layout_ptr)
{
        int result;
        struct index_layout *layout = NULL;
        struct save_layout_sizes sizes;

        result = compute_sizes(config, &sizes);
        if (result != UDS_SUCCESS)
                return result;

        result = vdo_allocate(1, __func__, &layout);
        if (result != VDO_SUCCESS)
                return result;

        result = create_layout_factory(layout, config);
        if (result != UDS_SUCCESS) {
                uds_free_index_layout(layout);
                return result;
        }

        if (layout->factory_size < sizes.total_size) {
                vdo_log_error("index storage (%zu) is smaller than the required size %llu",
                              layout->factory_size,
                              (unsigned long long) sizes.total_size);
                uds_free_index_layout(layout);
                return -ENOSPC;
        }

        if (new_layout)
                result = create_index_layout(layout, config);
        else
                result = load_index_layout(layout, config);
        if (result != UDS_SUCCESS) {
                uds_free_index_layout(layout);
                return result;
        }

        *layout_ptr = layout;
        return UDS_SUCCESS;
}

void uds_free_index_layout(struct index_layout *layout)
{
        if (layout == NULL)
                return;

        vdo_free(layout->index.saves);
        if (layout->factory != NULL)
                uds_put_io_factory(layout->factory);

        vdo_free(layout);
}

int uds_replace_index_layout_storage(struct index_layout *layout,
                                     struct block_device *bdev)
{
        return uds_replace_storage(layout->factory, bdev);
}

/* Obtain a dm_bufio_client for the volume region. */
int uds_open_volume_bufio(struct index_layout *layout, size_t block_size,
                          unsigned int reserved_buffers,
                          struct dm_bufio_client **client_ptr)
{
        off_t offset = (layout->index.volume.start_block +
                        layout->super.volume_offset -
                        layout->super.start_offset);

        return uds_make_bufio(layout->factory, offset, block_size, reserved_buffers,
                              client_ptr);
}

u64 uds_get_volume_nonce(struct index_layout *layout)
{
        return layout->index.nonce;
}