ns_forw.c

早期freebsd实现

skipserver: ;
	}
out:
	dprintf(3, (ddt, "nslookup: %d ns addrs total\n", n));
	qp->q_naddr = n;
#ifdef DATUMREFCNT
	/* must be run before the sort */
	for (i = naddr ; i < n ; i++) {
		qp->q_addr[i].nsdata->d_rcnt++;
		qp->q_addr[i].ns->d_rcnt++;
	}
#endif
	if (n > 1) {
		qsort((char *)qp->q_addr, n, sizeof(struct qserv),
		      (int (*)__P((const void *, const void *)))qcomp);
	}
	return (n - naddr);
}

/*
 * qcomp - compare two NS addresses, and return a negative, zero, or
 *	   positive value depending on whether the first NS address is
 *	   "better than", "equally good as", or "inferior to" the second
 *	   NS address.
 *
 * How "goodness" is defined (for the purposes of this routine):
 *  - If the estimated round trip times differ by an amount deemed significant
 *    then the one with the smaller estimate is preferred; else
 *  - If we can determine which one is topologically closer then the
 *    closer one is preferred; else
 *  - The one with the smaller estimated round trip time is preferred
 *    (zero is returned if the two estimates are identical).
 *
 * How "topological closeness" is defined (for the purposes of this routine):
 *    Ideally, named could consult some magic map of the Internet and
 *    determine the length of the path to an arbitrary destination.  Sadly,
 *    no such magic map exists.  However, named does have a little bit of
 *    topological information in the form of the sortlist (which includes
 *    the directly connected subnet(s), the directly connected net(s), and
 *    any additional nets that the administrator has added using the "sortlist"
 *    directive in the bootfile.  Thus, if only one of the addresses matches
 *    something in the sortlist then it is considered to be topologically
 *    closer.  If both match, but match different entries in the sortlist,
 *    then the one that matches the entry closer to the beginning of the
 *    sorlist is considered to be topologically closer.  In all other cases,
 *    topological closeness is ignored because it's either indeterminate or
 *    equal.
 *
 * How times are compared:
 *    Both times are rounded to the closest multiple of the NOISE constant
 *    defined below and then compared.  If the rounded values are equal
 *    then the difference in the times is deemed insignificant.  Rounding
 *    is used instead of merely taking the absolute value of the difference
 *    because doing the latter would make the ordering defined by this
 *    routine be incomplete in the mathematical sense (e.g. A > B and
 *    B > C would not imply A > C).  The mathematics are important in
 *    practice to avoid core dumps in qsort().
 *
 * XXX: this doesn't solve the European root nameserver problem very well.
 * XXX: we should detect and mark as inferior nameservers that give bogus
 *      answers
 *
 * (this was originally vixie's stuff but almquist fixed fatal bugs in it
 * and wrote the above documentation)
 */

/*
 * RTT delta deemed to be significant, in milliseconds.  With the current
 * definition of RTTROUND it must be a power of 2.
 */
#define NOISE 128		/* milliseconds; 0.128 seconds */

#define sign(x) (((x) < 0) ? -1 : ((x) > 0) ? 1 : 0)
#define RTTROUND(rtt) (((rtt) + (NOISE >> 1)) & ~(NOISE - 1))

int
qcomp(qs1, qs2)
	struct qserv *qs1, *qs2;
{
	int pos1, pos2, pdiff;
	u_long rtt1, rtt2;
	long tdiff;

	if ((!qs1->nsdata) || (!qs2->nsdata))
		return 0;
	rtt1 = qs1->nsdata->d_nstime;
	rtt2 = qs2->nsdata->d_nstime;

	dprintf(10, (ddt, "qcomp(%s, %s) %lu (%lu) - %lu (%lu) = %lu",
		     inet_ntoa(qs1->ns_addr.sin_addr),
		     inet_ntoa(qs2->ns_addr.sin_addr),
		     rtt1, RTTROUND(rtt1), rtt2, RTTROUND(rtt2),
		     rtt1 - rtt2));
	if (RTTROUND(rtt1) == RTTROUND(rtt2)) {
		pos1 = position_on_netlist(qs1->ns_addr.sin_addr, nettab);
		pos2 = position_on_netlist(qs2->ns_addr.sin_addr, nettab);
		pdiff = pos1 - pos2;
		dprintf(10, (ddt, ", pos1=%d, pos2=%d\n", pos1, pos2));
		if (pdiff)
			return (pdiff);
	} else {
		dprintf(10, (ddt, "\n"));
	}
	tdiff = rtt1 - rtt2;
	return (sign(tdiff));
}
#undef sign
#undef RTTROUND

/*
 * Arrange that forwarded query (qp) is retried after t seconds.
 */
