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 20sim_info simulation; /* Simulation Control Variables */ 21local_clock_info simclock; /* Local Clock Variables */ 22queue *event_queue; /* Event Queue */ 23queue *recv_queue; /* Receive Queue */ 24static double sys_residual = 0; /* adjustment residue (s) */ 25 26void (*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 34int determine_event_ordering(Event *e1, Event *e2); 35 36int 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 */ 44int determine_recv_buf_ordering(struct recvbuf *b1, struct recvbuf *b2); 45 46int 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 */ 57void 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 81int 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 161Event *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 */ 178void 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 */ 207int 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 336void 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 391void 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 ***/ 413void 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 446void 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 */ 467void 468get_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 */ 497int /* always succeeds */ 498adj_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 */ 544int /* always succeeds */ 545step_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 */ 561double /* Gaussian sample */ 562gauss( 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 */ 585double /* delay sample (s) */ 586poisson( 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 605