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  * Remove a value from the hashtable. Requires external locking
 219  * \returns the old value if \p key is already present or NULL
 220  */
 221 gpointer
 222 mono_conc_hashtable_remove (MonoConcurrentHashTable *hash_table, gpointer key)
 223 {
 224         conc_table *table;
 225         key_value_pair *kvs;
 226         int hash, i, table_mask;
 227
 228         g_assert (key != NULL && key != TOMBSTONE);
 229
 230         hash = mix_hash (hash_table->hash_func (key));
 231
 232         table = (conc_table*)hash_table->table;
 233         kvs = table->kvs;
 234         table_mask = table->table_size - 1;
 235         i = hash & table_mask;
 236
 237         if (!hash_table->equal_func) {
 238                 for (;;) {
 239                         if (!kvs [i].key) {
 240                                 return NULL; /*key not found*/
 241                         }
 242
 243                         if (key == kvs [i].key) {
 244                                 gpointer value = kvs [i].value;
 245                                 kvs [i].value = NULL;
 246                                 mono_memory_barrier ();
 247                                 kvs [i].key = TOMBSTONE;
 248                                 --hash_table->element_count;
 249
 250                                 if (hash_table->key_destroy_func != NULL)
 251                                         (*hash_table->key_destroy_func) (key);
 252                                 if (hash_table->value_destroy_func != NULL)
 253                                         (*hash_table->value_destroy_func) (value);
 254
 255                                 return value;
 256                         }
 257                         i = (i + 1) & table_mask;
 258                 }
 259         } else {
 260                 GEqualFunc equal = hash_table->equal_func;
 261                 for (;;) {
 262                         if (!kvs [i].key) {
 263                                 return NULL; /*key not found*/
 264                         }
 265
 266                         if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
 267                                 gpointer old_key = kvs [i].key;
 268                                 gpointer value = kvs [i].value;
 269                                 kvs [i].value = NULL;
 270                                 mono_memory_barrier ();
 271                                 kvs [i].key = TOMBSTONE;
 272
 273                                 if (hash_table->key_destroy_func != NULL)
 274                                         (*hash_table->key_destroy_func) (old_key);
 275                                 if (hash_table->value_destroy_func != NULL)
 276                                         (*hash_table->value_destroy_func) (value);
 277                                 return value;
 278                         }
 279
 280                         i = (i + 1) & table_mask;
 281                 }
 282         }
 283 }
 284 /**
 285  * mono_conc_hashtable_insert:
 286  * Insert a value into the hashtable. Requires external locking.
 287  * \returns the old value if \p key is already present or NULL
 288  */
 289 gpointer
 290 mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
 291 {
 292         conc_table *table;
 293         key_value_pair *kvs;
 294         int hash, i, table_mask;
 295
 296         g_assert (key != NULL && key != TOMBSTONE);
 297         g_assert (value != NULL);
 298
 299         hash = mix_hash (hash_table->hash_func (key));
 300
 301         if (hash_table->element_count >= hash_table->overflow_count)
 302                 expand_table (hash_table);
 303
 304         table = (conc_table*)hash_table->table;
 305         kvs = table->kvs;
 306         table_mask = table->table_size - 1;
 307         i = hash & table_mask;
 308
 309         if (!hash_table->equal_func) {
 310                 for (;;) {
 311                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 312                                 kvs [i].value = value;
 313                                 /* The write to values must happen after the write to keys */
 314                                 mono_memory_barrier ();
 315                                 kvs [i].key = key;
 316                                 ++hash_table->element_count;
 317                                 return NULL;
 318                         }
 319                         if (key == kvs [i].key) {
 320                                 gpointer value = kvs [i].value;
 321                                 return value;
 322                         }
 323                         i = (i + 1) & table_mask;
 324                 }
 325         } else {
 326                 GEqualFunc equal = hash_table->equal_func;
 327                 for (;;) {
 328                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 329                                 kvs [i].value = value;
 330                                 /* The write to values must happen after the write to keys */
 331                                 mono_memory_barrier ();
 332                                 kvs [i].key = key;
 333                                 ++hash_table->element_count;
 334                                 return NULL;
 335                         }
 336                         if (equal (key, kvs [i].key)) {
 337                                 gpointer value = kvs [i].value;
 338                                 return value;
 339                         }
 340                         i = (i + 1) & table_mask;
 341                 }
 342         }
 343 }
 344
 345 /**
 346  * mono_conc_hashtable_foreach:
 347  * Calls \p func for each value in the hashtable. Requires external locking.
 348  */
 349 void
 350 mono_conc_hashtable_foreach (MonoConcurrentHashTable *hash_table, GHFunc func, gpointer userdata)
 351 {
 352         int i;
 353         conc_table *table = (conc_table*)hash_table->table;
 354         key_value_pair *kvs = table->kvs;
 355
 356         for (i = 0; i < table->table_size; ++i) {
 357                 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
 358                         func (kvs [i].key, kvs [i].value, userdata);
 359                 }
 360         }
 361 }
 362
 363 /**
 364  * mono_conc_hashtable_foreach_steal:
 365  *
 366  * Calls @func for each entry in the hashtable, if @func returns true, remove from the hashtable. Requires external locking.
 367  * Same semantics as g_hash_table_foreach_steal.
 368  */
 369 void
 370 mono_conc_hashtable_foreach_steal (MonoConcurrentHashTable *hash_table, GHRFunc func, gpointer userdata)
 371 {
 372         int i;
 373         conc_table *table = (conc_table*)hash_table->table;
 374         key_value_pair *kvs = table->kvs;
 375
 376         for (i = 0; i < table->table_size; ++i) {
 377                 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
 378                         if (func (kvs [i].key, kvs [i].value, userdata)) {
 379                                 kvs [i].value = NULL;
 380                                 mono_memory_barrier ();
 381                                 kvs [i].key = TOMBSTONE;
 382                                 --hash_table->element_count;
 383                         }
 384                 }
 385         }
 386 }