1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #pragma once
18
19 #include <stdbool.h>
20 #include <stdint.h>
21 #include <stdio.h>
22 #include <string.h>
23
24 #include "block_cache.h"
25 #include "block_mac.h"
26
27 extern bool print_lookup; /* TODO: remove */
28
29 struct transaction;
30
31 #define BLOCK_TREE_MAX_DEPTH (9)
32
33 /**
34 * struct block_tree - In-memory state of block backed B+ tree
35 * @block_size: Block size
36 * @key_size: Number of bytes used per key. 0 < @key_size <= 8.
37 * @child_data_size: Child or data size. The value at index 0 is the
38 * number of bytes used for each child block_mac in
39 * internal nodes, and the value at index 1 is number
40 * of bytes stored in each data entry in leaf nodes.
41 * 0 < @child_data_size[n] <= sizeof(struct block_mac)
42 * == 24.
43 * @key_count: Array with number of keys per node. The value at
44 * index 0 applies to internal nodes and the value at
45 * index 1 applied to leaf nodes.
46 * @root: Block number and mac value for root block in tree.
47 * @inserting: Data currently beeing added to full node in the
48 * tree. Allows the tree to be read while it is
49 * updating.
50 * @inserting.block: Block number of node that is updating.
51 * @inserting.key: Key of entry that should be added.
52 * @inserting.child: Child that should be added to an internal node.
53 * @inserting.data: Data that should be added to a leaf node.
54 * @update_count: Update counter used to check that the three has not
55 * been modified after a block_tree_path was created.
56 * @root_block_changed: %true if root block was allocated or copied after
57 * this tree struct was initialized. %false otherwise.
58 * @updating: Used to relax some debug check while the tree is
59 * updating, and to detect reentrant updates.
60 * @copy_on_write: %true if tree is persistent, %false if tree should
61 * be discarded when completing transaction. Affects
62 * which set block are allocated from, and if
63 * copy-on-write opearation should be enabled.
64 * @allow_copy_on_write: %false if @allow_copy_on_write is %false or if
65 * tree is read-only, %true otherwise.
66 */
67 struct block_tree {
68 size_t block_size;
69 size_t key_size;
70 size_t child_data_size[2]; /* 0: internal/child, 1: leaf/data */
71 size_t key_count[2]; /* 0: internal, 1: leaf */
72 struct block_mac root;
73 struct {
74 data_block_t block;
75 data_block_t key;
76 struct block_mac child;
77 struct block_mac data;
78 } inserting;
79 int update_count;
80 bool root_block_changed;
81 bool updating;
82 bool copy_on_write;
83 bool allow_copy_on_write;
84 };
85
86 #define BLOCK_TREE_INITIAL_VALUE(block_tree) \
87 { \
88 0, 0, {0, 0}, {0, 0}, BLOCK_MAC_INITIAL_VALUE(block_tree.root), \
89 {0, 0, BLOCK_MAC_INITIAL_VALUE(block_tree.inserting.child), \
90 BLOCK_MAC_INITIAL_VALUE(block_tree.inserting.data)}, \
91 0, 0, 0, 0, 0 \
92 }
93
94 /**
95 * struct block_tree_path_entry - block tree path entry
96 * @block_mac: Block number and mac of tree node
97 * @index: Child or data index
98 * @prev_key: Key at @index - 1, or left key in parent when
99 * @index == 0.
100 * @next_key: Key at @index. Or, right key in parent if key at
101 * @index is not valid (0 or out of range).
102 */
103 struct block_tree_path_entry {
104 struct block_mac block_mac;
105 unsigned int index;
106 data_block_t prev_key;
107 data_block_t next_key;
108 };
109
110 /**
111 * struct block_tree_path - block tree
112 * @entry: Array of block tree path entries.
113 * @count: Number of entries in @entry.
114 * @data: Data found in leaf node at @entry[@count-1].index.
115 * @tr: Transaction object.
116 * @tree: Tree object.
117 * @tree_update_count: @tree.update_count at time of walk.
118 */
119 struct block_tree_path {
120 struct block_tree_path_entry entry[BLOCK_TREE_MAX_DEPTH];
121 unsigned int count;
122 struct block_mac data;
123 struct transaction* tr;
124 struct block_tree* tree;
125 int tree_update_count;
126 };
127
128 void block_tree_print(struct transaction* tr, const struct block_tree* tree);
129 bool block_tree_check(struct transaction* tr, const struct block_tree* tree);
130
131 void block_tree_walk(struct transaction* state,
132 struct block_tree* tree,
133 data_block_t key,
134 bool key_is_max,
135 struct block_tree_path* path);
136
137 void block_tree_path_next(struct block_tree_path* path);
138
block_tree_path_get_key(struct block_tree_path * path)139 static inline data_block_t block_tree_path_get_key(
140 struct block_tree_path* path) {
141 return (path->count > 0) ? path->entry[path->count - 1].next_key : 0;
142 }
143
block_tree_path_get_data(struct block_tree_path * path)144 static inline data_block_t block_tree_path_get_data(
145 struct block_tree_path* path) {
146 return block_mac_to_block(path->tr, &path->data);
147 }
148
block_tree_path_get_data_block_mac(struct block_tree_path * path)149 static inline struct block_mac block_tree_path_get_data_block_mac(
150 struct block_tree_path* path) {
151 return path->data;
152 }
153
154 void block_tree_path_put_dirty(struct transaction* tr,
155 struct block_tree_path* path,
156 int path_index,
157 void* data,
158 struct obj_ref* data_ref);
159
160 void block_tree_insert(struct transaction* state,
161 struct block_tree* tree,
162 data_block_t key,
163 data_block_t data);
164
165 void block_tree_insert_block_mac(struct transaction* state,
166 struct block_tree* tree,
167 data_block_t key,
168 struct block_mac data);
169
170 void block_tree_update(struct transaction* state,
171 struct block_tree* tree,
172 data_block_t old_key,
173 data_block_t old_data,
174 data_block_t new_key,
175 data_block_t new_data);
176
177 void block_tree_update_block_mac(struct transaction* state,
178 struct block_tree* tree,
179 data_block_t old_key,
180 struct block_mac old_data,
181 data_block_t new_key,
182 struct block_mac new_data);
183
184 void block_tree_remove(struct transaction* state,
185 struct block_tree* tree,
186 data_block_t key,
187 data_block_t data);
188
189 void block_tree_init(struct block_tree* tree,
190 size_t block_size,
191 size_t key_size,
192 size_t child_size,
193 size_t data_size);
194
195 void block_tree_copy(struct block_tree* dst, const struct block_tree* src);
196
197 #if BUILD_STORAGE_TEST
198 void block_tree_check_config(struct block_device* dev);
199 void block_tree_check_config_done(void);
200 #endif
201