3cd5d40d9fbce06010da457498a29d3e5dc735da
[openafs.git] / 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 }