app/storage/block_map.c

/*
 * Copyright (C) 2015-2016 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <assert.h>
#include <inttypes.h>

#include "block_allocator.h"
#include "block_map.h"
#include "block_tree.h"
#include "debug.h"
#include "transaction.h"

static bool print_block_map;

/**
 * block_map_init - Initialize in-memory block map structute
 * @tr:         Transaction object.
 * @block_map:  Block map object.
 * @root:       Block mac of root tree.
 * @block_size: Block size of device.
 */

void block_map_init(const struct transaction* tr,
                    struct block_map* block_map,
                    const struct block_mac* root,
                    size_t block_size) {
    size_t block_num_size = tr->fs->block_num_size;
    size_t block_mac_size = block_num_size + tr->fs->mac_size;
    memset(block_map, 0, sizeof(*block_map));
    block_tree_init(&block_map->tree, block_size, block_num_size,
                    block_mac_size, block_mac_size);
    block_map->tree.copy_on_write = 1;
    block_map->tree.allow_copy_on_write = 1;
    block_map->tree.root = *root;
}

/**
 * block_map_get - Lookup a block
 * @tr:         Transaction object.
 * @block_map:  Block map object.
 * @index:      Index of block to get.
 * @block_mac:  Pointer to return block_mac in.
 *
 * Return: %true if a block_mac exists at @index, %false if not. When returning
 * %true, @block_mac will be filled in. Otherwise, @block_mac is not touched.
 */
bool block_map_get(struct transaction* tr,
                   struct block_map* block_map,
                   data_block_t index,
                   struct block_mac* block_mac) {
    struct block_tree_path path;

    index++; /* 0 is not a valid block tree key */

    block_tree_walk(tr, &block_map->tree, index, false, &path);
    if (block_tree_path_get_key(&path) != index) {
        if (print_block_map) {
            printf("%s: %" PRIu64 " not found (next key %" PRIu64 ")\n",
                   __func__, index, block_tree_path_get_key(&path));
        }
        return false;
    }
    *block_mac = block_tree_path_get_data_block_mac(&path);

    return true;
}

/**
 * block_map_set - Store a block_mac
 * @tr:         Transaction object.
 * @block_map:  Block map object.
 * @index:      Index of block to set.
 * @block_mac:  block_mac to store, or %NULL to remove the block_mac at @index.
 */
void block_map_set(struct transaction* tr,
                   struct block_map* block_map,
                   data_block_t index,
                   const struct block_mac* block_mac) {
    struct block_tree_path path;

    index++; /* 0 is not a valid block tree key */

    if (tr->failed) {
        pr_warn("transaction failed, ignore\n");
        return;
    }

    block_tree_walk(tr, &block_map->tree, index, false, &path);
    if (tr->failed) {
        pr_warn("transaction failed, abort\n");
        return;
    }
    if (block_tree_path_get_key(&path) == index) {
        if (print_block_map) {
            printf("%s: block_map at %" PRIu64
                   ": remove existing entry at %" PRIu64 "\n",
                   __func__, block_mac_to_block(tr, &block_map->tree.root),
                   index);
        }
        block_tree_remove(tr, &block_map->tree, index,
                          block_tree_path_get_data(&path));
        if (tr->failed) {
            pr_warn("transaction failed, abort\n");
            return;
        }
    }
    if (block_mac && block_mac_valid(tr, block_mac)) {
        if (print_block_map) {
            printf("%s: block_map at %" PRIu64 ": [%" PRIu64 "] = %" PRIu64
                   "\n",
                   __func__, block_mac_to_block(tr, &block_map->tree.root),
                   index, block_mac_to_block(tr, block_mac));
        }
        block_tree_insert(tr, &block_map->tree, index,
                          block_mac_to_block(tr, block_mac));
        /* TODO: insert mac */
    }
}

/**
 * block_map_put_dirty - Release a block stored in a block_map, and update mac
 * @tr:         Transaction object.
 * @block_map:  Block map object.
 * @index:      Index of block to update.
 * @data:       block cache entry.
 * @data_ref:   reference to @data.
 */
void block_map_put_dirty(struct transaction* tr,
                         struct block_map* block_map,
                         data_block_t index,
                         void* data,
                         struct obj_ref* data_ref) {
    struct block_tree_path path;

    index++; /* 0 is not a valid block tree key */

    block_tree_walk(tr, &block_map->tree, index, false, &path);
    if (tr->failed) {
        pr_warn("transaction failed\n");
        block_put_dirty_discard(data, data_ref);
        return;
    }

    if (print_block_map) {
        printf("%s: %" PRIu64 " (found key %" PRIu64 ")\n", __func__, index,
               block_tree_path_get_key(&path));
    }

    assert(block_tree_path_get_key(&path) == index);
    block_tree_path_put_dirty(tr, &path, path.count, data, data_ref);
}

