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