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
17 typedef struct pending {
22 typedef struct haz_local {
23 pending_t *pending; // to be freed
27 haz_t static_haz[STATIC_HAZ_PER_THREAD];
33 } __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t;
35 static haz_local_t haz_local_[MAX_NUM_THREADS] = {};
37 static void sort_hazards (haz_t *hazards, int n) {
41 static int search_hazards (void *p, haz_t *hazards, int n) {
42 for (int i = 0; i < n; ++i) {
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);
59 void haz_defer_free (void *d, free_t f) {
62 LOCALIZE_THREAD_LOCAL(tid_, int);
63 haz_local_t *l = haz_local_ + tid_;
64 while (l->pending_count == l->pending_size) {
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);
72 // scan for hazard pointers
73 haz_t *hazards = nbd_malloc(sizeof(haz_t) * l->pending_size);
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) {
85 hazards[hazard_count++] = h->static_haz[j];
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) {
96 hazards[hazard_count++] = *h->dynamic[j];
100 sort_hazards(hazards, hazard_count);
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
111 p->free_(p->ptr); // free pending item
114 l->pending_count = conflicts_count;
117 assert(l->pending_size > l->pending_count);
118 l->pending[ l->pending_count ].ptr = d;
119 l->pending[ l->pending_count ].free_ = f;
123 haz_t *haz_get_static (int i) {
124 if (i >= STATIC_HAZ_PER_THREAD)
126 LOCALIZE_THREAD_LOCAL(tid_, int);
127 assert(i < STATIC_HAZ_PER_THREAD);
128 return &haz_local_[tid_].static_haz[i];
131 void haz_register_dynamic (haz_t *haz) {
132 LOCALIZE_THREAD_LOCAL(tid_, int);
133 haz_local_t *l = haz_local_ + tid_;
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);
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);
146 l->dynamic_size *= 2;
149 l->dynamic[ l->dynamic_count++ ] = haz;
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_;
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 ];