1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 /* 3 * Copyright (C) 2011 Red Hat, Inc. 4 * 5 * This file is released under the GPL. 6 */ 7 8 #ifndef DM_BTREE_INTERNAL_H 9 #define DM_BTREE_INTERNAL_H 10 11 #include "dm-btree.h" 12 13 /*----------------------------------------------------------------*/ 14 15 /* 16 * We'll need 2 accessor functions for n->csum and n->blocknr 17 * to support dm-btree-spine.c in that case. 18 */ 19 20 enum node_flags { 21 INTERNAL_NODE = 1, 22 LEAF_NODE = 1 << 1 23 }; 24 25 /* 26 * Every btree node begins with this structure. Make sure it's a multiple 27 * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned. 28 */ 29 struct node_header { 30 __le32 csum; 31 __le32 flags; 32 __le64 blocknr; /* Block this node is supposed to live in. */ 33 34 __le32 nr_entries; 35 __le32 max_entries; 36 __le32 value_size; 37 __le32 padding; 38 } __packed __aligned(8); 39 40 struct btree_node { 41 struct node_header header; 42 __le64 keys[]; 43 } __packed __aligned(8); 44 45 46 /* 47 * Locks a block using the btree node validator. 48 */ 49 int bn_read_lock(struct dm_btree_info *info, dm_block_t b, 50 struct dm_block **result); 51 52 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, 53 struct dm_btree_value_type *vt); 54 55 int new_block(struct dm_btree_info *info, struct dm_block **result); 56 void unlock_block(struct dm_btree_info *info, struct dm_block *b); 57 58 /* 59 * Spines keep track of the rolling locks. There are 2 variants, read-only 60 * and one that uses shadowing. These are separate structs to allow the 61 * type checker to spot misuse, for example accidentally calling read_lock 62 * on a shadow spine. 63 */ 64 struct ro_spine { 65 struct dm_btree_info *info; 66 67 int count; 68 struct dm_block *nodes[2]; 69 }; 70 71 void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info); 72 void exit_ro_spine(struct ro_spine *s); 73 int ro_step(struct ro_spine *s, dm_block_t new_child); 74 void ro_pop(struct ro_spine *s); 75 struct btree_node *ro_node(struct ro_spine *s); 76 77 struct shadow_spine { 78 struct dm_btree_info *info; 79 80 int count; 81 struct dm_block *nodes[2]; 82 83 dm_block_t root; 84 }; 85 86 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info); 87 void exit_shadow_spine(struct shadow_spine *s); 88 89 int shadow_step(struct shadow_spine *s, dm_block_t b, 90 struct dm_btree_value_type *vt); 91 92 /* 93 * The spine must have at least one entry before calling this. 94 */ 95 struct dm_block *shadow_current(struct shadow_spine *s); 96 97 /* 98 * The spine must have at least two entries before calling this. 99 */ 100 struct dm_block *shadow_parent(struct shadow_spine *s); 101 102 int shadow_has_parent(struct shadow_spine *s); 103 104 dm_block_t shadow_root(struct shadow_spine *s); 105 106 /* 107 * Some inlines. 108 */ 109 static inline __le64 *key_ptr(struct btree_node *n, uint32_t index) 110 { 111 return n->keys + index; 112 } 113 114 static inline void *value_base(struct btree_node *n) 115 { 116 return &n->keys[le32_to_cpu(n->header.max_entries)]; 117 } 118 119 static inline void *value_ptr(struct btree_node *n, uint32_t index) 120 { 121 uint32_t value_size = le32_to_cpu(n->header.value_size); 122 123 return value_base(n) + (value_size * index); 124 } 125 126 /* 127 * Assumes the values are suitably-aligned and converts to core format. 128 */ 129 static inline uint64_t value64(struct btree_node *n, uint32_t index) 130 { 131 __le64 *values_le = value_base(n); 132 133 return le64_to_cpu(values_le[index]); 134 } 135 136 /* 137 * Searching for a key within a single node. 138 */ 139 int lower_bound(struct btree_node *n, uint64_t key); 140 141 extern struct dm_block_validator btree_node_validator; 142 143 /* 144 * Value type for upper levels of multi-level btrees. 145 */ 146 extern void init_le64_type(struct dm_transaction_manager *tm, 147 struct dm_btree_value_type *vt); 148 149 /* 150 * This returns a shadowed btree leaf that you may modify. In practise 151 * this means overwrites only, since an insert could cause a node to 152 * be split. Useful if you need access to the old value to calculate the 153 * new one. 154 * 155 * This only works with single level btrees. The given key must be present in 156 * the tree, otherwise -EINVAL will be returned. 157 */ 158 int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root, 159 uint64_t key, int *index, 160 dm_block_t *new_root, struct dm_block **leaf); 161 162 #endif /* DM_BTREE_INTERNAL_H */ 163