simulator.c

计算机网络中的几个简单协议的仿真代码

/* Simulator for datalink protocols. 
 *    Written by Andrew S. Tanenbaum.
 *    Revised by Shivakant Mishra.
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <unistd.h>
#include <stdio.h>
#include "simulator.h"

#define NR_TIMERS 8             /* number of timers; this should be greater
                                   than half the number of sequence numbers. */
#define MAX_QUEUE 100000        /* max number of buffered frames */
#define NO_EVENT -1             /* no event possible */
#define FRAME_SIZE (sizeof(frame))
#define BYTE 0377               /* byte mask */
#define UINT_MAX  0xFFFFFFFF    /* maximum value of an unsigned 32-bit int */
#define INTERVAL 100000         /* interval for periodic printing */
#define AUX 2                   /* aux timeout is main timeout/AUX */

/* DEBUG MASKS */
#define SENDS        0x0001     /* frames sent */
#define RECEIVES     0x0002     /* frames received */
#define TIMEOUTS     0x0004     /* timeouts */
#define PERIODIC     0x0008     /* periodic printout for use with long runs */

#define DEADLOCK (3 * timeout_interval)	/* defines what a deadlock is */
#define MANY 256		/* big enough to clear pipe at the end */

/* Status variables used by the workers, M0 and M1. */
bigint ack_timer[NR_TIMERS];    /* ack timers */
unsigned int seqs[NR_TIMERS];   /* last sequence number sent per timer */
bigint lowest_timer;            /* lowest of the timers */
bigint aux_timer;               /* value of the auxiliary timer */
int network_layer_status;       /* 0 is disabled, 1 is enabled */
unsigned int next_net_pkt;      /* seq of next network packet to fetch */
unsigned int last_pkt_given= 0xFFFFFFFF;        /* seq of last pkt delivered*/
frame last_frame;               /* arrive frames are kept here */
int offset;                     /* to prevent multiple timeouts on same tick*/
bigint tick;                    /* current time */
int retransmitting;             /* flag that is set on a timeout */
int nseqs = NR_TIMERS;          /* must be MAX_SEQ + 1 after startup */
unsigned int oldest_frame = NR_TIMERS;  /* tells which frame timed out */

char *badgood[] = {"bad ", "good"};
char *tag[] = {"Data", "Ack ", "Nak "};

/* Statistics */
int data_sent;                  /* number of data frames sent */
int data_retransmitted;         /* number of data frames retransmitted */
int data_lost;                  /* number of data frames lost */
int data_not_lost;              /* number of data frames not lost */
int good_data_recd;             /* number of data frames received */
int cksum_data_recd;            /* number of bad data frames received */

int acks_sent;                  /* number of ack frames sent */
int acks_lost;                  /* number of ack frames lost */
int acks_not_lost;              /* number of ack frames not lost */
int good_acks_recd;             /* number of ack frames received */
int cksum_acks_recd;            /* number of bad ack frames received */

int payloads_accepted;          /* number of pkts passed to network layer */
int timeouts;                   /* number of timeouts */
int ack_timeouts;               /* number of ack timeouts */

/* Incoming frames are buffered here for later processing. */
frame queue[MAX_QUEUE];         /* buffered incoming frames */
frame *inp = &queue[0];         /* where to put the next frame */
frame *outp = &queue[0];        /* where to remove the next frame from */
int nframes;                    /* number of queued frames */

bigint tick = 0;		/* the current time, measured in events */
bigint last_tick;		/* when to stop the simulation */
int exited[2];			/* set if exited (for each worker) */
int hanging[2];			/* # times a process has done nothing */
struct sigaction act, oact;

/* Prototypes. */
void start_simulator(void (*p1)(), void (*p2)(), long event, int tm_out, int pk_loss, int grb, int d_flags);
void set_up_pipes(void);
void fork_off_workers(void);
void terminate(char *s);

