src/mcas/set_harness.c

   1 /******************************************************************************
   2  * set_harness.c
   3  *
   4  * Test harness for the various set implementations.
   5  *
   6  * Copyright (c) 2002-2003, K A Fraser
   7
   8 Redistribution and use in source and binary forms, with or without
   9 modification, are permitted provided that the following conditions are
  10 met:
  11
  12     * Redistributions of source code must retain the above copyright
  13     * notice, this list of conditions and the following disclaimer.
  14     * Redistributions in binary form must reproduce the above
  15     * copyright notice, this list of conditions and the following
  16     * disclaimer in the documentation and/or other materials provided
  17     * with the distribution.  Neither the name of the Keir Fraser
  18     * nor the names of its contributors may be used to endorse or
  19     * promote products derived from this software without specific
  20     * prior written permission.
  21
  22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  25 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  26 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  27 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  28 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  32 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 #include <sys/resource.h>
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <errno.h>
  40 #include <sys/stat.h>
  41 #include <sys/types.h>
  42 #include <sys/time.h>
  43 #include <sys/times.h>
  44 #include <sys/mman.h>
  45 #include <fcntl.h>
  46 #include <unistd.h>
  47 #include <ucontext.h>
  48 #include <signal.h>
  49 #include <sched.h>
  50 #include <limits.h>
  51 #include <assert.h>
  52 #include <stdarg.h>
  53
  54 #include "portable_defns.h"
  55 #include "set.h"
  56 #include "ptst.h"
  57
  58 /* This produces an operation log for the 'replay' checker. */
  59 /*#define DO_WRITE_LOG*/
  60
  61 #ifdef DO_WRITE_LOG
  62 #define MAX_ITERATIONS 100000
  63 #define MAX_WALL_TIME 50 /* seconds */
  64 #else
  65 #define MAX_ITERATIONS 100000000
  66 #define MAX_WALL_TIME 10 /* seconds */
  67 #endif
  68
  69 /*
  70  * ***************** LOGGING
  71  */
  72
  73 #define MAX_LOG_RECORDS 256
  74
  75 #define LOG_KIND_INT 0
  76 #define LOG_KIND_STRING 1
  77 #define LOG_KIND_FLOAT 2
  78
  79 typedef struct {
  80     char *name;
  81     int kind;
  82     int val_int;
  83     char *val_string;
  84     float val_float;
  85 } log_record_t;
  86
  87 static log_record_t log_records[MAX_LOG_RECORDS];
  88
  89 static int num_log_records = 0;
  90
  91 static void log_int (char *name, int val) {
  92     log_records[num_log_records].name = name;
  93     log_records[num_log_records].kind = LOG_KIND_INT;
  94     log_records[num_log_records].val_int = val;
  95     num_log_records ++;
  96 }
  97
  98 static void log_string (char *name, char *val) {
  99     log_records[num_log_records].name = name;
 100     log_records[num_log_records].kind = LOG_KIND_STRING;
 101     log_records[num_log_records].val_string = val;
 102     num_log_records ++;
 103 }
 104
 105 static void log_float (char *name, float val) {
 106     log_records[num_log_records].name = name;
 107     log_records[num_log_records].kind = LOG_KIND_FLOAT;
 108     log_records[num_log_records].val_float = val;
 109     num_log_records ++;
 110 }
 111
 112 static void dump_log (void) {
 113     int i;
 114
 115     fprintf (stdout, "-------------------------------------------"
 116              "---------------------------\n");
 117     for (i = 0; i < num_log_records; i ++)
 118     {
 119         char padding[40];
 120         strcpy(padding, "                                        ");
 121         if (30-strlen(log_records[i].name) >= 0){
 122             padding[30-strlen(log_records[i].name)] = '\0';
 123         }
 124         fprintf (stdout, "%s%s = ", padding, log_records[i].name);
 125         {
 126             int kind = log_records [i].kind;
 127             if (kind == LOG_KIND_INT) {
 128                 fprintf (stdout, "%d\n", log_records[i].val_int);
 129             } else if (kind == LOG_KIND_STRING) {
 130                 fprintf (stdout, "%s\n", log_records[i].val_string);
 131             } else if (kind == LOG_KIND_FLOAT) {
 132                 fprintf (stdout, "%.3f\n", log_records[i].val_float);
 133             }
 134         }
 135     }
 136     fprintf (stdout, "-------------------------------------------"
 137              "---------------------------\n");
 138
 139     for (i = 0; i < num_log_records; i ++)
 140     {
 141         int kind = log_records [i].kind;
 142         if (i != 0) { fprintf (stderr, " "); }
 143         if (kind == LOG_KIND_INT) {
 144             fprintf (stderr, "%d", log_records[i].val_int);
 145         } else if (kind == LOG_KIND_STRING) {
 146             fprintf (stderr, "%s", log_records[i].val_string);
 147         } else if (kind == LOG_KIND_FLOAT) {
 148             fprintf (stderr, "%.3f", log_records[i].val_float);
 149         }
 150     }
 151     fprintf (stderr, " LOG\n");
 152 }
 153
 154 /*
 155  * ************** END OF LOGGING
 156  */
 157
 158 #define TVAL(x) ((x.tv_sec * 1000000) + x.tv_usec)
 159
 160 /* Log tables. Written out at end-of-day. */
 161 typedef struct log_st
 162 {
 163     interval_t    start, end;
 164     unsigned int  key;
 165     void         *val, *old_val; /* @old_val used by update() and remove() */
 166 } log_t;
 167 #define SIZEOF_GLOBAL_LOG (num_threads*MAX_ITERATIONS*sizeof(log_t))
 168 static log_t *global_log;
 169 static interval_t interval = 0;
 170
 171 static bool_t go = FALSE;
 172 static int threads_initialised1 = 0, max_key, log_max_key;
 173 static int threads_initialised2 = 0;
 174 static int threads_initialised3 = 0;
 175 int num_threads;
 176
 177 static unsigned long proportion;
 178
 179 static struct timeval start_time, done_time;
 180 static struct tms start_tms, done_tms;
 181
 182 static int successes[MAX_THREADS];
 183
 184 #ifdef SPARC
 185 static int processors[MAX_THREADS];
 186 #endif
 187
 188 /* All the variables accessed in the critical main loop. */
 189 static struct {
 190     CACHE_PAD(0);
 191     bool_t alarm_time;
 192     CACHE_PAD(1);
 193     set_t *set;
 194     CACHE_PAD(2);
 195 } shared;
 196
 197 #define nrand(_r) (((_r) = (_r) * 1103515245) + 12345)
 198
 199 static void alarm_handler( int arg)
 200 {
 201     shared.alarm_time = 1;
 202 }
 203
 204 /*int cntr[MAX_THREADS] = { 0 };*/
 205
 206 static void *thread_start(void *arg)
 207 {
 208     unsigned long k;
 209     int i;
 210     void *ov, *v;
 211     int id = (int)arg;
 212 #ifdef DO_WRITE_LOG
 213     log_t *log = global_log + id*MAX_ITERATIONS;
 214     interval_t my_int;
 215 #endif
 216     unsigned long r = ((unsigned long)arg)+3; /*RDTICK();*/
 217     unsigned int prop = proportion;
 218     unsigned int _max_key = max_key;
 219
 220 #ifdef SPARC
 221     i = processor_bind(P_LWPID, P_MYID, processors[id], NULL);
 222     if ( i != 0 )
 223     {
 224         printf("Failed to bind to processor %d! (%d)\n", processors[id], i);
 225         abort();
 226     }
 227 #endif
 228
 229     if ( id == 0 )
 230     {
 231         _init_ptst_subsystem();
 232         _init_gc_subsystem();
 233         _init_set_subsystem();
 234         shared.set = set_alloc();
 235     }
 236
 237     /* BARRIER FOR ALL THREADS */
 238     {
 239         int n_id, id = threads_initialised1;
 240         while ( (n_id = CASIO(&threads_initialised1, id, id+1)) != id )
 241             id = n_id;
 242     }
 243     while ( threads_initialised1 != num_threads ) MB();
 244
 245 #ifndef DO_WRITE_LOG
 246     /* Start search structure off with a well-distributed set of inital keys */
 247     for ( i = (_max_key / num_threads); i != 0; i >>= 1 )
 248     {
 249         for ( k = i >> 1; k < (_max_key / num_threads); k += i )
 250         {
 251             set_update(shared.set,
 252                        k + id * (_max_key / num_threads),
 253                        (void *)0xdeadbee0, 1);
 254         }
 255     }
 256 #endif
 257
 258     {
 259         int n_id, id = threads_initialised2;
 260         while ( (n_id = CASIO(&threads_initialised2, id, id+1)) != id )
 261             id = n_id;
 262     }
 263     while ( threads_initialised2 != num_threads ) MB();
 264
 265     if ( id == 0 )
 266     {
 267         (void)signal(SIGALRM, &alarm_handler);
 268         (void)alarm(MAX_WALL_TIME);
 269         WMB();
 270         gettimeofday(&start_time, NULL);
 271         times(&start_tms);
 272         go = TRUE;
 273         WMB();
 274     }
 275     else
 276     {
 277         while ( !go ) MB();
 278     }
 279
 280 #ifdef DO_WRITE_LOG
 281     get_interval(my_int);
 282 #endif
 283     for ( i = 0; (i < MAX_ITERATIONS) && !shared.alarm_time; i++ )
 284     {
 285         /* O-3: ignore ; 4-11: proportion ; 12: ins/del */
 286         k = (nrand(r) >> 4) & (_max_key - 1);
 287         nrand(r);
 288 #ifdef DO_WRITE_LOG
 289         log->start = my_int;
 290 #endif
 291         if ( ((r>>4)&255) < prop )
 292         {
 293             ov = v = set_lookup(shared.set, k);
 294         }
 295         else if ( ((r>>12)&1) )
 296         {
 297             v = (void *)((r&~7)|0x8);
 298             ov = set_update(shared.set, k, v, 1);
 299         }
 300         else
 301         {
 302             v = NULL;
 303             ov = set_remove(shared.set, k);
 304         }
 305
 306 #ifdef DO_WRITE_LOG
 307         get_interval(my_int);
 308         log->key = k;
 309         log->val = v;
 310         log->old_val = ov;
 311         log->end = my_int;
 312         log++;
 313 #endif
 314     }
 315
 316     /* BARRIER FOR ALL THREADS */
 317     {
 318         int n_id, id = threads_initialised3;
 319         while ( (n_id = CASIO(&threads_initialised3, id, id+1)) != id )
 320             id = n_id;
 321     }
 322     while ( threads_initialised3 != num_threads ) MB();
 323
 324 #if 0
 325     if ( id == 0 )
 326     {
 327         extern void check_tree(set_t *);
 328         check_tree(shared.set);
 329     }
 330 #endif
 331
 332     if ( id == num_threads - 1 )
 333     {
 334         gettimeofday(&done_time, NULL);
 335         times(&done_tms);
 336         WMB();
 337         _destroy_gc_subsystem();
 338     }
 339
 340     successes[id] = i;
 341
 342     return(NULL);
 343 }
 344
 345 #define THREAD_TEST thread_start
 346 #define THREAD_FLAGS THR_BOUND
 347
 348 #ifdef PPC
 349 static pthread_attr_t attr;
 350 #endif
 351
 352 static void test_multithreaded (void)
 353 {
 354     int                 i, fd;
 355     pthread_t            thrs[MAX_THREADS];
 356     int num_successes;
 357     int min_successes, max_successes;
 358     int ticksps = sysconf(_SC_CLK_TCK);
 359     float wall_time, user_time, sys_time;
 360
 361     if ( num_threads == 1 ) goto skip_thread_creation;
 362
 363 #ifdef PPC
 364     i = pthread_attr_init (&attr);
 365     if (i !=0) {
 366         fprintf (stderr, "URK!  pthread_attr_init rc=%d\n", i);
 367     }
 368     i = pthread_attr_setscope (&attr, PTHREAD_SCOPE_SYSTEM);
 369     if (i !=0) {
 370         fprintf (stderr, "URK!  pthread_attr_setscope rc=%d\n", i);
 371     }
 372 #endif
 373
 374 #ifdef MIPS
 375     pthread_setconcurrency(num_threads + 1);
 376 #else
 377     pthread_setconcurrency(num_threads);
 378 #endif
 379
 380     for (i = 0; i < num_threads; i ++)
 381     {
 382         MB();
 383 #ifdef PPC
 384         pthread_create (&thrs[i], &attr, THREAD_TEST, (void *)i);
 385 #else
 386         pthread_create (&thrs[i], NULL, THREAD_TEST, (void *)i);
 387 #endif
 388     }
 389
 390  skip_thread_creation:
 391     if ( num_threads == 1 )
 392     {
 393         thread_start(0);
 394     }
 395     else
 396     {
 397         for (i = 0; i < num_threads; i ++)
 398         {
 399             (void)pthread_join (thrs[i], NULL);
 400         }
 401     }
 402
 403     wall_time = (float)(TVAL(done_time) - TVAL(start_time))/ 1000000;
 404     user_time = ((float)(done_tms.tms_utime - start_tms.tms_utime))/ticksps;
 405     sys_time  = ((float)(done_tms.tms_stime - start_tms.tms_stime))/ticksps;
 406
 407     log_float ("wall_time_s", wall_time);
 408     log_float ("user_time_s", user_time);
 409     log_float ("system_time_s", sys_time);
 410
 411     num_successes = 0;
 412     min_successes = INT_MAX;
 413     max_successes = INT_MIN;
 414     for ( i = 0; i < num_threads; i++ )
 415     {
 416         num_successes += successes[i];
 417         if ( successes[i] < min_successes ) min_successes = successes[i];
 418         if ( successes[i] > max_successes ) max_successes = successes[i];
 419     }
 420
 421     log_int ("min_successes", min_successes);
 422     log_int ("max_successes", max_successes);
 423     log_int ("num_successes", num_successes);
 424
 425     log_float("us_per_success", (num_threads*wall_time*1000000.0)/num_successes);
 426
 427     log_int("log max key", log_max_key);
 428 }
 429
 430 #if defined(INTEL)
 431 static void tstp_handler(int sig, siginfo_t *info, ucontext_t *uc)
 432 {
 433     static unsigned int sem = 0;
 434     unsigned long *esp = (unsigned long *)(uc->uc_mcontext.gregs[7]);
 435     int pid = getpid();
 436
 437     while ( CASIO(&sem, 0, 1) != 0 ) sched_yield();
 438
 439     printf("Signal %d for pid %d\n", sig, pid);
 440     printf("%d: EIP=%08x  EAX=%08x  EBX=%08x  ECX=%08x  EDX=%08x\n", pid,
 441            uc->uc_mcontext.gregs[14], uc->uc_mcontext.gregs[11],
 442            uc->uc_mcontext.gregs[ 8], uc->uc_mcontext.gregs[10],
 443            uc->uc_mcontext.gregs[ 9]);
 444     printf("%d: ESP=%08x  EBP=%08x  ESI=%08x  EDI=%08x  EFL=%08x\n", pid,
 445            uc->uc_mcontext.gregs[ 7], uc->uc_mcontext.gregs[ 6],
 446            uc->uc_mcontext.gregs[ 5], uc->uc_mcontext.gregs[ 4],
 447            uc->uc_mcontext.gregs[16]);
 448     printf("\n");
 449
 450     sem = 0;
 451
 452     for ( ; ; ) sched_yield();
 453 }
 454 #endif
 455
 456 int main (int argc, char **argv)
 457 {
 458 #ifdef DO_WRITE_LOG
 459     int fd;
 460     unsigned long log_header[] = { 0, MAX_ITERATIONS, 0 };
 461
 462     if ( argc != 5 )
 463     {
 464         printf("%s <num_threads> <read_proportion> <key power> <log name>\n"
 465                "(0 <= read_proportion <= 256)\n", argv[0]);
 466         exit(1);
 467     }
 468 #else
 469     if ( argc != 4 )
 470     {
 471         printf("%s <num_threads> <read_proportion> <key power>\n"
 472                "(0 <= read_proportion <= 256)\n", argv[0]);
 473         exit(1);
 474     }
 475 #endif
 476
 477     memset(&shared, 0, sizeof(shared));
 478
 479     num_threads = atoi(argv[1]);
 480     log_int ("num_threads", num_threads);
 481
 482     proportion = atoi(argv[2]);
 483     log_float ("frac_reads", (float)proportion/256.0);
 484
 485     log_max_key = atoi(argv[3]);
 486     max_key = 1 << atoi(argv[3]);
 487     log_int("max_key", max_key);
 488
 489     log_int ("max_iterations", MAX_ITERATIONS);
 490
 491     log_int ("wall_time_limit_s", MAX_WALL_TIME);
 492
 493 #ifdef SPARC
 494     {
 495         int st, maxcpu = sysconf(_SC_CPUID_MAX), i, j=0;
 496
 497         /* Favour processors that don't handle I/O interrupts. */
 498         for ( i = 0; i <= maxcpu; i++ )
 499         {
 500             st = p_online(i, P_STATUS);
 501             if ( st == P_NOINTR )
 502             {
 503                 if ( j == num_threads ) break;
 504                 processors[j++] = i;
 505                 if ( j == num_threads ) break;
 506             }
 507         }
 508
 509         /* Fall back to the system quads if necessary. */
 510         for ( i = 0; i <= maxcpu; i++ )
 511         {
 512             st = p_online(i, P_STATUS);
 513             if ( st == P_ONLINE )
 514             {
 515                 if ( j == num_threads ) break;
 516                 processors[j++] = i;
 517                 if ( j == num_threads ) break;
 518             }
 519         }
 520
 521         if ( j != num_threads )
 522         {
 523             printf("Urk! Not enough CPUs for threads (%d < %d)\n",
 524                    j, num_threads);
 525             abort();
 526         }
 527     }
 528 #endif
 529
 530 #ifdef DO_WRITE_LOG
 531     log_header[0] = num_threads;
 532     log_header[2] = max_key;
 533     global_log = malloc(SIZEOF_GLOBAL_LOG);
 534 #endif
 535
 536 #if defined(INTEL)
 537     {
 538         struct sigaction act;
 539         memset(&act, 0, sizeof(act));
 540         act.sa_handler = (void *)tstp_handler;
 541         act.sa_flags = SA_SIGINFO;
 542         sigaction(SIGTSTP, &act, NULL);
 543         sigaction(SIGQUIT, &act, NULL);
 544         sigaction(SIGSEGV, &act, NULL);
 545     }
 546 #endif
 547
 548     test_multithreaded ();
 549
 550     dump_log ();
 551
 552 #ifdef DO_WRITE_LOG
 553     printf("Writing log...\n");
 554     /* Write logs to data file */
 555     fd = open(argv[4], O_WRONLY | O_CREAT | O_TRUNC, 0644);
 556     if ( fd == -1 )
 557     {
 558         fprintf(stderr, "Error writing log!\n");
 559         exit(-1);
 560     }
 561
 562     if ( (write(fd, log_header, sizeof(log_header)) != sizeof(log_header)) ||
 563          (write(fd, global_log, SIZEOF_GLOBAL_LOG) != SIZEOF_GLOBAL_LOG) )
 564     {
 565         fprintf(stderr, "Log write truncated or erroneous\n");
 566         close(fd);
 567         exit(-1);
 568     }
 569
 570     close(fd);
 571 #endif
 572
 573     exit(0);
 574 }