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