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 */ 18int determine_event_ordering(const Event *e1, const Event *e2); 19int determine_recv_buf_ordering(const struct recvbuf *b1, 20 const struct recvbuf *b2); 21void create_server_associations(void); 22void init_sim_io(void); 23 24/* Global Variable Definitions */ 25sim_info simulation; /* Simulation Control Variables */ 26local_clock_info simclock; /* Local Clock Variables */ 27queue *event_queue; /* Event Queue */ 28queue *recv_queue; /* Receive Queue */ 29static double sys_residual = 0; /* adjustment residue (s) */ 30 31void (*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 */ 40int 41determine_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 */ 54int 55determine_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 */ 72void 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 100int 101ntpsim( 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 187void 188init_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 209Event *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 */ 226void 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 */ 255int 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 384void 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 443void 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 ***/ 465void 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 498void 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 */ 519void 520get_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 */ 549int /* always succeeds */ 550adj_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 */ 596int /* always succeeds */ 597step_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 */ 613double /* Gaussian sample */ 614gauss( 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 */ 638double /* delay sample (s) */ 639poisson( 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 659