urcu-ht.c

   1
   2 #define _LGPL_SOURCE
   3 #include <stdlib.h>
   4 #include <urcu.h>
   5 #include <arch.h>
   6 #include <arch_atomic.h>
   7 #include <assert.h>
   8 #include <compiler.h>
   9 #include <urcu-defer.h>
  10 #include <errno.h>
  11 #include <urcu-ht.h>
  12
  13 struct rcu_ht_node;
  14
  15 struct rcu_ht_node {
  16         struct rcu_ht_node *next;
  17         void *key;
  18         void *data;
  19 };
  20
  21 struct rcu_ht {
  22         struct rcu_ht_node *tbl[HASH_SIZE];
  23         ht_hash_fct hash_fct;
  24         void (*free_fct)(void *data);   /* fct to free data */
  25 };
  26
  27 struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*free_fct)(void *data))
  28 {
  29         struct rcu_ht *ht;
  30
  31         ht = calloc(1, sizeof(struct rcu_ht));
  32         ht->hash_fct = hash_fct;
  33         ht->free_fct = free_fct;
  34         return ht;
  35 }
  36
  37 /* delete all elements */
  38 void ht_delete_all(struct rcu_ht *ht)
  39 {
  40         unsigned long i;
  41         struct rcu_ht_node **prev, *node;
  42
  43         for (i = 0; i < HASH_SIZE; i++) {
  44                 rcu_read_lock();
  45
  46                 prev = &ht->tbl[i];
  47                 node = rcu_dereference(*prev);
  48                 /*
  49                  * Cut the head, therefore whole bucket will be unused
  50                  * after GP. (except for concurrent additions)
  51                  */
  52                 rcu_assign_pointer(prev, NULL);
  53                 for (;;) {
  54                         if (likely(!node)) {
  55                                 break;
  56                         }
  57                         prev = &node->next;
  58                         if (node->data)
  59                                 call_rcu(ht->free_fct, node->data);
  60                         call_rcu(free, node);
  61                         node = rcu_dereference(*prev);
  62                 }
  63                 rcu_read_unlock();
  64         }
  65 }
  66
  67 /*
  68  * Should only be called when no more concurrent readers nor writers can
  69  * possibly access the table.
  70  */
  71 void ht_destroy(struct rcu_ht *ht)
  72 {
  73         ht_delete_all(ht);
  74         free(ht);
  75 }
  76
  77 void *ht_lookup(struct rcu_ht *ht, void *key)
  78 {
  79         unsigned long hash;
  80         struct rcu_ht_node *node;
  81         void *ret;
  82
  83         hash = ht->hash_fct(key);
  84
  85         rcu_read_lock();
  86         node = rcu_dereference(ht->tbl[hash]);
  87         for (;;) {
  88                 if (likely(!node)) {
  89                         ret = NULL;
  90                         break;
  91                 }
  92                 if (node->key == key) {
  93                         ret = node->data;
  94                         break;
  95                 }
  96                 node = rcu_dereference(node->next);
  97         }
  98         rcu_read_unlock();
  99
 100         return ret;
 101 }
 102
 103 /*
 104  * Will re-try until either:
 105  * - The key is already there (-EEXIST)
 106  * - We successfully add the key at the head of a table bucket.
 107  */
 108 int ht_add(struct rcu_ht *ht, void *key, void *data)
 109 {
 110         struct rcu_ht_node *node, *old_head, *new_head;
 111         unsigned long hash;
 112         int ret = 0;
 113
 114         new_head = calloc(1, sizeof(struct rcu_ht_node));
 115         new_head->key = key;
 116         new_head->data = data;
 117         hash = ht->hash_fct(key);
 118
 119         /* here comes the fun and tricky part.
 120          * Add at the beginning with a cmpxchg.
 121          * Hold a read lock between the moment the first element is read
 122          * and the nodes traversal (to find duplicates). This ensures
 123          * the head pointer has not been reclaimed when cmpxchg is done.
 124          * Always adding at the head ensures that we would have to
 125          * re-try if a new item has been added concurrently. So we ensure that
 126          * we never add duplicates. */
 127 retry:
 128         rcu_read_lock();
 129
 130         old_head = node = rcu_dereference(ht->tbl[hash]);
 131         for (;;) {
 132                 if (likely(!node)) {
 133                         break;
 134                 }
 135                 if (node->key == key) {
 136                         ret = -EEXIST;
 137                         goto end;
 138                 }
 139                 node = rcu_dereference(node->next);
 140         }
 141         if (rcu_cmpxchg_pointer(&ht->tbl[hash], old_head, new_head) != old_head)
 142                 goto restart;
 143 end:
 144         rcu_read_unlock();
 145
 146         return ret;
 147
 148         /* restart loop, release and re-take the read lock to be kind to GP */
 149 restart:
 150         rcu_read_unlock();
 151         goto retry;
 152 }
 153
 154 /*
 155  * Restart until we successfully remove the entry, or no entry is left
 156  * ((void *)(unsigned long)-ENOENT).
 157  */
 158 void *ht_steal(struct rcu_ht *ht, void *key)
 159 {
 160         struct rcu_ht_node **prev, *node;
 161         unsigned long hash;
 162         void *data;
 163
 164         hash = ht->hash_fct(key);
 165
 166 retry:
 167         rcu_read_lock();
 168
 169         prev = &ht->tbl[hash];
 170         node = rcu_dereference(*prev);
 171         for (;;) {
 172                 if (likely(!node)) {
 173                         data = (void *)(unsigned long)-ENOENT;
 174                         goto end;
 175                 }
 176                 if (node->key == key) {
 177                         break;
 178                 }
 179                 prev = &node->next;
 180                 node = rcu_dereference(*prev);
 181         }
 182         /* Found it ! pointer to object is in "prev" */
 183         if (rcu_cmpxchg_pointer(prev, node, node->next) != node)
 184                 goto restart;
 185 end:
 186         rcu_read_unlock();
 187
 188         data = node->data;
 189         call_rcu(free, node);
 190
 191         return data;
 192
 193         /* restart loop, release and re-take the read lock to be kind to GP */
 194 restart:
 195         rcu_read_unlock();
 196         goto retry;
 197 }
 198
 199 int ht_delete(struct rcu_ht *ht, void *key)
 200 {
 201         void *data;
 202
 203         data = ht_steal(ht, key);
 204         if (data) {
 205                 if (ht->free_fct && data)
 206                         call_rcu(ht->free_fct, data);
 207                 return 0;
 208         } else {
 209                 return -ENOENT;
 210         }
 211 }
 212
 213 unsigned long stupid_hash(void *key)
 214 {
 215         return (unsigned long)key % HASH_SIZE;
 216 }