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  * Insertion (or overwrite an existing value).  O(ln(n))
114  */
115 int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
116 		    uint64_t *keys, void *value, dm_block_t *new_root)
117 		    __dm_written_to_disk(value);
118 
119 /*
120  * A variant of insert that indicates whether it actually inserted or just
121  * overwrote.  Useful if you're keeping track of the number of entries in a
122  * tree.
123  */
124 int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,
125 			   uint64_t *keys, void *value, dm_block_t *new_root,
126 			   int *inserted)
127 			   __dm_written_to_disk(value);
128 
129 /*
130  * Remove a key if present.  This doesn't remove empty sub trees.  Normally
131  * subtrees represent a separate entity, like a snapshot map, so this is
132  * correct behaviour.  O(ln(n)).
133  */
134 int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
135 		    uint64_t *keys, dm_block_t *new_root);
136 
137 /*
138  * Removes values between 'keys' and keys2, where keys2 is keys with the
139  * final key replaced with 'end_key'.  'end_key' is the one-past-the-end
140  * value.  'keys' may be altered.
141  */
142 int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
143 			   uint64_t *keys, uint64_t end_key,
144 			   dm_block_t *new_root, unsigned *nr_removed);
145 
146 /*
147  * Returns < 0 on failure.  Otherwise the number of key entries that have
148  * been filled out.  Remember trees can have zero entries, and as such have
149  * no lowest key.
150  */
151 int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
152 			     uint64_t *result_keys);
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 highest key.
158  */
159 int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
160 			      uint64_t *result_keys);
161 
162 /*
163  * Iterate through the a btree, calling fn() on each entry.
164  * It only works for single level trees and is internally recursive, so
165  * monitor stack usage carefully.
166  */
167 int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,
168 		  int (*fn)(void *context, uint64_t *keys, void *leaf),
169 		  void *context);
170 
171 #endif	/* _LINUX_DM_BTREE_H */
172