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[41];
 120         memset(padding, ' ', sizeof(padding) - 1);
 121         padding[40] = '\0';
 122         if (30-strlen(log_records[i].name) >= 0){
 123             padding[30-strlen(log_records[i].name)] = '\0';
 124         }
 125         fprintf (stdout, "%s%s = ", padding, log_records[i].name);
 126         {
 127             int kind = log_records [i].kind;
 128             if (kind == LOG_KIND_INT) {
 129                 fprintf (stdout, "%d\n", log_records[i].val_int);
 130             } else if (kind == LOG_KIND_STRING) {
 131                 fprintf (stdout, "%s\n", log_records[i].val_string);
 132             } else if (kind == LOG_KIND_FLOAT) {
 133                 fprintf (stdout, "%.3f\n", log_records[i].val_float);
 134             }
 135         }
 136     }
 137     fprintf (stdout, "-------------------------------------------"
 138              "---------------------------\n");
 139
 140     for (i = 0; i < num_log_records; i ++)
 141     {
 142         int kind = log_records [i].kind;
 143         if (i != 0) { fprintf (stderr, " "); }
 144         if (kind == LOG_KIND_INT) {
 145             fprintf (stderr, "%d", log_records[i].val_int);
 146         } else if (kind == LOG_KIND_STRING) {
 147             fprintf (stderr, "%s", log_records[i].val_string);
 148         } else if (kind == LOG_KIND_FLOAT) {
 149             fprintf (stderr, "%.3f", log_records[i].val_float);
 150         }
 151     }
 152     fprintf (stderr, " LOG\n");
 153 }
 154
 155 /*
 156  * ************** END OF LOGGING
 157  */
 158
 159 #define TVAL(x) ((x.tv_sec * 1000000) + x.tv_usec)
 160
 161 /* Log tables. Written out at end-of-day. */
 162 typedef struct log_st
 163 {
 164     interval_t    start, end;
 165     unsigned int  key;
 166     void         *val, *old_val; /* @old_val used by update() and remove() */
 167 } log_t;
 168 #define SIZEOF_GLOBAL_LOG (num_threads*MAX_ITERATIONS*sizeof(log_t))
 169 static log_t *global_log;
 170 static interval_t interval = 0;
 171
 172 static bool_t go = FALSE;
 173 static int threads_initialised1 = 0, max_key, log_max_key;
 174 static int threads_initialised2 = 0;
 175 static int threads_initialised3 = 0;
 176 int num_threads;
 177
 178 static unsigned long proportion;
 179
 180 static struct timeval start_time, done_time;
 181 static struct tms start_tms, done_tms;
 182
 183 static int successes[MAX_THREADS];
 184
 185 #ifdef SPARC
 186 static int processors[MAX_THREADS];
 187 #endif
 188
 189 /* All the variables accessed in the critical main loop. */
 190 static struct {
 191     CACHE_PAD(0);
 192     bool_t alarm_time;
 193     CACHE_PAD(1);
 194     set_t *set;
 195     CACHE_PAD(2);
 196 } shared;
 197
 198 #define nrand(_r) (((_r) = (_r) * 1103515245) + 12345)
 199
 200 static void alarm_handler( int arg)
 201 {
 202     shared.alarm_time = 1;
 203 }
 204
 205 /*int cntr[MAX_THREADS] = { 0 };*/
 206
 207 static void *thread_start(void *arg)
 208 {
 209     unsigned long k;
 210     int i;
 211     void *ov, *v;
 212     int id = (int)arg;
 213 #ifdef DO_WRITE_LOG
 214     log_t *log = global_log + id*MAX_ITERATIONS;
 215     interval_t my_int;
 216 #endif
 217     unsigned long r = ((unsigned long)arg)+3; /*RDTICK();*/
 218     unsigned int prop = proportion;
 219     unsigned int _max_key = max_key;
 220
 221 #ifdef SPARC
 222     i = processor_bind(P_LWPID, P_MYID, processors[id], NULL);
 223     if ( i != 0 )
 224     {
 225         printf("Failed to bind to processor %d! (%d)\n", processors[id], i);
 226         abort();
 227     }
 228 #endif
 229
 230     if ( id == 0 )
 231     {
 232         _init_ptst_subsystem();
 233         _init_gc_subsystem();
 234         _init_set_subsystem();
 235         shared.set = set_alloc();
 236     }
 237
 238     /* BARRIER FOR ALL THREADS */
 239     {
 240         int n_id, id = threads_initialised1;
 241         while ( (n_id = CASIO(&threads_initialised1, id, id+1)) != id )
 242             id = n_id;
 243     }
 244     while ( threads_initialised1 != num_threads ) MB();
 245
 246 #ifndef DO_WRITE_LOG
 247     /* Start search structure off with a well-distributed set of inital keys */
 248     for ( i = (_max_key / num_threads); i != 0; i >>= 1 )
 249     {
 250         for ( k = i >> 1; k < (_max_key / num_threads); k += i )
 251         {
 252             set_update(shared.set,
 253                        k + id * (_max_key / num_threads),
 254                        (void *)0xdeadbee0, 1);
 255         }
 256     }
 257 #endif
 258
 259     {
 260         int n_id, id = threads_initialised2;
 261         while ( (n_id = CASIO(&threads_initialised2, id, id+1)) != id )
 262             id = n_id;
 263     }
 264     while ( threads_initialised2 != num_threads ) MB();
 265
 266     if ( id == 0 )
 267     {
 268         (void)signal(SIGALRM, &alarm_handler);
 269         (void)alarm(MAX_WALL_TIME);
 270         WMB();
 271         gettimeofday(&start_time, NULL);
 272         times(&start_tms);
 273         go = TRUE;
 274         WMB();
 275     }
 276     else
 277     {
 278         while ( !go ) MB();
 279     }
 280
 281 #ifdef DO_WRITE_LOG
 282     get_interval(my_int);
 283 #endif
 284     for ( i = 0; (i < MAX_ITERATIONS) && !shared.alarm_time; i++ )
 285     {
 286         /* O-3: ignore ; 4-11: proportion ; 12: ins/del */
 287         k = (nrand(r) >> 4) & (_max_key - 1);
 288         nrand(r);
 289 #ifdef DO_WRITE_LOG
 290         log->start = my_int;
 291 #endif
 292         if ( ((r>>4)&255) < prop )
 293         {
 294             ov = v = set_lookup(shared.set, k);
 295         }
 296         else if ( ((r>>12)&1) )
 297         {
 298             v = (void *)((r&~7)|0x8);
 299             ov = set_update(shared.set, k, v, 1);
 300         }
 301         else
 302         {
 303             v = NULL;
 304             ov = set_remove(shared.set, k);
 305         }
 306
 307 #ifdef DO_WRITE_LOG
 308         get_interval(my_int);
 309         log->key = k;
 310         log->val = v;
 311         log->old_val = ov;
 312         log->end = my_int;
 313         log++;
 314 #endif
 315     }
 316
 317     /* BARRIER FOR ALL THREADS */
 318     {
 319         int n_id, id = threads_initialised3;
 320         while ( (n_id = CASIO(&threads_initialised3, id, id+1)) != id )
 321             id = n_id;
 322     }
 323     while ( threads_initialised3 != num_threads ) MB();
 324
 325 #if 0
 326     if ( id == 0 )
 327     {
 328         extern void check_tree(set_t *);
 329         check_tree(shared.set);
 330     }
 331 #endif
 332
 333     if ( id == num_threads - 1 )
 334     {
 335         gettimeofday(&done_time, NULL);
 336         times(&done_tms);
 337         WMB();
 338         _destroy_gc_subsystem();
 339     }
 340
 341     successes[id] = i;
 342
 343     return(NULL);
 344 }
 345
 346 #define THREAD_TEST thread_start
 347 #define THREAD_FLAGS THR_BOUND
 348
 349 #ifdef PPC
 350 static pthread_attr_t attr;
 351 #endif
 352
 353 static void test_multithreaded (void)
 354 {
 355     int                 i, fd;
 356     pthread_t            thrs[MAX_THREADS];
 357     int num_successes;
 358     int min_successes, max_successes;
 359     int ticksps = sysconf(_SC_CLK_TCK);
 360     float wall_time, user_time, sys_time;
 361
 362     if ( num_threads == 1 ) goto skip_thread_creation;
 363
 364 #ifdef PPC
 365     i = pthread_attr_init (&attr);
 366     if (i !=0) {
 367         fprintf (stderr, "URK!  pthread_attr_init rc=%d\n", i);
 368     }
 369     i = pthread_attr_setscope (&attr, PTHREAD_SCOPE_SYSTEM);
 370     if (i !=0) {
 371         fprintf (stderr, "URK!  pthread_attr_setscope rc=%d\n", i);
 372     }
 373 #endif
 374
 375 #ifdef MIPS
 376     pthread_setconcurrency(num_threads + 1);
 377 #else
 378     pthread_setconcurrency(num_threads);
 379 #endif
 380
 381     for (i = 0; i < num_threads; i ++)
 382     {
 383         MB();
 384 #ifdef PPC
 385         pthread_create (&thrs[i], &attr, THREAD_TEST, (void *)i);
 386 #else
 387         pthread_create (&thrs[i], NULL, THREAD_TEST, (void *)i);
 388 #endif
 389     }
 390
 391  skip_thread_creation:
 392     if ( num_threads == 1 )
 393     {
 394         thread_start(0);
 395     }
 396     else
 397     {
 398         for (i = 0; i < num_threads; i ++)
 399         {
 400             (void)pthread_join (thrs[i], NULL);
 401         }
 402     }
 403
 404     wall_time = (float)(TVAL(done_time) - TVAL(start_time))/ 1000000;
 405     user_time = ((float)(done_tms.tms_utime - start_tms.tms_utime))/ticksps;
 406     sys_time  = ((float)(done_tms.tms_stime - start_tms.tms_stime))/ticksps;
 407
 408     log_float ("wall_time_s", wall_time);
 409     log_float ("user_time_s", user_time);
 410     log_float ("system_time_s", sys_time);
 411
 412     num_successes = 0;
 413     min_successes = INT_MAX;
 414     max_successes = INT_MIN;
 415     for ( i = 0; i < num_threads; i++ )
 416     {
 417         num_successes += successes[i];
 418         if ( successes[i] < min_successes ) min_successes = successes[i];
 419         if ( successes[i] > max_successes ) max_successes = successes[i];
 420     }
 421
 422     log_int ("min_successes", min_successes);
 423     log_int ("max_successes", max_successes);
 424     log_int ("num_successes", num_successes);
 425
 426     log_float("us_per_success", (num_threads*wall_time*1000000.0)/num_successes);
 427
 428     log_int("log max key", log_max_key);
 429 }
 430
 431 #if defined(INTEL)
 432 static void tstp_handler(int sig, siginfo_t *info, ucontext_t *uc)
 433 {
 434     static unsigned int sem = 0;
 435     unsigned long *esp = (unsigned long *)(uc->uc_mcontext.gregs[7]);
 436     int pid = getpid();
 437
 438     while ( CASIO(&sem, 0, 1) != 0 ) sched_yield();
 439
 440     printf("Signal %d for pid %d\n", sig, pid);
 441     printf("%d: EIP=%08x  EAX=%08x  EBX=%08x  ECX=%08x  EDX=%08x\n", pid,
 442            uc->uc_mcontext.gregs[14], uc->uc_mcontext.gregs[11],
 443            uc->uc_mcontext.gregs[ 8], uc->uc_mcontext.gregs[10],
 444            uc->uc_mcontext.gregs[ 9]);
 445     printf("%d: ESP=%08x  EBP=%08x  ESI=%08x  EDI=%08x  EFL=%08x\n", pid,
 446            uc->uc_mcontext.gregs[ 7], uc->uc_mcontext.gregs[ 6],
 447            uc->uc_mcontext.gregs[ 5], uc->uc_mcontext.gregs[ 4],
 448            uc->uc_mcontext.gregs[16]);
 449     printf("\n");
 450
 451     sem = 0;
 452
 453     for ( ; ; ) sched_yield();
 454 }
 455 #endif
 456
 457 int main (int argc, char **argv)
 458 {
 459 #ifdef DO_WRITE_LOG
 460     int fd;
 461     unsigned long log_header[] = { 0, MAX_ITERATIONS, 0 };
 462
 463     if ( argc != 5 )
 464     {
 465         printf("%s <num_threads> <read_proportion> <key power> <log name>\n"
 466                "(0 <= read_proportion <= 256)\n", argv[0]);
 467         exit(1);
 468     }
 469 #else
 470     if ( argc != 4 )
 471     {
 472         printf("%s <num_threads> <read_proportion> <key power>\n"
 473                "(0 <= read_proportion <= 256)\n", argv[0]);
 474         exit(1);
 475     }
 476 #endif
 477
 478     memset(&shared, 0, sizeof(shared));
 479
 480     num_threads = atoi(argv[1]);
 481     log_int ("num_threads", num_threads);
 482
 483     proportion = atoi(argv[2]);
 484     log_float ("frac_reads", (float)proportion/256.0);
 485
 486     log_max_key = atoi(argv[3]);
 487     max_key = 1 << atoi(argv[3]);
 488     log_int("max_key", max_key);
 489
 490     log_int ("max_iterations", MAX_ITERATIONS);
 491
 492     log_int ("wall_time_limit_s", MAX_WALL_TIME);
 493
 494 #ifdef SPARC
 495     {
 496         int st, maxcpu = sysconf(_SC_CPUID_MAX), i, j=0;
 497
 498         /* Favour processors that don't handle I/O interrupts. */
 499         for ( i = 0; i <= maxcpu; i++ )
 500         {
 501             st = p_online(i, P_STATUS);
 502             if ( st == P_NOINTR )
 503             {
 504                 if ( j == num_threads ) break;
 505                 processors[j++] = i;
 506                 if ( j == num_threads ) break;
 507             }
 508         }
 509
 510         /* Fall back to the system quads if necessary. */
 511         for ( i = 0; i <= maxcpu; i++ )
 512         {
 513             st = p_online(i, P_STATUS);
 514             if ( st == P_ONLINE )
 515             {
 516                 if ( j == num_threads ) break;
 517                 processors[j++] = i;
 518                 if ( j == num_threads ) break;
 519             }
 520         }
 521
 522         if ( j != num_threads )
 523         {
 524             printf("Urk! Not enough CPUs for threads (%d < %d)\n",
 525                    j, num_threads);
 526             abort();
 527         }
 528     }
 529 #endif
 530
 531 #ifdef DO_WRITE_LOG
 532     log_header[0] = num_threads;
 533     log_header[2] = max_key;
 534     global_log = malloc(SIZEOF_GLOBAL_LOG);
 535 #endif
 536
 537 #if defined(INTEL)
 538     {
 539         struct sigaction act;
 540         memset(&act, 0, sizeof(act));
 541         act.sa_handler = (void *)tstp_handler;
 542         act.sa_flags = SA_SIGINFO;
 543         sigaction(SIGTSTP, &act, NULL);
 544         sigaction(SIGQUIT, &act, NULL);
 545         sigaction(SIGSEGV, &act, NULL);
 546     }
 547 #endif
 548
 549     test_multithreaded ();
 550
 551     dump_log ();
 552
 553 #ifdef DO_WRITE_LOG
 554     printf("Writing log...\n");
 555     /* Write logs to data file */
 556     fd = open(argv[4], O_WRONLY | O_CREAT | O_TRUNC, 0644);
 557     if ( fd == -1 )
 558     {
 559         fprintf(stderr, "Error writing log!\n");
 560         exit(-1);
 561     }
 562
 563     if ( (write(fd, log_header, sizeof(log_header)) != sizeof(log_header)) ||
 564          (write(fd, global_log, SIZEOF_GLOBAL_LOG) != SIZEOF_GLOBAL_LOG) )
 565     {
 566         fprintf(stderr, "Log write truncated or erroneous\n");
 567         close(fd);
 568         exit(-1);
 569     }
 570
 571     close(fd);
 572 #endif
 573
 574     exit(0);
 575 }