afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / stm_lock.c
1 /******************************************************************************
2  * stm_lock.c
3  *
4  * Lock-based software transactional memory (STM).
5  * Uses two-phase locking with multi-reader locks.
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 #include "portable_defns.h"
37 #include "ptst.h"
38 #include "gc.h"
39 #include <assert.h>
40 #include <stdarg.h>
41 #include <stdlib.h>
42 #include <stdio.h>
43 #include <string.h>
44 #include <setjmp.h>
45 #include <signal.h>
46
47 typedef struct stm_blk_st stm_blk;
48 typedef struct stm_tx_entry_st stm_tx_entry;
49 typedef struct stm_tx_st stm_tx;
50 typedef struct stm_st stm;
51
52 struct stm_blk_st {
53     void *data;
54     mrsw_lock_t lock;
55 };
56
57 struct stm_tx_entry_st {
58     stm_blk *b;
59     void    *old;
60     void    *new;
61     stm_tx_entry *next;
62 };
63
64 struct stm_tx_st {
65     int status;
66     stm_tx_entry *blocks;
67     stm_tx_entry *alloc_ptr, *check;
68     int gc_data_id, blk_size; /* copied from 'stm' structure */
69     sigjmp_buf *penv;
70 };
71
72 struct stm_st {
73     int gc_data_id;
74     int blk_size;
75 };
76
77 #define DESCRIPTOR_IN_USE(_t) ((_t)->penv != NULL)
78
79 #define DESCRIPTOR_SIZE  4096
80 #define MAX_TX_ENTS      (DESCRIPTOR_SIZE / sizeof(stm_tx_entry))
81
82 /* Private per-thread state. The array is indexed off ptst->id. */
83 typedef struct {
84     char desc[DESCRIPTOR_SIZE];
85 } priv_t;
86
87 static priv_t priv_ptst[MAX_THREADS];
88 static int gc_blk_id;  /* Allocation id for block descriptors. */
89 static int do_padding; /* Should all allocations be padded to a cache line? */
90
91 #define ALLOCATOR_SIZE(_s) (do_padding ? CACHE_LINE_SIZE : (_s))
92
93 #define TXS_IN_PROGRESS 0
94 #define TXS_FAILED      1
95 #define TXS_SUCCESSFUL  2
96
97 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t);
98
99 static stm_tx_entry *alloc_stm_tx_entry(stm_tx *t)
100 {
101     stm_tx_entry *ent = t->alloc_ptr++;
102     assert(((unsigned long)t->alloc_ptr - (unsigned long)t) <=
103            DESCRIPTOR_SIZE);
104     return ent;
105 }
106
107
108 static stm_tx_entry **search_stm_tx_entry(stm_tx_entry **pnext, stm_blk *b)
109 {
110     stm_tx_entry *next = *pnext;
111
112     while ( (next != NULL) && ((unsigned long)next->b < (unsigned long)b) )
113     {
114         pnext = &next->next;
115         next  = *pnext;
116     }
117
118     return pnext;
119 }
120
121
122 stm *new_stm(ptst_t *ptst, int blk_size)
123 {
124     stm *mem = malloc(CACHE_LINE_SIZE);
125     mem->blk_size = blk_size;
126     mem->gc_data_id = gc_add_allocator(ALLOCATOR_SIZE(blk_size));
127     return mem;
128 }
129
130
131 void free_stm(ptst_t *ptst, stm *mem)
132 {
133     gc_remove_allocator(mem->gc_data_id);
134     free(mem);
135 }
136
137
138 stm_blk *new_stm_blk(ptst_t *ptst, stm *mem)
139 {
140     stm_blk *b;
141     b       = gc_alloc(ptst, gc_blk_id);
142     b->data = gc_alloc(ptst, mem->gc_data_id);
143     mrsw_init(&b->lock);
144     return b;
145 }
146
147
148 void free_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
149 {
150     gc_free(ptst, b->data, mem->gc_data_id);
151     gc_free(ptst, b,       gc_blk_id);
152 }
153
154
155 void *init_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
156 {
157     return b->data;
158 }
159
160
161 int sizeof_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
162 {
163     return mem->blk_size;
164 }
165
166
167 stm_tx *new_stm_tx(ptst_t *ptst, stm *mem, sigjmp_buf *penv)
168 {
169     stm_tx *t = (stm_tx *)&priv_ptst[ptst->id];
170     if ( DESCRIPTOR_IN_USE(t) ) goto nesting;
171     t->status = TXS_IN_PROGRESS;
172     t->blocks = NULL;
173     t->alloc_ptr = t->check = (stm_tx_entry *)(t + 1);
174     t->gc_data_id = mem->gc_data_id;
175     t->blk_size = mem->blk_size;
176     t->penv = penv;
177     return t;
178
179  nesting:
180     fprintf(stderr, "No nesting of transactions is allowed\n");
181     return NULL;
182 }
183
184
185 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t)
186 {
187     stm_tx_entry *ent, *last_ent;
188     mrsw_qnode_t qn[MAX_TX_ENTS];
189     stm_blk *b;
190     void *old;
191     int i;
192
193     t->penv = NULL;
194
195     /* Outcome may have been decided by an 'abort' or 'validate' operation. */
196     if ( t->status != TXS_IN_PROGRESS ) goto out;
197
198     /* We start by taking locks in order, and checking old values. */
199     for ( i = 0, ent = t->blocks; ent != NULL; i++, ent = ent->next )
200     {
201         b = ent->b;
202         if ( (old = ent->old) == ent->new )
203         {
204             rd_lock(&b->lock, &qn[i]);
205         }
206         else
207         {
208             wr_lock(&b->lock, &qn[i]);
209         }
210         /* Check old value, and shortcut to failure if we mismatch. */
211         if ( b->data != old ) goto fail;
212     }
213
214     /*
215      * LINEARISATION POINT FOR SUCCESS:
216      * We haven't written new values yet, but that's okay as we have write
217      * locks on those locations. Noone can see old value now and yet still
218      * commit (as they'll be waiting for the read lock).
219      */
220     t->status = TXS_SUCCESSFUL;
221
222     /* We definitely succeed now: release locks and write new values. */
223     for ( i = 0, ent = t->blocks; ent != NULL; i++, ent = ent->next )
224     {
225         b = ent->b;
226         if ( ent->old == ent->new )
227         {
228             rd_unlock(&b->lock, &qn[i]);
229         }
230         else
231         {
232             b->data = ent->new;
233             wr_unlock(&b->lock, &qn[i]);
234         }
235     }
236
237  out:
238     if ( t->status == TXS_SUCCESSFUL )
239     {
240         for ( ent = t->blocks; ent != NULL; ent = ent->next )
241         {
242             if ( ent->old == ent->new ) continue;
243             gc_free(ptst, ent->old, t->gc_data_id);
244         }
245         return TRUE;
246     }
247     else
248     {
249         for ( ent = t->blocks; ent != NULL; ent = ent->next )
250         {
251             if ( ent->old == ent->new ) continue;
252             gc_unsafe_free(ptst, ent->new, t->gc_data_id);
253         }
254         return FALSE;
255     }
256
257     /*
258      * We put (hopefully rare) failure case out-of-line here.
259      * This is also the LINEARISTAION POINT FOR FAILURE.
260      */
261  fail:
262     last_ent = ent->next;
263     t->status = TXS_FAILED;
264     for ( i = 0, ent = t->blocks; ent != last_ent; i++, ent = ent->next )
265     {
266         b = ent->b;
267         if ( ent->old == ent->new )
268         {
269             rd_unlock(&b->lock, &qn[i]);
270         }
271         else
272         {
273             wr_unlock(&b->lock, &qn[i]);
274         }
275     }
276     goto out;
277 }
278
279
280 bool_t validate_stm_tx(ptst_t *ptst, stm_tx *t)
281 {
282     stm_tx_entry *ent, *last_ent = NULL;
283     mrsw_qnode_t qn[MAX_TX_ENTS];
284     stm_blk *b;
285     void *old;
286     int i;
287
288     RMB();
289
290     /* Lock-acquire phase */
291     for ( i = 0, ent = t->blocks; ent != NULL; i++, ent = ent->next )
292     {
293         b = ent->b;
294
295         if ( (old = ent->old) == ent->new )
296         {
297             rd_lock(&b->lock, &qn[i]);
298         }
299         else
300         {
301             wr_lock(&b->lock, &qn[i]);
302         }
303
304         if ( b->data != old )
305         {
306             t->status = TXS_FAILED;
307             last_ent = ent->next;
308             break;
309         }
310     }
311
312     /* Lock-release phase */
313     for ( i = 0, ent = t->blocks; ent != last_ent; i++, ent = ent->next )
314     {
315         b = ent->b;
316         if ( ent->old == ent->new )
317         {
318             rd_unlock(&b->lock, &qn[i]);
319         }
320         else
321         {
322             wr_unlock(&b->lock, &qn[i]);
323         }
324     }
325
326     return t->status != TXS_FAILED;
327 }
328
329
330 void abort_stm_tx(ptst_t *ptst, stm_tx *t)
331 {
332     t->status = TXS_FAILED;
333 }
334
335
336 void *read_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
337 {
338     stm_tx_entry **pent, *ent;
339     sigjmp_buf *penv;
340     void *result;
341
342     pent = search_stm_tx_entry(&t->blocks, b);
343     ent  = *pent;
344     if ( (ent != NULL) && (ent->b == b) ) goto found;
345
346     ent = alloc_stm_tx_entry(t);
347     ent->b    = b;
348     ent->old  = b->data;
349     ent->new  = ent->old;
350     ent->next = *pent;
351     *pent = ent;
352     return ent->new;
353
354  found:
355     result = ent->new;
356     ent = t->check;
357     if ( ent->b->data != ent->old ) goto fail;
358     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
359     return result;
360
361  fail:
362     penv = t->penv;
363     abort_stm_tx(ptst, t);
364     commit_stm_tx(ptst, t);
365     siglongjmp(*penv, 0);
366     assert(0);
367     return NULL;
368 }
369
370
371 void *write_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
372 {
373     stm_tx_entry **pent, *ent;
374     sigjmp_buf *penv;
375     void *result;
376
377     pent = search_stm_tx_entry(&t->blocks, b);
378     ent = *pent;
379     if ( (ent != NULL) && (ent->b == b) )
380     {
381         if ( ent->old != ent->new ) goto found;
382     }
383     else
384     {
385         ent = alloc_stm_tx_entry(t);
386         ent->b    = b;
387         ent->old  = b->data;
388         ent->next = *pent;
389         *pent = ent;
390     }
391
392     ent->new  = gc_alloc(ptst, t->gc_data_id);
393     memcpy(ent->new, ent->old, t->blk_size);
394     return ent->new;
395
396  found:
397     result = ent->new;
398     ent = t->check;
399     if ( ent->b->data != ent->old ) goto fail;
400     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
401     return result;
402
403  fail:
404     penv = t->penv;
405     abort_stm_tx(ptst, t);
406     commit_stm_tx(ptst, t);
407     siglongjmp(*penv, 0);
408     assert(0);
409     return NULL;
410 }
411
412
413 void remove_from_tx(ptst_t *ptst, stm_tx *t, stm_blk *b)
414 {
415     stm_tx_entry **pent, *ent;
416     void *data;
417
418     pent = search_stm_tx_entry(&t->blocks, b);
419     ent  = *pent;
420     if ( (ent != NULL) && (ent->b == b) )
421     {
422         *pent = ent->next;
423         if ( (data = ent->new) != ent->old )
424         {
425             gc_free(ptst, data, t->gc_data_id);
426         }
427     }
428 }
429
430
431 static void handle_fault(int sig)
432 {
433     ptst_t *ptst;
434     stm_tx *t;
435
436     ptst = critical_enter();
437     t = (stm_tx *)&priv_ptst[ptst->id];
438     if ( DESCRIPTOR_IN_USE(t) && !validate_stm_tx(ptst, t) )
439     {
440         sigjmp_buf *penv = t->penv;
441         commit_stm_tx(ptst, t);
442         critical_exit(ptst);
443         siglongjmp(*penv, 0);
444     }
445
446  fail:
447     fprintf(stderr, "Error: unhandleable SIGSEGV!\n");
448     abort();
449 }
450
451
452 void _init_stm_subsystem(int pad_data)
453 {
454     struct sigaction act;
455
456     do_padding = pad_data;
457     gc_blk_id = gc_add_allocator(ALLOCATOR_SIZE(sizeof(stm_blk)));
458     memset(priv_ptst, 0, sizeof(priv_ptst));
459
460     act.sa_handler = handle_fault;
461     sigemptyset(&act.sa_mask);
462     act.sa_flags = 0;
463     sigaction(SIGSEGV, &act, NULL);
464 }