]>
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 | ||
550929fa | 45 | void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, |
3241b1d3 JT |
46 | struct dm_btree_value_type *vt); |
47 | ||
48 | int new_block(struct dm_btree_info *info, struct dm_block **result); | |
49 | int unlock_block(struct dm_btree_info *info, struct dm_block *b); | |
50 | ||
51 | /* | |
52 | * Spines keep track of the rolling locks. There are 2 variants, read-only | |
53 | * and one that uses shadowing. These are separate structs to allow the | |
54 | * type checker to spot misuse, for example accidentally calling read_lock | |
55 | * on a shadow spine. | |
56 | */ | |
57 | struct ro_spine { | |
58 | struct dm_btree_info *info; | |
59 | ||
60 | int count; | |
61 | struct dm_block *nodes[2]; | |
62 | }; | |
63 | ||
64 | void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info); | |
65 | int exit_ro_spine(struct ro_spine *s); | |
66 | int ro_step(struct ro_spine *s, dm_block_t new_child); | |
4e7f1f90 | 67 | void ro_pop(struct ro_spine *s); |
550929fa | 68 | struct btree_node *ro_node(struct ro_spine *s); |
3241b1d3 JT |
69 | |
70 | struct shadow_spine { | |
71 | struct dm_btree_info *info; | |
72 | ||
73 | int count; | |
74 | struct dm_block *nodes[2]; | |
75 | ||
76 | dm_block_t root; | |
77 | }; | |
78 | ||
79 | void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info); | |
80 | int exit_shadow_spine(struct shadow_spine *s); | |
81 | ||
82 | int shadow_step(struct shadow_spine *s, dm_block_t b, | |
83 | struct dm_btree_value_type *vt); | |
84 | ||
85 | /* | |
86 | * The spine must have at least one entry before calling this. | |
87 | */ | |
88 | struct dm_block *shadow_current(struct shadow_spine *s); | |
89 | ||
90 | /* | |
91 | * The spine must have at least two entries before calling this. | |
92 | */ | |
93 | struct dm_block *shadow_parent(struct shadow_spine *s); | |
94 | ||
95 | int shadow_has_parent(struct shadow_spine *s); | |
96 | ||
97 | int shadow_root(struct shadow_spine *s); | |
98 | ||
99 | /* | |
100 | * Some inlines. | |
101 | */ | |
550929fa | 102 | static inline __le64 *key_ptr(struct btree_node *n, uint32_t index) |
3241b1d3 JT |
103 | { |
104 | return n->keys + index; | |
105 | } | |
106 | ||
550929fa | 107 | static inline void *value_base(struct btree_node *n) |
3241b1d3 JT |
108 | { |
109 | return &n->keys[le32_to_cpu(n->header.max_entries)]; | |
110 | } | |
111 | ||
550929fa | 112 | static inline void *value_ptr(struct btree_node *n, uint32_t index) |
3241b1d3 | 113 | { |
a3aefb39 | 114 | uint32_t value_size = le32_to_cpu(n->header.value_size); |
3241b1d3 JT |
115 | return value_base(n) + (value_size * index); |
116 | } | |
117 | ||
118 | /* | |
119 | * Assumes the values are suitably-aligned and converts to core format. | |
120 | */ | |
550929fa | 121 | static inline uint64_t value64(struct btree_node *n, uint32_t index) |
3241b1d3 JT |
122 | { |
123 | __le64 *values_le = value_base(n); | |
124 | ||
125 | return le64_to_cpu(values_le[index]); | |
126 | } | |
127 | ||
128 | /* | |
129 | * Searching for a key within a single node. | |
130 | */ | |
550929fa | 131 | int lower_bound(struct btree_node *n, uint64_t key); |
3241b1d3 JT |
132 | |
133 | extern struct dm_block_validator btree_node_validator; | |
134 | ||
135 | #endif /* DM_BTREE_INTERNAL_H */ |