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         mono_mutex_t *mutex;
  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 = 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_free_or_queue (table, conc_table_free, TRUE, FALSE);
  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 (mono_mutex_t *mutex, GHashFunc hash_func, GEqualFunc key_equal_func)
 115 {
 116         MonoConcurrentHashTable *res = g_new0 (MonoConcurrentHashTable, 1);
 117         res->mutex = mutex;
 118         res->hash_func = hash_func ? hash_func : g_direct_hash;
 119         res->equal_func = key_equal_func;
 120         // res->equal_func = g_direct_equal;
 121         res->table = conc_table_new (INITIAL_SIZE);
 122         res->element_count = 0;
 123         res->overflow_count = (int)(INITIAL_SIZE * LOAD_FACTOR);
 124         return res;
 125 }
 126
 127 MonoConcurrentHashTable*
 128 mono_conc_hashtable_new_full (mono_mutex_t *mutex, GHashFunc hash_func, GEqualFunc key_equal_func, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 129 {
 130         MonoConcurrentHashTable *res = mono_conc_hashtable_new (mutex, hash_func, key_equal_func);
 131         res->key_destroy_func = key_destroy_func;
 132         res->value_destroy_func = value_destroy_func;
 133         return res;
 134 }
 135
 136
 137 void
 138 mono_conc_hashtable_destroy (MonoConcurrentHashTable *hash_table)
 139 {
 140         if (hash_table->key_destroy_func || hash_table->value_destroy_func) {
 141                 int i;
 142                 conc_table *table = (conc_table*)hash_table->table;
 143                 key_value_pair *kvs = table->kvs;
 144
 145                 for (i = 0; i < table->table_size; ++i) {
 146                         if (kvs [i].key && kvs [i].key != TOMBSTONE) {
 147                                 if (hash_table->key_destroy_func)
 148                                         (hash_table->key_destroy_func) (kvs [i].key);
 149                                 if (hash_table->value_destroy_func)
 150                                         (hash_table->value_destroy_func) (kvs [i].value);
 151                         }
 152                 }
 153         }
 154         conc_table_free ((gpointer)hash_table->table);
 155         g_free (hash_table);
 156 }
 157
 158 gpointer
 159 mono_conc_hashtable_lookup (MonoConcurrentHashTable *hash_table, gpointer key)
 160 {
 161         MonoThreadHazardPointers* hp;
 162         conc_table *table;
 163         int hash, i, table_mask;
 164         key_value_pair *kvs;
 165         hash = mix_hash (hash_table->hash_func (key));
 166         hp = mono_hazard_pointer_get ();
 167
 168 retry:
 169         table = get_hazardous_pointer ((gpointer volatile*)&hash_table->table, hp, 0);
 170         table_mask = table->table_size - 1;
 171         kvs = table->kvs;
 172         i = hash & table_mask;
 173
 174         if (G_LIKELY (!hash_table->equal_func)) {
 175                 while (kvs [i].key) {
 176                         if (key == kvs [i].key) {
 177                                 gpointer value;
 178                                 /* The read of keys must happen before the read of values */
 179                                 mono_memory_barrier ();
 180                                 value = kvs [i].value;
 181                                 /* FIXME check for NULL if we add suppport for removal */
 182                                 mono_hazard_pointer_clear (hp, 0);
 183                                 return value;
 184                         }
 185                         i = (i + 1) & table_mask;
 186                 }
 187         } else {
 188                 GEqualFunc equal = hash_table->equal_func;
 189
 190                 while (kvs [i].key) {
 191                         if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
 192                                 gpointer value;
 193                                 /* The read of keys must happen before the read of values */
 194                                 mono_memory_barrier ();
 195                                 value = kvs [i].value;
 196
 197                                 /* We just read a value been deleted, try again. */
 198                                 if (G_UNLIKELY (!value))
 199                                         goto retry;
 200
 201                                 mono_hazard_pointer_clear (hp, 0);
 202                                 return value;
 203                         }
 204                         i = (i + 1) & table_mask;
 205                 }
 206         }
 207
 208         /* The table might have expanded and the value is now on the newer table */
 209         mono_memory_barrier ();
 210         if (hash_table->table != table)
 211                 goto retry;
 212
 213         mono_hazard_pointer_clear (hp, 0);
 214         return NULL;
 215 }
 216
 217 /**
 218  * mono_conc_hashtable_remove
 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         mono_mutex_lock (hash_table->mutex);
 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                                 mono_mutex_unlock (hash_table->mutex);
 243                                 return NULL; /*key not found*/
 244                         }
 245
 246                         if (key == kvs [i].key) {
 247                                 gpointer value = kvs [i].value;
 248                                 kvs [i].value = NULL;
 249                                 mono_memory_barrier ();
 250                                 kvs [i].key = TOMBSTONE;
 251
 252                                 mono_mutex_unlock (hash_table->mutex);
 253                                 if (hash_table->key_destroy_func != NULL)
 254                                         (*hash_table->key_destroy_func) (key);
 255                                 if (hash_table->value_destroy_func != NULL)
 256                                         (*hash_table->value_destroy_func) (value);
 257
 258                                 return value;
 259                         }
 260                         i = (i + 1) & table_mask;
 261                 }
 262         } else {
 263                 GEqualFunc equal = hash_table->equal_func;
 264                 for (;;) {
 265                         if (!kvs [i].key) {
 266                                 mono_mutex_unlock (hash_table->mutex);
 267                                 return NULL; /*key not found*/
 268                         }
 269
 270                         if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
 271                                 gpointer old_key = kvs [i].key;
 272                                 gpointer value = kvs [i].value;
 273                                 kvs [i].value = NULL;
 274                                 mono_memory_barrier ();
 275                                 kvs [i].key = TOMBSTONE;
 276
 277                                 mono_mutex_unlock (hash_table->mutex);
 278                                 if (hash_table->key_destroy_func != NULL)
 279                                         (*hash_table->key_destroy_func) (old_key);
 280                                 if (hash_table->value_destroy_func != NULL)
 281                                         (*hash_table->value_destroy_func) (value);
 282                                 return value;
 283                         }
 284
 285                         i = (i + 1) & table_mask;
 286                 }
 287         }
 288 }
 289 /**
 290  * mono_conc_hashtable_insert
 291  *
 292  * @Returns the old value if key is already present or null
 293  */
 294 gpointer
 295 mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
 296 {
 297         conc_table *table;
 298         key_value_pair *kvs;
 299         int hash, i, table_mask;
 300
 301         g_assert (key != NULL && key != TOMBSTONE);
 302         g_assert (value != NULL);
 303
 304         hash = mix_hash (hash_table->hash_func (key));
 305         mono_mutex_lock (hash_table->mutex);
 306
 307         if (hash_table->element_count >= hash_table->overflow_count)
 308                 expand_table (hash_table);
 309
 310         table = (conc_table*)hash_table->table;
 311         kvs = table->kvs;
 312         table_mask = table->table_size - 1;
 313         i = hash & table_mask;
 314
 315         if (!hash_table->equal_func) {
 316                 for (;;) {
 317                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 318                                 kvs [i].value = value;
 319                                 /* The write to values must happen after the write to keys */
 320                                 mono_memory_barrier ();
 321                                 kvs [i].key = key;
 322                                 ++hash_table->element_count;
 323                                 mono_mutex_unlock (hash_table->mutex);
 324                                 return NULL;
 325                         }
 326                         if (key == kvs [i].key) {
 327                                 gpointer value = kvs [i].value;
 328                                 mono_mutex_unlock (hash_table->mutex);
 329                                 return value;
 330                         }
 331                         i = (i + 1) & table_mask;
 332                 }
 333         } else {
 334                 GEqualFunc equal = hash_table->equal_func;
 335                 for (;;) {
 336                         if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
 337                                 kvs [i].value = value;
 338                                 /* The write to values must happen after the write to keys */
 339                                 mono_memory_barrier ();
 340                                 kvs [i].key = key;
 341                                 ++hash_table->element_count;
 342                                 mono_mutex_unlock (hash_table->mutex);
 343                                 return NULL;
 344                         }
 345                         if (equal (key, kvs [i].key)) {
 346                                 gpointer value = kvs [i].value;
 347                                 mono_mutex_unlock (hash_table->mutex);
 348                                 return value;
 349                         }
 350                         i = (i + 1) & table_mask;
 351                 }
 352         }
 353 }
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371