/* * Copyright (C) 2015 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. */ #pragma once #include #include #include #include #include "block_cache.h" #include "block_mac.h" extern bool print_lookup; /* TODO: remove */ struct transaction; #define BLOCK_TREE_MAX_DEPTH (9) /** * struct block_tree - In-memory state of block backed B+ tree * @block_size: Block size * @key_size: Number of bytes used per key. 0 < @key_size <= 8. * @child_data_size: Child or data size. The value at index 0 is the * number of bytes used for each child block_mac in * internal nodes, and the value at index 1 is number * of bytes stored in each data entry in leaf nodes. * 0 < @child_data_size[n] <= sizeof(struct block_mac) * == 24. * @key_count: Array with number of keys per node. The value at * index 0 applies to internal nodes and the value at * index 1 applied to leaf nodes. * @root: Block number and mac value for root block in tree. * @inserting: Data currently beeing added to full node in the * tree. Allows the tree to be read while it is * updating. * @inserting.block: Block number of node that is updating. * @inserting.key: Key of entry that should be added. * @inserting.child: Child that should be added to an internal node. * @inserting.data: Data that should be added to a leaf node. * @update_count: Update counter used to check that the three has not * been modified after a block_tree_path was created. * @root_block_changed: %true if root block was allocated or copied after * this tree struct was initialized. %false otherwise. * @updating: Used to relax some debug check while the tree is * updating, and to detect reentrant updates. * @copy_on_write: %true if tree is persistent, %false if tree should * be discarded when completing transaction. Affects * which set block are allocated from, and if * copy-on-write opearation should be enabled. * @allow_copy_on_write: %false if @allow_copy_on_write is %false or if * tree is read-only, %true otherwise. */ struct block_tree { size_t block_size; size_t key_size; size_t child_data_size[2]; /* 0: internal/child, 1: leaf/data */ size_t key_count[2]; /* 0: internal, 1: leaf */ struct block_mac root; struct { data_block_t block; data_block_t key; struct block_mac child; struct block_mac data; } inserting; int update_count; bool root_block_changed; bool updating; bool copy_on_write; bool allow_copy_on_write; }; #define BLOCK_TREE_INITIAL_VALUE(block_tree) \ { \ 0, 0, {0, 0}, {0, 0}, BLOCK_MAC_INITIAL_VALUE(block_tree.root), \ {0, 0, BLOCK_MAC_INITIAL_VALUE(block_tree.inserting.child), \ BLOCK_MAC_INITIAL_VALUE(block_tree.inserting.data)}, \ 0, 0, 0, 0, 0 \ } /** * struct block_tree_path_entry - block tree path entry * @block_mac: Block number and mac of tree node * @index: Child or data index * @prev_key: Key at @index - 1, or left key in parent when * @index == 0. * @next_key: Key at @index. Or, right key in parent if key at * @index is not valid (0 or out of range). */ struct block_tree_path_entry { struct block_mac block_mac; unsigned int index; data_block_t prev_key; data_block_t next_key; }; /** * struct block_tree_path - block tree * @entry: Array of block tree path entries. * @count: Number of entries in @entry. * @data: Data found in leaf node at @entry[@count-1].index. * @tr: Transaction object. * @tree: Tree object. * @tree_update_count: @tree.update_count at time of walk. */ struct block_tree_path { struct block_tree_path_entry entry[BLOCK_TREE_MAX_DEPTH]; unsigned int count; struct block_mac data; struct transaction* tr; struct block_tree* tree; int tree_update_count; }; void block_tree_print(struct transaction* tr, const struct block_tree* tree); bool block_tree_check(struct transaction* tr, const struct block_tree* tree); void block_tree_walk(struct transaction* state, struct block_tree* tree, data_block_t key, bool key_is_max, struct block_tree_path* path); void block_tree_path_next(struct block_tree_path* path); static inline data_block_t block_tree_path_get_key( struct block_tree_path* path) { return (path->count > 0) ? path->entry[path->count - 1].next_key : 0; } static inline data_block_t block_tree_path_get_data( struct block_tree_path* path) { return block_mac_to_block(path->tr, &path->data); } static inline struct block_mac block_tree_path_get_data_block_mac( struct block_tree_path* path) { return path->data; } void block_tree_path_put_dirty(struct transaction* tr, struct block_tree_path* path, int path_index, void* data, struct obj_ref* data_ref); void block_tree_insert(struct transaction* state, struct block_tree* tree, data_block_t key, data_block_t data); void block_tree_insert_block_mac(struct transaction* state, struct block_tree* tree, data_block_t key, struct block_mac data); void block_tree_update(struct transaction* state, struct block_tree* tree, data_block_t old_key, data_block_t old_data, data_block_t new_key, data_block_t new_data); void block_tree_update_block_mac(struct transaction* state, struct block_tree* tree, data_block_t old_key, struct block_mac old_data, data_block_t new_key, struct block_mac new_data); void block_tree_remove(struct transaction* state, struct block_tree* tree, data_block_t key, data_block_t data); void block_tree_init(struct block_tree* tree, size_t block_size, size_t key_size, size_t child_size, size_t data_size); void block_tree_copy(struct block_tree* dst, const struct block_tree* src); #if BUILD_STORAGE_TEST void block_tree_check_config(struct block_device* dev); void block_tree_check_config_done(void); #endif