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