ntp_proto.c

网络时间协议NTP 源码 版本v4.2.0b 该源码用于linux平台下

	/*
	 * Initially, we populate the island with all the rifraff peers
	 * that happen to be lying around. Those with seriously
	 * defective clocks are immediately booted off the island. Then,
	 * the falsetickers are culled and put to sea. The truechimers
	 * remaining are subject to repeated rounds where the most
	 * unpopular at each round is kicked off. When the population
	 * has dwindled to sys_minclock, the survivors split a million
	 * bucks and collectively crank the chimes.
	 */
	nlist = nl3 = 0;	/* none yet */
	for (n = 0; n < NTP_HASH_SIZE; n++) {
		for (peer = peer_hash[n]; peer != NULL; peer =
		    peer->next) {
			peer->flags &= ~FLAG_SYSPEER;
			peer->status = CTL_PST_SEL_REJECT;

			/*
			 * Leave the island immediately if the peer is
			 * unfit to synchronize.
			 */
			if (peer_unfit(peer))
				continue;

			/*
			 * Don't allow the local clock or modem drivers
			 * in the kitchen at this point, unless the
			 * prefer peer. Do that later, but only if
			 * nobody else is around. These guys are all
			 * configured, so we never throw them away.
			 */
#ifdef REFCLOCK
			if (peer->refclktype == REFCLK_LOCALCLOCK
#if defined(VMS) && defined(VMS_LOCALUNIT)
			/* wjm: VMS_LOCALUNIT taken seriously */
			    && REFCLOCKUNIT(&peer->srcadr) !=
			    VMS_LOCALUNIT
#endif	/* VMS && VMS_LOCALUNIT */
				) {
				typelocal = peer;
#ifndef LOCKCLOCK
				if (!(peer->flags & FLAG_PREFER))
					continue; /* no local clock */
#endif /* LOCKCLOCK */
			}
			if (peer->sstclktype == CTL_SST_TS_TELEPHONE) {
				typeacts = peer;
				if (!(peer->flags & FLAG_PREFER))
					continue; /* no acts */
			}
#endif /* REFCLOCK */

			/*
			 * If we get this far, the peer can stay on the
			 * island, but does not yet have the immunity
			 * idol.
			 */
			peer->status = CTL_PST_SEL_SANE;
			peer_list[nlist++] = peer;

			/*
			 * Insert each interval endpoint on the sorted
			 * list.
			 */
			e = peer->offset;	 /* Upper end */
			f = root_distance(peer);
			e = e + f;
			for (i = nl3 - 1; i >= 0; i--) {
				if (e >= endpoint[indx[i]].val)
					break;

				indx[i + 3] = indx[i];
			}
			indx[i + 3] = nl3;
			endpoint[nl3].type = 1;
			endpoint[nl3++].val = e;

			e = e - f;		/* Center point */
			for (; i >= 0; i--) {
				if (e >= endpoint[indx[i]].val)
					break;

				indx[i + 2] = indx[i];
			}
			indx[i + 2] = nl3;
			endpoint[nl3].type = 0;
			endpoint[nl3++].val = e;

			e = e - f;		/* Lower end */
			for (; i >= 0; i--) {
				if (e >= endpoint[indx[i]].val)
					break;

				indx[i + 1] = indx[i];
			}
			indx[i + 1] = nl3;
			endpoint[nl3].type = -1;
			endpoint[nl3++].val = e;
		}
	}
#ifdef DEBUG
	if (debug > 2)
		for (i = 0; i < nl3; i++)
			printf("select: endpoint %2d %.6f\n",
			   endpoint[indx[i]].type,
			   endpoint[indx[i]].val);
