afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / rb_stm.c
1 /******************************************************************************
2  * rb_stm.c
3  *
4  * Lock-free red-black trees, based on STM.
5  *
6  * Copyright (c) 2002-2003, K A Fraser
7  *
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are
10 met:
11
12     * Redistributions of source code must retain the above copyright
13     * notice, this list of conditions and the following disclaimer.
14     * Redistributions in binary form must reproduce the above
15     * copyright notice, this list of conditions and the following
16     * disclaimer in the documentation and/or other materials provided
17     * with the distribution.  Neither the name of the Keir Fraser
18     * nor the names of its contributors may be used to endorse or
19     * promote products derived from this software without specific
20     * prior written permission.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33  */
34
35 #define __SET_IMPLEMENTATION__
36
37 #include <stdio.h>
38 #include <assert.h>
39 #include <stdlib.h>
40 #include <unistd.h>
41 #include "portable_defns.h"
42 #include "gc.h"
43 #include "stm.h"
44 #include "set.h"
45
46 #define IS_BLACK(_v)   ((int_addr_t)(_v)&1)
47 #define IS_RED(_v)     (!IS_BLACK(_v))
48 #define MK_BLACK(_v)   ((setval_t)((int_addr_t)(_v)|1))
49 #define MK_RED(_v)     ((setval_t)((int_addr_t)(_v)&~1))
50 #define GET_VALUE(_v)  (MK_RED(_v))
51 #define GET_COLOUR(_v) (IS_BLACK(_v))
52 #define SET_COLOUR(_v,_c) ((setval_t)((unsigned long)(_v)|(unsigned long)(_c)))
53
54 typedef struct node_st node_t;
55 typedef stm_blk set_t;
56
57 struct node_st
58 {
59     setkey_t k;
60     setval_t v;
61     stm_blk *l, *r, *p;
62 };
63
64 static struct {
65     CACHE_PAD(0);
66     stm *memory;    /* read-only */
67     stm_blk *nullb; /* read-only */
68     CACHE_PAD(2);
69 } shared;
70
71 #define MEMORY (shared.memory)
72 #define NULLB  (shared.nullb)
73
74 static void left_rotate(ptst_t *ptst, stm_tx *tx, stm_blk *xb, node_t *x)
75 {
76     stm_blk *yb, *pb;
77     node_t *y, *p;
78
79     yb = x->r;
80     pb = x->p;
81
82     y = write_stm_blk(ptst, tx, yb);
83     p = write_stm_blk(ptst, tx, pb);
84
85     if ( (x->r = y->l) != NULLB )
86     {
87         node_t *xr = write_stm_blk(ptst, tx, x->r);
88         xr->p = xb;
89     }
90
91     x->p = yb;
92     y->l = xb;
93     y->p = pb;
94     if ( xb == p->l ) p->l = yb; else p->r = yb;
95 }
96
97
98 static void right_rotate(ptst_t *ptst, stm_tx *tx, stm_blk *xb, node_t *x)
99 {
100     stm_blk *yb, *pb;
101     node_t *y, *p;
102
103     yb = x->l;
104     pb = x->p;
105
106     y = write_stm_blk(ptst, tx, yb);
107     p = write_stm_blk(ptst, tx, pb);
108
109     if ( (x->l = y->r) != NULLB )
110     {
111         node_t *xl = write_stm_blk(ptst, tx, x->l);
112         xl->p = xb;
113     }
114
115     x->p = yb;
116     y->r = xb;
117     y->p = pb;
118     if ( xb == p->l ) p->l = yb; else p->r = yb;
119 }
120
121
122 static void delete_fixup(ptst_t *ptst, stm_tx *tx, set_t *s,
123                          stm_blk *xb, node_t *x)
124 {
125     stm_blk *pb, *wb, *wlb, *wrb;
126     node_t *p, *w, *wl, *wr;
127
128     while ( (x->p != s) && IS_BLACK(x->v) )
129     {
130         pb = x->p;
131         p  = write_stm_blk(ptst, tx, pb);
132
133         if ( xb == p->l )
134         {
135             wb = p->r;
136             w  = write_stm_blk(ptst, tx, wb);
137             if ( IS_RED(w->v) )
138             {
139                 w->v = MK_BLACK(w->v);
140                 p->v = MK_RED(p->v);
141                 left_rotate(ptst, tx, pb, p);
142                 wb = p->r;
143                 w  = write_stm_blk(ptst, tx, wb);
144             }
145
146             wlb = w->l;
147             wl  = read_stm_blk(ptst, tx, wlb);
148             wrb = w->r;
149             wr  = read_stm_blk(ptst, tx, wrb);
150             if ( IS_BLACK(wl->v) && IS_BLACK(wr->v) )
151             {
152                 w->v = MK_RED(w->v);
153                 xb = pb;
154                 x  = p;
155             }
156             else
157             {
158                 if ( IS_BLACK(wr->v) )
159                 {
160                     wl = write_stm_blk(ptst, tx, wlb);
161                     wl->v = MK_BLACK(wl->v);
162                     w->v  = MK_RED(w->v);
163                     right_rotate(ptst, tx, wb, w);
164                     wb = p->r;
165                     w  = write_stm_blk(ptst, tx, wb);
166                 }
167
168                 wrb = w->r;
169                 wr  = write_stm_blk(ptst, tx, wrb);
170                 w->v = SET_COLOUR(GET_VALUE(w->v), GET_COLOUR(p->v));
171                 p->v = MK_BLACK(p->v);
172                 wr->v = MK_BLACK(wr->v);
173                 left_rotate(ptst, tx, pb, p);
174                 break;
175             }
176         }
177         else /* SYMMETRIC CASE */
178         {
179             wb = p->l;
180             w  = write_stm_blk(ptst, tx, wb);
181             if ( IS_RED(w->v) )
182             {
183                 w->v = MK_BLACK(w->v);
184                 p->v = MK_RED(p->v);
185                 right_rotate(ptst, tx, pb, p);
186                 wb = p->l;
187                 w  = write_stm_blk(ptst, tx, wb);
188             }
189
190             wlb = w->l;
191             wl  = read_stm_blk(ptst, tx, wlb);
192             wrb = w->r;
193             wr  = read_stm_blk(ptst, tx, wrb);
194             if ( IS_BLACK(wl->v) && IS_BLACK(wr->v) )
195             {
196                 w->v = MK_RED(w->v);
197                 xb = pb;
198                 x  = p;
199             }
200             else
201             {
202                 if ( IS_BLACK(wl->v) )
203                 {
204                     wr = write_stm_blk(ptst, tx, wrb);
205                     wr->v = MK_BLACK(wr->v);
206                     w->v  = MK_RED(w->v);
207                     left_rotate(ptst, tx, wb, w);
208                     wb = p->l;
209                     w  = write_stm_blk(ptst, tx, wb);
210                 }
211
212                 wlb = w->l;
213                 wl  = write_stm_blk(ptst, tx, wlb);
214                 w->v = SET_COLOUR(GET_VALUE(w->v), GET_COLOUR(p->v));
215                 p->v = MK_BLACK(p->v);
216                 wl->v = MK_BLACK(wl->v);
217                 right_rotate(ptst, tx, pb, p);
218                 break;
219             }
220         }
221     }
222
223     x->v = MK_BLACK(x->v);
224 }
225
226
227 set_t *set_alloc(void)
228 {
229     ptst_t *ptst;
230     set_t  *set;
231     node_t *root;
232
233     ptst = critical_enter();
234
235     set = new_stm_blk(ptst, MEMORY);
236
237     root = init_stm_blk(ptst, MEMORY, set);
238     root->k = SENTINEL_KEYMIN;
239     root->v = MK_RED(NULL);
240     root->l = NULLB;
241     root->r = NULLB;
242     root->p = NULL;
243
244     critical_exit(ptst);
245
246     return set;
247 }
248
249
250 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
251 {
252     ptst_t  *ptst;
253     stm_tx  *tx;
254     stm_blk *xb, *b, *pb, *gb, *yb, *newb;
255     node_t  *x, *p, *g, *y, *new;
256     setval_t ov;
257
258     k = CALLER_TO_INTERNAL_KEY(k);
259
260     newb = NULL;
261
262     ptst = critical_enter();
263
264     do {
265         new_stm_tx(tx, ptst, MEMORY);
266
267         b = s;
268         while ( b != NULLB )
269         {
270             xb = b;
271             x = read_stm_blk(ptst, tx, xb);
272             if ( k == x->k ) break;
273             b = (k < x->k) ? x->l : x->r;
274         }
275
276         x = write_stm_blk(ptst, tx, xb);
277
278         if ( k == x->k )
279         {
280             ov = x->v;
281             if ( overwrite ) x->v = SET_COLOUR(v, GET_COLOUR(ov));
282             ov = GET_VALUE(ov);
283         }
284         else
285         {
286             ov = NULL;
287             if ( newb == NULL )
288             {
289                 newb = new_stm_blk(ptst, MEMORY);
290                 new = init_stm_blk(ptst, MEMORY, newb);
291                 new->k = k;
292             }
293
294             new->v = MK_RED(v);
295             new->l = NULLB;
296             new->r = NULLB;
297             new->p = xb;
298
299             if ( k < x->k ) x->l = newb; else x->r = newb;
300
301             xb = newb;
302             x  = new;
303
304             for ( ; ; )
305             {
306                 if ( (pb = x->p) == s )
307                 {
308                     x->v = MK_BLACK(x->v);
309                     break;
310                 }
311
312                 p = read_stm_blk(ptst, tx, pb);
313                 if ( IS_BLACK(p->v) ) break;
314
315                 gb = p->p;
316                 g = read_stm_blk(ptst, tx, gb);
317                 if ( pb == g->l )
318                 {
319                     yb = g->r;
320                     y  = read_stm_blk(ptst, tx, yb);
321                     if ( IS_RED(y->v) )
322                     {
323                         p = write_stm_blk(ptst, tx, pb);
324                         y = write_stm_blk(ptst, tx, yb);
325                         g = write_stm_blk(ptst, tx, gb);
326                         p->v = MK_BLACK(p->v);
327                         y->v = MK_BLACK(y->v);
328                         g->v = MK_RED(g->v);
329                         xb = gb;
330                         x  = g;
331                     }
332                     else
333                     {
334                         if ( xb == p->r )
335                         {
336                             xb = pb;
337                             x  = write_stm_blk(ptst, tx, pb);
338                             left_rotate(ptst, tx, xb, x);
339                         }
340                         pb = x->p;
341                         p  = write_stm_blk(ptst, tx, pb);
342                         gb = p->p;
343                         g  = write_stm_blk(ptst, tx, gb);
344                         p->v = MK_BLACK(p->v);
345                         g->v = MK_RED(g->v);
346                         right_rotate(ptst, tx, gb, g);
347                     }
348                 }
349                 else /* SYMMETRIC CASE */
350                 {
351                     yb = g->l;
352                     y  = read_stm_blk(ptst, tx, yb);
353                     if ( IS_RED(y->v) )
354                     {
355                         p = write_stm_blk(ptst, tx, pb);
356                         y = write_stm_blk(ptst, tx, yb);
357                         g = write_stm_blk(ptst, tx, gb);
358                         p->v = MK_BLACK(p->v);
359                         y->v = MK_BLACK(y->v);
360                         g->v = MK_RED(g->v);
361                         xb = gb;
362                         x  = g;
363                     }
364                     else
365                     {
366                         if ( xb == p->l )
367                         {
368                             xb = pb;
369                             x  = write_stm_blk(ptst, tx, pb);
370                             right_rotate(ptst, tx, xb, x);
371                         }
372                         pb = x->p;
373                         p  = write_stm_blk(ptst, tx, pb);
374                         gb = p->p;
375                         g  = write_stm_blk(ptst, tx, gb);
376                         p->v = MK_BLACK(p->v);
377                         g->v = MK_RED(g->v);
378                         left_rotate(ptst, tx, gb, g);
379                     }
380                 }
381             }
382         }
383
384         remove_from_tx(ptst, tx, NULLB);
385     }
386     while ( !commit_stm_tx(ptst, tx) );
387
388     /* Free unused new block. */
389     if ( (ov != NULL) && (newb != NULL) ) free_stm_blk(ptst, MEMORY, newb);
390
391     critical_exit(ptst);
392
393     return ov;
394 }
395
396
397 setval_t set_remove(set_t *s, setkey_t k)
398 {
399     ptst_t  *ptst;
400     stm_tx  *tx;
401     stm_blk *zb, *b, *xb, *yb;
402     node_t  *z, *x, *y, *yp;
403     setval_t ov;
404
405     k = CALLER_TO_INTERNAL_KEY(k);
406
407     ptst = critical_enter();
408
409     do {
410         new_stm_tx(tx, ptst, MEMORY);
411         ov = NULL;
412         b  = s;
413
414         while ( b != NULLB )
415         {
416             zb = b;
417             z = read_stm_blk(ptst, tx, zb);
418             if ( k == z->k )
419             {
420                 ov = GET_VALUE(z->v);
421                 break;
422             }
423             b = (k < z->k) ? z->l : z->r;
424         }
425
426         if ( ov != NULL )
427         {
428             z = write_stm_blk(ptst, tx, zb);
429
430             if ( (z->l != NULLB) && (z->r != NULLB) )
431             {
432                 /* Find successor of node z, and place in (yb,y). */
433                 yb = z->r;
434                 y  = read_stm_blk(ptst, tx, yb);
435
436                 while ( y->l != NULLB )
437                 {
438                     yb = y->l;
439                     y  = read_stm_blk(ptst, tx, yb);
440                 }
441
442                 y = write_stm_blk(ptst, tx, yb);
443             }
444             else
445             {
446                 yb = zb;
447                 y  = z;
448             }
449
450             xb = (y->l != NULLB) ? y->l : y->r;
451             x = write_stm_blk(ptst, tx, xb);
452             x->p = y->p;
453
454             yp = write_stm_blk(ptst, tx, y->p);
455             if ( yb == yp->l ) yp->l = xb; else yp->r = xb;
456
457             if ( y != z )
458             {
459                 z->k = y->k;
460                 z->v = SET_COLOUR(GET_VALUE(y->v), GET_COLOUR(z->v));
461             }
462
463             if ( IS_BLACK(y->v) ) delete_fixup(ptst, tx, s, xb, x);
464         }
465
466         remove_from_tx(ptst, tx, NULLB);
467     }
468     while ( !commit_stm_tx(ptst, tx) );
469
470     /* Free a deleted block. */
471     if ( ov != NULL ) free_stm_blk(ptst, MEMORY, yb);
472
473     critical_exit(ptst);
474
475     return ov;
476 }
477
478
479 setval_t set_lookup(set_t *s, setkey_t k)
480 {
481     ptst_t  *ptst;
482     stm_tx  *tx;
483     stm_blk *nb;
484     node_t  *n;
485     setval_t v;
486
487     k = CALLER_TO_INTERNAL_KEY(k);
488
489     ptst = critical_enter();
490
491     do {
492         new_stm_tx(tx, ptst, MEMORY);
493         v  = NULL;
494         nb = s;
495
496         while ( nb != NULLB )
497         {
498             n = read_stm_blk(ptst, tx, nb);
499             if ( k == n->k )
500             {
501                 v = GET_VALUE(n->v);
502                 break;
503             }
504             nb = (k < n->k) ? n->l : n->r;
505         }
506     }
507     while ( !commit_stm_tx(ptst, tx) );
508
509     critical_exit(ptst);
510
511     return v;
512 }
513
514
515 void _init_set_subsystem(void)
516 {
517     node_t *null;
518     ptst_t *ptst;
519
520     ptst = critical_enter();
521
522     _init_stm_subsystem(0);
523
524     MEMORY = new_stm(ptst, sizeof(node_t));
525
526     NULLB = new_stm_blk(ptst, MEMORY);
527     null  = init_stm_blk(ptst, MEMORY, NULLB);
528     null->k = 0;
529     null->v = MK_BLACK(NULL);
530     null->l = NULL;
531     null->r = NULL;
532     null->p = NULL;
533
534     critical_exit(ptst);
535 }