/**
 * block_map_truncate - Free blocks
 * @tr:         Transaction object.
 * @block_map:  Block map object.
 * @index:      Index to start freeing at.
 *
 * Remove and free all blocks starting at @index.
 */
void block_map_truncate(struct transaction* tr,
                        struct block_map* block_map,
                        data_block_t index) {
    struct block_tree_path path;
    data_block_t key;
    data_block_t data;
    data_block_t curr_index;

    curr_index = index + 1; /* 0 is not a valid block tree key */

    while (true) {
        block_tree_walk(tr, &block_map->tree, curr_index, false, &path);
        if (tr->failed) {
            pr_warn("transaction failed, abort\n");
            return;
        }
        key = block_tree_path_get_key(&path);
        if (!key) {
            break;
        }
        assert(key >= curr_index);
        data = block_tree_path_get_data(&path);
        if (!data) {
            /* block_tree_walk returned an empty insert spot for curr_index */
            assert(key != curr_index);
            curr_index = key;
            continue;
        }
        assert(data);
        block_tree_remove(tr, &block_map->tree, key, data);
        if (tr->failed) {
            pr_warn("transaction failed, abort\n");
            return;
        }
        block_discard_dirty_by_block(tr->fs->dev, data);
        block_free(tr, data);
        if (tr->failed) {
            pr_warn("transaction failed, abort\n");
            return;
        }
    }

    /* Only a root leaf node should remain if truncating to 0 */
    assert(index || path.count == 1);
}

/**
 * block_map_check - Check block map for errors
 * @tr:             Transaction object.
 * @block_map:      Block map object.
 * @max_index:      Block map index at and after which no data is expected (i.e.
 *                  maximum exclusive)
 *
 * Return: %false if an error was detected, %true otherwise.
 */
bool block_map_check(struct transaction* tr,
                     struct block_map* block_map,
                     data_block_t max_index) {
    struct block_tree_path path;
    data_block_t prev_index = 0;
    data_block_t index = 1;
    data_block_t min = tr->fs->min_block_num;
    data_block_t max = tr->fs->dev->block_count;
    data_block_t data;

    if (!block_tree_check(tr, &block_map->tree)) {
        return false;
    }

    max_index++; /* 0 is not a valid block tree key */

    block_tree_walk(tr, &block_map->tree, index, false, &path);
    index = block_tree_path_get_key(&path);
    while (index) {
        if (index <= prev_index) {
            pr_err("block map indices are not sequential, %" PRIu64
                   " is after %" PRIu64 "\n",
                   index, prev_index);
            return false;
        }
        if (index >= max_index) {
            pr_err("block map index %" PRIu64
                   " is past (exclusive) block map max index %" PRIu64 "\n",
                   index, max_index);
            return false;
        }
        data = block_tree_path_get_data(&path);
        if (data < min) {
            pr_err("block map data %" PRIu64 " < minimum block %" PRIu64 "\n",
                   index, min);
            return false;
        }
        if (data >= max) {
            pr_err("block map data %" PRIu64 " >= block count %" PRIu64 "\n",
                   index, max);
            return false;
        }
        prev_index = index;
        block_tree_path_next(&path);
        index = block_tree_path_get_key(&path);
    }

    return true;
}

/**
 * block_map_free - Free blocks
 * @tr:         Transaction object.
 * @block_map:  Block map object.
 *
 * Free block_map and all blocks stored in it.
 */
void block_map_free(struct transaction* tr, struct block_map* block_map) {
    data_block_t root_block;

    if (!block_mac_valid(tr, &block_map->tree.root)) {
        return;
    }
    if (print_block_map) {
        printf("%s: root %" PRIu64 "\n", __func__,
               block_mac_to_block(tr, &block_map->tree.root));
        block_tree_print(tr, &block_map->tree);
    }

    block_map_truncate(tr, block_map, 0);
    if (tr->failed) {
        pr_warn("transaction failed\n");
        return;
    }

    root_block = block_mac_to_block(tr, &block_map->tree.root);

    block_discard_dirty_by_block(tr->fs->dev, root_block);
    block_free(tr, root_block);
}