md/bcache/btree.h

1 /* SPDX-License-Identifier: GPL-2.0 */
13  * the key is the highest key in the child node - except that the highest key in
14  * an interior node is always MAX_KEY. The size field refers to the size on disk
15  * of the child node - this would allow us to have variable sized btree nodes
19  * thoroughly. Btree nodes on disk will in practice have extents that overlap
21  * overlapping extents - when we read in a btree node from disk, the first thing
26  * specifying read vs. write locking, and the embedded closure is used for
27  * waiting on IO or reserve memory.
35  * disk if necessary. This function is almost never called directly though - the
36  * btree() macro is used to get a btree node, call some function on it, and
39  * The root is special cased - it's taken out of the cache's lru (thus pinning
43  * points to - the btree_root() macro handles this.
49  * time, so there's a lock, implemented by a pointer to the btree_op closure -
57  * For writing, we have two btree_write structs embeddded in struct btree - one
58  * write in flight, and one being set up, and we toggle between them.
60  * Writing is done with a single function -  bch_btree_write() really serves two
62  * passing now = false, it merely indicates that the node is now dirty - calling
65  * When passing now = true, bch_btree_write() causes a write to happen
66  * "immediately" (if there was already a write in flight, it'll cause the write
67  * to happen as soon as the previous write completes). It returns immediately
68  * though - but it takes a refcount on the closure in struct btree_op you passed
69  * to it, so a closure_sync() later can be used to wait for the write to
73  * in parallel, reducing the amount of time they have to hold write locks.
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
82  * take write locks at level <= 0, i.e. only leaf nodes. bch_btree_node_get()
86  * then it must restart from the root and take new locks - to do this it changes
87  * the lock field and returns -EINTR, which causes the btree_root() macro to
90  * Handling cache misses require a different mechanism for upgrading to a write
93  * placeholder key to detect races - otherwise, we could race with a write and
97  * For this we use a sequence number that write locks and unlocks increment - to
98  * insert the check key it unlocks the btree node and then takes a write lock,
109 	 * btree node indicating it was freed; it takes a refcount on
110 	 * c->prio_blocked because we can't write the gens until the new
111 	 * pointer is on disk. This allows btree_write_endio() to release the
137 	/* For outstanding btree writes, used as a lock - protects write_idx */
153 {	return test_bit(BTREE_NODE_ ## flag, &b->flags); }		\
156 {	set_bit(BTREE_NODE_ ## flag, &b->flags); }
172 	return b->writes + btree_node_write_idx(b);  in btree_current_write()
177 	return b->writes + (btree_node_write_idx(b) ^ 1);  in btree_prev_write()
182 	return b->keys.set->data;  in btree_bset_first()
187 	return bset_tree_last(&b->keys)->data;  in btree_bset_last()
192 	return bset_sector_offset(&b->keys, i) >> b->c->block_bits;  in bset_block_offset()
197 	atomic_set(&c->sectors_to_gc, c->cache->sb.bucket_size * c->nbuckets / 16);  in set_gc_sectors()
206 	     iter < ARRAY_SIZE((c)->bucket_hash);			\
208 		hlist_for_each_entry_rcu((b), (c)->bucket_hash + iter, hash)
213 	/* for waiting on btree reserve in btree_split() */
214 	wait_queue_entry_t		wait;  member
216 	/* Btree level at which we start taking write locks */
237 	wait_queue_head_t		wait;  member
244 	init_wait(&op->wait);  in bch_btree_op_init()
245 	op->lock = write_lock_level;  in bch_btree_op_init()
250 	w ? down_write(&b->lock)  in rw_lock()
251 	  : down_read(&b->lock);  in rw_lock()
253 		b->seq++;  in rw_lock()
259 		b->seq++;  in rw_unlock()
260 	(w ? up_write : up_read)(&b->lock);  in rw_unlock()
269 				     int level, bool wait,
272 				 struct bkey *k, int level, bool write,
289 	wake_up(&c->gc_wait);  in wake_up_gc()
298 	 * Therefore sectors_to_gc is set to -1 here, before waking up  in force_wake_up_gc()
302 	 * that c->sectors_to_gc being set to other positive value. So  in force_wake_up_gc()
306 	atomic_set(&c->sectors_to_gc, -1);  in force_wake_up_gc()
311  * These macros are for recursing down the btree - they handle the details of
315  * op->lock determines whether we take a read or a write lock at a given depth.
316  * If you've got a read lock and find that you need a write lock (i.e. you're
317  * going to have to split), set op->lock and return -EINTR; btree_root() will
322  * btree - recurse down the btree on a specified key
324  * @key:	key to recurse on
330 	int _r, l = (b)->level - 1;					\
331 	bool _w = l <= (op)->lock;					\
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
350 	int _r = -EINTR;						\
352 		struct btree *_b = (c)->root;				\
354 		rw_lock(_w, _b, _b->level);				\
355 		if (_b == (c)->root &&					\
361 		if (_r == -EINTR)                                       \
363 	} while (_r == -EINTR);                                         \
365 	finish_wait(&(c)->btree_cache_wait, &(op)->wait);               \