| /* |
| * 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); |
| } |