void
schedretry(qp, t)
	struct qinfo *qp;
	time_t t;
{
	register struct qinfo *qp1, *qp2;

#ifdef DEBUG
	if (debug > 3) {
		fprintf(ddt,"schedretry(%#x, %dsec)\n", qp, t);
		if (qp->q_time)
		    fprintf(ddt,
			    "WARNING: schedretry(%#x, %d) q_time already %d\n",
			    qp, t, qp->q_time);
	}
#endif
	t += (u_long) tt.tv_sec;
	qp->q_time = t;

	if ((qp1 = retryqp) == NULL) {
		retryqp = qp;
		qp->q_next = NULL;
		return;
	}
	if (t < qp1->q_time) {
		qp->q_next = qp1;
		retryqp = qp;
		return;
	}
	while ((qp2 = qp1->q_next) != NULL && qp2->q_time < t)
		qp1 = qp2;
	qp1->q_next = qp;
	qp->q_next = qp2;
}

/*
 * Unsched is called to remove a forwarded query entry.
 */
void
unsched(qp)
	struct qinfo *qp;
{
	register struct qinfo *np;

	dprintf(3, (ddt, "unsched(%#x, %d )\n", qp, ntohs(qp->q_id)));
	if (retryqp == qp) {
		retryqp = qp->q_next;
	} else {
		for (np=retryqp;  np->q_next != QINFO_NULL;  np = np->q_next) {
			if (np->q_next != qp)
				continue;
			np->q_next = qp->q_next;	/* dequeue */
			break;
		}
	}
	qp->q_next = QINFO_NULL;		/* sanity check */
	qp->q_time = 0;
}

/*
 * Retry is called to retransmit query 'qp'.
 */
void
retry(qp)
	register struct qinfo *qp;
{
	register int n;
	register HEADER *hp;

	dprintf(3, (ddt, "retry(x%x) id=%d\n", qp, ntohs(qp->q_id)));

	if (qp->q_msg == NULL) {		/* XXX - why? */
		qremove(qp);
		return;
	}

	if (qp->q_expire && (qp->q_expire < tt.tv_sec)) {
		dprintf(1, (ddt,
		        "retry(x%x): expired @ %d (%d secs before now (%d))\n",
				qp, qp->q_expire, tt.tv_sec - qp->q_expire,
				tt.tv_sec));
		qremove(qp);
		return;
	}

	/* try next address */
	n = qp->q_curaddr;
	if (qp->q_fwd) {
		qp->q_fwd = qp->q_fwd->next;
		if (qp->q_fwd)
			goto found;
		/* out of forwarders, try direct queries */
	} else
		++qp->q_addr[n].nretry;
	if (!forward_only) {
		do {
			if (++n >= qp->q_naddr)
				n = 0;
			if (qp->q_addr[n].nretry < MAXRETRY)
				goto found;
		} while (n != qp->q_curaddr);
	}
	/*
	 * Give up. Can't reach destination.
	 */
	hp = (HEADER *)(qp->q_cmsg ? qp->q_cmsg : qp->q_msg);
	if (qp->q_flags & Q_PRIMING) {
		/* Can't give up priming */
		unsched(qp);
		schedretry(qp, (time_t)60*60);	/* 1 hour */
		hp->rcode = NOERROR;	/* Lets be safe, reset the query */
		hp->qr = hp->aa = 0;
		qp->q_fwd = fwdtab;
		for (n = 0; n < qp->q_naddr; n++)
			qp->q_addr[n].nretry = 0;
		return;
	}
	dprintf(5, (ddt, "give up\n"));
	n = ((HEADER *)qp->q_cmsg ? qp->q_cmsglen : qp->q_msglen);
	hp->id = qp->q_id;
	hp->qr = 1;
	hp->ra = 1;
	hp->rd = 1;
	hp->rcode = SERVFAIL;
#ifdef DEBUG
	if (debug >= 10)
		fp_query(qp->q_msg, ddt);
#endif
	if (send_msg((char *)hp, n, qp)) {
		dprintf(1, (ddt,"gave up retry(x%x) nsid=%d id=%d\n",
			    qp, ntohs(qp->q_nsid), ntohs(qp->q_id)));
	}
	qremove(qp);
	stats[S_RESPFAIL].cnt++;
	return;

found:
	if (qp->q_fwd == 0 && qp->q_addr[n].nretry == 0)
		qp->q_addr[n].stime = tt;
	qp->q_curaddr = n;
	hp = (HEADER *)qp->q_msg;
	hp->rd = (qp->q_fwd ? 1 : 0);
	dprintf(1, (ddt,
		    "%s(addr=%d n=%d) -> [%s].%d ds=%d nsid=%d id=%d %dms\n",
		    (qp->q_fwd ? "reforw" : "resend"),
		    n, qp->q_addr[n].nretry,
		    inet_ntoa(Q_NEXTADDR(qp,n)->sin_addr),
		    ntohs(Q_NEXTADDR(qp,n)->sin_port), ds,
		    ntohs(qp->q_nsid), ntohs(qp->q_id),
		    (qp->q_addr[n].nsdata != 0)
			? qp->q_addr[n].nsdata->d_nstime
			: (-1)));
#ifdef DEBUG
	if (debug >= 10)
		fp_query(qp->q_msg, ddt);
#endif
	/* NOSTRICT */
	if (sendto(ds, qp->q_msg, qp->q_msglen, 0,
	    (struct sockaddr *)Q_NEXTADDR(qp,n),
	    sizeof(struct sockaddr_in)) < 0) {
		dprintf(3, (ddt, "error resending msg errno=%d\n", errno));
	}
	hp->rd = 1;	/* leave set to 1 for dup detection */
	stats[S_OUTPKTS].cnt++;
	unsched(qp);
#ifdef SLAVE_FORWARD
	if(forward_only)
		schedretry(qp, (time_t)slave_retry);
	else
#endif /* SLAVE_FORWARD */
	schedretry(qp, qp->q_fwd ? (2*RETRYBASE) : retrytime(qp));
}

