afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / stm_herlihy.c
1 /******************************************************************************
2  * stm_herlihy.c
3  *
4  * Obstruction-free software transactional memory (STM).
5  *
6  * For more information see:
7  *  Software Transactional Memory for Dynamic-sized Data Structures
8  *  Maurice Herlihy, Victor Luchangco, Mark Moir, and William Scherer III
9  *  Proceedings of 2003 ACM Symposium on Principles of Distributed Computing
10  *
11  * Copyright (c) 2003, K A Fraser
12
13 Redistribution and use in source and binary forms, with or without
14 modification, are permitted provided that the following conditions are
15 met:
16
17     * Redistributions of source code must retain the above copyright
18     * notice, this list of conditions and the following disclaimer.
19     * Redistributions in binary form must reproduce the above
20     * copyright notice, this list of conditions and the following
21     * disclaimer in the documentation and/or other materials provided
22     * with the distribution.  Neither the name of the Keir Fraser
23     * nor the names of its contributors may be used to endorse or
24     * promote products derived from this software without specific
25     * prior written permission.
26
27 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
29 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
30 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
33 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
34 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
35 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
36 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
37 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38  */
39
40 #include "portable_defns.h"
41 #include "ptst.h"
42 #include "gc.h"
43 #include <assert.h>
44 #include <stdarg.h>
45 #include <stdlib.h>
46 #include <stdio.h>
47 #include <string.h>
48 #include <setjmp.h>
49 #include <signal.h>
50 #include <unistd.h>
51 #ifdef SPARC
52 #include <time.h>
53 #include <errno.h>
54 #endif
55
56 #define POLITE
57
58 typedef struct stm_loc_st stm_loc;
59 typedef struct stm_blk_st stm_blk;
60 typedef struct stm_tx_entry_st stm_tx_entry;
61 typedef struct stm_tx_st stm_tx;
62 typedef struct stm_st stm;
63
64 struct stm_loc_st {
65     unsigned long status; /* TXS_FAILED, TXS_SUCCESSFUL, descriptor. */
66     void   *old;
67     void   *new;
68 };
69
70 struct stm_blk_st {
71     stm_loc *loc;
72 };
73
74 struct stm_tx_entry_st {
75     stm_blk *b;
76     stm_loc *l;
77     void    *data;
78     stm_tx_entry *next;
79 };
80
81 struct stm_tx_st {
82     unsigned int status;
83     int rc;
84     stm_tx *next_free;
85     stm_tx_entry *reads;
86     stm_tx_entry *writes;
87     stm_tx_entry *alloc_ptr, *check;
88     void *dummy;
89     int gc_data_id, blk_size; /* copied from 'stm' structure */
90     sigjmp_buf *penv;
91 };
92
93 struct stm_st {
94     int gc_data_id;
95     int blk_size;
96 };
97
98 /* Private per-thread state. The array is indexed off ptst->id. */
99 typedef struct {
100     void *arena, *arena_lim;
101     stm_tx *next_descriptor;
102     stm_tx *cur_tx;
103 #ifdef SPARC
104     unsigned int random_counter;
105 #endif
106     CACHE_PAD(0);
107 } priv_t;
108
109 static priv_t priv_ptst[MAX_THREADS];
110 static int gc_blk_id;  /* Allocation id for block descriptors. */
111 static int gc_loc_id;  /* Allocation id for locators. */
112 static int do_padding; /* Should all allocations be padded to a cache line? */
113
114 #ifdef POLITE
115 #define MAX_RETRIES      8
116 #ifdef SPARC
117 #define MIN_LOG_BACKOFF  4
118 #define MAX_LOG_BACKOFF 31
119 #define RANDOM_BITS      8
120 #define RANDOM_SIZE      (1 << RANDOM_BITS)
121 #define RANDOM_MASK      (RANDOM_SIZE - 1)
122 static unsigned int rand_arr[RANDOM_SIZE];
123 #endif
124 #endif
125
126 static stm_blk *dummy_obj; /* Dummy object (used by red-black trees). */
127 static void *dummy_data;
128
129 #define ALLOCATOR_SIZE(_s) (do_padding ? CACHE_LINE_SIZE : (_s))
130
131 #define ARENA_SIZE      40960
132 #define DESCRIPTOR_SIZE  4096
133
134 #define TXS_IN_PROGRESS 0U
135 #define TXS_FAILED      1U
136 #define TXS_SUCCESSFUL  2U
137
138 #define is_descriptor(_p) (((unsigned long)(_p) & 3) == 0)
139 #define mk_descriptor(_p) ((stm_tx *)(_p))
140
141 /* Is transaction read-only? */
142 #define read_only(_t)         ((_t)->writes == NULL)
143
144 /* Is transaction definitely doomed to fail? */
145 #define is_stale(_t, _e) \
146     (((_t)->status != TXS_IN_PROGRESS) || ((_e)->b->loc != (_e)->l))
147
148 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t);
149
150 static void new_arena (priv_t *priv, int size)
151 {
152     priv->arena = malloc(size);
153     if ( priv->arena == NULL ) abort();
154     priv->arena_lim = (((char *) priv->arena) + size);
155 }
156
157 static void release_descriptor(ptst_t *ptst, stm_tx *t)
158 {
159     stm_tx_entry *ent;
160     priv_t *priv = &priv_ptst[ptst->id];
161     void *data;
162
163     t->next_free = priv->next_descriptor;
164     priv->next_descriptor = t;
165 }
166
167 static int rc_delta_descriptor(stm_tx *t, int delta)
168 {
169     int rc, new_rc = t->rc;
170
171     do { rc = new_rc; }
172     while ( (new_rc = CASIO (&t->rc, rc, rc + delta)) != rc );
173
174     return rc;
175 }
176
177 static void rc_up_descriptor(stm_tx *t)
178 {
179     rc_delta_descriptor(t, 2);
180     MB();
181 }
182
183 static void rc_down_descriptor(ptst_t *ptst, stm_tx *t)
184 {
185     int old_rc, new_rc, cur_rc = t->rc;
186
187     WMB();
188
189     do {
190         old_rc = cur_rc;
191         new_rc = old_rc - 2;
192         if ( new_rc == 0 ) new_rc = 1;
193     }
194     while ( (cur_rc = CASIO (&t->rc, old_rc, new_rc)) != old_rc );
195
196     if ( old_rc == 2 ) release_descriptor(ptst, t);
197 }
198
199 static stm_tx *new_descriptor(priv_t *priv)
200 {
201     stm_tx *t;
202
203     t = priv->next_descriptor;
204
205     if ( t != NULL )
206     {
207         priv->next_descriptor = t->next_free;
208         /* 'Unfree' descriptor, if it was previously freed. */
209         if ( (t->rc & 1) == 1 ) rc_delta_descriptor(t, 1);
210     }
211     else
212     {
213         t = (stm_tx *) priv->arena;
214         priv->arena = ((char *) (priv->arena)) + DESCRIPTOR_SIZE;
215
216         if ( priv->arena >= priv->arena_lim )
217         {
218             new_arena(priv, ARENA_SIZE);
219             t = (stm_tx *) priv->arena;
220             priv->arena = ((char *) (priv->arena)) + DESCRIPTOR_SIZE;
221         }
222
223         t->next_free = NULL;
224         t->rc = 2;
225     }
226
227     return t;
228 }
229
230
231 static stm_tx_entry *alloc_stm_tx_entry(stm_tx *t)
232 {
233     stm_tx_entry *ent = t->alloc_ptr++;
234     assert(((unsigned long)t->alloc_ptr - (unsigned long)t) <=
235            DESCRIPTOR_SIZE);
236     return ent;
237 }
238
239
240 static stm_tx_entry **search_stm_tx_entry(stm_tx_entry **pnext, stm_blk *b)
241 {
242     stm_tx_entry *next = *pnext;
243
244     while ( (next != NULL) && ((unsigned long)next->b < (unsigned long)b) )
245     {
246         pnext = &next->next;
247         next  = *pnext;
248     }
249
250     return pnext;
251 }
252
253
254 static int contention_wait(ptst_t *ptst, int attempts)
255 {
256 #ifdef POLITE
257     if ( (attempts > 1) && (attempts <= MAX_RETRIES) )
258     {
259 #ifdef SPARC /* Exactly as it was done by the original authors. */
260         priv_t *priv = &priv_ptst[ptst->id];
261         struct timespec rqtp;
262         unsigned int log_backoff, mask;
263         log_backoff = attempts - 2 + MIN_LOG_BACKOFF;
264         if ( log_backoff > MAX_LOG_BACKOFF )
265             log_backoff = MAX_LOG_BACKOFF;
266         mask = (1 << log_backoff) - 1;
267         rqtp.tv_nsec = rand_arr[priv->random_counter++ & RANDOM_MASK] & mask;
268         rqtp.tv_sec  = 0;
269         while ( nanosleep(&rqtp, NULL) != 0 ) continue;
270 #else
271         usleep(1);
272 #endif
273     }
274
275     return attempts < MAX_RETRIES;
276 #else
277     return FALSE;
278 #endif
279 }
280
281
282 static void *read_loc_data(ptst_t *ptst, stm_loc *l)
283 {
284     void           *data;
285     stm_tx         *t;
286     unsigned long   st;
287     stm_tx_entry  **pent;
288     int attempts = 0;
289
290     for ( ; ; )
291     {
292         switch ( (st = l->status) )
293         {
294         case TXS_SUCCESSFUL:
295             return l->new;
296         case TXS_FAILED:
297             return l->old;
298         default:
299             t = mk_descriptor(st);
300             rc_up_descriptor(t);
301             if ( l->status == st )
302             {
303                 switch ( t->status )
304                 {
305                 case TXS_SUCCESSFUL:
306                     rc_down_descriptor(ptst, t);
307                     l->status = TXS_SUCCESSFUL;
308                     return l->new;
309                 case TXS_FAILED:
310                     rc_down_descriptor(ptst, t);
311                     l->status = TXS_FAILED;
312                     return l->old;
313                 default:
314                     if ( !contention_wait(ptst, ++attempts) )
315                     {
316                         attempts = 0;
317                         CASIO(&t->status, TXS_IN_PROGRESS, TXS_FAILED);
318                     }
319                 }
320             }
321             rc_down_descriptor(ptst, t);
322         }
323     }
324 }
325
326
327 static stm_loc *install_loc(ptst_t *ptst, stm_tx *t,
328                             stm_blk *b, stm_loc *old_loc)
329 {
330     stm_loc *new_loc = gc_alloc(ptst, gc_loc_id);
331
332     new_loc->status = (unsigned long)t;
333     new_loc->new    = gc_alloc(ptst, t->gc_data_id);
334     new_loc->old    = read_loc_data(ptst, old_loc);
335     memcpy(new_loc->new, new_loc->old, t->blk_size);
336
337     if ( CASPO(&b->loc, old_loc, new_loc) != old_loc )
338     {
339         gc_unsafe_free(ptst, new_loc->new, t->gc_data_id);
340         gc_unsafe_free(ptst, new_loc     , gc_loc_id);
341         new_loc = NULL;
342     }
343     else
344     {
345         gc_free(ptst, old_loc, gc_loc_id);
346     }
347
348     return new_loc;
349 }
350
351
352 stm *new_stm(ptst_t *ptst, int blk_size)
353 {
354     stm *mem = malloc(CACHE_LINE_SIZE);
355     mem->blk_size = blk_size;
356     mem->gc_data_id = gc_add_allocator(ALLOCATOR_SIZE(blk_size));
357     return mem;
358 }
359
360
361 void free_stm(ptst_t *ptst, stm *mem)
362 {
363     gc_remove_allocator(mem->gc_data_id);
364     free(mem);
365 }
366
367
368 stm_blk *new_stm_blk(ptst_t *ptst, stm *mem)
369 {
370     stm_blk *b = gc_alloc(ptst, gc_blk_id);
371     stm_loc *l = gc_alloc(ptst, gc_loc_id);
372     b->loc     = l;
373     l->status  = TXS_SUCCESSFUL;
374     l->old     = NULL;
375     l->new     = gc_alloc(ptst, mem->gc_data_id);
376     return b;
377 }
378
379
380 void free_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
381 {
382     stm_loc *l;
383     void    *data;
384
385     l    = FASPO(&b->loc, NULL);
386     data = read_loc_data(ptst, l);
387
388     gc_free(ptst, data, mem->gc_data_id);
389     gc_free(ptst, l, gc_loc_id);
390     gc_free(ptst, b, gc_blk_id);
391 }
392
393
394 void *init_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
395 {
396     return b->loc->new;
397 }
398
399
400 int sizeof_stm_blk(ptst_t *ptst, stm *mem, stm_blk *b)
401 {
402     return mem->blk_size;
403 }
404
405
406 stm_tx *new_stm_tx(ptst_t *ptst, stm *mem, sigjmp_buf *penv)
407 {
408     priv_t *priv = &priv_ptst[ptst->id];
409     stm_tx *t;
410
411     if ( priv->cur_tx != NULL ) goto nesting;
412     t = new_descriptor(priv);
413     t->status = TXS_IN_PROGRESS;
414     t->reads = t->writes = NULL;
415     t->alloc_ptr = t->check = (stm_tx_entry *)(t + 1);
416     t->gc_data_id = mem->gc_data_id;
417     t->blk_size = mem->blk_size;
418     t->penv = penv;
419     t->dummy = NULL;
420     priv->cur_tx = t;
421     return t;
422
423  nesting:
424     fprintf(stderr, "No nesting of transactions is allowed\n");
425     return NULL;
426 }
427
428
429 bool_t commit_stm_tx(ptst_t *ptst, stm_tx *t)
430 {
431     unsigned int desired_st = TXS_SUCCESSFUL, st;
432     stm_tx_entry *ent;
433     priv_t *priv = &priv_ptst[ptst->id];
434
435     priv->cur_tx = NULL;
436
437     MB();
438
439     for ( ent = t->reads; ent != NULL; ent = ent->next )
440     {
441         if ( ent->b->loc != ent->l )
442             desired_st = TXS_FAILED;
443     }
444
445     if ( read_only(t) )
446     {
447         /* A very fast path: we can immediately reuse the descriptor. */
448         if ( t->dummy != NULL )
449             gc_unsafe_free(ptst, t->dummy, t->gc_data_id);
450         t->next_free = priv->next_descriptor;
451         priv->next_descriptor = t;
452         return desired_st == TXS_SUCCESSFUL;
453     }
454
455     st = CASIO(&t->status, TXS_IN_PROGRESS, desired_st);
456     if ( st == TXS_IN_PROGRESS )
457         st = desired_st;
458
459     assert((st == TXS_FAILED) || (st == TXS_SUCCESSFUL));
460
461     WMB_NEAR_CAS();
462
463     for ( ent = t->writes; ent != NULL; ent = ent->next )
464     {
465         ent->l->status = (unsigned long)st;
466         gc_free(ptst,
467                 (st == TXS_SUCCESSFUL) ? ent->l->old : ent->l->new,
468                 t->gc_data_id);
469     }
470
471     if ( t->dummy != NULL )
472         gc_unsafe_free(ptst, t->dummy, t->gc_data_id);
473
474     rc_down_descriptor(ptst, t);
475
476     return st == TXS_SUCCESSFUL;
477 }
478
479
480 bool_t validate_stm_tx(ptst_t *ptst, stm_tx *t)
481 {
482     stm_tx_entry *ent;
483
484     RMB();
485
486     /* A conflict on a pending update will cause us to get failed. */
487     if ( t->status == TXS_FAILED )
488         goto fail;
489
490     /* Reads must be explicitly checked. */
491     for ( ent = t->reads; ent != NULL; ent = ent->next )
492     {
493         if ( ent->b->loc != ent->l )
494             goto fail;
495     }
496
497     return TRUE;
498
499  fail:
500     t->status = TXS_FAILED;
501     return FALSE;
502 }
503
504
505 void abort_stm_tx(ptst_t *ptst, stm_tx *t)
506 {
507     t->status = TXS_FAILED;
508 }
509
510
511 void *read_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
512 {
513     stm_tx_entry **pent, *ent;
514     sigjmp_buf *penv;
515     void *result;
516
517     if ( b == dummy_obj )
518     {
519         if ( t->dummy == NULL )
520         {
521             t->dummy = gc_alloc(ptst, t->gc_data_id);
522             memcpy(t->dummy, dummy_data, t->blk_size);
523         }
524         return t->dummy;
525     }
526
527     pent = search_stm_tx_entry(&t->writes, b);
528     ent  = *pent;
529     if ( (ent != NULL) && (ent->b == b) ) goto found;
530
531     pent = search_stm_tx_entry(&t->reads, b);
532     ent  = *pent;
533     if ( (ent != NULL) && (ent->b == b) ) goto found;
534
535     ent = alloc_stm_tx_entry(t);
536     ent->b    = b;
537     if ( (ent->l = b->loc) == NULL )
538         goto fail;
539     ent->data = read_loc_data(ptst, ent->l);
540     ent->next = *pent;
541     *pent = ent;
542
543     return ent->data;
544
545  found:
546     result = ent->data;
547     ent = t->check;
548     if ( is_stale(t, ent) ) goto fail;
549     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
550     return result;
551
552  fail:
553     penv = t->penv;
554     abort_stm_tx(ptst, t);
555     commit_stm_tx(ptst, t);
556     siglongjmp(*penv, 0);
557     assert(0);
558     return NULL;
559 }
560
561
562 void *write_stm_blk(ptst_t *ptst, stm_tx *t, stm_blk *b)
563 {
564     stm_tx_entry **r_pent, **w_pent, *ent;
565     stm_loc *loc;
566     sigjmp_buf *penv;
567     void *result;
568
569     if ( b == dummy_obj )
570     {
571         if ( t->dummy == NULL )
572         {
573             t->dummy = gc_alloc(ptst, t->gc_data_id);
574             memcpy(t->dummy, dummy_data, t->blk_size);
575         }
576         return t->dummy;
577     }
578
579     w_pent = search_stm_tx_entry(&t->writes, b);
580     ent = *w_pent;
581     if ( (ent != NULL) && (ent->b == b) ) goto found;
582
583     r_pent = search_stm_tx_entry(&t->reads, b);
584     ent = *r_pent;
585     if ( (ent != NULL) && (ent->b == b) )
586     {
587         *r_pent = ent->next;
588     }
589     else
590     {
591         ent       = alloc_stm_tx_entry(t);
592         ent->b    = b;
593         if ( (ent->l = b->loc) == NULL )
594             goto fail;
595     }
596
597     loc = install_loc(ptst, t, b, ent->l);
598     if ( loc == NULL ) goto fail;
599
600     ent->l    = loc;
601     ent->data = loc->new;
602     ent->next = *w_pent;
603     *w_pent = ent;
604
605     return ent->data;
606
607  found:
608     result = ent->data;
609     ent = t->check;
610     if ( is_stale(t, ent) ) goto fail;
611     if ( ++t->check == t->alloc_ptr ) t->check = (stm_tx_entry *)(t + 1);
612     return result;
613
614  fail:
615     penv = t->penv;
616     abort_stm_tx(ptst, t);
617     commit_stm_tx(ptst, t);
618     siglongjmp(*penv, 0);
619     assert(0);
620     return NULL;
621 }
622
623
624 void remove_from_tx(ptst_t *ptst, stm_tx *t, stm_blk *b)
625 {
626     if ( dummy_obj == NULL )
627     {
628         dummy_obj  = b;
629         dummy_data = read_loc_data(ptst, b->loc);
630     }
631 }
632
633
634 static void handle_fault(int sig)
635 {
636     ptst_t *ptst;
637     stm_tx *t;
638
639     ptst = critical_enter();
640     t = priv_ptst[ptst->id].cur_tx;
641     if ( (t != NULL) && !validate_stm_tx(ptst, t) )
642     {
643         sigjmp_buf *penv = t->penv;
644         commit_stm_tx(ptst, t);
645         critical_exit(ptst);
646         siglongjmp(*penv, 0);
647     }
648
649  fail:
650     fprintf(stderr, "Error: unhandleable SIGSEGV!\n");
651     abort();
652 }
653
654
655 void _init_stm_subsystem(int pad_data)
656 {
657     struct sigaction act;
658
659 #ifdef SPARC
660     int i;
661     struct timespec rqtp;
662
663     rqtp.tv_sec  = 0;
664     rqtp.tv_nsec = 1000;
665
666     while ( nanosleep(&rqtp, NULL) != 0 )
667     {
668         if ( errno != EINTR )
669         {
670             printf("Urk! Nanosleep not supported!\n");
671             exit(1);
672         }
673     }
674
675     for ( i = 0; i < RANDOM_SIZE; i++ )
676         rand_arr[i] = (unsigned int)random();
677 #endif
678
679     do_padding = pad_data;
680     gc_blk_id = gc_add_allocator(ALLOCATOR_SIZE(sizeof(stm_blk)));
681     gc_loc_id = gc_add_allocator(ALLOCATOR_SIZE(sizeof(stm_loc)));
682     memset(priv_ptst, 0, sizeof(priv_ptst));
683
684     act.sa_handler = handle_fault;
685     sigemptyset(&act.sa_mask);
686     act.sa_flags = 0;
687     sigaction(SIGSEGV, &act, NULL);
688 }