Merge remote-tracking branch 'asoc/fix/si476x' into asoc-next
[platform/adaptation/renesas_rcar/renesas_kernel.git] / drivers / md / persistent-data / 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
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
39 struct btree_node {
40         struct node_header header;
41         __le64 keys[0];
42 } __packed;
43
44
45 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
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);
67 void ro_pop(struct ro_spine *s);
68 struct btree_node *ro_node(struct ro_spine *s);
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  */
102 static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
103 {
104         return n->keys + index;
105 }
106
107 static inline void *value_base(struct btree_node *n)
108 {
109         return &n->keys[le32_to_cpu(n->header.max_entries)];
110 }
111
112 static 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  */
121 static 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  */
131 int lower_bound(struct btree_node *n, uint64_t key);
132
133 extern struct dm_block_validator btree_node_validator;
134
135 #endif  /* DM_BTREE_INTERNAL_H */