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