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