/*
* 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 <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#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