mono/unit-tests/test-conc-hashtable.c

   1 /*
   2  * test-conc-hashtable.c: Unit test for the concurrent hashtable.
   3  *
   4  * Copyright (C) 2014 Xamarin Inc
   5  *
   6  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   7  */
   8
   9 #include "config.h"
  10
  11 #include "utils/mono-threads.h"
  12 #include "utils/mono-conc-hashtable.h"
  13 #include "utils/checked-build.h"
  14 #include "metadata/w32handle.h"
  15
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include <time.h>
  19 #include <assert.h>
  20
  21 #include <pthread.h>
  22
  23 static int
  24 single_writer_single_reader (void)
  25 {
  26         mono_mutex_t mutex;
  27         MonoConcurrentHashTable *h;
  28         int res = 0;
  29
  30         mono_os_mutex_init (&mutex);
  31         h = mono_conc_hashtable_new (NULL, NULL);
  32
  33         mono_os_mutex_lock (&mutex);
  34         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (10), GUINT_TO_POINTER (20));
  35         mono_os_mutex_unlock (&mutex);
  36
  37         mono_os_mutex_lock (&mutex);
  38         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (30), GUINT_TO_POINTER (40));
  39         mono_os_mutex_unlock (&mutex);
  40
  41         mono_os_mutex_lock (&mutex);
  42         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (50), GUINT_TO_POINTER (60));
  43         mono_os_mutex_unlock (&mutex);
  44
  45         mono_os_mutex_lock (&mutex);
  46         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (2), GUINT_TO_POINTER (3));
  47         mono_os_mutex_unlock (&mutex);
  48
  49         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (30)) != GUINT_TO_POINTER (40))
  50                 res = 1;
  51         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (10)) != GUINT_TO_POINTER (20))
  52                 res = 2;
  53         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (2)) != GUINT_TO_POINTER (3))
  54                 res = 3;
  55         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (50)) != GUINT_TO_POINTER (60))
  56                 res = 4;
  57
  58         mono_conc_hashtable_destroy (h);
  59         mono_os_mutex_destroy (&mutex);
  60         if (res)
  61                 printf ("SERIAL TEST FAILED %d\n", res);
  62         return res;
  63 }
  64
  65 static MonoConcurrentHashTable *hash;
  66 static mono_mutex_t global_mutex;
  67
  68 static void*
  69 pw_sr_thread (void *arg)
  70 {
  71         int i, idx = 1000 * GPOINTER_TO_INT (arg);
  72         mono_thread_info_attach ((gpointer)&arg);
  73
  74         for (i = 0; i < 1000; ++i) {
  75                 mono_os_mutex_lock (&global_mutex);
  76                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + idx), GINT_TO_POINTER (i + 1));
  77                 mono_os_mutex_unlock (&global_mutex);
  78         }
  79         return NULL;
  80 }
  81
  82 static int
  83 parallel_writer_single_reader (void)
  84 {
  85         pthread_t a,b,c;
  86         int i, j, res = 0;
  87
  88         mono_os_mutex_init (&global_mutex);
  89         hash = mono_conc_hashtable_new (NULL, NULL);
  90
  91         pthread_create (&a, NULL, pw_sr_thread, GINT_TO_POINTER (1));
  92         pthread_create (&b, NULL, pw_sr_thread, GINT_TO_POINTER (2));
  93         pthread_create (&c, NULL, pw_sr_thread, GINT_TO_POINTER (3));
  94
  95         pthread_join (a, NULL);
  96         pthread_join (b, NULL);
  97         pthread_join (c, NULL);
  98
  99         for (i = 0; i < 1000; ++i) {
 100                 for (j = 1; j < 4; ++j) {
 101                         if (mono_conc_hashtable_lookup (hash, GINT_TO_POINTER (j * 1000 + i)) != GINT_TO_POINTER (i + 1)) {
 102                                 res = j + 1;
 103                                 goto done;
 104                         }
 105                 }
 106         }
 107
 108 done:
 109         mono_conc_hashtable_destroy (hash);
 110         mono_os_mutex_destroy (&global_mutex);
 111         if (res)
 112                 printf ("PAR_WRITER_SINGLE_READER TEST FAILED %d\n", res);
 113         return res;
 114 }
 115
 116
 117 static void*
 118 pr_sw_thread (void *arg)
 119 {
 120         int i = 0, idx = 100 * GPOINTER_TO_INT (arg);
 121         mono_thread_info_attach ((gpointer)&arg);
 122
 123         while (i < 100) {
 124                 gpointer res = mono_conc_hashtable_lookup (hash, GINT_TO_POINTER (i + idx + 1));
 125                 if (!res)
 126                         continue;
 127                 if (res != GINT_TO_POINTER ((i + idx) * 2 + 1))
 128                         return GINT_TO_POINTER (i);
 129                 ++i;
 130         }
 131         return NULL;
 132 }
 133
 134 static int
 135 single_writer_parallel_reader (void)
 136 {
 137         pthread_t a,b,c;
 138         gpointer ra, rb, rc;
 139         int i, res = 0;
 140         ra = rb = rc = GINT_TO_POINTER (1);
 141
 142         mono_os_mutex_init (&global_mutex);
 143         hash = mono_conc_hashtable_new (NULL, NULL);
 144
 145         pthread_create (&a, NULL, pr_sw_thread, GINT_TO_POINTER (0));
 146         pthread_create (&b, NULL, pr_sw_thread, GINT_TO_POINTER (1));
 147         pthread_create (&c, NULL, pr_sw_thread, GINT_TO_POINTER (2));
 148
 149         for (i = 0; i < 100; ++i) {
 150                 mono_os_mutex_lock (&global_mutex);
 151                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i +   0 + 1), GINT_TO_POINTER ((i +   0) * 2 + 1));
 152                 mono_os_mutex_unlock (&global_mutex);
 153
 154                 mono_os_mutex_lock (&global_mutex);
 155                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + 100 + 1), GINT_TO_POINTER ((i + 100) * 2 + 1));
 156                 mono_os_mutex_unlock (&global_mutex);
 157
 158                 mono_os_mutex_lock (&global_mutex);
 159                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + 200 + 1), GINT_TO_POINTER ((i + 200) * 2 + 1));
 160                 mono_os_mutex_unlock (&global_mutex);
 161         }
 162
 163         pthread_join (a, &ra);
 164         pthread_join (b, &rb);
 165         pthread_join (c, &rc);
 166         res = GPOINTER_TO_INT (ra) + GPOINTER_TO_INT (rb) + GPOINTER_TO_INT (rc);
 167
 168         mono_conc_hashtable_destroy (hash);
 169         mono_os_mutex_destroy (&global_mutex);
 170         if (res)
 171                 printf ("SINGLE_WRITER_PAR_READER TEST FAILED %d\n", res);
 172         return res;
 173 }
 174
 175 int running = 1;
 176
 177 static void*
 178 pw_pr_r_thread (void *arg)
 179 {
 180         int key, val, i;
 181         mono_thread_info_attach ((gpointer)&arg);
 182
 183         /* i will not be incremented as long as running is set to 1, this guarantee that
 184            we loop over all the keys at least once after the writer threads have finished */
 185         for (i = 0; i < 2; i += 1 - running) {
 186                 for (key = 1; key < 3 * 1000 + 1; key++) {
 187                         val = GPOINTER_TO_INT (mono_conc_hashtable_lookup (hash, GINT_TO_POINTER (key)));
 188
 189                         if (!val)
 190                                 continue;
 191                         if (key != val)
 192                                 return GINT_TO_POINTER (key);
 193                 }
 194         }
 195         return NULL;
 196 }
 197
 198 static void*
 199 pw_pr_w_add_thread (void *arg)
 200 {
 201         int i, idx = 1000 * GPOINTER_TO_INT (arg);
 202
 203         mono_thread_info_attach ((gpointer)&arg);
 204
 205         for (i = idx; i < idx + 1000; i++) {
 206                 mono_os_mutex_lock (&global_mutex);
 207                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + 1), GINT_TO_POINTER (i + 1));
 208                 mono_os_mutex_unlock (&global_mutex);
 209         }
 210         return NULL;
 211 }
 212
 213 static void*
 214 pw_pr_w_del_thread (void *arg)
 215 {
 216         int i, idx = 1000 * GPOINTER_TO_INT (arg);
 217
 218         mono_thread_info_attach ((gpointer)&arg);
 219
 220         for (i = idx; i < idx + 1000; i++) {
 221                 mono_os_mutex_lock (&global_mutex);
 222                 mono_conc_hashtable_remove (hash, GINT_TO_POINTER (i + 1));
 223                 mono_os_mutex_unlock (&global_mutex);
 224         }
 225         return NULL;
 226 }
 227
 228 static int
 229 parallel_writer_parallel_reader (void)
 230 {
 231         pthread_t wa, wb, wc, ra, rb, rc;
 232         gpointer a, b, c;
 233         int res = 0, i;
 234
 235         srand(time(NULL));
 236
 237         mono_os_mutex_init (&global_mutex);
 238         hash = mono_conc_hashtable_new (NULL, NULL);
 239
 240         for (i = 0; i < 2; i++) {
 241                 running = 1;
 242
 243                 pthread_create (&ra, NULL, pw_pr_r_thread, NULL);
 244                 pthread_create (&rb, NULL, pw_pr_r_thread, NULL);
 245                 pthread_create (&rc, NULL, pw_pr_r_thread, NULL);
 246
 247                 switch (i) {
 248                 case 0:
 249                         pthread_create (&wa, NULL, pw_pr_w_add_thread, GINT_TO_POINTER (0));
 250                         pthread_create (&wb, NULL, pw_pr_w_add_thread, GINT_TO_POINTER (1));
 251                         pthread_create (&wc, NULL, pw_pr_w_add_thread, GINT_TO_POINTER (2));
 252                         break;
 253                 case 1:
 254                         pthread_create (&wa, NULL, pw_pr_w_del_thread, GINT_TO_POINTER (0));
 255                         pthread_create (&wb, NULL, pw_pr_w_del_thread, GINT_TO_POINTER (1));
 256                         pthread_create (&wc, NULL, pw_pr_w_del_thread, GINT_TO_POINTER (2));
 257                         break;
 258                 }
 259
 260                 pthread_join (wa, NULL);
 261                 pthread_join (wb, NULL);
 262                 pthread_join (wc, NULL);
 263
 264                 running = 0;
 265
 266                 pthread_join (ra, &a);
 267                 pthread_join (rb, &b);
 268                 pthread_join (rc, &c);
 269
 270                 res += GPOINTER_TO_INT (a) + GPOINTER_TO_INT (b) + GPOINTER_TO_INT (c);
 271         }
 272
 273         if (res)
 274                 printf ("PAR_WRITER_PAR_READER TEST FAILED %d %d %d\n", GPOINTER_TO_INT (a), GPOINTER_TO_INT (b), GPOINTER_TO_INT (c));
 275
 276         mono_conc_hashtable_destroy (hash);
 277         mono_os_mutex_destroy (&global_mutex);
 278
 279         return res;
 280 }
 281
 282 static void G_GNUC_UNUSED
 283 benchmark_conc (void)
 284 {
 285         MonoConcurrentHashTable *h;
 286         int i, j;
 287
 288         h = mono_conc_hashtable_new (NULL, NULL);
 289
 290         for (i = 1; i < 10 * 1000; ++i) {
 291                 mono_conc_hashtable_insert (h, GUINT_TO_POINTER (i), GUINT_TO_POINTER (i));
 292         }
 293
 294
 295         for (j = 0; j < 100000; ++j)
 296                 for (i = 1; i < 10 * 105; ++i)
 297                         mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (i));
 298
 299         mono_conc_hashtable_destroy (h);
 300 }
 301
 302 static void G_GNUC_UNUSED
 303 benchmark_glib (void)
 304 {
 305         GHashTable *h;
 306         int i, j;
 307
 308         h = g_hash_table_new (NULL, NULL);
 309
 310         for (i = 1; i < 10 * 1000; ++i)
 311                 g_hash_table_insert (h, GUINT_TO_POINTER (i), GUINT_TO_POINTER (i));
 312
 313
 314         for (j = 0; j < 100000; ++j)
 315                 for (i = 1; i < 10 * 105; ++i)
 316                         g_hash_table_lookup (h, GUINT_TO_POINTER (i));
 317
 318         g_hash_table_destroy (h);
 319 }
 320
 321 static void
 322 thread_state_init (MonoThreadUnwindState *ctx)
 323 {
 324 }
 325
 326
 327 int
 328 main (void)
 329 {
 330         MonoThreadInfoCallbacks cb = { NULL };
 331         MonoThreadInfoRuntimeCallbacks ticallbacks;
 332         int res = 0;
 333
 334         CHECKED_MONO_INIT ();
 335         mono_threads_init (&cb, sizeof (MonoThreadInfo));
 336         memset (&ticallbacks, 0, sizeof (ticallbacks));
 337         ticallbacks.thread_state_init = thread_state_init;
 338         mono_threads_runtime_init (&ticallbacks);
 339 #ifndef HOST_WIN32
 340         mono_w32handle_init ();
 341 #endif
 342
 343         mono_thread_info_attach ((gpointer)&cb);
 344
 345         // benchmark_conc ();
 346         // benchmark_glib ();
 347
 348         res += single_writer_single_reader ();
 349         res += parallel_writer_single_reader ();
 350         res += single_writer_parallel_reader ();
 351         res += parallel_writer_parallel_reader ();
 352
 353         return res;
 354 }