ntpd/ntpsim.c

   1 /* ntpdsim.c
   2  *
   3  * The source code for the ntp discrete event simulator.
   4  *
   5  * Written By:  Sachin Kamboj
   6  *              University of Delaware
   7  *              Newark, DE 19711
   8  * Copyright (c) 2006
   9  * (Some code shamelessly based on the original NTP discrete event simulator)
  10  */
  11
  12 #ifdef SIM
  13 #include "ntpd.h"
  14 #include "ntpsim.h"
  15 #include "ntp_data_structures.h"
  16
  17
  18 /* Global Variable Definitions */
  19
  20 sim_info simulation;            /* Simulation Control Variables */
  21 local_clock_info simclock;      /* Local Clock Variables */
  22 queue *event_queue;             /* Event Queue */
  23 queue *recv_queue;              /* Receive Queue */
  24 static double sys_residual = 0; /* adjustment residue (s) */
  25
  26 void (*event_ptr[]) (Event *) = {
  27     sim_event_beep, sim_update_clocks, sim_event_timer, sim_event_recv_packet
  28 };                      /* Function pointer to the events */
  29
  30
  31 /* Define a function to compare two events to determine which one occurs first
  32  */
  33
  34 int determine_event_ordering(Event *e1, Event *e2);
  35
  36 int determine_event_ordering(Event *e1, Event *e2)
  37 {
  38     return (e1->time - e2->time);
  39 }
  40
  41 /* Define a function to compare two received packets to determine which one
  42  * is received first
  43  */
  44 int determine_recv_buf_ordering(struct recvbuf *b1, struct recvbuf *b2);
  45
  46 int determine_recv_buf_ordering(struct recvbuf *b1, struct recvbuf *b2)
  47 {
  48     double recv_time1, recv_time2;
  49
  50     /* Simply convert the time received to double and subtract */
  51     LFPTOD(&b1->recv_time, recv_time1);
  52     LFPTOD(&b2->recv_time, recv_time2);
  53     return ((int)(recv_time1 - recv_time2));
  54 }
  55
  56 /* Define a function to create the server associations */
  57 void create_server_associations()
  58 {
  59     int i;
  60     for (i = 0;i < simulation.num_of_servers;++i) {
  61         printf("%s\n", stoa(simulation.servers[i].addr));
  62         if (peer_config(simulation.servers[i].addr,
  63                         ANY_INTERFACE_CHOOSE(simulation.servers[i].addr),
  64                         MODE_CLIENT,
  65                         NTP_VERSION,
  66                         NTP_MINDPOLL,
  67                         NTP_MAXDPOLL,
  68                         0, /* peerflags */
  69                         0, /* ttl */
  70                         0, /* peerkey */
  71                         (u_char *)"*" /* peerkeystr */) == 0) {
  72             fprintf(stderr, "ERROR!! Could not create association for: %s",
  73                     stoa(simulation.servers[i].addr));
  74         }
  75     }
  76 }
  77
  78
  79 /* Main Simulator Code */
  80
  81 int ntpsim(int argc, char *argv[])
  82 {
  83     Event *curr_event;
  84     struct timeval seed;
  85
  86     /* Initialize the local Clock
  87      */
  88     simclock.local_time = 0;
  89     simclock.adj = 0;
  90     simclock.slew = 0;
  91
  92     /* Initialize the simulation
  93      */
  94     simulation.num_of_servers = 0;
  95     simulation.beep_delay = BEEP_DLY;
  96     simulation.sim_time = 0;
  97     simulation.end_time = SIM_TIME;
  98
  99     /*
 100      * Initialize ntp variables
 101      */
 102     initializing = 1;
 103     init_auth();
 104     init_util();
 105     init_restrict();
 106     init_mon();
 107     init_timer();
 108     init_lib();
 109     init_request();
 110     init_control();
 111     init_peer();
 112     init_proto();
 113     init_io();
 114     init_loopfilter();
 115     mon_start(MON_OFF);
 116
 117     /* Call getconfig to parse the configuration file */
 118     getconfig(argc, argv);
 119     initializing = 0;
 120     loop_config(LOOP_DRIFTCOMP, old_drift / 1e6);
 121
 122     /*
 123      * Watch out here, we want the real time, not the silly stuff.
 124      */
 125     gettimeofday(&seed, NULL);
 126     ntp_srandom(seed.tv_usec);
 127
 128
 129     /* Initialize the event queue */
 130     event_queue = create_priority_queue((int(*)(void *, void*))
 131                                         determine_event_ordering);
 132
 133     /* Initialize the receive queue */
 134     recv_queue = create_priority_queue((int(*)(void *, void*))
 135                                        determine_recv_buf_ordering);
 136
 137     /* Push a beep and a timer on the event queue */
 138     enqueue(event_queue, event(0, BEEP));
 139     enqueue(event_queue, event(simulation.sim_time + 1.0, TIMER));
 140     /*
 141      * Pop the queue until nothing is left or time is exceeded
 142      */
 143     /* maxtime = simulation.sim_time + simulation.end_time;*/
 144     while (simulation.sim_time <= simulation.end_time &&
 145            (!empty(event_queue))) {
 146         curr_event = dequeue(event_queue);
 147         /* Update all the clocks to the time on the event */
 148         sim_update_clocks(curr_event);
 149
 150         /* Execute the function associated with the event */
 151         event_ptr[curr_event->function](curr_event);
 152         free_node(curr_event);
 153     }
 154     return (0);
 155 }
 156
 157
 158
 159 /* Define a function to create an return an Event  */
 160
 161 Event *event(double t, funcTkn f)
 162 {
 163     Event *e;
 164
 165     if ((e = get_node(sizeof(*e))) == NULL)
 166         abortsim("get_node failed in event");
 167     e->time = t;
 168     e->function = f;
 169     return (e);
 170 }
 171
 172 /* NTP SIMULATION FUNCTIONS */
 173
 174 /* Define a function for processing a timer interrupt.
 175  * On every timer interrupt, call the NTP timer to send packets and process
 176  * the clock and then call the receive function to receive packets.
 177  */
 178 void sim_event_timer(Event *e)
 179 {
 180     struct recvbuf *rbuf;
 181
 182     /* Call the NTP timer.
 183      * This will be responsible for actually "sending the packets."
 184      * Since this is a simulation, the packets sent over the network
 185      * will be processed by the simulate_server routine below.
 186      */
 187     timer();
 188
 189     /* Process received buffers */
 190     while (!empty(recv_queue)) {
 191         rbuf = (struct recvbuf *)dequeue(recv_queue);
 192         (rbuf->receiver)(rbuf);
 193         free_node(rbuf);
 194     }
 195
 196     /* Arm the next timer interrupt. */
 197     enqueue(event_queue,
 198             event(simulation.sim_time + (1 << EVENT_TIMEOUT), TIMER));
 199 }
 200
 201
 202
 203 /* Define a function to simulate a server.
 204  * This function processes the sent packet according to the server script,
 205  * creates a reply packet and pushes the reply packet onto the event queue
 206  */
 207 int simulate_server(
 208     sockaddr_u *serv_addr,              /* Address of the server */
 209     struct interface *inter,            /* Interface on which the reply should
 210                                            be inserted */
 211     struct pkt *rpkt                    /* Packet sent to the server that
 212                                            needs to be processed. */
 213 )
 214 {
 215     struct pkt xpkt;           /* Packet to be transmitted back
 216                                   to the client */
 217     struct recvbuf rbuf;       /* Buffer for the received packet */
 218     Event *e;                  /* Packet receive event */
 219     server_info *server;       /* Pointer to the server being simulated */
 220     script_info *curr_script;  /* Current script being processed */
 221     int i;
 222     double d1, d2, d3;         /* Delays while the packet is enroute */
 223     double t1, t2, t3, t4;     /* The four timestamps in the packet */
 224
 225     memset(&xpkt, 0, sizeof(xpkt));
 226     memset(&rbuf, 0, sizeof(rbuf));
 227
 228     /* Search for the server with the desired address */
 229     server = NULL;
 230     for (i = 0; i < simulation.num_of_servers; ++i) {
 231         fprintf(stderr,"Checking address: %s\n", stoa(simulation.servers[i].addr));
 232         if (memcmp(simulation.servers[i].addr, serv_addr,
 233                    sizeof(*serv_addr)) == 0) {
 234             server = &simulation.servers[i];
 235             break;
 236         }
 237     }
 238
 239     fprintf(stderr, "Received packet for: %s\n", stoa(serv_addr));
 240     if (server == NULL)
 241         abortsim("Server with specified address not found!!!");
 242
 243     /* Get the current script for the server */
 244     curr_script = server->curr_script;
 245
 246     /* Create a server reply packet.
 247      * Masquerade the reply as a stratum-1 server with a GPS clock
 248      */
 249     xpkt.li_vn_mode = PKT_LI_VN_MODE(LEAP_NOWARNING, NTP_VERSION,
 250                                      MODE_SERVER);
 251     xpkt.stratum = STRATUM_TO_PKT(((u_char)1));
 252     memcpy(&xpkt.refid, "GPS", 4);
 253     xpkt.ppoll = rpkt->ppoll;
 254     xpkt.precision = rpkt->precision;
 255     xpkt.rootdelay = 0;
 256     xpkt.rootdisp = 0;
 257
 258     /* TIMESTAMP CALCULATIONS
 259             t1                           t4
 260              \                          /
 261           d1  \                        / d3
 262                \                      /
 263                t2 ----------------- t3
 264                          d2
 265     */
 266     /* Compute the delays */
 267     d1 = poisson(curr_script->prop_delay, curr_script->jitter);
 268     d2 = poisson(curr_script->proc_delay, 0);
 269     d3 = poisson(curr_script->prop_delay, curr_script->jitter);
 270
 271     /* Note: In the transmitted packet:
 272      * 1. t1 and t4 are times in the client according to the local clock.
 273      * 2. t2 and t3 are server times according to the simulated server.
 274      * Compute t1, t2, t3 and t4
 275      * Note: This function is called at time t1.
 276      */
 277
 278     LFPTOD(&rpkt->xmt, t1);
 279     t2 = server->server_time + d1;
 280     t3 = server->server_time + d1 + d2;
 281     t4 = t1 + d1 + d2 + d3;
 282
 283     /* Save the timestamps */
 284     xpkt.org = rpkt->xmt;
 285     DTOLFP(t2, &xpkt.rec);
 286     DTOLFP(t3, &xpkt.xmt);
 287     xpkt.reftime = xpkt.xmt;
 288
 289
 290
 291     /* Ok, we are done with the packet. Now initialize the receive buffer for
 292      * the packet.
 293      */
 294     rbuf.receiver = receive;   /* Function to call to process the packet */
 295     rbuf.recv_length = LEN_PKT_NOMAC;
 296     rbuf.recv_pkt = xpkt;
 297     rbuf.used = 1;
 298
 299     memcpy(&rbuf.srcadr, serv_addr, sizeof(rbuf.srcadr));
 300     memcpy(&rbuf.recv_srcadr, serv_addr, sizeof(rbuf.recv_srcadr));
 301     if ((rbuf.dstadr = malloc(sizeof(*rbuf.dstadr))) == NULL)
 302         abortsim("malloc failed in simulate_server");
 303     memcpy(rbuf.dstadr, inter, sizeof(*rbuf.dstadr));
 304     /* rbuf.link = NULL; */
 305
 306     /* Create a packet event and insert it onto the event_queue at the
 307      * arrival time (t4) of the packet at the client
 308      */
 309     e = event(t4, PACKET);
 310     e->rcv_buf = rbuf;
 311     enqueue(event_queue, e);
 312
 313
 314     /* Check if the time of the script has expired. If yes, delete the script.
 315      * If not, re-enqueue the script onto the server script queue
 316      */
 317     if (curr_script->duration > simulation.sim_time &&
 318         !empty(server->script)) {
 319         printf("Hello\n");
 320         /*
 321          * For some reason freeing up the curr_script memory kills the
 322          * simulation. Further debugging is needed to determine why.
 323          * free_node(curr_script);
 324          */
 325         curr_script = dequeue(server->script);
 326     }
 327
 328     return (0);
 329 }
 330
 331
 332 /* Define a function to update all the clocks
 333  * Most of the code is modified from the systime.c file by Prof. Mills
 334  */
 335
 336 void sim_update_clocks (Event *e)
 337 {
 338     double time_gap;
 339     double adj;
 340     int i;
 341
 342     /* Compute the time between the last update event and this update */
 343     time_gap = e->time - simulation.sim_time;
 344
 345     /* Advance the client clock */
 346     simclock.local_time = e->time + time_gap;
 347
 348     /* Advance the simulation time */
 349     simulation.sim_time = e->time;
 350
 351     /* Advance the server clocks adjusted for systematic and random frequency
 352      * errors. The random error is a random walk computed as the
 353      * integral of samples from a Gaussian distribution.
 354      */
 355     for (i = 0;i < simulation.num_of_servers; ++i) {
 356         simulation.servers[i].curr_script->freq_offset +=
 357             gauss(0, time_gap * simulation.servers[i].curr_script->wander);
 358
 359         simulation.servers[i].server_time += time_gap *
 360             (1 + simulation.servers[i].curr_script->freq_offset);
 361     }
 362
 363
 364     /* Perform the adjtime() function. If the adjustment completed
 365      * in the previous interval, amortize the entire amount; if not,
 366      * carry the leftover to the next interval.
 367      */
 368
 369     adj = time_gap * simclock.slew;
 370     if (adj < fabs(simclock.adj)) {
 371         if (simclock.adj < 0) {
 372             simclock.adj += adj;
 373             simclock.local_time -= adj;
 374         }
 375         else {
 376             simclock.adj -= adj;
 377             simclock.local_time += adj;
 378         }
 379     }
 380     else {
 381         simclock.local_time += simclock.adj;
 382         simclock.adj = 0;
 383     }
 384 }
 385
 386
 387 /* Define a function that processes a receive packet event.
 388  * This function simply inserts the packet received onto the receive queue
 389  */
 390
 391 void sim_event_recv_packet(Event *e)
 392 {
 393     struct recvbuf *rbuf;
 394
 395     /* Allocate a receive buffer and copy the packet to it */
 396     if ((rbuf = get_node(sizeof(*rbuf))) == NULL)
 397         abortsim("get_node failed in sim_event_recv_packet");
 398     memcpy(rbuf, &e->rcv_buf, sizeof(*rbuf));
 399
 400     /* Store the local time in the received packet */
 401     DTOLFP(simclock.local_time, &rbuf->recv_time);
 402
 403     /* Insert the packet received onto the receive queue */
 404     enqueue(recv_queue, rbuf);
 405 }
 406
 407
 408
 409 /* Define a function to output simulation statistics on a beep event
 410  */
 411
 412 /*** TODO: Need to decide on how to output for multiple servers ***/
 413 void sim_event_beep(Event *e)
 414 {
 415 #if 0
 416     static int first_time = 1;
 417     char *dash = "-----------------";
 418 #endif
 419
 420     fprintf(stderr, "BEEP!!!\n");
 421     enqueue(event_queue, event(e->time + simulation.beep_delay, BEEP));
 422 #if 0
 423     if(simulation.beep_delay > 0) {
 424         if (first_time) {
 425             printf("\t%4c    T    %4c\t%4c  T+ERR  %3c\t%5cT+ERR+NTP\n",
 426                    ' ', ' ', ' ', ' ',' ');
 427             printf("\t%s\t%s\t%s\n", dash, dash, dash);
 428             first_time = 0;
 429
 430             printf("\t%16.6f\t%16.6f\t%16.6f\n",
 431                    n->time, n->clk_time, n->ntp_time);
 432             return;
 433         }
 434         printf("\t%16.6f\t%16.6f\t%16.6f\n",
 435                simclock.local_time,
 436                n->time, n->clk_time, n->ntp_time);
 437 #endif
 438
 439 }
 440
 441
 442 /* Define a function to abort the simulation on an error and spit out an
 443  * error message
 444  */
 445
 446 void abortsim(char *errmsg)
 447 {
 448     perror(errmsg);
 449     exit(1);
 450 }
 451
 452
 453
 454 /* CODE ORIGINALLY IN libntp/systime.c
 455  * -----------------------------------
 456  * This code was a part of the original NTP simulator and originally
 457  * had its home in the libntp/systime.c file.
 458  *
 459  * It has been shamelessly moved to here and has been modified for the
 460  * purposes of the current simulator.
 461  */
 462
 463
 464 /*
 465  * get_systime - return the system time in NTP timestamp format
 466  */
 467 void
 468 get_systime(
 469     l_fp *now           /* current system time in l_fp */        )
 470 {
 471     /*
 472      * To fool the code that determines the local clock precision,
 473      * we advance the clock a minimum of 200 nanoseconds on every
 474      * clock read. This is appropriate for a typical modern machine
 475      * with nanosecond clocks. Note we make no attempt here to
 476      * simulate reading error, since the error is so small. This may
 477      * change when the need comes to implement picosecond clocks.
 478      */
 479     if (simclock.local_time == simclock.last_read_time)
 480         simclock.local_time += 200e-9;
 481
 482     simclock.last_read_time = simclock.local_time;
 483     DTOLFP(simclock.local_time, now);
 484 /* OLD Code
 485    if (ntp_node.ntp_time == ntp_node.last_time)
 486    ntp_node.ntp_time += 200e-9;
 487    ntp_node.last_time = ntp_node.ntp_time;
 488    DTOLFP(ntp_node.ntp_time, now);
 489 */
 490 }
 491
 492
 493 /*
 494  * adj_systime - advance or retard the system clock exactly like the
 495  * real thng.
 496  */
 497 int                             /* always succeeds */
 498 adj_systime(
 499     double now          /* time adjustment (s) */
 500     )
 501 {
 502     struct timeval adjtv;       /* new adjustment */
 503     double      dtemp;
 504     long        ticks;
 505     int isneg = 0;
 506
 507     /*
 508      * Most Unix adjtime() implementations adjust the system clock
 509      * in microsecond quanta, but some adjust in 10-ms quanta. We
 510      * carefully round the adjustment to the nearest quantum, then
 511      * adjust in quanta and keep the residue for later.
 512      */
 513     dtemp = now + sys_residual;
 514     if (dtemp < 0) {
 515         isneg = 1;
 516         dtemp = -dtemp;
 517     }
 518     adjtv.tv_sec = (long)dtemp;
 519     dtemp -= adjtv.tv_sec;
 520     ticks = (long)(dtemp / sys_tick + .5);
 521     adjtv.tv_usec = (long)(ticks * sys_tick * 1e6);
 522     dtemp -= adjtv.tv_usec / 1e6;
 523     sys_residual = dtemp;
 524
 525     /*
 526      * Convert to signed seconds and microseconds for the Unix
 527      * adjtime() system call. Note we purposely lose the adjtime()
 528      * leftover.
 529      */
 530     if (isneg) {
 531         adjtv.tv_sec = -adjtv.tv_sec;
 532         adjtv.tv_usec = -adjtv.tv_usec;
 533         sys_residual = -sys_residual;
 534     }
 535     simclock.adj = now;
 536 /*      ntp_node.adj = now; */
 537     return (1);
 538 }
 539
 540
 541 /*
 542  * step_systime - step the system clock. We are religious here.
 543  */
 544 int                             /* always succeeds */
 545 step_systime(
 546     double now          /* step adjustment (s) */
 547     )
 548 {
 549 #ifdef DEBUG
 550     if (debug)
 551         printf("step_systime: time %.6f adj %.6f\n",
 552                simclock.local_time, now);
 553 #endif
 554     simclock.local_time += now;
 555     return (1);
 556 }
 557
 558 /*
 559  * gauss() - returns samples from a gaussion distribution
 560  */
 561 double                          /* Gaussian sample */
 562 gauss(
 563     double m,           /* sample mean */
 564     double s            /* sample standard deviation (sigma) */
 565     )
 566 {
 567     double q1, q2;
 568
 569     /*
 570      * Roll a sample from a Gaussian distribution with mean m and
 571      * standard deviation s. For m = 0, s = 1, mean(y) = 0,
 572      * std(y) = 1.
 573      */
 574     if (s == 0)
 575         return (m);
 576     while ((q1 = drand48()) == 0);
 577     q2 = drand48();
 578     return (m + s * sqrt(-2. * log(q1)) * cos(2. * PI * q2));
 579 }
 580
 581
 582 /*
 583  * poisson() - returns samples from a network delay distribution
 584  */
 585 double                          /* delay sample (s) */
 586 poisson(
 587     double m,           /* fixed propagation delay (s) */
 588     double s            /* exponential parameter (mu) */
 589     )
 590 {
 591     double q1;
 592
 593     /*
 594      * Roll a sample from a composite distribution with propagation
 595      * delay m and exponential distribution time with parameter s.
 596      * For m = 0, s = 1, mean(y) = std(y) = 1.
 597      */
 598     if (s == 0)
 599         return (m);
 600     while ((q1 = drand48()) == 0);
 601     return (m - s * log(q1 * s));
 602 }
 603
 604 #endif