1 // SPDX-License-Identifier: CDDL-1.0 2 /* 3 * This file and its contents are supplied under the terms of the 4 * Common Development and Distribution License ("CDDL"), version 1.0. 5 * You may only use this file in accordance with the terms of version 6 * 1.0 of the CDDL. 7 * 8 * A full copy of the text of the CDDL should have accompanied this 9 * source. A copy of the CDDL is also available via the Internet at 10 * https://opensource.org/license/CDDL-1.0. 11 */ 12 /* 13 * Copyright (c) 2019 by Delphix. All rights reserved. 14 */ 15 16 #ifndef _BTREE_H 17 #define _BTREE_H 18 19 #ifdef __cplusplus 20 extern "C" { 21 #endif 22 23 #include <sys/zfs_context.h> 24 25 /* 26 * This file defines the interface for a B-Tree implementation for ZFS. The 27 * tree can be used to store arbitrary sortable data types with low overhead 28 * and good operation performance. In addition the tree intelligently 29 * optimizes bulk in-order insertions to improve memory use and performance. 30 * 31 * Note that for all B-Tree functions, the values returned are pointers to the 32 * internal copies of the data in the tree. The internal data can only be 33 * safely mutated if the changes cannot change the ordering of the element 34 * with respect to any other elements in the tree. 35 * 36 * The major drawback of the B-Tree is that any returned elements or indexes 37 * are only valid until a side-effectful operation occurs, since these can 38 * result in reallocation or relocation of data. Side effectful operations are 39 * defined as insertion, removal, and zfs_btree_destroy_nodes. 40 * 41 * The B-Tree has two types of nodes: core nodes, and leaf nodes. Core 42 * nodes have an array of children pointing to other nodes, and an array of 43 * elements that act as separators between the elements of the subtrees rooted 44 * at its children. Leaf nodes only contain data elements, and form the bottom 45 * layer of the tree. Unlike B+ Trees, in this B-Tree implementation the 46 * elements in the core nodes are not copies of or references to leaf node 47 * elements. Each element occurs only once in the tree, no matter what kind 48 * of node it is in. 49 * 50 * The tree's height is the same throughout, unlike many other forms of search 51 * tree. Each node (except for the root) must be between half minus one and 52 * completely full of elements (and children) at all times. Any operation that 53 * would put the node outside of that range results in a rebalancing operation 54 * (taking, merging, or splitting). 55 * 56 * This tree was implemented using descriptions from Wikipedia's articles on 57 * B-Trees and B+ Trees. 58 */ 59 60 /* 61 * Decreasing these values results in smaller memmove operations, but more of 62 * them, and increased memory overhead. Increasing these values results in 63 * higher variance in operation time, and reduces memory overhead. 64 */ 65 #define BTREE_CORE_ELEMS 126 66 #define BTREE_LEAF_SIZE 4096 67 68 extern kmem_cache_t *zfs_btree_leaf_cache; 69 70 typedef struct zfs_btree_hdr { 71 struct zfs_btree_core *bth_parent; 72 /* 73 * Set to -1 to indicate core nodes. Other values represent first 74 * valid element offset for leaf nodes. 75 */ 76 uint32_t bth_first; 77 /* 78 * For both leaf and core nodes, represents the number of elements in 79 * the node. For core nodes, they will have bth_count + 1 children. 80 */ 81 uint32_t bth_count; 82 } zfs_btree_hdr_t; 83 84 typedef struct zfs_btree_core { 85 zfs_btree_hdr_t btc_hdr; 86 zfs_btree_hdr_t *btc_children[BTREE_CORE_ELEMS + 1]; 87 uint8_t btc_elems[]; 88 } zfs_btree_core_t; 89 90 typedef struct zfs_btree_leaf { 91 zfs_btree_hdr_t btl_hdr; 92 uint8_t btl_elems[]; 93 } zfs_btree_leaf_t; 94 95 typedef struct zfs_btree_index { 96 zfs_btree_hdr_t *bti_node; 97 uint32_t bti_offset; 98 /* 99 * True if the location is before the list offset, false if it's at 100 * the listed offset. 101 */ 102 boolean_t bti_before; 103 } zfs_btree_index_t; 104 105 typedef struct btree zfs_btree_t; 106 typedef void * (*bt_find_in_buf_f) (zfs_btree_t *, uint8_t *, uint32_t, 107 const void *, zfs_btree_index_t *); 108 109 struct btree { 110 int (*bt_compar) (const void *, const void *); 111 bt_find_in_buf_f bt_find_in_buf; 112 size_t bt_elem_size; 113 size_t bt_leaf_size; 114 uint32_t bt_leaf_cap; 115 int32_t bt_height; 116 uint64_t bt_num_elems; 117 uint64_t bt_num_nodes; 118 zfs_btree_hdr_t *bt_root; 119 zfs_btree_leaf_t *bt_bulk; // non-null if bulk loading 120 }; 121 122 /* 123 * Implementation of Shar's algorithm designed to accelerate binary search by 124 * eliminating impossible to predict branches. 125 * 126 * For optimality, this should be used to generate the search function in the 127 * same file as the comparator and the comparator should be marked 128 * `__attribute__((always_inline) inline` so that the compiler will inline it. 129 * 130 * Arguments are: 131 * 132 * NAME - The function name for this instance of the search function. Use it 133 * in a subsequent call to zfs_btree_create(). 134 * T - The element type stored inside the B-Tree. 135 * COMP - A comparator to compare two nodes, it must return exactly: -1, 0, 136 * or +1 -1 for <, 0 for ==, and +1 for >. For trivial comparisons, 137 * TREE_CMP() from avl.h can be used in a boilerplate function. 138 */ 139 /* BEGIN CSTYLED */ 140 #define ZFS_BTREE_FIND_IN_BUF_FUNC(NAME, T, COMP) \ 141 _Pragma("GCC diagnostic push") \ 142 _Pragma("GCC diagnostic ignored \"-Wunknown-pragmas\"") \ 143 static void * \ 144 NAME(zfs_btree_t *tree, uint8_t *buf, uint32_t nelems, \ 145 const void *value, zfs_btree_index_t *where) \ 146 { \ 147 T *i = (T *)buf; \ 148 (void) tree; \ 149 _Pragma("GCC unroll 9") \ 150 while (nelems > 1) { \ 151 uint32_t half = nelems / 2; \ 152 nelems -= half; \ 153 i += (COMP(&i[half - 1], value) < 0) * half; \ 154 } \ 155 \ 156 int comp = COMP(i, value); \ 157 where->bti_offset = (i - (T *)buf) + (comp < 0); \ 158 where->bti_before = (comp != 0); \ 159 \ 160 if (comp == 0) { \ 161 return (i); \ 162 } \ 163 \ 164 return (NULL); \ 165 } \ 166 _Pragma("GCC diagnostic pop") 167 /* END CSTYLED */ 168 169 /* 170 * Allocate and deallocate caches for btree nodes. 171 */ 172 void zfs_btree_init(void); 173 void zfs_btree_fini(void); 174 175 /* 176 * Initialize an B-Tree. Arguments are: 177 * 178 * tree - the tree to be initialized 179 * compar - function to compare two nodes, it must return exactly: -1, 0, or +1 180 * -1 for <, 0 for ==, and +1 for > 181 * find - optional function to accelerate searches inside B-Tree nodes 182 * through Shar's algorithm and comparator inlining. Setting this to 183 * NULL will use a generic function. The function should be created 184 * using ZFS_BTREE_FIND_IN_BUF_FUNC() in the same file as compar. 185 * compar should be marked `__attribute__((always_inline)) inline` or 186 * performance is unlikely to improve very much. 187 * size - the value of sizeof(struct my_type) 188 * lsize - custom leaf size 189 */ 190 void zfs_btree_create(zfs_btree_t *, 191 int (*) (const void *, const void *), 192 bt_find_in_buf_f, size_t); 193 void zfs_btree_create_custom(zfs_btree_t *, 194 int (*)(const void *, const void *), 195 bt_find_in_buf_f, size_t, size_t); 196 197 /* 198 * Find a node with a matching value in the tree. Returns the matching node 199 * found. If not found, it returns NULL and then if "where" is not NULL it sets 200 * "where" for use with zfs_btree_add_idx() or zfs_btree_nearest(). 201 * 202 * node - node that has the value being looked for 203 * where - position for use with zfs_btree_nearest() or zfs_btree_add_idx(), 204 * may be NULL 205 */ 206 void *zfs_btree_find(zfs_btree_t *, const void *, zfs_btree_index_t *); 207 208 /* 209 * Insert a node into the tree. 210 * 211 * node - the node to insert 212 * where - position as returned from zfs_btree_find() 213 */ 214 void zfs_btree_add_idx(zfs_btree_t *, const void *, 215 const zfs_btree_index_t *); 216 217 /* 218 * Return the first or last valued node in the tree. Will return NULL if the 219 * tree is empty. The index can be NULL if the location of the first or last 220 * element isn't required. 221 */ 222 void *zfs_btree_first(zfs_btree_t *, zfs_btree_index_t *); 223 void *zfs_btree_last(zfs_btree_t *, zfs_btree_index_t *); 224 225 /* 226 * Return the next or previous valued node in the tree. The second index can 227 * safely be NULL, if the location of the next or previous value isn't 228 * required. 229 */ 230 void *zfs_btree_next(zfs_btree_t *, const zfs_btree_index_t *, 231 zfs_btree_index_t *); 232 void *zfs_btree_prev(zfs_btree_t *, const zfs_btree_index_t *, 233 zfs_btree_index_t *); 234 235 /* 236 * Get a value from a tree and an index. 237 */ 238 void *zfs_btree_get(zfs_btree_t *, zfs_btree_index_t *); 239 240 /* 241 * Add a single value to the tree. The value must not compare equal to any 242 * other node already in the tree. Note that the value will be copied out, not 243 * inserted directly. It is safe to free or destroy the value once this 244 * function returns. 245 */ 246 void zfs_btree_add(zfs_btree_t *, const void *); 247 248 /* 249 * Remove a single value from the tree. The value must be in the tree. The 250 * pointer passed in may be a pointer into a tree-controlled buffer, but it 251 * need not be. 252 */ 253 void zfs_btree_remove(zfs_btree_t *, const void *); 254 255 /* 256 * Remove the value at the given location from the tree. 257 */ 258 void zfs_btree_remove_idx(zfs_btree_t *, zfs_btree_index_t *); 259 260 /* 261 * Return the number of nodes in the tree 262 */ 263 ulong_t zfs_btree_numnodes(zfs_btree_t *); 264 265 /* 266 * Used to destroy any remaining nodes in a tree. The cookie argument should 267 * be initialized to NULL before the first call. Returns a node that has been 268 * removed from the tree and may be free()'d. Returns NULL when the tree is 269 * empty. 270 * 271 * Once you call zfs_btree_destroy_nodes(), you can only continuing calling it 272 * and finally zfs_btree_destroy(). No other B-Tree routines will be valid. 273 * 274 * cookie - an index used to save state between calls to 275 * zfs_btree_destroy_nodes() 276 * 277 * EXAMPLE: 278 * zfs_btree_t *tree; 279 * struct my_data *node; 280 * zfs_btree_index_t *cookie; 281 * 282 * cookie = NULL; 283 * while ((node = zfs_btree_destroy_nodes(tree, &cookie)) != NULL) 284 * data_destroy(node); 285 * zfs_btree_destroy(tree); 286 */ 287 void *zfs_btree_destroy_nodes(zfs_btree_t *, zfs_btree_index_t **); 288 289 /* 290 * Destroys all nodes in the tree quickly. This doesn't give the caller an 291 * opportunity to iterate over each node and do its own cleanup; for that, use 292 * zfs_btree_destroy_nodes(). 293 */ 294 void zfs_btree_clear(zfs_btree_t *); 295 296 /* 297 * Final destroy of an B-Tree. Arguments are: 298 * 299 * tree - the empty tree to destroy 300 */ 301 void zfs_btree_destroy(zfs_btree_t *tree); 302 303 /* Runs a variety of self-checks on the btree to verify integrity. */ 304 void zfs_btree_verify(zfs_btree_t *tree); 305 306 #ifdef __cplusplus 307 } 308 #endif 309 310 #endif /* _BTREE_H */ 311