mono/utils/mono-conc-hashtable.c

   1 /**
   2  * \file
   3  * A mostly concurrent hashtable
   4  *
   5  * Author:
   6  *      Rodrigo Kumpera (kumpera@gmail.com)
   7  *
   8  * (C) 2014 Xamarin
   9  */
  10
  11 #include "mono-conc-hashtable.h"
  12 #include <mono/utils/hazard-pointer.h>
  13
  14 /* Configuration knobs. */
  15
  16 #define INITIAL_SIZE 32
  17 #define LOAD_FACTOR 0.75f
  18 #define TOMBSTONE ((gpointer)(ssize_t)-1)
  19
  20 typedef struct {
  21         gpointer key;
  22         gpointer value;
  23 } key_value_pair;
  24
  25 typedef struct {
  26         int table_size;
  27         key_value_pair *kvs;
  28 } conc_table;
  29
  30 struct _MonoConcurrentHashTable {
  31         volatile conc_table *table; /* goes to HP0 */
  32         GHashFunc hash_func;
  33         GEqualFunc equal_func;
  34         int element_count;
  35         int overflow_count;
  36         GDestroyNotify key_destroy_func;
  37         GDestroyNotify value_destroy_func;
  38 };
  39
  40 static conc_table*
  41 conc_table_new (int size)
  42 {
  43         conc_table *res = g_new (conc_table, 1);
  44         res->table_size = size;
  45         res->kvs = g_new0 (key_value_pair, size);
  46         return res;
  47 }
  48
  49 static void
  50 conc_table_free (gpointer ptr)
  51 {
  52         conc_table *table = (conc_table *)ptr;
  53         g_free (table->kvs);
  54         g_free (table);
  55 }
  56
  57 static void
  58 conc_table_lf_free (conc_table *table)
  59 {
  60         mono_thread_hazardous_try_free (table, conc_table_free);
  61 }
  62
  63
  64 /*
  65 A common problem with power of two hashtables is that it leads of bad clustering when dealing
  66 with aligned numbers.
  67
  68 The solution here is to mix the bits from two primes plus the hash itself, it produces a better spread
  69 than just the numbers.
  70 */
  71
  72 static MONO_ALWAYS_INLINE int
  73 mix_hash (int hash)
  74 {
  75         return ((hash * 215497) >> 16) ^ (hash * 1823231 + hash);
  76 }
  77
  78 static MONO_ALWAYS_INLINE void
  79 insert_one_local (conc_table *table, GHashFunc hash_func, gpointer key, gpointer value)
  80 {
  81         key_value_pair *kvs = table->kvs;
  82         int table_mask = table->table_size - 1;
  83         int hash = mix_hash (hash_func (key));
  84         int i = hash & table_mask;
  85
  86         while (table->kvs [i].key)
  87                 i = (i + 1) & table_mask;
  88
  89         kvs [i].key = key;
  90         kvs [i].value = value;
  91 }
  92
  93 /* LOCKING: Must be called holding hash_table->mutex */
  94 static void
  95 expand_table (MonoConcurrentHashTable *hash_table)
  96 {
  97         conc_table *old_table = (conc_table*)hash_table->table;
  98         conc_table *new_table = conc_table_new (old_table->table_size * 2);
  99         key_value_pair *kvs = old_table->kvs;
 100         int i;
 101
 102         for (i = 0; i < old_table->table_size; ++i) {
 103                 if (kvs [i].key && kvs [i].key != TOMBSTONE)
 104                         insert_one_local (new_table, hash_table->hash_func, kvs [i].key, kvs [i].value);
 105         }
 106         mono_memory_barrier ();
 107         hash_table->table = new_table;
 108         hash_table->overflow_count = (int)(new_table->table_size * LOAD_FACTOR);
 109         conc_table_lf_free (old_table);
 110 }
 111
 112
 113 MonoConcurrentHashTable*
 114 mono_conc_hashtable_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 115 {
 116         MonoConcurrentHashTable *res = g_new0 (MonoConcurrentHashTable, 1);
 117         res->hash_func = hash_func ? hash_func : g_direct_hash;
 118         res->equal_func = key_equal_func;
 119         // res->equal_func = g_direct_equal;
 120         res->table = conc_table_new (INITIAL_SIZE);
 121         res->element_count = 0;
 122         res->overflow_count = (int)(INITIAL_SIZE * LOAD_FACTOR);
 123         return res;
 124 }
 125
 126 MonoConcurrentHashTable*
 127 mono_conc_hashtable_new_full (GHashFunc hash_func, GEqualFunc key_equal_func, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 128 {
 129         MonoConcurrentHashTable *res = mono_conc_hashtable_new (hash_func, key_equal_func);
 130         res->key_destroy_func = key_destroy_func;
 131         res->value_destroy_func = value_destroy_func;
 132         return res;
 133 }
 134
 135
 136 void
 137 mono_conc_hashtable_destroy (MonoConcurrentHashTable *hash_table)
 138 {
 139         if (hash_table->key_destroy_func || hash_table->value_destroy_func) {
 140                 int i;
 141                 conc_table *table = (conc_table*)hash_table->table;
 142                 key_value_pair *kvs = table->kvs;
 143
 144                 for (i = 0; i < table->table_size; ++i) {
 145                         if (kvs [i].key && kvs [i].key != TOMBSTONE) {
 146                                 if (hash_table->key_destroy_func)
 147                                         (hash_table->key_destroy_func) (kvs [i].key);
 148                                 if (hash_table->value_destroy_func)
 149                                         (hash_table->value_destroy_func) (kvs [i].value);
 150                         }
 151                 }
 152         }
 153         conc_table_free ((gpointer)hash_table->table);
 154         g_free (hash_table);
 155 }
 156
 157 gpointer
 158 mono_conc_hashtable_lookup (MonoConcurrentHashTable *hash_table, gpointer key)
 159 {
 160         MonoThreadHazardPointers* hp;
 161         conc_table *table;
 162         int hash, i, table_mask;
 163         key_value_pair *kvs;
 164         hash = mix_hash (hash_table->hash_func (key));
 165         hp = mono_hazard_pointer_get ();
 166
 167 retry:
 168         table = (conc_table *)mono_get_hazardous_pointer ((gpointer volatile*)&hash_table->table, hp, 0);
 169         table_mask = table->table_size - 1;
 170         kvs = table->kvs;
 171         i = hash & table_mask;
 172
 173         if (G_LIKELY (!hash_table->equal_func)) {
 174                 while (kvs [i].key) {
 175                         if (key == kvs [i].key) {
 176                                 gpointer value;
 177                                 /* The read of keys must happen before the read of values */
 178                                 mono_memory_barrier ();
 179                                 value = kvs [i].value;
 180                                 /* FIXME check for NULL if we add suppport for removal */
 181                                 mono_hazard_pointer_clear (hp, 0);
 182                                 return value;
 183                         }
 184                         i = (i + 1) & table_mask;
 185                 }
 186         } else {
 187                 GEqualFunc equal = hash_table->equal_func;
 188
 189                 while (kvs [i].key) {
 190                         if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
 191                                 gpointer value;
 192                                 /* The read of keys must happen before the read of values */
 193                                 mono_memory_barrier ();
 194                                 value = kvs [i].value;
 195
 196                                 /* We just read a value been deleted, try again. */
 197                                 if (G_UNLIKELY (!value))
 198                                         goto retry;
 199
 200                                 mono_hazard_pointer_clear (hp, 0);
 201                                 return value;
 202                         }
 203                         i = (i + 1) & table_mask;
 204                 }
 205         }
 206
 207         /* The table might have expanded and the value is now on the newer table */
 208         mono_memory_barrier ();
 209         if (hash_table->table != table)
 210                 goto retry;
 211
 212         mono_hazard_pointer_clear (hp, 0);
 213         return NULL;
 214 }
 215
 216 /**
 217  * mono_conc_hashtable_remove:
 218  *
 219  * Remove a value from the hashtable. Requires external locking
 220  *
 221  * @Returns the old value if key is already present or null
 222  */
 223 gpointer
 224 mono_conc_hashtable_remove (MonoConcurrentHashTable *hash_table, gpointer key)
 225 {
 226         conc_table *table;
 227         key_value_pair *kvs;
 228         int hash, i, table_mask;
 229
 230         g_assert (key != NULL && key != TOMBSTONE);
 231
 232         hash = mix_hash (hash_table->hash_func (key));
 233
 234         table = (conc_table*)hash_table->table;
 235         kvs = table->kvs;
 236         table_mask = table->table_size - 1;
 237         i = hash & table_mask;
 238
 239         if (!hash_table->equal_func) {
 240                 for (;;) {
 241                         if (!kvs [i].key) {
 242                                 return NULL; /*key not found*/
 243                         }
 244
 245                         if (key == kvs [i].key) {
 246                                 gpointer value = kvs [i].value;
 247                                 kvs [i].value = NULL;
 248                                 mono_memory_barrier ();
 249                                 kvs [i].key = TOMBSTONE;
 250
 251                                 if (hash_table->key_destroy_func != NULL)
 252                                         (*hash_table->key_destroy_func) (key);
 253                                 if (hash_table->value_destroy_func != NULL)
 254                                         (*hash_table->value_destroy_func) (value);
 255
 256                                 return value;
 257                         }
 258                         i = (i + 1) & table_mask;
 259                 }
 260         } else {
 261                 GEqualFunc equal = hash_table->equal_func;
 262                 for (;;) {
 263                         if (!kvs [i].key) {
 264                                 return NULL; /*key not found*/
 265                         }
 266
 267                         if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
 268                                 gpointer old_key = kvs [i].key;
 269                                 gpointer value = kvs [i].value;
 270                                 kvs [i].value = NULL;
 271                                 mono_memory_barrier ();
 272                                 kvs [i].key = TOMBSTONE;
 273
 274                                 if (hash_table->key_destroy_func != NULL)
 275                                         (*hash_table->key_destroy_func) (old_key);
 276                                 if (hash_table->value_destroy_func != NULL)
 277                                         (*hash_table->value_destroy_func) (value);
 278                                 return value;
 279                         }
 280
 281                         i = (i + 1) & table_mask;
 282                 }
 283         }
 284 }
 285 /**
 286  * mono_conc_hashtable_insert:
 287  *
 288  * Insert a value into the hashtable. Requires external locking.
 289  * @Returns the old value if key is already present or null
 290  */
 291 gpointer
 292 mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
 293 {
 294         conc_table *table;
 295         key_value_pair *kvs;
 296         int hash, i, table_mask;
 297
 298         g_assert (key != NULL && key != TOMBSTONE);
 299         g_assert (value != NULL);
 300
 301         hash = mix_hash (hash_table->hash_func (key));
 302
 303         if (hash_table->element_count >= hash_table->overflow_count)
 304                 expand_table (hash_table);
 305
 306         table = (conc_table*)hash_table->table;
 307         kvs = table->kvs;
 308         table_mask = table->table_size - 1;
 309         i = hash & table_mask;
 310
 311         if (!hash_table->equal_func) {
 312                 for (;;) {
 313                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 314                                 kvs [i].value = value;
 315                                 /* The write to values must happen after the write to keys */
 316                                 mono_memory_barrier ();
 317                                 kvs [i].key = key;
 318                                 ++hash_table->element_count;
 319                                 return NULL;
 320                         }
 321                         if (key == kvs [i].key) {
 322                                 gpointer value = kvs [i].value;
 323                                 return value;
 324                         }
 325                         i = (i + 1) & table_mask;
 326                 }
 327         } else {
 328                 GEqualFunc equal = hash_table->equal_func;
 329                 for (;;) {
 330                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 331                                 kvs [i].value = value;
 332                                 /* The write to values must happen after the write to keys */
 333                                 mono_memory_barrier ();
 334                                 kvs [i].key = key;
 335                                 ++hash_table->element_count;
 336                                 return NULL;
 337                         }
 338                         if (equal (key, kvs [i].key)) {
 339                                 gpointer value = kvs [i].value;
 340                                 return value;
 341                         }
 342                         i = (i + 1) & table_mask;
 343                 }
 344         }
 345 }
 346
 347 /**
 348  * mono_conc_hashtable_foreach:
 349  *
 350  * Calls @func for each value in the hashtable. Requires external locking.
 351  */
 352 void
 353 mono_conc_hashtable_foreach (MonoConcurrentHashTable *hash_table, GHFunc func, gpointer userdata)
 354 {
 355         int i;
 356         conc_table *table = (conc_table*)hash_table->table;
 357         key_value_pair *kvs = table->kvs;
 358
 359         for (i = 0; i < table->table_size; ++i) {
 360                 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
 361                         func (kvs [i].key, kvs [i].value, userdata);
 362                 }
 363         }
 364 }