163 lines · c
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_H9#define DM_BTREE_INTERNAL_H10 11#include "dm-btree.h"12 13/*----------------------------------------------------------------*/14 15/*16 * We'll need 2 accessor functions for n->csum and n->blocknr17 * to support dm-btree-spine.c in that case.18 */19 20enum node_flags {21 INTERNAL_NODE = 1,22 LEAF_NODE = 1 << 123};24 25/*26 * Every btree node begins with this structure. Make sure it's a multiple27 * 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-only60 * and one that uses shadowing. These are separate structs to allow the61 * type checker to spot misuse, for example accidentally calling read_lock62 * 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 const 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 practise151 * this means overwrites only, since an insert could cause a node to152 * be split. Useful if you need access to the old value to calculate the153 * new one.154 *155 * This only works with single level btrees. The given key must be present in156 * 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