Commit | Line | Data |
---|---|---|
3241b1d3 JT |
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 | ||
19 | enum 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 | */ | |
28 | struct 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 | } __packed; | |
38 | ||
550929fa | 39 | struct btree_node { |
3241b1d3 JT |
40 | struct node_header header; |
41 | __le64 keys[0]; | |
42 | } __packed; | |
43 | ||
44 | ||
9b460d36 JT |
45 | /* |
46 | * Locks a block using the btree node validator. | |
47 | */ | |
48 | int bn_read_lock(struct dm_btree_info *info, dm_block_t b, | |
49 | struct dm_block **result); | |
50 | ||
550929fa | 51 | void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, |
3241b1d3 JT |
52 | struct dm_btree_value_type *vt); |
53 | ||
54 | int new_block(struct dm_btree_info *info, struct dm_block **result); | |
4c7da06f | 55 | void unlock_block(struct dm_btree_info *info, struct dm_block *b); |
3241b1d3 JT |
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 | */ | |
63 | struct ro_spine { | |
64 | struct dm_btree_info *info; | |
65 | ||
66 | int count; | |
67 | struct dm_block *nodes[2]; | |
68 | }; | |
69 | ||
70 | void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info); | |
71 | int exit_ro_spine(struct ro_spine *s); | |
72 | int ro_step(struct ro_spine *s, dm_block_t new_child); | |
4e7f1f90 | 73 | void ro_pop(struct ro_spine *s); |
550929fa | 74 | struct btree_node *ro_node(struct ro_spine *s); |
3241b1d3 JT |
75 | |
76 | struct 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 | ||
85 | void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info); | |
86 | int exit_shadow_spine(struct shadow_spine *s); | |
87 | ||
88 | int 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 | */ | |
94 | struct dm_block *shadow_current(struct shadow_spine *s); | |
95 | ||
96 | /* | |
97 | * The spine must have at least two entries before calling this. | |
98 | */ | |
99 | struct dm_block *shadow_parent(struct shadow_spine *s); | |
100 | ||
101 | int shadow_has_parent(struct shadow_spine *s); | |
102 | ||
103 | int shadow_root(struct shadow_spine *s); | |
104 | ||
105 | /* | |
106 | * Some inlines. | |
107 | */ | |
550929fa | 108 | static inline __le64 *key_ptr(struct btree_node *n, uint32_t index) |
3241b1d3 JT |
109 | { |
110 | return n->keys + index; | |
111 | } | |
112 | ||
550929fa | 113 | static inline void *value_base(struct btree_node *n) |
3241b1d3 JT |
114 | { |
115 | return &n->keys[le32_to_cpu(n->header.max_entries)]; | |
116 | } | |
117 | ||
550929fa | 118 | static inline void *value_ptr(struct btree_node *n, uint32_t index) |
3241b1d3 | 119 | { |
a3aefb39 | 120 | uint32_t value_size = le32_to_cpu(n->header.value_size); |
3241b1d3 JT |
121 | return value_base(n) + (value_size * index); |
122 | } | |
123 | ||
124 | /* | |
125 | * Assumes the values are suitably-aligned and converts to core format. | |
126 | */ | |
550929fa | 127 | static inline uint64_t value64(struct btree_node *n, uint32_t index) |
3241b1d3 JT |
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 | */ | |
550929fa | 137 | int lower_bound(struct btree_node *n, uint64_t key); |
3241b1d3 JT |
138 | |
139 | extern struct dm_block_validator btree_node_validator; | |
140 | ||
b0dc3c8b JT |
141 | /* |
142 | * Value type for upper levels of multi-level btrees. | |
143 | */ | |
144 | extern void init_le64_type(struct dm_transaction_manager *tm, | |
145 | struct dm_btree_value_type *vt); | |
146 | ||
3241b1d3 | 147 | #endif /* DM_BTREE_INTERNAL_H */ |