#endif
	/*
	 * This is the actual algorithm that cleaves the truechimers
	 * from the falsetickers. The original algorithm was described
	 * in Keith Marzullo's dissertation, but has been modified for
	 * better accuracy.
	 *
	 * Briefly put, we first assume there are no falsetickers, then
	 * scan the candidate list first from the low end upwards and
	 * then from the high end downwards. The scans stop when the
	 * number of intersections equals the number of candidates less
	 * the number of falsetickers. If this doesn't happen for a
	 * given number of falsetickers, we bump the number of
	 * falsetickers and try again. If the number of falsetickers
	 * becomes equal to or greater than half the number of
	 * candidates, the Albanians have won the Byzantine wars and
	 * correct synchronization is not possible.
	 *
	 * Here, nlist is the number of candidates and allow is the
	 * number of falsetickers. Upon exit, the truechimers are the
	 * susvivors with offsets not less than low and not greater than
	 * high. There may be none of them.
	 */
	low = 1e9;
	high = -1e9;
	for (allow = 0; 2 * allow < nlist; allow++) {
		int	found;

		/*
		 * Bound the interval (low, high) as the largest
		 * interval containing points from presumed truechimers.
		 */
		found = 0;
		n = 0;
		for (i = 0; i < nl3; i++) {
			low = endpoint[indx[i]].val;
			n -= endpoint[indx[i]].type;
			if (n >= nlist - allow)
				break;
			if (endpoint[indx[i]].type == 0)
				found++;
		}
		n = 0;
		for (j = nl3 - 1; j >= 0; j--) {
			high = endpoint[indx[j]].val;
			n += endpoint[indx[j]].type;
			if (n >= nlist - allow)
				break;
			if (endpoint[indx[j]].type == 0)
				found++;
		}

		/*
		 * If the number of candidates found outside the
		 * interval is greater than the number of falsetickers,
		 * then at least one truechimer is outside the interval,
		 * so go around again. This is what makes this algorithm
		 * different than Marzullo's.
		 */
		if (found > allow)
			continue;

		/*
		 * If an interval containing truechimers is found, stop.
		 * If not, increase the number of falsetickers and go
		 * around again.
		 */
		if (high > low)
			break;
	}

	/*
	 * Clustering algorithm. Construct candidate list in order first
	 * by stratum then by root distance, but keep only the best
	 * NTP_MAXASSOC of them. Scan the list to find falsetickers, who
	 * leave the island immediately. The TRUE peer is always a
	 * truechimer. We must leave at least one peer to collect the
	 * million bucks. If in orphan mode, rascals found with lower
	 * stratum are guaranteed a seat on the bus.
	 */
	j = 0;
	for (i = 0; i < nlist; i++) {
		peer = peer_list[i];
		if (nlist > 1 && (peer->offset <= low || peer->offset >=
		    high) && !(peer->flags & FLAG_TRUE) &&
		    !(sys_stratum >= sys_orphan && peer->stratum <
		    sys_orphan))
			continue;

		peer->status = CTL_PST_SEL_DISTSYSPEER;

		/*
		 * The order metric is formed from the stratum times
		 * max distance (1.) plus the root distance. It strongly
		 * favors the lowest stratum, but a higher stratum peer
		 * can capture the clock if the low stratum dominant
		 * hasn't been heard for awhile.
		 */
		d = root_distance(peer) + peer->stratum * sys_maxdist;
		if (j >= NTP_MAXASSOC) {
			if (d >= synch[j - 1])
				continue;
			else
				j--;
		}
		for (k = j; k > 0; k--) {
			if (d >= synch[k - 1])
				break;

			peer_list[k] = peer_list[k - 1];
			error[k] = error[k - 1];
			synch[k] = synch[k - 1];
		}
		peer_list[k] = peer;
		error[k] = peer->jitter;
		synch[k] = d;
		j++;
	}
	nlist = j;

	/*
	 * If no survivors remain at this point, check if the local
	 * clock or modem drivers have been found. If so, nominate one
	 * of them as the only survivor. Otherwise, give up and leave
	 * the island to the rats.
	 */
	if (nlist == 0) {
		if (typeacts != 0) {
			typeacts->status = CTL_PST_SEL_DISTSYSPEER;
			peer_list[0] = typeacts;
			nlist = 1;
		} else if (typelocal != 0) {
			typelocal->status = CTL_PST_SEL_DISTSYSPEER;
			peer_list[0] = typelocal;
			nlist = 1;
		} else {
			if (osys_peer != NULL) {
				NLOG(NLOG_SYNCSTATUS)
				    msyslog(LOG_INFO,
				    "no servers reachable");
				report_event(EVNT_PEERSTCHG, NULL);
			}
		}
	}

	/*
	 * We can only trust the survivors if the number of candidates
	 * sys_minsane is at least the number required to detect and
	 * cast out one falsticker. For the Byzantine agreement
	 * algorithm used here, that number is 4; however, the default
	 * sys_minsane is 1 to speed initial synchronization. Careful
	 * operators will tinker a higher value and use at least that
	 * number of synchronization sources.
	 */
	if (nlist < sys_minsane)
		return;

	for (i = 0; i < nlist; i++)
		peer_list[i]->status = CTL_PST_SEL_SELCAND;

	/*
	 * Now, vote outlyers off the island by select jitter weighted
	 * by root distance. Continue voting as long as there are more
	 * than sys_minclock survivors and the minimum select jitter is
	 * greater than the maximum peer jitter. Stop if we are about to
	 * discard a TRUE or PREFER  peer, who of course has the
	 * immunity idol.
	 */
	while (1) {
		d = 1e9;
		e = -1e9;
		f = g = 0;
		k = 0;
		for (i = 0; i < nlist; i++) {
			if (error[i] < d)
				d = error[i];
			f = 0;
			if (nlist > 1) {
				for (j = 0; j < nlist; j++)
					f += DIFF(peer_list[j]->offset,
					    peer_list[i]->offset);
				f = SQRT(f / (nlist - 1));
			}
			if (f * synch[i] > e) {
				g = f;
				e = f * synch[i];
				k = i;
			}
		}
		f = max(f, LOGTOD(sys_precision));
		if (nlist <= sys_minclock || f <= d ||
		    peer_list[k]->flags & (FLAG_TRUE | FLAG_PREFER))
			break;
#ifdef DEBUG
		if (debug > 2)
			printf(
			    "select: drop %s select %.6f jitter %.6f\n",
			    ntoa(&peer_list[k]->srcadr), g, d);
#endif
		for (j = k + 1; j < nlist; j++) {
			peer_list[j - 1] = peer_list[j];
			error[j - 1] = error[j];
		}
		nlist--;
	}

	/*
	 * What remains is a list usually not greater than sys_minclock
	 * peers. We want only a peer at the lowest stratum to become
	 * the system peer, although all survivors are eligible for the
	 * combining algorithm. Consider each peer in turn and OR the
	 * leap bits on the assumption that, if some of them honk
	 * nonzero bits, they must know what they are doing. Check for
	 * prefer and pps peers at any stratum. Note that the head of
	 * the list is at the lowest stratum and that unsynchronized
	 * peers cannot survive this far.
	 */
	leap_next = 0;
	for (i = 0; i < nlist; i++) {
		peer = peer_list[i];
		sys_survivors++;
		leap_next |= peer->leap;
		peer->status = CTL_PST_SEL_SYNCCAND;
		if (peer->flags & FLAG_PREFER)
			sys_prefer = peer;
		if (peer == osys_peer)
			typesystem = peer;
#ifdef REFCLOCK
		if (peer->refclktype == REFCLK_ATOM_PPS)
			sys_pps = peer;
#endif /* REFCLOCK */
#if DEBUG
		if (debug > 1)
			printf("cluster: survivor %s metric %.6f\n",
			    ntoa(&peer_list[i]->srcadr), synch[i]);
#endif
	}

	/*
	 * Anticlockhop provision. Keep the current system peer if it is
	 * a survivor but not first in the list. But do that only HOPPER
	 * times.
	 */
	if (osys_peer == NULL || typesystem == NULL || typesystem ==
	    peer_list[0] || sys_hopper > sys_maxhop) {
		typesystem = peer_list[0];
		sys_hopper = 0;
	} else {
		peer->selbroken++;
	}

	/*
	 * Mitigation rules of the game. There are several types of
	 * peers that can be selected here: (1) orphan, (2) prefer peer
	 * (flag FLAG_PREFER) (3) pps peers (type REFCLK_ATOM_PPS), (4)
	 * the existing system peer, if any, and (5) the head of the
	 * survivor list.
	 */
	if (typesystem->stratum >= sys_orphan) {

		/*
		 * If in orphan mode, choose the system peer. If the
		 * lowest distance, we are the orphan parent and the
		 * offset is zero.
		 */
		sys_peer = typesystem;
		sys_peer->status = CTL_PST_SEL_SYSPEER;
		if (sys_orphandelay < sys_peer->rootdelay) {
			sys_offset = 0;
			sys_refid = htonl(LOOPBACKADR);
		} else {
			sys_offset = sys_peer->offset;
			sys_refid = addr2refid(&sys_peer->srcadr);
		}
		sys_jitter = LOGTOD(sys_precision);
#ifdef DEBUG
		if (debug > 1)
			printf("select: orphan offset %.6f\n",
			    sys_offset);
#endif
	} else if (sys_prefer) {

		/*
		 * If a pps peer is present, choose it; otherwise,
		 * choose the prefer peer.
		 */
		if (sys_pps) {
			sys_peer = sys_pps;
			sys_peer->status = CTL_PST_SEL_PPS;
			sys_offset = sys_peer->offset;
			if (!pps_control)
				NLOG(NLOG_SYSEVENT)
				    msyslog(LOG_INFO,
				    "pps sync enabled");
			pps_control = current_time;
#ifdef DEBUG
			if (debug > 1)
				printf("select: pps offset %.6f\n",
				    sys_offset);
#endif
		} else {
			sys_peer = sys_prefer;
			sys_peer->status = CTL_PST_SEL_SYSPEER;
			sys_offset = sys_peer->offset;
#ifdef DEBUG
			if (debug > 1)
				printf("select: prefer offset %.6f\n",
				    sys_offset);
#endif
		}
		if (sys_peer->stratum == STRATUM_REFCLOCK ||
		    sys_peer->stratum == STRATUM_UNSPEC)
			sys_refid = sys_peer->refid;
		else
			sys_refid = addr2refid(&sys_peer->srcadr);
		sys_jitter = sys_peer->jitter;
	} else {

		/*
		 * Otherwise, choose the anticlockhopper.
		 */ 
		sys_peer = typesystem;
		sys_peer->status = CTL_PST_SEL_SYSPEER;
		clock_combine(peer_list, nlist);
		if (sys_peer->stratum == STRATUM_REFCLOCK ||
		    sys_peer->stratum == STRATUM_UNSPEC)
			sys_refid = sys_peer->refid;
		else
			sys_refid = addr2refid(&sys_peer->srcadr);
		sys_jitter = SQRT(SQUARE(sys_peer->jitter) +
		    SQUARE(sys_jitter));
#ifdef DEBUG
		if (debug > 1)
			printf("select: combine offset %.6f\n",
			   sys_offset);
#endif
	}

	/*
	 * We have found the alpha male.
	 */
	sys_peer->flags |= FLAG_SYSPEER;
	i