void init_max_seqnr(unsigned int o);
unsigned int get_timedout_seqnr(void);
void wait_for_event(event_type *event);
void init_frame(frame *s);
void queue_frames(void);
int pick_event(void);
event_type frametype(void);
void from_network_layer(packet *p);
void to_network_layer(packet *p);
void from_physical_layer(frame *r);
void to_physical_layer(frame *s);
void start_timer(seq_nr k);
void stop_timer(seq_nr k);
void start_ack_timer(void);
void stop_ack_timer(void);
void enable_network_layer(void);
void disable_network_layer(void);
int check_timers(void);
int check_ack_timer(void);
unsigned int pktnum(packet *p);
void fr(frame *f);
void recalc_timers(void);
void print_statistics(void);
void sim_error(char *s);
int parse_first_five_parameters(int argc, char *argv[], long *event, int *timeout_interval, int *pkt_loss, int *garbled, int *debug_flags);

void start_simulator(void (*p1)(), void (*p2)(), long event, int tm_out, int pk_loss, int grb, int d_flags)
{
/* The simulator has three processes: main(this process), M0, and M1, all of
 * which run independently.  Set them all up first.  Once set up, main
 * maintains the clock (tick), and picks a process to run.  Then it writes a
 * 32-bit word to that process to tell it to run.  The process sends back an
 * answer when it is done.  Main then picks another process, and the cycle
 * repeats.
 */

  int process = 0;		/* whose turn is it */
  int rfd, wfd;			/* file descriptor for talking to workers */
  bigint word;			/* message from worker */

  act.sa_handler = SIG_IGN;
  setvbuf(stdout, (char *) 0, _IONBF, (size_t) 0);	/* disable buffering*/

  proc1 = p1;
  proc2 = p2;
  /* Each event uses DELTA ticks to make it possible for each timeout to
   * occur at a different tick.  For example, with DELTA = 10, ticks will
   * occur at 0, 10, 20, etc.  This makes it possible to schedule multiple
   * events (e.g. in protocol 5), all at unique times, e.g. 1070, 1071, 1072,
   * 1073, etc.  This property is needed to make sure timers go off in the
   * order they were set.  As a consequence, internally, the variable tick
   * is bumped by DELTA on each event. Thus asking for a simulation run of
   * 1000 events will give 1000 events, but they internally they will be
   * called 0 to 10,000.
   */
  last_tick = DELTA * event; 

  /* Convert from external units to internal units so the user does not see
   * the internal units at all.
   */
  timeout_interval = DELTA * tm_out;

  /* Packet loss takes place at the sender.  Packets selected for being lost
   * are not put on the wire at all.  Internally, pkt_loss and garbled are
   * from 0 to 990 so they can be compared to 10 bit random numbers.  The
   * inaccuracy here is about 2.4% because 1000 != 1024.  In effect, it is
   * not possible to say that all packets are lost.  The most that can be
   * be lost is 990/1024.
   */

  pkt_loss = 10 * pk_loss; /* for our purposes, 1000 == 1024 */

  /* This arg tells what fraction of arriving packets are garbled.  Thus if
   * pkt_loss is 50 and garbled is 50, half of all packets (actually,
   * 500/1024 of all packets) will not be sent at all, and of the ones that
   * are sent, 500/1024 will arrive garbled.
   */

  garbled = 10 * grb; /* for our purposes, 1000 == 1024 */

  /* Turn tracing options on or off.  The bits are defined in worker.c. */
  debug_flags = d_flags;
  printf("\n\nEvents: %u    Parameters: %u %d %u\n",
      last_tick/DELTA, timeout_interval/DELTA, pkt_loss/10, garbled/10);

  set_up_pipes();		/* create five pipes */
  fork_off_workers();		/* fork off the worker processes */

  /* Main simulation loop. */
  while (tick <last_tick) {
	process = rand() & 1;		/* pick process to run: 0 or 1 */
	tick = tick + DELTA;
	rfd = (process == 0 ? r4 : r6);
	if (read(rfd, &word, TICK_SIZE) != TICK_SIZE) terminate("");
	if (word == OK) hanging[process] = 0;
	if (word == NOTHING) hanging[process] += DELTA;
	if (hanging[0] >= DEADLOCK && hanging[1] >= DEADLOCK)
		terminate("A deadlock has been detected");

	/* Write the time to the selected process to tell it to run. */
	wfd = (process == 0 ? w3 : w5);
	if (write(wfd, &tick, TICK_SIZE) != TICK_SIZE)
		terminate("Main could not write to worker");

  }

  /* Simulation run has finished. */
  terminate("End of simulation");
}


