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