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