/*
 * Compute retry time for the next server for a query.
 * Use a minimum time of RETRYBASE (4 sec.) or twice the estimated
 * service time; * back off exponentially on retries, but place a 45-sec.
 * ceiling on retry times for now.  (This is because we don't hold a reference
 * on servers or their addresses, and we have to finish before they time out.)
 */
time_t
retrytime(qp)
	register struct qinfo *qp;
{
	time_t t;
	struct qserv *ns = &qp->q_addr[qp->q_curaddr];

	dprintf(3, (ddt, "retrytime: nstime %dms.\n",
		    (ns->nsdata != 0)
		    	? (ns->nsdata->d_nstime / 1000)
		    	: (-1)));
	if (ns->nsdata != NULL)
		t = (time_t) MAX(RETRYBASE, 2 * ns->nsdata->d_nstime / 1000);
	else
		t = (time_t) RETRYBASE;
	t <<= ns->nretry;
	t = MIN(t, RETRY_TIMEOUT);	/* max. retry timeout for now */
	return (t);
}

void
qflush()
{
	while (qhead)
		qremove(qhead);
	qhead = QINFO_NULL;
}

void
qremove(qp)
	register struct qinfo *qp;
{
	dprintf(3, (ddt, "qremove(x%x)\n", qp));

	if (qp->q_flags & Q_ZSERIAL)
		qserial_answer(qp, 0);
	unsched(qp);
	qfree(qp);
}

#if defined(__STDC__) || defined(__GNUC__)
struct qinfo *
qfindid(u_int16_t id)
#else
struct qinfo *
qfindid(id)
	register u_int16_t id;
#endif
{
	register struct qinfo *qp;

	dprintf(3, (ddt, "qfindid(%d)\n", ntohs(id)));
	for (qp = qhead; qp!=QINFO_NULL; qp = qp->q_link) {
		if (qp->q_nsid == id)
			return(qp);
	}
	dprintf(5, (ddt, "qp not found\n"));
	return(NULL);
}

struct qinfo *
#ifdef DMALLOC
qnew_tagged(file, line)
	char *file;
	int line;
#else
qnew()
#endif
{
	register struct qinfo *qp;

	if ((qp = (struct qinfo *)
#ifdef DMALLOC
				  dcalloc(file, line,
#else
				  calloc(
#endif
					 1, sizeof(struct qinfo))) == NULL) {
		dprintf(5, (ddt, "qnew: calloc error\n"));
		syslog(LOG_ERR, "forw: %m");
		exit(12);
	}
	dprintf(5, (ddt, "qnew(x%x)\n", qp));
	qp->q_link = qhead;
	qhead = qp;
	return( qp );
}

void
qfree(qp)
	struct qinfo *qp;
{
	register struct qinfo *np;
	register struct databuf *dp;
#ifdef	DATUMREFCNT
	int i;
#endif

#ifdef DEBUG
	if(debug > 3)
		fprintf(ddt,"Qfree( x%x )\n", qp);
	if(debug && qp->q_next)
		fprintf(ddt,"WARNING:  qfree of linked ptr x%x\n", qp);
#endif
	if (qp->q_msg)
	 	free(qp->q_msg);
 	if (qp->q_cmsg)
 		free(qp->q_cmsg);
#ifdef	DATUMREFCNT
	for (i = 0 ; i < qp->q_naddr ; i++) {
		dp = qp->q_addr[i].ns;
		if (dp)
			if (--(dp->d_rcnt)) {
				dprintf(3, (ddt, "qfree: ns %s rcnt %d\n",
						dp->d_data,
						dp->d_rcnt));
			} else {
				dprintf(3, (ddt, "qfree: ns %s rcnt %d delayed\n",
						dp->d_data,
						dp->d_rcnt));
				free((char*)dp);
			}
		dp = qp->q_addr[i].nsdata;
		if (dp)
			if ((--(dp->d_rcnt))) {
				dprintf(3, (ddt, "qfree: nsdata %08.8X rcnt %d\n",
					*(int32_t *)(dp->d_data),
					dp->d_rcnt));
			} else {
				dprintf(3, (ddt, "qfree: nsdata %08.8X rcnt %d delayed\n",
					*(int32_t *)(dp->d_data),
					dp->d_rcnt));
			free((char*)dp);
			}
	}
#endif
	if( qhead == qp )  {
		qhead = qp->q_link;
	} else {
		for( np=qhead; np->q_link != QINFO_NULL; np = np->q_link )  {
			if( np->q_link != qp )  continue;
			np->q_link = qp->q_link;	/* dequeue */
			break;
		}
	}
	free((char *)qp);
}