Simulation of Cleopatra:

Generating an equivalent C program

Abstract

This project aims to make a preprocessor of the programming language Cleopatra, created by Professor Azer Bestavros. The preprocessor parses Cleopatra specifications and generates an equivalent simulator written in C, which is then compiled and run on UNIX operating system. Various UNIX system calls are used in the C simulator. Pipe() and fork(), among others, are mainly used in simulating the parallelism of Cleopatra.

Table of Contents

1. Simulation
• Input Channel Duplication
• Variations of Duplication
• Output Channel Protection
• Time Constraint
• Channel Mapping In TET Level
2. Parsing Cleopatra Specification
3. Problems and Restrictions
4. Components of Preprocessor
5. Installation
6. Sample Program

TRA-class main()
{

internal:
   -> x(), y(), z()

include:
   world    y() -> x(), z();
   control  x() -> y();

act:
   x() -> y():
   y() -> z():
}

world   (alias_y1, x, z);
control (alias_x1, y);

TET1    (alias_x2, y);
TET2    (alias_y2, z);

while (1) {
   read(x, buffer);
   write(alias_x1, buffer);
   write(alias_x2, buffer);
}

• Signature and Included Class are fixed entities, so direction of the signature is strictly observed when Signature is mapped to Included Class.
• Output Internal Channel can be mapped to input Signature of Included Class or TET.
• Output signature can be mapped to input channel of a TET.
• If no input channel is given to a TET, then its trigger is considered to be the entire set of Signature.

TRA-class user
   -> x()               /* output signature */
{

act:
   init(), x() -> x():

}

TET(x)
{
  while (1) {
    read(alias_x);       /* initially don't block */

    (commit section)

    write(x);            /* to outside */
    write(alias_x);      /* to itself  */
  }

}

If the channel x were an Internal Channel, then the TET could fire once to the channel x only, because the destination channel is known so that an agent process can be spawned as before.

• Input multiplexing using select or poll function to sense the channel, rather than actually reading it.
• Create another agent process, which explicitly trigger TET.

while (1) {

  (commit section)

  P(sem_x);             /* for mutual exclusion */
  write(x, buffer);
  V(sem_x);

}

while (1) {               /* process that triggers channel x */

  read(x, x_buffer);
  P(sem_write);           /* to protect triggering value */
  write(data, x_buffer);
  write(info, infobuffer);
  V(sem_write);

}

while (1) {               /* process that triggers channel y */

  read(y, y_buffer);
  P(sem_write);
  write(data, y_buffer);
  write(info, infobuffer);
  V(sem_write);

}

while (1) {               /* firing process */

  read(info, infobuffer);
  if (x triggered)
    read(data, x_buffer);
  else if (y triggered)
    read(data, y_buffer);

  (commit section)

}

1. Declaration: type and declarator
   Type and declarator are parsed partially. Composite type, for example, can be used but its members are not parsed and left unknown. Structure and array can be used, but pointer should not be used in that State Space (variable) resides in shared memory area.
2. Expression / assignment statement
   These are not parsed and copied verbatim to the target file.

1. State variable (in which incoming value is saved) in triggering channel of TET
   It is treated as a text, and is not checked whether it is valid or not. Text inside a triggering channel is copied verbatim to the target file. It is because composite type or variable is not completely parsed.
2. Expression that is specified in firing channel of TET
3. Actual parameter in Included Class
4. Condition and time constraint in TET
5. Init section and commit section in TET

1. Error checking:
   Preprocessing a Cleopatra specification and compiling the generated C program are independent, thus tracing an error might be difficult.
2. Partial syntax specification:
   Source program is not completely parsed. Programmer is responsible for such unparsed parts mentioned before.
3. Resource cleanup upon termination:
   Semaphores and shared memories should be removed when program terminates. In this preprocessor, program runs for a specified time (in seconds). If, however, program terminates abnormally (i.e. by pressing control-C or a system call failure) then these resources could remain in the system and user might have to remove them manually.
4. Time constraint:
   Granularity of time is second, in that the only available UNIX function for timestamping is time(), which returns current time in seconds.
5. Init: section and commit section:
   They are copied as a string of characters. Moreover, it is returned by lex as a single token. Thus it could be a problem even for a moderately large commit section. It is also true for #include or #define section.
