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 20enum 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 */ 29struct 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 40struct 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 */ 49int bn_read_lock(struct dm_btree_info *info, dm_block_t b, 50 struct dm_block **result); 51 52void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, 53 struct dm_btree_value_type *vt); 54 55int new_block(struct dm_btree_info *info, struct dm_block **result); 56void 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 */ 64struct ro_spine { 65 struct dm_btree_info *info; 66 67 int count; 68 struct dm_block *nodes[2]; 69}; 70 71void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info); 72void exit_ro_spine(struct ro_spine *s); 73int ro_step(struct ro_spine *s, dm_block_t new_child); 74void ro_pop(struct ro_spine *s); 75struct btree_node *ro_node(struct ro_spine *s); 76 77struct 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 86void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info); 87void exit_shadow_spine(struct shadow_spine *s); 88 89int 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 */ 95struct dm_block *shadow_current(struct shadow_spine *s); 96 97/* 98 * The spine must have at least two entries before calling this. 99 */ 100struct dm_block *shadow_parent(struct shadow_spine *s); 101 102int shadow_has_parent(struct shadow_spine *s); 103 104dm_block_t shadow_root(struct shadow_spine *s); 105 106/* 107 * Some inlines. 108 */ 109static inline __le64 *key_ptr(struct btree_node *n, uint32_t index) 110{ 111 return n->keys + index; 112} 113 114static inline void *value_base(struct btree_node *n) 115{ 116 return &n->keys[le32_to_cpu(n->header.max_entries)]; 117} 118 119static 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 */ 129static 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 */ 139int lower_bound(struct btree_node *n, uint64_t key); 140 141extern struct dm_block_validator btree_node_validator; 142 143/* 144 * Value type for upper levels of multi-level btrees. 145 */ 146extern 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 */ 158int 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