/* file: philos.c

   dining philosphers program
   --------------------------
   with various synchronization mechanism options
   to be used for illustration of these mechanisms in use

Define a subset of the following symbols to compile a specific
version of this program:

 USE_POSIX_SEMAPHORES
 USE_MMAP
 USE_ORDERED_LOCKING
 USE_UNNAMED_SEMAPHORES

USE_MMAP will enable memory mapping and allow the detection of
failed mutual exclusion.   USE_ORDERED_LOCKING will prevent
deadlock, USE_POSIX_SEMAPHORES will enforce mutual exclusion,
and USE_UNNAMED_SEMAPHORES will used unnamed semaphores.

USE_ORDERED_LOCKING requires USE_POSIX_SEMAPHORES.
USE_UNNAMED_SEMAPHORES requires USE_POSIX_SEMAPHORES and USE_MMAP.

 */

#ifdef USE_ORDERED_LOCKING
#ifndef USE_POSIX_SEMAPHORS
#define USE_POSIX_SEMAPHORES
#endif
#endif

#ifdef USE_UNNAMED_SEMAPHORES
#ifndef USE_MMAP
#define USE_MMAP
#endif
#ifndef USE_POSIX_SEMAPHORS
#define USE_POSIX_SEMAPHORES
#endif
#endif

#define _XOPEN_SOURCE 500
#define _POSIX_C_SOURCE 199506L
#define __EXTENSIONS__
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <signal.h>
#include <fcntl.h>
#include <time.h>

#define CHECK(CALL)\
  if (((int)(CALL)) == -1) {\
    perror (#CALL);\
    kill (-mainpid, SIGKILL);\
    exit (-1);\
 }

#define ERR_QUIT(MSG) {\
 perror (MSG);\
 cleanup();\
 kill (-mainpid, SIGKILL);\
 exit (-1);\
 }

#define QUIT(MSG) {\
 fprintf (stderr, "fatal error: %s\n", MSG);\
 cleanup();\
 kill (-mainpid, SIGKILL);\
 exit (-1);\
 }

#define NPHILOS 5
#define NSEMS (NPHILOS + 1)
/* the extra (last) semaphore is used for output synchronization,
   in function xprintf */

pid_t mainpid, philo[NPHILOS];

#ifdef USE_POSIX_SEMAPHORES
#include <semaphore.h>
sem_t *S[NSEMS];
char  S_name[NSEMS][10] =
 {"/my_sem_0",
  "/my_sem_1",
  "/my_sem_2",
  "/my_sem_3",
  "/my_sem_4",
  "/my_sem_5"};
/* consider using getpid to create per-process unique names... */
int sem_isopen[NSEMS];
char sem_kind[] = "POSIX semaphores";
#else
char sem_kind[] = "no mutual exclusion";
#endif  

#ifdef USE_MMAP
const char sharefilename[] = "/tmp/my_share";
int sharefd;       /* to be memory-mapped */
int share_isopen = 0;
void * sharedmem;  /* points to shared memory */
int share_ismapped = 0;
char mm_kind[] = "memory mapping";
typedef struct {
  int   holder[NPHILOS];
#ifdef USE_UNNAMED_SEMAPHORES
  sem_t S_Object[NSEMS];
#endif
} sharedregion_t;
sharedregion_t *shared;  /* points to shared memory region */
#else
char mm_kind[] = "no memory mapping";
#endif

void cleanup(){
/* remove semaphores and shared memory files
   so that they don't cause trouble later */
#ifdef USE_POSIX_SEMAPHORES
   int i;
   for (i = 0; i < NSEMS; i++) {
      if (sem_isopen[i]) {
#ifdef USE_UNNAMED_SEMAPHORES
         CHECK(sem_destroy(S[i]));
#else
         CHECK(sem_close(S[i]));
         CHECK(sem_unlink(S_name[i]));
#endif
         sem_isopen[i] = 0;
      }
   }
#endif
#ifdef USE_MMAP
   if (share_ismapped) {
      CHECK(munmap(sharedmem, sizeof(sharedregion_t)));
   }
   if (share_isopen) {
      CHECK(close (sharefd));
      CHECK(unlink (sharefilename));
   }
#endif
}

int xprintf (FILE *stream, const char * format, ...) {
/* behaves like fprintf except that the output is
   atomic with respect to other calls to xprintf */
   va_list arg;
   int done;
   va_start(arg, format);
#ifdef USE_POSIX_SEMAPHORES
   CHECK(sem_wait(S[NSEMS-1]));
#endif
   done = vfprintf(stream, format, arg);
#ifdef USE_POSIX_SEMAPHORES
   CHECK(sem_post(S[NSEMS-1]));
#endif
   va_end(arg);
   return done;
}

void ransleep(int scale){
/* sleep for a random number of microseconds */
  usleep (random() % scale);
}

