/* 
 * psum.c - A simple parallel sum program
 */
/* $begin psum */
#include "csapp.h"
#include "realtimer.h"
#include <getopt.h>

#include "locks.h"

#define MAXTHREADS 32    
#define MAXSPACING 16

/* Underlying data type */
typedef unsigned long data_t;
/* Thread type */
typedef void * (*thread_fun_t)(void *);

/* Thread routines */
void *sum_race(void *vargp);
void *sum_spin(void *vargp);
void *sum_fetch_add(void *vargp);
void *sum_mutex(void *vargp);
void *sum_cas(void *vargp);
void *sum_ticket(void *vargp);

/* Number of times each thread should increment */
data_t nelems_per_thread = 100000;

/* Single accumulator */
volatile data_t global_sum = 0;

/* Mutexes for global sum */
pthread_spinlock_t smutex;
pthread_mutex_t mutex;
cas_lock_t cmutex;
ticket_lock_t tmutex;

/* Interface declaration */
#define NMODE 6
/* Different summation modes */
typedef enum { SUM_RACE, SUM_FETCH_ADD, SUM_SPIN, SUM_MUTEX, SUM_CAS, SUM_TICKET } sum_mode_t;
/* String mode selectors */
char *mode_string[NMODE] = {"race", "fetch+add", "spin", "mutex", "cas-lock", "ticket" };
/* Thread functions */
thread_fun_t mode_fun[NMODE] = { sum_race, sum_fetch_add, sum_spin, sum_mutex, sum_cas, sum_ticket };

void run(size_t npt, int nthreads, thread_fun_t fun) {
    int i;
    pthread_t tid[MAXTHREADS];
    data_t expected = npt * nthreads;
    nelems_per_thread = npt;

    /* Set global values */
    global_sum = 0;
    pthread_spin_init(&smutex, PTHREAD_PROCESS_PRIVATE);
    pthread_mutex_init(&mutex, NULL);
    cas_lock_init(&cmutex);
    ticket_lock_init(&tmutex);

    start_timer();

    /* Create peer threads and wait for them to finish */
    for (i = 0; i < nthreads; i++) {
	Pthread_create(&tid[i], NULL, fun, NULL);
    }                                                
    for (i = 0; i < nthreads; i++)                   
	Pthread_join(tid[i], NULL);                  
    
    double time = elapsed_time();

    /* Check final answer */
    if (global_sum != expected)
        printf("Error: result=%lu.  Should be %lu\n", global_sum, expected);

    double npi = time * 1e9 / expected;

    printf("%d threads, %.2f seconds, %.2f ns per increment\n", nthreads, time, npi);
}

/* Thread routines */

/* No synchronization */
void *sum_race(void *vargp) 
{
    int i;
    for (i = 0; i < nelems_per_thread; i++) {
	global_sum ++;
    }	                           
    return NULL;
}

/* Use spin lock */
void *sum_spin(void *vargp) 
{
    int i;
    for (i = 0; i < nelems_per_thread; i++) {
        pthread_spin_lock(&smutex);
	global_sum ++;
	pthread_spin_unlock(&smutex);
    }	                           
    return NULL;
}

/* Use mutex */
void *sum_mutex(void *vargp) 
{
    int i;
    for (i = 0; i < nelems_per_thread; i++) {
        pthread_mutex_lock(&mutex);
	global_sum ++;
	pthread_mutex_unlock(&mutex);
    }	                           
    return NULL;
}

/* Use fetch and add */
void *sum_fetch_add(void *vargp) 
{
    int i;
    for (i = 0; i < nelems_per_thread; i++) {
	__sync_fetch_and_add(&global_sum, 1);
    }	                           
    return NULL;
}

/* Use cas lock */
void *sum_cas(void *vargp) 
{
    int i;
    for (i = 0; i < nelems_per_thread; i++) {
        cas_lock_lock(&cmutex);
	global_sum ++;
	cas_lock_unlock(&cmutex);
    }	                           
    return NULL;
}

/* Use ticket lock */
void *sum_ticket(void *vargp) 
{
    int i;
    for (i = 0; i < nelems_per_thread; i++) {
        ticket_lock_lock(&tmutex);
	global_sum ++;
	ticket_lock_unlock(&tmutex);
    }	                           
    return NULL;
}




void usage(char *cmd) {
  printf("Usage: %s [-h] [-t minthreads] [-x maxthreads] [-l logelems] [-m (r|s|m|f)]\n", cmd);
  printf("\t-h Print this message\n");
  printf("\t-t minthreads\tMinimum thread count\n");
  printf("\t-x maxthreads\tMaximum thread count\n");
  printf("\t-l logelems\tLog_2 of number of elements per thread\n");
  printf("\t-m Select summation mode\n");
  printf("\t\tr\tAccumulate globally with race\n");
  printf("\t\ts\tAccumulate globally with semaphore\n");
  printf("\t\tm\tAccumulate globally with mutex\n");
  printf("\t\tf\tAccumulate globally with fetch-and-add\n");
  exit(0);
}

int main(int argc, char *argv[]) {
    int minthreads = 1;
    int maxthreads = 8;
    int log_nelems = 25;
    data_t npt = 0;
    int mode = 0;

  int c;
  while ((c = getopt(argc, argv, "ht:x:l:m:")) != -1) {
    switch(c) {
    case 'h':
      usage(argv[0]);
      break;
    case 't':
      minthreads = maxthreads = atoi(optarg);
      break;
    case 'x':
      maxthreads = atoi(optarg);
      break;
    case 'l':
      log_nelems = atoi(optarg);
      break;
    case 'm':
      for (mode = 0; mode < NMODE; mode++)
	if (optarg[0] == mode_string[mode][0]) {
	  break;
	}
      if (mode >= NMODE) {
	printf("Unrecognized mode '%s'\n", optarg);
	usage(argv[0]);
      }
      break;
    default:
      printf("Unrecognized option '%c'\n", c);
      usage(argv[0]);
      break;
    }
  }
  npt = 1ULL << log_nelems;
  int i;
  printf("%lu nelems/thread\n", npt);
  printf("Mode %s\n", mode_string[mode]);
  printf("Threads\tSeconds\n");
  for (i = minthreads; i <= maxthreads; i++)
    run(npt, i, mode_fun[mode]);
  return 0;
}