#include #include #include #include #include #include #include #include #include #include #include #define SHARED_FILE "/u/scott/work/lock/shared_file" #define MAX_PROCS 8 #define FREE MAX_PROCS+1 #define BYTES_PER_CACHE_LINE 64 #define SUX /* #define BACKOFF */ /* #define COUNT_BUS_OPS */ /* #define MEASURE_CONTENTION */ #define DEFAULT_PROCS 7 #ifdef MEASURE_CONTENTION #define DEFAULT_ITERATIONS 10 #else #define DEFAULT_ITERATIONS 100000 #endif #ifdef BACKOFF #define DEFAULT_DELAY 400 #else #define DEFAULT_DELAY 600 #endif #define DEFAULT_CRITICAL_SECTION 0 #define DEFAULT_NON_CRITICAL_SECTION 0 #define BACKOFF_BASE 0x1ff #define BACKOFF_CAP 0x3ffff /* must both be 2^n-1 */ /* these constants are tuned for minimum time with -O3 */ #define BACKOFF_BITS 2 #define BACKOFF_ADDEND 3 /* backoff_addend must be all ones -- backoff_bits of 'em */ #define BACK_OFF(x) (x <<= BACKOFF_BITS, x += BACKOFF_ADDEND, x &= BACKOFF_CAP) int pid; int procs = DEFAULT_PROCS; /* how many processes to run, including master */ int iterations = DEFAULT_ITERATIONS; /* number of times around loop IN EACH PROCESSOR */ int delay = DEFAULT_DELAY; /* how long to wait when resolving colisions */ int crit_section = DEFAULT_CRITICAL_SECTION; /* how long to wait inside critical section */ int non_crit_section = DEFAULT_NON_CRITICAL_SECTION; /* how long to wait outside critical section */ int fd; /* file descriptor of shred (mmap-ed) region */ char arena_name[64]; /* for creating native sgi lock */ usptr_t *arena_handle; ulock_t sgi_lock; int bus_ops; /* local (cacheable) counter */ int losers1, losers2, losers3; /* how many times did we fail in each possible way? */ struct { char pad1[NBPP]; int X; /* designed to be made uncacheable */ char pad2[NBPP]; } in_mem_var; #ifdef MEASURE_CONTENTION #define ARRAY_SIZE (128 * NBPP) char pad3[NBPP]; double A[ARRAY_SIZE], B[ARRAY_SIZE]; char pad4[NBPP]; #endif typedef union { struct { volatile unsigned short y; volatile unsigned short f; /* boolean */ } apart; volatile unsigned long together; } pair; typedef union { volatile int data; char padding[BYTES_PER_CACHE_LINE]; } cache_line_int; struct shared_mem { volatile pair yf; volatile unsigned short x; volatile unsigned short y; volatile unsigned short f; volatile int b[MAX_PROCS]; volatile int shared_counter; /* supposed to be protected by lock */ volatile int proc_counters[MAX_PROCS]; char padding[NBPP]; /* force rest of struct onto another (cacheable) page */ cache_line_int sense[MAX_PROCS]; /* for barrier */ cache_line_int toggle; /* for barrier */ } *smp; void map_sm () { if ((smp = (struct shared_mem*) mmap (0, sizeof (struct shared_mem), PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0)) == (struct shared_mem*) -1) { perror ("cannot mmap file"); exit (1); } } #define INITIAL_SENSE 0 static int local_sense = INITIAL_SENSE; /* this barrier is designed to release waiting processes as nearly in unison as possible. I'm not sure the SGI arena barriers do that, so I do it myself just in case. */ void my_barrier () { int i; local_sense = 1-local_sense; if (pid == 0) /* master */ { for (i=1; isense[i].data != local_sense); } smp->toggle.data = local_sense; /* let children go */ } else { smp->sense[pid].data = local_sense; /* inform master of arrival */ while (smp->toggle.data != local_sense); /* spin until released */ } } void at_acquire () /* Alur and Taubenfeld's lock */ { int i; int backoff; at_start: #ifdef COUNT_BUS_OPS bus_ops += 2; #endif smp->x = pid; if (smp->y != FREE) { #ifdef COUNT_BUS_OPS losers1 += 1; #endif at_backoff: #ifdef BACKOFF backoff = BACKOFF_BASE; #endif do { #ifdef BACKOFF for (i = 0; i < backoff; i++); BACK_OFF (backoff); #endif #ifdef COUNT_BUS_OPS bus_ops ++; #endif } while (smp->y != FREE); goto at_start; } #ifdef COUNT_BUS_OPS bus_ops += 2; #endif smp->y = pid; if (smp->x != pid) { /* conflict */ for (i = 0; i < delay; i++); #ifdef COUNT_BUS_OPS bus_ops += 1; #endif if (smp->y != pid) { #ifdef COUNT_BUS_OPS losers2 += 1; #endif goto at_backoff; } if (smp->f) { #ifdef COUNT_BUS_OPS losers3 += 1; #endif #ifdef BACKOFF backoff = BACKOFF_BASE; #endif do { #ifdef BACKOFF for (i = 0; i < backoff; i++); BACK_OFF (backoff); #ifdef COUNT_BUS_OPS bus_ops ++; #endif #endif } while (smp->f); } losers1++; } else { #ifdef COUNT_BUS_OPS bus_ops += 1; #endif smp->f = 1; } } void at_release () { #ifdef COUNT_BUS_OPS bus_ops += 2; #endif smp->f = 0; if (smp->y == pid) { #ifdef COUNT_BUS_OPS bus_ops ++; #endif smp->y = FREE; } } pair test_val, free_val; /* constants */ void new_acquire () { pair t2; int i; int backoff; new_start: #ifdef COUNT_BUS_OPS bus_ops += 2; #endif smp->x = pid; if (smp->yf.apart.y != FREE) { #ifdef COUNT_BUS_OPS losers1 += 1; #endif new_backoff: #ifdef BACKOFF backoff = BACKOFF_BASE; #endif do { #ifdef BACKOFF for (i = 0; i < backoff; i++); BACK_OFF (backoff); #endif #ifdef COUNT_BUS_OPS bus_ops ++; #endif } while (smp->yf.apart.y != FREE); goto new_start; } #ifdef COUNT_BUS_OPS bus_ops += 2; #endif smp->yf.apart.y = pid; if (smp->x != pid) { /* conflict */ for (i = 0; i < delay; i++); #ifdef COUNT_BUS_OPS bus_ops += 1; #endif if (smp->yf.together != test_val.together) { #ifdef COUNT_BUS_OPS losers2 += 1; #endif goto new_backoff; } losers1++; } #ifdef COUNT_BUS_OPS bus_ops += 1; #endif smp->yf.apart.f = 1; } void new_release () { #ifdef COUNT_BUS_OPS bus_ops += 1; #endif smp->yf.together = free_val.together; } void empty_acquire () {} void empty_release () {} void lamport_acquire () { int i, j; int backoff; lamport_start: #ifdef COUNT_BUS_OPS bus_ops += 3; #endif smp->b[pid] = 1; smp->x = pid; if (smp->y != FREE) { #ifdef COUNT_BUS_OPS bus_ops += 1; /* set of b */ losers1 += 1; #endif smp->b[pid] = 0; lamport_backoff: #ifdef BACKOFF backoff = BACKOFF_BASE; #endif do { #ifdef BACKOFF for (j = 0; j < backoff; j++); BACK_OFF (backoff); #endif #ifdef COUNT_BUS_OPS bus_ops ++; #endif } while (smp->y != FREE); goto lamport_start; } #ifdef COUNT_BUS_OPS bus_ops += 2; /* set of y and test of x */ #endif smp->y = pid; if (smp->x != pid) { #ifdef COUNT_BUS_OPS bus_ops += 1; /* set of b[pid] */ #endif smp->b[pid] = 0; for (i = 0; i < procs; i++) { #ifdef BACKOFF backoff = BACKOFF_BASE; #endif #ifdef COUNT_BUS_OPS bus_ops += 1; #endif while (smp->b[i]) { #ifdef BACKOFF for (j = 0; j < backoff; j++); BACK_OFF (backoff); #endif #ifdef COUNT_BUS_OPS losers2 += 1; bus_ops += 1; #endif } } if (smp->y != pid) { #ifdef COUNT_BUS_OPS losers3 += 1; #endif goto lamport_backoff; } } } void lamport_release () { #ifdef COUNT_BUS_OPS bus_ops += 2; #endif smp->y = FREE; smp->b[pid] = 0; } void sgi_acquire () { ussetlock (sgi_lock); } void sgi_release () { usunsetlock (sgi_lock); } typedef void (*fn) (); void time_test (fn acq_fn, fn rel_fn, char *test_name) { struct tms time_val; clock_t t1, t2; int i, j; int local_counter; int dummy; int no_lock = !strcmp (test_name, "no locking"); int new_lock = !strcmp (test_name, "new lock"); int *crit_delays = malloc (iterations * sizeof(int)); int *non_crit_delays = malloc (iterations * sizeof(int)); srandom (pid*pid); for (i = 0; i < iterations; i++) { crit_delays[i] = crit_section ? random() % (2*crit_section+1) : 0; non_crit_delays[i] = non_crit_section ? random() % (2*non_crit_section+1) : 0; } my_barrier (); bus_ops = 0; losers1 = losers2 = losers3 = 0; if (pid == 0) /* master */ { smp->shared_counter = 0; suxify (); t1 = times (&time_val); } my_barrier (); #ifdef MEASURE_CONTENTION if (pid == 0) { int k; for (j = 0; j < iterations; j++) { for (k = 0; k < ARRAY_SIZE; k++) { B[k] = A[k]; } } smp->shared_counter = procs*iterations; /* tell peers to stop */ } else { while (!smp->shared_counter) { acq_fn (); for (i = 0; i < crit_section; i++) { /* waste some time, but generate bus accesses */ dummy = smp->shared_counter; } rel_fn (); for (i = 0; i < non_crit_section; i++) { /* waste some time, but generate bus accesses */ dummy = in_mem_var.X; } } } #else for (j = 0; j < iterations; j++) { acq_fn (); local_counter = smp->shared_counter; for (i = 0; i < crit_delays[j]; i++) { /* waste some time, but generate bus accesses */ dummy = smp->shared_counter; } smp->shared_counter = local_counter + 1; rel_fn (); for (i = 0; i < non_crit_delays[j]; i++) { /* waste some time, but generate bus accesses */ dummy = in_mem_var.X; } } #endif my_barrier (); if (pid == 0) /* master */ { t2 = times (&time_val); unsuxify (); printf ("%s: %lf seconds\n", test_name, (t2-t1)/(double)HZ); fflush (stdout); /* #ifdef COUNT_BUS_OPS */ } my_barrier (); smp->proc_counters[pid] = bus_ops; my_barrier (); if (pid == 0) { local_counter = 0; for (i = 0; i < procs; i++) { local_counter += smp->proc_counters[i]; } printf ("bus ops: %d\n", local_counter); } my_barrier (); smp->proc_counters[pid] = losers1; my_barrier (); if (pid == 0) { local_counter = 0; for (i = 0; i < procs; i++) { local_counter += smp->proc_counters[i]; } printf ("losers1: %d\n", local_counter); } my_barrier (); smp->proc_counters[pid] = losers2; my_barrier (); if (pid == 0) { local_counter = 0; for (i = 0; i < procs; i++) { local_counter += smp->proc_counters[i]; } printf ("losers2: %d\n", local_counter); } my_barrier (); smp->proc_counters[pid] = losers3; my_barrier (); if (pid == 0) { local_counter = 0; for (i = 0; i < procs; i++) { local_counter += smp->proc_counters[i]; } printf ("losers3: %d\n", local_counter); fflush (stdout); /* #endif */ { int broken = (!no_lock && (smp->shared_counter != procs*iterations)); if (broken) printf ("*** MUTEX BROKEN ***\n"); if (broken || no_lock) { printf ("Expected sum = %d;", procs*iterations); printf (" Shared counter = %d\n", smp->shared_counter); fflush (stdout); } } } } void The_Task() /* the main loop, executed by each processor */ { int i; pair y_s_f; void *addr; #ifdef SUX if (sysmp (MP_MUSTRUN, pid+1) == -1) { perror ("Could not MUSTRUN"); } #endif addr = (void *)((unsigned long)smp & PG_ADDR); if (cachectl (addr, NBPP, UNCACHEABLE)) { perror ("unable to make shared page uncacheable"); } addr = (void *)((unsigned long)&in_mem_var.X & PG_ADDR); if (cachectl (addr, NBPP, UNCACHEABLE)) { perror ("unable to make private page uncacheable"); } #ifdef MEASURE_CONTENTION addr = (void *)((unsigned long)&A[0] & PG_ADDR); if (cachectl (addr, ARRAY_SIZE*sizeof(double), UNCACHEABLE)) { perror ("unable to make A uncacheable"); } addr = (void *)((unsigned long)&B[0] & PG_ADDR); if (cachectl (addr, ARRAY_SIZE*sizeof(double), UNCACHEABLE)) { perror ("unable to make B uncacheable"); } #endif if (pid == 0) { printf ("%d processes, %d iterations/proc, %d CS, %d NCS, %d delay", procs, iterations, crit_section, non_crit_section, delay); #ifdef BACKOFF printf (" B\n"); #else printf (" NB\n"); #endif fflush (stdout); } test_val.apart.y = pid; test_val.apart.f = 0; free_val.apart.y = FREE; free_val.apart.f = 0; time_test (empty_acquire, empty_release, "no locking"); time_test (new_acquire, new_release, "new lock"); time_test (at_acquire, at_release, "at lock"); time_test (lamport_acquire, lamport_release, "lamport lock"); time_test (sgi_acquire, sgi_release, "native lock"); } void suxify () { #ifdef SUX int i; for (i=1; i < procs+1; i++) { if (sysmp (MP_ISOLATE, i) == -1) { perror ("Could not isolate processor"); } if (sysmp (MP_RESTRICT, i) == -1) { perror ("Could not restrict processor"); } if (sysmp (MP_NONPREEMPTIVE, i) == -1) { perror ("Could not turn off preemption"); } } #endif } void unsuxify () { #ifdef SUX int i; for (i=1; i < procs+1; i++) { if (sysmp (MP_PREEMPTIVE, i) == -1) { perror ("Could not turn on preemption"); } if (sysmp (MP_UNISOLATE, i) == -1) { perror ("Could not unisolate processor"); } if (sysmp (MP_EMPOWER, i) == -1) { perror ("Could not empower processor"); } } #endif } main (int argc, char **argv) { int i; if ((fd = open (SHARED_FILE, O_RDWR)) == EOF) { perror ("can't open shared file"); exit (1); } parse_args(argc, argv); /* set up shared memory */ map_sm (); smp->yf.apart.y = FREE; smp->yf.apart.f = 0; /* no one is in critical section */ /* smp->x doesn't matter */ smp->y = FREE; smp->f = 0; for (i=0; ib[i] = 0; smp->sense[i].data = INITIAL_SENSE; } smp->toggle.data = INITIAL_SENSE; /* set up arena for native sgi lock */ tmpnam (arena_name); arena_handle = usinit (arena_name); sgi_lock = usnewlock (arena_handle); for (pid=1; pid