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