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
41 	struct rb_node node[2];  member
50  * latch_tree_ops - operators to define the tree order
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)
70 __lt_from_rb(struct rb_node *node, int idx)  in __lt_from_rb()  argument
72 	return container_of(node, struct latch_tree_node, node[idx]);  in __lt_from_rb()
79 	struct rb_root *root = &ltr->tree[idx];  in __lt_insert()  local
80 	struct rb_node **link = &root->rb_node;  in __lt_insert()
81 	struct rb_node *node = &ltn->node[idx];  in __lt_insert()  local
90 			link = &parent->rb_left;  in __lt_insert()
92 			link = &parent->rb_right;  in __lt_insert()
95 	rb_link_node_rcu(node, parent, link);  in __lt_insert()
96 	rb_insert_color(node, root);  in __lt_insert()
102 	rb_erase(&ltn->node[idx], &ltr->tree[idx]);  in __lt_erase()
107 	  int (*comp)(void *key, struct latch_tree_node *node))  in __lt_find()  argument
109 	struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node);  in __lt_find()  local
113 	while (node) {  in __lt_find()
114 		ltn = __lt_from_rb(node, idx);  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
130  * @node: nodes to insert
131  * @root: trees to insert @node into
132  * @ops: operators defining the node order
134  * It inserts @node into @root in an ordered fashion such that we can always
138  * tree structure is stored before we can observe the new @node.
144 latch_tree_insert(struct latch_tree_node *node,  in latch_tree_insert()  argument
145 		  struct latch_tree_root *root,  in latch_tree_insert()  argument
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
156  * @node: nodes to remote
157  * @root: trees to remove @node from
158  * @ops: operators defining the node order
160  * Removes @node from the trees @root in an ordered fashion such that we can
164  * It is assumed that @node will observe one RCU quiescent state before being
171 latch_tree_erase(struct latch_tree_node *node,  in latch_tree_erase()  argument
172 		 struct latch_tree_root *root,  in latch_tree_erase()  argument
175 	raw_write_seqcount_latch(&root->seq);  in latch_tree_erase()
176 	__lt_erase(node, root, 0);  in latch_tree_erase()
177 	raw_write_seqcount_latch(&root->seq);  in latch_tree_erase()
178 	__lt_erase(node, root, 1);  in latch_tree_erase()
182  * latch_tree_find() - find the node matching @key in the trees @root
184  * @root: trees to search for @key
185  * @ops: operators defining the node order
187  * Does a lockless lookup in the trees @root for the node matching @key.
197  * Returns: a pointer to the node matching @key or NULL.
200 latch_tree_find(void *key, struct latch_tree_root *root,  in latch_tree_find()  argument
203 	struct latch_tree_node *node;  in latch_tree_find()  local
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()
211 	return node;  in latch_tree_find()