void pick_up_chopsticks(int self){
#ifdef USE_POSIX_SEMAPHORES
#ifdef USE_ORDERED_LOCKING
  if (self + 1 == NPHILOS) {
     CHECK (sem_wait(S[0]));
     CHECK (sem_wait(S[self]));
  } else {
     CHECK (sem_wait(S[self]));
     CHECK (sem_wait(S[self + 1]));
  }
#else
  CHECK (sem_wait(S[self]));
  CHECK (sem_wait(S[(self + 1) % NPHILOS]));
#endif
#endif  
#ifdef USE_MMAP
  /* check that no one else is holding the chopsticks */
  if (shared->holder[self] != 0) {
     QUIT ("mutual exclusion failed (1)");
  }
  if (shared->holder[(self+1) % NPHILOS] != 0) {
     QUIT ("mutual exclusion failed (1)");
  }
  shared->holder[self] = self;
  shared->holder[(self+1) % NPHILOS] = self;
#endif
}

void put_down_chopsticks(int self){
#ifdef USE_MMAP
  /* check that we are still holding both chopsticks */
  if (shared->holder[self] != self) {
     QUIT ("mutual exclusion failed (2)");
  }
  if (shared->holder[(self+1) % NPHILOS] != self) {
     QUIT ("mutual exclusion failed (2)");
  }
  shared->holder[self] = 0;
  shared->holder[(self+1) % NPHILOS] = 0;
#endif
#ifdef USE_POSIX_SEMAPHORES
  CHECK (sem_post(S[self]));
  CHECK (sem_post(S[(self + 1) % NPHILOS]));
#endif
}

void philosopher(int self) {
   sleep(1);
   for (;;) {
      pick_up_chopsticks(self);
      ransleep(10000);
      put_down_chopsticks(self);
   }
}

int main() {

   int i, status;
   pid_t child;

#ifdef USE_MMAP
{  int result;
   sharedregion_t init;
   for (i = 0; i < NPHILOS; i++) init.holder[i] = 0;
   unlink(sharefilename);
   CHECK(sharefd = open (sharefilename, O_CREAT | O_RDWR,
     S_IRUSR | S_IWUSR));

   result = write(sharefd, &init, sizeof(init));
   if (result != sizeof(init)) ERR_QUIT ("write");

   share_isopen = 1;
   sharedmem = mmap(0,    /* suggested address */
     sizeof (sharedregion_t),   /* size of region to be mapped */
     PROT_READ | PROT_WRITE,    /* allow read and write access */
     MAP_SHARED,                /* share changes */
     sharefd,                   /* file descriptor */
     0                          /* offset in file */);
   if ((sharedmem == MAP_FAILED)) {
      ERR_QUIT ("mmmap");
   }
   share_ismapped = 1;
   shared = (sharedregion_t *) sharedmem;

}
#endif

#ifdef USE_POSIX_SEMAPHORES
   for (i = 0; i <= NPHILOS; i++) {
#ifdef USE_UNNAMED_SEMAPHORES
      S[i] = &(shared->S_Object[i]);
      CHECK (sem_init(S[i], 1, 1));
#else
      CHECK (S[i] = sem_open(S_name[i], O_CREAT, S_IRWXU, 1));
#endif
      sem_isopen[i] = 1;
   }
#endif  

   xprintf (stdout, "running %d philosphers using %s and %s....\n",
     NPHILOS, sem_kind, mm_kind);

   /* set random seed */
   srandom((int) time(NULL));

   mainpid = getpid();

   for (i = 0; i < NPHILOS; i++) {
      philo[i] = 0;
   }
   for (i = 0; i < NPHILOS; i++) {
      CHECK (child = fork());
      if (child == 0) { /* child */
         philosopher (i);
         /* the call above should never return */
         cleanup();
         exit (i);
      }
      philo[i] = child;
   }

   sleep (5);

   for (i = 0; i < NPHILOS; i++) {
      CHECK(kill(philo[i], SIGKILL));
   }

   for (i = 0; i < NPHILOS; i++) {
      while ((child = waitpid (philo[i], &status, 0)) == -1) {
         if (errno != EINTR) {
            ERR_QUIT ("bad waitpid");
         } else {
            xprintf (stderr, "interrupted while waiting for child\n");
         }
         if (WIFEXITED(status)) {
         } else if (WIFSIGNALED(status)) {
            xprintf (stderr, "child %d killed by signal %d\n",
               i, WTERMSIG(status));
         } else if (WIFSTOPPED(status)) {
            QUIT("stopped status value");
         } else QUIT("bad status value");
      }
      if (child != philo[i]) {
         ERR_QUIT ("bad child id from waitpid");
      }
   }

   xprintf(stderr, "exited normally.\n");
   cleanup();

   return 0;
}