1 #include <u.h>
2 #include <sys/time.h>
3 #include <libc.h>
4 #include <ip.h>
5 #include <bio.h>
6 #include <ndb.h>
7 #include "dns.h"
8 
9 enum
10 {
11 	Maxdest=	24,	/* maximum destinations for a request message */
12 	Maxtrans=	3	/* maximum transmissions to a server */
13 };
14 
15 static int	netquery(DN*, int, RR*, Request*, int);
16 static RR*	dnresolve1(char*, int, int, Request*, int, int);
17 
18 char *LOG = "dns";
19 
20 /*
21  *  lookup 'type' info for domain name 'name'.  If it doesn't exist, try
22  *  looking it up as a canonical name.
23  */
24 RR*
25 dnresolve(char *name, int class, int type, Request *req, RR **cn, int depth, int recurse, int rooted, int *status)
26 {
27 	RR *rp, *nrp, *drp;
28 	DN *dp;
29 	int loops;
30 	char nname[Domlen];
31 
32 	if(status)
33 		*status = 0;
34 
35 	/*
36 	 *  hack for systems that don't have resolve search
37 	 *  lists.  Just look up the simple name in the database.
38 	 */
39 	if(!rooted && strchr(name, '.') == 0){
40 		rp = nil;
41 		drp = domainlist(class);
42 		for(nrp = drp; nrp != nil; nrp = nrp->next){
43 			snprint(nname, sizeof(nname), "%s.%s", name, nrp->ptr->name);
44 			rp = dnresolve(nname, class, type, req,cn, depth, recurse, rooted, status);
45 			rrfreelist(rrremneg(&rp));
46 			if(rp != nil)
47 				break;
48 		}
49 		if(drp != nil)
50 			rrfree(drp);
51 		return rp;
52 	}
53 
54 	/*
55 	 *  try the name directly
56 	 */
57 	rp = dnresolve1(name, class, type, req, depth, recurse);
58 	if(rp)
59 		return randomize(rp);
60 
61 	/* try it as a canonical name if we weren't told the name didn't exist */
62 	dp = dnlookup(name, class, 0);
63 	if(type != Tptr && dp->nonexistent != Rname){
64 		for(loops=0; rp == nil && loops < 32; loops++){
65 			rp = dnresolve1(name, class, Tcname, req, depth, recurse);
66 			if(rp == nil)
67 				break;
68 
69 			if(rp->negative){
70 				rrfreelist(rp);
71 				rp = nil;
72 				break;
73 			}
74 
75 			name = rp->host->name;
76 			if(cn)
77 				rrcat(cn, rp);
78 			else
79 				rrfreelist(rp);
80 
81 			rp = dnresolve1(name, class, type, req, depth, recurse);
82 		}
83 	}
84 
85 	/* distinction between not found and not good */
86 	if(rp == 0 && status != 0 && dp->nonexistent != 0)
87 		*status = dp->nonexistent;
88 
89 	return randomize(rp);
90 }
91 
92 static RR*
93 dnresolve1(char *name, int class, int type, Request *req, int depth, int recurse)
94 {
95 	DN *dp, *nsdp;
96 	RR *rp, *nsrp, *dbnsrp;
97 	char *cp;
98 
99 	if(debug)
100 		syslog(0, LOG, "dnresolve1 %s %d %d", name, type, class);
101 
102 	/* only class Cin implemented so far */
103 	if(class != Cin)
104 		return 0;
105 
106 	dp = dnlookup(name, class, 1);
107 
108 	/*
109 	 *  Try the cache first
110 	 */
111 	rp = rrlookup(dp, type, OKneg);
112 	if(rp){
113 		if(rp->db){
114 			/* unauthenticated db entries are hints */
115 			if(rp->auth)
116 				return rp;
117 		} else {
118 			/* cached entry must still be valid */
119 			if(rp->ttl > now){
120 				/* but Tall entries are special */
121 				if(type != Tall || rp->query == Tall)
122 					return rp;
123 			}
124 		}
125 	}
126 	rrfreelist(rp);
127 
128 	/*
129 	 * try the cache for a canonical name. if found punt
130 	 * since we'll find it during the canonical name search
131 	 * in dnresolve().
132 	 */
133 	if(type != Tcname){
134 		rp = rrlookup(dp, Tcname, NOneg);
135 		rrfreelist(rp);
136 		if(rp)
137 			return 0;
138 	}
139 
140 	/*
141 	 *  if we're running as just a resolver, go to our
142 	 *  designated name servers
143 	 */
144 	if(resolver){
145 		nsrp = randomize(getdnsservers(class));
146 		if(nsrp != nil) {
147 			if(netquery(dp, type, nsrp, req, depth+1)){
148 				rrfreelist(nsrp);
149 				return rrlookup(dp, type, OKneg);
150 			}
151 			rrfreelist(nsrp);
152 		}
153 	}
154 
155 	/*
156  	 *  walk up the domain name looking for
157 	 *  a name server for the domain.
158 	 */
159 	for(cp = name; cp; cp = walkup(cp)){
160 		/*
161 		 *  if this is a local (served by us) domain,
162 		 *  return answer
163 		 */
164 		dbnsrp = randomize(dblookup(cp, class, Tns, 0, 0));
165 		if(dbnsrp && dbnsrp->local){
166 			rp = dblookup(name, class, type, 1, dbnsrp->ttl);
167 			rrfreelist(dbnsrp);
168 			return rp;
169 		}
170 
171 		/*
172 		 *  if recursion isn't set, just accept local
173 		 *  entries
174 		 */
175 		if(recurse == Dontrecurse){
176 			if(dbnsrp)
177 				rrfreelist(dbnsrp);
178 			continue;
179 		}
180 
181 		/* look for ns in cache */
182 		nsdp = dnlookup(cp, class, 0);
183 		nsrp = nil;
184 		if(nsdp)
185 			nsrp = randomize(rrlookup(nsdp, Tns, NOneg));
186 
187 		/* if the entry timed out, ignore it */
188 		if(nsrp && nsrp->ttl < now){
189 			rrfreelist(nsrp);
190 			nsrp = nil;
191 		}
192 
193 		if(nsrp){
194 			rrfreelist(dbnsrp);
195 
196 			/* try the name servers found in cache */
197 			if(netquery(dp, type, nsrp, req, depth+1)){
198 				rrfreelist(nsrp);
199 				return rrlookup(dp, type, OKneg);
200 			}
201 			rrfreelist(nsrp);
202 			continue;
203 		}
204 
205 		/* use ns from db */
206 		if(dbnsrp){
207 			/* try the name servers found in db */
208 			if(netquery(dp, type, dbnsrp, req, depth+1)){
209 				/* we got an answer */
210 				rrfreelist(dbnsrp);
211 				return rrlookup(dp, type, NOneg);
212 			}
213 			rrfreelist(dbnsrp);
214 		}
215 	}
216 
217 	/* settle for a non-authoritative answer */
218 	rp = rrlookup(dp, type, OKneg);
219 	if(rp)
220 		return rp;
221 
222 	/* noone answered.  try the database, we might have a chance. */
223 	return dblookup(name, class, type, 0, 0);
224 }
225 
226 /*
227  *  walk a domain name one element to the right.  return a pointer to that element.
228  *  in other words, return a pointer to the parent domain name.
229  */
230 char*
231 walkup(char *name)
232 {
233 	char *cp;
234 
235 	cp = strchr(name, '.');
236 	if(cp)
237 		return cp+1;
238 	else if(*name)
239 		return "";
240 	else
241 		return 0;
242 }
243 
244 /*
245  *  Get a udpport for requests and replies.
246  */
247 int
248 udpport(void)
249 {
250 	int fd;
251 
252 	if((fd = dial("udp!0!53", nil, nil, nil)) < 0)
253 		warning("can't get udp port");
254 	return fd;
255 }
256 
257 int
258 mkreq(DN *dp, int type, uchar *buf, int flags, ushort reqno)
259 {
260 	DNSmsg m;
261 	int len;
262 	Udphdr *uh = (Udphdr*)buf;
263 
264 	/* stuff port number into output buffer */
265 	memset(uh, 0, sizeof(*uh));
266 	hnputs(uh->rport, 53);
267 
268 	/* make request and convert it to output format */
269 	memset(&m, 0, sizeof(m));
270 	m.flags = flags;
271 	m.id = reqno;
272 	m.qd = rralloc(type);
273 	m.qd->owner = dp;
274 	m.qd->type = type;
275 	len = convDNS2M(&m, &buf[Udphdrsize], Maxudp);
276 	if(len < 0)
277 		abort(); /* "can't convert" */;
278 	rrfree(m.qd);
279 	return len;
280 }
281 
282 static void
283 freeanswers(DNSmsg *mp)
284 {
285 	rrfreelist(mp->qd);
286 	rrfreelist(mp->an);
287 	rrfreelist(mp->ns);
288 	rrfreelist(mp->ar);
289 }
290 
291 /*
292  *  read replies to a request.  ignore any of the wrong type.  wait at most 5 seconds.
293  */
294 static int udpreadtimeout(int, Udphdr*, void*, int, int);
295 static int
296 readreply(int fd, DN *dp, int type, ushort req,
297 	  uchar *ibuf, DNSmsg *mp, ulong endtime, Request *reqp)
298 {
299 	char *err;
300 	int len;
301 	ulong now;
302 	RR *rp;
303 
304 	for(; ; freeanswers(mp)){
305 		now = time(0);
306 		if(now >= endtime)
307 			return -1;	/* timed out */
308 
309 		/* timed read */
310 		len = udpreadtimeout(fd, (Udphdr*)ibuf, ibuf+Udphdrsize, Maxudpin, (endtime-now)*1000);
311 		if(len < 0)
312 			return -1;	/* timed out */
313 
314 		/* convert into internal format  */
315 		memset(mp, 0, sizeof(*mp));
316 		err = convM2DNS(&ibuf[Udphdrsize], len, mp);
317 		if(err){
318 			syslog(0, LOG, "input err %s: %I", err, ibuf);
319 			continue;
320 		}
321 		if(debug)
322 			logreply(reqp->id, ibuf, mp);
323 
324 		/* answering the right question? */
325 		if(mp->id != req){
326 			syslog(0, LOG, "%d: id %d instead of %d: %I", reqp->id,
327 					mp->id, req, ibuf);
328 			continue;
329 		}
330 		if(mp->qd == 0){
331 			syslog(0, LOG, "%d: no question RR: %I", reqp->id, ibuf);
332 			continue;
333 		}
334 		if(mp->qd->owner != dp){
335 			syslog(0, LOG, "%d: owner %s instead of %s: %I", reqp->id,
336 				mp->qd->owner->name, dp->name, ibuf);
337 			continue;
338 		}
339 		if(mp->qd->type != type){
340 			syslog(0, LOG, "%d: type %d instead of %d: %I", reqp->id,
341 				mp->qd->type, type, ibuf);
342 			continue;
343 		}
344 
345 		/* remember what request this is in answer to */
346 		for(rp = mp->an; rp; rp = rp->next)
347 			rp->query = type;
348 
349 		return 0;
350 	}
351 
352 	return 0;	/* never reached */
353 }
354 
355 static int
356 udpreadtimeout(int fd, Udphdr *h, void *data, int n, int ms)
357 {
358 	fd_set rd;
359 	struct timeval tv;
360 
361 	FD_ZERO(&rd);
362 	FD_SET(fd, &rd);
363 
364 	tv.tv_sec = ms/1000;
365 	tv.tv_usec = (ms%1000)*1000;
366 
367 	if(select(fd+1, &rd, 0, 0, &tv) != 1)
368 		return -1;
369 	return udpread(fd, h, data, n);
370 }
371 
372 /*
373  *	return non-0 if first list includes second list
374  */
375 int
376 contains(RR *rp1, RR *rp2)
377 {
378 	RR *trp1, *trp2;
379 
380 	for(trp2 = rp2; trp2; trp2 = trp2->next){
381 		for(trp1 = rp1; trp1; trp1 = trp1->next){
382 			if(trp1->type == trp2->type)
383 			if(trp1->host == trp2->host)
384 			if(trp1->owner == trp2->owner)
385 				break;
386 		}
387 		if(trp1 == 0)
388 			return 0;
389 	}
390 
391 	return 1;
392 }
393 
394 
395 typedef struct Dest	Dest;
396 struct Dest
397 {
398 	uchar	a[IPaddrlen];	/* ip address */
399 	DN	*s;		/* name server */
400 	int	nx;		/* number of transmissions */
401 	int	code;
402 };
403 
404 
405 /*
406  *  return multicast version if any
407  */
408 int
409 ipisbm(uchar *ip)
410 {
411 	if(isv4(ip)){
412 		if(ip[IPv4off] >= 0xe0 && ip[IPv4off] < 0xf0)
413 			return 4;
414 		if(ipcmp(ip, IPv4bcast) == 0)
415 			return 4;
416 	} else {
417 		if(ip[0] == 0xff)
418 			return 6;
419 	}
420 	return 0;
421 }
422 
423 /*
424  *  Get next server address
425  */
426 static int
427 serveraddrs(RR *nsrp, Dest *dest, int nd, int depth, Request *reqp)
428 {
429 	RR *rp, *arp, *trp;
430 	Dest *cur;
431 
432 	if(nd >= Maxdest)
433 		return 0;
434 
435 	/*
436 	 *  look for a server whose address we already know.
437 	 *  if we find one, mark it so we ignore this on
438 	 *  subsequent passes.
439 	 */
440 	arp = 0;
441 	for(rp = nsrp; rp; rp = rp->next){
442 		assert(rp->magic == RRmagic);
443 		if(rp->marker)
444 			continue;
445 		arp = rrlookup(rp->host, Ta, NOneg);
446 		if(arp){
447 			rp->marker = 1;
448 			break;
449 		}
450 		arp = dblookup(rp->host->name, Cin, Ta, 0, 0);
451 		if(arp){
452 			rp->marker = 1;
453 			break;
454 		}
455 	}
456 
457 	/*
458 	 *  if the cache and database lookup didn't find any new
459 	 *  server addresses, try resolving one via the network.
460 	 *  Mark any we try to resolve so we don't try a second time.
461 	 */
462 	if(arp == 0){
463 		for(rp = nsrp; rp; rp = rp->next){
464 			if(rp->marker)
465 				continue;
466 			rp->marker = 1;
467 
468 			/*
469 			 *  avoid loops looking up a server under itself
470 			 */
471 			if(subsume(rp->owner->name, rp->host->name))
472 				continue;
473 
474 			arp = dnresolve(rp->host->name, Cin, Ta, reqp, 0, depth+1, Recurse, 1, 0);
475 			rrfreelist(rrremneg(&arp));
476 			if(arp)
477 				break;
478 		}
479 	}
480 
481 	/* use any addresses that we found */
482 	for(trp = arp; trp; trp = trp->next){
483 		if(nd >= Maxdest)
484 			break;
485 		cur = &dest[nd];
486 		parseip(cur->a, trp->ip->name);
487 		if(ipisbm(cur->a))
488 			continue;
489 		cur->nx = 0;
490 		cur->s = trp->owner;
491 		cur->code = Rtimeout;
492 		nd++;
493 	}
494 	rrfreelist(arp);
495 	return nd;
496 }
497 
498 /*
499  *  cache negative responses
500  */
501 static void
502 cacheneg(DN *dp, int type, int rcode, RR *soarr)
503 {
504 	RR *rp;
505 	DN *soaowner;
506 	ulong ttl;
507 
508 	/* no cache time specified, don' make anything up */
509 	if(soarr != nil){
510 		if(soarr->next != nil){
511 			rrfreelist(soarr->next);
512 			soarr->next = nil;
513 		}
514 		soaowner = soarr->owner;
515 	} else
516 		soaowner = nil;
517 
518 	/* the attach can cause soarr to be freed so mine it now */
519 	if(soarr != nil && soarr->soa != nil)
520 		ttl = soarr->soa->minttl+now;
521 	else
522 		ttl = 5*Min;
523 
524 	/* add soa and negative RR to the database */
525 	rrattach(soarr, 1);
526 
527 	rp = rralloc(type);
528 	rp->owner = dp;
529 	rp->negative = 1;
530 	rp->negsoaowner = soaowner;
531 	rp->negrcode = rcode;
532 	rp->ttl = ttl;
533 	rrattach(rp, 1);
534 }
535 
536 /*
537  *  query name servers.  If the name server returns a pointer to another
538  *  name server, recurse.
539  */
540 static int
541 netquery1(int fd, DN *dp, int type, RR *nsrp, Request *reqp, int depth, uchar *ibuf, uchar *obuf)
542 {
543 	int ndest, j, len, replywaits, rv;
544 	ushort req;
545 	RR *tp, *soarr;
546 	Dest *p, *l, *np;
547 	DN *ndp;
548 	Dest dest[Maxdest];
549 	DNSmsg m;
550 	ulong endtime;
551 	Udphdr *uh;
552 
553 	/* pack request into a message */
554 	req = rand();
555 	len = mkreq(dp, type, obuf, Frecurse|Oquery, req);
556 
557 	/* no server addresses yet */
558 	l = dest;
559 
560 	/*
561 	 *  transmit requests and wait for answers.
562 	 *  at most Maxtrans attempts to each address.
563 	 *  each cycle send one more message than the previous.
564 	 */
565 	for(ndest = 1; ndest < Maxdest; ndest++){
566 		p = dest;
567 
568 		endtime = time(0);
569 		if(endtime >= reqp->aborttime)
570 			break;
571 
572 		/* get a server address if we need one */
573 		if(ndest > l - p){
574 			j = serveraddrs(nsrp, dest, l - p, depth, reqp);
575 			l = &dest[j];
576 		}
577 
578 		/* no servers, punt */
579 		if(l == dest)
580 			break;
581 
582 		/* send to first 'ndest' destinations */
583 		j = 0;
584 		for(; p < &dest[ndest] && p < l; p++){
585 			/* skip destinations we've finished with */
586 			if(p->nx >= Maxtrans)
587 				continue;
588 
589 			j++;
590 
591 			/* exponential backoff of requests */
592 			if((1<<p->nx) > ndest)
593 				continue;
594 
595 			memmove(obuf, p->a, sizeof(p->a));
596 			if(debug)
597 				logsend(reqp->id, depth, obuf, p->s->name,
598 					dp->name, type);
599 			uh = (Udphdr*)obuf;
600 			fprint(2, "send %I %I %d %d\n", uh->raddr, uh->laddr, nhgets(uh->rport), nhgets(uh->lport));
601 			if(udpwrite(fd, uh, obuf+Udphdrsize, len) < 0)
602 				warning("sending udp msg %r");
603 			p->nx++;
604 		}
605 		if(j == 0)
606 			break;		/* no destinations left */
607 
608 		/* wait up to 5 seconds for replies */
609 		endtime = time(0) + 5;
610 		if(endtime > reqp->aborttime)
611 			endtime = reqp->aborttime;
612 
613 		for(replywaits = 0; replywaits < ndest; replywaits++){
614 			if(readreply(fd, dp, type, req, ibuf, &m, endtime, reqp) < 0)
615 				break;		/* timed out */
616 
617 			/* find responder */
618 			for(p = dest; p < l; p++)
619 				if(memcmp(p->a, ibuf, sizeof(p->a)) == 0)
620 					break;
621 
622 			/* remove all addrs of responding server from list */
623 			for(np = dest; np < l; np++)
624 				if(np->s == p->s)
625 					p->nx = Maxtrans;
626 
627 			/* ignore any error replies */
628 			if((m.flags & Rmask) == Rserver){
629 				rrfreelist(m.qd);
630 				rrfreelist(m.an);
631 				rrfreelist(m.ar);
632 				rrfreelist(m.ns);
633 				if(p != l)
634 					p->code = Rserver;
635 				continue;
636 			}
637 
638 			/* ignore any bad delegations */
639 			if(m.ns && baddelegation(m.ns, nsrp, ibuf)){
640 				rrfreelist(m.ns);
641 				m.ns = nil;
642 				if(m.an == nil){
643 					rrfreelist(m.qd);
644 					rrfreelist(m.ar);
645 					if(p != l)
646 						p->code = Rserver;
647 					continue;
648 				}
649 			}
650 
651 
652 			/* remove any soa's from the authority section */
653 			soarr = rrremtype(&m.ns, Tsoa);
654 
655 			/* incorporate answers */
656 			if(m.an)
657 				rrattach(m.an, (m.flags & Fauth) ? 1 : 0);
658 			if(m.ar)
659 				rrattach(m.ar, 0);
660 			if(m.ns){
661 				ndp = m.ns->owner;
662 				rrattach(m.ns, 0);
663 			} else
664 				ndp = 0;
665 
666 			/* free the question */
667 			if(m.qd)
668 				rrfreelist(m.qd);
669 
670 			/*
671 			 *  Any reply from an authoritative server,
672 			 *  or a positive reply terminates the search
673 			 */
674 			if(m.an != nil || (m.flags & Fauth)){
675 				if(m.an == nil && (m.flags & Rmask) == Rname)
676 					dp->nonexistent = Rname;
677 				else
678 					dp->nonexistent = 0;
679 
680 				/*
681 				 *  cache any negative responses, free soarr
682 				 */
683 				if((m.flags & Fauth) && m.an == nil)
684 					cacheneg(dp, type, (m.flags & Rmask), soarr);
685 				else
686 					rrfreelist(soarr);
687 				return 1;
688 			}
689 			rrfreelist(soarr);
690 
691 			/*
692 			 *  if we've been given better name servers
693 			 *  recurse
694 			 */
695 			if(m.ns){
696 				tp = rrlookup(ndp, Tns, NOneg);
697 				if(!contains(nsrp, tp)){
698 					rv = netquery(dp, type, tp, reqp, depth+1);
699 					rrfreelist(tp);
700 					return rv;
701 				} else
702 					rrfreelist(tp);
703 			}
704 		}
705 	}
706 
707 	/* if all servers returned failure, propogate it */
708 	dp->nonexistent = Rserver;
709 	for(p = dest; p < l; p++)
710 		if(p->code != Rserver)
711 			dp->nonexistent = 0;
712 
713 	return 0;
714 }
715 
716 typedef struct Qarg Qarg;
717 struct Qarg
718 {
719 	DN *dp;
720 	int type;
721 	RR *nsrp;
722 	Request *reqp;
723 	int depth;
724 };
725 
726 
727 static int
728 netquery(DN *dp, int type, RR *nsrp, Request *reqp, int depth)
729 {
730 	uchar *obuf;
731 	uchar *ibuf;
732 	RR *rp;
733 	int fd, rv;
734 
735 	if(depth > 12)
736 		return 0;
737 
738 	/* use alloced buffers rather than ones from the stack */
739 	ibuf = emalloc(Maxudpin+Udphdrsize);
740 	obuf = emalloc(Maxudp+Udphdrsize);
741 
742 	/* prepare server RR's for incremental lookup */
743 	for(rp = nsrp; rp; rp = rp->next)
744 		rp->marker = 0;
745 
746 	fd = udpport();
747 	if(fd < 0)
748 		return 0;
749 	rv = netquery1(fd, dp, type, nsrp, reqp, depth, ibuf, obuf);
750 	close(fd);
751 	free(ibuf);
752 	free(obuf);
753 
754 	return rv;
755 }