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
  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 }