md/bcache/btree.h

8  * At a high level, bcache's btree is relatively standard b+ tree. All keys and
12  * In the interior nodes, a struct bkey always points to a child btree node, and
15  * of the child node - this would allow us to have variable sized btree nodes
16  * (handy for keeping the depth of the btree 1 by expanding just the root).
21  * overlapping extents - when we read in a btree node from disk, the first thing
25  * struct btree_op is a central interface to the btree code. It's used for
31  * Btree nodes are cached in memory; traversing the btree might require reading
32  * in btree nodes which is handled mostly transparently.
34  * bch_btree_node_get() looks up a btree node in the cache and reads it in from
36  * btree() macro is used to get a btree node, call some function on it, and
40  * it in memory), so we can find the root of the btree by just dereferencing a
42  * tricky, since the root pointer is protected by the lock in the btree node it
45  * In various places we must be able to allocate memory for multiple btree nodes
46  * in order to make forward progress. To do this we use the btree cache itself
47  * as a reserve; if __get_free_pages() fails, we'll find a node in the btree
57  * For writing, we have two btree_write structs embeddded in struct btree - one
77  * When traversing the btree, we may need write locks starting at some level -
78  * inserting a key into the btree will typically only require a write lock on
85  * If, after traversing the btree, the insertion code discovers it has to split
98  * insert the check key it unlocks the btree node and then takes a write lock,
108 	/* If btree_split() frees a btree node, it writes a new pointer to that
109 	 * btree node indicating it was freed; it takes a refcount on
117 struct btree {
121 	/* Key/pointer for this btree node */
127 	struct btree		*parent;
137 	/* For outstanding btree writes, used as a lock - protects write_idx */
152 static inline bool btree_node_ ## flag(struct btree *b)			\
155 static inline void set_btree_node_ ## flag(struct btree *b)		\
170 static inline struct btree_write *btree_current_write(struct btree *b)
175 static inline struct btree_write *btree_prev_write(struct btree *b)
180 static inline struct bset *btree_bset_first(struct btree *b)
185 static inline struct bset *btree_bset_last(struct btree *b)
190 static inline unsigned int bset_block_offset(struct btree *b, struct bset *i)
210 /* Recursing down the btree */
213 	/* for waiting on btree reserve in btree_split() */
248 static inline void rw_lock(bool w, struct btree *b, int level)
256 static inline void rw_unlock(bool w, struct btree *b)
263 void bch_btree_node_read_done(struct btree *b);
264 void __bch_btree_node_write(struct btree *b, struct closure *parent);
265 void bch_btree_node_write(struct btree *b, struct closure *parent);
267 void bch_btree_set_root(struct btree *b);
268 struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op,
270 				     struct btree *parent);
271 struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op,
273 				 struct btree *parent);
275 int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,
311  * These macros are for recursing down the btree - they handle the details of
322  * btree - recurse down the btree on a specified key
325  * @b:		parent btree node
332 	struct btree *_child = bch_btree_node_get((b)->c, op, key, l,	\
343  * btree_root - call a function on the root of the btree
352 		struct btree *_b = (c)->root;				\
377 typedef int (btree_map_nodes_fn)(struct btree_op *b_op, struct btree *b);
395 typedef int (btree_map_keys_fn)(struct btree_op *op, struct btree *b,
399 int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op,