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
 249                                 if (hash_table->key_destroy_func != NULL)
 250                                         (*hash_table->key_destroy_func) (key);
 251                                 if (hash_table->value_destroy_func != NULL)
 252                                         (*hash_table->value_destroy_func) (value);
 253
 254                                 return value;
 255                         }
 256                         i = (i + 1) & table_mask;
 257                 }
 258         } else {
 259                 GEqualFunc equal = hash_table->equal_func;
 260                 for (;;) {
 261                         if (!kvs [i].key) {
 262                                 return NULL; /*key not found*/
 263                         }
 264
 265                         if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
 266                                 gpointer old_key = kvs [i].key;
 267                                 gpointer value = kvs [i].value;
 268                                 kvs [i].value = NULL;
 269                                 mono_memory_barrier ();
 270                                 kvs [i].key = TOMBSTONE;
 271
 272                                 if (hash_table->key_destroy_func != NULL)
 273                                         (*hash_table->key_destroy_func) (old_key);
 274                                 if (hash_table->value_destroy_func != NULL)
 275                                         (*hash_table->value_destroy_func) (value);
 276                                 return value;
 277                         }
 278
 279                         i = (i + 1) & table_mask;
 280                 }
 281         }
 282 }
 283 /**
 284  * mono_conc_hashtable_insert:
 285  * Insert a value into the hashtable. Requires external locking.
 286  * \returns the old value if \p key is already present or NULL
 287  */
 288 gpointer
 289 mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
 290 {
 291         conc_table *table;
 292         key_value_pair *kvs;
 293         int hash, i, table_mask;
 294
 295         g_assert (key != NULL && key != TOMBSTONE);
 296         g_assert (value != NULL);
 297
 298         hash = mix_hash (hash_table->hash_func (key));
 299
 300         if (hash_table->element_count >= hash_table->overflow_count)
 301                 expand_table (hash_table);
 302
 303         table = (conc_table*)hash_table->table;
 304         kvs = table->kvs;
 305         table_mask = table->table_size - 1;
 306         i = hash & table_mask;
 307
 308         if (!hash_table->equal_func) {
 309                 for (;;) {
 310                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 311                                 kvs [i].value = value;
 312                                 /* The write to values must happen after the write to keys */
 313                                 mono_memory_barrier ();
 314                                 kvs [i].key = key;
 315                                 ++hash_table->element_count;
 316                                 return NULL;
 317                         }
 318                         if (key == kvs [i].key) {
 319                                 gpointer value = kvs [i].value;
 320                                 return value;
 321                         }
 322                         i = (i + 1) & table_mask;
 323                 }
 324         } else {
 325                 GEqualFunc equal = hash_table->equal_func;
 326                 for (;;) {
 327                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 328                                 kvs [i].value = value;
 329                                 /* The write to values must happen after the write to keys */
 330                                 mono_memory_barrier ();
 331                                 kvs [i].key = key;
 332                                 ++hash_table->element_count;
 333                                 return NULL;
 334                         }
 335                         if (equal (key, kvs [i].key)) {
 336                                 gpointer value = kvs [i].value;
 337                                 return value;
 338                         }
 339                         i = (i + 1) & table_mask;
 340                 }
 341         }
 342 }
 343
 344 /**
 345  * mono_conc_hashtable_foreach:
 346  * Calls \p func for each value in the hashtable. Requires external locking.
 347  */
 348 void
 349 mono_conc_hashtable_foreach (MonoConcurrentHashTable *hash_table, GHFunc func, gpointer userdata)
 350 {
 351         int i;
 352         conc_table *table = (conc_table*)hash_table->table;
 353         key_value_pair *kvs = table->kvs;
 354
 355         for (i = 0; i < table->table_size; ++i) {
 356                 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
 357                         func (kvs [i].key, kvs [i].value, userdata);
 358                 }
 359         }
 360 }