6. Static variable:
   TET consists of heavyweight processes, so variable to be shared by multiple processes reside in shared memory area. If TETs were implemented as threads (i.e. they share an address space) then array or pointer could be feasible and used more efficiently.
7. Syntax specification:
   I tried to conform to the original Cleopatra syntax, but there are some restrictions. For example, State variables must be initialized in Init: section, not in State: section, which only accepts declaration. More details are in cleo.y file.

factorial.cleo

TRA-class main
   ->
{
   internal:
   -> in(int), out(int)

   included:
   fact in() -> out();
   start     -> in();
	
}

TRA-class fact
   request(int) -> result(int)
{
   state:
   int x, f;

   init:
   x = -1; f = 0;

   act:
   request(x) -> :
      commit { f = 1; }

   -> :
      unless (x < 1)
      commit {f = f * x; x--; }

   -> result(f) :
      unless (x > 0)
      commit {printf("result is: %d\n", f);}
}

TRA-class start
   -> send(int)
{
   act:
   init() -> send(6):
   ;
}

ccleo factorial.cleo -3

output C file is factorial.c

#include <stdio.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/time.h>
#include <unistd.h>
#include <sys/sem.h>
#include <sys/stat.h>
#include <signal.h>
#include <setjmp.h>
#include <errno.h>

#define  SHM_MODE (SHM_R | SHM_W)
#define  PERMS    (S_IRUSR | S_IWUSR)
#define  CHAR     "c"
#define  ERR_MSG(x) perror("x error")

#define  lock(x)  \
while (((retval = semop(x, P, 1)) == -1) &&  \
(errno == EINTR)) ;                          \
if (retval == -1) ERR_MSG(sem P);

#define  unlock(x)  \
while (((retval = semop(x, V, 1)) == -1) &&  \
(errno == EINTR)) ;                          \
if (retval == -1) ERR_MSG(sem V);

