1 | /* SPDX-License-Identifier: GPL-2.0 */ |
2 | /* |
3 | * Latched RB-trees |
4 | * |
5 | * Copyright (C) 2015 Intel Corp., Peter Zijlstra <peterz@infradead.org> |
6 | * |
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 |
9 | * lockless lookups; we cannot guarantee they return a correct result. |
10 | * |
11 | * The simplest solution is a seqlock + RB-tree, this will allow lockless |
12 | * lookups; but has the constraint (inherent to the seqlock) that read sides |
13 | * cannot nest in write sides. |
14 | * |
15 | * If we need to allow unconditional lookups (say as required for NMI context |
16 | * usage) we need a more complex setup; this data structure provides this by |
17 | * employing the latch technique -- see @raw_write_seqcount_latch -- to |
18 | * implement a latched RB-tree which does allow for unconditional lookups by |
19 | * virtue of always having (at least) one stable copy of the tree. |
20 | * |
21 | * However, while we have the guarantee that there is at all times one stable |
22 | * copy, this does not guarantee an iteration will not observe modifications. |
23 | * What might have been a stable copy at the start of the iteration, need not |
24 | * remain so for the duration of the iteration. |
25 | * |
26 | * Therefore, this does require a lockless RB-tree iteration to be non-fatal; |
27 | * see the comment in lib/rbtree.c. Note however that we only require the first |
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 |
30 | * pointed at the stable tree and complete while the modification was halted. |
31 | */ |
32 | |
33 | #ifndef RB_TREE_LATCH_H |
34 | #define RB_TREE_LATCH_H |
35 | |
36 | #include <linux/rbtree.h> |
37 | #include <linux/seqlock.h> |
38 | #include <linux/rcupdate.h> |
39 | |
40 | struct latch_tree_node { |
41 | struct rb_node node[2]; |
42 | }; |
43 | |
44 | struct latch_tree_root { |
45 | seqcount_latch_t seq; |
46 | struct rb_root tree[2]; |
47 | }; |
48 | |
49 | /** |
50 | * latch_tree_ops - operators to define the tree order |
51 | * @less: used for insertion; provides the (partial) order between two elements. |
52 | * @comp: used for lookups; provides the order between the search key and an element. |
53 | * |
54 | * The operators are related like: |
55 | * |
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) |
59 | * |
60 | * If these operators define a partial order on the elements we make no |
61 | * guarantee on which of the elements matching the key is found. See |
62 | * latch_tree_find(). |
63 | */ |
64 | struct latch_tree_ops { |
65 | bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b); |
66 | int (*comp)(void *key, struct latch_tree_node *b); |
67 | }; |
68 | |
69 | static __always_inline struct latch_tree_node * |
70 | __lt_from_rb(struct rb_node *node, int idx) |
71 | { |
72 | return container_of(node, struct latch_tree_node, node[idx]); |
73 | } |
74 | |
75 | static __always_inline void |
76 | __lt_insert(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx, |
77 | bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b)) |
78 | { |
79 | struct rb_root *root = <r->tree[idx]; |
80 | struct rb_node **link = &root->rb_node; |
81 | struct rb_node *node = <n->node[idx]; |
82 | struct rb_node *parent = NULL; |
83 | struct latch_tree_node *ltp; |
84 | |
85 | while (*link) { |
86 | parent = *link; |
87 | ltp = __lt_from_rb(node: parent, idx); |
88 | |
89 | if (less(ltn, ltp)) |
90 | link = &parent->rb_left; |
91 | else |
92 | link = &parent->rb_right; |
93 | } |
94 | |
95 | rb_link_node_rcu(node, parent, rb_link: link); |
96 | rb_insert_color(node, root); |
97 | } |
98 | |
99 | static __always_inline void |
100 | __lt_erase(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx) |
101 | { |
102 | rb_erase(<n->node[idx], <r->tree[idx]); |
103 | } |
104 | |
105 | static __always_inline struct latch_tree_node * |
106 | __lt_find(void *key, struct latch_tree_root *ltr, int idx, |
107 | int (*comp)(void *key, struct latch_tree_node *node)) |
108 | { |
109 | struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node); |
110 | struct latch_tree_node *ltn; |
111 | int c; |
112 | |
113 | while (node) { |
114 | ltn = __lt_from_rb(node, idx); |
115 | c = comp(key, ltn); |
116 | |
117 | if (c < 0) |
118 | node = rcu_dereference_raw(node->rb_left); |
119 | else if (c > 0) |
120 | node = rcu_dereference_raw(node->rb_right); |
121 | else |
122 | return ltn; |
123 | } |
124 | |
125 | return NULL; |
126 | } |
127 | |
128 | /** |
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 |
133 | * |
134 | * It inserts @node into @root in an ordered fashion such that we can always |
135 | * observe one complete tree. See the comment for raw_write_seqcount_latch(). |
136 | * |
137 | * The inserts use rcu_assign_pointer() to publish the element such that the |
138 | * tree structure is stored before we can observe the new @node. |
139 | * |
140 | * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be |
141 | * serialized. |
142 | */ |
143 | static __always_inline void |
144 | latch_tree_insert(struct latch_tree_node *node, |
145 | struct latch_tree_root *root, |
146 | const struct latch_tree_ops *ops) |
147 | { |
148 | raw_write_seqcount_latch(s: &root->seq); |
149 | __lt_insert(ltn: node, ltr: root, idx: 0, less: ops->less); |
150 | raw_write_seqcount_latch(s: &root->seq); |
151 | __lt_insert(ltn: node, ltr: root, idx: 1, less: ops->less); |
152 | } |
153 | |
154 | /** |
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 |
159 | * |
160 | * Removes @node from the trees @root in an ordered fashion such that we can |
161 | * always observe one complete tree. See the comment for |
162 | * raw_write_seqcount_latch(). |
163 | * |
164 | * It is assumed that @node will observe one RCU quiescent state before being |
165 | * reused of freed. |
166 | * |
167 | * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be |
168 | * serialized. |
169 | */ |
170 | static __always_inline void |
171 | latch_tree_erase(struct latch_tree_node *node, |
172 | struct latch_tree_root *root, |
173 | const struct latch_tree_ops *ops) |
174 | { |
175 | raw_write_seqcount_latch(s: &root->seq); |
176 | __lt_erase(ltn: node, ltr: root, idx: 0); |
177 | raw_write_seqcount_latch(s: &root->seq); |
178 | __lt_erase(ltn: node, ltr: root, idx: 1); |
179 | } |
180 | |
181 | /** |
182 | * latch_tree_find() - find the node matching @key in the trees @root |
183 | * @key: search key |
184 | * @root: trees to search for @key |
185 | * @ops: operators defining the node order |
186 | * |
187 | * Does a lockless lookup in the trees @root for the node matching @key. |
188 | * |
189 | * It is assumed that this is called while holding the appropriate RCU read |
190 | * side lock. |
191 | * |
192 | * If the operators define a partial order on the elements (there are multiple |
193 | * elements which have the same key value) it is undefined which of these |
194 | * elements will be found. Nor is it possible to iterate the tree to find |
195 | * further elements with the same key value. |
196 | * |
197 | * Returns: a pointer to the node matching @key or NULL. |
198 | */ |
199 | static __always_inline struct latch_tree_node * |
200 | latch_tree_find(void *key, struct latch_tree_root *root, |
201 | const struct latch_tree_ops *ops) |
202 | { |
203 | struct latch_tree_node *node; |
204 | unsigned int seq; |
205 | |
206 | do { |
207 | seq = raw_read_seqcount_latch(s: &root->seq); |
208 | node = __lt_find(key, ltr: root, idx: seq & 1, comp: ops->comp); |
209 | } while (raw_read_seqcount_latch_retry(s: &root->seq, start: seq)); |
210 | |
211 | return node; |
212 | } |
213 | |
214 | #endif /* RB_TREE_LATCH_H */ |
215 | |