code.grnet.gr Git - archipelago/blob - xseg/xtypes/xq_test.c

   1 /*
   2  * Copyright 2012 GRNET S.A. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or
   5  * without modification, are permitted provided that the following
   6  * conditions are met:
   7  *
   8  *   1. Redistributions of source code must retain the above
   9  *      copyright notice, this list of conditions and the following
  10  *      disclaimer.
  11  *   2. Redistributions in binary form must reproduce the above
  12  *      copyright notice, this list of conditions and the following
  13  *      disclaimer in the documentation and/or other materials
  14  *      provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
  17  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  23  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  24  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  26  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27  * POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * The views and conclusions contained in the software and
  30  * documentation are those of the authors and should not be
  31  * interpreted as representing official policies, either expressed
  32  * or implied, of GRNET S.A.
  33  */
  34
  35 #define _GNU_SOURCE
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <math.h>
  39 #include <pthread.h>
  40 #include <sys/time.h>
  41 #include <assert.h>
  42
  43 #include "xq.h"
  44
  45 struct item {
  46     long   seed;
  47     double seed_sin;
  48     long   seed_times_sin;
  49     long   seed_xor_times;
  50 };
  51
  52 void item_calculate(struct item *item) {
  53     item->seed_sin = sin(item->seed | 1);
  54     item->seed_times_sin = (double)(item->seed | 1) * item->seed_sin;
  55     item->seed_xor_times = item->seed ^ item->seed_times_sin;
  56 }
  57
  58 int item_verify(struct item *item) {
  59     struct item t;
  60
  61     t.seed = item->seed;
  62     item_calculate(&t);
  63
  64     /*
  65     printf("seed %ld, sin: %lf, times: %ld, xor: %ld\n",
  66            item->seed, item->seed_sin, item->seed_times_sin, item->seed_xor_times);
  67     */
  68
  69     if (t.seed_sin       != item->seed_sin       ||
  70         t.seed_times_sin != item->seed_times_sin ||
  71         t.seed_xor_times != item->seed_xor_times) {
  72         printf("seed %ld, sin: %lf, times: %ld, xor: %ld\n",
  73                item->seed, item->seed_sin, item->seed_times_sin, item->seed_xor_times);
  74         return 0;
  75     }
  76
  77     return 1;
  78 }
  79
  80 int basic_sanity_test(struct xq *q) {
  81     xqindex t, r;
  82
  83     //printf("append_tail 9183\n");
  84     r = xq_append_tail(q, 9183, 0);
  85     //xq_print(q);
  86     //printf("\n");
  87     assert(r != Noneidx);
  88
  89     //printf("pop_head 9183\n");
  90     r = xq_pop_head(q, 0);
  91     //xq_print(q);
  92     //printf("\n");
  93     assert(r == 9183);
  94
  95     //printf("append_head 1834\n");
  96     r = xq_append_head(q, 1834, 0);
  97     //xq_print(q);
  98     //printf("\n");
  99     assert(r != Noneidx);
 100
 101     //printf("pop_tail 1834\n");
 102     r = xq_pop_tail(q, 0);
 103     //xq_print(q);
 104     //printf("\n");
 105     assert(r == 1834);
 106
 107     //printf("append_tail 3814\n");
 108     xq_append_tail(q, 3814, 0);
 109     //xq_print(q);
 110     //printf("\n");
 111
 112     //printf("append_head 5294\n");
 113     xq_append_head(q, 5294, 0);
 114     //xq_print(q);
 115     //printf("\n");
 116
 117     //printf("append_tail 1983\n");
 118     r = xq_append_tail(q, 1983, 0);
 119     //xq_print(q);
 120     //printf("\n");
 121     assert(r != Noneidx);
 122
 123     //printf("pop_tail 1983\n");
 124     r = xq_pop_tail(q, 0);
 125     //xq_print(q);
 126     //printf("\n");
 127     assert(r == 1983);
 128
 129     //printf("append_head 8134\n");
 130     r = xq_append_head(q, 8134, 0);
 131     //xq_print(q);
 132     //printf("\n");
 133     assert(r != Noneidx);
 134
 135     //printf("pop_head 8134\n");
 136     r = xq_pop_head(q, 0);
 137     //xq_print(q);
 138     //printf("\n");
 139     assert(r == 8134);
 140
 141     //printf("pop_tail 3814\n");
 142     r = xq_pop_tail(q, 0);
 143     //xq_print(q);
 144     //printf("\n");
 145     assert(r == 3814);
 146
 147     //printf("pop_head 5294\n");
 148     r = xq_pop_head(q, 0);
 149     //xq_print(q);
 150     //printf("\n");
 151     assert(r == 5294);
 152
 153     //printf("pop_tail Noneidx\n");
 154     r = xq_pop_tail(q, 0);
 155     //xq_print(q);
 156     //printf("\n");
 157     assert(r == Noneidx);
 158
 159     //printf("pop_head Noneidx\n");
 160     r = xq_pop_head(q, 0);
 161     //xq_print(q);
 162     //printf("\n");
 163     assert(r == Noneidx);
 164
 165     xqindex qsize = q->size;
 166     for (t = 0; t < qsize; t += 1) {
 167          r = xq_append_tail(q, t, 0);
 168          //if (r == Noneidx) printf("Noneidx: %lu\n", (unsigned long)t);
 169          //xq_print(q);
 170          assert(r != Noneidx);
 171     }
 172
 173     //xq_print(q);
 174
 175     for (t = qsize-1; t != Noneidx; t -= 1) {
 176          r = xq_pop_tail(q, 0);
 177          assert(t == r);
 178          //printf("%lu vs %lu\n", t, (unsigned long)xq_pop_tail(q));
 179     }
 180
 181     return 0;
 182 }
 183
 184 struct thread_data {
 185     long loops;
 186     struct xq *q;
 187     struct item *items;
 188     struct random_data *rdata;
 189     long size;
 190     int id;
 191 };
 192
 193 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
 194
 195 void *random_test_thread(void *arg) {
 196     struct thread_data *th = arg;
 197     long loops = th->loops;
 198     struct xq *q = th->q;
 199     struct item *items = th->items;
 200     //struct random_data *rdata = th->rdata;
 201     int id = th->id;
 202     long i;
 203
 204
 205     /*
 206     pthread_mutex_lock(&mutex);
 207     printf("---->\n");
 208     xq_print(&q[0]);
 209     xq_print(&q[1]);
 210     printf("<----\n");
 211     pthread_mutex_unlock(&mutex);
 212     */
 213
 214     for (i = 0; i < loops; i++) {
 215          int32_t rand;
 216          xqindex xqi;
 217
 218          if ((i & (1024*1024 -1)) == 0) {
 219              printf("%d %ld\n", id, i);
 220          }
 221
 222          //random_r(rdata, &rand);
 223          rand = random();
 224
 225          switch (rand & 3) {
 226          case 0:
 227              xqi = xq_pop_tail(&q[0], arg);
 228              if (xqi == Noneidx) goto unlock;
 229              items[xqi].seed = rand;
 230              item_calculate(&items[xqi]);
 231              xq_append_head(&q[1], xqi, arg);
 232              break;
 233          case 1:
 234              xqi = xq_pop_head(&q[0], arg);
 235              if (xqi == Noneidx) goto unlock;
 236              items[xqi].seed = rand;
 237              item_calculate(&items[xqi]);
 238              xq_append_tail(&q[1], xqi, arg);
 239              break;
 240          case 2:
 241              xqi = xq_pop_tail(&q[1], arg);
 242              if (xqi == Noneidx) goto unlock;
 243              items[xqi].seed = rand;
 244              item_calculate(&items[xqi]);
 245              xq_append_head(&q[0], xqi, arg);
 246              break;
 247          case 3:
 248              xqi = xq_pop_head(&q[1], arg);
 249              if (xqi == Noneidx) goto unlock;
 250              items[xqi].seed = rand;
 251              item_calculate(&items[xqi]);
 252              xq_append_tail(&q[0], xqi, arg);
 253              break;
 254          }
 255     unlock:
 256          ;
 257     }
 258
 259     return NULL;
 260 }
 261
 262 int error(const char *msg) {
 263     perror(msg);
 264     return 1;
 265 }
 266
 267 int random_test(long seed, long nr_threads, long loops, xqindex qsize, struct xq *q) {
 268     srandom(seed);
 269
 270     struct thread_data *th = malloc(nr_threads * sizeof(struct thread_data));
 271     if (!th) return error("malloc");
 272
 273     long t, r;
 274
 275     struct item *items = malloc(qsize * sizeof(struct item));
 276     if (!items) return error("malloc");
 277
 278     for (t = 0; t < qsize; t += 1) item_calculate(&items[t]);
 279
 280     for (t = 0; t < qsize; t += 4) {
 281          xq_append_tail(&q[0], t+0, 0);
 282          xq_append_head(&q[0], t+1, 0);
 283          xq_append_tail(&q[1], t+2, 0);
 284          xq_append_head(&q[1], t+3, 0);
 285     }
 286
 287     pthread_t *threads = malloc(nr_threads * sizeof(pthread_t));
 288     if (!threads) return error("malloc");
 289
 290     //struct random_data *rdata = malloc(nr_threads * sizeof(struct random_data));
 291     //if (!rdata) return error("malloc");
 292
 293     for (t = 0; t < nr_threads; t++) {
 294          th[t].id = t;
 295          th[t].loops = loops;
 296          th[t].size = qsize;
 297          th[t].q = q;
 298          //th[t].rdata = &rdata[t];
 299          th[t].items = items;
 300          //srandom_r(random(), th[t].rdata);
 301     }
 302
 303     for (t = 0; t < nr_threads; t++) {
 304          r = pthread_create(&threads[t], NULL, random_test_thread, &th[t]);
 305          if (r) return error("pthread_create");
 306     }
 307
 308     for (t = 0; t < nr_threads; t++) {
 309          pthread_join(threads[t], NULL);
 310     }
 311
 312     int errors = 0;
 313     for (t = 0; t < qsize; t++) {
 314          if (!item_verify(&items[t])) {
 315              errors ++;
 316              printf("error: item %ld\n", t);
 317          };
 318     }
 319
 320     return errors;
 321 }
 322
 323 struct xq q[2];
 324
 325 int main(int argc, char **argv) {
 326     int r;
 327
 328     if (argc < 5) {
 329         printf("Usage: struct xqest <seed> <nr_threads> <nr_loops> <qsize>\n");
 330         return 1;
 331     }
 332
 333     long seed = atol(argv[1]);
 334     int nr_threads = atoi(argv[2]);
 335     long loops = atol(argv[3]);
 336     long qsize = atol(argv[4]);
 337
 338     if (nr_threads < 0) nr_threads = 2;
 339     if (loops < 0) loops = 1000;
 340     if (qsize < 0) qsize = 1000;
 341
 342     xq_alloc_empty(&q[0], qsize);
 343     xq_alloc_empty(&q[1], qsize);
 344     qsize = q[0].size;
 345     assert(q[1].size == qsize);
 346
 347     r = basic_sanity_test(&q[0]);
 348     if (r) return r;
 349     printf("basic sanity test complete.\n");
 350
 351     struct timeval tv0, tv1;
 352     gettimeofday(&tv0, NULL);
 353     r = random_test(seed, nr_threads, loops, qsize, q);
 354     gettimeofday(&tv1, NULL);
 355     double seconds = tv1.tv_sec + tv1.tv_usec/1000000.0 - tv0.tv_sec - tv0.tv_usec / 1000000.0;
 356     printf("random multi-thread test complete with %d errors in %lf seconds\n", r, seconds);
 357     if (r) return r;
 358
 359     return 0;
 360 }