void set_up_pipes(void)
{
/* Create six pipes so main, M0 and M1 can communicate pairwise. */

  int fd[2];

  pipe(fd);  r1 = fd[0];  w1 = fd[1];	/* M0 to M1 for frames */
  pipe(fd);  r2 = fd[0];  w2 = fd[1];	/* M1 to M0 for frames */
  pipe(fd);  r3 = fd[0];  w3 = fd[1];	/* main to M0 for go-ahead */
  pipe(fd);  r4 = fd[0];  w4 = fd[1];	/* M0 to main to signal readiness */
  pipe(fd);  r5 = fd[0];  w5 = fd[1];	/* main to M1 for go-ahead */
  pipe(fd);  r6 = fd[0];  w6 = fd[1];	/* M1 to main to signal readiness */
}

void fork_off_workers(void)
{
/* Fork off the two workers, M0 and M1. */

  if (fork() != 0) {
	/* This is the Parent.  It will become main, but first fork off M1. */
	if (fork() != 0) {
		/* This is main. */
		sigaction(SIGPIPE, &act, &oact);
	        setvbuf(stdout, (char *)0, _IONBF, (size_t)0);/*don't buffer*/
		close(r1);
		close(w1);
		close(r2);
		close(w2);
		close(r3);
		close(w4);
		close(r5);
		close(w6);
		return;
	} else {
		/* This is the code for M1. Run protocol. */
		sigaction(SIGPIPE, &act, &oact);
	        setvbuf(stdout, (char *)0, _IONBF, (size_t)0);/*don't buffer*/
		close(w1);
		close(r2);
		close(r3);
		close(w3);
		close(r4);
		close(w4);
		close(w5);
		close(r6);
	
		id = 1;		/* M1 gets id 1 */
		mrfd = r5;	/* fd for reading time from main */
		mwfd = w6;	/* fd for writing reply to main */
		prfd = r1;	/* fd for reading frames from worker 0 */
		(*proc2)();	/* call the user-defined protocol function */
		terminate("Impossible.  Protocol terminated");
	}
  } else {
	/* This is the code for M0. Run protocol. */
	sigaction(SIGPIPE, &act, &oact);
        setvbuf(stdout, (char *)0, _IONBF, (size_t)0);/*don't buffer*/
	close(r1);
	close(w2);
	close(w3);
	close(r4);
	close(r5);
	close(w5);
	close(r6);

	id = 0;		/* M0 gets id 0 */
	mrfd = r3;	/* fd for reading time from main */
	mwfd = w4;	/* fd for writing reply to main */
	prfd = r2;	/* fd for reading frames from worker 1 */
	(*proc1)();	/* call the user-defined protocol function */
	terminate("Impossible. protocol terminated");
  }
}

void terminate(char *s)
{
/* End the simulation run by sending each worker a 32-bit zero command. */

  int n, k1, k2, res1[MANY], res2[MANY], eff, acc, sent;

  for (n = 0; n < MANY; n++) {res1[n] = 0; res2[n] = 0;}
  write(w3, &zero, TICK_SIZE);
  write(w5, &zero, TICK_SIZE);
  sleep(2);

  /* Clean out the pipe.  The zero word indicates start of statistics. */
  n = read(r4, res1, MANY*sizeof(int));
  k1 = 0;
  while (res1[k1] != 0) k1++;
  k1++;				/* res1[k1] = accepted, res1[k1+1] = sent */

  /* Clean out the other pipe and look for statistics. */
  n = read(r6, res2, MANY*sizeof(int));
  k2 = 0;
  while (res1[k2] != 0) k2++;
  k2++;				/* res1[k2] = accepted, res1[k2+1] = sent */

  if (strlen(s) > 0) {
	acc = res1[k1] + res2[k2];
	sent = res1[k1+1] + res2[k2+1];
	if (sent > 0) {
		eff = (100 * acc)/sent;
 	        printf("\nEfficiency (payloads accepted/data pkts sent) = %d%c\n", eff, '%');
	}
	printf("%s.  Time=%u\n",s, tick/DELTA);
  }
  exit(1);
 }

