pad struct to improve hazard performance, fix off-by-one error
[nbds] / runtime / 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 } __attribute__ ((aligned(CACHE_LINE_SIZE))) 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     assert(l->pending_size > l->pending_count);
118     l->pending[ l->pending_count ].ptr   = d;
119     l->pending[ l->pending_count ].free_ = f;
120     l->pending_count++;
121 }
122
123 haz_t *haz_get_static (int i) {
124     if (i >= STATIC_HAZ_PER_THREAD)
125         return NULL;
126     LOCALIZE_THREAD_LOCAL(tid_, int);
127     assert(i < STATIC_HAZ_PER_THREAD);
128     return &haz_local_[tid_].static_haz[i];
129 }
130
131 void haz_register_dynamic (haz_t *haz) {
132     LOCALIZE_THREAD_LOCAL(tid_, int);
133     haz_local_t *l = haz_local_ + tid_;
134
135     if (l->dynamic_size == 0) {
136         int n = MAX_NUM_THREADS * STATIC_HAZ_PER_THREAD;
137         l->dynamic = nbd_malloc(sizeof(haz_t *) * n);
138         l->dynamic_size = n;
139     }
140
141     if (l->dynamic_count == l->dynamic_size) {
142         haz_t **d = nbd_malloc(sizeof(haz_t *) * l->dynamic_size * 2);
143         memcpy(d, l->dynamic, l->dynamic_size);
144         nbd_free(l->dynamic);
145         l->dynamic = d;
146         l->dynamic_size *= 2;
147     }
148
149     l->dynamic[ l->dynamic_count++ ] = haz;
150 }
151
152 // assumes <haz> was registered in the same thread
153 void haz_unregister_dynamic (void **haz) {
154     LOCALIZE_THREAD_LOCAL(tid_, int);
155     haz_local_t *l = haz_local_ + tid_;
156
157     for (int i = 0; i < l->dynamic_count; ++i) {
158         if (l->dynamic[i] == haz) {
159             if (i != l->dynamic_count - 1) {
160                 l->dynamic[i] = l->dynamic[ l->dynamic_count - 1 ];
161             }
162             l->dynamic_count--;
163             return;
164         }
165     }
166     assert(0);
167 }