#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/wait.h>
#include <errno.h>

union semun {
	long val;
	struct semid_ds *buf;
	ushort *array;
};

/* Handle for dealing with semaphore */
static int sem_id = -1;

/* Create n semaphores */
void semaphore_open(int n)
{
	sem_id = semget( IPC_PRIVATE, n, IPC_CREAT | IPC_EXCL | 0600);
	if (sem_id < 0) {
		perror("semget");
		exit(1);
	}
}

/* Set semaphore n to value v, no exclusion */
void semaphore_set(int n, int v)
{
	union semun  se;

	se.val = v;
	if (semctl(sem_id, n, SETVAL, se)==-1) {
		perror("semaphore_set");
		exit(1);
	}
}

/* return value of semaphore n, no exclusion */
int semaphore_get(int n)
{
	union semun se;
	int v;

	if ((v=semctl(sem_id, n, GETVAL, se))==-1) {
		perror("semaphore_set");
		exit(1);
	}
	return(v);
}

/* Enter critical section, or block (sleep) until you can */
/* Works by trying to reduce semaphore n from 1 to 0 */
void semaphore_lock(int n)
{
	struct sembuf op;

	op.sem_num = n;
	op.sem_op = -1;
	op.sem_flg = SEM_UNDO;

	while (semop(sem_id, &op, 1) < 0) {
		/* if we got woken up by an interupt/signal keep trying */
		if (errno != EINTR) {
			/* something bad happened */
			perror("semaphore_lock");
			exit(-1);
		}
	}
}

/* Leave critical section, doesn't need to block */
/* Works by adding 1 to semaphore n */
void semaphore_unlock(int n)
{
	struct sembuf op;

	op.sem_num = n;
	op.sem_op = 1;
	op.sem_flg = SEM_UNDO;

	while (semop(sem_id, &op, 1) < 0) {
		/* if we got woken up by an interupt/signal keep trying */
		if (errno != EINTR) {
			/* something bad happened */
			perror("semaphore_lock");
			exit(-1);
		}
	}
}

/* Delay for a random ( < max) uS */
void small_delay( int max )
{
	int n;

	n = ( int )((( double )max)*rand()/(RAND_MAX+1.0));
	usleep(n);
}

#define CHILDREN 10

/***  This code tries to illustrate two different uses of semaphores:
 ***  one as a means for sharing a variable (int) amongst several process,
 ***  second as a Mutual Exclusion mechanism.
 ***
 ***  The usefulness of a MutEx mechanism is illustrated by having each
 ***  of 10 children simultaneously trying to add values to a shared number.
 ***  The version that does not use mutex ends with the wrong value because
 ***  in between it reading, adding 1, and writing back the value, another
 ***  process may happen to get in there and also perform the same task.
 ***  The first process then destroys the second's work when it finishes
 ***  writing back the value.
 ***/
int main(int argc, char **argv)
{
	int pid[CHILDREN], i;

	/* Create 3 semaphores 
	 * 0  running count
	 * 1  running count with mutex (mutual exclusion) 
	 * 2  mutex
	 */	
	semaphore_open(3);

	/* initialise counts to zero and mutex to 1 */
	semaphore_set(0, 0);
	semaphore_set(1, 0);
	semaphore_set(2, 1);

	printf("PARENT: Starting %d children...\n", CHILDREN);

	/* create 10 children */
	for (i=0; i<CHILDREN; i++) {
		if ((pid[i] = fork()) == 0) {
			/* I am a child */
			printf("CHILD: I am a child. pid=%d\n", getpid());
			/* as I'm the child, stop trying to fork, that's the parent's job */
			break;
		}
		/* Only the parent task gets to this line */
		printf("PARENT: Child pid=%d started.\n", pid[i]);
	}

	if (i>=CHILDREN) {
		/* I completed the fork loop, I must therefore be the parent */
		/* Parent code */
		int z;

		printf("PARENT: sleeping to wait for children.\n");
		while (1) {
			int ppid, j, c;

			/* wait for the next child to die */
			ppid = wait(NULL);
			if (ppid==-1) {
				perror("wait");
				sleep(1);
				continue;
			}

			/* find the child */
			j=0;
			while (j<CHILDREN && pid[j]!=ppid) j++;
			if (j>=CHILDREN) {
				printf("PARENT: Strange, pid %d died, but it wasn't one of my children.\n", ppid);
			} else	/* mark it dead */
				pid[j]=0;

			/* count how many remain */
			c=0;
			for (j=0;j<CHILDREN;j++) 
				if (pid[j] > 0) c++;

			if (c==0) /* none left */
				break;

		}
		/* Run out of children now */
		z = semaphore_get(0);
		printf("PARENT: First Value  : %d\n", z);
		z = semaphore_get(1);
		printf("PARENT: Second Value : %d (with mutex)\n", z);
		exit(0);

	} else {
		/* Child code */
		int j, k, p;

		/* Which child am I? */
		p = getpid();

		/* make the random times more random */
		srand(p);

		/* wait a little before starting */
		small_delay(10000);
		printf("CHILD: pid %d starting my run.\n", p);


		/* Our job: to add 1 to the counters 100 times */
		for (j=0; j< 100; j++) {
			/* reduce the chance that two will happen at
			   the same time by waiting a little */
			small_delay(100);

			/* first read, add 1, write the unprotected var */
			k = semaphore_get(0);
			k++;
			/* this delay is what causes the problem as another
			   process might slip in the gap */
			small_delay(2);
			semaphore_set(0, k);

			/* Next lock, read, add, write, unlock  var2 */
			/* This is the same as above, only using exclusion */
			semaphore_lock(2); /* semaphore 2 is our mutex */			
			k = semaphore_get(1);
			k++;
			small_delay(2);
			semaphore_set(1, k);
			semaphore_unlock(2);

		}
		printf("CHILD pid %d finished.\n", p);
		exit(0);
	}
}