afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / skip_lock.c
1 /******************************************************************************
2  * skip_lock.c (Variable-granularity Mutexes)
3  *
4  * Mutex only taken for write operations (reads are unprotected). Write
5  * mutexes come in three flavours, selected by a compile-time flag.
6  *
7  * If FAT_MTX is defined:
8  *  A skip list is protected by one mutex for the entire list. Note that this
9  *  differs from skip_bm.c, which  takes the mutex for read operations as well.
10  *
11  * If TINY_MTX is defined:
12  *  Mutex per forward pointer in each node.
13  *
14  * If neither flag is defined:
15  *  Mutex per node.
16  *
17  * Copyright (c) 2001-2003, K A Fraser
18
19 Redistribution and use in source and binary forms, with or without
20 modification, are permitted provided that the following conditions are
21 met:
22
23     * Redistributions of source code must retain the above copyright
24     * notice, this list of conditions and the following disclaimer.
25     * Redistributions in binary form must reproduce the above
26     * copyright notice, this list of conditions and the following
27     * disclaimer in the documentation and/or other materials provided
28     * with the distribution.  Neither the name of the Keir Fraser
29     * nor the names of its contributors may be used to endorse or
30     * promote products derived from this software without specific
31     * prior written permission.
32
33 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
34 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
35 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
36 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
37 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
38 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
39 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
40 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
41 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
42 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
43 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44  */
45
46 #define __SET_IMPLEMENTATION__
47
48 #include <stdlib.h>
49 #include <string.h>
50 #include <assert.h>
51 #include "portable_defns.h"
52 #include "ptst.h"
53 #include "set.h"
54
55
56 /*
57  * SKIP LIST
58  */
59
60 typedef struct node_st node_t;
61 typedef struct set_st set_t;
62 typedef VOLATILE node_t *sh_node_pt;
63
64 typedef struct ptr_st ptr_t;
65 struct ptr_st
66 {
67 #ifdef TINY_MTX /* mutex per forward pointer */
68     mcs_lock_t m;
69 #endif
70     sh_node_pt      p;
71 };
72
73 struct node_st
74 {
75     int             level;
76     setkey_t       k;
77     setval_t       v;
78 #ifndef FAT_MTX
79     mcs_lock_t m;
80 #endif
81     ptr_t           next[1];
82 };
83
84 struct set_st
85 {
86 #ifdef FAT_MTX
87     mcs_lock_t m;
88 #endif
89     node_t          head;
90 };
91
92 static int gc_id[NUM_LEVELS];
93
94 /*
95  * LOCKING
96  */
97
98 #ifdef FAT_MTX
99
100 #define LIST_LOCK(_l,_qn)            ((void)mcs_lock((void*)&(_l)->m, (_qn)))
101 #define LIST_UNLOCK(_l,_qn)          ((void)mcs_unlock((void*)&(_l)->m, (_qn)))
102 #define NODE_LOCK(_x,_qn)            ((void)0)
103 #define NODE_UNLOCK(_x,_qn)          ((void)0)
104 #define PTR_UPDATE_LOCK(_x,_i,_qn)   ((void)0)
105 #define PTR_UPDATE_UNLOCK(_x,_i,_qn) ((void)0)
106 #define PTR_DELETE_LOCK(_x,_i,_qn)   ((void)0)
107 #define PTR_DELETE_UNLOCK(_x,_i,_qn) ((void)0)
108
109 #else
110
111 #define LIST_LOCK(_l,_qn)         ((void)0)
112 #define LIST_UNLOCK(_l,_qn)       ((void)0)
113
114 /* We take the main node lock to get exclusive rights on insert/delete ops. */
115 #define NODE_LOCK(_x,_qn)         ((void)mcs_lock((void*)&(_x)->m, (_qn)))
116 #define NODE_UNLOCK(_x,_qn)       ((void)mcs_unlock((void*)&(_x)->m, (_qn)))
117
118 #ifdef TINY_MTX
119
120 /*
121  * Predecessor's pointer is locked before swinging (on delete), or
122  * replumbing (on insert).
123  */
124 #define PTR_UPDATE_LOCK(_x, _i, _qn)   \
125     ((void)mcs_lock((void*)&(_x)->next[(_i)].m, (_qn)))
126 #define PTR_UPDATE_UNLOCK(_x, _i, _qn) \
127     ((void)mcs_unlock((void*)&(_x)->next[(_i)].m, (_qn)))
128 /*
129  * When deleting a node, we take the lock on each of its pointers in turn,
130  * to prevent someone from inserting a new node directly after, or deleting
131  * immediate successor.
132  */
133 #define PTR_DELETE_LOCK(_x, _i, _qn)   PTR_UPDATE_LOCK(_x,_i,(_qn))
134 #define PTR_DELETE_UNLOCK(_x, _i, _qn) PTR_UPDATE_UNLOCK(_x,_i,(_qn))
135
136 #else /* LITTLE_MTX */
137
138 /*
139  * Predecessor must certainly be locked for insert/delete ops. So we take
140  * the only lock we can.
141  */
142 #define PTR_UPDATE_LOCK(_x, _i, _qn)   NODE_LOCK(_x,(_qn))
143 #define PTR_UPDATE_UNLOCK(_x, _i, _qn) NODE_UNLOCK(_x,(_qn))
144 /*
145  * We can't lock individual pointers. There's no need anyway, since we have
146  * the node's lock already (to allow us exclusive delete rights).
147  */
148 #define PTR_DELETE_LOCK(_x, _i, _qn)   ((void)0)
149 #define PTR_DELETE_UNLOCK(_x, _i, _qn) ((void)0)
150
151 #endif
152
153 #endif
154
155
156 /*
157  * PRIVATE FUNCTIONS
158  */
159
160 /*
161  * Random level generator. Drop-off rate is 0.5 per level.
162  * Returns value 1 <= level <= NUM_LEVELS.
163  */
164 static int get_level(ptst_t *ptst)
165 {
166     unsigned long r = rand_next(ptst);
167     int l = 1;
168     r = (r >> 4) & ((1 << (NUM_LEVELS-1)) - 1);
169     while ( (r & 1) ) { l++; r >>= 1; }
170     return(l);
171 }
172
173
174 /*
175  * Allocate a new node, and initialise its @level field.
176  * NB. Initialisation will eventually be pushed into garbage collector,
177  * because of dependent read reordering.
178  */
179 static node_t *alloc_node(ptst_t *ptst)
180 {
181     int l;
182     node_t *n;
183     l = get_level(ptst);
184     n = gc_alloc(ptst, gc_id[l - 1]);
185     n->level = l;
186 #ifndef FAT_MTX
187     mcs_init(&n->m);
188 #endif
189 #ifdef TINY_MTX
190     for ( l = 0; l < n->level; l++ )
191     {
192         mcs_init(&n->next[l].m);
193     }
194 #endif
195     return(n);
196 }
197
198
199 /* Free a node to the garbage collector. */
200 static void free_node(ptst_t *ptst, sh_node_pt n)
201 {
202     gc_free(ptst, (void *)n, gc_id[n->level - 1]);
203 }
204
205
206 /*
207  * Find and lock predecessor at level @i of node with key @k. This
208  * predecessor must have key >= @x->k.
209  */
210 #ifndef FAT_MTX
211 static sh_node_pt get_lock(sh_node_pt x, setkey_t k, int i, qnode_t *qn)
212 {
213     sh_node_pt y;
214     setkey_t  y_k;
215
216     for ( ; ; )
217     {
218         READ_FIELD(y,   x->next[i].p);
219         READ_FIELD(y_k, y->k);
220         if ( y_k >= k ) break;
221     retry:
222         x = y;
223     }
224
225     PTR_UPDATE_LOCK(x, i, qn); /* MB => no need for READ_FIELD on x or y. */
226     y = x->next[i].p;
227     if ( y->k < k )
228     {
229         PTR_UPDATE_UNLOCK(x, i, qn);
230         goto retry;
231     }
232
233     return(x);
234 }
235 #else
236 #define get_lock(_x,_k,_i,_qn) (_x)
237 #endif
238
239
240 /*
241  * Search for first non-deleted node, N, with key >= @k at each level in @l.
242  * RETURN VALUES:
243  *  Array @pa: @pa[i] is non-deleted predecessor of N at level i
244  *  MAIN RETURN VALUE: N at level 0.
245  */
246 static sh_node_pt search_predecessors(set_t *l, setkey_t k, sh_node_pt *pa)
247 {
248     sh_node_pt x, y;
249     setkey_t  y_k;
250     int        i;
251
252     x = &l->head;
253     for ( i = NUM_LEVELS - 1; i >= 0; i-- )
254     {
255         for ( ; ; )
256         {
257             READ_FIELD(y,   x->next[i].p);
258             READ_FIELD(y_k, y->k);
259             if ( y_k >= k ) break;
260             x = y; /* remember largest predecessor so far */
261         }
262
263         if ( pa ) pa[i] = x;
264     }
265
266     return(y);
267 }
268
269
270 /*
271  * PUBLIC FUNCTIONS
272  */
273
274 set_t *set_alloc(void)
275 {
276     set_t *l;
277     node_t *n;
278     int i;
279
280     n = malloc(sizeof(*n) + (NUM_LEVELS-1)*sizeof(ptr_t));
281     memset(n, 0, sizeof(*n) + (NUM_LEVELS-1)*sizeof(ptr_t));
282     n->k = SENTINEL_KEYMAX;
283
284     l = malloc(sizeof(*l) + (NUM_LEVELS-1)*sizeof(ptr_t));
285     l->head.k = SENTINEL_KEYMIN;
286     l->head.level = NUM_LEVELS;
287 #ifdef FAT_MTX
288     mcs_init(&l->m);
289 #else
290     mcs_init(&l->head.m);
291 #endif
292     for ( i = 0; i < NUM_LEVELS; i++ )
293     {
294         l->head.next[i].p = n;
295 #ifdef TINY_MTX
296         mcs_init(&l->head.next[i].m);
297 #endif
298     }
299
300     return(l);
301 }
302
303
304 setval_t set_update(set_t *l, setkey_t k, setval_t v, int overwrite)
305 {
306     setval_t  ov = NULL;
307     ptst_t    *ptst;
308     sh_node_pt update[NUM_LEVELS];
309     sh_node_pt x, y;
310     int        i;
311     qnode_t    l_qn, x_qn, y_qn;
312
313     k = CALLER_TO_INTERNAL_KEY(k);
314
315     ptst = critical_enter();
316     LIST_LOCK(l, &l_qn);
317
318     (void)search_predecessors(l, k, update);
319
320     x = get_lock(update[0], k, 0, &x_qn);
321     y = x->next[0].p;
322     if ( y->k == k )
323     {
324         ov = y->v;
325         if ( overwrite ) y->v = v;
326         PTR_UPDATE_UNLOCK(x, 0, &x_qn);
327         goto out;
328     }
329
330     /* Not in the list, so do the insertion. */
331     y    = alloc_node(ptst);
332     y->k = k;
333     y->v = v;
334     NODE_LOCK(y, &y_qn);
335
336     for ( i = 0; i < y->level; i++ )
337     {
338         if ( i != 0 ) x = get_lock(update[i], k, i, &x_qn);
339         y->next[i].p = x->next[i].p;
340         WMB();
341         x->next[i].p = y;
342         PTR_UPDATE_UNLOCK(x, i, &x_qn);
343     }
344
345     NODE_UNLOCK(y, &y_qn);
346
347  out:
348     LIST_UNLOCK(l, &l_qn);
349     critical_exit(ptst);
350     return(ov);
351 }
352
353
354 setval_t set_remove(set_t *l, setkey_t k)
355 {
356     setval_t  v = NULL;
357     ptst_t    *ptst;
358     sh_node_pt update[NUM_LEVELS];
359     sh_node_pt x, y;
360     int        i;
361     qnode_t    l_qn, x_qn, y_qn, yd_qn;
362
363     k = CALLER_TO_INTERNAL_KEY(k);
364
365     ptst = critical_enter();
366     LIST_LOCK(l, &l_qn);
367
368     y = search_predecessors(l, k, update);
369
370 #ifdef FAT_MTX
371     if ( y->k != k ) goto out;
372 #else
373     y = update[0];
374     for ( ; ; )
375     {
376         setkey_t y_k;
377         y = y->next[0].p; /* no need for READ_FIELD() */
378         READ_FIELD(y_k, y->k);
379         if ( y_k > k ) goto out;
380         NODE_LOCK(y, &y_qn);
381         if ( (y_k == k) && (y_k <= y->next[0].p->k) ) break;
382         NODE_UNLOCK(y, &y_qn);
383     }
384 #endif
385
386     /* @y is the correct node, and we have it locked, so now delete it. */
387     for ( i = y->level - 1; i >= 0; i-- )
388     {
389         x = get_lock(update[i], k, i, &x_qn);
390         PTR_DELETE_LOCK(y, i, &yd_qn);
391         x->next[i].p = y->next[i].p;
392         WMB();
393         y->next[i].p = x;
394         PTR_DELETE_UNLOCK(y, i, &yd_qn);
395         PTR_UPDATE_UNLOCK(x, i, &x_qn);
396     }
397
398     v = y->v;
399     free_node(ptst, y);
400     NODE_UNLOCK(y, &y_qn);
401
402  out:
403     LIST_UNLOCK(l, &l_qn);
404     critical_exit(ptst);
405     return(v);
406 }
407
408
409 setval_t set_lookup(set_t *l, setkey_t k)
410 {
411     setval_t  v = NULL;
412     ptst_t    *ptst;
413     sh_node_pt x;
414
415     k = CALLER_TO_INTERNAL_KEY(k);
416
417     ptst = critical_enter();
418
419     x = search_predecessors(l, k, NULL);
420     if ( x->k == k ) READ_FIELD(v, x->v);
421
422     critical_exit(ptst);
423     return(v);
424 }
425
426
427 void _init_set_subsystem(void)
428 {
429     int i;
430
431     for ( i = 0; i < NUM_LEVELS; i++ )
432     {
433         gc_id[i] = gc_add_allocator(sizeof(node_t) + i*sizeof(ptr_t));
434     }
435 }