mono/utils/mono-conc-hashtable.c

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