Loading...
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} __packed;
38
39struct node {
40 struct node_header header;
41 __le64 keys[0];
42} __packed;
43
44
45void inc_children(struct dm_transaction_manager *tm, struct node *n,
46 struct dm_btree_value_type *vt);
47
48int new_block(struct dm_btree_info *info, struct dm_block **result);
49int 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 */
57struct ro_spine {
58 struct dm_btree_info *info;
59
60 int count;
61 struct dm_block *nodes[2];
62};
63
64void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
65int exit_ro_spine(struct ro_spine *s);
66int ro_step(struct ro_spine *s, dm_block_t new_child);
67struct node *ro_node(struct ro_spine *s);
68
69struct shadow_spine {
70 struct dm_btree_info *info;
71
72 int count;
73 struct dm_block *nodes[2];
74
75 dm_block_t root;
76};
77
78void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
79int exit_shadow_spine(struct shadow_spine *s);
80
81int shadow_step(struct shadow_spine *s, dm_block_t b,
82 struct dm_btree_value_type *vt);
83
84/*
85 * The spine must have at least one entry before calling this.
86 */
87struct dm_block *shadow_current(struct shadow_spine *s);
88
89/*
90 * The spine must have at least two entries before calling this.
91 */
92struct dm_block *shadow_parent(struct shadow_spine *s);
93
94int shadow_has_parent(struct shadow_spine *s);
95
96int shadow_root(struct shadow_spine *s);
97
98/*
99 * Some inlines.
100 */
101static inline __le64 *key_ptr(struct node *n, uint32_t index)
102{
103 return n->keys + index;
104}
105
106static inline void *value_base(struct node *n)
107{
108 return &n->keys[le32_to_cpu(n->header.max_entries)];
109}
110
111static inline void *value_ptr(struct node *n, uint32_t index)
112{
113 uint32_t value_size = le32_to_cpu(n->header.value_size);
114 return value_base(n) + (value_size * index);
115}
116
117/*
118 * Assumes the values are suitably-aligned and converts to core format.
119 */
120static inline uint64_t value64(struct node *n, uint32_t index)
121{
122 __le64 *values_le = value_base(n);
123
124 return le64_to_cpu(values_le[index]);
125}
126
127/*
128 * Searching for a key within a single node.
129 */
130int lower_bound(struct node *n, uint64_t key);
131
132extern struct dm_block_validator btree_node_validator;
133
134#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} __packed;
38
39struct btree_node {
40 struct node_header header;
41 __le64 keys[0];
42} __packed;
43
44
45void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
46 struct dm_btree_value_type *vt);
47
48int new_block(struct dm_btree_info *info, struct dm_block **result);
49int 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 */
57struct ro_spine {
58 struct dm_btree_info *info;
59
60 int count;
61 struct dm_block *nodes[2];
62};
63
64void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
65int exit_ro_spine(struct ro_spine *s);
66int ro_step(struct ro_spine *s, dm_block_t new_child);
67void ro_pop(struct ro_spine *s);
68struct btree_node *ro_node(struct ro_spine *s);
69
70struct 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
79void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
80int exit_shadow_spine(struct shadow_spine *s);
81
82int 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 */
88struct dm_block *shadow_current(struct shadow_spine *s);
89
90/*
91 * The spine must have at least two entries before calling this.
92 */
93struct dm_block *shadow_parent(struct shadow_spine *s);
94
95int shadow_has_parent(struct shadow_spine *s);
96
97int shadow_root(struct shadow_spine *s);
98
99/*
100 * Some inlines.
101 */
102static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
103{
104 return n->keys + index;
105}
106
107static inline void *value_base(struct btree_node *n)
108{
109 return &n->keys[le32_to_cpu(n->header.max_entries)];
110}
111
112static inline void *value_ptr(struct btree_node *n, uint32_t index)
113{
114 uint32_t value_size = le32_to_cpu(n->header.value_size);
115 return value_base(n) + (value_size * index);
116}
117
118/*
119 * Assumes the values are suitably-aligned and converts to core format.
120 */
121static inline uint64_t value64(struct btree_node *n, uint32_t index)
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 */
131int lower_bound(struct btree_node *n, uint64_t key);
132
133extern struct dm_block_validator btree_node_validator;
134
135#endif /* DM_BTREE_INTERNAL_H */