afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / bst_lock_kung.c
1 /******************************************************************************
2  * bst_lock_kung.c
3  *
4  * Lock-based binary search trees (BSTs), based on:
5  *  H. T. Kung and Philip L. Lehman.
6  *  "Concurrent manipulation of binary search trees".
7  *  ACM Tranactions on Database Systems, Vol. 5, No. 3, September 1980.
8  *
9  * Copyright (c) 2002-2003, K A Fraser
10
11 Redistribution and use in source and binary forms, with or without
12 modification, are permitted provided that the following conditions are
13 met:
14
15     * Redistributions of source code must retain the above copyright
16     * notice, this list of conditions and the following disclaimer.
17     * Redistributions in binary form must reproduce the above
18     * copyright notice, this list of conditions and the following
19     * disclaimer in the documentation and/or other materials provided
20     * with the distribution.  Neither the name of the Keir Fraser
21     * nor the names of its contributors may be used to endorse or
22     * promote products derived from this software without specific
23     * prior written permission.
24
25 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36  */
37
38 #define __SET_IMPLEMENTATION__
39
40 #include <ucontext.h>
41 #include <signal.h>
42 #include <stdio.h>
43 #include <limits.h>
44 #include <errno.h>
45 #include <stdlib.h>
46 #include <assert.h>
47 #include <sys/types.h>
48 #include <sys/stat.h>
49 #include <fcntl.h>
50 #include <unistd.h>
51 #include <stdarg.h>
52 #include "portable_defns.h"
53 #include "gc.h"
54 #include "set.h"
55
56 #define IS_BLUE(_n)      ((int)(_n)->v & 1)
57 #define MK_BLUE(_n)      ((_n)->v = (setval_t)((unsigned long)(_n)->v | 1))
58
59 #define GET_VALUE(_n) ((setval_t)((unsigned long)(_n)->v & ~1UL))
60
61 #define LEFT  0
62 #define RIGHT 1
63 #define FOLLOW(_n, _d) ((_d) ? (_n)->r : (_n)->l)
64 #define UPDATE(_n, _d, _x) ((_d) ? ((_n)->r = (_x)) : ((_n)->l = (_x)))
65 #define FLIP(_d) ((_d)^1)
66
67 typedef struct node_st node_t;
68 typedef struct set_st set_t;
69
70 struct node_st
71 {
72     setkey_t k;
73     setval_t v;
74     node_t *l, *r, *p;
75     mcs_lock_t lock;
76 };
77
78 struct set_st
79 {
80     node_t root;
81 };
82
83 static int gc_id;
84
85 #define LOCK(_n, _pqn)   mcs_lock(&(_n)->lock, (_pqn))
86 #define UNLOCK(_n, _pqn) mcs_unlock(&(_n)->lock, (_pqn))
87
88
89 static node_t *weak_find(node_t *n, setkey_t k)
90 {
91     while ( n != NULL )
92     {
93         if ( n->k < k )
94             n = n->r;
95         else if ( n->k > k )
96             n = n->l;
97         else
98             break;
99     }
100     return n;
101 }
102
103
104 static node_t *find(node_t *n, setkey_t k, qnode_t *qn, int *pdir)
105 {
106     int dir;
107     node_t *f, *s;
108
109     s = n;
110
111     do {
112         f = s;
113     retry:
114         if ( k < f->k )
115         {
116             dir = LEFT;
117             s   = f->l;
118         }
119         else
120         {
121             dir = RIGHT;
122             s   = f->r;
123         }
124     }
125     while ( (s != NULL) && (s->k != k) );
126
127     LOCK(f, qn);
128     if ( IS_BLUE(f) )
129     {
130         UNLOCK(f, qn);
131         f = f->p;
132         goto retry;
133     }
134     if ( s != FOLLOW(f, dir) )
135     {
136         UNLOCK(f, qn);
137         goto retry;
138     }
139
140     *pdir = dir;
141     return f;
142 }
143
144
145 static node_t *rotate(ptst_t *ptst, node_t *a, int dir1,
146                       int dir2, node_t **pc, qnode_t *pqn[])
147 {
148     node_t *b = FOLLOW(a, dir1), *c = FOLLOW(b, dir2);
149     node_t *bp = gc_alloc(ptst, gc_id), *cp = gc_alloc(ptst, gc_id);
150     qnode_t c_qn;
151
152     LOCK(c, &c_qn);
153
154     memcpy(bp, b, sizeof(*b));
155     memcpy(cp, c, sizeof(*c));
156
157     mcs_init(&bp->lock);
158     mcs_init(&cp->lock);
159
160     LOCK(bp, pqn[3]);
161     LOCK(cp, pqn[2]);
162
163     assert(!IS_BLUE(a));
164     assert(!IS_BLUE(b));
165     assert(!IS_BLUE(c));
166
167     UPDATE(cp, FLIP(dir2), bp);
168     UPDATE(bp, dir2,       FOLLOW(c, FLIP(dir2)));
169
170     UPDATE(a, dir1, cp);
171     b->p = a;
172     MK_BLUE(b);
173     c->p = cp;
174     MK_BLUE(c);
175
176     gc_free(ptst, b, gc_id);
177     gc_free(ptst, c, gc_id);
178
179     UNLOCK(a, pqn[0]);
180     UNLOCK(b, pqn[1]);
181     UNLOCK(c, &c_qn);
182
183     *pc = bp;
184     return cp;
185 }
186
187
188 static void _remove(ptst_t *ptst, node_t *a, int dir1, int dir2, qnode_t **pqn)
189 {
190     node_t *b = FOLLOW(a, dir1), *c = FOLLOW(b, dir2);
191     assert(FOLLOW(b, FLIP(dir2)) == NULL);
192     assert(!IS_BLUE(a));
193     assert(!IS_BLUE(b));
194     UPDATE(a, dir1,       c);
195     UPDATE(b, FLIP(dir2), c);
196     b->p = a;
197     MK_BLUE(b);
198     gc_free(ptst, b, gc_id);
199     UNLOCK(a, pqn[0]);
200     UNLOCK(b, pqn[1]);
201 }
202
203
204 static void delete_by_rotation(ptst_t *ptst, node_t *f, int dir,
205                                qnode_t *pqn[], int lock_idx)
206 {
207     node_t *g, *h, *s = FOLLOW(f, dir);
208
209     if ( s->v != NULL )
210     {
211         UNLOCK(f, pqn[lock_idx+0]);
212         UNLOCK(s, pqn[lock_idx+1]);
213         return;
214     }
215
216     if ( s->l == NULL )
217         _remove(ptst, f, dir, RIGHT, pqn+lock_idx);
218     else if ( s->r == NULL )
219         _remove(ptst, f, dir, LEFT, pqn+lock_idx);
220     else
221     {
222         g = rotate(ptst, f, dir, LEFT, &h, pqn+lock_idx);
223         lock_idx ^= 2;
224         if ( h->l == NULL )
225         {
226             assert(h->v == NULL);
227             _remove(ptst, g, RIGHT, RIGHT, pqn+lock_idx);
228         }
229         else
230         {
231             delete_by_rotation(ptst, g, RIGHT, pqn, lock_idx);
232             LOCK(f, pqn[0]);
233             if ( (g != FOLLOW(f, dir)) || IS_BLUE(f) )
234             {
235                 UNLOCK(f, pqn[0]);
236             }
237             else
238             {
239                 LOCK(g, pqn[1]);
240                 /*
241                  * XXX Check that there is a node H to be rotated up.
242                  * This is missing from the original paper, and must surely
243                  * be a bug (we lost all locks at previous delete_by_rotation,
244                  * so we can't know the existence of G's children).
245                  */
246                 if ( g->r != NULL )
247                 {
248                     g = rotate(ptst, f, dir, RIGHT, &h, pqn);
249                     UNLOCK(g, pqn[2]);
250                     UNLOCK(h, pqn[3]);
251                 }
252                 else
253                 {
254                     UNLOCK(f, pqn[0]);
255                     UNLOCK(g, pqn[1]);
256                 }
257             }
258         }
259     }
260 }
261
262
263 set_t *set_alloc(void)
264 {
265     set_t *s;
266
267     s = malloc(sizeof(*s));
268     mcs_init(&s->root.lock);
269     s->root.k = SENTINEL_KEYMIN;
270     s->root.v = (setval_t)(~1UL); /* dummy root node is white. */
271     s->root.l = NULL;
272     s->root.r = NULL;
273
274     return s;
275 }
276
277
278 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
279 {
280     node_t  *f, *w;
281     qnode_t  f_qn, w_qn;
282     int dir;
283     setval_t ov = NULL;
284     ptst_t  *ptst;
285
286     k = CALLER_TO_INTERNAL_KEY(k);
287
288     ptst = critical_enter();
289
290  retry:
291     f = find(&s->root, k, &f_qn, &dir);
292
293     if ( (w = FOLLOW(f, dir)) != NULL )
294     {
295         /* Protected by parent lock. */
296         assert(!IS_BLUE(w));
297         ov = w->v;
298         if ( overwrite || (ov == NULL) ) w->v = v;
299     }
300     else
301     {
302         w = gc_alloc(ptst, gc_id);
303         w->l = NULL;
304         w->r = NULL;
305         w->v = v;
306         w->k = k;
307         mcs_init(&w->lock);
308         UPDATE(f, dir, w);
309     }
310
311     UNLOCK(f, &f_qn);
312
313     critical_exit(ptst);
314
315     return ov;
316 }
317
318
319 setval_t set_remove(set_t *s, setkey_t k)
320 {
321     node_t *f, *w;
322     qnode_t qn[4], *pqn[] = { qn+0, qn+1, qn+2, qn+3, qn+0, qn+1 };
323     int dir;
324     setval_t v = NULL;
325     ptst_t *ptst;
326
327     k = CALLER_TO_INTERNAL_KEY(k);
328
329     ptst = critical_enter();
330
331     f = find(&s->root, k, pqn[0], &dir);
332     if ( (w = FOLLOW(f, dir)) != NULL )
333     {
334         LOCK(w, pqn[1]);
335         v = w->v;
336         w->v = NULL;
337         assert(!IS_BLUE(w));
338         delete_by_rotation(ptst, f, dir, pqn, 0);
339     }
340     else
341     {
342         UNLOCK(f, pqn[0]);
343     }
344
345     critical_exit(ptst);
346
347     return v;
348 }
349
350
351 setval_t set_lookup(set_t *s, setkey_t k)
352 {
353     node_t *n;
354     setval_t v = NULL;
355     ptst_t *ptst;
356
357     k = CALLER_TO_INTERNAL_KEY(k);
358
359     ptst = critical_enter();
360
361     n = weak_find(&s->root, k);
362     if ( n != NULL ) v = GET_VALUE(n);
363
364     critical_exit(ptst);
365     return v;
366 }
367
368
369 void _init_set_subsystem(void)
370 {
371     gc_id = gc_add_allocator(sizeof(node_t));
372 }