src/mcas/skip_adt_test.c

   1 #include <sys/resource.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <errno.h>
   6 #include <sys/stat.h>
   7 #include <sys/types.h>
   8 #include <sys/time.h>
   9 #include <sys/times.h>
  10 #include <sys/mman.h>
  11 #include <fcntl.h>
  12 #include <unistd.h>
  13 #include <ucontext.h>
  14 #include <signal.h>
  15 #include <sched.h>
  16 #include <limits.h>
  17 #include <assert.h>
  18 #include <stdarg.h>
  19
  20 /* for mutex testing */
  21 #include <pthread.h>
  22
  23 #include "portable_defns.h"
  24 #include "set_queue_adt.h"
  25 #include "ptst.h"
  26
  27 #define CREATE_N 1000000
  28
  29 #define SENTINEL_KEYMIN ( 1UL)
  30 #define SENTINEL_KEYMAX (~0UL)
  31
  32 typedef struct {
  33     unsigned long key;
  34     unsigned long secret_key;
  35     unsigned long xxx[10];
  36     int traversal;
  37     pthread_mutex_t lock;
  38     void *gc_id;
  39 } harness_ulong_t;
  40
  41 static struct {
  42     CACHE_PAD(0);
  43     osi_set_t *set;
  44       CACHE_PAD(1);
  45     osi_set_t *set2;
  46       CACHE_PAD(2);
  47 } shared;
  48
  49 /* lock-free object cache */
  50
  51 typedef int osi_mcas_obj_cache_t;
  52
  53 void
  54 osi_mcas_obj_cache_create(osi_mcas_obj_cache_t * gc_id, size_t size)
  55 {                               /* alignment? */
  56     *(int *)gc_id = gc_add_allocator(size + sizeof(int *));
  57 }
  58
  59 void *
  60 osi_mcas_obj_cache_alloc(osi_mcas_obj_cache_t gc_id)
  61 {
  62     ptst_t *ptst;
  63     void *obj;
  64
  65     ptst = critical_enter();
  66     obj = (void *)gc_alloc(ptst, gc_id);
  67     critical_exit(ptst);
  68     return (obj);
  69 }
  70
  71 void
  72 osi_mcas_obj_cache_free(osi_mcas_obj_cache_t gc_id, void *obj)
  73 {
  74     ptst_t *ptst;
  75
  76     ptst = critical_enter();
  77     gc_free(ptst, (void *)obj, gc_id);
  78     critical_exit(ptst);
  79 }
  80
  81 void
  82 osi_mcas_obj_cache_destroy(osi_mcas_obj_cache_t gc_id)
  83 {
  84     // implement?
  85     return;
  86 }
  87
  88 /* lock-free object cache */
  89
  90 /* Key data type and comparison function */
  91 int
  92 harness_ulong_comp(const void *lhs, const void *rhs)
  93 {
  94     harness_ulong_t *l, *r;
  95
  96     l = (harness_ulong_t *) lhs;
  97     r = (harness_ulong_t *) rhs;
  98
  99     /* todo:  move to wrapper macro outside
 100      * cmpf */
 101
 102     if (lhs == (void *)SENTINEL_KEYMAX)
 103         return (1);
 104     if (rhs == (void *)SENTINEL_KEYMAX)
 105         return (-1);
 106
 107     if (lhs == (void *)SENTINEL_KEYMIN)
 108         return (-1);
 109     if (rhs == (void *)SENTINEL_KEYMIN)
 110         return (1);
 111     /* end todo */
 112
 113     if (l->key == r->key)
 114         return (0);
 115     if (l->key > r->key)
 116         return (1);
 117
 118     return (-1);
 119 }
 120
 121 void
 122 test_each_func(osi_set_t * l, setval_t v, void *arg)
 123 {
 124
 125     harness_ulong_t *z;
 126     osi_mcas_obj_cache_t gc_id;
 127     int traversal;
 128
 129     traversal = *(int *)arg;
 130     z = (harness_ulong_t *) v;
 131     gc_id = z->gc_id;
 132
 133     if (z->traversal == traversal)
 134         goto done;
 135
 136     if (z->key % 10 == 0) {
 137         printf("SPONGEBOB would delete key %d: secret key: %d (t: %d) \n",
 138                z->key, z->secret_key, z->traversal);
 139
 140         osi_cas_skip_remove(l, z);
 141         osi_mcas_obj_cache_free(gc_id, z);
 142     } else {
 143         printf("SQUAREPANTS still here key %d: secret key: %d (t: %d) \n",
 144                z->key, z->secret_key, z->traversal);
 145     }
 146
 147   done:
 148     z->traversal = traversal;
 149 }
 150
 151 void
 152 test_each_func_2(osi_set_t * l, setval_t v, void *arg)
 153 {
 154
 155     int traversal;
 156     harness_ulong_t *z;
 157
 158     traversal = *(int *)arg;
 159     z = (harness_ulong_t *) v;
 160
 161     if (z->traversal == traversal)
 162         goto done;
 163
 164     printf("SQUAREPANTS still here key %d: secret key: %d\n",
 165            z->key, z->secret_key);
 166   done:
 167     z->traversal = traversal;
 168 }
 169
 170 void
 171 thread_do_test(void *arg)
 172 {
 173     int ix, ix2, six, eix, sv;
 174     harness_ulong_t *node, *node2, *snode;
 175
 176     sv = *((int *)arg);
 177
 178     six = CREATE_N / 4 * sv;
 179     eix = six + CREATE_N / 4;
 180
 181     printf("Starting thread with %d %d %d\n", sv, six, eix);
 182
 183     /* Allocate nodes and insert in skip queue */
 184
 185     for (; six < eix; ++six) {
 186
 187         /* set 1 */
 188         node = (harness_ulong_t *) malloc(sizeof(harness_ulong_t));
 189         memset(node, 0, sizeof(harness_ulong_t));
 190         node->key = six;
 191         node->secret_key = 2 * six;
 192         printf("thread %d insert: %d key: %d secret: %d\n", sv, node,
 193                node->key, node->secret_key);
 194         osi_cas_skip_update(shared.set, node, node, 1);
 195
 196 #if 0                           /* reuse package test */
 197         /* set 2 */
 198         node2 = (harness_ulong_t *) malloc(sizeof(harness_ulong_t));
 199         memset(node2, 0, sizeof(harness_ulong_t));
 200         node2->key = six;
 201         node2->secret_key = 3 * six;
 202         printf("thread %d insert: %d key: %d secret: %d\n", sv, node2,
 203                node2->key, node2->secret_key);
 204         osi_cas_skip_update(shared.set2, node2, node2, 1);
 205 #endif
 206     }
 207
 208     snode = (harness_ulong_t *) malloc(sizeof(harness_ulong_t));
 209     goto tdone;
 210
 211     ix2 = 0;
 212     do {
 213         for (ix = 0; ix < CREATE_N; ix += 1) {
 214             snode->key = ix;
 215             node = osi_cas_skip_lookup(shared.set, snode);
 216             if (node) {
 217                 printf("thread %d searched set(1) for and found: key: "
 218                        "%d secret_key: %d\n",
 219                        sv, node->key, node->secret_key);
 220             } else {
 221                 printf("thread %d searched set(1) for and didn't find: %d\n",
 222                        sv, snode->key);
 223             }
 224 #if 0                           /* set2 */
 225             node = osi_cas_skip_lookup(shared.set2, snode);
 226             if (node) {
 227                 printf("thread %d searched set(2) for and found: key: "
 228                        "%d secret_key: %d\n",
 229                        sv, node->key, node->secret_key);
 230             } else {
 231                 printf("thread %d searched set(2) for and didn't find: %d\n",
 232                        sv, snode->key);
 233             }
 234 #endif
 235         }
 236         ix2++;
 237     } while (ix2 < 10000);
 238
 239     /* dump queue */
 240   tdone:
 241     ix2++;
 242
 243 }
 244
 245 /* help test atomic inc, dec */
 246
 247 typedef long osi_atomic_t;
 248
 249 #define osi_atomic_inc(x) \
 250 do { \
 251     RMB(); \
 252     FASPO(&x, x+1);     \
 253 } while(0);
 254
 255 #define osi_atomic_dec(x) \
 256 do { \
 257     RMB(); \
 258     FASPO(&x, x-1);     \
 259 } while(0);
 260
 261
 262 int
 263 main(int argc, char **argv)
 264 {
 265
 266     int ix, traversal;
 267     harness_ulong_t *node, *node2, *snode;
 268     osi_mcas_obj_cache_t gc_id, gc2_id;
 269
 270     printf("Starting ADT Test\n");
 271
 272     /* do this once, 1st thread */
 273     _init_ptst_subsystem();
 274     _init_gc_subsystem();
 275     _init_osi_cas_skip_subsystem();
 276
 277     osi_mcas_obj_cache_create(&gc_id, sizeof(harness_ulong_t));
 278     osi_mcas_obj_cache_create(&gc2_id, sizeof(harness_ulong_t));
 279
 280     shared.set = osi_cas_skip_alloc(&harness_ulong_comp);
 281     shared.set2 = osi_cas_skip_alloc(&harness_ulong_comp);
 282
 283     /* just insert and iterate */
 284
 285     for (ix = 0; ix < CREATE_N; ++ix) {
 286
 287         /* set 1 */
 288         node = (harness_ulong_t *) osi_mcas_obj_cache_alloc(gc_id);
 289         pthread_mutex_init(&node->lock, NULL);
 290
 291         /* and pound on collector 2 */
 292         node2 = (harness_ulong_t *) osi_mcas_obj_cache_alloc(gc2_id);
 293
 294         node->gc_id = gc_id;
 295         node->key = ix;
 296         node->secret_key = 2 * ix;
 297         printf("insert: %d key: %d secret: %d\n", node,
 298                node->key, node->secret_key);
 299         osi_cas_skip_update(shared.set, node, node, 1);
 300     }
 301
 302     snode = (harness_ulong_t *) osi_mcas_obj_cache_alloc(gc_id);
 303     snode->gc_id = gc_id;
 304     snode->key = 5;
 305     node = osi_cas_skip_lookup(shared.set, snode);
 306     if (node) {
 307         printf("searched set(1) for and found: key: "
 308                "%d secret_key: %d\n", node->key, node->secret_key);
 309     } else {
 310         printf("searched set(1) for and didn't find: %d\n", snode->key);
 311     }
 312
 313     sleep(1);
 314
 315     /* traversal is used to avoid acting on duplicate references (which
 316      * are an artifact of skip list implementation;  assumes only one
 317      * thread may be in set_for_each, as implemented */
 318
 319     printf("now... \n");
 320     traversal = 1;
 321     osi_cas_skip_for_each(shared.set, &test_each_func, &traversal);
 322
 323     sleep(1);
 324
 325     printf("now... \n");
 326     traversal = 2;
 327     osi_cas_skip_for_each(shared.set, &test_each_func_2, &traversal);
 328
 329     /* test osi_atomic_inc */
 330
 331     {
 332         int a_ix;
 333         osi_atomic_t ai;
 334
 335         for (ai = 0, a_ix = 0; a_ix < 10; ++a_ix) {
 336             osi_atomic_inc(ai);
 337         }
 338         osi_atomic_dec(ai);
 339
 340         printf("ai is: %d\n", ai);
 341     }
 342
 343     osi_mcas_obj_cache_free(gc_id, node);
 344
 345     return 0;
 346 }