include/linux/rbtree_latch.h

1 /* SPDX-License-Identifier: GPL-2.0 */
3  * Latched RB-trees
7  * Since RB-trees have non-atomic modifications they're not immediately suited
8  * for RCU/lockless queries. Even though we made RB-tree lookups non-fatal for
11  * The simplest solution is a seqlock + RB-tree, this will allow lockless
17  * employing the latch technique -- see @raw_write_seqcount_latch -- to
18  * implement a latched RB-tree which does allow for unconditional lookups by
26  * Therefore, this does require a lockless RB-tree iteration to be non-fatal;
28  * condition -- not seeing partial stores -- because the latch thing isolates
29  * us from loops. If we were to interrupt a modification the lookup would be
50  * latch_tree_ops - operators to define the tree order
51  * @less: used for insertion; provides the (partial) order between two elements.
56  *	comp(a->key,b) < 0  := less(a,b)
57  *	comp(a->key,b) > 0  := less(b,a)
58  *	comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
65 	bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b);  member
77 	    bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b))  in __lt_insert()
79 	struct rb_root *root = &ltr->tree[idx];  in __lt_insert()
80 	struct rb_node **link = &root->rb_node;  in __lt_insert()
81 	struct rb_node *node = &ltn->node[idx];  in __lt_insert()
89 		if (less(ltn, ltp))  in __lt_insert()
90 			link = &parent->rb_left;  in __lt_insert()
92 			link = &parent->rb_right;  in __lt_insert()
102 	rb_erase(&ltn->node[idx], &ltr->tree[idx]);  in __lt_erase()
109 	struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node);  in __lt_find()
118 			node = rcu_dereference_raw(node->rb_left);  in __lt_find()
120 			node = rcu_dereference_raw(node->rb_right);  in __lt_find()
129  * latch_tree_insert() - insert @node into the trees @root
148 	raw_write_seqcount_latch(&root->seq);  in latch_tree_insert()
149 	__lt_insert(node, root, 0, ops->less);  in latch_tree_insert()
150 	raw_write_seqcount_latch(&root->seq);  in latch_tree_insert()
151 	__lt_insert(node, root, 1, ops->less);  in latch_tree_insert()
155  * latch_tree_erase() - removes @node from the trees @root
175 	raw_write_seqcount_latch(&root->seq);  in latch_tree_erase()
177 	raw_write_seqcount_latch(&root->seq);  in latch_tree_erase()
182  * latch_tree_find() - find the node matching @key in the trees @root
207 		seq = raw_read_seqcount_latch(&root->seq);  in latch_tree_find()
208 		node = __lt_find(key, root, seq & 1, ops->comp);  in latch_tree_find()
209 	} while (raw_read_seqcount_latch_retry(&root->seq, seq));  in latch_tree_find()