typedef void Sigfunc(int);
Sigfunc  *signal(int, Sigfunc *);
int       pid, bufsize, sz, retval;
jmp_buf   env_alrm;
struct {
   int       pd;
   time_t    time;
}         buf;
struct sembuf P[1];
struct sembuf V[1];
union semun {
   int       val;
   struct semid_ds *buf;
   ushort   *array;
}         sem_init_arg;
void      sigfunc(int signo);
void      sig_alrm(int signo);
int
main()
{
   int       in[2];
   int       inbuf;
   int       sem_in;
   int       alias00[2];
   int       out[2];
   int       outbuf;
   int       sem_out;
   signal(SIGUSR1, SIG_DFL);
   signal(SIGALRM, SIG_IGN);
   sz = sizeof(buf);
   P[0].sem_num = 0;
   P[0].sem_op = -1;
   P[0].sem_flg = 0;
   V[0].sem_num = 0;
   V[0].sem_op = 1;
   V[0].sem_flg = 0;
   sem_init_arg.val = 1;
   if (pipe(in) == -1)
      ERR_MSG(pipe);
   if (pipe(alias00) == -1)
      ERR_MSG(pipe);
   if (pipe(out) == -1)
      ERR_MSG(pipe);
   if ((sem_in = semget(IPC_PRIVATE, 1, PERMS)) == -1)
      ERR_MSG(sem get);
   if (semctl(sem_in, 0, SETVAL, sem_init_arg) != 0)
      ERR_MSG(sem initialize);
   if ((sem_out = semget(IPC_PRIVATE, 1, PERMS)) == -1)
      ERR_MSG(sem get);
   if (semctl(sem_out, 0, SETVAL, sem_init_arg) != 0)
      ERR_MSG(sem initialize);
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      bufsize = sizeof(int);
      while (1) {
	 if (read(in[0], &inbuf, bufsize) != bufsize)
	    ERR_MSG(read);
	 if (write(alias00[1], &inbuf, bufsize) != bufsize)
	    ERR_MSG(write);
      }
      exit(0);
   }
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      bufsize = sizeof(int);
      while (1) {
	 if (read(out[0], &outbuf, bufsize) != bufsize)
	    ERR_MSG(read);
      }
      exit(0);
   }
   fact(alias00, out, sem_out);
   start(in, sem_in);
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      signal(SIGUSR1, sigfunc);
      pause();
      if (semctl(sem_in, 0, IPC_RMID, 0) == -1)
	 ERR_MSG(sem remove);
      if (semctl(sem_out, 0, IPC_RMID, 0) == -1)
	 ERR_MSG(sem remove);
      exit(0);
   } sleep(3);
   kill(0, SIGUSR1);
   return 0;
}
int
fact(int request[], int result[], int sem_result)
{
   int       requestbuf;
   int       alias00[2];
   int       resultbuf;
   int       trigger[2];
   char      triggerbuf;
   int       alias01[2];
   int       alias02[2];
   int       x;
   int      *shm_x;
   int       xid;
   int       f;
   int      *shm_f;
   int       fid;
   int       sem_var;
   if (pipe(alias00) == -1)
      ERR_MSG(pipe);
   if (pipe(trigger) == -1)
      ERR_MSG(pipe);
   if (pipe(alias01) == -1)
      ERR_MSG(pipe);
   if (pipe(alias02) == -1)
      ERR_MSG(pipe);
   if ((xid = shmget(IPC_PRIVATE, sizeof(int), SHM_MODE)) == -1)
      ERR_MSG(shm get);
   if ((shm_x = (int *) shmat(xid, 0, 0)) == (int *) -1)
      ERR_MSG(shm attach);
   if ((fid = shmget(IPC_PRIVATE, sizeof(int), SHM_MODE)) == -1)
      ERR_MSG(shm get);
   if ((shm_f = (int *) shmat(fid, 0, 0)) == (int *) -1)
      ERR_MSG(shm attach);
   if ((sem_var = semget(IPC_PRIVATE, 1, PERMS)) == -1)
      ERR_MSG(sem get);
   if (semctl(sem_var, 0, SETVAL, sem_init_arg) != 0)
      ERR_MSG(sem initialize);

   x = -1;
   f = 0;


   *shm_x = x;
   *shm_f = f;
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      bufsize = sizeof(int);
      while (1) {
	 if (read(request[0], &requestbuf, bufsize) != bufsize)
	    ERR_MSG(read);
	 if (write(alias00[1], &requestbuf, bufsize) != bufsize)
	    ERR_MSG(write);
	 if (write(trigger[1], CHAR, 1) != 1)
	    ERR_MSG(write);
      }
      exit(0);
   }
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      while (1) {
	 if (read(trigger[0], &triggerbuf, 1) != 1)
	    ERR_MSG(read);
	 if (write(alias01[1], CHAR, 1) != 1)
	    ERR_MSG(write);
	 if (write(alias02[1], CHAR, 1) != 1)
	    ERR_MSG(write);
      }
      exit(0);
   }
   facttet00(sem_var, shm_x, shm_f, alias00, trigger);
   facttet01(sem_var, shm_x, shm_f, alias01, trigger);
   facttet02(sem_var, shm_x, shm_f, alias02, result, sem_result);
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      signal(SIGUSR1, sigfunc);
      pause();
      if (shmctl(xid, IPC_RMID, NULL) == -1)
	 ERR_MSG(shm remove);
      if (shmctl(fid, IPC_RMID, NULL) == -1)
	 ERR_MSG(shm remove);
      if (semctl(sem_var, 0, IPC_RMID, 0) == -1)
	 ERR_MSG(sem remove);
      exit(0);
   } return 0;
}
int
facttet00(int sem_var, int *shm_x, int *shm_f, int request[], int fire[])
{
   int       info[2], data[2];
   int       requestbuf;
   char      firebuf;
   int       x;
   int       f;
   pipe(info);
   pipe(data);
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      bufsize = sizeof(int);
      while (1) {
	 if (read(request[0], &requestbuf, bufsize) != bufsize)
	    ERR_MSG(read);
	 if (write(data[1], &requestbuf, bufsize) != bufsize)
	    ERR_MSG(write);
	 if (write(info[1], &buf, sz) != sz)
	    ERR_MSG(write);
      }
      exit(0);
   }
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      while (1) {
	 if (read(info[0], &buf, sz) != sz)
	    ERR_MSG(read);
	 if (read(data[0], &requestbuf, sizeof(int)) != sizeof(int))
	    ERR_MSG(read);
	 lock(sem_var);
	 x = *(shm_x);
	 f = *(shm_f);
	 x = requestbuf;
	 unlock(sem_var);
	 f = 1;
	 lock(sem_var);
	 *(shm_x) = x;
	 *(shm_f) = f;
	 unlock(sem_var);
	 if (write(fire[1], CHAR, 1) != 1)
	    ERR_MSG(write);
      }
      exit(0);
   }
   return 0;
}
int
facttet01(int sem_var, int *shm_x, int *shm_f, int trigger[], int fire[])
{
   int       info[2], data[2];
   char      triggerbuf;
   char      firebuf;
   int       x;
   int       f;
   pipe(info);
   pipe(data);
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      bufsize = sizeof(char);
      while (1) {
	 if (read(trigger[0], &triggerbuf, bufsize) != bufsize)
	    ERR_MSG(read);
	 if (write(data[1], &triggerbuf, bufsize) != bufsize)
	    ERR_MSG(write);
	 if (write(info[1], &buf, sz) != sz)
	    ERR_MSG(write);
      }
      exit(0);
   }
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      while (1) {
	 if (read(info[0], &buf, sz) != sz)
	    ERR_MSG(read);
	 if (read(data[0], &triggerbuf, sizeof(char)) != sizeof(char))
	    ERR_MSG(read);
	 lock(sem_var);
	 x = *(shm_x);
	 f = *(shm_f);
	 if (x < 0) {
	    unlock(sem_var);
	    continue;
	 }
	 f = f * x;
	 x--;
	 if (x < 0) {
	    unlock(sem_var);
	    continue;
	 }
	 *(shm_x) = x;
	 *(shm_f) = f;
	 unlock(sem_var);
	 if (write(fire[1], CHAR, 1) != 1)
	    ERR_MSG(write);
      }
      exit(0);
   }
   return 0;
}
int
facttet02(int sem_var, int *shm_x, int *shm_f, int trigger[], int result[], int sem_result)
{
   int       info[2], data[2];
   char      triggerbuf;
   int       resultbuf;
   int       x;
   int       f;
   pipe(info);
   pipe(data);
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      bufsize = sizeof(char);
      while (1) {
	 if (read(trigger[0], &triggerbuf, bufsize) != bufsize)
	    ERR_MSG(read);
	 if (write(data[1], &triggerbuf, bufsize) != bufsize)
	    ERR_MSG(write);
	 if (write(info[1], &buf, sz) != sz)
	    ERR_MSG(write);
      }
      exit(0);
   }
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      while (1) {
	 if (read(info[0], &buf, sz) != sz)
	    ERR_MSG(read);
	 if (read(data[0], &triggerbuf, sizeof(char)) != sizeof(char))
	    ERR_MSG(read);
	 lock(sem_var);
	 x = *(shm_x);
	 f = *(shm_f);
	 if (x > 0) {
	    unlock(sem_var);
	    continue;
	 }
	 printf("result is: %d\n", f);
	 if (x > 0) {
	    unlock(sem_var);
	    continue;
	 }
	 *(shm_x) = x;
	 *(shm_f) = f;
	 unlock(sem_var);
	 lock(sem_result);
	 resultbuf = f;
	 if (write(result[1], &resultbuf, sizeof(int)) != sizeof(int))
	    ERR_MSG(write);
	 unlock(sem_result);
      }
      exit(0);
   }
   return 0;
}
int
start(int send[], int sem_send)
{
   int       sendbuf;
   starttet00(send, sem_send);
   return 0;
}
int
starttet00(int send[], int sem_send)
{
   int       sendbuf;
   if ((pid = fork()) < 0)
      ERR_MSG(fork);
   else if (pid == 0) {
      lock(sem_send);
      sendbuf = 6;
      if (write(send[1], &sendbuf, sizeof(int)) != sizeof(int))
	 ERR_MSG(write);
      unlock(sem_send);
      exit(0);
   }
   return 0;
}
void
sigfunc(int signo)
{
   return;
}
void
sig_alrm(int signo)
{
   longjmp(env_alrm, 1);
}