afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / skip_cas.c
1 /******************************************************************************
2  * skip_cas.c
3  *
4  * Skip lists, allowing concurrent update by use of CAS primitives.
5  *
6  * Copyright (c) 2001-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 <stdlib.h>
38 #include <string.h>
39 #include <assert.h>
40 #include "portable_defns.h"
41 #include "ptst.h"
42 #include "set.h"
43
44
45 /*
46  * SKIP LIST
47  */
48
49 typedef struct node_st node_t;
50 typedef struct set_st set_t;
51 typedef VOLATILE node_t *sh_node_pt;
52
53 struct node_st
54 {
55     int        level;
56 #define LEVEL_MASK     0x0ff
57 #define READY_FOR_FREE 0x100
58     setkey_t  k;
59     setval_t  v;
60     sh_node_pt next[1];
61 };
62
63 struct set_st
64 {
65     node_t head;
66 };
67
68 static int gc_id[NUM_LEVELS];
69
70 /*
71  * PRIVATE FUNCTIONS
72  */
73
74 /*
75  * Random level generator. Drop-off rate is 0.5 per level.
76  * Returns value 1 <= level <= NUM_LEVELS.
77  */
78 static int get_level(ptst_t *ptst)
79 {
80     unsigned long r = rand_next(ptst);
81     int l = 1;
82     r = (r >> 4) & ((1 << (NUM_LEVELS-1)) - 1);
83     while ( (r & 1) ) { l++; r >>= 1; }
84     return(l);
85 }
86
87
88 /*
89  * Allocate a new node, and initialise its @level field.
90  * NB. Initialisation will eventually be pushed into garbage collector,
91  * because of dependent read reordering.
92  */
93 static node_t *alloc_node(ptst_t *ptst)
94 {
95     int l;
96     node_t *n;
97     l = get_level(ptst);
98     n = gc_alloc(ptst, gc_id[l - 1]);
99     n->level = l;
100     return(n);
101 }
102
103
104 /* Free a node to the garbage collector. */
105 static void free_node(ptst_t *ptst, sh_node_pt n)
106 {
107     gc_free(ptst, (void *)n, gc_id[(n->level & LEVEL_MASK) - 1]);
108 }
109
110
111 /*
112  * Search for first non-deleted node, N, with key >= @k at each level in @l.
113  * RETURN VALUES:
114  *  Array @pa: @pa[i] is non-deleted predecessor of N at level i
115  *  Array @na: @na[i] is N itself, which should be pointed at by @pa[i]
116  *  MAIN RETURN VALUE: same as @na[0].
117  */
118 static sh_node_pt strong_search_predecessors(
119     set_t *l, setkey_t k, sh_node_pt *pa, sh_node_pt *na)
120 {
121     sh_node_pt x, x_next, old_x_next, y, y_next;
122     setkey_t  y_k;
123     int        i;
124
125  retry:
126     RMB();
127
128     x = &l->head;
129     for ( i = NUM_LEVELS - 1; i >= 0; i-- )
130     {
131         /* We start our search at previous level's unmarked predecessor. */
132         READ_FIELD(x_next, x->next[i]);
133         /* If this pointer's marked, so is @pa[i+1]. May as well retry. */
134         if ( is_marked_ref(x_next) ) goto retry;
135
136         for ( y = x_next; ; y = y_next )
137         {
138             /* Shift over a sequence of marked nodes. */
139             for ( ; ; )
140             {
141                 READ_FIELD(y_next, y->next[i]);
142                 if ( !is_marked_ref(y_next) ) break;
143                 y = get_unmarked_ref(y_next);
144             }
145
146             READ_FIELD(y_k, y->k);
147             if ( y_k >= k ) break;
148
149             /* Update estimate of predecessor at this level. */
150             x      = y;
151             x_next = y_next;
152         }
153
154         /* Swing forward pointer over any marked nodes. */
155         if ( x_next != y )
156         {
157             old_x_next = CASPO(&x->next[i], x_next, y);
158             if ( old_x_next != x_next ) goto retry;
159         }
160
161         if ( pa ) pa[i] = x;
162         if ( na ) na[i] = y;
163     }
164
165     return(y);
166 }
167
168
169 /* This function does not remove marked nodes. Use it optimistically. */
170 static sh_node_pt weak_search_predecessors(
171     set_t *l, setkey_t k, sh_node_pt *pa, sh_node_pt *na)
172 {
173     sh_node_pt x, x_next;
174     setkey_t  x_next_k;
175     int        i;
176
177     x = &l->head;
178     for ( i = NUM_LEVELS - 1; i >= 0; i-- )
179     {
180         for ( ; ; )
181         {
182             READ_FIELD(x_next, x->next[i]);
183             x_next = get_unmarked_ref(x_next);
184
185             READ_FIELD(x_next_k, x_next->k);
186             if ( x_next_k >= k ) break;
187
188             x = x_next;
189         }
190
191         if ( pa ) pa[i] = x;
192         if ( na ) na[i] = x_next;
193     }
194
195     return(x_next);
196 }
197
198
199 /*
200  * Mark @x deleted at every level in its list from @level down to level 1.
201  * When all forward pointers are marked, node is effectively deleted.
202  * Future searches will properly remove node by swinging predecessors'
203  * forward pointers.
204  */
205 static void mark_deleted(sh_node_pt x, int level)
206 {
207     sh_node_pt x_next;
208
209     while ( --level >= 0 )
210     {
211         x_next = x->next[level];
212         while ( !is_marked_ref(x_next) )
213         {
214             x_next = CASPO(&x->next[level], x_next, get_marked_ref(x_next));
215         }
216         WEAK_DEP_ORDER_WMB(); /* mark in order */
217     }
218 }
219
220
221 static int check_for_full_delete(sh_node_pt x)
222 {
223     int level = x->level;
224     return ((level & READY_FOR_FREE) ||
225             (CASIO(&x->level, level, level | READY_FOR_FREE) != level));
226 }
227
228
229 static void do_full_delete(ptst_t *ptst, set_t *l, sh_node_pt x, int level)
230 {
231     int k = x->k;
232 #ifdef WEAK_MEM_ORDER
233     sh_node_pt preds[NUM_LEVELS];
234     int i = level;
235  retry:
236     (void)strong_search_predecessors(l, k, preds, NULL);
237     /*
238      * Above level 1, references to @x can disappear if a node is inserted
239      * immediately before and we see an old value for its forward pointer. This
240      * is a conservative way of checking for that situation.
241      */
242     if ( i > 0 ) RMB();
243     while ( i > 0 )
244     {
245         node_t *n = get_unmarked_ref(preds[i]->next[i]);
246         while ( n->k < k )
247         {
248             n = get_unmarked_ref(n->next[i]);
249             RMB(); /* we don't want refs to @x to "disappear" */
250         }
251         if ( n == x ) goto retry;
252         i--; /* don't need to check this level again, even if we retry. */
253     }
254 #else
255     (void)strong_search_predecessors(l, k, NULL, NULL);
256 #endif
257     free_node(ptst, x);
258 }
259
260
261 /*
262  * PUBLIC FUNCTIONS
263  */
264
265 set_t *set_alloc(void)
266 {
267     set_t *l;
268     node_t *n;
269     int i;
270
271     n = malloc(sizeof(*n) + (NUM_LEVELS-1)*sizeof(node_t *));
272     memset(n, 0, sizeof(*n) + (NUM_LEVELS-1)*sizeof(node_t *));
273     n->k = SENTINEL_KEYMAX;
274
275     /*
276      * Set the forward pointers of final node to other than NULL,
277      * otherwise READ_FIELD() will continually execute costly barriers.
278      * Note use of 0xfe -- that doesn't look like a marked value!
279      */
280     memset(n->next, 0xfe, NUM_LEVELS*sizeof(node_t *));
281
282     l = malloc(sizeof(*l) + (NUM_LEVELS-1)*sizeof(node_t *));
283     l->head.k = SENTINEL_KEYMIN;
284     l->head.level = NUM_LEVELS;
285     for ( i = 0; i < NUM_LEVELS; i++ )
286     {
287         l->head.next[i] = n;
288     }
289
290     return(l);
291 }
292
293
294 setval_t set_update(set_t *l, setkey_t k, setval_t v, int overwrite)
295 {
296     setval_t  ov, new_ov;
297     ptst_t    *ptst;
298     sh_node_pt preds[NUM_LEVELS], succs[NUM_LEVELS];
299     sh_node_pt pred, succ, new = NULL, new_next, old_next;
300     int        i, level;
301
302     k = CALLER_TO_INTERNAL_KEY(k);
303
304     ptst = critical_enter();
305
306     succ = weak_search_predecessors(l, k, preds, succs);
307
308  retry:
309     ov = NULL;
310
311     if ( succ->k == k )
312     {
313         /* Already a @k node in the list: update its mapping. */
314         new_ov = succ->v;
315         do {
316             if ( (ov = new_ov) == NULL )
317             {
318                 /* Finish deleting the node, then retry. */
319                 READ_FIELD(level, succ->level);
320                 mark_deleted(succ, level & LEVEL_MASK);
321                 succ = strong_search_predecessors(l, k, preds, succs);
322                 goto retry;
323             }
324         }
325         while ( overwrite && ((new_ov = CASPO(&succ->v, ov, v)) != ov) );
326
327         if ( new != NULL ) free_node(ptst, new);
328         goto out;
329     }
330
331 #ifdef WEAK_MEM_ORDER
332     /* Free node from previous attempt, if this is a retry. */
333     if ( new != NULL )
334     {
335         free_node(ptst, new);
336         new = NULL;
337     }
338 #endif
339
340     /* Not in the list, so initialise a new node for insertion. */
341     if ( new == NULL )
342     {
343         new    = alloc_node(ptst);
344         new->k = k;
345         new->v = v;
346     }
347     level = new->level;
348
349     /* If successors don't change, this saves us some CAS operations. */
350     for ( i = 0; i < level; i++ )
351     {
352         new->next[i] = succs[i];
353     }
354
355     /* We've committed when we've inserted at level 1. */
356     WMB_NEAR_CAS(); /* make sure node fully initialised before inserting */
357     old_next = CASPO(&preds[0]->next[0], succ, new);
358     if ( old_next != succ )
359     {
360         succ = strong_search_predecessors(l, k, preds, succs);
361         goto retry;
362     }
363
364     /* Insert at each of the other levels in turn. */
365     i = 1;
366     while ( i < level )
367     {
368         pred = preds[i];
369         succ = succs[i];
370
371         /* Someone *can* delete @new under our feet! */
372         new_next = new->next[i];
373         if ( is_marked_ref(new_next) ) goto success;
374
375         /* Ensure forward pointer of new node is up to date. */
376         if ( new_next != succ )
377         {
378             old_next = CASPO(&new->next[i], new_next, succ);
379             if ( is_marked_ref(old_next) ) goto success;
380             assert(old_next == new_next);
381         }
382
383         /* Ensure we have unique key values at every level. */
384         if ( succ->k == k ) goto new_world_view;
385         assert((pred->k < k) && (succ->k > k));
386
387         /* Replumb predecessor's forward pointer. */
388         old_next = CASPO(&pred->next[i], succ, new);
389         if ( old_next != succ )
390         {
391         new_world_view:
392             RMB(); /* get up-to-date view of the world. */
393             (void)strong_search_predecessors(l, k, preds, succs);
394             continue;
395         }
396
397         /* Succeeded at this level. */
398         i++;
399     }
400
401  success:
402     /* Ensure node is visible at all levels before punting deletion. */
403     WEAK_DEP_ORDER_WMB();
404     if ( check_for_full_delete(new) )
405     {
406         MB(); /* make sure we see all marks in @new. */
407         do_full_delete(ptst, l, new, level - 1);
408     }
409  out:
410     critical_exit(ptst);
411     return(ov);
412 }
413
414
415 setval_t set_remove(set_t *l, setkey_t k)
416 {
417     setval_t  v = NULL, new_v;
418     ptst_t    *ptst;
419     sh_node_pt preds[NUM_LEVELS], x;
420     int        level, i;
421
422     k = CALLER_TO_INTERNAL_KEY(k);
423
424     ptst = critical_enter();
425
426     x = weak_search_predecessors(l, k, preds, NULL);
427     if ( x->k > k ) goto out;
428     READ_FIELD(level, x->level);
429     level = level & LEVEL_MASK;
430
431     /* Once we've marked the value field, the node is effectively deleted. */
432     new_v = x->v;
433     do {
434         v = new_v;
435         if ( v == NULL ) goto out;
436     }
437     while ( (new_v = CASPO(&x->v, v, NULL)) != v );
438
439     /* Committed to @x: mark lower-level forward pointers. */
440     WEAK_DEP_ORDER_WMB(); /* enforce above as linearisation point */
441     mark_deleted(x, level);
442
443     /*
444      * We must swing predecessors' pointers, or we can end up with
445      * an unbounded number of marked but not fully deleted nodes.
446      * Doing this creates a bound equal to number of threads in the system.
447      * Furthermore, we can't legitimately call 'free_node' until all shared
448      * references are gone.
449      */
450     for ( i = level - 1; i >= 0; i-- )
451     {
452         if ( CASPO(&preds[i]->next[i], x, get_unmarked_ref(x->next[i])) != x )
453         {
454             if ( (i != (level - 1)) || check_for_full_delete(x) )
455             {
456                 MB(); /* make sure we see node at all levels. */
457                 do_full_delete(ptst, l, x, i);
458             }
459             goto out;
460         }
461     }
462
463     free_node(ptst, x);
464
465  out:
466     critical_exit(ptst);
467     return(v);
468 }
469
470
471 setval_t set_lookup(set_t *l, setkey_t k)
472 {
473     setval_t  v = NULL;
474     ptst_t    *ptst;
475     sh_node_pt x;
476
477     k = CALLER_TO_INTERNAL_KEY(k);
478
479     ptst = critical_enter();
480
481     x = weak_search_predecessors(l, k, NULL, NULL);
482     if ( x->k == k ) READ_FIELD(v, x->v);
483
484     critical_exit(ptst);
485     return(v);
486 }
487
488
489 void _init_set_subsystem(void)
490 {
491     int i;
492
493     for ( i = 0; i < NUM_LEVELS; i++ )
494     {
495         gc_id[i] = gc_add_allocator(sizeof(node_t) + i*sizeof(node_t *));
496     }
497 }