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