mono/metadata/mono-conc-hash.c

   1 /**
   2  * \file
   3  * Conc GC aware Hashtable implementation
   4  *
   5  * Author:
   6  *   Rodrigo Kumpera (kumpera@gmail.com)
   7  *
   8  */
   9 #include <config.h>
  10 #include <stdio.h>
  11 #include <math.h>
  12 #include <glib.h>
  13 #include "mono-conc-hash.h"
  14 #include "metadata/gc-internals.h"
  15 #include <mono/utils/checked-build.h>
  16 #include <mono/utils/mono-threads-coop.h>
  17
  18 #ifdef HAVE_BOEHM_GC
  19 #define mg_new0(type,n)  ((type *) GC_MALLOC(sizeof(type) * (n)))
  20 #define mg_new(type,n)   ((type *) GC_MALLOC(sizeof(type) * (n)))
  21 #define mg_free(x)       do { } while (0)
  22 #else
  23 #define mg_new0(x,n)     g_new0(x,n)
  24 #define mg_new(type,n)   g_new(type,n)
  25 #define mg_free(x)       g_free(x)
  26 #endif
  27
  28 #define INITIAL_SIZE 32
  29 #define LOAD_FACTOR 0.75f
  30 #define PTR_TOMBSTONE ((gpointer)(ssize_t)-1)
  31 /* Expand ration must be a power of two */
  32 #define EXPAND_RATIO 2
  33
  34 typedef struct {
  35         int table_size;
  36         MonoGHashGCType gc_type;
  37         void **keys;
  38         void **values;
  39 } conc_table;
  40
  41 struct _MonoConcGHashTable {
  42         volatile conc_table *table; /* goes to HP0 */
  43         GHashFunc hash_func;
  44         GEqualFunc equal_func;
  45         int element_count;
  46         int overflow_count;
  47         GDestroyNotify key_destroy_func;
  48         GDestroyNotify value_destroy_func;
  49         MonoGHashGCType gc_type;
  50         MonoGCRootSource source;
  51         const char *msg;
  52 };
  53
  54
  55 static conc_table*
  56 conc_table_new (MonoConcGHashTable *hash, int size)
  57 {
  58 #ifdef HAVE_SGEN_GC
  59         conc_table *table = mg_new0 (conc_table, 1);
  60 #else
  61         conc_table *table = mono_gc_alloc_fixed (sizeof (conc_table), MONO_GC_ROOT_DESCR_FOR_FIXED (sizeof (conc_table)), hash->source, hash->msg);
  62 #endif
  63
  64         table->keys = mg_new0 (void*, size);
  65         table->values = mg_new0 (void*, size);
  66         table->table_size = size;
  67         table->gc_type = hash->gc_type;
  68
  69 #ifdef HAVE_SGEN_GC
  70         if (hash->gc_type & MONO_HASH_KEY_GC)
  71                 mono_gc_register_root_wbarrier ((char*)table->keys, sizeof (MonoObject*) * size, mono_gc_make_vector_descr (), hash->source, hash->msg);
  72         if (hash->gc_type & MONO_HASH_VALUE_GC)
  73                 mono_gc_register_root_wbarrier ((char*)table->values, sizeof (MonoObject*) * size, mono_gc_make_vector_descr (), hash->source, hash->msg);
  74 #endif
  75
  76         return table;
  77 }
  78
  79 static void
  80 conc_table_free (gpointer ptr)
  81 {
  82         conc_table *table = (conc_table *)ptr;
  83 #ifdef HAVE_SGEN_GC
  84         if (table->gc_type & MONO_HASH_KEY_GC)
  85                 mono_gc_deregister_root ((char*)table->keys);
  86         if (table->gc_type & MONO_HASH_VALUE_GC)
  87                 mono_gc_deregister_root ((char*)table->values);
  88 #endif
  89
  90         mg_free (table->keys);
  91         mg_free (table->values);
  92 #ifdef HAVE_SGEN_GC
  93         mg_free (table);
  94 #else
  95         mono_gc_free_fixed (table);
  96 #endif
  97 }
  98
  99 static void
 100 conc_table_lf_free (conc_table *table)
 101 {
 102         mono_thread_hazardous_try_free (table, conc_table_free);
 103 }
 104
 105
 106 static gboolean
 107 key_is_tombstone (MonoConcGHashTable *hash, gpointer ptr)
 108 {
 109         if (hash->gc_type & MONO_HASH_KEY_GC)
 110                 return ptr == mono_domain_get()->ephemeron_tombstone;
 111         return ptr == PTR_TOMBSTONE;
 112 }
 113
 114 /*
 115 A common problem with power of two hashtables is that it leads of bad clustering when dealing
 116 with aligned numbers.
 117
 118 The solution here is to mix the bits from two primes plus the hash itself, it produces a better spread
 119 than just the numbers.
 120 */
 121
 122 static MONO_ALWAYS_INLINE int
 123 mix_hash (int hash)
 124 {
 125         return ((hash * 215497) >> 16) ^ (hash * 1823231 + hash);
 126 }
 127
 128
 129 static inline void
 130 set_key (conc_table *table, int slot, gpointer key)
 131 {
 132         gpointer *key_addr = &table->keys [slot];
 133         if (table->gc_type & MONO_HASH_KEY_GC)
 134                 mono_gc_wbarrier_generic_store (key_addr, key);
 135         else
 136                 *key_addr = key;
 137 }
 138
 139 static inline void
 140 set_key_to_tombstone (conc_table *table, int slot)
 141 {
 142         gpointer *key_addr = &table->keys [slot];
 143         if (table->gc_type & MONO_HASH_KEY_GC)
 144                 mono_gc_wbarrier_generic_store (key_addr, mono_domain_get()->ephemeron_tombstone);
 145         else
 146                 *key_addr = PTR_TOMBSTONE;
 147 }
 148
 149 static inline void
 150 set_value (conc_table *table, int slot, gpointer value)
 151 {
 152         gpointer *value_addr = &table->values [slot];
 153         if (table->gc_type & MONO_HASH_VALUE_GC)
 154                 mono_gc_wbarrier_generic_store (value_addr, value);
 155         else
 156                 *value_addr = value;
 157 }
 158
 159 static MONO_ALWAYS_INLINE void
 160 insert_one_local (conc_table *table, GHashFunc hash_func, gpointer key, gpointer value)
 161 {
 162         int table_mask = table->table_size - 1;
 163         int hash = mix_hash (hash_func (key));
 164         int i = hash & table_mask;
 165
 166         while (table->keys [i])
 167                 i = (i + 1) & table_mask;
 168
 169         set_key (table, i, key);
 170         set_value (table, i, value);
 171 }
 172
 173 static void
 174 expand_table (MonoConcGHashTable *hash_table)
 175 {
 176         conc_table *old_table = (conc_table*)hash_table->table;
 177         conc_table *new_table = conc_table_new (hash_table, old_table->table_size * EXPAND_RATIO);
 178         int i;
 179
 180         for (i = 0; i < old_table->table_size; ++i) {
 181                 if (old_table->keys [i] && !key_is_tombstone (hash_table, old_table->keys [i]))
 182                         insert_one_local (new_table, hash_table->hash_func, old_table->keys [i], old_table->values [i]);
 183         }
 184
 185         mono_memory_barrier ();
 186         hash_table->table = new_table;
 187         hash_table->overflow_count = (int)(new_table->table_size * LOAD_FACTOR);
 188         conc_table_lf_free (old_table);
 189 }
 190
 191
 192 MonoConcGHashTable *
 193 mono_conc_g_hash_table_new_type (GHashFunc hash_func, GEqualFunc key_equal_func, MonoGHashGCType type, MonoGCRootSource source, const char *msg)
 194 {
 195         MonoConcGHashTable *hash;
 196
 197         if (!hash_func)
 198                 hash_func = g_direct_hash;
 199
 200         hash = g_new0 (MonoConcGHashTable, 1);
 201         hash->hash_func = hash_func;
 202         hash->equal_func = key_equal_func;
 203
 204         hash->element_count = 0;
 205         hash->overflow_count = (int)(INITIAL_SIZE * LOAD_FACTOR);
 206         hash->gc_type = type;
 207         hash->source = source;
 208         hash->msg = msg;
 209
 210         hash->table = conc_table_new (hash, INITIAL_SIZE);
 211
 212         if (type > MONO_HASH_KEY_VALUE_GC)
 213                 g_error ("wrong type for gc hashtable");
 214
 215         return hash;
 216 }
 217
 218 gpointer
 219 mono_conc_g_hash_table_lookup (MonoConcGHashTable *hash, gconstpointer key)
 220 {
 221         gpointer orig_key, value;
 222
 223         if (mono_conc_g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 224                 return value;
 225         else
 226                 return NULL;
 227 }
 228
 229 gboolean
 230 mono_conc_g_hash_table_lookup_extended (MonoConcGHashTable *hash_table, gconstpointer key, gpointer *orig_key_ptr, gpointer *value_ptr)
 231 {
 232         MonoThreadHazardPointers* hp;
 233         conc_table *table;
 234         int hash, i, table_mask;
 235         hash = mix_hash (hash_table->hash_func (key));
 236         hp = mono_hazard_pointer_get ();
 237
 238 retry:
 239         table = (conc_table *)mono_get_hazardous_pointer ((gpointer volatile*)&hash_table->table, hp, 0);
 240         table_mask = table->table_size - 1;
 241         i = hash & table_mask;
 242
 243         if (G_LIKELY (!hash_table->equal_func)) {
 244                 while (table->keys [i]) {
 245                         gpointer orig_key = table->keys [i];
 246                         if (key == orig_key) {
 247                                 gpointer value;
 248                                 /* The read of keys must happen before the read of values */
 249                                 mono_memory_barrier ();
 250                                 value = table->values [i];
 251
 252                                 /* We just read a value been deleted, try again. */
 253                                 if (G_UNLIKELY (!value))
 254                                         goto retry;
 255
 256                                 mono_hazard_pointer_clear (hp, 0);
 257
 258                                 *orig_key_ptr = orig_key;
 259                                 *value_ptr = value;
 260                                 return TRUE;
 261                         }
 262                         i = (i + 1) & table_mask;
 263                 }
 264         } else {
 265                 GEqualFunc equal = hash_table->equal_func;
 266
 267                 while (table->keys [i]) {
 268                         gpointer orig_key = table->keys [i];
 269                         if (!key_is_tombstone (hash_table, orig_key) && equal (key, orig_key)) {
 270                                 gpointer value;
 271                                 /* The read of keys must happen before the read of values */
 272                                 mono_memory_barrier ();
 273                                 value = table->values [i];
 274
 275                                 /* We just read a value been deleted, try again. */
 276                                 if (G_UNLIKELY (!value))
 277                                         goto retry;
 278
 279                                 mono_hazard_pointer_clear (hp, 0);
 280                                 *orig_key_ptr = orig_key;
 281                                 *value_ptr = value;
 282                                 return TRUE;
 283
 284                         }
 285                         i = (i + 1) & table_mask;
 286                 }
 287         }
 288
 289         /* The table might have expanded and the value is now on the newer table */
 290         mono_memory_barrier ();
 291         if (hash_table->table != table)
 292                 goto retry;
 293
 294         mono_hazard_pointer_clear (hp, 0);
 295
 296         *orig_key_ptr = NULL;
 297         *value_ptr = NULL;
 298         return FALSE;
 299 }
 300
 301 void
 302 mono_conc_g_hash_table_foreach (MonoConcGHashTable *hash_table, GHFunc func, gpointer user_data)
 303 {
 304         int i;
 305         conc_table *table = (conc_table*)hash_table->table;
 306
 307         for (i = 0; i < table->table_size; ++i) {
 308                 if (table->keys [i] && !key_is_tombstone (hash_table, table->keys [i])) {
 309                         func (table->keys [i], table->values [i], user_data);
 310                 }
 311         }
 312 }
 313
 314 void
 315 mono_conc_g_hash_table_destroy (MonoConcGHashTable *hash_table)
 316 {
 317         if (hash_table->key_destroy_func || hash_table->value_destroy_func) {
 318                 int i;
 319                 conc_table *table = (conc_table*)hash_table->table;
 320
 321                 for (i = 0; i < table->table_size; ++i) {
 322                         if (table->keys [i] && !key_is_tombstone (hash_table, table->keys [i])) {
 323                                 if (hash_table->key_destroy_func)
 324                                         (hash_table->key_destroy_func) (table->keys [i]);
 325                                 if (hash_table->value_destroy_func)
 326                                         (hash_table->value_destroy_func) (table->values [i]);
 327                         }
 328                 }
 329         }
 330         conc_table_free ((gpointer)hash_table->table);
 331         g_free (hash_table);
 332 }
 333
 334 /* Return NULL on success or the old value in failure */
 335 gpointer
 336 mono_conc_g_hash_table_insert (MonoConcGHashTable *hash_table, gpointer key, gpointer value)
 337 {
 338         conc_table *table;
 339         int hash, i, table_mask;
 340
 341         g_assert (key != NULL);
 342         g_assert (value != NULL);
 343
 344         hash = mix_hash (hash_table->hash_func (key));
 345
 346         if (hash_table->element_count >= hash_table->overflow_count)
 347                 expand_table (hash_table);
 348
 349         table = (conc_table*)hash_table->table;
 350         table_mask = table->table_size - 1;
 351         i = hash & table_mask;
 352
 353         if (!hash_table->equal_func) {
 354                 for (;;) {
 355                         gpointer cur_key = table->keys [i];
 356                         if (!cur_key || key_is_tombstone (hash_table, cur_key)) {
 357                                 set_value (table, i, value);
 358
 359                                 /* The write to values must happen after the write to keys */
 360                                 mono_memory_barrier ();
 361                                 set_key (table, i, key);
 362                                 ++hash_table->element_count;
 363                                 return NULL;
 364                         }
 365                         if (key == cur_key) {
 366                                 gpointer value = table->values [i];
 367                                 return value;
 368                         }
 369                         i = (i + 1) & table_mask;
 370                 }
 371         } else {
 372                 GEqualFunc equal = hash_table->equal_func;
 373                 for (;;) {
 374                         gpointer cur_key = table->keys [i];
 375                         if (!cur_key || key_is_tombstone (hash_table, cur_key)) {
 376                                 set_value (table, i, value);
 377                                 /* The write to values must happen after the write to keys */
 378                                 mono_memory_barrier ();
 379                                 set_key (table, i, key);
 380                                 ++hash_table->element_count;
 381                                 return NULL;
 382                         }
 383                         if (equal (key, cur_key)) {
 384                                 gpointer value = table->values [i];
 385                                 return value;
 386                         }
 387                         i = (i + 1) & table_mask;
 388                 }
 389         }
 390 }
 391
 392 gpointer
 393 mono_conc_g_hash_table_remove (MonoConcGHashTable *hash_table, gconstpointer key)
 394 {
 395         conc_table *table;
 396         int hash, i, table_mask;
 397
 398         g_assert (key != NULL);
 399
 400         hash = mix_hash (hash_table->hash_func (key));
 401
 402         table = (conc_table*)hash_table->table;
 403         table_mask = table->table_size - 1;
 404         i = hash & table_mask;
 405
 406         if (!hash_table->equal_func) {
 407                 for (;;) {
 408                         gpointer cur_key = table->keys [i];
 409                         if (!cur_key) {
 410                                 return NULL; /*key not found*/
 411                         }
 412
 413                         if (key == cur_key) {
 414                                 gpointer value = table->values [i];
 415                                 table->values [i] = NULL;
 416                                 mono_memory_barrier ();
 417                                 set_key_to_tombstone (table, i);
 418
 419                                 --hash_table->element_count;
 420
 421                                 if (hash_table->key_destroy_func != NULL)
 422                                         (*hash_table->key_destroy_func) (cur_key);
 423                                 if (hash_table->value_destroy_func != NULL)
 424                                         (*hash_table->value_destroy_func) (value);
 425
 426                                 return value;
 427                         }
 428                         i = (i + 1) & table_mask;
 429                 }
 430         } else {
 431                 GEqualFunc equal = hash_table->equal_func;
 432                 for (;;) {
 433                         gpointer cur_key = table->keys [i];
 434                         if (!cur_key) {
 435                                 return NULL; /*key not found*/
 436                         }
 437
 438                         if (!key_is_tombstone (hash_table, cur_key) && equal (key, cur_key)) {
 439                                 gpointer value = table->values [i];
 440                                 table->values [i] = NULL;
 441                                 mono_memory_barrier ();
 442                                 set_key_to_tombstone (table, i);
 443
 444                                 if (hash_table->key_destroy_func != NULL)
 445                                         (*hash_table->key_destroy_func) (cur_key);
 446                                 if (hash_table->value_destroy_func != NULL)
 447                                         (*hash_table->value_destroy_func) (value);
 448                                 return value;
 449                         }
 450
 451                         i = (i + 1) & table_mask;
 452                 }
 453         }
 454 }