pd.if.org Git - nbds/blob - 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 #include "lwt.h"
  17
  18 typedef struct pending {
  19     void * ptr;
  20     free_t free_;
  21 } pending_t;
  22
  23 typedef struct haz_local {
  24     pending_t *pending; // to be freed
  25     int pending_size;
  26     int pending_count;
  27
  28     haz_t static_haz[STATIC_HAZ_PER_THREAD];
  29
  30     haz_t **dynamic;
  31     int dynamic_size;
  32     int dynamic_count;
  33
  34 } __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t;
  35
  36 static haz_local_t haz_local_[MAX_NUM_THREADS] = {};
  37
  38 static void sort_hazards (haz_t *hazards, int n) {
  39     TRACE("H3", "sort_hazards: sorting hazard list %p of %p elements", hazards, n);
  40     return;
  41 }
  42
  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);
  48             return TRUE;
  49         }
  50     }
  51     return FALSE;
  52 }
  53
  54 static void resize_pending (void) {
  55     TRACE("H2", "haz_resize_pending", 0, 0);
  56     LOCALIZE_THREAD_LOCAL(ThreadId, int);
  57     haz_local_t *l = haz_local_ + ThreadId;
  58     pending_t *p = nbd_malloc(sizeof(pending_t) * l->pending_size * 2);
  59     memcpy(p, l->pending, l->pending_size);
  60     nbd_free(l->pending);
  61     l->pending = p;
  62     l->pending_size *= 2;
  63 }
  64
  65 void haz_defer_free (void *d, free_t f) {
  66     TRACE("H1", "haz_defer_free: %p (%p)", d, f);
  67     assert(d);
  68     assert(f);
  69     LOCALIZE_THREAD_LOCAL(ThreadId, int);
  70     haz_local_t *l = haz_local_ + ThreadId;
  71     while (l->pending_count == l->pending_size) {
  72
  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);
  76             break;
  77         }
  78
  79         // scan for hazard pointers
  80         haz_t *hazards = nbd_malloc(sizeof(haz_t) * l->pending_size);
  81         int    hazard_count = 0;
  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) {
  87                         resize_pending();
  88                         nbd_free(hazards);
  89                         haz_defer_free(d, f);
  90                         return;
  91                     }
  92                     hazards[hazard_count++] = h->static_haz[j];
  93                 }
  94             }
  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) {
  98                         resize_pending();
  99                         nbd_free(hazards);
 100                         haz_defer_free(d, f);
 101                         return;
 102                     }
 103                     hazards[hazard_count++] = *h->dynamic[j];
 104                 }
 105             }
 106         }
 107         sort_hazards(hazards, hazard_count);
 108
 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
 115             } else {
 116                 assert(p->free_);
 117                 assert(p->ptr);
 118                 p->free_(p->ptr); // free pending item
 119             }
 120         }
 121         l->pending_count = conflicts_count;
 122         nbd_free(hazards);
 123     }
 124     assert(l->pending_size > l->pending_count);
 125     l->pending[ l->pending_count ].ptr   = d;
 126     l->pending[ l->pending_count ].free_ = f;
 127     l->pending_count++;
 128 }
 129
 130 haz_t *haz_get_static (int i) {
 131     TRACE("H1", "haz_get_static: %p", i, 0);
 132     if (i >= STATIC_HAZ_PER_THREAD)
 133         return NULL;
 134     LOCALIZE_THREAD_LOCAL(ThreadId, int);
 135     assert(i < STATIC_HAZ_PER_THREAD);
 136     haz_t *ret = &haz_local_[ThreadId].static_haz[i];
 137     TRACE("H1", "haz_get_static: returning %p", ret, 0);
 138     return ret;
 139 }
 140
 141 void haz_register_dynamic (haz_t *haz) {
 142     TRACE("H1", "haz_register_dynamic: %p", haz, 0);
 143     LOCALIZE_THREAD_LOCAL(ThreadId, int);
 144     haz_local_t *l = haz_local_ + ThreadId;
 145
 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);
 149         l->dynamic_size = n;
 150     }
 151
 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);
 156         l->dynamic = d;
 157         l->dynamic_size *= 2;
 158     }
 159
 160     l->dynamic[ l->dynamic_count++ ] = haz;
 161 }
 162
 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(ThreadId, int);
 167     haz_local_t *l = haz_local_ + ThreadId;
 168
 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 ];
 173             }
 174             l->dynamic_count--;
 175             return;
 176         }
 177     }
 178     assert(0);
 179 }