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