2 * Written by Josh Dybnis and released to the public domain, as explained at
3 * http://creativecommons.org/licenses/publicdomain
7 * www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
18 typedef struct pending {
23 typedef struct haz_local {
24 pending_t *pending; // to be freed
28 haz_t static_haz[STATIC_HAZ_PER_THREAD];
34 } __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t;
36 static haz_local_t haz_local_[MAX_NUM_THREADS] = {};
38 static void sort_hazards (haz_t *hazards, int n) {
39 TRACE("H3", "sort_hazards: sorting hazard list %p of %p elements", hazards, n);
43 static int search_hazards (void *p, haz_t *hazards, int n) {
44 TRACE("H4", "search_hazards: searching list %p for hazard %p", hazards, p);
45 for (int i = 0; i < n; ++i) {
46 if (hazards[i] == p) {
47 TRACE("H2", "haz_search_hazards: found hazard %p", p, 0);
54 static void resize_pending (void) {
55 TRACE("H2", "haz_resize_pending", 0, 0);
56 LOCALIZE_THREAD_LOCAL(tid_, int);
57 haz_local_t *l = haz_local_ + tid_;
58 pending_t *p = nbd_malloc(sizeof(pending_t) * l->pending_size * 2);
59 memcpy(p, l->pending, l->pending_size);
65 void haz_defer_free (void *d, free_t f) {
66 TRACE("H1", "haz_defer_free: %p (%p)", d, f);
69 LOCALIZE_THREAD_LOCAL(tid_, int);
70 haz_local_t *l = haz_local_ + tid_;
71 while (l->pending_count == l->pending_size) {
73 if (l->pending_size == 0) {
74 l->pending_size = MAX_NUM_THREADS * STATIC_HAZ_PER_THREAD;
75 l->pending = nbd_malloc(sizeof(pending_t) * l->pending_size);
79 // scan for hazard pointers
80 haz_t *hazards = nbd_malloc(sizeof(haz_t) * l->pending_size);
82 for (int i = 0; i < MAX_NUM_THREADS; ++i) {
83 haz_local_t *h = haz_local_ + i;
84 for (int j = 0; j < STATIC_HAZ_PER_THREAD; ++j) {
85 if (h->static_haz[j] != NULL) {
86 if (hazard_count == l->pending_size) {
92 hazards[hazard_count++] = h->static_haz[j];
95 for (int j = 0; j < h->dynamic_count; ++j) {
96 if (h->dynamic[j] != NULL && *h->dynamic[j] != NULL) {
97 if (hazard_count == l->pending_size) {
100 haz_defer_free(d, f);
103 hazards[hazard_count++] = *h->dynamic[j];
107 sort_hazards(hazards, hazard_count);
109 // check for conflicts
110 int conflicts_count = 0;
111 for (int i = 0; i < l->pending_count; ++i) {
112 pending_t *p = l->pending + i;
113 if (search_hazards(p->ptr, hazards, hazard_count)) {
114 l->pending[conflicts_count++] = *p; // put conflicts back on the pending list
118 p->free_(p->ptr); // free pending item
121 l->pending_count = conflicts_count;
124 assert(l->pending_size > l->pending_count);
125 l->pending[ l->pending_count ].ptr = d;
126 l->pending[ l->pending_count ].free_ = f;
130 haz_t *haz_get_static (int i) {
131 TRACE("H1", "haz_get_static: %p", i, 0);
132 if (i >= STATIC_HAZ_PER_THREAD)
134 LOCALIZE_THREAD_LOCAL(tid_, int);
135 assert(i < STATIC_HAZ_PER_THREAD);
136 haz_t *ret = &haz_local_[tid_].static_haz[i];
137 TRACE("H1", "haz_get_static: returning %p", ret, 0);
141 void haz_register_dynamic (haz_t *haz) {
142 TRACE("H1", "haz_register_dynamic: %p", haz, 0);
143 LOCALIZE_THREAD_LOCAL(tid_, int);
144 haz_local_t *l = haz_local_ + tid_;
146 if (l->dynamic_size == 0) {
147 int n = MAX_NUM_THREADS * STATIC_HAZ_PER_THREAD;
148 l->dynamic = nbd_malloc(sizeof(haz_t *) * n);
152 if (l->dynamic_count == l->dynamic_size) {
153 haz_t **d = nbd_malloc(sizeof(haz_t *) * l->dynamic_size * 2);
154 memcpy(d, l->dynamic, l->dynamic_size);
155 nbd_free(l->dynamic);
157 l->dynamic_size *= 2;
160 l->dynamic[ l->dynamic_count++ ] = haz;
163 // assumes <haz> was registered in the same thread
164 void haz_unregister_dynamic (void **haz) {
165 TRACE("H1", "haz_unregister_dynamic: %p", haz, 0);
166 LOCALIZE_THREAD_LOCAL(tid_, int);
167 haz_local_t *l = haz_local_ + tid_;
169 for (int i = 0; i < l->dynamic_count; ++i) {
170 if (l->dynamic[i] == haz) {
171 if (i != l->dynamic_count - 1) {
172 l->dynamic[i] = l->dynamic[ l->dynamic_count - 1 ];