1 /* SPDX-License-Identifier: GPL-2.0-only */
3 * Copyright (C) 2011 Red Hat, Inc.
5 * This file is released under the GPL.
8 #ifndef DM_BTREE_INTERNAL_H
9 #define DM_BTREE_INTERNAL_H
13 /*----------------------------------------------------------------*/
16 * We'll need 2 accessor functions for n->csum and n->blocknr
17 * to support dm-btree-spine.c in that case.
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.
32 __le64 blocknr; /* Block this node is supposed to live in. */
38 } __packed __aligned(8);
41 struct node_header header;
43 } __packed __aligned(8);
47 * Locks a block using the btree node validator.
49 int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
50 struct dm_block **result);
52 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
53 struct dm_btree_value_type *vt);
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);
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
65 struct dm_btree_info *info;
68 struct dm_block *nodes[2];
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);
78 struct dm_btree_info *info;
81 struct dm_block *nodes[2];
86 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
87 void exit_shadow_spine(struct shadow_spine *s);
89 int shadow_step(struct shadow_spine *s, dm_block_t b,
90 struct dm_btree_value_type *vt);
93 * The spine must have at least one entry before calling this.
95 struct dm_block *shadow_current(struct shadow_spine *s);
98 * The spine must have at least two entries before calling this.
100 struct dm_block *shadow_parent(struct shadow_spine *s);
102 int shadow_has_parent(struct shadow_spine *s);
104 dm_block_t shadow_root(struct shadow_spine *s);
109 static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
111 return n->keys + index;
114 static inline void *value_base(struct btree_node *n)
116 return &n->keys[le32_to_cpu(n->header.max_entries)];
119 static inline void *value_ptr(struct btree_node *n, uint32_t index)
121 uint32_t value_size = le32_to_cpu(n->header.value_size);
123 return value_base(n) + (value_size * index);
127 * Assumes the values are suitably-aligned and converts to core format.
129 static inline uint64_t value64(struct btree_node *n, uint32_t index)
131 __le64 *values_le = value_base(n);
133 return le64_to_cpu(values_le[index]);
137 * Searching for a key within a single node.
139 int lower_bound(struct btree_node *n, uint64_t key);
141 extern struct dm_block_validator btree_node_validator;
144 * Value type for upper levels of multi-level btrees.
146 extern void init_le64_type(struct dm_transaction_manager *tm,
147 struct dm_btree_value_type *vt);
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
155 * This only works with single level btrees. The given key must be present in
156 * the tree, otherwise -EINVAL will be returned.
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);
162 #endif /* DM_BTREE_INTERNAL_H */