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];
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 l->pending[ l->pending_count ].ptr = d;
118 l->pending[ l->pending_count ].free_ = f;
122 haz_t *haz_get_static (int i) {
123 if (i >= STATIC_HAZ_PER_THREAD)
125 LOCALIZE_THREAD_LOCAL(tid_, int);
126 return &haz_local_[tid_].static_haz[i];
129 void haz_register_dynamic (haz_t *haz) {
130 LOCALIZE_THREAD_LOCAL(tid_, int);
131 haz_local_t *l = haz_local_ + tid_;
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);
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);
143 l->dynamic_size *= 2;
146 l->dynamic[ l->dynamic_count++ ] = haz;
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_;
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 ];