void init_max_seqnr(unsigned int o)
{
  nseqs = oldest_frame = o;
}

unsigned int get_timedout_seqnr(void)
{
  return(oldest_frame);
}

void wait_for_event(event_type *event)
{
/* Wait_for_event reads the pipe from main to get the time.  Then it
 * fstat's the pipe from the other worker to see if any
 * frames are there.  If so, if collects them all in the queue array.
 * Once the pipe is empty, it makes a decision about what to do next.
 */
 
 bigint ct, word = OK;

  offset = 0;			/* prevents two timeouts at the same tick */
  retransmitting = 0;		/* counts retransmissions */
  while (true) {
	queue_frames();		/* go get any newly arrived frames */
	if (write(mwfd, &word, TICK_SIZE) != TICK_SIZE) print_statistics();
	if (read(mrfd, &ct, TICK_SIZE) != TICK_SIZE) print_statistics();
	if (ct == 0) print_statistics();
	tick = ct;		/* update time */
	if ((debug_flags & PERIODIC) && (tick%INTERVAL == 0))
		printf("Tick %u. Proc %d. Data sent=%d  Payloads accepted=%d  Timeouts=%d\n", tick/DELTA, id, data_sent, payloads_accepted, timeouts);

	/* Now pick event. */
	*event = pick_event();
	if (*event == NO_EVENT) {
		word = (lowest_timer == 0 ? NOTHING : OK);
		continue;
	}
	word = OK;
	if (*event == timeout) {
		timeouts++;
		retransmitting = 1;	/* enter retransmission mode */
		if (debug_flags & TIMEOUTS)
		      printf("Tick %u. Proc %d got timeout for frame %d\n",
					       tick/DELTA, id, oldest_frame);
	}

	if (*event == ack_timeout) {
		ack_timeouts++;
		if (debug_flags & TIMEOUTS)
		      printf("Tick %u. Proc %d got ack timeout\n",
					       tick/DELTA, id);
	}
	return;
  }
}

void init_frame(frame *s)
{
  /* Fill in fields that that the simulator expects. Protocols may update
   * some of these fields. This filling is not strictly needed, but makes the
   * simulation trace look better, showing unused fields as zeros.
   */

  s->seq = 0;
  s->ack = 0;
  s->kind = (id == 0 ? data : ack);
  s->info.data[0] = 0;
  s->info.data[1] = 0;
  s->info.data[2] = 0;
  s->info.data[3] = 0;
}

void queue_frames(void)
{
/* See if any frames from the peer have arrived; if so get and queue them.
 * Queue_frames() sucks frames out of the pipe into the circular buffer,
 * queue[]. It first fstats the pipe, to avoid reading from an empty pipe and
 * thus blocking.  If inp is near the top of queue[], a single call here
 * may read a few frames into the top of queue[] and then some more starting
 * at queue[0].  This is done in two read operations.
 */

  int prfd, frct, k;
  frame *top;
  struct stat statbuf;

  prfd = (id == 0 ? r2 : r1);	/* which file descriptor is pipe on */

  if (fstat(prfd, &statbuf) < 0) sim_error("Cannot fstat peer pipe");
  frct = statbuf.st_size/FRAME_SIZE;	/* number of arrived frames */

  if (nframes + frct >= MAX_QUEUE)	/* check for possible queue overflow*/
	sim_error("Out of queue space. Increase MAX_QUEUE and re-make.");  

  /* If frct is 0, the pipe is empty, so don't read from it. */