afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / bst_mcas.c
1 /******************************************************************************
2  * bst_mcas.c
3  *
4  * Lock-free binary search trees (BSTs), based on MCAS.
5  * Uses a threaded representation to synchronise searches with deletions.
6  *
7  * Copyright (c) 2002-2003, K A Fraser
8
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are
11 met:
12
13     * Redistributions of source code must retain the above copyright
14     * notice, this list of conditions and the following disclaimer.
15     * Redistributions in binary form must reproduce the above
16     * copyright notice, this list of conditions and the following
17     * disclaimer in the documentation and/or other materials provided
18     * with the distribution.  Neither the name of the Keir Fraser
19     * nor the names of its contributors may be used to endorse or
20     * promote products derived from this software without specific
21     * prior written permission.
22
23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34  */
35
36 #define __SET_IMPLEMENTATION__
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <unistd.h>
41 #include "portable_defns.h"
42 #include "gc.h"
43 #include "set.h"
44
45 /* Allow MCAS marks to be detected using a single bitop (see IS_MCAS_OWNED). */
46 #define MARK_IN_PROGRESS 2
47 #define MARK_PTR_TO_CD   3
48
49 #define MARK_THREAD      1
50 #define MARK_GARBAGE     4
51
52 #define THREAD(_p)     ((node_t *)((int_addr_t)(_p)|(MARK_THREAD)))
53 #define GARBAGE(_p)    ((node_t *)((int_addr_t)(_p)|(MARK_GARBAGE)))
54 #define UNTHREAD(_p) ((node_t *)((int_addr_t)(_p)&~MARK_THREAD))
55 #define UNGARBAGE(_p) ((node_t *)((int_addr_t)(_p)&~MARK_GARBAGE))
56 /* Following only matches 2 and 3 (mod 4). Those happen to be MCAS marks :) */
57 #define IS_MCAS_OWNED(_p)   ((int)((int_addr_t)(_p)&2))
58 /* Matches 1 and 3 (mod 4). So only use if the ref is *not* owned by MCAS!! */
59 #define IS_THREAD(_p)       ((int)((int_addr_t)(_p)&MARK_THREAD))
60 /* Only use if the ref is *not* owned by MCAS (which may use bit 2)!! */
61 #define IS_GARBAGE(_p)      ((int)((int_addr_t)(_p)&MARK_GARBAGE))
62
63 #include "mcas.c"
64
65 typedef struct node_st node_t;
66 typedef struct set_st set_t;
67
68 struct node_st
69 {
70     setkey_t k;
71     setval_t v;
72     node_t *l, *r;
73 };
74
75 struct set_st
76 {
77     node_t root;
78     node_t sentinel;
79 };
80
81 static int gc_id;
82
83 #define READ_LINK(_var, _link)                              \
84     do {                                                    \
85         (_var) = (_link);                                   \
86         if ( !IS_MCAS_OWNED(_var) ) break;                  \
87         mcas_fixup((void **)&(_link), (_var));              \
88     } while ( 1 )
89
90 #define WEAK_READ_LINK(_var, _link)                         \
91     do {                                                    \
92         READ_LINK(_var, _link);                             \
93         (_var) = UNGARBAGE(_var);                           \
94     } while ( 0 )
95
96 #define STRONG_READ_LINK(_var, _link)                       \
97     do {                                                    \
98         READ_LINK(_var, _link);                             \
99         if ( IS_GARBAGE(_var) ) goto retry;                 \
100     } while ( 0 )
101
102 #define PROCESS_VAL(_v,_pv)                                 \
103     do {                                                    \
104         while ( IS_MCAS_OWNED(_v) )                         \
105         {                                                   \
106             mcas_fixup((void **)(_pv), (_v));               \
107             (_v) = *(_pv);                                  \
108         }                                                   \
109     } while ( 0 )
110
111
112 /*
113  * Search for node with key == k. Return NULL if none such, else ptr to node.
114  * @ppn is filled in with parent node, or closest leaf if no match.
115  * p and n will both be unmarked and adjacent on return.
116  */
117 static node_t *search(set_t *s, setkey_t k, node_t **ppn)
118 {
119     node_t *p, *n, *c;
120
121  retry:
122     p = &s->root;
123     WEAK_READ_LINK(n, p->r);
124
125     while ( !IS_THREAD(n) )
126     {
127         if ( k < n->k ) {
128             WEAK_READ_LINK(c, n->l);
129             assert(UNTHREAD(c)->k < n->k);
130         } else if ( k > n->k ) {
131             WEAK_READ_LINK(c, n->r);
132             assert(UNTHREAD(c)->k > n->k);
133         } else /* k == n->k */
134             goto found;
135
136         p = n; n = c;
137     }
138
139     /* Follow final thread, just in case. */
140     c = UNTHREAD(n);
141     if ( k == c->k ) goto followed_thread;
142
143  found:
144     if ( ppn ) *ppn = p;
145     return n;
146
147  followed_thread:
148     if ( ppn ) { RMB(); goto retry; }
149     return c;
150 }
151
152
153 set_t *set_alloc(void)
154 {
155     set_t *s;
156
157     static int mcas_inited = 0;
158     if ( !CASIO(&mcas_inited, 0, 1) )
159     {
160         if ( (sizeof(node_t) % 8) != 0 )
161         {
162             fprintf(stderr, "FATAL: node_t must be multiple of 8 bytes\n");
163             *((int*)0)=0;
164         }
165         mcas_init();
166     }
167
168     s = malloc(sizeof(*s));
169     s->root.k = SENTINEL_KEYMIN;
170     s->root.v = NULL;
171     s->root.l = THREAD(&s->root);
172     s->root.r = THREAD(&s->sentinel);
173
174     s->sentinel.k = SENTINEL_KEYMAX;
175
176     return s;
177 }
178
179
180 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
181 {
182     setval_t ov, nov;
183     node_t *p, *n, *new = NULL, **ppc;
184     ptst_t *ptst;
185
186     k = CALLER_TO_INTERNAL_KEY(k);
187
188     ptst = critical_enter();
189
190     do {
191     retry:
192         ov = NULL;
193
194         n = search(s, k, &p);
195         if ( !IS_THREAD(n) )
196         {
197             /* Already a @k node in the set: update its mapping. */
198             nov = n->v;
199             do {
200                 ov = nov;
201                 PROCESS_VAL(ov, &n->v);
202                 if ( ov == NULL ) goto retry;
203             }
204             while ( overwrite && ((nov = CASPO(&n->v, ov, v)) != ov) );
205
206             goto out;
207         }
208
209         if ( new == NULL )
210         {
211             new = gc_alloc(ptst, gc_id);
212             new->k = k;
213             new->v = v;
214         }
215
216         if ( p->k < k )
217         {
218             /* Ensure we insert in the correct interval. */
219             if ( UNTHREAD(n)->k < k ) goto retry;
220             new->l = THREAD(p);
221             new->r = n;
222             ppc = &p->r;
223         }
224         else
225         {
226             if ( UNTHREAD(n)->k > k ) goto retry;
227             new->l = n;
228             new->r = THREAD(p);
229             ppc = &p->l;
230         }
231
232         WMB_NEAR_CAS();
233     }
234     while ( CASPO(ppc, n, new) != n );
235
236     new = NULL;
237
238  out:
239     if ( new ) gc_free(ptst, new, gc_id);
240     critical_exit(ptst);
241     return ov;
242 }
243
244
245 #define FIND_HELPER(_d1, _d2, _n, _ap, _a)                               \
246 {                                                                        \
247     node_t *ac;                                                          \
248     (_ap) = NULL;                                                        \
249     (_a)  = (_n);                                                        \
250     WEAK_READ_LINK(ac, (_a)->_d1);                                       \
251     while ( !IS_THREAD(ac) )                                             \
252     {                                                                    \
253         (_ap) = (_a);                                                    \
254         (_a)  = ac;                                                      \
255         WEAK_READ_LINK(ac, (_a)->_d2);                                   \
256     }                                                                    \
257 }
258
259
260 /*
261  * Order of first two cases does matter! If @n is the left-link of @p, then
262  * we use DELETE_HELPER(l, r). What matters is what we do when @n is a leaf.
263  * In this case we end up choosing n->l to propagate to p->l -- this
264  * happens to be the correct choice :-)
265  *
266  * NB. Note symmetric deletion cases dependent on parameter @dir. We
267  * could simplify the algorithm by always following one direction. In fact,
268  * that is slightly worse, or much worse, depending on the chosen case
269  * (hint: works best with dir hardwired to zero :-)....
270  */
271 #define dir 0
272 #define DELETE_HELPER(_d1, _d2)                                              \
273     FIND_HELPER(_d1, _d2, n, pal, al);                                       \
274     FIND_HELPER(_d2, _d1, n, par, ar);                                       \
275     if ( IS_THREAD(n ## _d2) )                                               \
276     {                                                                        \
277         if ( IS_THREAD(n ## _d1) )                                           \
278         {                                                                    \
279             r = mcas(4,                                                      \
280                      (void **)&n->v, v,  NULL,                               \
281                      (void **)&n->l, nl, GARBAGE(nl),                        \
282                      (void **)&n->r, nr, GARBAGE(nr),                        \
283                      (void **)p_pc,  n,  n ## _d1);                          \
284         }                                                                    \
285         else                                                                 \
286         {                                                                    \
287             if ( al == n ) goto retry;                                       \
288             r = mcas(5,                                                      \
289                      (void **)&n->v, v,  NULL,                               \
290                      (void **)&n->l, nl, GARBAGE(nl),                        \
291                      (void **)&n->r, nr, GARBAGE(nr),                        \
292                      (void **)p_pc,  n,  n ## _d1,                           \
293                      (void **)&al->_d2, THREAD(n), n ## _d2);                \
294         }                                                                    \
295     }                                                                        \
296     else if ( IS_THREAD(n ## _d1) )                                          \
297     {                                                                        \
298         if ( ar == n ) goto retry;                                           \
299         r = mcas(5,                                                          \
300                  (void **)&n->v, v,  NULL,                                   \
301                  (void **)&n->l, nl, GARBAGE(nl),                            \
302                  (void **)&n->r, nr, GARBAGE(nr),                            \
303                  (void **)p_pc,  n,  n ## _d2,                               \
304                  (void **)&ar->_d1, THREAD(n), n ## _d1);                    \
305     }                                                                        \
306     else if ( dir )                                                          \
307     {                                                                        \
308         if ( (al == n) || (ar == n) ) goto retry;                            \
309         if ( par == n )                                                      \
310         {                                                                    \
311             r = mcas(6,                                                      \
312                      (void **)&n->v, v,  NULL,                               \
313                      (void **)&ar->_d1, THREAD(n), n ## _d1,                 \
314                      (void **)&al->_d2, THREAD(n), THREAD(ar),               \
315                      (void **)&n->l,    nl, GARBAGE(nl),                     \
316                      (void **)&n->r,    nr, GARBAGE(nr),                     \
317                      (void **)p_pc,     n,  ar);                             \
318         }                                                                    \
319         else                                                                 \
320         {                                                                    \
321             STRONG_READ_LINK(ac, ar->_d2);                                   \
322             r = mcas(8,                                                      \
323                      (void **)&n->v, v,  NULL,                               \
324                      (void **)&par->_d1, ar,                                 \
325                                          (IS_THREAD(ac) ? THREAD(ar) : ac),  \
326                      (void **)&ar->_d2, ac, n ## _d2,                        \
327                      (void **)&ar->_d1, THREAD(n), n ## _d1,                 \
328                      (void **)&al->_d2, THREAD(n), THREAD(ar),               \
329                      (void **)&n->l,    nl, GARBAGE(nl),                     \
330                      (void **)&n->r,    nr, GARBAGE(nr),                     \
331                      (void **)p_pc,     n,  ar);                             \
332         }                                                                    \
333     }                                                                        \
334     else                                                                     \
335     {                                                                        \
336         if ( (al == n) || (ar == n) ) goto retry;                            \
337         if ( pal == n )                                                      \
338         {                                                                    \
339             r = mcas(6,                                                      \
340                      (void **)&n->v, v,  NULL,                               \
341                      (void **)&al->_d2, THREAD(n), n ## _d2,                 \
342                      (void **)&ar->_d1, THREAD(n), THREAD(al),               \
343                      (void **)&n->l,    nl, GARBAGE(nl),                     \
344                      (void **)&n->r,    nr, GARBAGE(nr),                     \
345                      (void **)p_pc,     n,  al);                             \
346         }                                                                    \
347         else                                                                 \
348         {                                                                    \
349             STRONG_READ_LINK(ac, al->_d1);                                   \
350             r = mcas(8,                                                      \
351                      (void **)&n->v, v,  NULL,                               \
352                      (void **)&pal->_d2, al,                                 \
353                                          (IS_THREAD(ac) ? THREAD(al) : ac),  \
354                      (void **)&al->_d1, ac, n ## _d1,                        \
355                      (void **)&al->_d2, THREAD(n), n ## _d2,                 \
356                      (void **)&ar->_d1, THREAD(n), THREAD(al),               \
357                      (void **)&n->l,    nl, GARBAGE(nl),                     \
358                      (void **)&n->r,    nr, GARBAGE(nr),                     \
359                      (void **)p_pc,     n,  al);                             \
360         }                                                                    \
361     }
362
363
364 /* @k: key of node to be deleted */
365 setval_t set_remove(set_t *s, setkey_t k)
366 {
367     node_t *p, *n, *nl, *nr, *al, *ar, *pal, *par, *ac, **p_pc;
368     int r = 0;
369     setval_t v;
370     ptst_t *ptst;
371
372     k = CALLER_TO_INTERNAL_KEY(k);
373
374     ptst = critical_enter();
375
376     do
377     {
378     retry:
379         v = NULL;
380
381         /* Node present? */
382         n = search(s, k, &p);
383         if ( IS_THREAD(n) ) goto out;
384
385         /* Already deleted? */
386         v = n->v;
387         PROCESS_VAL(v, &n->v);
388         if ( v == NULL ) goto out;
389
390         STRONG_READ_LINK(nl, n->l);
391         STRONG_READ_LINK(nr, n->r);
392         p_pc = (p->k > n->k) ? &p->l : &p->r;
393
394         if ( p->k > n->k )
395         {
396             /* @n is leftwards link from @p. */
397             DELETE_HELPER(l, r);
398         }
399         else
400         {
401             /* @n is rightwards link from @p. */
402             DELETE_HELPER(r, l);
403         }
404     } while ( !r );
405
406     gc_free(ptst, n, gc_id);
407
408  out:
409     critical_exit(ptst);
410     return v;
411 }
412
413
414 setval_t set_lookup(set_t *s, setkey_t k)
415 {
416     node_t *n;
417     setval_t v;
418     ptst_t *ptst;
419
420     k = CALLER_TO_INTERNAL_KEY(k);
421
422     ptst = critical_enter();
423
424     n = search(s, k, NULL);
425     v = (!IS_THREAD(n)) ? n->v : NULL;
426     PROCESS_VAL(v, &n->v);
427
428     critical_exit(ptst);
429     return v;
430 }
431
432
433 void _init_set_subsystem(void)
434 {
435     gc_id = gc_add_allocator(sizeof(node_t));
436 }