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 	OUdphdr *uh = (OUdphdr*)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[OUdphdrsize], Maxudp);
275 	if(len < 0)
276 		abort(); /* "can't convert" */;
277 	rrfree(m.qd);
278 	return len;
279 }
280 
281 /* for alarms in readreply */
282 static void
283 ding(void *x, char *msg)
284 {
285 	USED(x);
286 	if(strcmp(msg, "alarm") == 0)
287 		noted(NCONT);
288 	else
289 		noted(NDFLT);
290 }
291 
292 static void
293 freeanswers(DNSmsg *mp)
294 {
295 	rrfreelist(mp->qd);
296 	rrfreelist(mp->an);
297 	rrfreelist(mp->ns);
298 	rrfreelist(mp->ar);
299 }
300 
301 /*
302  *  read replies to a request.  ignore any of the wrong type.  wait at most 5 seconds.
303  */
304 static int
305 readreply(int fd, DN *dp, int type, ushort req,
306 	  uchar *ibuf, DNSmsg *mp, ulong endtime, Request *reqp)
307 {
308 	char *err;
309 	int len;
310 	ulong now;
311 	RR *rp;
312 
313 	notify(ding);
314 
315 	for(; ; freeanswers(mp)){
316 		now = time(0);
317 		if(now >= endtime)
318 			return -1;	/* timed out */
319 
320 		/* timed read */
321 		alarm((endtime - now) * 1000);
322 		len = udpread(fd, (OUdphdr*)ibuf, ibuf+OUdphdrsize, Maxudpin);
323 		alarm(0);
324 		if(len < 0)
325 			return -1;	/* timed out */
326 		
327 		/* convert into internal format  */
328 		memset(mp, 0, sizeof(*mp));
329 		err = convM2DNS(&ibuf[OUdphdrsize], len, mp);
330 		if(err){
331 			syslog(0, LOG, "input err %s: %I", err, ibuf);
332 			continue;
333 		}
334 		if(debug)
335 			logreply(reqp->id, ibuf, mp);
336 
337 		/* answering the right question? */
338 		if(mp->id != req){
339 			syslog(0, LOG, "%d: id %d instead of %d: %I", reqp->id,
340 					mp->id, req, ibuf);
341 			continue;
342 		}
343 		if(mp->qd == 0){
344 			syslog(0, LOG, "%d: no question RR: %I", reqp->id, ibuf);
345 			continue;
346 		}
347 		if(mp->qd->owner != dp){
348 			syslog(0, LOG, "%d: owner %s instead of %s: %I", reqp->id,
349 				mp->qd->owner->name, dp->name, ibuf);
350 			continue;
351 		}
352 		if(mp->qd->type != type){
353 			syslog(0, LOG, "%d: type %d instead of %d: %I", reqp->id,
354 				mp->qd->type, type, ibuf);
355 			continue;
356 		}
357 
358 		/* remember what request this is in answer to */
359 		for(rp = mp->an; rp; rp = rp->next)
360 			rp->query = type;
361 
362 		return 0;
363 	}
364 
365 	return 0;	/* never reached */
366 }
367 
368 /*
369  *	return non-0 if first list includes second list
370  */
371 int
372 contains(RR *rp1, RR *rp2)
373 {
374 	RR *trp1, *trp2;
375 
376 	for(trp2 = rp2; trp2; trp2 = trp2->next){
377 		for(trp1 = rp1; trp1; trp1 = trp1->next){
378 			if(trp1->type == trp2->type)
379 			if(trp1->host == trp2->host)
380 			if(trp1->owner == trp2->owner)
381 				break;
382 		}
383 		if(trp1 == 0)
384 			return 0;
385 	}
386 
387 	return 1;
388 }
389 
390 
391 typedef struct Dest	Dest;
392 struct Dest
393 {
394 	uchar	a[IPaddrlen];	/* ip address */
395 	DN	*s;		/* name server */
396 	int	nx;		/* number of transmissions */
397 	int	code;
398 };
399 
400 
401 /*
402  *  return multicast version if any
403  */
404 int
405 ipisbm(uchar *ip)
406 {
407 	if(isv4(ip)){
408 		if(ip[IPv4off] >= 0xe0 && ip[IPv4off] < 0xf0)
409 			return 4;
410 		if(ipcmp(ip, IPv4bcast) == 0)
411 			return 4;
412 	} else {
413 		if(ip[0] == 0xff)
414 			return 6;
415 	}
416 	return 0;
417 }
418 
419 /*
420  *  Get next server address
421  */
422 static int
423 serveraddrs(RR *nsrp, Dest *dest, int nd, int depth, Request *reqp)
424 {
425 	RR *rp, *arp, *trp;
426 	Dest *cur;
427 
428 	if(nd >= Maxdest)
429 		return 0;
430 
431 	/*
432 	 *  look for a server whose address we already know.
433 	 *  if we find one, mark it so we ignore this on
434 	 *  subsequent passes.
435 	 */
436 	arp = 0;
437 	for(rp = nsrp; rp; rp = rp->next){
438 		assert(rp->magic == RRmagic);
439 		if(rp->marker)
440 			continue;
441 		arp = rrlookup(rp->host, Ta, NOneg);
442 		if(arp){
443 			rp->marker = 1;
444 			break;
445 		}
446 		arp = dblookup(rp->host->name, Cin, Ta, 0, 0);
447 		if(arp){
448 			rp->marker = 1;
449 			break;
450 		}
451 	}
452 
453 	/*
454 	 *  if the cache and database lookup didn't find any new
455 	 *  server addresses, try resolving one via the network.
456 	 *  Mark any we try to resolve so we don't try a second time.
457 	 */
458 	if(arp == 0){
459 		for(rp = nsrp; rp; rp = rp->next){
460 			if(rp->marker)
461 				continue;
462 			rp->marker = 1;
463 
464 			/*
465 			 *  avoid loops looking up a server under itself
466 			 */
467 			if(subsume(rp->owner->name, rp->host->name))
468 				continue;
469 
470 			arp = dnresolve(rp->host->name, Cin, Ta, reqp, 0, depth+1, Recurse, 1, 0);
471 			rrfreelist(rrremneg(&arp));
472 			if(arp)
473 				break;
474 		}
475 	}
476 
477 	/* use any addresses that we found */
478 	for(trp = arp; trp; trp = trp->next){
479 		if(nd >= Maxdest)
480 			break;
481 		cur = &dest[nd];
482 		parseip(cur->a, trp->ip->name);
483 		if(ipisbm(cur->a))
484 			continue;
485 		cur->nx = 0;
486 		cur->s = trp->owner;
487 		cur->code = Rtimeout;
488 		nd++;
489 	}
490 	rrfreelist(arp);
491 	return nd;
492 }
493 
494 /*
495  *  cache negative responses
496  */
497 static void
498 cacheneg(DN *dp, int type, int rcode, RR *soarr)
499 {
500 	RR *rp;
501 	DN *soaowner;
502 	ulong ttl;
503 
504 	/* no cache time specified, don' make anything up */
505 	if(soarr != nil){
506 		if(soarr->next != nil){
507 			rrfreelist(soarr->next);
508 			soarr->next = nil;
509 		}
510 		soaowner = soarr->owner;
511 	} else 
512 		soaowner = nil;
513 
514 	/* the attach can cause soarr to be freed so mine it now */
515 	if(soarr != nil && soarr->soa != nil)
516 		ttl = soarr->soa->minttl+now;
517 	else
518 		ttl = 5*Min;
519 
520 	/* add soa and negative RR to the database */
521 	rrattach(soarr, 1);
522 
523 	rp = rralloc(type);
524 	rp->owner = dp;
525 	rp->negative = 1;
526 	rp->negsoaowner = soaowner;
527 	rp->negrcode = rcode;
528 	rp->ttl = ttl;
529 	rrattach(rp, 1);
530 }
531 
532 /*
533  *  query name servers.  If the name server returns a pointer to another
534  *  name server, recurse.
535  */
536 static int
537 netquery1(int fd, DN *dp, int type, RR *nsrp, Request *reqp, int depth, uchar *ibuf, uchar *obuf)
538 {
539 	int ndest, j, len, replywaits, rv;
540 	ushort req;
541 	RR *tp, *soarr;
542 	Dest *p, *l, *np;
543 	DN *ndp;
544 	Dest dest[Maxdest];
545 	DNSmsg m;
546 	ulong endtime;
547 
548 	/* pack request into a message */
549 	req = rand();
550 	len = mkreq(dp, type, obuf, Frecurse|Oquery, req);
551 
552 	/* no server addresses yet */
553 	l = dest;
554 
555 	/*
556 	 *  transmit requests and wait for answers.
557 	 *  at most Maxtrans attempts to each address.
558 	 *  each cycle send one more message than the previous.
559 	 */
560 	for(ndest = 1; ndest < Maxdest; ndest++){
561 		p = dest;
562 
563 		endtime = time(0);
564 		if(endtime >= reqp->aborttime)
565 			break;
566 
567 		/* get a server address if we need one */
568 		if(ndest > l - p){
569 			j = serveraddrs(nsrp, dest, l - p, depth, reqp);
570 			l = &dest[j];
571 		}
572 
573 		/* no servers, punt */
574 		if(l == dest)
575 			break;
576 
577 		/* send to first 'ndest' destinations */
578 		j = 0;
579 		for(; p < &dest[ndest] && p < l; p++){
580 			/* skip destinations we've finished with */
581 			if(p->nx >= Maxtrans)
582 				continue;
583 
584 			j++;
585 
586 			/* exponential backoff of requests */
587 			if((1<<p->nx) > ndest)
588 				continue;
589 
590 			memmove(obuf, p->a, sizeof(p->a));
591 			if(debug)
592 				logsend(reqp->id, depth, obuf, p->s->name,
593 					dp->name, type);
594 {Udphdr *uh = (Udphdr*)obuf;
595 print("send %I %I %d %d\n", uh->raddr, uh->laddr, nhgets(uh->rport), nhgets(uh->lport));
596 }
597 			if(udpwrite(fd, (OUdphdr*)obuf, obuf+OUdphdrsize, len) < 0)
598 				warning("sending udp msg %r");
599 			p->nx++;
600 		}
601 		if(j == 0)
602 			break;		/* no destinations left */
603 
604 		/* wait up to 5 seconds for replies */
605 		endtime = time(0) + 5;
606 		if(endtime > reqp->aborttime)
607 			endtime = reqp->aborttime;
608 
609 		for(replywaits = 0; replywaits < ndest; replywaits++){
610 			if(readreply(fd, dp, type, req, ibuf, &m, endtime, reqp) < 0)
611 				break;		/* timed out */
612 
613 			/* find responder */
614 			for(p = dest; p < l; p++)
615 				if(memcmp(p->a, ibuf, sizeof(p->a)) == 0)
616 					break;
617 
618 			/* remove all addrs of responding server from list */
619 			for(np = dest; np < l; np++)
620 				if(np->s == p->s)
621 					p->nx = Maxtrans;
622 
623 			/* ignore any error replies */
624 			if((m.flags & Rmask) == Rserver){
625 				rrfreelist(m.qd);
626 				rrfreelist(m.an);
627 				rrfreelist(m.ar);
628 				rrfreelist(m.ns);
629 				if(p != l)
630 					p->code = Rserver;
631 				continue;
632 			}
633 
634 			/* ignore any bad delegations */
635 			if(m.ns && baddelegation(m.ns, nsrp, ibuf)){
636 				rrfreelist(m.ns);
637 				m.ns = nil;
638 				if(m.an == nil){
639 					rrfreelist(m.qd);
640 					rrfreelist(m.ar);
641 					if(p != l)
642 						p->code = Rserver;
643 					continue;
644 				}
645 			}
646 
647 
648 			/* remove any soa's from the authority section */
649 			soarr = rrremtype(&m.ns, Tsoa);
650 
651 			/* incorporate answers */
652 			if(m.an)
653 				rrattach(m.an, (m.flags & Fauth) ? 1 : 0);
654 			if(m.ar)
655 				rrattach(m.ar, 0);
656 			if(m.ns){
657 				ndp = m.ns->owner;
658 				rrattach(m.ns, 0);
659 			} else
660 				ndp = 0;
661 
662 			/* free the question */
663 			if(m.qd)
664 				rrfreelist(m.qd);
665 
666 			/*
667 			 *  Any reply from an authoritative server,
668 			 *  or a positive reply terminates the search
669 			 */
670 			if(m.an != nil || (m.flags & Fauth)){
671 				if(m.an == nil && (m.flags & Rmask) == Rname)
672 					dp->nonexistent = Rname;
673 				else
674 					dp->nonexistent = 0;
675 
676 				/*
677 				 *  cache any negative responses, free soarr
678 				 */
679 				if((m.flags & Fauth) && m.an == nil)
680 					cacheneg(dp, type, (m.flags & Rmask), soarr);
681 				else
682 					rrfreelist(soarr);
683 				return 1;
684 			}
685 			rrfreelist(soarr);
686 
687 			/*
688 			 *  if we've been given better name servers
689 			 *  recurse
690 			 */
691 			if(m.ns){
692 				tp = rrlookup(ndp, Tns, NOneg);
693 				if(!contains(nsrp, tp)){
694 					rv = netquery(dp, type, tp, reqp, depth+1);
695 					rrfreelist(tp);
696 					return rv;
697 				} else
698 					rrfreelist(tp);
699 			}
700 		}
701 	}
702 
703 	/* if all servers returned failure, propogate it */
704 	dp->nonexistent = Rserver;
705 	for(p = dest; p < l; p++)
706 		if(p->code != Rserver)
707 			dp->nonexistent = 0;
708 
709 	return 0;
710 }
711 
712 typedef struct Qarg Qarg;
713 struct Qarg
714 {
715 	DN *dp;
716 	int type;
717 	RR *nsrp;
718 	Request *reqp;
719 	int depth;
720 };
721 
722 
723 static int
724 netquery(DN *dp, int type, RR *nsrp, Request *reqp, int depth)
725 {
726 	uchar *obuf;
727 	uchar *ibuf;
728 	RR *rp;
729 	int fd, rv;
730 
731 	if(depth > 12)
732 		return 0;
733 
734 	/* use alloced buffers rather than ones from the stack */
735 	ibuf = emalloc(Maxudpin+OUdphdrsize);
736 	obuf = emalloc(Maxudp+OUdphdrsize);
737 
738 	slave(reqp);
739 
740 	/* prepare server RR's for incremental lookup */
741 	for(rp = nsrp; rp; rp = rp->next)
742 		rp->marker = 0;
743 
744 	fd = udpport();
745 	if(fd < 0)
746 		return 0;
747 	rv = netquery1(fd, dp, type, nsrp, reqp, depth, ibuf, obuf);
748 	close(fd);
749 	free(ibuf);
750 	free(obuf);
751 
752 	return rv;
753 }