2 * ntp_proto.c - NTP version 4 protocol machinery
4 * ATTENTION: Get approval from Dave Mills on all changes to this file!
12 #include "ntp_stdlib.h"
13 #include "ntp_unixtime.h"
14 #include "ntp_control.h"
15 #include "ntp_string.h"
16 #include "ntp_leapsec.h"
17 #include "refidsmear.h"
28 * This macro defines the authentication state. If x is 1 authentication
29 * is required; othewise it is optional.
31 #define AUTH(x, y) ((x) ? (y) == AUTH_OK : (y) == AUTH_OK || \
34 #define AUTH_NONE 0 /* authentication not required */
35 #define AUTH_OK 1 /* authentication OK */
36 #define AUTH_ERROR 2 /* authentication error */
37 #define AUTH_CRYPTO 3 /* crypto_NAK */
40 * traffic shaping parameters
42 #define NTP_IBURST 6 /* packets in iburst */
43 #define RESP_DELAY 1 /* refclock burst delay (s) */
46 * pool soliciting restriction duration (s)
48 #define POOL_SOLICIT_WINDOW 8
51 * peer_select groups statistics for a peer used by clock_select() and
54 typedef struct peer_select_tag {
56 double synch; /* sync distance */
57 double error; /* jitter */
58 double seljit; /* selection jitter */
62 * System variables are declared here. Unless specified otherwise, all
63 * times are in seconds.
65 u_char sys_leap; /* system leap indicator, use set_sys_leap() to change this */
66 u_char xmt_leap; /* leap indicator sent in client requests, set up by set_sys_leap() */
67 u_char sys_stratum; /* system stratum */
68 s_char sys_precision; /* local clock precision (log2 s) */
69 double sys_rootdelay; /* roundtrip delay to primary source */
70 double sys_rootdisp; /* dispersion to primary source */
71 u_int32 sys_refid; /* reference id (network byte order) */
72 l_fp sys_reftime; /* last update time */
73 struct peer *sys_peer; /* current peer */
76 struct leap_smear_info leap_smear;
78 int leap_sec_in_progress;
81 * Rate controls. Leaky buckets are used to throttle the packet
82 * transmission rates in order to protect busy servers such as at NIST
83 * and USNO. There is a counter for each association and another for KoD
84 * packets. The association counter decrements each second, but not
85 * below zero. Each time a packet is sent the counter is incremented by
86 * a configurable value representing the average interval between
87 * packets. A packet is delayed as long as the counter is greater than
88 * zero. Note this does not affect the time value computations.
91 * Nonspecified system state variables
93 int sys_bclient; /* broadcast client enable */
94 double sys_bdelay; /* broadcast client default delay */
95 int sys_authenticate; /* requre authentication for config */
96 l_fp sys_authdelay; /* authentication delay */
97 double sys_offset; /* current local clock offset */
98 double sys_mindisp = MINDISPERSE; /* minimum distance (s) */
99 double sys_maxdist = MAXDISTANCE; /* selection threshold */
100 double sys_jitter; /* system jitter */
101 u_long sys_epoch; /* last clock update time */
102 static double sys_clockhop; /* clockhop threshold */
103 static int leap_vote_ins; /* leap consensus for insert */
104 static int leap_vote_del; /* leap consensus for delete */
105 keyid_t sys_private; /* private value for session seed */
106 int sys_manycastserver; /* respond to manycast client pkts */
107 int ntp_mode7; /* respond to ntpdc (mode7) */
108 int peer_ntpdate; /* active peers in ntpdate mode */
109 int sys_survivors; /* truest of the truechimers */
110 char *sys_ident = NULL; /* identity scheme */
113 * TOS and multicast mapping stuff
115 int sys_floor = 0; /* cluster stratum floor */
116 int sys_ceiling = STRATUM_UNSPEC - 1; /* cluster stratum ceiling */
117 int sys_minsane = 1; /* minimum candidates */
118 int sys_minclock = NTP_MINCLOCK; /* minimum candidates */
119 int sys_maxclock = NTP_MAXCLOCK; /* maximum candidates */
120 int sys_cohort = 0; /* cohort switch */
121 int sys_orphan = STRATUM_UNSPEC + 1; /* orphan stratum */
122 int sys_orphwait = NTP_ORPHWAIT; /* orphan wait */
123 int sys_beacon = BEACON; /* manycast beacon interval */
124 int sys_ttlmax; /* max ttl mapping vector index */
125 u_char sys_ttl[MAX_TTL]; /* ttl mapping vector */
128 * Statistics counters - first the good, then the bad
130 u_long sys_stattime; /* elapsed time */
131 u_long sys_received; /* packets received */
132 u_long sys_processed; /* packets for this host */
133 u_long sys_newversion; /* current version */
134 u_long sys_oldversion; /* old version */
135 u_long sys_restricted; /* access denied */
136 u_long sys_badlength; /* bad length or format */
137 u_long sys_badauth; /* bad authentication */
138 u_long sys_declined; /* declined */
139 u_long sys_limitrejected; /* rate exceeded */
140 u_long sys_kodsent; /* KoD sent */
142 static double root_distance (struct peer *);
143 static void clock_combine (peer_select *, int, int);
144 static void peer_xmit (struct peer *);
145 static void fast_xmit (struct recvbuf *, int, keyid_t, int);
146 static void pool_xmit (struct peer *);
147 static void clock_update (struct peer *);
148 static void measure_precision(void);
149 static double measure_tick_fuzz(void);
150 static int local_refid (struct peer *);
151 static int peer_unfit (struct peer *);
153 static int group_test (char *, char *);
156 void pool_name_resolved (int, int, void *, const char *,
157 const char *, const struct addrinfo *,
158 const struct addrinfo *);
162 set_sys_leap(u_char new_sys_leap) {
163 sys_leap = new_sys_leap;
167 * Under certain conditions we send faked leap bits to clients, so
168 * eventually change xmt_leap below, but never change LEAP_NOTINSYNC.
170 if (xmt_leap != LEAP_NOTINSYNC) {
171 if (leap_sec_in_progress) {
172 /* always send "not sync" */
173 xmt_leap = LEAP_NOTINSYNC;
178 * If leap smear is enabled in general we must never send a leap second warning
179 * to clients, so make sure we only send "in sync".
181 if (leap_smear.enabled)
182 xmt_leap = LEAP_NOWARNING;
184 #endif /* LEAP_SMEAR */
190 * transmit - transmit procedure called by poll timeout
194 struct peer *peer /* peer structure pointer */
200 * The polling state machine. There are two kinds of machines,
201 * those that never expect a reply (broadcast and manycast
202 * server modes) and those that do (all other modes). The dance
208 * In broadcast mode the poll interval is never changed from
211 if (peer->cast_flags & (MDF_BCAST | MDF_MCAST)) {
212 peer->outdate = current_time;
213 if (sys_leap != LEAP_NOTINSYNC)
215 poll_update(peer, hpoll);
220 * In manycast mode we start with unity ttl. The ttl is
221 * increased by one for each poll until either sys_maxclock
222 * servers have been found or the maximum ttl is reached. When
223 * sys_maxclock servers are found we stop polling until one or
224 * more servers have timed out or until less than sys_minclock
225 * associations turn up. In this case additional better servers
226 * are dragged in and preempt the existing ones. Once every
227 * sys_beacon seconds we are to transmit unconditionally, but
228 * this code is not quite right -- peer->unreach counts polls
229 * and is being compared with sys_beacon, so the beacons happen
230 * every sys_beacon polls.
232 if (peer->cast_flags & MDF_ACAST) {
233 peer->outdate = current_time;
234 if (peer->unreach > sys_beacon) {
238 } else if (sys_survivors < sys_minclock ||
239 peer_associations < sys_maxclock) {
240 if (peer->ttl < (u_int32)sys_ttlmax)
245 poll_update(peer, hpoll);
250 * Pool associations transmit unicast solicitations when there
251 * are less than a hard limit of 2 * sys_maxclock associations,
252 * and either less than sys_minclock survivors or less than
253 * sys_maxclock associations. The hard limit prevents unbounded
254 * growth in associations if the system clock or network quality
255 * result in survivor count dipping below sys_minclock often.
256 * This was observed testing with pool, where sys_maxclock == 12
257 * resulted in 60 associations without the hard limit. A
258 * similar hard limit on manycastclient ephemeral associations
259 * may be appropriate.
261 if (peer->cast_flags & MDF_POOL) {
262 peer->outdate = current_time;
263 if ((peer_associations <= 2 * sys_maxclock) &&
264 (peer_associations < sys_maxclock ||
265 sys_survivors < sys_minclock))
267 poll_update(peer, hpoll);
272 * In unicast modes the dance is much more intricate. It is
273 * designed to back off whenever possible to minimize network
276 if (peer->burst == 0) {
280 * Update the reachability status. If not heard for
281 * three consecutive polls, stuff infinity in the clock
284 oreach = peer->reach;
285 peer->outdate = current_time;
291 * Here the peer is unreachable. If it was
292 * previously reachable raise a trap. Send a
295 clock_filter(peer, 0., 0., MAXDISPERSE);
298 report_event(PEVNT_UNREACH, peer, NULL);
300 if ((peer->flags & FLAG_IBURST) &&
302 peer->retry = NTP_RETRY;
306 * Here the peer is reachable. Send a burst if
307 * enabled and the peer is fit. Reset unreach
308 * for persistent and ephemeral associations.
309 * Unreach is also reset for survivors in
313 if (!(peer->flags & FLAG_PREEMPT))
315 if ((peer->flags & FLAG_BURST) && peer->retry ==
316 0 && !peer_unfit(peer))
317 peer->retry = NTP_RETRY;
321 * Watch for timeout. If ephemeral, toss the rascal;
322 * otherwise, bump the poll interval. Note the
323 * poll_update() routine will clamp it to maxpoll.
324 * If preemptible and we have more peers than maxclock,
325 * and this peer has the minimum score of preemptibles,
328 if (peer->unreach >= NTP_UNREACH) {
330 /* ephemeral: no FLAG_CONFIG nor FLAG_PREEMPT */
331 if (!(peer->flags & (FLAG_CONFIG | FLAG_PREEMPT))) {
332 report_event(PEVNT_RESTART, peer, "timeout");
333 peer_clear(peer, "TIME");
337 if ((peer->flags & FLAG_PREEMPT) &&
338 (peer_associations > sys_maxclock) &&
340 report_event(PEVNT_RESTART, peer, "timeout");
341 peer_clear(peer, "TIME");
348 if (peer->burst == 0) {
351 * If ntpdate mode and the clock has not been
352 * set and all peers have completed the burst,
353 * we declare a successful failure.
357 if (peer_ntpdate == 0) {
359 "ntpd: no servers found");
362 "ntpd: no servers found\n");
372 * Do not transmit if in broadcast client mode.
374 if (peer->hmode != MODE_BCLIENT)
376 poll_update(peer, hpoll);
381 * receive - receive procedure called for each packet received
385 struct recvbuf *rbufp
388 register struct peer *peer; /* peer structure pointer */
389 register struct pkt *pkt; /* receive packet pointer */
390 u_char hisversion; /* packet version */
391 u_char hisleap; /* packet leap indicator */
392 u_char hismode; /* packet mode */
393 u_char hisstratum; /* packet stratum */
394 u_short restrict_mask; /* restrict bits */
395 int has_mac; /* length of MAC field */
396 int authlen; /* offset of MAC field */
397 int is_authentic = 0; /* cryptosum ok */
398 int retcode = AM_NOMATCH; /* match code */
399 keyid_t skeyid = 0; /* key IDs */
400 u_int32 opcode = 0; /* extension field opcode */
401 sockaddr_u *dstadr_sin; /* active runway */
402 struct peer *peer2; /* aux peer structure pointer */
403 endpt * match_ep; /* newpeer() local address */
404 l_fp p_org; /* origin timestamp */
405 l_fp p_rec; /* receive timestamp */
406 l_fp p_xmt; /* transmit timestamp */
408 char hostname[NTP_MAXSTRLEN + 1];
409 char *groupname = NULL;
410 struct autokey *ap; /* autokey structure pointer */
411 int rval; /* cookie snatcher */
412 keyid_t pkeyid = 0, tkeyid = 0; /* key IDs */
414 #ifdef HAVE_NTP_SIGND
415 static unsigned char zero_key[16];
416 #endif /* HAVE_NTP_SIGND */
419 * Monitor the packet and get restrictions. Note that the packet
420 * length for control and private mode packets must be checked
421 * by the service routines. Some restrictions have to be handled
422 * later in order to generate a kiss-o'-death packet.
425 * Bogus port check is before anything, since it probably
426 * reveals a clogging attack.
429 if (0 == SRCPORT(&rbufp->recv_srcadr)) {
431 return; /* bogus port */
433 restrict_mask = restrictions(&rbufp->recv_srcadr);
434 DPRINTF(2, ("receive: at %ld %s<-%s flags %x restrict %03x\n",
435 current_time, stoa(&rbufp->dstadr->sin),
436 stoa(&rbufp->recv_srcadr),
437 rbufp->dstadr->flags, restrict_mask));
438 pkt = &rbufp->recv_pkt;
439 hisversion = PKT_VERSION(pkt->li_vn_mode);
440 hisleap = PKT_LEAP(pkt->li_vn_mode);
441 hismode = (int)PKT_MODE(pkt->li_vn_mode);
442 hisstratum = PKT_TO_STRATUM(pkt->stratum);
443 if (restrict_mask & RES_IGNORE) {
445 return; /* ignore everything */
447 if (hismode == MODE_PRIVATE) {
448 if (!ntp_mode7 || (restrict_mask & RES_NOQUERY)) {
450 return; /* no query private */
452 process_private(rbufp, ((restrict_mask &
453 RES_NOMODIFY) == 0));
456 if (hismode == MODE_CONTROL) {
457 if (restrict_mask & RES_NOQUERY) {
459 return; /* no query control */
461 process_control(rbufp, restrict_mask);
464 if (restrict_mask & RES_DONTSERVE) {
466 return; /* no time serve */
470 * This is for testing. If restricted drop ten percent of
473 if (restrict_mask & RES_FLAKE) {
474 if ((double)ntp_random() / 0x7fffffff < .1) {
476 return; /* no flakeway */
481 * Version check must be after the query packets, since they
482 * intentionally use an early version.
484 if (hisversion == NTP_VERSION) {
485 sys_newversion++; /* new version */
486 } else if (!(restrict_mask & RES_VERSION) && hisversion >=
488 sys_oldversion++; /* previous version */
491 return; /* old version */
495 * Figure out his mode and validate the packet. This has some
496 * legacy raunch that probably should be removed. In very early
497 * NTP versions mode 0 was equivalent to what later versions
498 * would interpret as client mode.
500 if (hismode == MODE_UNSPEC) {
501 if (hisversion == NTP_OLDVERSION) {
502 hismode = MODE_CLIENT;
505 return; /* invalid mode */
510 * Parse the extension field if present. We figure out whether
511 * an extension field is present by measuring the MAC size. If
512 * the number of words following the packet header is 0, no MAC
513 * is present and the packet is not authenticated. If 1, the
514 * packet is a crypto-NAK; if 3, the packet is authenticated
515 * with DES; if 5, the packet is authenticated with MD5; if 6,
516 * the packet is authenticated with SHA. If 2 or * 4, the packet
517 * is a runt and discarded forthwith. If greater than 6, an
518 * extension field is present, so we subtract the length of the
519 * field and go around again.
521 authlen = LEN_PKT_NOMAC;
522 has_mac = rbufp->recv_length - authlen;
523 while (has_mac > 0) {
530 if (has_mac % 4 != 0 || has_mac < (int)MIN_MAC_LEN) {
532 return; /* bad length */
534 if (has_mac <= (int)MAX_MAC_LEN) {
535 skeyid = ntohl(((u_int32 *)pkt)[authlen / 4]);
539 opcode = ntohl(((u_int32 *)pkt)[authlen / 4]);
540 len = opcode & 0xffff;
541 if (len % 4 != 0 || len < 4 || (int)len +
542 authlen > rbufp->recv_length) {
544 return; /* bad length */
548 * Extract calling group name for later. If
549 * sys_groupname is non-NULL, there must be
550 * a group name provided to elicit a response.
552 if ((opcode & 0x3fff0000) == CRYPTO_ASSOC &&
553 sys_groupname != NULL) {
554 ep = (struct exten *)&((u_int32 *)pkt)[authlen / 4];
555 hostlen = ntohl(ep->vallen);
556 if (hostlen >= sizeof(hostname) ||
558 offsetof(struct exten, pkt)) {
560 return; /* bad length */
562 memcpy(hostname, &ep->pkt, hostlen);
563 hostname[hostlen] = '\0';
564 groupname = strchr(hostname, '@');
565 if (groupname == NULL) {
578 * If has_mac is < 0 we had a malformed packet.
582 return; /* bad length */
586 * If authentication required, a MAC must be present.
588 if (restrict_mask & RES_DONTTRUST && has_mac == 0) {
590 return; /* access denied */
594 * Update the MRU list and finger the cloggers. It can be a
595 * little expensive, so turn it off for production use.
596 * RES_LIMITED and RES_KOD will be cleared in the returned
597 * restrict_mask unless one or both actions are warranted.
599 restrict_mask = ntp_monitor(rbufp, restrict_mask);
600 if (restrict_mask & RES_LIMITED) {
602 if (!(restrict_mask & RES_KOD) || MODE_BROADCAST ==
603 hismode || MODE_SERVER == hismode) {
604 if (MODE_SERVER == hismode)
605 DPRINTF(1, ("Possibly self-induced rate limiting of MODE_SERVER from %s\n",
606 stoa(&rbufp->recv_srcadr)));
607 return; /* rate exceeded */
609 if (hismode == MODE_CLIENT)
610 fast_xmit(rbufp, MODE_SERVER, skeyid,
613 fast_xmit(rbufp, MODE_ACTIVE, skeyid,
615 return; /* rate exceeded */
617 restrict_mask &= ~RES_KOD;
620 * We have tossed out as many buggy packets as possible early in
621 * the game to reduce the exposure to a clogging attack. Now we
622 * have to burn some cycles to find the association and
623 * authenticate the packet if required. Note that we burn only
624 * digest cycles, again to reduce exposure. There may be no
625 * matching association and that's okay.
627 * More on the autokey mambo. Normally the local interface is
628 * found when the association was mobilized with respect to a
629 * designated remote address. We assume packets arriving from
630 * the remote address arrive via this interface and the local
631 * address used to construct the autokey is the unicast address
632 * of the interface. However, if the sender is a broadcaster,
633 * the interface broadcast address is used instead.
634 * Notwithstanding this technobabble, if the sender is a
635 * multicaster, the broadcast address is null, so we use the
636 * unicast address anyway. Don't ask.
638 peer = findpeer(rbufp, hismode, &retcode);
639 dstadr_sin = &rbufp->dstadr->sin;
640 NTOHL_FP(&pkt->org, &p_org);
641 NTOHL_FP(&pkt->rec, &p_rec);
642 NTOHL_FP(&pkt->xmt, &p_xmt);
645 * Authentication is conditioned by three switches:
647 * NOPEER (RES_NOPEER) do not mobilize an association unless
649 * NOTRUST (RES_DONTTRUST) do not allow access unless
650 * authenticated (implies NOPEER)
651 * enable (sys_authenticate) master NOPEER switch, by default
654 * The NOPEER and NOTRUST can be specified on a per-client basis
655 * using the restrict command. The enable switch if on implies
656 * NOPEER for all clients. There are four outcomes:
658 * NONE The packet has no MAC.
659 * OK the packet has a MAC and authentication succeeds
660 * ERROR the packet has a MAC and authentication fails
661 * CRYPTO crypto-NAK. The MAC has four octets only.
663 * Note: The AUTH(x, y) macro is used to filter outcomes. If x
664 * is zero, acceptable outcomes of y are NONE and OK. If x is
665 * one, the only acceptable outcome of y is OK.
669 restrict_mask &= ~RES_MSSNTP;
670 is_authentic = AUTH_NONE; /* not required */
674 "receive: at %ld %s<-%s mode %d len %d\n",
675 current_time, stoa(dstadr_sin),
676 stoa(&rbufp->recv_srcadr), hismode,
679 } else if (has_mac == 4) {
680 restrict_mask &= ~RES_MSSNTP;
681 is_authentic = AUTH_CRYPTO; /* crypto-NAK */
685 "receive: at %ld %s<-%s mode %d keyid %08x len %d auth %d\n",
686 current_time, stoa(dstadr_sin),
687 stoa(&rbufp->recv_srcadr), hismode, skeyid,
688 authlen + has_mac, is_authentic);
691 #ifdef HAVE_NTP_SIGND
693 * If the signature is 20 bytes long, the last 16 of
694 * which are zero, then this is a Microsoft client
695 * wanting AD-style authentication of the server's
698 * This is described in Microsoft's WSPP docs, in MS-SNTP:
699 * http://msdn.microsoft.com/en-us/library/cc212930.aspx
701 } else if (has_mac == MAX_MD5_LEN && (restrict_mask & RES_MSSNTP) &&
702 (retcode == AM_FXMIT || retcode == AM_NEWPASS) &&
703 (memcmp(zero_key, (char *)pkt + authlen + 4, MAX_MD5_LEN - 4) ==
705 is_authentic = AUTH_NONE;
706 #endif /* HAVE_NTP_SIGND */
709 restrict_mask &= ~RES_MSSNTP;
712 * For autokey modes, generate the session key
713 * and install in the key cache. Use the socket
714 * broadcast or unicast address as appropriate.
716 if (crypto_flags && skeyid > NTP_MAXKEY) {
719 * More on the autokey dance (AKD). A cookie is
720 * constructed from public and private values.
721 * For broadcast packets, the cookie is public
722 * (zero). For packets that match no
723 * association, the cookie is hashed from the
724 * addresses and private value. For server
725 * packets, the cookie was previously obtained
726 * from the server. For symmetric modes, the
727 * cookie was previously constructed using an
728 * agreement protocol; however, should PKI be
729 * unavailable, we construct a fake agreement as
730 * the EXOR of the peer and host cookies.
732 * hismode ephemeral persistent
733 * =======================================
736 * client sys cookie 0%
737 * server 0% sys cookie
743 if (has_mac < (int)MAX_MD5_LEN) {
747 if (hismode == MODE_BROADCAST) {
750 * For broadcaster, use the interface
751 * broadcast address when available;
752 * otherwise, use the unicast address
753 * found when the association was
754 * mobilized. However, if this is from
755 * the wildcard interface, game over.
757 if (crypto_flags && rbufp->dstadr ==
758 ANY_INTERFACE_CHOOSE(&rbufp->recv_srcadr)) {
760 return; /* no wildcard */
763 if (!SOCK_UNSPEC(&rbufp->dstadr->bcast))
765 &rbufp->dstadr->bcast;
766 } else if (peer == NULL) {
767 pkeyid = session_key(
768 &rbufp->recv_srcadr, dstadr_sin, 0,
771 pkeyid = peer->pcookie;
775 * The session key includes both the public
776 * values and cookie. In case of an extension
777 * field, the cookie used for authentication
778 * purposes is zero. Note the hash is saved for
779 * use later in the autokey mambo.
781 if (authlen > (int)LEN_PKT_NOMAC && pkeyid != 0) {
782 session_key(&rbufp->recv_srcadr,
783 dstadr_sin, skeyid, 0, 2);
784 tkeyid = session_key(
785 &rbufp->recv_srcadr, dstadr_sin,
788 tkeyid = session_key(
789 &rbufp->recv_srcadr, dstadr_sin,
797 * Compute the cryptosum. Note a clogging attack may
798 * succeed in bloating the key cache. If an autokey,
799 * purge it immediately, since we won't be needing it
800 * again. If the packet is authentic, it can mobilize an
801 * association. Note that there is no key zero.
803 if (!authdecrypt(skeyid, (u_int32 *)pkt, authlen,
805 is_authentic = AUTH_ERROR;
807 is_authentic = AUTH_OK;
809 if (crypto_flags && skeyid > NTP_MAXKEY)
810 authtrust(skeyid, 0);
815 "receive: at %ld %s<-%s mode %d keyid %08x len %d auth %d\n",
816 current_time, stoa(dstadr_sin),
817 stoa(&rbufp->recv_srcadr), hismode, skeyid,
818 authlen + has_mac, is_authentic);
823 * The association matching rules are implemented by a set of
824 * routines and an association table. A packet matching an
825 * association is processed by the peer process for that
826 * association. If there are no errors, an ephemeral association
827 * is mobilized: a broadcast packet mobilizes a broadcast client
828 * aassociation; a manycast server packet mobilizes a manycast
829 * client association; a symmetric active packet mobilizes a
830 * symmetric passive association.
835 * This is a client mode packet not matching any association. If
836 * an ordinary client, simply toss a server mode packet back
837 * over the fence. If a manycast client, we have to work a
843 * If authentication OK, send a server reply; otherwise,
846 if (!(rbufp->dstadr->flags & INT_MCASTOPEN)) {
847 if (AUTH(restrict_mask & RES_DONTTRUST,
849 fast_xmit(rbufp, MODE_SERVER, skeyid,
851 } else if (is_authentic == AUTH_ERROR) {
852 fast_xmit(rbufp, MODE_SERVER, 0,
862 * This must be manycast. Do not respond if not
863 * configured as a manycast server.
865 if (!sys_manycastserver) {
867 return; /* not enabled */
872 * Do not respond if not the same group.
874 if (group_test(groupname, NULL)) {
881 * Do not respond if we are not synchronized or our
882 * stratum is greater than the manycaster or the
883 * manycaster has already synchronized to us.
885 if (sys_leap == LEAP_NOTINSYNC || sys_stratum >=
886 hisstratum || (!sys_cohort && sys_stratum ==
887 hisstratum + 1) || rbufp->dstadr->addr_refid ==
890 return; /* no help */
894 * Respond only if authentication succeeds. Don't do a
895 * crypto-NAK, as that would not be useful.
897 if (AUTH(restrict_mask & RES_DONTTRUST, is_authentic))
898 fast_xmit(rbufp, MODE_SERVER, skeyid,
903 * This is a server mode packet returned in response to a client
904 * mode packet sent to a multicast group address (for
905 * manycastclient) or to a unicast address (for pool). The
906 * origin timestamp is a good nonce to reliably associate the
907 * reply with what was sent. If there is no match, that's
908 * curious and could be an intruder attempting to clog, so we
911 * If the packet is authentic and the manycastclient or pool
912 * association is found, we mobilize a client association and
913 * copy pertinent variables from the manycastclient or pool
914 * association to the new client association. If not, just
917 * There is an implosion hazard at the manycast client, since
918 * the manycast servers send the server packet immediately. If
919 * the guy is already here, don't fire up a duplicate.
925 * Do not respond if not the same group.
927 if (group_test(groupname, NULL)) {
932 if ((peer2 = findmanycastpeer(rbufp)) == NULL) {
934 return; /* not enabled */
936 if (!AUTH((!(peer2->cast_flags & MDF_POOL) &&
937 sys_authenticate) | (restrict_mask & (RES_NOPEER |
938 RES_DONTTRUST)), is_authentic)) {
940 return; /* access denied */
944 * Do not respond if unsynchronized or stratum is below
945 * the floor or at or above the ceiling.
947 if (hisleap == LEAP_NOTINSYNC || hisstratum <
948 sys_floor || hisstratum >= sys_ceiling) {
950 return; /* no help */
952 peer = newpeer(&rbufp->recv_srcadr, NULL, rbufp->dstadr,
953 MODE_CLIENT, hisversion, peer2->minpoll,
954 peer2->maxpoll, FLAG_PREEMPT |
955 (FLAG_IBURST & peer2->flags), MDF_UCAST |
956 MDF_UCLNT, 0, skeyid, sys_ident);
959 return; /* ignore duplicate */
963 * After each ephemeral pool association is spun,
964 * accelerate the next poll for the pool solicitor so
965 * the pool will fill promptly.
967 if (peer2->cast_flags & MDF_POOL)
968 peer2->nextdate = current_time + 1;
971 * Further processing of the solicitation response would
972 * simply detect its origin timestamp as bogus for the
973 * brand-new association (it matches the prototype
974 * association) and tinker with peer->nextdate delaying
977 return; /* solicitation response handled */
980 * This is the first packet received from a broadcast server. If
981 * the packet is authentic and we are enabled as broadcast
982 * client, mobilize a broadcast client association. We don't
983 * kiss any frogs here.
989 * Do not respond if not the same group.
991 if (group_test(groupname, sys_ident)) {
996 if (sys_bclient == 0) {
998 return; /* not enabled */
1000 if (!AUTH(sys_authenticate | (restrict_mask &
1001 (RES_NOPEER | RES_DONTTRUST)), is_authentic)) {
1003 return; /* access denied */
1007 * Do not respond if unsynchronized or stratum is below
1008 * the floor or at or above the ceiling.
1010 if (hisleap == LEAP_NOTINSYNC || hisstratum <
1011 sys_floor || hisstratum >= sys_ceiling) {
1013 return; /* no help */
1018 * Do not respond if Autokey and the opcode is not a
1019 * CRYPTO_ASSOC response with association ID.
1021 if (crypto_flags && skeyid > NTP_MAXKEY && (opcode &
1022 0xffff0000) != (CRYPTO_ASSOC | CRYPTO_RESP)) {
1024 return; /* protocol error */
1026 #endif /* AUTOKEY */
1029 * Broadcasts received via a multicast address may
1030 * arrive after a unicast volley has begun
1031 * with the same remote address. newpeer() will not
1032 * find duplicate associations on other local endpoints
1033 * if a non-NULL endpoint is supplied. multicastclient
1034 * ephemeral associations are unique across all local
1037 if (!(INT_MCASTOPEN & rbufp->dstadr->flags))
1038 match_ep = rbufp->dstadr;
1043 * Determine whether to execute the initial volley.
1045 if (sys_bdelay != 0) {
1048 * If a two-way exchange is not possible,
1049 * neither is Autokey.
1051 if (crypto_flags && skeyid > NTP_MAXKEY) {
1053 return; /* no autokey */
1055 #endif /* AUTOKEY */
1058 * Do not execute the volley. Start out in
1059 * broadcast client mode.
1061 peer = newpeer(&rbufp->recv_srcadr, NULL,
1062 match_ep, MODE_BCLIENT, hisversion,
1063 pkt->ppoll, pkt->ppoll, FLAG_PREEMPT,
1064 MDF_BCLNT, 0, skeyid, sys_ident);
1067 return; /* ignore duplicate */
1070 peer->delay = sys_bdelay;
1076 * Execute the initial volley in order to calibrate the
1077 * propagation delay and run the Autokey protocol.
1079 * Note that the minpoll is taken from the broadcast
1080 * packet, normally 6 (64 s) and that the poll interval
1081 * is fixed at this value.
1083 peer = newpeer(&rbufp->recv_srcadr, NULL, match_ep,
1084 MODE_CLIENT, hisversion, pkt->ppoll, pkt->ppoll,
1085 FLAG_BC_VOL | FLAG_IBURST | FLAG_PREEMPT, MDF_BCLNT,
1086 0, skeyid, sys_ident);
1089 return; /* ignore duplicate */
1092 if (skeyid > NTP_MAXKEY)
1093 crypto_recv(peer, rbufp);
1094 #endif /* AUTOKEY */
1096 return; /* hooray */
1099 * This is the first packet received from a symmetric active
1100 * peer. If the packet is authentic and the first he sent,
1101 * mobilize a passive association. If not, kiss the frog.
1107 * Do not respond if not the same group.
1109 if (group_test(groupname, sys_ident)) {
1113 #endif /* AUTOKEY */
1114 if (!AUTH(sys_authenticate | (restrict_mask &
1115 (RES_NOPEER | RES_DONTTRUST)), is_authentic)) {
1118 * If authenticated but cannot mobilize an
1119 * association, send a symmetric passive
1120 * response without mobilizing an association.
1121 * This is for drat broken Windows clients. See
1122 * Microsoft KB 875424 for preferred workaround.
1124 if (AUTH(restrict_mask & RES_DONTTRUST,
1126 fast_xmit(rbufp, MODE_PASSIVE, skeyid,
1128 return; /* hooray */
1130 if (is_authentic == AUTH_ERROR) {
1131 fast_xmit(rbufp, MODE_ACTIVE, 0,
1139 * Do not respond if synchronized and if stratum is
1140 * below the floor or at or above the ceiling. Note,
1141 * this allows an unsynchronized peer to synchronize to
1142 * us. It would be very strange if he did and then was
1143 * nipped, but that could only happen if we were
1144 * operating at the top end of the range. It also means
1145 * we will spin an ephemeral association in response to
1146 * MODE_ACTIVE KoDs, which will time out eventually.
1148 if (hisleap != LEAP_NOTINSYNC && (hisstratum <
1149 sys_floor || hisstratum >= sys_ceiling)) {
1151 return; /* no help */
1155 * The message is correctly authenticated and allowed.
1156 * Mobilize a symmetric passive association.
1158 if ((peer = newpeer(&rbufp->recv_srcadr, NULL,
1159 rbufp->dstadr, MODE_PASSIVE, hisversion, pkt->ppoll,
1160 NTP_MAXDPOLL, 0, MDF_UCAST, 0, skeyid,
1161 sys_ident)) == NULL) {
1163 return; /* ignore duplicate */
1169 * Process regular packet. Nothing special.
1175 * Do not respond if not the same group.
1177 if (group_test(groupname, peer->ident)) {
1181 #endif /* AUTOKEY */
1185 * A passive packet matches a passive association. This is
1186 * usually the result of reconfiguring a client on the fly. As
1187 * this association might be legitimate and this packet an
1188 * attempt to deny service, just ignore it.
1195 * For everything else there is the bit bucket.
1204 * If the association is configured for Autokey, the packet must
1205 * have a public key ID; if not, the packet must have a
1208 if (is_authentic != AUTH_CRYPTO && (((peer->flags &
1209 FLAG_SKEY) && skeyid <= NTP_MAXKEY) || (!(peer->flags &
1210 FLAG_SKEY) && skeyid > NTP_MAXKEY))) {
1214 #endif /* AUTOKEY */
1216 peer->flash &= ~PKT_TEST_MASK;
1217 if (peer->flags & FLAG_XBOGUS) {
1218 peer->flags &= ~FLAG_XBOGUS;
1219 peer->flash |= TEST3;
1223 * Next comes a rigorous schedule of timestamp checking. If the
1224 * transmit timestamp is zero, the server has not initialized in
1225 * interleaved modes or is horribly broken.
1227 if (L_ISZERO(&p_xmt)) {
1228 peer->flash |= TEST3; /* unsynch */
1231 * If the transmit timestamp duplicates a previous one, the
1232 * packet is a replay. This prevents the bad guys from replaying
1233 * the most recent packet, authenticated or not.
1235 } else if (L_ISEQU(&peer->xmt, &p_xmt)) {
1236 peer->flash |= TEST1; /* duplicate */
1241 * If this is a broadcast mode packet, skip further checking. If
1242 * an initial volley, bail out now and let the client do its
1243 * stuff. If the origin timestamp is nonzero, this is an
1244 * interleaved broadcast. so restart the protocol.
1246 } else if (hismode == MODE_BROADCAST) {
1247 if (!L_ISZERO(&p_org) && !(peer->flags & FLAG_XB)) {
1248 peer->flags |= FLAG_XB;
1250 peer->borg = rbufp->recv_time;
1251 report_event(PEVNT_XLEAVE, peer, NULL);
1256 * Check for bogus packet in basic mode. If found, switch to
1257 * interleaved mode and resynchronize, but only after confirming
1258 * the packet is not bogus in symmetric interleaved mode.
1260 } else if (peer->flip == 0) {
1261 if (!L_ISEQU(&p_org, &peer->aorg)) {
1263 peer->flash |= TEST2; /* bogus */
1264 if (!L_ISZERO(&peer->dst) && L_ISEQU(&p_org,
1267 report_event(PEVNT_XLEAVE, peer, NULL);
1274 * Check for valid nonzero timestamp fields.
1276 } else if (L_ISZERO(&p_org) || L_ISZERO(&p_rec) ||
1277 L_ISZERO(&peer->dst)) {
1278 peer->flash |= TEST3; /* unsynch */
1281 * Check for bogus packet in interleaved symmetric mode. This
1282 * can happen if a packet is lost, duplicated or crossed. If
1283 * found, flip and resynchronize.
1285 } else if (!L_ISZERO(&peer->dst) && !L_ISEQU(&p_org,
1288 peer->flags |= FLAG_XBOGUS;
1289 peer->flash |= TEST2; /* bogus */
1293 * If this is a crypto_NAK, the server cannot authenticate a
1294 * client packet. The server might have just changed keys. Clear
1295 * the association and restart the protocol.
1297 if (is_authentic == AUTH_CRYPTO) {
1298 report_event(PEVNT_AUTH, peer, "crypto_NAK");
1299 peer->flash |= TEST5; /* bad auth */
1301 if (peer->flags & FLAG_PREEMPT) {
1307 peer_clear(peer, "AUTH");
1308 #endif /* AUTOKEY */
1312 * If the digest fails or it's missing for authenticated
1313 * associations, the client cannot authenticate a server
1314 * reply to a client packet previously sent. The loopback check
1315 * is designed to avoid a bait-and-switch attack, which was
1316 * possible in past versions. If symmetric modes, return a
1317 * crypto-NAK. The peer should restart the protocol.
1319 } else if (!AUTH(peer->keyid || has_mac ||
1320 (restrict_mask & RES_DONTTRUST), is_authentic)) {
1321 report_event(PEVNT_AUTH, peer, "digest");
1322 peer->flash |= TEST5; /* bad auth */
1325 (hismode == MODE_ACTIVE || hismode == MODE_PASSIVE))
1326 fast_xmit(rbufp, MODE_ACTIVE, 0, restrict_mask);
1327 if (peer->flags & FLAG_PREEMPT) {
1333 peer_clear(peer, "AUTH");
1334 #endif /* AUTOKEY */
1339 * Update the state variables.
1341 if (peer->flip == 0) {
1342 if (hismode != MODE_BROADCAST)
1344 peer->dst = rbufp->recv_time;
1349 * Set the peer ppoll to the maximum of the packet ppoll and the
1350 * peer minpoll. If a kiss-o'-death, set the peer minpoll to
1351 * this maximum and advance the headway to give the sender some
1352 * headroom. Very intricate.
1354 peer->ppoll = max(peer->minpoll, pkt->ppoll);
1355 if (hismode == MODE_SERVER && hisleap == LEAP_NOTINSYNC &&
1356 hisstratum == STRATUM_UNSPEC && memcmp(&pkt->refid,
1359 report_event(PEVNT_RATE, peer, NULL);
1360 if (pkt->ppoll > peer->minpoll)
1361 peer->minpoll = peer->ppoll;
1362 peer->burst = peer->retry = 0;
1363 peer->throttle = (NTP_SHIFT + 1) * (1 << peer->minpoll);
1364 poll_update(peer, pkt->ppoll);
1365 return; /* kiss-o'-death */
1369 * That was hard and I am sweaty, but the packet is squeaky
1370 * clean. Get on with real work.
1372 peer->timereceived = current_time;
1373 if (is_authentic == AUTH_OK)
1374 peer->flags |= FLAG_AUTHENTIC;
1376 peer->flags &= ~FLAG_AUTHENTIC;
1380 * More autokey dance. The rules of the cha-cha are as follows:
1382 * 1. If there is no key or the key is not auto, do nothing.
1384 * 2. If this packet is in response to the one just previously
1385 * sent or from a broadcast server, do the extension fields.
1386 * Otherwise, assume bogosity and bail out.
1388 * 3. If an extension field contains a verified signature, it is
1389 * self-authenticated and we sit the dance.
1391 * 4. If this is a server reply, check only to see that the
1392 * transmitted key ID matches the received key ID.
1394 * 5. Check to see that one or more hashes of the current key ID
1395 * matches the previous key ID or ultimate original key ID
1396 * obtained from the broadcaster or symmetric peer. If no
1397 * match, sit the dance and call for new autokey values.
1399 * In case of crypto error, fire the orchestra, stop dancing and
1400 * restart the protocol.
1402 if (peer->flags & FLAG_SKEY) {
1404 * Decrement remaining autokey hashes. This isn't
1405 * perfect if a packet is lost, but results in no harm.
1407 ap = (struct autokey *)peer->recval.ptr;
1412 peer->flash |= TEST8;
1413 rval = crypto_recv(peer, rbufp);
1414 if (rval == XEVNT_OK) {
1417 if (rval == XEVNT_ERR) {
1418 report_event(PEVNT_RESTART, peer,
1420 peer_clear(peer, "CRYP");
1421 peer->flash |= TEST9; /* bad crypt */
1422 if (peer->flags & FLAG_PREEMPT)
1429 * If server mode, verify the receive key ID matches
1430 * the transmit key ID.
1432 if (hismode == MODE_SERVER) {
1433 if (skeyid == peer->keyid)
1434 peer->flash &= ~TEST8;
1437 * If an extension field is present, verify only that it
1438 * has been correctly signed. We don't need a sequence
1439 * check here, but the sequence continues.
1441 } else if (!(peer->flash & TEST8)) {
1442 peer->pkeyid = skeyid;
1445 * Now the fun part. Here, skeyid is the current ID in
1446 * the packet, pkeyid is the ID in the last packet and
1447 * tkeyid is the hash of skeyid. If the autokey values
1448 * have not been received, this is an automatic error.
1449 * If so, check that the tkeyid matches pkeyid. If not,
1450 * hash tkeyid and try again. If the number of hashes
1451 * exceeds the number remaining in the sequence, declare
1452 * a successful failure and refresh the autokey values.
1454 } else if (ap != NULL) {
1457 for (i = 0; ; i++) {
1458 if (tkeyid == peer->pkeyid ||
1459 tkeyid == ap->key) {
1460 peer->flash &= ~TEST8;
1461 peer->pkeyid = skeyid;
1470 tkeyid = session_key(
1471 &rbufp->recv_srcadr, dstadr_sin,
1474 if (peer->flash & TEST8)
1475 report_event(PEVNT_AUTH, peer, "keylist");
1477 if (!(peer->crypto & CRYPTO_FLAG_PROV)) /* test 9 */
1478 peer->flash |= TEST8; /* bad autokey */
1481 * The maximum lifetime of the protocol is about one
1482 * week before restarting the Autokey protocol to
1483 * refresh certificates and leapseconds values.
1485 if (current_time > peer->refresh) {
1486 report_event(PEVNT_RESTART, peer,
1488 peer_clear(peer, "TIME");
1492 #endif /* AUTOKEY */
1495 * The dance is complete and the flash bits have been lit. Toss
1496 * the packet over the fence for processing, which may light up
1499 process_packet(peer, pkt, rbufp->recv_length);
1502 * In interleaved mode update the state variables. Also adjust the
1503 * transmit phase to avoid crossover.
1505 if (peer->flip != 0) {
1507 peer->dst = rbufp->recv_time;
1508 if (peer->nextdate - current_time < (1U << min(peer->ppoll,
1518 * process_packet - Packet Procedure, a la Section 3.4.4 of the
1519 * specification. Or almost, at least. If we're in here we have a
1520 * reasonable expectation that we will be having a long term
1521 * relationship with this host.
1525 register struct peer *peer,
1526 register struct pkt *pkt,
1531 double p_offset, p_del, p_disp;
1532 l_fp p_rec, p_xmt, p_org, p_reftime, ci;
1533 u_char pmode, pleap, pversion, pstratum;
1534 char statstr[NTP_MAXSTRLEN];
1537 double etemp, ftemp, td;
1542 p_del = FPTOD(NTOHS_FP(pkt->rootdelay));
1544 p_disp = FPTOD(NTOHS_FP(pkt->rootdisp));
1545 NTOHL_FP(&pkt->reftime, &p_reftime);
1546 NTOHL_FP(&pkt->org, &p_org);
1547 NTOHL_FP(&pkt->rec, &p_rec);
1548 NTOHL_FP(&pkt->xmt, &p_xmt);
1549 pmode = PKT_MODE(pkt->li_vn_mode);
1550 pleap = PKT_LEAP(pkt->li_vn_mode);
1551 pversion = PKT_VERSION(pkt->li_vn_mode);
1552 pstratum = PKT_TO_STRATUM(pkt->stratum);
1555 * Capture the header values in the client/peer association..
1557 record_raw_stats(&peer->srcadr, peer->dstadr ?
1558 &peer->dstadr->sin : NULL,
1559 &p_org, &p_rec, &p_xmt, &peer->dst,
1560 pleap, pversion, pmode, pstratum, pkt->ppoll, pkt->precision,
1561 p_del, p_disp, pkt->refid);
1563 peer->stratum = min(pstratum, STRATUM_UNSPEC);
1564 peer->pmode = pmode;
1565 peer->precision = pkt->precision;
1566 peer->rootdelay = p_del;
1567 peer->rootdisp = p_disp;
1568 peer->refid = pkt->refid; /* network byte order */
1569 peer->reftime = p_reftime;
1572 * First, if either burst mode is armed, enable the burst.
1573 * Compute the headway for the next packet and delay if
1574 * necessary to avoid exceeding the threshold.
1576 if (peer->retry > 0) {
1579 peer->burst = min(1 << (peer->hpoll -
1580 peer->minpoll), NTP_SHIFT) - 1;
1582 peer->burst = NTP_IBURST - 1;
1583 if (peer->burst > 0)
1584 peer->nextdate = current_time;
1586 poll_update(peer, peer->hpoll);
1589 * Verify the server is synchronized; that is, the leap bits,
1590 * stratum and root distance are valid.
1592 if (pleap == LEAP_NOTINSYNC || /* test 6 */
1593 pstratum < sys_floor || pstratum >= sys_ceiling)
1594 peer->flash |= TEST6; /* bad synch or strat */
1595 if (p_del / 2 + p_disp >= MAXDISPERSE) /* test 7 */
1596 peer->flash |= TEST7; /* bad header */
1599 * If any tests fail at this point, the packet is discarded.
1600 * Note that some flashers may have already been set in the
1601 * receive() routine.
1603 if (peer->flash & PKT_TEST_MASK) {
1604 peer->seldisptoolarge++;
1607 printf("packet: flash header %04x\n",
1614 * If the peer was previously unreachable, raise a trap. In any
1615 * case, mark it reachable.
1618 report_event(PEVNT_REACH, peer, NULL);
1619 peer->timereachable = current_time;
1624 * For a client/server association, calculate the clock offset,
1625 * roundtrip delay and dispersion. The equations are reordered
1626 * from the spec for more efficient use of temporaries. For a
1627 * broadcast association, offset the last measurement by the
1628 * computed delay during the client/server volley. Note the
1629 * computation of dispersion includes the system precision plus
1630 * that due to the frequency error since the origin time.
1632 * It is very important to respect the hazards of overflow. The
1633 * only permitted operation on raw timestamps is subtraction,
1634 * where the result is a signed quantity spanning from 68 years
1635 * in the past to 68 years in the future. To avoid loss of
1636 * precision, these calculations are done using 64-bit integer
1637 * arithmetic. However, the offset and delay calculations are
1638 * sums and differences of these first-order differences, which
1639 * if done using 64-bit integer arithmetic, would be valid over
1640 * only half that span. Since the typical first-order
1641 * differences are usually very small, they are converted to 64-
1642 * bit doubles and all remaining calculations done in floating-
1643 * double arithmetic. This preserves the accuracy while
1644 * retaining the 68-year span.
1646 * There are three interleaving schemes, basic, interleaved
1647 * symmetric and interleaved broadcast. The timestamps are
1648 * idioscyncratically different. See the onwire briefing/white
1649 * paper at www.eecis.udel.edu/~mills for details.
1651 * Interleaved symmetric mode
1652 * t1 = peer->aorg/borg, t2 = peer->rec, t3 = p_xmt,
1655 if (peer->flip != 0) {
1656 ci = p_xmt; /* t3 - t4 */
1657 L_SUB(&ci, &peer->dst);
1659 ci = p_rec; /* t2 - t1 */
1661 L_SUB(&ci, &peer->borg);
1663 L_SUB(&ci, &peer->aorg);
1666 p_offset = (t21 + t34) / 2.;
1667 if (p_del < 0 || p_del > 1.) {
1668 snprintf(statstr, sizeof(statstr),
1669 "t21 %.6f t34 %.6f", t21, t34);
1670 report_event(PEVNT_XERR, peer, statstr);
1677 } else if (peer->pmode == MODE_BROADCAST) {
1680 * Interleaved broadcast mode. Use interleaved timestamps.
1681 * t1 = peer->borg, t2 = p_org, t3 = p_org, t4 = aorg
1683 if (peer->flags & FLAG_XB) {
1684 ci = p_org; /* delay */
1685 L_SUB(&ci, &peer->aorg);
1687 ci = p_org; /* t2 - t1 */
1688 L_SUB(&ci, &peer->borg);
1691 peer->borg = peer->dst;
1692 if (t34 < 0 || t34 > 1.) {
1693 snprintf(statstr, sizeof(statstr),
1694 "offset %.6f delay %.6f", t21, t34);
1695 report_event(PEVNT_XERR, peer, statstr);
1702 * Basic broadcast - use direct timestamps.
1703 * t3 = p_xmt, t4 = peer->dst
1706 ci = p_xmt; /* t3 - t4 */
1707 L_SUB(&ci, &peer->dst);
1713 * When calibration is complete and the clock is
1714 * synchronized, the bias is calculated as the difference
1715 * between the unicast timestamp and the broadcast
1716 * timestamp. This works for both basic and interleaved
1719 if (FLAG_BC_VOL & peer->flags) {
1720 peer->flags &= ~FLAG_BC_VOL;
1721 peer->delay = fabs(peer->offset - p_offset) * 2;
1723 p_del = peer->delay;
1724 p_offset += p_del / 2;
1728 * Basic mode, otherwise known as the old fashioned way.
1730 * t1 = p_org, t2 = p_rec, t3 = p_xmt, t4 = peer->dst
1733 ci = p_xmt; /* t3 - t4 */
1734 L_SUB(&ci, &peer->dst);
1736 ci = p_rec; /* t2 - t1 */
1739 p_del = fabs(t21 - t34);
1740 p_offset = (t21 + t34) / 2.;
1742 p_del = max(p_del, LOGTOD(sys_precision));
1743 p_disp = LOGTOD(sys_precision) + LOGTOD(peer->precision) +
1748 * This code calculates the outbound and inbound data rates by
1749 * measuring the differences between timestamps at different
1750 * packet lengths. This is helpful in cases of large asymmetric
1751 * delays commonly experienced on deep space communication
1754 if (peer->t21_last > 0 && peer->t34_bytes > 0) {
1755 itemp = peer->t21_bytes - peer->t21_last;
1757 etemp = t21 - peer->t21;
1758 if (fabs(etemp) > 1e-6) {
1759 ftemp = itemp / etemp;
1764 itemp = len - peer->t34_bytes;
1766 etemp = -t34 - peer->t34;
1767 if (fabs(etemp) > 1e-6) {
1768 ftemp = itemp / etemp;
1776 * The following section compensates for different data rates on
1777 * the outbound (d21) and inbound (t34) directions. To do this,
1778 * it finds t such that r21 * t - r34 * (d - t) = 0, where d is
1779 * the roundtrip delay. Then it calculates the correction as a
1783 peer->t21_last = peer->t21_bytes;
1785 peer->t34_bytes = len;
1788 printf("packet: t21 %.9lf %d t34 %.9lf %d\n", peer->t21,
1789 peer->t21_bytes, peer->t34, peer->t34_bytes);
1791 if (peer->r21 > 0 && peer->r34 > 0 && p_del > 0) {
1792 if (peer->pmode != MODE_BROADCAST)
1793 td = (peer->r34 / (peer->r21 + peer->r34) -
1799 * Unfortunately, in many cases the errors are
1800 * unacceptable, so for the present the rates are not
1801 * used. In future, we might find conditions where the
1802 * calculations are useful, so this should be considered
1803 * a work in progress.
1809 printf("packet: del %.6lf r21 %.1lf r34 %.1lf %.6lf\n",
1810 p_del, peer->r21 / 1e3, peer->r34 / 1e3,
1817 * That was awesome. Now hand off to the clock filter.
1819 clock_filter(peer, p_offset + peer->bias, p_del, p_disp);
1822 * If we are in broadcast calibrate mode, return to broadcast
1823 * client mode when the client is fit and the autokey dance is
1826 if ((FLAG_BC_VOL & peer->flags) && MODE_CLIENT == peer->hmode &&
1827 !(TEST11 & peer_unfit(peer))) { /* distance exceeded */
1829 if (peer->flags & FLAG_SKEY) {
1830 if (!(~peer->crypto & CRYPTO_FLAG_ALL))
1831 peer->hmode = MODE_BCLIENT;
1833 peer->hmode = MODE_BCLIENT;
1835 #else /* !AUTOKEY follows */
1836 peer->hmode = MODE_BCLIENT;
1837 #endif /* !AUTOKEY */
1843 * clock_update - Called at system process update intervals.
1847 struct peer *peer /* peer structure pointer */
1852 #ifdef HAVE_LIBSCF_H
1854 #endif /* HAVE_LIBSCF_H */
1857 * Update the system state variables. We do this very carefully,
1858 * as the poll interval might need to be clamped differently.
1861 sys_epoch = peer->epoch;
1862 if (sys_poll < peer->minpoll)
1863 sys_poll = peer->minpoll;
1864 if (sys_poll > peer->maxpoll)
1865 sys_poll = peer->maxpoll;
1866 poll_update(peer, sys_poll);
1867 sys_stratum = min(peer->stratum + 1, STRATUM_UNSPEC);
1868 if (peer->stratum == STRATUM_REFCLOCK ||
1869 peer->stratum == STRATUM_UNSPEC)
1870 sys_refid = peer->refid;
1872 sys_refid = addr2refid(&peer->srcadr);
1874 * Root Dispersion (E) is defined (in RFC 5905) as:
1876 * E = p.epsilon_r + p.epsilon + p.psi + PHI*(s.t - p.t) + |THETA|
1879 * p.epsilon_r is the PollProc's root dispersion
1880 * p.epsilon is the PollProc's dispersion
1881 * p.psi is the PollProc's jitter
1882 * THETA is the combined offset
1884 * NB: Think Hard about where these numbers come from and
1885 * what they mean. When did peer->update happen? Has anything
1886 * interesting happened since then? What values are the most
1889 * DLM thinks this equation is probably the best of all worse choices.
1891 dtemp = peer->rootdisp
1894 + clock_phi * (current_time - peer->update)
1897 if (dtemp > sys_mindisp)
1898 sys_rootdisp = dtemp;
1900 sys_rootdisp = sys_mindisp;
1901 sys_rootdelay = peer->delay + peer->rootdelay;
1902 sys_reftime = peer->dst;
1907 "clock_update: at %lu sample %lu associd %d\n",
1908 current_time, peer->epoch, peer->associd);
1912 * Comes now the moment of truth. Crank the clock discipline and
1913 * see what comes out.
1915 switch (local_clock(peer, sys_offset)) {
1918 * Clock exceeds panic threshold. Life as we know it ends.
1921 #ifdef HAVE_LIBSCF_H
1923 * For Solaris enter the maintenance mode.
1925 if ((fmri = getenv("SMF_FMRI")) != NULL) {
1926 if (smf_maintain_instance(fmri, 0) < 0) {
1927 printf("smf_maintain_instance: %s\n",
1928 scf_strerror(scf_error()));
1932 * Sleep until SMF kills us.
1937 #endif /* HAVE_LIBSCF_H */
1942 * Clock was stepped. Flush all time values of all peers.
1946 set_sys_leap(LEAP_NOTINSYNC);
1947 sys_stratum = STRATUM_UNSPEC;
1948 memcpy(&sys_refid, "STEP", 4);
1951 L_CLR(&sys_reftime);
1952 sys_jitter = LOGTOD(sys_precision);
1953 leapsec_reset_frame();
1957 * Clock was slewed. Handle the leapsecond stuff.
1962 * If this is the first time the clock is set, reset the
1963 * leap bits. If crypto, the timer will goose the setup
1966 if (sys_leap == LEAP_NOTINSYNC) {
1967 set_sys_leap(LEAP_NOWARNING);
1971 #endif /* AUTOKEY */
1973 * If our parent process is waiting for the
1974 * first clock sync, send them home satisfied.
1976 #ifdef HAVE_WORKING_FORK
1977 if (waitsync_fd_to_close != -1) {
1978 close(waitsync_fd_to_close);
1979 waitsync_fd_to_close = -1;
1980 DPRINTF(1, ("notified parent --wait-sync is done\n"));
1982 #endif /* HAVE_WORKING_FORK */
1987 * If there is no leap second pending and the number of
1988 * survivor leap bits is greater than half the number of
1989 * survivors, try to schedule a leap for the end of the
1990 * current month. (This only works if no leap second for
1991 * that range is in the table, so doing this more than
1992 * once is mostly harmless.)
1994 if (leapsec == LSPROX_NOWARN) {
1995 if (leap_vote_ins > leap_vote_del
1996 && leap_vote_ins > sys_survivors / 2) {
1998 leapsec_add_dyn(TRUE, now.l_ui, NULL);
2000 if (leap_vote_del > leap_vote_ins
2001 && leap_vote_del > sys_survivors / 2) {
2003 leapsec_add_dyn(FALSE, now.l_ui, NULL);
2009 * Popcorn spike or step threshold exceeded. Pretend it never
2019 * poll_update - update peer poll interval
2023 struct peer *peer, /* peer structure pointer */
2031 * This routine figures out when the next poll should be sent.
2032 * That turns out to be wickedly complicated. One problem is
2033 * that sometimes the time for the next poll is in the past when
2034 * the poll interval is reduced. We watch out for races here
2035 * between the receive process and the poll process.
2037 * Clamp the poll interval between minpoll and maxpoll.
2039 hpoll = max(min(peer->maxpoll, mpoll), peer->minpoll);
2043 * If during the crypto protocol the poll interval has changed,
2044 * the lifetimes in the key list are probably bogus. Purge the
2045 * the key list and regenerate it later.
2047 if ((peer->flags & FLAG_SKEY) && hpoll != peer->hpoll)
2049 #endif /* AUTOKEY */
2050 peer->hpoll = hpoll;
2053 * There are three variables important for poll scheduling, the
2054 * current time (current_time), next scheduled time (nextdate)
2055 * and the earliest time (utemp). The earliest time is 2 s
2056 * seconds, but could be more due to rate management. When
2057 * sending in a burst, use the earliest time. When not in a
2058 * burst but with a reply pending, send at the earliest time
2059 * unless the next scheduled time has not advanced. This can
2060 * only happen if multiple replies are pending in the same
2061 * response interval. Otherwise, send at the later of the next
2062 * scheduled time and the earliest time.
2064 * Now we figure out if there is an override. If a burst is in
2065 * progress and we get called from the receive process, just
2066 * slink away. If called from the poll process, delay 1 s for a
2067 * reference clock, otherwise 2 s.
2069 utemp = current_time + max(peer->throttle - (NTP_SHIFT - 1) *
2070 (1 << peer->minpoll), ntp_minpkt);
2071 if (peer->burst > 0) {
2072 if (peer->nextdate > current_time)
2075 else if (peer->flags & FLAG_REFCLOCK)
2076 peer->nextdate = current_time + RESP_DELAY;
2077 #endif /* REFCLOCK */
2079 peer->nextdate = utemp;
2083 * If a burst is not in progress and a crypto response message
2084 * is pending, delay 2 s, but only if this is a new interval.
2086 } else if (peer->cmmd != NULL) {
2087 if (peer->nextdate > current_time) {
2088 if (peer->nextdate + ntp_minpkt != utemp)
2089 peer->nextdate = utemp;
2091 peer->nextdate = utemp;
2093 #endif /* AUTOKEY */
2096 * The ordinary case. If a retry, use minpoll; if unreachable,
2097 * use host poll; otherwise, use the minimum of host and peer
2098 * polls; In other words, oversampling is okay but
2099 * understampling is evil. Use the maximum of this value and the
2100 * headway. If the average headway is greater than the headway
2101 * threshold, increase the headway by the minimum interval.
2104 if (peer->retry > 0)
2105 hpoll = peer->minpoll;
2106 else if (!(peer->reach))
2107 hpoll = peer->hpoll;
2109 hpoll = min(peer->ppoll, peer->hpoll);
2111 if (peer->flags & FLAG_REFCLOCK)
2114 #endif /* REFCLOCK */
2115 next = ((0x1000UL | (ntp_random() & 0x0ff)) <<
2117 next += peer->outdate;
2119 peer->nextdate = next;
2121 peer->nextdate = utemp;
2122 if (peer->throttle > (1 << peer->minpoll))
2123 peer->nextdate += ntp_minpkt;
2125 DPRINTF(2, ("poll_update: at %lu %s poll %d burst %d retry %d head %d early %lu next %lu\n",
2126 current_time, ntoa(&peer->srcadr), peer->hpoll,
2127 peer->burst, peer->retry, peer->throttle,
2128 utemp - current_time, peer->nextdate -
2134 * peer_clear - clear peer filter registers. See Section 3.4.8 of the
2139 struct peer *peer, /* peer structure */
2140 const char *ident /* tally lights */
2147 * If cryptographic credentials have been acquired, toss them to
2148 * Valhalla. Note that autokeys are ephemeral, in that they are
2149 * tossed immediately upon use. Therefore, the keylist can be
2150 * purged anytime without needing to preserve random keys. Note
2151 * that, if the peer is purged, the cryptographic variables are
2152 * purged, too. This makes it much harder to sneak in some
2153 * unauthenticated data in the clock filter.
2156 if (peer->iffval != NULL)
2157 BN_free(peer->iffval);
2158 value_free(&peer->cookval);
2159 value_free(&peer->recval);
2160 value_free(&peer->encrypt);
2161 value_free(&peer->sndval);
2162 if (peer->cmmd != NULL)
2164 if (peer->subject != NULL)
2165 free(peer->subject);
2166 if (peer->issuer != NULL)
2168 #endif /* AUTOKEY */
2171 * Clear all values, including the optional crypto values above.
2173 memset(CLEAR_TO_ZERO(peer), 0, LEN_CLEAR_TO_ZERO(peer));
2174 peer->ppoll = peer->maxpoll;
2175 peer->hpoll = peer->minpoll;
2176 peer->disp = MAXDISPERSE;
2177 peer->flash = peer_unfit(peer);
2178 peer->jitter = LOGTOD(sys_precision);
2181 * If interleave mode, initialize the alternate origin switch.
2183 if (peer->flags & FLAG_XLEAVE)
2185 for (u = 0; u < NTP_SHIFT; u++) {
2186 peer->filter_order[u] = u;
2187 peer->filter_disp[u] = MAXDISPERSE;
2190 if (!(peer->flags & FLAG_REFCLOCK)) {
2192 peer->leap = LEAP_NOTINSYNC;
2193 peer->stratum = STRATUM_UNSPEC;
2194 memcpy(&peer->refid, ident, 4);
2200 * During initialization use the association count to spread out
2201 * the polls at one-second intervals. Passive associations'
2202 * first poll is delayed by the "discard minimum" to avoid rate
2203 * limiting. Other post-startup new or cleared associations
2204 * randomize the first poll over the minimum poll interval to
2207 peer->nextdate = peer->update = peer->outdate = current_time;
2209 peer->nextdate += peer_associations;
2210 } else if (MODE_PASSIVE == peer->hmode) {
2211 peer->nextdate += ntp_minpkt;
2213 peer->nextdate += ntp_random() % peer->minpoll;
2216 peer->refresh = current_time + (1 << NTP_REFRESH);
2217 #endif /* AUTOKEY */
2221 "peer_clear: at %ld next %ld associd %d refid %s\n",
2222 current_time, peer->nextdate, peer->associd,
2229 * clock_filter - add incoming clock sample to filter register and run
2230 * the filter procedure to find the best sample.
2234 struct peer *peer, /* peer structure pointer */
2235 double sample_offset, /* clock offset */
2236 double sample_delay, /* roundtrip delay */
2237 double sample_disp /* dispersion */
2240 double dst[NTP_SHIFT]; /* distance vector */
2241 int ord[NTP_SHIFT]; /* index vector */
2243 double dtemp, etemp;
2247 * A sample consists of the offset, delay, dispersion and epoch
2248 * of arrival. The offset and delay are determined by the on-
2249 * wire protocol. The dispersion grows from the last outbound
2250 * packet to the arrival of this one increased by the sum of the
2251 * peer precision and the system precision as required by the
2252 * error budget. First, shift the new arrival into the shift
2253 * register discarding the oldest one.
2255 j = peer->filter_nextpt;
2256 peer->filter_offset[j] = sample_offset;
2257 peer->filter_delay[j] = sample_delay;
2258 peer->filter_disp[j] = sample_disp;
2259 peer->filter_epoch[j] = current_time;
2260 j = (j + 1) % NTP_SHIFT;
2261 peer->filter_nextpt = j;
2264 * Update dispersions since the last update and at the same
2265 * time initialize the distance and index lists. Since samples
2266 * become increasingly uncorrelated beyond the Allan intercept,
2267 * only under exceptional cases will an older sample be used.
2268 * Therefore, the distance list uses a compound metric. If the
2269 * dispersion is greater than the maximum dispersion, clamp the
2270 * distance at that value. If the time since the last update is
2271 * less than the Allan intercept use the delay; otherwise, use
2272 * the sum of the delay and dispersion.
2274 dtemp = clock_phi * (current_time - peer->update);
2275 peer->update = current_time;
2276 for (i = NTP_SHIFT - 1; i >= 0; i--) {
2278 peer->filter_disp[j] += dtemp;
2279 if (peer->filter_disp[j] >= MAXDISPERSE) {
2280 peer->filter_disp[j] = MAXDISPERSE;
2281 dst[i] = MAXDISPERSE;
2282 } else if (peer->update - peer->filter_epoch[j] >
2283 (u_long)ULOGTOD(allan_xpt)) {
2284 dst[i] = peer->filter_delay[j] +
2285 peer->filter_disp[j];
2287 dst[i] = peer->filter_delay[j];
2290 j = (j + 1) % NTP_SHIFT;
2294 * If the clock has stabilized, sort the samples by distance.
2296 if (freq_cnt == 0) {
2297 for (i = 1; i < NTP_SHIFT; i++) {
2298 for (j = 0; j < i; j++) {
2299 if (dst[j] > dst[i]) {
2312 * Copy the index list to the association structure so ntpq
2313 * can see it later. Prune the distance list to leave only
2314 * samples less than the maximum dispersion, which disfavors
2315 * uncorrelated samples older than the Allan intercept. To
2316 * further improve the jitter estimate, of the remainder leave
2317 * only samples less than the maximum distance, but keep at
2318 * least two samples for jitter calculation.
2321 for (i = 0; i < NTP_SHIFT; i++) {
2322 peer->filter_order[i] = (u_char) ord[i];
2323 if (dst[i] >= MAXDISPERSE || (m >= 2 && dst[i] >=
2330 * Compute the dispersion and jitter. The dispersion is weighted
2331 * exponentially by NTP_FWEIGHT (0.5) so it is normalized close
2332 * to 1.0. The jitter is the RMS differences relative to the
2333 * lowest delay sample.
2335 peer->disp = peer->jitter = 0;
2337 for (i = NTP_SHIFT - 1; i >= 0; i--) {
2339 peer->disp = NTP_FWEIGHT * (peer->disp +
2340 peer->filter_disp[j]);
2342 peer->jitter += DIFF(peer->filter_offset[j],
2343 peer->filter_offset[k]);
2347 * If no acceptable samples remain in the shift register,
2348 * quietly tiptoe home leaving only the dispersion. Otherwise,
2349 * save the offset, delay and jitter. Note the jitter must not
2350 * be less than the precision.
2356 etemp = fabs(peer->offset - peer->filter_offset[k]);
2357 peer->offset = peer->filter_offset[k];
2358 peer->delay = peer->filter_delay[k];
2360 peer->jitter /= m - 1;
2361 peer->jitter = max(SQRT(peer->jitter), LOGTOD(sys_precision));
2364 * If the the new sample and the current sample are both valid
2365 * and the difference between their offsets exceeds CLOCK_SGATE
2366 * (3) times the jitter and the interval between them is less
2367 * than twice the host poll interval, consider the new sample
2368 * a popcorn spike and ignore it.
2370 if (peer->disp < sys_maxdist && peer->filter_disp[k] <
2371 sys_maxdist && etemp > CLOCK_SGATE * peer->jitter &&
2372 peer->filter_epoch[k] - peer->epoch < 2. *
2373 ULOGTOD(peer->hpoll)) {
2374 snprintf(tbuf, sizeof(tbuf), "%.6f s", etemp);
2375 report_event(PEVNT_POPCORN, peer, tbuf);
2380 * A new minimum sample is useful only if it is later than the
2381 * last one used. In this design the maximum lifetime of any
2382 * sample is not greater than eight times the poll interval, so
2383 * the maximum interval between minimum samples is eight
2386 if (peer->filter_epoch[k] <= peer->epoch) {
2389 printf("clock_filter: old sample %lu\n", current_time -
2390 peer->filter_epoch[k]);
2394 peer->epoch = peer->filter_epoch[k];
2397 * The mitigated sample statistics are saved for later
2398 * processing. If not synchronized or not in a burst, tickle the
2399 * clock select algorithm.
2401 record_peer_stats(&peer->srcadr, ctlpeerstatus(peer),
2402 peer->offset, peer->delay, peer->disp, peer->jitter);
2406 "clock_filter: n %d off %.6f del %.6f dsp %.6f jit %.6f\n",
2407 m, peer->offset, peer->delay, peer->disp,
2410 if (peer->burst == 0 || sys_leap == LEAP_NOTINSYNC)
2416 * clock_select - find the pick-of-the-litter clock
2418 * LOCKCLOCK: (1) If the local clock is the prefer peer, it will always
2419 * be enabled, even if declared falseticker, (2) only the prefer peer
2420 * can be selected as the system peer, (3) if the external source is
2421 * down, the system leap bits are set to 11 and the stratum set to
2435 double orphmet = 2.0 * U_INT32_MAX; /* 2x is greater than */
2436 struct endpoint endp;
2437 struct peer *osys_peer;
2438 struct peer *sys_prefer = NULL; /* prefer peer */
2439 struct peer *typesystem = NULL;
2440 struct peer *typeorphan = NULL;
2442 struct peer *typeacts = NULL;
2443 struct peer *typelocal = NULL;
2444 struct peer *typepps = NULL;
2445 #endif /* REFCLOCK */
2446 static struct endpoint *endpoint = NULL;
2447 static int *indx = NULL;
2448 static peer_select *peers = NULL;
2449 static u_int endpoint_size = 0;
2450 static u_int peers_size = 0;
2451 static u_int indx_size = 0;
2455 * Initialize and create endpoint, index and peer lists big
2456 * enough to handle all associations.
2458 osys_peer = sys_peer;
2461 set_sys_leap(LEAP_NOTINSYNC);
2462 sys_stratum = STRATUM_UNSPEC;
2463 memcpy(&sys_refid, "DOWN", 4);
2464 #endif /* LOCKCLOCK */
2467 * Allocate dynamic space depending on the number of
2471 for (peer = peer_list; peer != NULL; peer = peer->p_link)
2473 endpoint_size = ALIGNED_SIZE(nlist * 2 * sizeof(*endpoint));
2474 peers_size = ALIGNED_SIZE(nlist * sizeof(*peers));
2475 indx_size = ALIGNED_SIZE(nlist * 2 * sizeof(*indx));
2476 octets = endpoint_size + peers_size + indx_size;
2477 endpoint = erealloc(endpoint, octets);
2478 peers = INC_ALIGNED_PTR(endpoint, endpoint_size);
2479 indx = INC_ALIGNED_PTR(peers, peers_size);
2482 * Initially, we populate the island with all the rifraff peers
2483 * that happen to be lying around. Those with seriously
2484 * defective clocks are immediately booted off the island. Then,
2485 * the falsetickers are culled and put to sea. The truechimers
2486 * remaining are subject to repeated rounds where the most
2487 * unpopular at each round is kicked off. When the population
2488 * has dwindled to sys_minclock, the survivors split a million
2489 * bucks and collectively crank the chimes.
2491 nlist = nl2 = 0; /* none yet */
2492 for (peer = peer_list; peer != NULL; peer = peer->p_link) {
2493 peer->new_status = CTL_PST_SEL_REJECT;
2496 * Leave the island immediately if the peer is
2497 * unfit to synchronize.
2499 if (peer_unfit(peer))
2503 * If this peer is an orphan parent, elect the
2504 * one with the lowest metric defined as the
2505 * IPv4 address or the first 64 bits of the
2506 * hashed IPv6 address. To ensure convergence
2507 * on the same selected orphan, consider as
2508 * well that this system may have the lowest
2509 * metric and be the orphan parent. If this
2510 * system wins, sys_peer will be NULL to trigger
2511 * orphan mode in timer().
2513 if (peer->stratum == sys_orphan) {
2517 if (peer->dstadr != NULL)
2518 localmet = ntohl(peer->dstadr->addr_refid);
2520 localmet = U_INT32_MAX;
2521 peermet = ntohl(addr2refid(&peer->srcadr));
2522 if (peermet < localmet && peermet < orphmet) {
2530 * If this peer could have the orphan parent
2531 * as a synchronization ancestor, exclude it
2532 * from selection to avoid forming a
2533 * synchronization loop within the orphan mesh,
2534 * triggering stratum climb to infinity
2535 * instability. Peers at stratum higher than
2536 * the orphan stratum could have the orphan
2537 * parent in ancestry so are excluded.
2538 * See http://bugs.ntp.org/2050
2540 if (peer->stratum > sys_orphan)
2544 * The following are special cases. We deal
2547 if (!(peer->flags & FLAG_PREFER)) {
2548 switch (peer->refclktype) {
2549 case REFCLK_LOCALCLOCK:
2550 if (current_time > orphwait &&
2556 if (current_time > orphwait &&
2562 #endif /* REFCLOCK */
2565 * If we get this far, the peer can stay on the
2566 * island, but does not yet have the immunity
2569 peer->new_status = CTL_PST_SEL_SANE;
2570 f = root_distance(peer);
2571 peers[nlist].peer = peer;
2572 peers[nlist].error = peer->jitter;
2573 peers[nlist].synch = f;
2577 * Insert each interval endpoint on the unsorted
2581 endpoint[nl2].type = -1; /* lower end */
2582 endpoint[nl2].val = e - f;
2584 endpoint[nl2].type = 1; /* upper end */
2585 endpoint[nl2].val = e + f;
2589 * Construct sorted indx[] of endpoint[] indexes ordered by
2592 for (i = 0; i < nl2; i++)
2594 for (i = 0; i < nl2; i++) {
2595 endp = endpoint[indx[i]];
2598 for (j = i + 1; j < nl2; j++) {
2599 endp = endpoint[indx[j]];
2611 for (i = 0; i < nl2; i++)
2612 DPRINTF(3, ("select: endpoint %2d %.6f\n",
2613 endpoint[indx[i]].type, endpoint[indx[i]].val));
2616 * This is the actual algorithm that cleaves the truechimers
2617 * from the falsetickers. The original algorithm was described
2618 * in Keith Marzullo's dissertation, but has been modified for
2621 * Briefly put, we first assume there are no falsetickers, then
2622 * scan the candidate list first from the low end upwards and
2623 * then from the high end downwards. The scans stop when the
2624 * number of intersections equals the number of candidates less
2625 * the number of falsetickers. If this doesn't happen for a
2626 * given number of falsetickers, we bump the number of
2627 * falsetickers and try again. If the number of falsetickers
2628 * becomes equal to or greater than half the number of
2629 * candidates, the Albanians have won the Byzantine wars and
2630 * correct synchronization is not possible.
2632 * Here, nlist is the number of candidates and allow is the
2633 * number of falsetickers. Upon exit, the truechimers are the
2634 * survivors with offsets not less than low and not greater than
2635 * high. There may be none of them.
2639 for (allow = 0; 2 * allow < nlist; allow++) {
2642 * Bound the interval (low, high) as the smallest
2643 * interval containing points from the most sources.
2646 for (i = 0; i < nl2; i++) {
2647 low = endpoint[indx[i]].val;
2648 n -= endpoint[indx[i]].type;
2649 if (n >= nlist - allow)
2653 for (j = nl2 - 1; j >= 0; j--) {
2654 high = endpoint[indx[j]].val;
2655 n += endpoint[indx[j]].type;
2656 if (n >= nlist - allow)
2661 * If an interval containing truechimers is found, stop.
2662 * If not, increase the number of falsetickers and go
2670 * Clustering algorithm. Whittle candidate list of falsetickers,
2671 * who leave the island immediately. The TRUE peer is always a
2672 * truechimer. We must leave at least one peer to collect the
2675 * We assert the correct time is contained in the interval, but
2676 * the best offset estimate for the interval might not be
2677 * contained in the interval. For this purpose, a truechimer is
2678 * defined as the midpoint of an interval that overlaps the
2679 * intersection interval.
2682 for (i = 0; i < nlist; i++) {
2685 peer = peers[i].peer;
2687 if ((high <= low || peer->offset + h < low ||
2688 peer->offset - h > high) && !(peer->flags & FLAG_TRUE))
2693 * Eligible PPS peers must survive the intersection
2694 * algorithm. Use the first one found, but don't
2695 * include any of them in the cluster population.
2697 if (peer->flags & FLAG_PPS) {
2698 if (typepps == NULL)
2700 if (!(peer->flags & FLAG_TSTAMP_PPS))
2703 #endif /* REFCLOCK */
2706 peers[j] = peers[i];
2712 * If no survivors remain at this point, check if the modem
2713 * driver, local driver or orphan parent in that order. If so,
2714 * nominate the first one found as the only survivor.
2715 * Otherwise, give up and leave the island to the rats.
2719 peers[0].synch = sys_mindisp;
2721 if (typeacts != NULL) {
2722 peers[0].peer = typeacts;
2724 } else if (typelocal != NULL) {
2725 peers[0].peer = typelocal;
2728 #endif /* REFCLOCK */
2729 if (typeorphan != NULL) {
2730 peers[0].peer = typeorphan;
2736 * Mark the candidates at this point as truechimers.
2738 for (i = 0; i < nlist; i++) {
2739 peers[i].peer->new_status = CTL_PST_SEL_SELCAND;
2740 DPRINTF(2, ("select: survivor %s %f\n",
2741 stoa(&peers[i].peer->srcadr), peers[i].synch));
2745 * Now, vote outlyers off the island by select jitter weighted
2746 * by root distance. Continue voting as long as there are more
2747 * than sys_minclock survivors and the select jitter of the peer
2748 * with the worst metric is greater than the minimum peer
2749 * jitter. Stop if we are about to discard a TRUE or PREFER
2750 * peer, who of course have the immunity idol.
2757 for (i = 0; i < nlist; i++) {
2758 if (peers[i].error < d)
2760 peers[i].seljit = 0;
2763 for (j = 0; j < nlist; j++)
2764 f += DIFF(peers[j].peer->offset,
2765 peers[i].peer->offset);
2766 peers[i].seljit = SQRT(f / (nlist - 1));
2768 if (peers[i].seljit * peers[i].synch > e) {
2769 g = peers[i].seljit;
2770 e = peers[i].seljit * peers[i].synch;
2774 g = max(g, LOGTOD(sys_precision));
2775 if (nlist <= max(1, sys_minclock) || g <= d ||
2776 ((FLAG_TRUE | FLAG_PREFER) & peers[k].peer->flags))
2779 DPRINTF(3, ("select: drop %s seljit %.6f jit %.6f\n",
2780 ntoa(&peers[k].peer->srcadr), g, d));
2781 if (nlist > sys_maxclock)
2782 peers[k].peer->new_status = CTL_PST_SEL_EXCESS;
2783 for (j = k + 1; j < nlist; j++)
2784 peers[j - 1] = peers[j];
2789 * What remains is a list usually not greater than sys_minclock
2790 * peers. Note that unsynchronized peers cannot survive this
2791 * far. Count and mark these survivors.
2793 * While at it, count the number of leap warning bits found.
2794 * This will be used later to vote the system leap warning bit.
2795 * If a leap warning bit is found on a reference clock, the vote
2798 * Choose the system peer using a hybrid metric composed of the
2799 * selection jitter scaled by the root distance augmented by
2800 * stratum scaled by sys_mindisp (.001 by default). The goal of
2801 * the small stratum factor is to avoid clockhop between a
2802 * reference clock and a network peer which has a refclock and
2803 * is using an older ntpd, which does not floor sys_rootdisp at
2806 * In contrast, ntpd 4.2.6 and earlier used stratum primarily
2807 * in selecting the system peer, using a weight of 1 second of
2808 * additional root distance per stratum. This heavy bias is no
2809 * longer appropriate, as the scaled root distance provides a
2810 * more rational metric carrying the cumulative error budget.
2816 for (i = 0; i < nlist; i++) {
2817 peer = peers[i].peer;
2819 peer->new_status = CTL_PST_SEL_SYNCCAND;
2821 if (peer->leap == LEAP_ADDSECOND) {
2822 if (peer->flags & FLAG_REFCLOCK)
2823 leap_vote_ins = nlist;
2824 else if (leap_vote_ins < nlist)
2827 if (peer->leap == LEAP_DELSECOND) {
2828 if (peer->flags & FLAG_REFCLOCK)
2829 leap_vote_del = nlist;
2830 else if (leap_vote_del < nlist)
2833 if (peer->flags & FLAG_PREFER)
2835 speermet = peers[i].seljit * peers[i].synch +
2836 peer->stratum * sys_mindisp;
2844 * Unless there are at least sys_misane survivors, leave the
2845 * building dark. Otherwise, do a clockhop dance. Ordinarily,
2846 * use the selected survivor speer. However, if the current
2847 * system peer is not speer, stay with the current system peer
2848 * as long as it doesn't get too old or too ugly.
2850 if (nlist > 0 && nlist >= sys_minsane) {
2853 typesystem = peers[speer].peer;
2854 if (osys_peer == NULL || osys_peer == typesystem) {
2856 } else if ((x = fabs(typesystem->offset -
2857 osys_peer->offset)) < sys_mindisp) {
2858 if (sys_clockhop == 0)
2859 sys_clockhop = sys_mindisp;
2862 DPRINTF(1, ("select: clockhop %d %.6f %.6f\n",
2863 j, x, sys_clockhop));
2864 if (fabs(x) < sys_clockhop)
2865 typesystem = osys_peer;
2874 * Mitigation rules of the game. We have the pick of the
2875 * litter in typesystem if any survivors are left. If
2876 * there is a prefer peer, use its offset and jitter.
2877 * Otherwise, use the combined offset and jitter of all kitters.
2879 if (typesystem != NULL) {
2880 if (sys_prefer == NULL) {
2881 typesystem->new_status = CTL_PST_SEL_SYSPEER;
2882 clock_combine(peers, sys_survivors, speer);
2884 typesystem = sys_prefer;
2886 typesystem->new_status = CTL_PST_SEL_SYSPEER;
2887 sys_offset = typesystem->offset;
2888 sys_jitter = typesystem->jitter;
2890 DPRINTF(1, ("select: combine offset %.9f jitter %.9f\n",
2891 sys_offset, sys_jitter));
2895 * If a PPS driver is lit and the combined offset is less than
2896 * 0.4 s, select the driver as the PPS peer and use its offset
2897 * and jitter. However, if this is the atom driver, use it only
2898 * if there is a prefer peer or there are no survivors and none
2901 if (typepps != NULL && fabs(sys_offset) < 0.4 &&
2902 (typepps->refclktype != REFCLK_ATOM_PPS ||
2903 (typepps->refclktype == REFCLK_ATOM_PPS && (sys_prefer !=
2904 NULL || (typesystem == NULL && sys_minsane == 0))))) {
2905 typesystem = typepps;
2907 typesystem->new_status = CTL_PST_SEL_PPS;
2908 sys_offset = typesystem->offset;
2909 sys_jitter = typesystem->jitter;
2910 DPRINTF(1, ("select: pps offset %.9f jitter %.9f\n",
2911 sys_offset, sys_jitter));
2913 #endif /* REFCLOCK */
2916 * If there are no survivors at this point, there is no
2917 * system peer. If so and this is an old update, keep the
2918 * current statistics, but do not update the clock.
2920 if (typesystem == NULL) {
2921 if (osys_peer != NULL) {
2922 if (sys_orphwait > 0)
2923 orphwait = current_time + sys_orphwait;
2924 report_event(EVNT_NOPEER, NULL, NULL);
2927 for (peer = peer_list; peer != NULL; peer = peer->p_link)
2928 peer->status = peer->new_status;
2933 * Do not use old data, as this may mess up the clock discipline
2936 if (typesystem->epoch <= sys_epoch)
2940 * We have found the alpha male. Wind the clock.
2942 if (osys_peer != typesystem)
2943 report_event(PEVNT_NEWPEER, typesystem, NULL);
2944 for (peer = peer_list; peer != NULL; peer = peer->p_link)
2945 peer->status = peer->new_status;
2946 clock_update(typesystem);
2952 peer_select * peers, /* survivor list */
2953 int npeers, /* number of survivors */
2954 int syspeer /* index of sys.peer */
2961 for (i = 0; i < npeers; i++) {
2962 x = 1. / peers[i].synch;
2964 z += x * peers[i].peer->offset;
2965 w += x * DIFF(peers[i].peer->offset,
2966 peers[syspeer].peer->offset);
2969 sys_jitter = SQRT(w / y + SQUARE(peers[syspeer].seljit));
2974 * root_distance - compute synchronization distance from peer to root
2978 struct peer *peer /* peer structure pointer */
2984 * Root Distance (LAMBDA) is defined as:
2985 * (delta + DELTA)/2 + epsilon + EPSILON + phi
2988 * delta is the round-trip delay
2989 * DELTA is the root delay
2990 * epsilon is the remote server precision + local precision
2991 * + (15 usec each second)
2992 * EPSILON is the root dispersion
2993 * phi is the peer jitter statistic
2995 * NB: Think hard about why we are using these values, and what
2996 * the alternatives are, and the various pros/cons.
2998 * DLM thinks these are probably the best choices from any of the
2999 * other worse choices.
3001 dtemp = (peer->delay + peer->rootdelay) / 2
3002 + LOGTOD(peer->precision)
3003 + LOGTOD(sys_precision)
3004 + clock_phi * (current_time - peer->update)
3008 * Careful squeak here. The value returned must be greater than
3009 * the minimum root dispersion in order to avoid clockhop with
3010 * highly precise reference clocks. Note that the root distance
3011 * cannot exceed the sys_maxdist, as this is the cutoff by the
3012 * selection algorithm.
3014 if (dtemp < sys_mindisp)
3015 dtemp = sys_mindisp;
3021 * peer_xmit - send packet for persistent association.
3025 struct peer *peer /* peer structure pointer */
3028 struct pkt xpkt; /* transmit packet */
3029 size_t sendlen, authlen;
3030 keyid_t xkeyid = 0; /* transmit key ID */
3031 l_fp xmt_tx, xmt_ty;
3033 if (!peer->dstadr) /* drop peers without interface */
3036 xpkt.li_vn_mode = PKT_LI_VN_MODE(sys_leap, peer->version,
3038 xpkt.stratum = STRATUM_TO_PKT(sys_stratum);
3039 xpkt.ppoll = peer->hpoll;
3040 xpkt.precision = sys_precision;
3041 xpkt.refid = sys_refid;
3042 xpkt.rootdelay = HTONS_FP(DTOFP(sys_rootdelay));
3043 xpkt.rootdisp = HTONS_FP(DTOUFP(sys_rootdisp));
3044 HTONL_FP(&sys_reftime, &xpkt.reftime);
3045 HTONL_FP(&peer->rec, &xpkt.org);
3046 HTONL_FP(&peer->dst, &xpkt.rec);
3049 * If the received packet contains a MAC, the transmitted packet
3050 * is authenticated and contains a MAC. If not, the transmitted
3051 * packet is not authenticated.
3053 * It is most important when autokey is in use that the local
3054 * interface IP address be known before the first packet is
3055 * sent. Otherwise, it is not possible to compute a correct MAC
3056 * the recipient will accept. Thus, the I/O semantics have to do
3057 * a little more work. In particular, the wildcard interface
3058 * might not be usable.
3060 sendlen = LEN_PKT_NOMAC;
3062 if (!(peer->flags & FLAG_SKEY) && peer->keyid == 0) {
3063 #else /* !AUTOKEY follows */
3064 if (peer->keyid == 0) {
3065 #endif /* !AUTOKEY */
3068 * Transmit a-priori timestamps
3070 get_systime(&xmt_tx);
3071 if (peer->flip == 0) { /* basic mode */
3072 peer->aorg = xmt_tx;
3073 HTONL_FP(&xmt_tx, &xpkt.xmt);
3074 } else { /* interleaved modes */
3075 if (peer->hmode == MODE_BROADCAST) { /* bcst */
3076 HTONL_FP(&xmt_tx, &xpkt.xmt);
3078 HTONL_FP(&peer->borg,
3081 HTONL_FP(&peer->aorg,
3083 } else { /* symmetric */
3085 HTONL_FP(&peer->borg,
3088 HTONL_FP(&peer->aorg,
3092 peer->t21_bytes = sendlen;
3093 sendpkt(&peer->srcadr, peer->dstadr, sys_ttl[peer->ttl],
3096 peer->throttle += (1 << peer->minpoll) - 2;
3099 * Capture a-posteriori timestamps
3101 get_systime(&xmt_ty);
3102 if (peer->flip != 0) { /* interleaved modes */
3104 peer->aorg = xmt_ty;
3106 peer->borg = xmt_ty;
3107 peer->flip = -peer->flip;
3109 L_SUB(&xmt_ty, &xmt_tx);
3110 LFPTOD(&xmt_ty, peer->xleave);
3113 printf("transmit: at %ld %s->%s mode %d len %zu\n",
3114 current_time, peer->dstadr ?
3115 stoa(&peer->dstadr->sin) : "-",
3116 stoa(&peer->srcadr), peer->hmode, sendlen);
3122 * Authentication is enabled, so the transmitted packet must be
3123 * authenticated. If autokey is enabled, fuss with the various
3124 * modes; otherwise, symmetric key cryptography is used.
3127 if (peer->flags & FLAG_SKEY) {
3128 struct exten *exten; /* extension field */
3131 * The Public Key Dance (PKD): Cryptographic credentials
3132 * are contained in extension fields, each including a
3133 * 4-octet length/code word followed by a 4-octet
3134 * association ID and optional additional data. Optional
3135 * data includes a 4-octet data length field followed by
3136 * the data itself. Request messages are sent from a
3137 * configured association; response messages can be sent
3138 * from a configured association or can take the fast
3139 * path without ever matching an association. Response
3140 * messages have the same code as the request, but have
3141 * a response bit and possibly an error bit set. In this
3142 * implementation, a message may contain no more than
3143 * one command and one or more responses.
3145 * Cryptographic session keys include both a public and
3146 * a private componet. Request and response messages
3147 * using extension fields are always sent with the
3148 * private component set to zero. Packets without
3149 * extension fields indlude the private component when
3150 * the session key is generated.
3155 * Allocate and initialize a keylist if not
3156 * already done. Then, use the list in inverse
3157 * order, discarding keys once used. Keep the
3158 * latest key around until the next one, so
3159 * clients can use client/server packets to
3160 * compute propagation delay.
3162 * Note that once a key is used from the list,
3163 * it is retained in the key cache until the
3164 * next key is used. This is to allow a client
3165 * to retrieve the encrypted session key
3166 * identifier to verify authenticity.
3168 * If for some reason a key is no longer in the
3169 * key cache, a birthday has happened or the key
3170 * has expired, so the pseudo-random sequence is
3171 * broken. In that case, purge the keylist and
3174 if (peer->keynumber == 0)
3175 make_keylist(peer, peer->dstadr);
3178 xkeyid = peer->keylist[peer->keynumber];
3179 if (authistrusted(xkeyid))
3184 peer->keyid = xkeyid;
3186 switch (peer->hmode) {
3189 * In broadcast server mode the autokey values are
3190 * required by the broadcast clients. Push them when a
3191 * new keylist is generated; otherwise, push the
3192 * association message so the client can request them at
3195 case MODE_BROADCAST:
3196 if (peer->flags & FLAG_ASSOC)
3197 exten = crypto_args(peer, CRYPTO_AUTO |
3198 CRYPTO_RESP, peer->associd, NULL);
3200 exten = crypto_args(peer, CRYPTO_ASSOC |
3201 CRYPTO_RESP, peer->associd, NULL);
3205 * In symmetric modes the parameter, certificate,
3206 * identity, cookie and autokey exchanges are
3207 * required. The leapsecond exchange is optional. But, a
3208 * peer will not believe the other peer until the other
3209 * peer has synchronized, so the certificate exchange
3210 * might loop until then. If a peer finds a broken
3211 * autokey sequence, it uses the autokey exchange to
3212 * retrieve the autokey values. In any case, if a new
3213 * keylist is generated, the autokey values are pushed.
3219 * Parameter, certificate and identity.
3222 exten = crypto_args(peer, CRYPTO_ASSOC,
3223 peer->associd, hostval.ptr);
3224 else if (!(peer->crypto & CRYPTO_FLAG_CERT))
3225 exten = crypto_args(peer, CRYPTO_CERT,
3226 peer->associd, peer->issuer);
3227 else if (!(peer->crypto & CRYPTO_FLAG_VRFY))
3228 exten = crypto_args(peer,
3229 crypto_ident(peer), peer->associd,
3233 * Cookie and autokey. We request the cookie
3234 * only when the this peer and the other peer
3235 * are synchronized. But, this peer needs the
3236 * autokey values when the cookie is zero. Any
3237 * time we regenerate the key list, we offer the
3238 * autokey values without being asked. If for
3239 * some reason either peer finds a broken
3240 * autokey sequence, the autokey exchange is
3241 * used to retrieve the autokey values.
3243 else if (sys_leap != LEAP_NOTINSYNC &&
3244 peer->leap != LEAP_NOTINSYNC &&
3245 !(peer->crypto & CRYPTO_FLAG_COOK))
3246 exten = crypto_args(peer, CRYPTO_COOK,
3247 peer->associd, NULL);
3248 else if (!(peer->crypto & CRYPTO_FLAG_AUTO))
3249 exten = crypto_args(peer, CRYPTO_AUTO,
3250 peer->associd, NULL);
3251 else if (peer->flags & FLAG_ASSOC &&
3252 peer->crypto & CRYPTO_FLAG_SIGN)
3253 exten = crypto_args(peer, CRYPTO_AUTO |
3254 CRYPTO_RESP, peer->assoc, NULL);
3257 * Wait for clock sync, then sign the
3258 * certificate and retrieve the leapsecond
3261 else if (sys_leap == LEAP_NOTINSYNC)
3264 else if (!(peer->crypto & CRYPTO_FLAG_SIGN))
3265 exten = crypto_args(peer, CRYPTO_SIGN,
3266 peer->associd, hostval.ptr);
3267 else if (!(peer->crypto & CRYPTO_FLAG_LEAP))
3268 exten = crypto_args(peer, CRYPTO_LEAP,
3269 peer->associd, NULL);
3273 * In client mode the parameter, certificate, identity,
3274 * cookie and sign exchanges are required. The
3275 * leapsecond exchange is optional. If broadcast client
3276 * mode the same exchanges are required, except that the
3277 * autokey exchange is substitutes for the cookie
3278 * exchange, since the cookie is always zero. If the
3279 * broadcast client finds a broken autokey sequence, it
3280 * uses the autokey exchange to retrieve the autokey
3286 * Parameter, certificate and identity.
3289 exten = crypto_args(peer, CRYPTO_ASSOC,
3290 peer->associd, hostval.ptr);
3291 else if (!(peer->crypto & CRYPTO_FLAG_CERT))
3292 exten = crypto_args(peer, CRYPTO_CERT,
3293 peer->associd, peer->issuer);
3294 else if (!(peer->crypto & CRYPTO_FLAG_VRFY))
3295 exten = crypto_args(peer,
3296 crypto_ident(peer), peer->associd,
3300 * Cookie and autokey. These are requests, but
3301 * we use the peer association ID with autokey
3302 * rather than our own.
3304 else if (!(peer->crypto & CRYPTO_FLAG_COOK))
3305 exten = crypto_args(peer, CRYPTO_COOK,
3306 peer->associd, NULL);
3307 else if (!(peer->crypto & CRYPTO_FLAG_AUTO))
3308 exten = crypto_args(peer, CRYPTO_AUTO,
3312 * Wait for clock sync, then sign the
3313 * certificate and retrieve the leapsecond
3316 else if (sys_leap == LEAP_NOTINSYNC)
3319 else if (!(peer->crypto & CRYPTO_FLAG_SIGN))
3320 exten = crypto_args(peer, CRYPTO_SIGN,
3321 peer->associd, hostval.ptr);
3322 else if (!(peer->crypto & CRYPTO_FLAG_LEAP))
3323 exten = crypto_args(peer, CRYPTO_LEAP,
3324 peer->associd, NULL);
3329 * Add a queued extension field if present. This is
3330 * always a request message, so the reply ID is already
3331 * in the message. If an error occurs, the error bit is
3332 * lit in the response.
3334 if (peer->cmmd != NULL) {
3337 temp32 = CRYPTO_RESP;
3338 peer->cmmd->opcode |= htonl(temp32);
3339 sendlen += crypto_xmit(peer, &xpkt, NULL,
3340 sendlen, peer->cmmd, 0);
3346 * Add an extension field created above. All but the
3347 * autokey response message are request messages.
3349 if (exten != NULL) {
3350 if (exten->opcode != 0)
3351 sendlen += crypto_xmit(peer, &xpkt,
3352 NULL, sendlen, exten, 0);
3357 * Calculate the next session key. Since extension
3358 * fields are present, the cookie value is zero.
3360 if (sendlen > (int)LEN_PKT_NOMAC) {
3361 session_key(&peer->dstadr->sin, &peer->srcadr,
3365 #endif /* AUTOKEY */
3368 * Transmit a-priori timestamps
3370 get_systime(&xmt_tx);
3371 if (peer->flip == 0) { /* basic mode */
3372 peer->aorg = xmt_tx;
3373 HTONL_FP(&xmt_tx, &xpkt.xmt);
3374 } else { /* interleaved modes */
3375 if (peer->hmode == MODE_BROADCAST) { /* bcst */
3376 HTONL_FP(&xmt_tx, &xpkt.xmt);
3378 HTONL_FP(&peer->borg, &xpkt.org);
3380 HTONL_FP(&peer->aorg, &xpkt.org);
3381 } else { /* symmetric */
3383 HTONL_FP(&peer->borg, &xpkt.xmt);
3385 HTONL_FP(&peer->aorg, &xpkt.xmt);
3388 xkeyid = peer->keyid;
3389 authlen = authencrypt(xkeyid, (u_int32 *)&xpkt, sendlen);
3391 report_event(PEVNT_AUTH, peer, "no key");
3392 peer->flash |= TEST5; /* auth error */
3398 if (xkeyid > NTP_MAXKEY)
3399 authtrust(xkeyid, 0);
3400 #endif /* AUTOKEY */
3401 if (sendlen > sizeof(xpkt)) {
3402 msyslog(LOG_ERR, "proto: buffer overflow %zu", sendlen);
3405 peer->t21_bytes = sendlen;
3406 sendpkt(&peer->srcadr, peer->dstadr, sys_ttl[peer->ttl], &xpkt,
3409 peer->throttle += (1 << peer->minpoll) - 2;
3412 * Capture a-posteriori timestamps
3414 get_systime(&xmt_ty);
3415 if (peer->flip != 0) { /* interleaved modes */
3417 peer->aorg = xmt_ty;
3419 peer->borg = xmt_ty;
3420 peer->flip = -peer->flip;
3422 L_SUB(&xmt_ty, &xmt_tx);
3423 LFPTOD(&xmt_ty, peer->xleave);
3427 printf("transmit: at %ld %s->%s mode %d keyid %08x len %zu index %d\n",
3428 current_time, latoa(peer->dstadr),
3429 ntoa(&peer->srcadr), peer->hmode, xkeyid, sendlen,
3432 #else /* !AUTOKEY follows */
3435 printf("transmit: at %ld %s->%s mode %d keyid %08x len %d\n",
3436 current_time, peer->dstadr ?
3437 ntoa(&peer->dstadr->sin) : "-",
3438 ntoa(&peer->srcadr), peer->hmode, xkeyid, sendlen);
3440 #endif /* !AUTOKEY */
3447 leap_smear_add_offs(l_fp *t, l_fp *t_recv) {
3448 L_ADD(t, &leap_smear.offset);
3451 #endif /* LEAP_SMEAR */
3455 * fast_xmit - Send packet for nonpersistent association. Note that
3456 * neither the source or destination can be a broadcast address.
3460 struct recvbuf *rbufp, /* receive packet pointer */
3461 int xmode, /* receive mode */
3462 keyid_t xkeyid, /* transmit key ID */
3463 int flags /* restrict mask */
3466 struct pkt xpkt; /* transmit packet structure */
3467 struct pkt *rpkt; /* receive packet structure */
3468 l_fp xmt_tx, xmt_ty;
3475 * Initialize transmit packet header fields from the receive
3476 * buffer provided. We leave the fields intact as received, but
3477 * set the peer poll at the maximum of the receive peer poll and
3478 * the system minimum poll (ntp_minpoll). This is for KoD rate
3479 * control and not strictly specification compliant, but doesn't
3482 * If the gazinta was from a multicast address, the gazoutta
3483 * must go out another way.
3485 rpkt = &rbufp->recv_pkt;
3486 if (rbufp->dstadr->flags & INT_MCASTOPEN)
3487 rbufp->dstadr = findinterface(&rbufp->recv_srcadr);
3490 * If this is a kiss-o'-death (KoD) packet, show leap
3491 * unsynchronized, stratum zero, reference ID the four-character
3492 * kiss code and system root delay. Note we don't reveal the
3493 * local time, so these packets can't be used for
3496 if (flags & RES_KOD) {
3498 xpkt.li_vn_mode = PKT_LI_VN_MODE(LEAP_NOTINSYNC,
3499 PKT_VERSION(rpkt->li_vn_mode), xmode);
3500 xpkt.stratum = STRATUM_PKT_UNSPEC;
3501 xpkt.ppoll = max(rpkt->ppoll, ntp_minpoll);
3502 xpkt.precision = rpkt->precision;
3503 memcpy(&xpkt.refid, "RATE", 4);
3504 xpkt.rootdelay = rpkt->rootdelay;
3505 xpkt.rootdisp = rpkt->rootdisp;
3506 xpkt.reftime = rpkt->reftime;
3507 xpkt.org = rpkt->xmt;
3508 xpkt.rec = rpkt->xmt;
3509 xpkt.xmt = rpkt->xmt;
3512 * This is a normal packet. Use the system variables.
3517 * Make copies of the variables which can be affected by smearing.
3520 l_fp this_recv_time;
3524 * If we are inside the leap smear interval we add the current smear offset to
3525 * the packet receive time, to the packet transmit time, and eventually to the
3526 * reftime to make sure the reftime isn't later than the transmit/receive times.
3528 xpkt.li_vn_mode = PKT_LI_VN_MODE(xmt_leap,
3529 PKT_VERSION(rpkt->li_vn_mode), xmode);
3531 xpkt.stratum = STRATUM_TO_PKT(sys_stratum);
3532 xpkt.ppoll = max(rpkt->ppoll, ntp_minpoll);
3533 xpkt.precision = sys_precision;
3534 xpkt.refid = sys_refid;
3535 xpkt.rootdelay = HTONS_FP(DTOFP(sys_rootdelay));
3536 xpkt.rootdisp = HTONS_FP(DTOUFP(sys_rootdisp));
3539 this_ref_time = sys_reftime;
3540 if (leap_smear.in_progress) {
3541 leap_smear_add_offs(&this_ref_time, NULL);
3542 xpkt.refid = convertLFPToRefID(leap_smear.offset);
3543 DPRINTF(2, ("fast_xmit: leap_smear.in_progress: refid %8x, smear %s\n",
3545 lfptoa(&leap_smear.offset, 8)
3548 HTONL_FP(&this_ref_time, &xpkt.reftime);
3550 HTONL_FP(&sys_reftime, &xpkt.reftime);
3553 xpkt.org = rpkt->xmt;
3556 this_recv_time = rbufp->recv_time;
3557 if (leap_smear.in_progress)
3558 leap_smear_add_offs(&this_recv_time, NULL);
3559 HTONL_FP(&this_recv_time, &xpkt.rec);
3561 HTONL_FP(&rbufp->recv_time, &xpkt.rec);
3564 get_systime(&xmt_tx);
3566 if (leap_smear.in_progress)
3567 leap_smear_add_offs(&xmt_tx, &this_recv_time);
3569 HTONL_FP(&xmt_tx, &xpkt.xmt);
3572 #ifdef HAVE_NTP_SIGND
3573 if (flags & RES_MSSNTP) {
3574 send_via_ntp_signd(rbufp, xmode, xkeyid, flags, &xpkt);
3577 #endif /* HAVE_NTP_SIGND */
3580 * If the received packet contains a MAC, the transmitted packet
3581 * is authenticated and contains a MAC. If not, the transmitted
3582 * packet is not authenticated.
3584 sendlen = LEN_PKT_NOMAC;
3585 if (rbufp->recv_length == sendlen) {
3586 sendpkt(&rbufp->recv_srcadr, rbufp->dstadr, 0, &xpkt,
3591 "transmit: at %ld %s->%s mode %d len %d\n",
3592 current_time, stoa(&rbufp->dstadr->sin),
3593 stoa(&rbufp->recv_srcadr), xmode, sendlen);
3599 * The received packet contains a MAC, so the transmitted packet
3600 * must be authenticated. For symmetric key cryptography, use
3601 * the predefined and trusted symmetric keys to generate the
3602 * cryptosum. For autokey cryptography, use the server private
3603 * value to generate the cookie, which is unique for every
3604 * source-destination-key ID combination.
3607 if (xkeyid > NTP_MAXKEY) {
3611 * The only way to get here is a reply to a legitimate
3612 * client request message, so the mode must be
3613 * MODE_SERVER. If an extension field is present, there
3614 * can be only one and that must be a command. Do what
3615 * needs, but with private value of zero so the poor
3616 * jerk can decode it. If no extension field is present,
3617 * use the cookie to generate the session key.
3619 cookie = session_key(&rbufp->recv_srcadr,
3620 &rbufp->dstadr->sin, 0, sys_private, 0);
3621 if (rbufp->recv_length > sendlen + (int)MAX_MAC_LEN) {
3622 session_key(&rbufp->dstadr->sin,
3623 &rbufp->recv_srcadr, xkeyid, 0, 2);
3624 temp32 = CRYPTO_RESP;
3625 rpkt->exten[0] |= htonl(temp32);
3626 sendlen += crypto_xmit(NULL, &xpkt, rbufp,
3627 sendlen, (struct exten *)rpkt->exten,
3630 session_key(&rbufp->dstadr->sin,
3631 &rbufp->recv_srcadr, xkeyid, cookie, 2);
3634 #endif /* AUTOKEY */
3635 get_systime(&xmt_tx);
3636 sendlen += authencrypt(xkeyid, (u_int32 *)&xpkt, sendlen);
3638 if (xkeyid > NTP_MAXKEY)
3639 authtrust(xkeyid, 0);
3640 #endif /* AUTOKEY */
3641 sendpkt(&rbufp->recv_srcadr, rbufp->dstadr, 0, &xpkt, sendlen);
3642 get_systime(&xmt_ty);
3643 L_SUB(&xmt_ty, &xmt_tx);
3644 sys_authdelay = xmt_ty;
3648 "transmit: at %ld %s->%s mode %d keyid %08x len %d\n",
3649 current_time, ntoa(&rbufp->dstadr->sin),
3650 ntoa(&rbufp->recv_srcadr), xmode, xkeyid, sendlen);
3656 * pool_xmit - resolve hostname or send unicast solicitation for pool.
3660 struct peer *pool /* pool solicitor association */
3664 struct pkt xpkt; /* transmit packet structure */
3665 struct addrinfo hints;
3667 struct interface * lcladr;
3668 sockaddr_u * rmtadr;
3673 if (NULL == pool->ai) {
3674 if (pool->addrs != NULL) {
3675 /* free() is used with copy_addrinfo_list() */
3680 hints.ai_family = AF(&pool->srcadr);
3681 hints.ai_socktype = SOCK_DGRAM;
3682 hints.ai_protocol = IPPROTO_UDP;
3683 /* ignore getaddrinfo_sometime() errors, we will retry */
3684 rc = getaddrinfo_sometime(
3689 &pool_name_resolved,
3690 (void *)(intptr_t)pool->associd);
3692 DPRINTF(1, ("pool DNS lookup %s started\n",
3696 "unable to start pool DNS %s %m",
3702 /* copy_addrinfo_list ai_addr points to a sockaddr_u */
3703 rmtadr = (sockaddr_u *)(void *)pool->ai->ai_addr;
3704 pool->ai = pool->ai->ai_next;
3705 p = findexistingpeer(rmtadr, NULL, NULL, MODE_CLIENT, 0);
3706 } while (p != NULL && pool->ai != NULL);
3708 return; /* out of addresses, re-query DNS next poll */
3709 restrict_mask = restrictions(rmtadr);
3710 if (RES_FLAGS & restrict_mask)
3711 restrict_source(rmtadr, 0,
3712 current_time + POOL_SOLICIT_WINDOW + 1);
3713 lcladr = findinterface(rmtadr);
3714 memset(&xpkt, 0, sizeof(xpkt));
3715 xpkt.li_vn_mode = PKT_LI_VN_MODE(sys_leap, pool->version,
3717 xpkt.stratum = STRATUM_TO_PKT(sys_stratum);
3718 xpkt.ppoll = pool->hpoll;
3719 xpkt.precision = sys_precision;
3720 xpkt.refid = sys_refid;
3721 xpkt.rootdelay = HTONS_FP(DTOFP(sys_rootdelay));
3722 xpkt.rootdisp = HTONS_FP(DTOUFP(sys_rootdisp));
3723 HTONL_FP(&sys_reftime, &xpkt.reftime);
3724 get_systime(&xmt_tx);
3725 pool->aorg = xmt_tx;
3726 HTONL_FP(&xmt_tx, &xpkt.xmt);
3727 sendpkt(rmtadr, lcladr, sys_ttl[pool->ttl], &xpkt,
3730 pool->throttle += (1 << pool->minpoll) - 2;
3733 printf("transmit: at %ld %s->%s pool\n",
3734 current_time, latoa(lcladr), stoa(rmtadr));
3736 msyslog(LOG_INFO, "Soliciting pool server %s", stoa(rmtadr));
3743 * group_test - test if this is the same group
3745 * host assoc return action
3746 * none none 0 mobilize *
3747 * none group 0 mobilize *
3748 * group none 0 mobilize *
3749 * group group 1 mobilize
3750 * group different 1 ignore
3751 * * ignore if notrust
3761 if (strcmp(grp, sys_groupname) == 0)
3767 if (strcmp(grp, ident) == 0)
3772 #endif /* AUTOKEY */
3781 const char * service,
3782 const struct addrinfo * hints,
3783 const struct addrinfo * res
3786 struct peer * pool; /* pool solicitor association */
3791 "error resolving pool %s: %s (%d)",
3792 name, gai_strerror(rescode), rescode);
3796 assoc = (associd_t)(intptr_t)context;
3797 pool = findpeerbyassoc(assoc);
3800 "Could not find assoc %u for pool DNS %s",
3804 DPRINTF(1, ("pool DNS %s completed\n", name));
3805 pool->addrs = copy_addrinfo_list(res);
3806 pool->ai = pool->addrs;
3815 * key_expire - purge the key list
3819 struct peer *peer /* peer structure pointer */
3824 if (peer->keylist != NULL) {
3825 for (i = 0; i <= peer->keynumber; i++)
3826 authtrust(peer->keylist[i], 0);
3827 free(peer->keylist);
3828 peer->keylist = NULL;
3830 value_free(&peer->sndval);
3831 peer->keynumber = 0;
3832 peer->flags &= ~FLAG_ASSOC;
3835 printf("key_expire: at %lu associd %d\n", current_time,
3839 #endif /* AUTOKEY */
3843 * local_refid(peer) - check peer refid to avoid selecting peers
3844 * currently synced to this ntpd.
3853 if (p->dstadr != NULL && !(INT_MCASTIF & p->dstadr->flags))
3854 unicast_ep = p->dstadr;
3856 unicast_ep = findinterface(&p->srcadr);
3858 if (unicast_ep != NULL && p->refid == unicast_ep->addr_refid)
3866 * Determine if the peer is unfit for synchronization
3868 * A peer is unfit for synchronization if
3869 * > TEST10 bad leap or stratum below floor or at or above ceiling
3870 * > TEST11 root distance exceeded for remote peer
3871 * > TEST12 a direct or indirect synchronization loop would form
3872 * > TEST13 unreachable or noselect
3874 int /* FALSE if fit, TRUE if unfit */
3876 struct peer *peer /* peer structure pointer */
3882 * A stratum error occurs if (1) the server has never been
3883 * synchronized, (2) the server stratum is below the floor or
3884 * greater than or equal to the ceiling.
3886 if (peer->leap == LEAP_NOTINSYNC || peer->stratum < sys_floor ||
3887 peer->stratum >= sys_ceiling)
3888 rval |= TEST10; /* bad synch or stratum */
3891 * A distance error for a remote peer occurs if the root
3892 * distance is greater than or equal to the distance threshold
3893 * plus the increment due to one host poll interval.
3895 if (!(peer->flags & FLAG_REFCLOCK) && root_distance(peer) >=
3896 sys_maxdist + clock_phi * ULOGTOD(peer->hpoll))
3897 rval |= TEST11; /* distance exceeded */
3900 * A loop error occurs if the remote peer is synchronized to the
3901 * local peer or if the remote peer is synchronized to the same
3902 * server as the local peer but only if the remote peer is
3903 * neither a reference clock nor an orphan.
3905 if (peer->stratum > 1 && local_refid(peer))
3906 rval |= TEST12; /* synchronization loop */
3909 * An unreachable error occurs if the server is unreachable or
3910 * the noselect bit is set.
3912 if (!peer->reach || (peer->flags & FLAG_NOSELECT))
3913 rval |= TEST13; /* unreachable */
3915 peer->flash &= ~PEER_TEST_MASK;
3916 peer->flash |= rval;
3922 * Find the precision of this particular machine
3924 #define MINSTEP 20e-9 /* minimum clock increment (s) */
3925 #define MAXSTEP 1 /* maximum clock increment (s) */
3926 #define MINCHANGES 12 /* minimum number of step samples */
3927 #define MAXLOOPS ((int)(1. / MINSTEP)) /* avoid infinite loop */
3930 * This routine measures the system precision defined as the minimum of
3931 * a sequence of differences between successive readings of the system
3932 * clock. However, if a difference is less than MINSTEP, the clock has
3933 * been read more than once during a clock tick and the difference is
3934 * ignored. We set MINSTEP greater than zero in case something happens
3935 * like a cache miss, and to tolerate underlying system clocks which
3936 * ensure each reading is strictly greater than prior readings while
3937 * using an underlying stepping (not interpolated) clock.
3939 * sys_tick and sys_precision represent the time to read the clock for
3940 * systems with high-precision clocks, and the tick interval or step
3941 * size for lower-precision stepping clocks.
3943 * This routine also measures the time to read the clock on stepping
3944 * system clocks by counting the number of readings between changes of
3945 * the underlying clock. With either type of clock, the minimum time
3946 * to read the clock is saved as sys_fuzz, and used to ensure the
3947 * get_systime() readings always increase and are fuzzed below sys_fuzz.
3950 measure_precision(void)
3953 * With sys_fuzz set to zero, get_systime() fuzzing of low bits
3954 * is effectively disabled. trunc_os_clock is FALSE to disable
3955 * get_ostime() simulation of a low-precision system clock.
3958 trunc_os_clock = FALSE;
3959 measured_tick = measure_tick_fuzz();
3960 set_sys_tick_precision(measured_tick);
3961 msyslog(LOG_INFO, "proto: precision = %.3f usec (%d)",
3962 sys_tick * 1e6, sys_precision);
3963 if (sys_fuzz < sys_tick) {
3964 msyslog(LOG_NOTICE, "proto: fuzz beneath %.3f usec",
3971 * measure_tick_fuzz()
3973 * measures the minimum time to read the clock (stored in sys_fuzz)
3974 * and returns the tick, the larger of the minimum increment observed
3975 * between successive clock readings and the time to read the clock.
3978 measure_tick_fuzz(void)
3980 l_fp minstep; /* MINSTEP as l_fp */
3981 l_fp val; /* current seconds fraction */
3982 l_fp last; /* last seconds fraction */
3983 l_fp ldiff; /* val - last */
3984 double tick; /* computed tick value */
3989 int i; /* log2 precision */
3995 DTOLFP(MINSTEP, &minstep);
3997 for (i = 0; i < MAXLOOPS && changes < MINCHANGES; i++) {
4000 L_SUB(&ldiff, &last);
4002 if (L_ISGT(&ldiff, &minstep)) {
4003 max_repeats = max(repeats, max_repeats);
4006 LFPTOD(&ldiff, diff);
4007 tick = min(diff, tick);
4012 if (changes < MINCHANGES) {
4013 msyslog(LOG_ERR, "Fatal error: precision could not be measured (MINSTEP too large?)");
4017 if (0 == max_repeats) {
4020 set_sys_fuzz(tick / max_repeats);
4028 set_sys_tick_precision(
4036 "unsupported tick %.3f > 1s ignored", tick);
4039 if (tick < measured_tick) {
4041 "proto: tick %.3f less than measured tick %.3f, ignored",
4042 tick, measured_tick);
4044 } else if (tick > measured_tick) {
4045 trunc_os_clock = TRUE;
4047 "proto: truncating system clock to multiples of %.9f",
4053 * Find the nearest power of two.
4055 for (i = 0; tick <= 1; i--)
4057 if (tick - 1 > 1 - tick / 2)
4060 sys_precision = (s_char)i;
4065 * init_proto - initialize the protocol module's data
4074 * Fill in the sys_* stuff. Default is don't listen to
4075 * broadcasting, require authentication.
4077 set_sys_leap(LEAP_NOTINSYNC);
4078 sys_stratum = STRATUM_UNSPEC;
4079 memcpy(&sys_refid, "INIT", 4);
4083 L_CLR(&sys_reftime);
4085 measure_precision();
4086 get_systime(&dummy);
4088 sys_manycastserver = 0;
4091 sys_authenticate = 1;
4092 sys_stattime = current_time;
4093 orphwait = current_time + sys_orphwait;
4095 for (i = 0; i < MAX_TTL; i++) {
4096 sys_ttl[i] = (u_char)((i * 256) / MAX_TTL);
4105 * proto_config - configure the protocol module
4116 * Figure out what he wants to change, then do it
4118 DPRINTF(2, ("proto_config: code %d value %lu dvalue %lf\n",
4119 item, value, dvalue));
4124 * enable and disable commands - arguments are Boolean.
4126 case PROTO_AUTHENTICATE: /* authentication (auth) */
4127 sys_authenticate = value;
4130 case PROTO_BROADCLIENT: /* broadcast client (bclient) */
4131 sys_bclient = (int)value;
4132 if (sys_bclient == 0)
4139 case PROTO_CAL: /* refclock calibrate (calibrate) */
4142 #endif /* REFCLOCK */
4144 case PROTO_KERNEL: /* kernel discipline (kernel) */
4148 case PROTO_MONITOR: /* monitoring (monitor) */
4154 msyslog(LOG_WARNING,
4155 "restrict: 'monitor' cannot be disabled while 'limited' is enabled");
4159 case PROTO_NTP: /* NTP discipline (ntp) */
4163 case PROTO_MODE7: /* mode7 management (ntpdc) */
4167 case PROTO_PPS: /* PPS discipline (pps) */
4168 hardpps_enable = value;
4171 case PROTO_FILEGEN: /* statistics (stats) */
4172 stats_control = value;
4176 * tos command - arguments are double, sometimes cast to int
4178 case PROTO_BEACON: /* manycast beacon (beacon) */
4179 sys_beacon = (int)dvalue;
4182 case PROTO_BROADDELAY: /* default broadcast delay (bdelay) */
4183 sys_bdelay = dvalue;
4186 case PROTO_CEILING: /* stratum ceiling (ceiling) */
4187 sys_ceiling = (int)dvalue;
4190 case PROTO_COHORT: /* cohort switch (cohort) */
4191 sys_cohort = (int)dvalue;
4194 case PROTO_FLOOR: /* stratum floor (floor) */
4195 sys_floor = (int)dvalue;
4198 case PROTO_MAXCLOCK: /* maximum candidates (maxclock) */
4199 sys_maxclock = (int)dvalue;
4202 case PROTO_MAXDIST: /* select threshold (maxdist) */
4203 sys_maxdist = dvalue;
4206 case PROTO_CALLDELAY: /* modem call delay (mdelay) */
4207 break; /* NOT USED */
4209 case PROTO_MINCLOCK: /* minimum candidates (minclock) */
4210 sys_minclock = (int)dvalue;
4213 case PROTO_MINDISP: /* minimum distance (mindist) */
4214 sys_mindisp = dvalue;
4217 case PROTO_MINSANE: /* minimum survivors (minsane) */
4218 sys_minsane = (int)dvalue;
4221 case PROTO_ORPHAN: /* orphan stratum (orphan) */
4222 sys_orphan = (int)dvalue;
4225 case PROTO_ORPHWAIT: /* orphan wait (orphwait) */
4226 orphwait -= sys_orphwait;
4227 sys_orphwait = (int)dvalue;
4228 orphwait += sys_orphwait;
4232 * Miscellaneous commands
4234 case PROTO_MULTICAST_ADD: /* add group address */
4236 io_multicast_add(svalue);
4240 case PROTO_MULTICAST_DEL: /* delete group address */
4242 io_multicast_del(svalue);
4247 "proto: unsupported option %d", item);
4253 * proto_clr_stats - clear protocol stat counters
4256 proto_clr_stats(void)
4258 sys_stattime = current_time;
4267 sys_limitrejected = 0;