]> pd.if.org Git - nbds/blob - hazard.c
72ed0c12c609d4de0f04854948fdf81c7d59e3ff
[nbds] / hazard.c
1 /* 
2  * Written by Josh Dybnis and released to the public domain, as explained at
3  * http://creativecommons.org/licenses/publicdomain
4  *
5  * hazard pointers
6  *
7  * www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
8  *
9  */
10 #include "common.h"
11 #include "lwt.h"
12 #include "mem.h"
13 #include "tls.h"
14 #include "runtime.h"
15 #include "hazard.h"
16
17 typedef struct pending {
18     void * ptr; 
19     free_t free_; 
20 } pending_t;
21
22 typedef struct haz_local {
23     pending_t *pending; // to be freed
24     int pending_size;
25     int pending_count;
26
27     haz_t static_haz[STATIC_HAZ_PER_THREAD];
28
29     haz_t **dynamic;
30     int dynamic_size;
31     int dynamic_count;
32
33 } haz_local_t;
34
35 static haz_local_t haz_local_[MAX_NUM_THREADS] = {};
36
37 static void sort_hazards (haz_t *hazards, int n) {
38     return;
39 }
40
41 static int search_hazards (void *p, haz_t *hazards, int n) {
42     for (int i = 0; i < n; ++i) {
43         if (hazards[i] == p) 
44             return TRUE;
45     }
46     return FALSE;
47 }
48
49 static void resize_pending (void) {
50     LOCALIZE_THREAD_LOCAL(tid_, int);
51     haz_local_t *l = haz_local_ + tid_;
52     pending_t *p = nbd_malloc(sizeof(pending_t) * l->pending_size * 2);
53     memcpy(p, l->pending, l->pending_size);
54     nbd_free(l->pending);
55     l->pending = p;
56     l->pending_size *= 2;
57 }
58
59 void haz_defer_free (void *d, free_t f) {
60     assert(d);
61     assert(f);
62     LOCALIZE_THREAD_LOCAL(tid_, int);
63     haz_local_t *l = haz_local_ + tid_;
64     while (l->pending_count == l->pending_size) {
65
66         if (l->pending_size == 0) {
67             l->pending_size = MAX_NUM_THREADS * STATIC_HAZ_PER_THREAD;
68             l->pending = nbd_malloc(sizeof(pending_t) * l->pending_size);
69             break;
70         }
71
72         // scan for hazard pointers
73         haz_t *hazards = nbd_malloc(sizeof(haz_t) * l->pending_size);
74         int    hazard_count = 0;
75         for (int i = 0; i < MAX_NUM_THREADS; ++i) {
76             haz_local_t *h = haz_local_ + i;
77             for (int j = 0; j < STATIC_HAZ_PER_THREAD; ++j) {
78                 if (h->static_haz[j] != NULL) {
79                     if (hazard_count == l->pending_size) {
80                         resize_pending();
81                         nbd_free(hazards);
82                         haz_defer_free(d, f);
83                         return;
84                     }
85                     hazards[hazard_count++] = h->static_haz[j];
86                 }
87             }
88             for (int j = 0; j < h->dynamic_count; ++j) {
89                 if (h->dynamic[j] != NULL && *h->dynamic[j] != NULL) {
90                     if (hazard_count == l->pending_size) {
91                         resize_pending();
92                         nbd_free(hazards);
93                         haz_defer_free(d, f);
94                         return;
95                     }
96                     hazards[hazard_count++] = *h->dynamic[j];
97                 }
98             }
99         }
100         sort_hazards(hazards, hazard_count);
101
102         // check for conflicts
103         int  conflicts_count = 0;
104         for (int i = 0; i < l->pending_count; ++i) {
105             pending_t *p = l->pending + i;
106             if (search_hazards(p->ptr, hazards, hazard_count)) {
107                 l->pending[conflicts_count++] = *p; // put conflicts back on the pending list
108             } else {
109                 assert(p->free_);
110                 assert(p->ptr);
111                 p->free_(p->ptr); // free pending item
112             }
113         }
114         l->pending_count = conflicts_count;
115         nbd_free(hazards);
116     }
117     l->pending[ l->pending_count ].ptr  = d;
118     l->pending[ l->pending_count ].free_ = f;
119     l->pending_count++;
120 }
121
122 haz_t *haz_get_static (int i) {
123     if (i >= STATIC_HAZ_PER_THREAD)
124         return NULL;
125     LOCALIZE_THREAD_LOCAL(tid_, int);
126     return &haz_local_[tid_].static_haz[i];
127 }
128
129 void haz_register_dynamic (haz_t *haz) {
130     LOCALIZE_THREAD_LOCAL(tid_, int);
131     haz_local_t *l = haz_local_ + tid_;
132
133     if (l->dynamic_size == 0) {
134         l->dynamic_size = MAX_NUM_THREADS * STATIC_HAZ_PER_THREAD;
135         l->dynamic = nbd_malloc(sizeof(haz_t *) * l->dynamic_size);
136     }
137
138     if (l->dynamic_count == l->dynamic_size) {
139         haz_t **d = nbd_malloc(sizeof(haz_t *) * l->dynamic_size * 2);
140         memcpy(d, l->dynamic, l->dynamic_size);
141         nbd_free(l->dynamic);
142         l->dynamic = d;
143         l->dynamic_size *= 2;
144     }
145
146     l->dynamic[ l->dynamic_count++ ] = haz;
147 }
148
149 // assumes <haz> was registered in the same thread
150 void haz_unregister_dynamic (void **haz) {
151     LOCALIZE_THREAD_LOCAL(tid_, int);
152     haz_local_t *l = haz_local_ + tid_;
153
154     for (int i = 0; i < l->dynamic_count; ++i) {
155         if (l->dynamic[i] == haz) {
156             if (i != l->dynamic_count - 1) {
157                 l->dynamic[i] = l->dynamic[ l->dynamic_count ];
158             }
159             l->dynamic_count--;
160             return;
161         }
162     }
163     assert(0);
164 }