afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / skip_stm.c
1 /******************************************************************************
2  * skip_stm.c
3  *
4  * Skip lists, allowing concurrent update by use of the STM abstraction.
5  *
6  * Copyright (c) 2003, K A Fraser
7  *
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 <unistd.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <assert.h>
42 #include "portable_defns.h"
43 #include "gc.h"
44 #include "stm.h"
45 #include "set.h"
46
47 typedef struct node_st node_t;
48 typedef stm_blk set_t;
49
50 struct node_st
51 {
52     int       level;
53     setkey_t  k;
54     setval_t  v;
55     stm_blk  *next[NUM_LEVELS];
56 };
57
58 static struct {
59     CACHE_PAD(0);
60     stm *memory;    /* read-only */
61     CACHE_PAD(2);
62 } shared;
63
64 #define MEMORY (shared.memory)
65
66 /*
67  * Random level generator. Drop-off rate is 0.5 per level.
68  * Returns value 1 <= level <= NUM_LEVELS.
69  */
70 static int get_level(ptst_t *ptst)
71 {
72     unsigned long r = rand_next(ptst);
73     int l = 1;
74     r = (r >> 4) & ((1 << (NUM_LEVELS-1)) - 1);
75     while ( (r & 1) ) { l++; r >>= 1; }
76     return l;
77 }
78
79
80 /*
81  * Search for first non-deleted node, N, with key >= @k at each level in @l.
82  * RETURN VALUES:
83  *  Array @pa: @pa[i] is non-deleted predecessor of N at level i
84  *  Array @na: @na[i] is N itself, which should be pointed at by @pa[i]
85  *  MAIN RETURN VALUE: same as @na[0], direct pointer open for reading.
86  */
87 static node_t *search_predecessors(
88     ptst_t *ptst, stm_tx *tx, set_t *l, setkey_t k, stm_blk **pa, stm_blk **na)
89 {
90     stm_blk *xb, *x_nextb;
91     node_t  *x,  *x_next;
92     int      i;
93
94     xb = l;
95     x  = read_stm_blk(ptst, tx, l);
96     for ( i = NUM_LEVELS - 1; i >= 0; i-- )
97     {
98         for ( ; ; )
99         {
100             x_nextb = x->next[i];
101             x_next  = read_stm_blk(ptst, tx, x_nextb);
102             if ( x_next->k >= k ) break;
103             xb = x_nextb;
104             x  = x_next;
105         }
106
107         if ( pa ) pa[i] = xb;
108         if ( na ) na[i] = x_nextb;
109     }
110
111     return x_next;
112 }
113
114
115 /*
116  * PUBLIC FUNCTIONS
117  */
118
119 set_t *set_alloc(void)
120 {
121     ptst_t  *ptst;
122     stm_blk *hb, *tb;
123     node_t  *h, *t;
124     int      i;
125
126     ptst = critical_enter();
127
128     tb = new_stm_blk(ptst, MEMORY);
129     t  = init_stm_blk(ptst, MEMORY, tb);
130     memset(t, 0, sizeof(*t));
131     t->k = SENTINEL_KEYMAX;
132
133     hb = new_stm_blk(ptst, MEMORY);
134     h  = init_stm_blk(ptst, MEMORY, hb);
135     memset(h, 0, sizeof(*h));
136     h->k     = SENTINEL_KEYMIN;
137     h->level = NUM_LEVELS;
138     for ( i = 0; i < NUM_LEVELS; i++ )
139         h->next[i] = tb;
140
141     critical_exit(ptst);
142
143     return hb;
144 }
145
146
147 setval_t set_update(set_t *l, setkey_t k, setval_t v, int overwrite)
148 {
149     ptst_t   *ptst;
150     stm_tx   *tx;
151     setval_t  ov;
152     stm_blk  *bpreds[NUM_LEVELS], *bsuccs[NUM_LEVELS], *newb = NULL;
153     node_t   *x, *p, *new;
154     int       i;
155
156     k = CALLER_TO_INTERNAL_KEY(k);
157
158     ptst = critical_enter();
159
160     do {
161         new_stm_tx(tx, ptst, MEMORY);
162         x = search_predecessors(ptst, tx, l, k, bpreds, bsuccs);
163
164         if ( x->k == k )
165         {
166             x    = write_stm_blk(ptst, tx, bsuccs[0]);
167             ov   = x->v;
168             x->v = v;
169         }
170         else
171         {
172             ov = NULL;
173
174             if ( newb == NULL )
175             {
176                 newb = new_stm_blk(ptst, MEMORY);
177                 new  = init_stm_blk(ptst, MEMORY, newb);
178                 new->k = k;
179                 new->v = v;
180                 new->level = get_level(ptst);
181             }
182
183             for ( i = 0; i < new->level; i++ )
184             {
185                 new->next[i] = bsuccs[i];
186                 p = write_stm_blk(ptst, tx, bpreds[i]);
187                 p->next[i] = newb;
188             }
189         }
190     }
191     while ( !commit_stm_tx(ptst, tx) );
192
193     if ( (ov != NULL) && (newb != NULL) )
194         free_stm_blk(ptst, MEMORY, newb);
195
196     critical_exit(ptst);
197
198     return ov;
199 }
200
201
202 setval_t set_remove(set_t *l, setkey_t k)
203 {
204     setval_t  v;
205     ptst_t   *ptst;
206     stm_tx   *tx;
207     stm_blk  *bpreds[NUM_LEVELS], *bsuccs[NUM_LEVELS];
208     node_t   *p, *x;
209     int       i;
210
211     k = CALLER_TO_INTERNAL_KEY(k);
212
213     ptst = critical_enter();
214
215     do {
216         new_stm_tx(tx, ptst, MEMORY);
217         x = search_predecessors(ptst, tx, l, k, bpreds, bsuccs);
218         if ( x->k == k )
219         {
220             v = x->v;
221             for ( i = 0; i < x->level; i++ )
222             {
223                 p = write_stm_blk(ptst, tx, bpreds[i]);
224                 p->next[i] = x->next[i];
225             }
226         }
227         else
228         {
229             v = NULL;
230         }
231     }
232     while ( !commit_stm_tx(ptst, tx) );
233
234     if ( v != NULL )
235         free_stm_blk(ptst, MEMORY, bsuccs[0]);
236
237     critical_exit(ptst);
238
239     return v;
240 }
241
242
243 setval_t set_lookup(set_t *l, setkey_t k)
244 {
245     setval_t  v;
246     ptst_t   *ptst;
247     stm_tx   *tx;
248     node_t   *x;
249
250     k = CALLER_TO_INTERNAL_KEY(k);
251
252     ptst = critical_enter();
253
254     do {
255         new_stm_tx(tx, ptst, MEMORY);
256         x = search_predecessors(ptst, tx, l, k, NULL, NULL);
257         v = (x->k == k) ? x->v : NULL;
258     }
259     while ( !commit_stm_tx(ptst, tx) );
260
261     critical_exit(ptst);
262
263     return v;
264 }
265
266
267 void _init_set_subsystem(void)
268 {
269     ptst_t *ptst = critical_enter();
270     _init_stm_subsystem(0);
271     MEMORY = new_stm(ptst, sizeof(node_t));
272     critical_exit(ptst);
273 }