mono/unit-tests/test-mono-linked-list-set.c

   1 #include <assert.h>
   2 #include <pthread.h>
   3
   4 #include <config.h>
   5 #include <mono/metadata/metadata.h>
   6 #include <mono/utils/mono-threads.h>
   7 #include <mono/utils/hazard-pointer.h>
   8 #include <mono/utils/mono-linked-list-set.h>
   9 #include <mono/utils/atomic.h>
  10
  11 static MonoLinkedListSet lls;
  12
  13 enum {
  14         STATE_OUT,
  15         STATE_BUSY,
  16         STATE_IN
  17 };
  18
  19 #define N 23
  20 #define NUM_ITERS 1000000
  21 #define NUM_THREADS 8
  22
  23 typedef struct {
  24         MonoLinkedListSetNode node;
  25         int state;
  26 } node_t;
  27
  28 typedef struct {
  29         int skip;
  30         int num_adds;
  31         int num_removes;
  32         pthread_t thread;
  33 } thread_data_t;
  34
  35 static node_t nodes [N];
  36
  37 static inline void
  38 mono_hazard_pointer_clear_all (MonoThreadHazardPointers *hp, int retain)
  39 {
  40         if (retain != 0)
  41                 mono_hazard_pointer_clear (hp, 0);
  42         if (retain != 1)
  43                 mono_hazard_pointer_clear (hp, 1);
  44         if (retain != 2)
  45                 mono_hazard_pointer_clear (hp, 2);
  46 }
  47
  48 static void
  49 free_node (void *n)
  50 {
  51         node_t *node = (node_t *)n;
  52         assert (node->state == STATE_BUSY);
  53         node->state = STATE_OUT;
  54 }
  55
  56 static void*
  57 worker (void *arg)
  58 {
  59         thread_data_t *thread_data = (thread_data_t *)arg;
  60         MonoThreadHazardPointers *hp;
  61         int skip = thread_data->skip;
  62         int i, j;
  63         gboolean result;
  64
  65         mono_thread_info_register_small_id ();
  66
  67         hp = mono_hazard_pointer_get ();
  68
  69         i = 0;
  70         for (j = 0; j < NUM_ITERS; ++j) {
  71                 switch (nodes [i].state) {
  72                 case STATE_BUSY:
  73                         mono_thread_hazardous_try_free_some ();
  74                         break;
  75                 case STATE_OUT:
  76                         if (mono_atomic_cas_i32 (&nodes [i].state, STATE_BUSY, STATE_OUT) == STATE_OUT) {
  77                                 result = mono_lls_find (&lls, hp, i);
  78                                 assert (!result);
  79                                 mono_hazard_pointer_clear_all (hp, -1);
  80
  81                                 result = mono_lls_insert (&lls, hp, &nodes [i].node);
  82                                 mono_hazard_pointer_clear_all (hp, -1);
  83
  84                                 assert (nodes [i].state == STATE_BUSY);
  85                                 nodes [i].state = STATE_IN;
  86
  87                                 ++thread_data->num_adds;
  88                         }
  89                         break;
  90                 case STATE_IN:
  91                         if (mono_atomic_cas_i32 (&nodes [i].state, STATE_BUSY, STATE_IN) == STATE_IN) {
  92                                 result = mono_lls_find (&lls, hp, i);
  93                                 assert (result);
  94                                 assert (mono_hazard_pointer_get_val (hp, 1) == &nodes [i].node);
  95                                 mono_hazard_pointer_clear_all (hp, -1);
  96
  97                                 result = mono_lls_remove (&lls, hp, &nodes [i].node);
  98                                 mono_hazard_pointer_clear_all (hp, -1);
  99
 100                                 ++thread_data->num_removes;
 101                         }
 102                         break;
 103                 default:
 104                         assert (FALSE);
 105                 }
 106
 107                 i += skip;
 108                 if (i >= N)
 109                         i -= N;
 110         }
 111
 112         return NULL;
 113 }
 114
 115 #ifdef __cplusplus
 116 extern "C"
 117 #endif
 118 int
 119 test_mono_linked_list_set_main (void);
 120
 121 int
 122 test_mono_linked_list_set_main (void)
 123 {
 124         int primes [] = { 1, 2, 3, 5, 7, 11, 13, 17 };
 125         thread_data_t thread_data [NUM_THREADS];
 126         int i;
 127
 128         mono_metadata_init ();
 129
 130         mono_thread_info_init (0);
 131
 132         mono_lls_init (&lls, free_node);
 133
 134         for (i = 0; i < N; ++i) {
 135                 nodes [i].node.key = i;
 136                 nodes [i].state = STATE_OUT;
 137         }
 138
 139         for (i = 0; i < NUM_THREADS; ++i) {
 140                 int result;
 141
 142                 thread_data [i].num_adds = thread_data [i].num_removes = 0;
 143                 thread_data [i].skip = primes [i];
 144                 result = pthread_create (&thread_data [i].thread, NULL, worker, &thread_data [i]);
 145                 assert (!result);
 146         }
 147
 148         for (i = 0; i < NUM_THREADS; ++i) {
 149                 int result = pthread_join (thread_data [i].thread, NULL);
 150                 assert (!result);
 151                 printf ("thread %d  adds %d  removes %d\n", i, thread_data [i].num_adds, thread_data [i].num_removes);
 152         }
 153
 154         return 0;
 155 }