GNU Linux-libre 4.19.264-gnu1
[releases.git] / drivers / md / persistent-data / dm-btree.h
1 /*
2  * Copyright (C) 2011 Red Hat, Inc.
3  *
4  * This file is released under the GPL.
5  */
6 #ifndef _LINUX_DM_BTREE_H
7 #define _LINUX_DM_BTREE_H
8
9 #include "dm-block-manager.h"
10
11 struct dm_transaction_manager;
12
13 /*----------------------------------------------------------------*/
14
15 /*
16  * Annotations used to check on-disk metadata is handled as little-endian.
17  */
18 #ifdef __CHECKER__
19 #  define __dm_written_to_disk(x) __releases(x)
20 #  define __dm_reads_from_disk(x) __acquires(x)
21 #  define __dm_bless_for_disk(x) __acquire(x)
22 #  define __dm_unbless_for_disk(x) __release(x)
23 #else
24 #  define __dm_written_to_disk(x)
25 #  define __dm_reads_from_disk(x)
26 #  define __dm_bless_for_disk(x)
27 #  define __dm_unbless_for_disk(x)
28 #endif
29
30 /*----------------------------------------------------------------*/
31
32 /*
33  * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized
34  * values.
35  */
36
37 /*
38  * Information about the values stored within the btree.
39  */
40 struct dm_btree_value_type {
41         void *context;
42
43         /*
44          * The size in bytes of each value.
45          */
46         uint32_t size;
47
48         /*
49          * Any of these methods can be safely set to NULL if you do not
50          * need the corresponding feature.
51          */
52
53         /*
54          * The btree is making a duplicate of the value, for instance
55          * because previously-shared btree nodes have now diverged.
56          * @value argument is the new copy that the copy function may modify.
57          * (Probably it just wants to increment a reference count
58          * somewhere.) This method is _not_ called for insertion of a new
59          * value: It is assumed the ref count is already 1.
60          */
61         void (*inc)(void *context, const void *value);
62
63         /*
64          * This value is being deleted.  The btree takes care of freeing
65          * the memory pointed to by @value.  Often the del function just
66          * needs to decrement a reference count somewhere.
67          */
68         void (*dec)(void *context, const void *value);
69
70         /*
71          * A test for equality between two values.  When a value is
72          * overwritten with a new one, the old one has the dec method
73          * called _unless_ the new and old value are deemed equal.
74          */
75         int (*equal)(void *context, const void *value1, const void *value2);
76 };
77
78 /*
79  * The shape and contents of a btree.
80  */
81 struct dm_btree_info {
82         struct dm_transaction_manager *tm;
83
84         /*
85          * Number of nested btrees. (Not the depth of a single tree.)
86          */
87         unsigned levels;
88         struct dm_btree_value_type value_type;
89 };
90
91 /*
92  * Set up an empty tree.  O(1).
93  */
94 int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root);
95
96 /*
97  * Delete a tree.  O(n) - this is the slow one!  It can also block, so
98  * please don't call it on an IO path.
99  */
100 int dm_btree_del(struct dm_btree_info *info, dm_block_t root);
101
102 /*
103  * All the lookup functions return -ENODATA if the key cannot be found.
104  */
105
106 /*
107  * Tries to find a key that matches exactly.  O(ln(n))
108  */
109 int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
110                     uint64_t *keys, void *value_le);
111
112 /*
113  * Tries to find the first key where the bottom level key is >= to that
114  * given.  Useful for skipping empty sections of the btree.
115  */
116 int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,
117                          uint64_t *keys, uint64_t *rkey, void *value_le);
118
119 /*
120  * Insertion (or overwrite an existing value).  O(ln(n))
121  */
122 int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
123                     uint64_t *keys, void *value, dm_block_t *new_root)
124                     __dm_written_to_disk(value);
125
126 /*
127  * A variant of insert that indicates whether it actually inserted or just
128  * overwrote.  Useful if you're keeping track of the number of entries in a
129  * tree.
130  */
131 int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,
132                            uint64_t *keys, void *value, dm_block_t *new_root,
133                            int *inserted)
134                            __dm_written_to_disk(value);
135
136 /*
137  * Remove a key if present.  This doesn't remove empty sub trees.  Normally
138  * subtrees represent a separate entity, like a snapshot map, so this is
139  * correct behaviour.  O(ln(n)).
140  */
141 int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
142                     uint64_t *keys, dm_block_t *new_root);
143
144 /*
145  * Removes a _contiguous_ run of values starting from 'keys' and not
146  * reaching keys2 (where keys2 is keys with the final key replaced with
147  * 'end_key').  'end_key' is the one-past-the-end value.  'keys' may be
148  * altered.
149  */
150 int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
151                            uint64_t *keys, uint64_t end_key,
152                            dm_block_t *new_root, unsigned *nr_removed);
153
154 /*
155  * Returns < 0 on failure.  Otherwise the number of key entries that have
156  * been filled out.  Remember trees can have zero entries, and as such have
157  * no lowest key.
158  */
159 int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
160                              uint64_t *result_keys);
161
162 /*
163  * Returns < 0 on failure.  Otherwise the number of key entries that have
164  * been filled out.  Remember trees can have zero entries, and as such have
165  * no highest key.
166  */
167 int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
168                               uint64_t *result_keys);
169
170 /*
171  * Iterate through the a btree, calling fn() on each entry.
172  * It only works for single level trees and is internally recursive, so
173  * monitor stack usage carefully.
174  */
175 int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,
176                   int (*fn)(void *context, uint64_t *keys, void *leaf),
177                   void *context);
178
179
180 /*----------------------------------------------------------------*/
181
182 /*
183  * Cursor API.  This does not follow the rolling lock convention.  Since we
184  * know the order that values are required we can issue prefetches to speed
185  * up iteration.  Use on a single level btree only.
186  */
187 #define DM_BTREE_CURSOR_MAX_DEPTH 16
188
189 struct cursor_node {
190         struct dm_block *b;
191         unsigned index;
192 };
193
194 struct dm_btree_cursor {
195         struct dm_btree_info *info;
196         dm_block_t root;
197
198         bool prefetch_leaves;
199         unsigned depth;
200         struct cursor_node nodes[DM_BTREE_CURSOR_MAX_DEPTH];
201 };
202
203 /*
204  * Creates a fresh cursor.  If prefetch_leaves is set then it is assumed
205  * the btree contains block indexes that will be prefetched.  The cursor is
206  * quite large, so you probably don't want to put it on the stack.
207  */
208 int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root,
209                           bool prefetch_leaves, struct dm_btree_cursor *c);
210 void dm_btree_cursor_end(struct dm_btree_cursor *c);
211 int dm_btree_cursor_next(struct dm_btree_cursor *c);
212 int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count);
213 int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le);
214
215 #endif  /* _LINUX_DM_BTREE_H */