Commit | Line | Data |
---|---|---|
dff86257 MD |
1 | /* |
2 | * urcu-rbtree.c | |
3 | * | |
4 | * Userspace RCU library - Red-Black Tree | |
5 | * | |
6 | * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
7 | * | |
8 | * This library is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU Lesser General Public | |
10 | * License as published by the Free Software Foundation; either | |
11 | * version 2.1 of the License, or (at your option) any later version. | |
12 | * | |
13 | * This library is distributed in the hope that it will be useful, | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
16 | * Lesser General Public License for more details. | |
17 | * | |
18 | * You should have received a copy of the GNU Lesser General Public | |
19 | * License along with this library; if not, write to the Free Software | |
20 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
21 | * | |
22 | * Implementation of RCU-adapted data structures and operations based on the RB | |
23 | * tree algorithms found in chapter 12 of: | |
24 | * | |
25 | * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and | |
26 | * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT | |
27 | * Press, September 2009. | |
28 | */ | |
29 | ||
30 | #define _BSD_SOURCE | |
31 | #define _LGPL_SOURCE | |
32 | ||
33 | #include <stdio.h> | |
34 | #include <pthread.h> | |
35 | #include <assert.h> | |
269a9ef6 | 36 | #include <string.h> |
230dd288 | 37 | #include <unistd.h> |
8f354bc4 | 38 | #include <errno.h> |
dff86257 MD |
39 | |
40 | #include <urcu/rcurbtree.h> | |
41 | #include <urcu-pointer.h> | |
c479601c | 42 | #include <urcu-call-rcu.h> |
dca45c9f | 43 | #include <urcu/compiler.h> |
dff86257 | 44 | |
ae46d4ae MD |
45 | /* |
46 | * Explanation of next/prev walk coherency and search coherency when | |
47 | * performed concurrently with updates. | |
48 | * | |
49 | * next/prev walk coherency with respect to concurrent updates: | |
50 | * | |
51 | * There are 3 scenarios for which we need to model and validate this: | |
52 | * rotation, transplant and "teleportation" (the latter being a remote | |
53 | * transplant in a remove non-nil case). | |
54 | * | |
55 | * - rotation left (right is symmetric) | |
56 | * xl and yr point to the same parent nodes before/after left | |
57 | * rotation. yll and ylr also point to the same parent node | |
58 | * before/after left rotation. | |
59 | * As we are copying x, y and yl (the 3 nodes which parent/child | |
60 | * relationship are changed) to "new" version of this node cluster, | |
61 | * all external references to the cluster either point to the old | |
62 | * cluster or the new one. If we take this cluster as a "black box" | |
63 | * from the point of view of next/prev traversal, all we have to | |
64 | * ensure is that the old and the new cluster behave in the exact same | |
65 | * way with respect to traversal order. | |
66 | * | |
67 | * - transplant | |
68 | * In this operation, we transplant a copy of "v" into its parent | |
69 | * location (u), thus replacing it. The children of "v", vl and vr, | |
70 | * still point to v (new version) after the transplant, so it does not | |
71 | * change the behavior when considering the next/prev traversal. "v" | |
72 | * being copied to a new version ensures that the parent pointers of v | |
73 | * are pointing to its new parent (parent of u) before it is published | |
74 | * to readers (by setting the child pointer of u's parent to the new | |
75 | * copy of v). | |
76 | * | |
77 | * - teleportation | |
78 | * This one is probably the most tricky and will require some ascii | |
79 | * art to explain. | |
80 | * | |
81 | * We want to remove z from this tree: | |
82 | * | |
83 | * zp | |
84 | * \ | |
85 | * z | |
86 | * / \ | |
87 | * zl zr | |
88 | * / | |
89 | * a | |
90 | * / \ | |
91 | * b ar | |
92 | * / \ | |
93 | * y br | |
94 | * \ | |
95 | * yr | |
96 | * / \ | |
97 | * yrl yrr | |
98 | * | |
99 | * What we are going to do is to "teleport" y into z's location, | |
100 | * reparenting yr to b. We are taking care to create a new cluster | |
101 | * copy that is isolated from any reader. We will represent the new | |
102 | * members of the cluster with capital letters. | |
103 | * | |
104 | * zp | |
105 | * \ | |
106 | * Y | |
107 | * / \ | |
108 | * zl ZR | |
109 | * / | |
110 | * A | |
111 | * / \ | |
112 | * B ar | |
113 | * / \ | |
114 | * YR br | |
115 | * / \ | |
116 | * yrl yrr | |
117 | * | |
118 | * In this transient state, we notice that the pointers within the | |
119 | * cluster all point to the new cluster nodes, and they point to the | |
120 | * correct external nodes. However, no external pointer point to the | |
121 | * cluster (yet). The first pointer to point to this cluster will be | |
122 | * "zp->right". It will therefore make the cluster visible for search. | |
123 | * | |
124 | * In this intermediate state, we can walk through the new cluster | |
125 | * when coming from the top (in a next/prev traversal), but can come | |
126 | * back to the old cluster when going back up from the children nodes. | |
127 | * All we have to ensure is that the two clusters, taken as a black | |
128 | * box from a next/prev traversal perspective, yield to the exact same | |
129 | * result. | |
130 | * | |
131 | * Search coherency with concurrent updates: | |
132 | * | |
133 | * Simple "search" (only going down the tree) is also handled by this | |
134 | * cluster scheme. The explanation is a subset of the prev/next | |
135 | * explanation, where we don't have to care about the intermediate | |
136 | * stages where the children point to the old cluster, because we only | |
137 | * ever use the top level pointers to go down into the children nodes, | |
138 | * we never go back up. So by simply making sure that all the cluster | |
139 | * internal nodes pointers are setup correctly before making the | |
140 | * cluster visible to the readers (by setting the parent pointer to | |
141 | * the topmost new node in the cluster), we are sure that readers will | |
142 | * see a coherent view of the cluster at all times. | |
143 | */ | |
144 | ||
dff86257 MD |
145 | #ifdef DEBUG |
146 | #define dbg_printf(args...) printf(args) | |
9c161ee1 | 147 | #define dbg_usleep(usecs) usleep(usecs) |
dff86257 MD |
148 | #else |
149 | #define dbg_printf(args...) | |
9c161ee1 | 150 | #define dbg_usleep(usecs) |
dff86257 MD |
151 | #endif |
152 | ||
6daf6090 MD |
153 | /* |
154 | * Undefine this to enable the non-RCU rotate and transplant functions | |
2abaffb0 MD |
155 | * (for debugging). Note that these versions don't support the tree |
156 | * max_end updates, so lookups must be performed with | |
157 | * rcu_rbtree_search_begin_key when using this debug facility. | |
6daf6090 | 158 | */ |
dbe4ae98 MD |
159 | #define RBTREE_RCU_SUPPORT_ROTATE_LEFT |
160 | #define RBTREE_RCU_SUPPORT_ROTATE_RIGHT | |
6daf6090 | 161 | #define RBTREE_RCU_SUPPORT_TRANSPLANT |
c2ceb27c | 162 | #define RBTREE_RCU_SUPPORT |
6daf6090 | 163 | |
24b9b19b MD |
164 | #ifdef RBTREE_RCU_SUPPORT |
165 | #define c_rcu_dereference(x) rcu_dereference(x) | |
21b35829 MD |
166 | #define c_cmm_smp_wmb() cmm_smp_wmb() |
167 | #define c_cmm_smp_wmc() cmm_smp_wmc() | |
168 | #define C_CMM_STORE_SHARED(x, v) CMM_STORE_SHARED(x, v) | |
169 | #define C__CMM_STORE_SHARED(x, v) _CMM_STORE_SHARED(x, v) | |
24b9b19b MD |
170 | #else |
171 | #define c_rcu_dereference(x) (x) | |
21b35829 MD |
172 | #define c_cmm_smp_wmb() |
173 | #define c_cmm_smp_wmc() | |
174 | #define C_CMM_STORE_SHARED(x, v) ((x) = (v)) | |
175 | #define C__CMM_STORE_SHARED(x, v) ((x) = (v)) | |
24b9b19b MD |
176 | #endif |
177 | ||
1444707c MD |
178 | /* |
179 | * Add internal mutex locking within the RBTree, for debugging. Enable this | |
180 | * define and add mutexes to RCU readers to debug races with with rotation or | |
181 | * transplant. | |
182 | */ | |
183 | /* #define RBTREE_INTERNAL_LOCKING */ | |
184 | ||
185 | #ifdef RBTREE_INTERNAL_LOCKING | |
230dd288 MD |
186 | static pthread_mutex_t test_mutex = PTHREAD_MUTEX_INITIALIZER; |
187 | static pthread_mutex_t outer_mutex = PTHREAD_MUTEX_INITIALIZER; | |
188 | ||
189 | static | |
190 | void lock_outer_mutex(void) | |
191 | { | |
192 | pthread_mutex_lock(&outer_mutex); | |
193 | } | |
194 | ||
195 | static | |
196 | void unlock_outer_mutex(void) | |
197 | { | |
198 | pthread_mutex_unlock(&outer_mutex); | |
199 | } | |
200 | ||
201 | static | |
202 | void lock_test_mutex(void) | |
203 | { | |
204 | pthread_mutex_lock(&test_mutex); | |
205 | } | |
206 | ||
207 | static | |
208 | void unlock_test_mutex(void) | |
209 | { | |
210 | pthread_mutex_unlock(&test_mutex); | |
211 | } | |
1444707c MD |
212 | #else |
213 | static | |
214 | void lock_outer_mutex(void) | |
215 | { | |
216 | } | |
217 | ||
218 | static | |
219 | void unlock_outer_mutex(void) | |
220 | { | |
221 | } | |
222 | ||
223 | static | |
224 | void lock_test_mutex(void) | |
225 | { | |
226 | } | |
227 | ||
228 | static | |
229 | void unlock_test_mutex(void) | |
230 | { | |
231 | } | |
230dd288 MD |
232 | #endif |
233 | ||
7ba89e62 MD |
234 | static |
235 | void set_parent(struct rcu_rbtree_node *node, | |
236 | struct rcu_rbtree_node *parent, | |
237 | unsigned int pos) | |
238 | { | |
21b35829 | 239 | C__CMM_STORE_SHARED(node->parent, ((unsigned long) parent) | pos); |
7ba89e62 MD |
240 | } |
241 | ||
242 | static | |
243 | struct rcu_rbtree_node *get_parent(struct rcu_rbtree_node *node) | |
244 | { | |
245 | return (struct rcu_rbtree_node *) (node->parent & ~1UL); | |
246 | } | |
247 | ||
248 | static | |
249 | unsigned int get_pos(struct rcu_rbtree_node *node) | |
250 | { | |
251 | return (unsigned int) (node->parent & 1UL); | |
252 | } | |
253 | ||
254 | static | |
255 | struct rcu_rbtree_node *get_parent_and_pos(struct rcu_rbtree_node *node, | |
256 | unsigned int *pos) | |
257 | { | |
24b9b19b | 258 | unsigned long parent_pos = c_rcu_dereference(node->parent); |
7ba89e62 MD |
259 | |
260 | *pos = (unsigned int) (parent_pos & 1UL); | |
261 | return (struct rcu_rbtree_node *) (parent_pos & ~1UL); | |
262 | } | |
263 | ||
269a9ef6 MD |
264 | static |
265 | void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc) | |
266 | { | |
267 | x->decay_next = xc; | |
268 | } | |
269 | ||
270 | static | |
271 | struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x) | |
272 | { | |
dbe4ae98 MD |
273 | if (!x) |
274 | return NULL; | |
269a9ef6 MD |
275 | while (x->decay_next) |
276 | x = x->decay_next; | |
277 | return x; | |
278 | } | |
279 | ||
280 | static | |
281 | struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x) | |
282 | { | |
283 | return x->decay_next; | |
284 | } | |
285 | ||
3c672595 | 286 | static |
8f354bc4 MD |
287 | struct rcu_rbtree_node *_rcu_rbtree_alloc_node(struct rcu_rbtree *rbtree) |
288 | { | |
289 | return rbtree->rballoc(sizeof(struct rcu_rbtree_node)); | |
290 | } | |
291 | ||
292 | static | |
293 | void _rcu_rbtree_free_node(struct rcu_head *head) | |
3c672595 MD |
294 | { |
295 | struct rcu_rbtree_node *node = | |
296 | caa_container_of(head, struct rcu_rbtree_node, head); | |
297 | node->rbtree->rbfree(node); | |
298 | } | |
299 | ||
c2ceb27c MD |
300 | #ifdef RBTREE_RCU_SUPPORT |
301 | ||
269a9ef6 MD |
302 | static |
303 | struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree, | |
304 | struct rcu_rbtree_node *x) | |
305 | { | |
306 | struct rcu_rbtree_node *xc; | |
307 | ||
8ded5fe9 | 308 | if (rcu_rbtree_is_nil(rbtree, x)) |
269a9ef6 MD |
309 | return x; |
310 | ||
8f354bc4 | 311 | xc = _rcu_rbtree_alloc_node(rbtree); |
3c672595 | 312 | memcpy(xc, x, sizeof(*xc)); |
269a9ef6 MD |
313 | xc->decay_next = NULL; |
314 | set_decay(x, xc); | |
1cdd423d | 315 | rbtree->call_rcu(&x->head, _rcu_rbtree_free_node); |
269a9ef6 MD |
316 | return xc; |
317 | } | |
318 | ||
c2ceb27c MD |
319 | #else /* RBTREE_RCU_SUPPORT */ |
320 | ||
321 | static | |
322 | struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree, | |
323 | struct rcu_rbtree_node *x) | |
324 | { | |
325 | return x; | |
326 | } | |
327 | ||
328 | #endif | |
329 | ||
dca45c9f MD |
330 | /* |
331 | * Info for range lookups: | |
332 | * Range lookup information is only valid when used when searching for | |
333 | * ranges. It should never be used in next/prev traversal because the | |
334 | * pointers to parents are not in sync with the parent vision of the | |
335 | * children range. | |
336 | */ | |
337 | static | |
a84e8c8e MD |
338 | void set_left(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node, |
339 | struct rcu_rbtree_node *left) | |
dca45c9f | 340 | { |
dca45c9f | 341 | node->_left = left; |
dca45c9f MD |
342 | } |
343 | ||
344 | static | |
a84e8c8e MD |
345 | void set_right(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node, |
346 | struct rcu_rbtree_node *right) | |
dca45c9f | 347 | { |
dca45c9f | 348 | node->_right = right; |
dca45c9f MD |
349 | } |
350 | ||
66b64c35 MD |
351 | static |
352 | void *calculate_node_max_end(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node) | |
353 | { | |
354 | void *max_end; | |
355 | ||
356 | max_end = node->end; | |
357 | if (!rcu_rbtree_is_nil(rbtree, node->_right)) { | |
358 | if (rbtree->comp(max_end, node->_right->max_end) < 0) | |
359 | max_end = node->_right->max_end; | |
360 | } | |
361 | if (!rcu_rbtree_is_nil(rbtree, node->_left)) { | |
362 | if (rbtree->comp(max_end, node->_left->max_end) < 0) | |
363 | max_end = node->_left->max_end; | |
364 | } | |
365 | return max_end; | |
366 | } | |
367 | ||
dff86257 MD |
368 | /* |
369 | * TODO | |
370 | * Deal with memory allocation errors. | |
371 | * Can be ensured by reserving a pool of memory entries before doing the | |
372 | * insertion, which will have to be function of number of | |
e20fb727 MD |
373 | * transplantations/rotations required for the operation (which is a |
374 | * multiple of the tree height). | |
dff86257 MD |
375 | */ |
376 | ||
5d2c985d | 377 | #ifdef DEBUG |
dff86257 MD |
378 | static |
379 | void show_tree(struct rcu_rbtree *rbtree) | |
380 | { | |
381 | struct rcu_rbtree_node *node; | |
382 | ||
383 | node = rcu_rbtree_min(rbtree, rbtree->root); | |
8ded5fe9 | 384 | while (!rcu_rbtree_is_nil(rbtree, node)) { |
269a9ef6 | 385 | assert(!is_decay(node)); |
fcb4eea8 | 386 | printf("{ b:%lX e:%lX pb: %lX r:%lX l:%lX %s %s %s} ", |
3366b9c0 MD |
387 | (unsigned long) node->begin, |
388 | (unsigned long) node->end, | |
389 | (unsigned long) get_parent(node)->begin, | |
fcb4eea8 MD |
390 | (unsigned long) node->_right->begin, |
391 | (unsigned long) node->_left->begin, | |
dff86257 | 392 | node->color ? "red" : "black", |
7ba89e62 | 393 | get_pos(node) ? "right" : "left", |
a84e8c8e | 394 | rcu_rbtree_is_nil(rbtree, node) ? "nil" : ""); |
dff86257 MD |
395 | node = rcu_rbtree_next(rbtree, node); |
396 | } | |
397 | printf("\n"); | |
398 | } | |
66b64c35 MD |
399 | |
400 | #define check_max_end(rbtree, x) \ | |
401 | do { \ | |
402 | if (rcu_rbtree_is_nil(rbtree, x)) \ | |
403 | break; \ | |
404 | assert(rbtree->comp(x->max_end, \ | |
405 | calculate_node_max_end(rbtree, x)) == 0); \ | |
406 | } while (0) | |
407 | ||
5d2c985d MD |
408 | #else /* DEBUG */ |
409 | static | |
410 | void show_tree(struct rcu_rbtree *rbtree) | |
411 | { | |
412 | } | |
66b64c35 MD |
413 | |
414 | static | |
415 | void check_max_end(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x) | |
416 | { | |
417 | } | |
5d2c985d | 418 | #endif /* DEBUG */ |
dff86257 MD |
419 | |
420 | static | |
421 | struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree) | |
422 | { | |
423 | return &rbtree->nil_node; | |
424 | } | |
425 | ||
426 | /* | |
427 | * Iterative rbtree search. | |
428 | */ | |
00539351 | 429 | struct rcu_rbtree_node *rcu_rbtree_search(struct rcu_rbtree *rbtree, |
66b64c35 MD |
430 | struct rcu_rbtree_node *x, |
431 | void *point) | |
432 | { | |
433 | struct rcu_rbtree_node *xl; | |
434 | ||
435 | dbg_printf("searching point 0x%lx\n", (unsigned long) point); | |
24b9b19b | 436 | x = c_rcu_dereference(x); |
66b64c35 MD |
437 | |
438 | while (!rcu_rbtree_is_nil(rbtree, x)) { | |
439 | dbg_usleep(10); | |
24b9b19b | 440 | xl = c_rcu_dereference(x->_left); |
66b64c35 MD |
441 | dbg_printf("search x %lx x_end %lx x_max_end %lx\n", (unsigned long) x->begin, |
442 | (unsigned long) x->end, (unsigned long) x->max_end); | |
443 | dbg_printf("search xl %lx xl_end %lx xl_max_end %lx\n", (unsigned long) xl->begin, | |
444 | (unsigned long) xl->end, (unsigned long) xl->max_end); | |
445 | if (!rcu_rbtree_is_nil(rbtree, xl) | |
446 | && (rbtree->comp(xl->max_end, point) > 0)) { | |
447 | dbg_printf("go left\n"); | |
448 | x = xl; | |
3d8a234b | 449 | } else if (rbtree->comp(x->begin, point) <= 0 |
66b64c35 MD |
450 | && rbtree->comp(point, x->end) < 0) { |
451 | dbg_printf("got it!\n"); | |
452 | break; | |
453 | } else if (rbtree->comp(point, x->begin) > 0) { | |
454 | dbg_printf("go right\n"); | |
24b9b19b | 455 | x = c_rcu_dereference(x->_right); |
66b64c35 MD |
456 | } else { |
457 | dbg_printf("not found!\n"); | |
458 | x = make_nil(rbtree); | |
459 | } | |
460 | } | |
461 | if (rcu_rbtree_is_nil(rbtree, x)) | |
462 | dbg_printf("Reached bottom of tree.\n"); | |
463 | ||
464 | return x; | |
465 | } | |
466 | ||
467 | struct rcu_rbtree_node *rcu_rbtree_search_range(struct rcu_rbtree *rbtree, | |
468 | struct rcu_rbtree_node *x, | |
469 | void *begin, void *end) | |
470 | { | |
471 | struct rcu_rbtree_node *node; | |
472 | ||
473 | node = rcu_rbtree_search(rbtree, x, begin); | |
474 | if (rcu_rbtree_is_nil(rbtree, node)) | |
475 | return node; | |
476 | if (rbtree->comp(node->end, end) < 0) | |
477 | return NULL; /* High is outside lookup range */ | |
478 | return node; | |
479 | } | |
480 | ||
481 | /* | |
482 | * Search by exact range start value. | |
483 | */ | |
484 | struct rcu_rbtree_node *rcu_rbtree_search_begin_key(struct rcu_rbtree *rbtree, | |
dff86257 MD |
485 | struct rcu_rbtree_node *x, |
486 | void *k) | |
487 | { | |
24b9b19b | 488 | x = c_rcu_dereference(x); |
ac5f3963 | 489 | int comp; |
dff86257 | 490 | |
3366b9c0 | 491 | while (!rcu_rbtree_is_nil(rbtree, x) && (comp = rbtree->comp(k, x->begin)) != 0) { |
9c161ee1 | 492 | dbg_usleep(10); |
ac5f3963 | 493 | if (comp < 0) |
24b9b19b | 494 | x = c_rcu_dereference(x->_left); |
dff86257 | 495 | else |
24b9b19b | 496 | x = c_rcu_dereference(x->_right); |
dff86257 MD |
497 | } |
498 | return x; | |
499 | } | |
500 | ||
230dd288 MD |
501 | static |
502 | struct rcu_rbtree_node *rcu_rbtree_min_dup_decay(struct rcu_rbtree *rbtree, | |
503 | struct rcu_rbtree_node *x, | |
504 | struct rcu_rbtree_node **zr) | |
505 | { | |
506 | struct rcu_rbtree_node *xl; | |
507 | ||
24b9b19b | 508 | x = c_rcu_dereference(x); |
230dd288 | 509 | |
8ded5fe9 | 510 | if (rcu_rbtree_is_nil(rbtree, x)) { |
230dd288 MD |
511 | *zr = x; |
512 | return x; | |
513 | } else | |
514 | *zr = x = dup_decay_node(rbtree, x); | |
515 | ||
24b9b19b | 516 | while (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left))) { |
230dd288 | 517 | x = dup_decay_node(rbtree, xl); |
7ba89e62 | 518 | set_parent(x, get_decay(get_parent(x)), get_pos(x)); |
dca45c9f | 519 | get_parent(x)->_left = get_decay(get_parent(x)->_left); |
230dd288 MD |
520 | } |
521 | return x; | |
522 | } | |
523 | ||
524 | static | |
525 | struct rcu_rbtree_node *rcu_rbtree_min_update_decay(struct rcu_rbtree *rbtree, | |
526 | struct rcu_rbtree_node *x) | |
527 | { | |
528 | struct rcu_rbtree_node *xl; | |
529 | ||
24b9b19b | 530 | x = c_rcu_dereference(x); |
230dd288 | 531 | |
8ded5fe9 | 532 | if (rcu_rbtree_is_nil(rbtree, x)) |
230dd288 MD |
533 | return x; |
534 | else { | |
dca45c9f MD |
535 | set_parent(x->_right, get_decay(get_parent(x->_right)), |
536 | get_pos(x->_right)); | |
537 | set_parent(x->_left, get_decay(get_parent(x->_left)), | |
538 | get_pos(x->_left)); | |
230dd288 MD |
539 | } |
540 | ||
24b9b19b | 541 | while (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left))) { |
230dd288 | 542 | x = xl; |
dca45c9f MD |
543 | set_parent(x->_right, get_decay(get_parent(x->_right)), |
544 | get_pos(x->_right)); | |
545 | set_parent(x->_left, get_decay(get_parent(x->_left)), | |
546 | get_pos(x->_left)); | |
230dd288 MD |
547 | } |
548 | return x; | |
549 | } | |
550 | ||
dff86257 MD |
551 | struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree, |
552 | struct rcu_rbtree_node *x) | |
553 | { | |
554 | struct rcu_rbtree_node *xl; | |
555 | ||
24b9b19b | 556 | x = c_rcu_dereference(x); |
dff86257 | 557 | |
8ded5fe9 | 558 | if (rcu_rbtree_is_nil(rbtree, x)) |
dff86257 MD |
559 | return x; |
560 | ||
24b9b19b | 561 | while (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left))) |
dff86257 MD |
562 | x = xl; |
563 | return x; | |
564 | } | |
565 | ||
566 | struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree, | |
567 | struct rcu_rbtree_node *x) | |
568 | { | |
569 | struct rcu_rbtree_node *xr; | |
570 | ||
24b9b19b | 571 | x = c_rcu_dereference(x); |
dff86257 | 572 | |
8ded5fe9 | 573 | if (rcu_rbtree_is_nil(rbtree, x)) |
dff86257 MD |
574 | return x; |
575 | ||
24b9b19b | 576 | while (!rcu_rbtree_is_nil(rbtree, xr = c_rcu_dereference(x->_right))) |
dff86257 MD |
577 | x = xr; |
578 | return x; | |
579 | } | |
580 | ||
dff86257 | 581 | /* |
7ba89e62 MD |
582 | * RCU read lock must be held across the next/prev calls to ensure validity of |
583 | * the returned node. | |
dff86257 MD |
584 | */ |
585 | struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree, | |
586 | struct rcu_rbtree_node *x) | |
587 | { | |
269a9ef6 | 588 | struct rcu_rbtree_node *xr, *y; |
7ba89e62 | 589 | unsigned int x_pos; |
dff86257 | 590 | |
24b9b19b | 591 | x = c_rcu_dereference(x); |
dff86257 | 592 | |
24b9b19b | 593 | if (!rcu_rbtree_is_nil(rbtree, xr = c_rcu_dereference(x->_right))) |
dff86257 | 594 | return rcu_rbtree_min(rbtree, xr); |
7ba89e62 | 595 | y = get_parent_and_pos(x, &x_pos); |
8ded5fe9 | 596 | while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_RIGHT) { |
dff86257 | 597 | x = y; |
7ba89e62 | 598 | y = get_parent_and_pos(y, &x_pos); |
dff86257 MD |
599 | } |
600 | return y; | |
601 | } | |
602 | ||
603 | struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree, | |
604 | struct rcu_rbtree_node *x) | |
605 | { | |
269a9ef6 | 606 | struct rcu_rbtree_node *xl, *y; |
7ba89e62 | 607 | unsigned int x_pos; |
dff86257 | 608 | |
24b9b19b | 609 | x = c_rcu_dereference(x); |
dff86257 | 610 | |
24b9b19b | 611 | if (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left))) |
4aa30442 | 612 | return rcu_rbtree_max(rbtree, xl); |
7ba89e62 | 613 | y = get_parent_and_pos(x, &x_pos); |
8ded5fe9 | 614 | while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_LEFT) { |
dff86257 | 615 | x = y; |
7ba89e62 | 616 | y = get_parent_and_pos(y, &x_pos); |
dff86257 MD |
617 | } |
618 | return y; | |
619 | } | |
620 | ||
7bc64d1d MD |
621 | /* |
622 | * "node" needs to be non-visible by readers. | |
623 | */ | |
624 | static | |
625 | void populate_node_end(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node, | |
fcb4eea8 | 626 | unsigned int copy_parents, struct rcu_rbtree_node *stop) |
7bc64d1d MD |
627 | { |
628 | struct rcu_rbtree_node *prev = NULL, *orig_node = node, *top; | |
629 | ||
630 | do { | |
631 | void *max_end; | |
632 | ||
fcb4eea8 | 633 | assert(node); |
7bc64d1d | 634 | assert(!rcu_rbtree_is_nil(rbtree, node)); |
4459c487 | 635 | |
66b64c35 MD |
636 | if (prev && copy_parents) { |
637 | node = dup_decay_node(rbtree, node); | |
638 | if (get_pos(prev) == IS_RIGHT) | |
639 | node->_right = prev; | |
640 | else | |
641 | node->_left = prev; | |
642 | set_parent(prev, node, get_pos(prev)); | |
643 | } | |
644 | ||
fda7316a | 645 | max_end = calculate_node_max_end(rbtree, node); |
66b64c35 MD |
646 | /* |
647 | * Compare the node max_end keys to make sure we replace | |
648 | * references to a key belonging to a node we remove | |
649 | * from the tree. Otherwise we would still be using this | |
650 | * pointer as an invalid reference after garbage | |
651 | * collection of the node and of its associated | |
652 | * begin/end pointers. | |
653 | */ | |
654 | if (max_end != node->max_end) { | |
7bc64d1d MD |
655 | node->max_end = max_end; |
656 | } else { | |
7bc64d1d | 657 | top = get_parent(node); |
21b35829 | 658 | c_cmm_smp_wmb(); /* write into node before publish */ |
7bc64d1d MD |
659 | /* make new branch visible to readers */ |
660 | if (rcu_rbtree_is_nil(rbtree, top)) | |
21b35829 | 661 | C__CMM_STORE_SHARED(rbtree->root, node); |
7bc64d1d | 662 | if (get_pos(node) == IS_LEFT) |
21b35829 | 663 | C__CMM_STORE_SHARED(top->_left, node); |
7bc64d1d | 664 | else |
21b35829 | 665 | C__CMM_STORE_SHARED(top->_right, node); |
7bc64d1d MD |
666 | goto end; |
667 | } | |
fcb4eea8 MD |
668 | |
669 | /* Check for propagation stop */ | |
670 | if (node == stop) | |
671 | return; | |
672 | ||
7bc64d1d | 673 | prev = node; |
fcb4eea8 MD |
674 | node = get_parent(node); |
675 | } while (!rcu_rbtree_is_nil(rbtree, node)); | |
7bc64d1d MD |
676 | |
677 | top = node; /* nil */ | |
21b35829 | 678 | c_cmm_smp_wmb(); /* write into node before publish */ |
7bc64d1d | 679 | /* make new branch visible to readers */ |
21b35829 | 680 | C__CMM_STORE_SHARED(rbtree->root, prev); |
7bc64d1d MD |
681 | |
682 | end: | |
fcb4eea8 MD |
683 | if (!copy_parents) |
684 | return; | |
7bc64d1d MD |
685 | /* update children */ |
686 | node = orig_node; | |
687 | do { | |
688 | assert(!rcu_rbtree_is_nil(rbtree, node)); | |
689 | set_parent(node->_left, get_decay(get_parent(node->_left)), IS_LEFT); | |
690 | set_parent(node->_right, get_decay(get_parent(node->_right)), IS_RIGHT); | |
691 | } while ((node = get_parent(node)) != top); | |
692 | } | |
693 | ||
dff86257 MD |
694 | /* |
695 | * We have to ensure these assumptions are correct for prev/next | |
696 | * traversal: | |
697 | * | |
698 | * with x being a right child, the assumption that: | |
dca45c9f | 699 | * get_parent(x)->_right == x |
dff86257 | 700 | * or if x is a left child, the assumption that: |
dca45c9f | 701 | * get_parent(x)->_left == x |
dff86257 MD |
702 | * |
703 | * This explains why we have to allocate a vc copy of the node for left_rotate, | |
704 | * right_rotate and transplant operations. | |
705 | * | |
706 | * We always ensure that the right/left child and correct parent is set in the | |
707 | * node copies *before* we reparent the children and make the upper-level point | |
708 | * to the copy. | |
709 | */ | |
710 | ||
711 | /* RCU: copy x and y, atomically point to new versions. GC old. */ | |
712 | /* Should be eventually followed by a cmm_smp_wmc() */ | |
dff86257 | 713 | |
dbe4ae98 MD |
714 | #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT |
715 | ||
dff86257 | 716 | static |
269a9ef6 MD |
717 | void left_rotate(struct rcu_rbtree *rbtree, |
718 | struct rcu_rbtree_node *x) | |
dff86257 | 719 | { |
a84e8c8e | 720 | struct rcu_rbtree_node *y, *y_left; |
dff86257 | 721 | |
66b64c35 MD |
722 | dbg_printf("left rotate %lx\n", (unsigned long) x->begin); |
723 | ||
dca45c9f MD |
724 | y = x->_right; |
725 | y_left = y->_left; | |
269a9ef6 MD |
726 | |
727 | /* Now operate on new copy, decay old versions */ | |
dbe4ae98 MD |
728 | x = dup_decay_node(rbtree, x); |
729 | y = dup_decay_node(rbtree, y); | |
730 | y_left = dup_decay_node(rbtree, y_left); | |
269a9ef6 | 731 | |
66b64c35 MD |
732 | check_max_end(rbtree, get_parent(x)); |
733 | check_max_end(rbtree, x); | |
734 | check_max_end(rbtree, y); | |
735 | ||
676dd8b6 | 736 | /* Internal node modifications */ |
7ba89e62 MD |
737 | set_parent(y, get_parent(x), get_pos(x)); |
738 | set_parent(x, y, IS_LEFT); | |
a84e8c8e MD |
739 | set_left(rbtree, y, x); |
740 | set_right(rbtree, x, y_left); | |
dca45c9f | 741 | |
8ded5fe9 | 742 | if (!rcu_rbtree_is_nil(rbtree, y_left)) |
7ba89e62 | 743 | set_parent(y_left, x, IS_RIGHT); |
676dd8b6 | 744 | |
fda7316a MD |
745 | /* |
746 | * We only changed the relative position of x and y wrt their | |
747 | * children, and reparented y (but are keeping the same nodes in | |
748 | * place, so its parent does not need to have end value | |
749 | * recalculated). | |
750 | */ | |
751 | x->max_end = calculate_node_max_end(rbtree, x); | |
752 | y->max_end = calculate_node_max_end(rbtree, y); | |
753 | ||
21b35829 | 754 | c_cmm_smp_wmb(); /* write into node before publish */ |
676dd8b6 MD |
755 | |
756 | /* External references update (visible by readers) */ | |
a84e8c8e | 757 | if (rcu_rbtree_is_nil(rbtree, get_parent(y))) |
21b35829 | 758 | C__CMM_STORE_SHARED(rbtree->root, y); |
a84e8c8e | 759 | else if (get_pos(y) == IS_LEFT) |
21b35829 | 760 | C__CMM_STORE_SHARED(get_parent(y)->_left, y); |
676dd8b6 | 761 | else |
21b35829 | 762 | C__CMM_STORE_SHARED(get_parent(y)->_right, y); |
676dd8b6 | 763 | |
dbe4ae98 | 764 | /* Point children to new copy (parent only used by updates/next/prev) */ |
dca45c9f MD |
765 | set_parent(x->_left, get_decay(get_parent(x->_left)), |
766 | get_pos(x->_left)); | |
767 | set_parent(y->_right, get_decay(get_parent(y->_right)), | |
768 | get_pos(y->_right)); | |
8ded5fe9 | 769 | if (!rcu_rbtree_is_nil(rbtree, y_left)) { |
dca45c9f MD |
770 | set_parent(y_left->_right, |
771 | get_decay(get_parent(y_left->_right)), | |
772 | get_pos(y_left->_right)); | |
773 | set_parent(y_left->_left, | |
774 | get_decay(get_parent(y_left->_left)), | |
775 | get_pos(y_left->_left)); | |
dbe4ae98 | 776 | } |
269a9ef6 MD |
777 | |
778 | /* Sanity checks */ | |
dca45c9f MD |
779 | assert(y == rbtree->root || get_parent(y)->_left == y |
780 | || get_parent(y)->_right == y); | |
781 | assert(x == rbtree->root || get_parent(x)->_left == x | |
782 | || get_parent(x)->_right == x); | |
8ded5fe9 MD |
783 | assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x); |
784 | assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x); | |
785 | assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y); | |
786 | assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y); | |
269a9ef6 MD |
787 | assert(!is_decay(rbtree->root)); |
788 | assert(!is_decay(x)); | |
789 | assert(!is_decay(y)); | |
dca45c9f MD |
790 | assert(!is_decay(x->_right)); |
791 | assert(!is_decay(x->_left)); | |
792 | assert(!is_decay(y->_right)); | |
793 | assert(!is_decay(y->_left)); | |
66b64c35 MD |
794 | check_max_end(rbtree, get_parent(y)); |
795 | check_max_end(rbtree, x); | |
796 | check_max_end(rbtree, y); | |
dff86257 MD |
797 | } |
798 | ||
dbe4ae98 MD |
799 | #else |
800 | ||
801 | /* non-rcu version */ | |
802 | static | |
803 | void left_rotate(struct rcu_rbtree *rbtree, | |
804 | struct rcu_rbtree_node *x) | |
805 | { | |
806 | struct rcu_rbtree_node *y; | |
807 | ||
230dd288 | 808 | lock_test_mutex(); |
dca45c9f MD |
809 | y = x->_right; |
810 | x->_right = y->_left; | |
8ded5fe9 | 811 | if (!rcu_rbtree_is_nil(rbtree, y->_left)) |
dca45c9f | 812 | set_parent(y->_left, x, IS_RIGHT); |
7ba89e62 | 813 | set_parent(y, get_parent(x), get_pos(x)); |
8ded5fe9 | 814 | if (rcu_rbtree_is_nil(rbtree, get_parent(x))) |
dbe4ae98 | 815 | rbtree->root = y; |
dca45c9f MD |
816 | else if (x == get_parent(x)->_left) { |
817 | get_parent(x)->_left = y; | |
dbe4ae98 | 818 | } else { |
dca45c9f | 819 | get_parent(x)->_right = y; |
dbe4ae98 | 820 | } |
dca45c9f | 821 | y->_left = x; |
7ba89e62 | 822 | set_parent(x, y, IS_LEFT); |
1444707c MD |
823 | |
824 | /* | |
825 | * We only changed the relative position of x and y wrt their | |
826 | * children, and reparented y (but are keeping the same nodes in | |
827 | * place, so its parent does not need to have end value | |
828 | * recalculated). | |
829 | */ | |
830 | x->max_end = calculate_node_max_end(rbtree, x); | |
831 | y->max_end = calculate_node_max_end(rbtree, y); | |
832 | ||
230dd288 | 833 | unlock_test_mutex(); |
dbe4ae98 MD |
834 | } |
835 | ||
836 | #endif | |
837 | ||
838 | #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT | |
dff86257 | 839 | static |
269a9ef6 MD |
840 | void right_rotate(struct rcu_rbtree *rbtree, |
841 | struct rcu_rbtree_node *x) | |
dff86257 | 842 | { |
a84e8c8e | 843 | struct rcu_rbtree_node *y, *y_right; |
dff86257 | 844 | |
66b64c35 MD |
845 | dbg_printf("right rotate %lx\n", (unsigned long) x->begin); |
846 | ||
dca45c9f MD |
847 | y = x->_left; |
848 | y_right = y->_right; | |
269a9ef6 MD |
849 | |
850 | /* Now operate on new copy, decay old versions */ | |
dbe4ae98 MD |
851 | x = dup_decay_node(rbtree, x); |
852 | y = dup_decay_node(rbtree, y); | |
853 | y_right = dup_decay_node(rbtree, y_right); | |
269a9ef6 | 854 | |
66b64c35 MD |
855 | check_max_end(rbtree, get_parent(x)); |
856 | check_max_end(rbtree, x); | |
857 | check_max_end(rbtree, y); | |
858 | ||
676dd8b6 | 859 | /* Internal node modifications */ |
7ba89e62 MD |
860 | set_parent(y, get_parent(x), get_pos(x)); |
861 | set_parent(x, y, IS_RIGHT); | |
a84e8c8e MD |
862 | set_right(rbtree, y, x); |
863 | set_left(rbtree, x, y_right); | |
dca45c9f | 864 | |
8ded5fe9 | 865 | if (!rcu_rbtree_is_nil(rbtree, y_right)) |
7ba89e62 | 866 | set_parent(y_right, x, IS_LEFT); |
676dd8b6 | 867 | |
fda7316a MD |
868 | /* |
869 | * We only changed the relative position of x and y wrt their | |
870 | * children, and reparented y (but are keeping the same nodes in | |
871 | * place, so its parent does not need to have end value | |
872 | * recalculated). | |
873 | */ | |
874 | x->max_end = calculate_node_max_end(rbtree, x); | |
875 | y->max_end = calculate_node_max_end(rbtree, y); | |
876 | ||
21b35829 | 877 | c_cmm_smp_wmb(); /* write into node before publish */ |
676dd8b6 MD |
878 | |
879 | /* External references update (visible by readers) */ | |
a84e8c8e | 880 | if (rcu_rbtree_is_nil(rbtree, get_parent(y))) |
21b35829 | 881 | C__CMM_STORE_SHARED(rbtree->root, y); |
a84e8c8e | 882 | else if (get_pos(y) == IS_RIGHT) |
21b35829 | 883 | C__CMM_STORE_SHARED(get_parent(y)->_right, y); |
676dd8b6 | 884 | else |
21b35829 | 885 | C__CMM_STORE_SHARED(get_parent(y)->_left, y); |
676dd8b6 | 886 | |
dbe4ae98 | 887 | /* Point children to new copy (parent only used by updates/next/prev) */ |
dca45c9f MD |
888 | set_parent(x->_right, get_decay(get_parent(x->_right)), |
889 | get_pos(x->_right)); | |
890 | set_parent(y->_left, get_decay(get_parent(y->_left)), | |
891 | get_pos(y->_left)); | |
8ded5fe9 | 892 | if (!rcu_rbtree_is_nil(rbtree, y_right)) { |
dca45c9f MD |
893 | set_parent(y_right->_left, |
894 | get_decay(get_parent(y_right->_left)), | |
895 | get_pos(y_right->_left)); | |
896 | set_parent(y_right->_right, | |
897 | get_decay(get_parent(y_right->_right)), | |
898 | get_pos(y_right->_right)); | |
dbe4ae98 | 899 | } |
269a9ef6 MD |
900 | |
901 | /* Sanity checks */ | |
dca45c9f MD |
902 | assert(y == rbtree->root || get_parent(y)->_right == y |
903 | || get_parent(y)->_left == y); | |
904 | assert(x == rbtree->root || get_parent(x)->_right == x | |
905 | || get_parent(x)->_left == x); | |
8ded5fe9 MD |
906 | assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x); |
907 | assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x); | |
908 | assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y); | |
909 | assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y); | |
269a9ef6 MD |
910 | assert(!is_decay(rbtree->root)); |
911 | assert(!is_decay(x)); | |
912 | assert(!is_decay(y)); | |
dca45c9f MD |
913 | assert(!is_decay(x->_left)); |
914 | assert(!is_decay(x->_right)); | |
915 | assert(!is_decay(y->_left)); | |
916 | assert(!is_decay(y->_right)); | |
66b64c35 MD |
917 | check_max_end(rbtree, x); |
918 | check_max_end(rbtree, y); | |
919 | check_max_end(rbtree, get_parent(y)); | |
dff86257 MD |
920 | } |
921 | ||
6daf6090 MD |
922 | #else |
923 | ||
dbe4ae98 | 924 | /* non-rcu version */ |
6daf6090 MD |
925 | static |
926 | void right_rotate(struct rcu_rbtree *rbtree, | |
927 | struct rcu_rbtree_node *x) | |
928 | { | |
929 | struct rcu_rbtree_node *y; | |
930 | ||
230dd288 | 931 | lock_test_mutex(); |
dca45c9f MD |
932 | y = x->_left; |
933 | x->_left = y->_right; | |
8ded5fe9 | 934 | if (!rcu_rbtree_is_nil(rbtree, y->_right)) |
dca45c9f | 935 | set_parent(y->_right, x, IS_LEFT); |
7ba89e62 | 936 | set_parent(y, get_parent(x), get_pos(x)); |
8ded5fe9 | 937 | if (rcu_rbtree_is_nil(rbtree, get_parent(x))) |
6daf6090 | 938 | rbtree->root = y; |
dca45c9f MD |
939 | else if (x == get_parent(x)->_right) { |
940 | get_parent(x)->_right = y; | |
6daf6090 | 941 | } else { |
dca45c9f | 942 | get_parent(x)->_left = y; |
6daf6090 | 943 | } |
dca45c9f | 944 | y->_right = x; |
7ba89e62 | 945 | set_parent(x, y, IS_RIGHT); |
1444707c MD |
946 | |
947 | /* | |
948 | * We only changed the relative position of x and y wrt their | |
949 | * children, and reparented y (but are keeping the same nodes in | |
950 | * place, so its parent does not need to have end value | |
951 | * recalculated). | |
952 | */ | |
953 | x->max_end = calculate_node_max_end(rbtree, x); | |
954 | y->max_end = calculate_node_max_end(rbtree, y); | |
955 | ||
230dd288 | 956 | unlock_test_mutex(); |
6daf6090 MD |
957 | } |
958 | ||
959 | #endif | |
960 | ||
dff86257 MD |
961 | static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree, |
962 | struct rcu_rbtree_node *z) | |
963 | { | |
964 | struct rcu_rbtree_node *y; | |
965 | ||
3366b9c0 | 966 | dbg_printf("insert fixup %p\n", z->begin); |
269a9ef6 | 967 | assert(!is_decay(rbtree->root)); |
dff86257 | 968 | |
7ba89e62 | 969 | while (get_parent(z)->color == COLOR_RED) { |
dca45c9f MD |
970 | if (get_parent(z) == get_parent(get_parent(z))->_left) { |
971 | y = get_parent(get_parent(z))->_right; | |
dff86257 | 972 | if (y->color == COLOR_RED) { |
7ba89e62 | 973 | get_parent(z)->color = COLOR_BLACK; |
dff86257 | 974 | y->color = COLOR_BLACK; |
7ba89e62 MD |
975 | get_parent(get_parent(z))->color = COLOR_RED; |
976 | z = get_parent(get_parent(z)); | |
dff86257 | 977 | } else { |
dca45c9f | 978 | if (z == get_parent(z)->_right) { |
7ba89e62 | 979 | z = get_parent(z); |
dff86257 | 980 | left_rotate(rbtree, z); |
269a9ef6 MD |
981 | z = get_decay(z); |
982 | assert(!is_decay(rbtree->root)); | |
dff86257 | 983 | } |
7ba89e62 MD |
984 | get_parent(z)->color = COLOR_BLACK; |
985 | get_parent(get_parent(z))->color = COLOR_RED; | |
269a9ef6 | 986 | assert(!is_decay(z)); |
7ba89e62 MD |
987 | assert(!is_decay(get_parent(z))); |
988 | assert(!is_decay(get_parent(get_parent(z)))); | |
989 | right_rotate(rbtree, get_parent(get_parent(z))); | |
269a9ef6 MD |
990 | assert(!is_decay(z)); |
991 | assert(!is_decay(rbtree->root)); | |
dff86257 MD |
992 | } |
993 | } else { | |
dca45c9f | 994 | y = get_parent(get_parent(z))->_left; |
dff86257 | 995 | if (y->color == COLOR_RED) { |
7ba89e62 | 996 | get_parent(z)->color = COLOR_BLACK; |
dff86257 | 997 | y->color = COLOR_BLACK; |
7ba89e62 MD |
998 | get_parent(get_parent(z))->color = COLOR_RED; |
999 | z = get_parent(get_parent(z)); | |
dff86257 | 1000 | } else { |
dca45c9f | 1001 | if (z == get_parent(z)->_left) { |
7ba89e62 | 1002 | z = get_parent(z); |
dff86257 | 1003 | right_rotate(rbtree, z); |
269a9ef6 MD |
1004 | z = get_decay(z); |
1005 | assert(!is_decay(rbtree->root)); | |
dff86257 | 1006 | } |
7ba89e62 MD |
1007 | get_parent(z)->color = COLOR_BLACK; |
1008 | get_parent(get_parent(z))->color = COLOR_RED; | |
1009 | left_rotate(rbtree, get_parent(get_parent(z))); | |
269a9ef6 MD |
1010 | assert(!is_decay(z)); |
1011 | assert(!is_decay(rbtree->root)); | |
dff86257 MD |
1012 | } |
1013 | } | |
1014 | } | |
1015 | rbtree->root->color = COLOR_BLACK; | |
1016 | } | |
1017 | ||
1018 | /* | |
1019 | * rcu_rbtree_insert - Insert a node in the RCU rbtree | |
1020 | * | |
1021 | * Returns 0 on success, or < 0 on error. | |
1022 | */ | |
1023 | int rcu_rbtree_insert(struct rcu_rbtree *rbtree, | |
3c672595 | 1024 | void *begin, void *end) |
dff86257 | 1025 | { |
3c672595 MD |
1026 | struct rcu_rbtree_node *x, *y, *z; |
1027 | ||
8f354bc4 MD |
1028 | z = _rcu_rbtree_alloc_node(rbtree); |
1029 | if (!z) | |
1030 | return -ENOMEM; | |
3c672595 MD |
1031 | z->begin = begin; |
1032 | z->end = end; | |
dff86257 | 1033 | |
3366b9c0 | 1034 | dbg_printf("insert %p\n", z->begin); |
269a9ef6 | 1035 | assert(!is_decay(rbtree->root)); |
dff86257 MD |
1036 | |
1037 | y = make_nil(rbtree); | |
dff86257 | 1038 | x = rbtree->root; |
8ded5fe9 | 1039 | while (!rcu_rbtree_is_nil(rbtree, x)) { |
dff86257 | 1040 | y = x; |
3366b9c0 | 1041 | if (rbtree->comp(z->begin, x->begin) < 0) |
dca45c9f | 1042 | x = x->_left; |
dff86257 | 1043 | else |
dca45c9f | 1044 | x = x->_right; |
dff86257 MD |
1045 | } |
1046 | ||
dca45c9f MD |
1047 | z->_left = make_nil(rbtree); |
1048 | z->_right = make_nil(rbtree); | |
dff86257 | 1049 | z->color = COLOR_RED; |
269a9ef6 | 1050 | z->decay_next = NULL; |
55b5e812 | 1051 | z->max_end = z->end; |
3c672595 | 1052 | z->rbtree = rbtree; |
dff86257 | 1053 | |
8ded5fe9 | 1054 | if (rcu_rbtree_is_nil(rbtree, y)) { |
7bc64d1d | 1055 | set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */ |
0bd215cc MD |
1056 | /* |
1057 | * Order stores to z (children/parents) before stores | |
1058 | * that will make it visible to the rest of the tree. | |
1059 | */ | |
21b35829 MD |
1060 | c_cmm_smp_wmb(); |
1061 | C__CMM_STORE_SHARED(rbtree->root, z); | |
3366b9c0 | 1062 | } else if (rbtree->comp(z->begin, y->begin) < 0) { |
7bc64d1d MD |
1063 | y = dup_decay_node(rbtree, y); |
1064 | set_parent(z, y, IS_LEFT); | |
1065 | if (get_pos(z) == IS_LEFT) | |
21b35829 | 1066 | C__CMM_STORE_SHARED(y->_left, z); |
dca45c9f | 1067 | else |
21b35829 | 1068 | C__CMM_STORE_SHARED(y->_right, z); |
fcb4eea8 | 1069 | populate_node_end(rbtree, y, 1, NULL); |
dca45c9f | 1070 | } else { |
7bc64d1d MD |
1071 | y = dup_decay_node(rbtree, y); |
1072 | set_parent(z, y, IS_RIGHT); | |
1073 | if (get_pos(z) == IS_LEFT) | |
21b35829 | 1074 | C__CMM_STORE_SHARED(y->_left, z); |
dca45c9f | 1075 | else |
21b35829 | 1076 | C__CMM_STORE_SHARED(y->_right, z); |
fcb4eea8 | 1077 | populate_node_end(rbtree, y, 1, NULL); |
dca45c9f | 1078 | } |
dff86257 MD |
1079 | rcu_rbtree_insert_fixup(rbtree, z); |
1080 | /* | |
21b35829 | 1081 | * Make sure to commit all C__CMM_STORE_SHARED() for non-coherent caches. |
dff86257 | 1082 | */ |
21b35829 | 1083 | c_cmm_smp_wmc(); |
dff86257 | 1084 | show_tree(rbtree); |
66b64c35 MD |
1085 | check_max_end(rbtree, z); |
1086 | check_max_end(rbtree, y); | |
dff86257 MD |
1087 | |
1088 | return 0; | |
1089 | } | |
1090 | ||
1091 | /* | |
1092 | * Transplant v into u position. | |
dff86257 | 1093 | */ |
6daf6090 MD |
1094 | |
1095 | #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT | |
1096 | ||
269a9ef6 MD |
1097 | static |
1098 | void rcu_rbtree_transplant(struct rcu_rbtree *rbtree, | |
1099 | struct rcu_rbtree_node *u, | |
dca45c9f | 1100 | struct rcu_rbtree_node *v, |
fcb4eea8 MD |
1101 | unsigned int copy_parents, |
1102 | struct rcu_rbtree_node *stop) | |
dff86257 | 1103 | { |
3366b9c0 | 1104 | dbg_printf("transplant %p\n", v->begin); |
dff86257 | 1105 | |
8ded5fe9 | 1106 | if (!rcu_rbtree_is_nil(rbtree, v)) |
dbe4ae98 | 1107 | v = dup_decay_node(rbtree, v); |
c479601c | 1108 | |
8ded5fe9 | 1109 | if (rcu_rbtree_is_nil(rbtree, get_parent(u))) { |
7ba89e62 MD |
1110 | /* pos is arbitrary for root node */ |
1111 | set_parent(v, get_parent(u), IS_RIGHT); | |
21b35829 MD |
1112 | c_cmm_smp_wmb(); /* write into node before publish */ |
1113 | C__CMM_STORE_SHARED(rbtree->root, v); | |
dff86257 | 1114 | } else { |
fcb4eea8 MD |
1115 | struct rcu_rbtree_node *vp; |
1116 | ||
1117 | vp = get_parent(u); | |
1118 | if (copy_parents) | |
1119 | vp = dup_decay_node(rbtree, vp); | |
1120 | set_parent(v, vp, get_pos(u)); | |
1121 | if (get_pos(v) == IS_LEFT) | |
21b35829 | 1122 | C__CMM_STORE_SHARED(vp->_left, v); |
806967f3 | 1123 | else |
21b35829 | 1124 | C__CMM_STORE_SHARED(vp->_right, v); |
fcb4eea8 | 1125 | populate_node_end(rbtree, vp, copy_parents, stop); |
66b64c35 | 1126 | check_max_end(rbtree, vp); |
c479601c | 1127 | } |
806967f3 | 1128 | |
dbe4ae98 | 1129 | /* Point children to new copy (parent only used by updates/next/prev) */ |
8ded5fe9 | 1130 | if (!rcu_rbtree_is_nil(rbtree, v)) { |
dca45c9f MD |
1131 | set_parent(v->_right, get_decay(get_parent(v->_right)), |
1132 | get_pos(v->_right)); | |
1133 | set_parent(v->_left, get_decay(get_parent(v->_left)), | |
1134 | get_pos(v->_left)); | |
dff86257 | 1135 | } |
269a9ef6 | 1136 | assert(!is_decay(rbtree->root)); |
66b64c35 | 1137 | check_max_end(rbtree, v); |
dff86257 MD |
1138 | } |
1139 | ||
6daf6090 MD |
1140 | #else |
1141 | ||
1142 | /* Non-RCU version */ | |
1143 | static | |
1144 | void rcu_rbtree_transplant(struct rcu_rbtree *rbtree, | |
1145 | struct rcu_rbtree_node *u, | |
dca45c9f | 1146 | struct rcu_rbtree_node *v, |
fcb4eea8 MD |
1147 | unsigned int copy_parents, |
1148 | struct rcu_rbtree_node *stop) | |
6daf6090 | 1149 | { |
3366b9c0 | 1150 | dbg_printf("transplant %p\n", v->begin); |
6daf6090 | 1151 | |
230dd288 | 1152 | lock_test_mutex(); |
1444707c | 1153 | if (rcu_rbtree_is_nil(rbtree, get_parent(u))) { |
6daf6090 | 1154 | rbtree->root = v; |
1444707c MD |
1155 | } else { |
1156 | if (u == get_parent(u)->_left) | |
1157 | get_parent(u)->_left = v; | |
1158 | else | |
1159 | get_parent(u)->_right = v; | |
1160 | populate_node_end(rbtree, get_parent(u), copy_parents, stop); | |
1161 | } | |
7ba89e62 | 1162 | set_parent(v, get_parent(u), get_pos(u)); |
230dd288 | 1163 | unlock_test_mutex(); |
6daf6090 MD |
1164 | } |
1165 | ||
1166 | #endif | |
1167 | ||
dff86257 MD |
1168 | static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree, |
1169 | struct rcu_rbtree_node *x) | |
1170 | { | |
3366b9c0 | 1171 | dbg_printf("remove fixup %p\n", x->begin); |
dff86257 MD |
1172 | |
1173 | while (x != rbtree->root && x->color == COLOR_BLACK) { | |
7ba89e62 | 1174 | assert(!is_decay(get_parent(x))); |
dca45c9f MD |
1175 | assert(!is_decay(get_parent(x)->_left)); |
1176 | if (x == get_parent(x)->_left) { | |
269a9ef6 | 1177 | struct rcu_rbtree_node *w; |
dff86257 | 1178 | |
dca45c9f | 1179 | w = get_parent(x)->_right; |
dff86257 MD |
1180 | |
1181 | if (w->color == COLOR_RED) { | |
269a9ef6 | 1182 | w->color = COLOR_BLACK; |
7ba89e62 MD |
1183 | get_parent(x)->color = COLOR_RED; |
1184 | left_rotate(rbtree, get_parent(x)); | |
269a9ef6 MD |
1185 | x = get_decay(x); |
1186 | assert(!is_decay(rbtree->root)); | |
dca45c9f | 1187 | w = get_parent(x)->_right; |
dff86257 | 1188 | } |
dca45c9f MD |
1189 | if (w->_left->color == COLOR_BLACK |
1190 | && w->_right->color == COLOR_BLACK) { | |
dff86257 | 1191 | w->color = COLOR_RED; |
7ba89e62 | 1192 | x = get_parent(x); |
c479601c MD |
1193 | assert(!is_decay(rbtree->root)); |
1194 | assert(!is_decay(x)); | |
dff86257 | 1195 | } else { |
dca45c9f MD |
1196 | if (w->_right->color == COLOR_BLACK) { |
1197 | w->_left->color = COLOR_BLACK; | |
dff86257 MD |
1198 | w->color = COLOR_RED; |
1199 | right_rotate(rbtree, w); | |
c479601c | 1200 | assert(!is_decay(rbtree->root)); |
269a9ef6 | 1201 | x = get_decay(x); |
dca45c9f | 1202 | w = get_parent(x)->_right; |
dff86257 | 1203 | } |
7ba89e62 MD |
1204 | w->color = get_parent(x)->color; |
1205 | get_parent(x)->color = COLOR_BLACK; | |
dca45c9f | 1206 | w->_right->color = COLOR_BLACK; |
7ba89e62 | 1207 | left_rotate(rbtree, get_parent(x)); |
269a9ef6 | 1208 | assert(!is_decay(rbtree->root)); |
dff86257 MD |
1209 | x = rbtree->root; |
1210 | } | |
1211 | } else { | |
269a9ef6 | 1212 | struct rcu_rbtree_node *w; |
dff86257 | 1213 | |
dca45c9f | 1214 | w = get_parent(x)->_left; |
dff86257 MD |
1215 | |
1216 | if (w->color == COLOR_RED) { | |
269a9ef6 | 1217 | w->color = COLOR_BLACK; |
7ba89e62 MD |
1218 | get_parent(x)->color = COLOR_RED; |
1219 | right_rotate(rbtree, get_parent(x)); | |
c479601c | 1220 | assert(!is_decay(rbtree->root)); |
269a9ef6 | 1221 | x = get_decay(x); |
dca45c9f | 1222 | w = get_parent(x)->_left; |
dff86257 | 1223 | } |
dca45c9f MD |
1224 | if (w->_right->color == COLOR_BLACK |
1225 | && w->_left->color == COLOR_BLACK) { | |
dff86257 | 1226 | w->color = COLOR_RED; |
7ba89e62 | 1227 | x = get_parent(x); |
c479601c MD |
1228 | assert(!is_decay(rbtree->root)); |
1229 | assert(!is_decay(x)); | |
dff86257 | 1230 | } else { |
dca45c9f MD |
1231 | if (w->_left->color == COLOR_BLACK) { |
1232 | w->_right->color = COLOR_BLACK; | |
dff86257 MD |
1233 | w->color = COLOR_RED; |
1234 | left_rotate(rbtree, w); | |
269a9ef6 MD |
1235 | assert(!is_decay(rbtree->root)); |
1236 | x = get_decay(x); | |
dca45c9f | 1237 | w = get_parent(x)->_left; |
dff86257 | 1238 | } |
7ba89e62 MD |
1239 | w->color = get_parent(x)->color; |
1240 | get_parent(x)->color = COLOR_BLACK; | |
dca45c9f | 1241 | w->_left->color = COLOR_BLACK; |
7ba89e62 | 1242 | right_rotate(rbtree, get_parent(x)); |
c479601c | 1243 | assert(!is_decay(rbtree->root)); |
dff86257 MD |
1244 | x = rbtree->root; |
1245 | } | |
1246 | } | |
1247 | } | |
1248 | x->color = COLOR_BLACK; | |
1249 | } | |
1250 | ||
1251 | /* | |
269a9ef6 MD |
1252 | * Delete z. All non-copied children left/right positions are unchanged. |
1253 | */ | |
1254 | static | |
1255 | void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree, | |
1256 | struct rcu_rbtree_node *z, | |
1257 | struct rcu_rbtree_node *y) | |
dff86257 | 1258 | { |
a84e8c8e | 1259 | struct rcu_rbtree_node *x; |
dff86257 | 1260 | |
3366b9c0 | 1261 | dbg_printf("remove nonil %p\n", z->begin); |
dff86257 MD |
1262 | show_tree(rbtree); |
1263 | ||
c479601c MD |
1264 | assert(!is_decay(z)); |
1265 | assert(!is_decay(y)); | |
dca45c9f | 1266 | assert(!is_decay(y->_right)); |
7ba89e62 | 1267 | assert(!is_decay(get_parent(y))); |
dca45c9f | 1268 | x = y->_right; |
c479601c | 1269 | assert(!is_decay(x)); |
7ba89e62 | 1270 | if (get_parent(y) == z) { |
230dd288 | 1271 | y = dup_decay_node(rbtree, y); |
7ba89e62 | 1272 | set_parent(x, y, get_pos(x)); /* parent for nil */ |
66b64c35 | 1273 | /* y is z's right node */ |
a84e8c8e | 1274 | set_left(rbtree, y, z->_left); |
66b64c35 | 1275 | y->max_end = calculate_node_max_end(rbtree, y); |
fcb4eea8 | 1276 | rcu_rbtree_transplant(rbtree, z, y, 1, NULL); |
230dd288 MD |
1277 | } else { |
1278 | struct rcu_rbtree_node *oy_right, *z_right; | |
1279 | ||
1280 | /* | |
1281 | * Need to make sure y is always visible by readers. | |
1282 | */ | |
dca45c9f | 1283 | y = rcu_rbtree_min_dup_decay(rbtree, z->_right, &z_right); |
269a9ef6 MD |
1284 | assert(!is_decay(y)); |
1285 | assert(!is_decay(z)); | |
dca45c9f MD |
1286 | oy_right = y->_right; |
1287 | ||
1288 | /* | |
3366b9c0 | 1289 | * The max child begin of z_right does not change, because |
dca45c9f MD |
1290 | * we're only changing its left children. |
1291 | */ | |
1292 | y->_right = z_right; | |
1293 | set_parent(y->_right, y, IS_RIGHT); | |
dca45c9f MD |
1294 | assert(!is_decay(z->_left)); |
1295 | y->_left = z->_left; | |
230dd288 | 1296 | assert(!is_decay(oy_right)); |
dca45c9f MD |
1297 | /* |
1298 | * Transplant of oy_right to old y's location will only | |
fcb4eea8 | 1299 | * trigger a "end" value update of the already copied branch |
dca45c9f MD |
1300 | * (which is not visible yet). We are transplanting |
1301 | * oy_right as a left child of old y's parent, so the | |
1302 | * min values update propagated upward necessarily stops | |
1303 | * at z_right. | |
1304 | */ | |
fcb4eea8 | 1305 | rcu_rbtree_transplant(rbtree, y, oy_right, 0, y); |
66b64c35 | 1306 | y->max_end = calculate_node_max_end(rbtree, y); |
fcb4eea8 | 1307 | rcu_rbtree_transplant(rbtree, z, y, 1, NULL); |
230dd288 | 1308 | /* Update children */ |
dca45c9f | 1309 | (void) rcu_rbtree_min_update_decay(rbtree, y->_right); |
dff86257 | 1310 | } |
c479601c | 1311 | y = get_decay(y); |
269a9ef6 | 1312 | assert(!is_decay(z)); |
dca45c9f | 1313 | assert(!is_decay(z->_left)); |
dff86257 | 1314 | y->color = z->color; |
dca45c9f MD |
1315 | set_parent(y->_left, y, IS_LEFT); |
1316 | set_parent(y->_right, get_decay(get_parent(y->_right)), IS_RIGHT); | |
1317 | assert(!is_decay(y->_left)); | |
1318 | assert(!is_decay(y->_right)); | |
dff86257 MD |
1319 | } |
1320 | ||
1321 | int rcu_rbtree_remove(struct rcu_rbtree *rbtree, | |
1322 | struct rcu_rbtree_node *z) | |
1323 | { | |
1324 | struct rcu_rbtree_node *x, *y; | |
1325 | unsigned int y_original_color; | |
1326 | ||
269a9ef6 | 1327 | assert(!is_decay(rbtree->root)); |
3366b9c0 | 1328 | dbg_printf("remove %p\n", z->begin); |
dff86257 MD |
1329 | show_tree(rbtree); |
1330 | ||
c479601c | 1331 | assert(!is_decay(z)); |
dff86257 MD |
1332 | y = z; |
1333 | y_original_color = y->color; | |
1334 | ||
8ded5fe9 | 1335 | if (rcu_rbtree_is_nil(rbtree, z->_left)) { |
fcb4eea8 | 1336 | rcu_rbtree_transplant(rbtree, z, z->_right, 1, NULL); |
269a9ef6 | 1337 | assert(!is_decay(z)); |
dca45c9f | 1338 | x = get_decay(z->_right); |
dff86257 | 1339 | show_tree(rbtree); |
8ded5fe9 | 1340 | } else if (rcu_rbtree_is_nil(rbtree, z->_right)) { |
fcb4eea8 | 1341 | rcu_rbtree_transplant(rbtree, z, z->_left, 1, NULL); |
269a9ef6 | 1342 | assert(!is_decay(z)); |
dca45c9f | 1343 | x = get_decay(z->_left); |
dff86257 MD |
1344 | show_tree(rbtree); |
1345 | } else { | |
dca45c9f | 1346 | y = rcu_rbtree_min(rbtree, z->_right); |
c479601c | 1347 | assert(!is_decay(y)); |
dff86257 | 1348 | y_original_color = y->color; |
dca45c9f | 1349 | x = y->_right; |
269a9ef6 | 1350 | rcu_rbtree_remove_nonil(rbtree, z, y); |
6daf6090 | 1351 | x = get_decay(x); |
dff86257 MD |
1352 | show_tree(rbtree); |
1353 | } | |
1354 | if (y_original_color == COLOR_BLACK) | |
1355 | rcu_rbtree_remove_fixup(rbtree, x); | |
1356 | show_tree(rbtree); | |
66b64c35 MD |
1357 | check_max_end(rbtree, x); |
1358 | check_max_end(rbtree, get_decay(y)); | |
dff86257 | 1359 | /* |
21b35829 | 1360 | * Commit all C__CMM_STORE_SHARED(). |
dff86257 | 1361 | */ |
21b35829 | 1362 | c_cmm_smp_wmc(); |
c2ceb27c | 1363 | #ifdef RBTREE_RCU_SUPPORT |
1cdd423d | 1364 | rbtree->call_rcu(&z->head, _rcu_rbtree_free_node); |
c2ceb27c MD |
1365 | #else |
1366 | _rcu_rbtree_free_node(&z->head); | |
1367 | #endif | |
dff86257 MD |
1368 | |
1369 | return 0; | |
1370 | } |