#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/shm.h>

/* simple version to demonstrate the problem with out of order execution */

volatile char	*sh_turn;	/* mutual exclusion flags - in shared memory */
volatile char	*sh_flag0;
volatile char	*sh_flag1;	/* make them all fit 1 word */

volatile int	*in_crit;	/* count nr of threads that made it into critical section */
volatile char	*s_m;		/* start of shared memory segment */

int	cnt;			/* counts nr of attempts to enter cs */
int	shared_id;		/* shared memory */
int	is_parent;		/* 0 in child, non-zero in parent */
int	who;			/* pid of parent process */

#ifdef MEMORY_BARRIER_USED

#if defined(__i386__)
	#define MB()	__asm__ __volatile__ ( "lock; addl $0,0(%%esp)" : : : "memory" )
#elif defined(__x86_64__)
	#define MB()	__asm__ __volatile__ ( "mfence" : : : "memory")
#elif defined(__powerpc__)
	#define MB()	__asm__ __volatile__ ("sync" : : : "memory")
#else
	#define MB()
	#warning "missing definition of a memory barrier function for this machine"
#endif

#endif

void
enter_critical(void)
{
	if (is_parent > 0)	/* cpu0 */
	{	*sh_flag0 = 1;
		*sh_turn  = 1;

		MB();
	      while (*sh_flag1 == 1 && *sh_turn == 1)
		{	MB();
		}
	} else			/* cpu1 */
	{	*sh_flag1 = 1;
		*sh_turn  = 0;
		MB();
	      while (*sh_flag0 == 1 && *sh_turn == 0)
		{	MB();
		}
	}
	*in_crit = *in_crit + 1;
}

void
leave_critical(void)
{
	*in_crit = *in_crit - 1;

	if (is_parent > 0)	/* cpu0 */
	{	*sh_flag0 = 0;
	} else			/* cpu1 */
	{	*sh_flag1 = 0;
	}
}

void
cleanup(void)
{
	if (shmdt((void *) s_m) != 0)				/* detach */
	{	perror("shmdt");
	}
	if (shmctl(shared_id, IPC_RMID, NULL) == -1)	/* remove */
	{	perror("shmctl");
	}
}

int
invariant(void)
{
	if (*in_crit != 1)
	{	char buf[64];

		printf("%d\terror in step %d (value %d)\n", is_parent, cnt, *in_crit);

		sprintf(buf, "kill -9 %d", is_parent>0?is_parent:who);
		system(buf);

		return 0;
	}
	return 1;
}

int
main(int argc, char *argv[])
{	volatile char	*x;
	key_t		key;

	if ((key = ftok("peterson.c", 123)) == -1)
	{	perror("ftok");
		exit(1);
	}
	if ((shared_id = shmget(key, 1024, 0600 | IPC_CREAT | IPC_EXCL)) == -1)	/* create */
	{	perror("shmget");
		exit(1);
	}

	s_m = x = (volatile char *) shmat(shared_id, (void *) 0, 0);		/* attach */
	if ((char *) x == (char *) -1)
	{	perror("shmat");
		exit(1);
	}

	memset((char *) x, 0, 1024);	/* make sure all values are initially zero */

	sh_turn   = (volatile char *) x;  x += sizeof(char);
	sh_flag0  = (volatile char *) x;  x += sizeof(char);
	sh_flag1  = (volatile char *) x;  x += sizeof(char);

	if (((long)x)&(sizeof(void *)-1))	/* align with next word boundary */
	{	x += sizeof(void *)-(((long)x)&(sizeof(void *)-1));
	}

	in_crit   = (volatile int *) x;  x += sizeof(int);

	who = getpid();

	if ((is_parent = fork()) == -1)
	{	perror("fork failed");
		exit(1);
	}

	srand(argc);
	for (cnt = 0; cnt < 1000000; cnt++)
	{	enter_critical();
		if (!invariant())
		{	break;
		}
		if ((rand()%100) == 0) sleep(1);
		leave_critical();
	}
	cleanup();

	return 0;
}
#if 0
	Sample output on a 64-bit linux machine:
	$ gcc -o p peterson.c
	$ ./p
	26938   error in step 124687 (value 0)
	$ ./p
	27237   error in step 104429 (value 2)
#endif