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
determine_event_ordering(const Event * e1,const Event * e2)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
determine_recv_buf_ordering(const struct recvbuf * b1,const struct recvbuf * b2)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 */
create_server_associations(void)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
ntpsim(int argc,char * argv[])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
init_sim_io(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
event(double t,funcTkn f)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 */
sim_event_timer(Event * e)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 */
simulate_server(sockaddr_u * serv_addr,endpt * inter,struct pkt * rpkt)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
sim_update_clocks(Event * e)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
sim_event_recv_packet(Event * e)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 ***/
sim_event_beep(Event * e)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