1 #include <u.h>
2 #include <libc.h>
3 #include <ip.h>
4 #include <ctype.h>
5 #include <bio.h>
6 #include <ndb.h>
7 #include <thread.h>
8 #include "dns.h"
9 
10 /*
11  *  Hash table for domain names.  The hash is based only on the
12  *  first element of the domain name.
13  */
14 DN	*ht[HTLEN];
15 
16 
17 static struct
18 {
19 	Lock	lk;
20 	ulong	names;	/* names allocated */
21 	ulong	oldest;	/* longest we'll leave a name around */
22 	int	active;
23 	int	mutex;
24 	int	id;
25 } dnvars;
26 
27 /* names of RR types */
28 char *rrtname[Tall+2] =
29 {
30 	nil,
31 	"ip",
32 	"ns",
33 	"md",
34 	"mf",
35 	"cname",
36 	"soa",
37 	"mb",
38 	"mg",
39 	"mr",
40 	"null",
41 	"wks",
42 	"ptr",
43 	"hinfo",
44 	"minfo",
45 	"mx",
46 	"txt",
47 	"rp",
48 	nil,
49 	nil,
50 	nil,
51 	nil,
52 	nil,
53 	nil,
54 	"sig",
55 	"key",
56 	nil,
57 	nil,
58 	"aaaa",
59 	nil,
60 	nil,
61 	nil,
62 	nil,
63 	nil,
64 	nil,
65 	nil,
66 	nil,
67 	"cert",
68 	nil,
69 	nil,
70 
71 /* 40 */	nil, nil, nil, nil, nil, nil, nil, nil,
72 /* 48 */	nil, nil, nil, nil, nil, nil, nil, nil,
73 /* 56 */	nil, nil, nil, nil, nil, nil, nil, nil,
74 /* 64 */	nil, nil, nil, nil, nil, nil, nil, nil,
75 /* 72 */	nil, nil, nil, nil, nil, nil, nil, nil,
76 /* 80 */	nil, nil, nil, nil, nil, nil, nil, nil,
77 /* 88 */	nil, nil, nil, nil, nil, nil, nil, nil,
78 /* 96 */	nil, nil, nil, nil, nil, nil, nil, nil,
79 /* 104 */	nil, nil, nil, nil, nil, nil, nil, nil,
80 /* 112 */	nil, nil, nil, nil, nil, nil, nil, nil,
81 /* 120 */	nil, nil, nil, nil, nil, nil, nil, nil,
82 /* 128 */	nil, nil, nil, nil, nil, nil, nil, nil,
83 /* 136 */	nil, nil, nil, nil, nil, nil, nil, nil,
84 /* 144 */	nil, nil, nil, nil, nil, nil, nil, nil,
85 /* 152 */	nil, nil, nil, nil, nil, nil, nil, nil,
86 /* 160 */	nil, nil, nil, nil, nil, nil, nil, nil,
87 /* 168 */	nil, nil, nil, nil, nil, nil, nil, nil,
88 /* 176 */	nil, nil, nil, nil, nil, nil, nil, nil,
89 /* 184 */	nil, nil, nil, nil, nil, nil, nil, nil,
90 /* 192 */	nil, nil, nil, nil, nil, nil, nil, nil,
91 /* 200 */	nil, nil, nil, nil, nil, nil, nil, nil,
92 /* 208 */	nil, nil, nil, nil, nil, nil, nil, nil,
93 /* 216 */	nil, nil, nil, nil, nil, nil, nil, nil,
94 /* 224 */	nil, nil, nil, nil, nil, nil, nil, nil,
95 /* 232 */	nil, nil, nil, nil, nil, nil, nil, nil,
96 /* 240 */	nil, nil, nil, nil, nil, nil, nil, nil,
97 /* 248 */	nil, nil, nil,
98 
99 	"ixfr",
100 	"axfr",
101 	"mailb",
102 	nil,
103 	"all",
104 	nil
105 };
106 
107 /* names of response codes */
108 char *rname[Rmask+1] =
109 {
110 	"ok",
111 	"format error",
112 	"server failure",
113 	"bad name",
114 	"unimplemented",
115 	"we don't like you"
116 };
117 
118 Lock	dnlock;
119 
120 static int sencodefmt(Fmt*);
121 
122 /*
123  *  set up a pipe to use as a lock
124  */
125 void
126 dninit(void)
127 {
128 	fmtinstall('E', eipfmt);
129 	fmtinstall('I', eipfmt);
130 	fmtinstall('V', eipfmt);
131 	fmtinstall('R', rrfmt);
132 	fmtinstall('Q', rravfmt);
133 	fmtinstall('H', sencodefmt);
134 
135 	dnvars.oldest = maxage;
136 	dnvars.names = 0;
137 }
138 
139 /*
140  *  hash for a domain name
141  */
142 static ulong
143 dnhash(char *name)
144 {
145 	ulong hash;
146 	uchar *val = (uchar*)name;
147 
148 	for(hash = 0; *val; val++)
149 		hash = (hash*13) + tolower(*val)-'a';
150 	return hash % HTLEN;
151 }
152 
153 /*
154  *  lookup a symbol.  if enter is not zero and the name is
155  *  not found, create it.
156  */
157 DN*
158 dnlookup(char *name, int class, int enter)
159 {
160 	DN **l;
161 	DN *dp;
162 
163 	l = &ht[dnhash(name)];
164 	lock(&dnlock);
165 	for(dp = *l; dp; dp = dp->next) {
166 		assert(dp->magic == DNmagic);
167 		if(dp->class == class && cistrcmp(dp->name, name) == 0){
168 			dp->referenced = now;
169 			unlock(&dnlock);
170 			return dp;
171 		}
172 		l = &dp->next;
173 	}
174 	if(enter == 0){
175 		unlock(&dnlock);
176 		return 0;
177 	}
178 	dnvars.names++;
179 	dp = emalloc(sizeof(*dp));
180 	dp->magic = DNmagic;
181 	dp->name = estrdup(name);
182 	assert(dp->name != 0);
183 	dp->class = class;
184 	dp->rr = 0;
185 	dp->next = 0;
186 	dp->referenced = now;
187 	*l = dp;
188 	unlock(&dnlock);
189 
190 	return dp;
191 }
192 
193 /*
194  *  dump the cache
195  */
196 void
197 dndump(char *file)
198 {
199 	DN *dp;
200 	int i, fd;
201 	RR *rp;
202 
203 	fd = open(file, OWRITE|OTRUNC);
204 	if(fd < 0)
205 		return;
206 	lock(&dnlock);
207 	for(i = 0; i < HTLEN; i++){
208 		for(dp = ht[i]; dp; dp = dp->next){
209 			fprint(fd, "%s\n", dp->name);
210 			for(rp = dp->rr; rp; rp = rp->next)
211 				fprint(fd, "	%R %c%c %lud/%lud\n", rp, rp->auth?'A':'U',
212 					rp->db?'D':'N', rp->expire, rp->ttl);
213 		}
214 	}
215 	unlock(&dnlock);
216 	close(fd);
217 }
218 
219 /*
220  *  purge all records
221  */
222 void
223 dnpurge(void)
224 {
225 	DN *dp;
226 	RR *rp, *srp;
227 	int i;
228 
229 	lock(&dnlock);
230 
231 	for(i = 0; i < HTLEN; i++)
232 		for(dp = ht[i]; dp; dp = dp->next){
233 			srp = rp = dp->rr;
234 			dp->rr = nil;
235 			for(; rp != nil; rp = rp->next)
236 				rp->cached = 0;
237 			rrfreelist(srp);
238 		}
239 
240 	unlock(&dnlock);
241 }
242 
243 /*
244  *  check the age of resource records, free any that have timed out
245  */
246 void
247 dnage(DN *dp)
248 {
249 	RR **l;
250 	RR *rp, *next;
251 	ulong diff;
252 
253 	diff = now - dp->referenced;
254 	if(diff < Reserved)
255 		return;
256 
257 	l = &dp->rr;
258 	for(rp = dp->rr; rp; rp = next){
259 		assert(rp->magic == RRmagic && rp->cached);
260 		next = rp->next;
261 		if(!rp->db)
262 		if(rp->expire < now || diff > dnvars.oldest){
263 			*l = next;
264 			rp->cached = 0;
265 			rrfree(rp);
266 			continue;
267 		}
268 		l = &rp->next;
269 	}
270 }
271 
272 #define REF(x) if(x) x->refs++
273 
274 /*
275  *  our target is 4000 names cached, this should be larger on large servers
276  */
277 #define TARGET 4000
278 
279 /*
280  *  periodicly sweep for old records and remove unreferenced domain names
281  *
282  *  only called when all other threads are locked out
283  */
284 void
285 dnageall(int doit)
286 {
287 	DN *dp, **l;
288 	int i;
289 	RR *rp;
290 	static ulong nextage;
291 
292 	if(dnvars.names < TARGET && now < nextage && !doit){
293 		dnvars.oldest = maxage;
294 		return;
295 	}
296 
297 	if(dnvars.names > TARGET)
298 		dnvars.oldest /= 2;
299 	nextage = now + maxage;
300 
301 	lock(&dnlock);
302 
303 	/* time out all old entries (and set refs to 0) */
304 	for(i = 0; i < HTLEN; i++)
305 		for(dp = ht[i]; dp; dp = dp->next){
306 			dp->refs = 0;
307 			dnage(dp);
308 		}
309 
310 	/* mark all referenced domain names */
311 	for(i = 0; i < HTLEN; i++)
312 		for(dp = ht[i]; dp; dp = dp->next)
313 			for(rp = dp->rr; rp; rp = rp->next){
314 				REF(rp->owner);
315 				if(rp->negative){
316 					REF(rp->negsoaowner);
317 					continue;
318 				}
319 				switch(rp->type){
320 				case Thinfo:
321 					REF(rp->cpu);
322 					REF(rp->os);
323 					break;
324 				case Ttxt:
325 					break;
326 				case Tcname:
327 				case Tmb:
328 				case Tmd:
329 				case Tmf:
330 				case Tns:
331 					REF(rp->host);
332 					break;
333 				case Tmg:
334 				case Tmr:
335 					REF(rp->mb);
336 					break;
337 				case Tminfo:
338 					REF(rp->rmb);
339 					REF(rp->mb);
340 					break;
341 				case Trp:
342 					REF(rp->rmb);
343 					REF(rp->rp);
344 					break;
345 				case Tmx:
346 					REF(rp->host);
347 					break;
348 				case Ta:
349 				case Taaaa:
350 					REF(rp->ip);
351 					break;
352 				case Tptr:
353 					REF(rp->ptr);
354 					break;
355 				case Tsoa:
356 					REF(rp->host);
357 					REF(rp->rmb);
358 					break;
359 				}
360 			}
361 
362 	/* sweep and remove unreferenced domain names */
363 	for(i = 0; i < HTLEN; i++){
364 		l = &ht[i];
365 		for(dp = *l; dp; dp = *l){
366 			if(dp->rr == 0 && dp->refs == 0){
367 				assert(dp->magic == DNmagic);
368 				*l = dp->next;
369 				if(dp->name)
370 					free(dp->name);
371 				dp->magic = ~dp->magic;
372 				dnvars.names--;
373 				free(dp);
374 				continue;
375 			}
376 			l = &dp->next;
377 		}
378 	}
379 
380 	unlock(&dnlock);
381 }
382 
383 /*
384  *  timeout all database records (used when rereading db)
385  */
386 void
387 dnagedb(void)
388 {
389 	DN *dp;
390 	int i;
391 	RR *rp;
392 
393 	lock(&dnlock);
394 
395 	/* time out all database entries */
396 	for(i = 0; i < HTLEN; i++)
397 		for(dp = ht[i]; dp; dp = dp->next)
398 			for(rp = dp->rr; rp; rp = rp->next)
399 				if(rp->db)
400 					rp->expire = 0;
401 
402 	unlock(&dnlock);
403 }
404 
405 /*
406  *  mark all local db records about my area as authoritative, time out any others
407  */
408 void
409 dnauthdb(void)
410 {
411 	DN *dp;
412 	int i;
413 	Area *area;
414 	RR *rp;
415 
416 	lock(&dnlock);
417 
418 	/* time out all database entries */
419 	for(i = 0; i < HTLEN; i++)
420 		for(dp = ht[i]; dp; dp = dp->next){
421 			area = inmyarea(dp->name);
422 			for(rp = dp->rr; rp; rp = rp->next)
423 				if(rp->db){
424 					if(area){
425 						if(rp->ttl < area->soarr->soa->minttl)
426 							rp->ttl = area->soarr->soa->minttl;
427 						rp->auth = 1;
428 					}
429 					if(rp->expire == 0){
430 						rp->db = 0;
431 						dp->referenced = now - Reserved - 1;
432 					}
433 				}
434 		}
435 
436 	unlock(&dnlock);
437 }
438 
439 /*
440  *  keep track of other processes to know if we can
441  *  garbage collect.  block while garbage collecting.
442  */
443 int
444 getactivity(Request *req)
445 {
446 	int rv;
447 
448 	if(traceactivity) syslog(0, "dns", "get %d by %d.%d", dnvars.active, getpid(), threadid());
449 	lock(&dnvars.lk);
450 	while(dnvars.mutex){
451 		unlock(&dnvars.lk);
452 		sleep(200);
453 		lock(&dnvars.lk);
454 	}
455 	rv = ++dnvars.active;
456 	now = time(0);
457 	req->id = ++dnvars.id;
458 	unlock(&dnvars.lk);
459 
460 	return rv;
461 }
462 void
463 putactivity(void)
464 {
465 	if(traceactivity) syslog(0, "dns", "put %d by %d.%d", dnvars.active, getpid(), threadid());
466 	lock(&dnvars.lk);
467 	dnvars.active--;
468 	assert(dnvars.active >= 0); /* "dnvars.active %d", dnvars.active */;
469 
470 	/*
471 	 *  clean out old entries and check for new db periodicly
472 	 */
473 	if(dnvars.mutex || (needrefresh == 0 && dnvars.active > 0)){
474 		unlock(&dnvars.lk);
475 		return;
476 	}
477 
478 	/* wait till we're alone */
479 	dnvars.mutex = 1;
480 	while(dnvars.active > 0){
481 		unlock(&dnvars.lk);
482 		sleep(100);
483 		lock(&dnvars.lk);
484 	}
485 	unlock(&dnvars.lk);
486 
487 	db2cache(needrefresh);
488 	dnageall(0);
489 
490 	/* let others back in */
491 	needrefresh = 0;
492 	dnvars.mutex = 0;
493 }
494 
495 /*
496  *  Attach a single resource record to a domain name.
497  *	- Avoid duplicates with already present RR's
498  *	- Chain all RR's of the same type adjacent to one another
499  *	- chain authoritative RR's ahead of non-authoritative ones
500  */
501 static void
502 rrattach1(RR *new, int auth)
503 {
504 	RR **l;
505 	RR *rp;
506 	DN *dp;
507 
508 	assert(new->magic == RRmagic && !new->cached);
509 
510 	if(!new->db)
511 		new->expire = new->ttl;
512 	else
513 		new->expire = now + Year;
514 	dp = new->owner;
515 	assert(dp->magic == DNmagic);
516 	new->auth |= auth;
517 	new->next = 0;
518 
519 	/*
520 	 *  find first rr of the right type
521 	 */
522 	l = &dp->rr;
523 	for(rp = *l; rp; rp = *l){
524 		assert(rp->magic == RRmagic && rp->cached);
525 		if(rp->type == new->type)
526 			break;
527 		l = &rp->next;
528 	}
529 
530 	/*
531 	 *  negative entries replace positive entries
532 	 *  positive entries replace negative entries
533 	 *  newer entries replace older entries with the same fields
534 	 */
535 	for(rp = *l; rp; rp = *l){
536 		assert(rp->magic == RRmagic && rp->cached);
537 		if(rp->type != new->type)
538 			break;
539 
540 		if(rp->db == new->db && rp->auth == new->auth){
541 			/* negative drives out positive and vice versa */
542 			if(rp->negative != new->negative){
543 				*l = rp->next;
544 				rp->cached = 0;
545 				rrfree(rp);
546 				continue;
547 			}
548 
549 			/* all things equal, pick the newer one */
550 			if(rp->arg0 == new->arg0 && rp->arg1 == new->arg1){
551 				/* new drives out old */
552 				if(new->ttl > rp->ttl || new->expire > rp->expire){
553 					*l = rp->next;
554 					rp->cached = 0;
555 					rrfree(rp);
556 					continue;
557 				} else {
558 					rrfree(new);
559 					return;
560 				}
561 			}
562 
563 			/*  Hack for pointer records.  This makes sure
564 			 *  the ordering in the list reflects the ordering
565 			 *  received or read from the database
566 			 */
567 			if(rp->type == Tptr){
568 				if(!rp->negative && !new->negative
569 				&& rp->ptr->ordinal > new->ptr->ordinal)
570 					break;
571 			}
572 		}
573 		l = &rp->next;
574 	}
575 
576 	/*
577 	 *  add to chain
578 	 */
579 	new->cached = 1;
580 	new->next = *l;
581 	*l = new;
582 }
583 
584 /*
585  *  Attach a list of resource records to a domain name.
586  *	- Avoid duplicates with already present RR's
587  *	- Chain all RR's of the same type adjacent to one another
588  *	- chain authoritative RR's ahead of non-authoritative ones
589  *	- remove any expired RR's
590  */
591 void
592 rrattach(RR *rp, int auth)
593 {
594 	RR *next;
595 
596 	lock(&dnlock);
597 	for(; rp; rp = next){
598 		next = rp->next;
599 		rp->next = 0;
600 
601 		/* avoid any outside spoofing */
602 		if(cachedb && !rp->db && inmyarea(rp->owner->name))
603 			rrfree(rp);
604 		else
605 			rrattach1(rp, auth);
606 	}
607 	unlock(&dnlock);
608 }
609 
610 /*
611  *  allocate a resource record of a given type
612  */
613 RR*
614 rralloc(int type)
615 {
616 	RR *rp;
617 
618 	rp = emalloc(sizeof(*rp));
619 	rp->magic = RRmagic;
620 	rp->pc = getcallerpc(&type);
621 	rp->type = type;
622 	switch(type){
623 	case Tsoa:
624 		rp->soa = emalloc(sizeof(*rp->soa));
625 		rp->soa->slaves = nil;
626 		break;
627 	case Tkey:
628 		rp->key = emalloc(sizeof(*rp->key));
629 		break;
630 	case Tcert:
631 		rp->cert = emalloc(sizeof(*rp->cert));
632 		break;
633 	case Tsig:
634 		rp->sig = emalloc(sizeof(*rp->sig));
635 		break;
636 	case Tnull:
637 		rp->null = emalloc(sizeof(*rp->null));
638 		break;
639 	}
640 	rp->ttl = 0;
641 	rp->expire = 0;
642 	rp->next = 0;
643 	return rp;
644 }
645 
646 /*
647  *  free a resource record and any related structs
648  */
649 void
650 rrfree(RR *rp)
651 {
652 	DN *dp;
653 	RR *nrp;
654 	Txt *t;
655 
656 	assert(rp->magic = RRmagic);
657 	assert(!rp->cached);
658 
659 	dp = rp->owner;
660 	if(dp){
661 		assert(dp->magic == DNmagic);
662 		for(nrp = dp->rr; nrp; nrp = nrp->next)
663 			assert(nrp != rp); /* "rrfree of live rr" */;
664 	}
665 
666 	switch(rp->type){
667 	case Tsoa:
668 		freeserverlist(rp->soa->slaves);
669 		free(rp->soa);
670 		break;
671 	case Tkey:
672 		free(rp->key->data);
673 		free(rp->key);
674 		break;
675 	case Tcert:
676 		free(rp->cert->data);
677 		free(rp->cert);
678 		break;
679 	case Tsig:
680 		free(rp->sig->data);
681 		free(rp->sig);
682 		break;
683 	case Tnull:
684 		free(rp->null->data);
685 		free(rp->null);
686 		break;
687 	case Ttxt:
688 		while(rp->txt != nil){
689 			t = rp->txt;
690 			rp->txt = t->next;
691 			free(t->p);
692 			free(t);
693 		}
694 		break;
695 	}
696 
697 	rp->magic = ~rp->magic;
698 	free(rp);
699 }
700 
701 /*
702  *  free a list of resource records and any related structs
703  */
704 void
705 rrfreelist(RR *rp)
706 {
707 	RR *next;
708 
709 	for(; rp; rp = next){
710 		next = rp->next;
711 		rrfree(rp);
712 	}
713 }
714 
715 extern RR**
716 rrcopy(RR *rp, RR **last)
717 {
718 	RR *nrp;
719 	SOA *soa;
720 	Key *key;
721 	Cert *cert;
722 	Sig *sig;
723 	Null *null;
724 	Txt *t, *nt, **l;
725 
726 	nrp = rralloc(rp->type);
727 	switch(rp->type){
728 	case Ttxt:
729 		*nrp = *rp;
730 		l = &nrp->txt;
731 		*l = nil;
732 		for(t = rp->txt; t != nil; t = t->next){
733 			nt = emalloc(sizeof(*nt));
734 			nt->p = estrdup(t->p);
735 			nt->next = nil;
736 			*l = nt;
737 			l = &nt->next;
738 		}
739 		break;
740 	case Tsoa:
741 		soa = nrp->soa;
742 		*nrp = *rp;
743 		nrp->soa = soa;
744 		*nrp->soa = *rp->soa;
745 		nrp->soa->slaves = copyserverlist(rp->soa->slaves);
746 		break;
747 	case Tkey:
748 		key = nrp->key;
749 		*nrp = *rp;
750 		nrp->key = key;
751 		*key = *rp->key;
752 		key->data = emalloc(key->dlen);
753 		memmove(key->data, rp->key->data, rp->key->dlen);
754 		break;
755 	case Tsig:
756 		sig = nrp->sig;
757 		*nrp = *rp;
758 		nrp->sig = sig;
759 		*sig = *rp->sig;
760 		sig->data = emalloc(sig->dlen);
761 		memmove(sig->data, rp->sig->data, rp->sig->dlen);
762 		break;
763 	case Tcert:
764 		cert = nrp->cert;
765 		*nrp = *rp;
766 		nrp->cert = cert;
767 		*cert = *rp->cert;
768 		cert->data = emalloc(cert->dlen);
769 		memmove(cert->data, rp->cert->data, rp->cert->dlen);
770 		break;
771 	case Tnull:
772 		null = nrp->null;
773 		*nrp = *rp;
774 		nrp->null = null;
775 		*null = *rp->null;
776 		null->data = emalloc(null->dlen);
777 		memmove(null->data, rp->null->data, rp->null->dlen);
778 		break;
779 	default:
780 		*nrp = *rp;
781 		break;
782 	}
783 	nrp->cached = 0;
784 	nrp->next = 0;
785 	*last = nrp;
786 	return &nrp->next;
787 }
788 
789 /*
790  *  lookup a resource record of a particular type and
791  *  class attached to a domain name.  Return copies.
792  *
793  *  Priority ordering is:
794  *	db authoritative
795  *	not timed out network authoritative
796  *	not timed out network unauthoritative
797  *	unauthoritative db
798  *
799  *  if flag NOneg is set, don't return negative cached entries.
800  *  return nothing instead.
801  */
802 RR*
803 rrlookup(DN *dp, int type, int flag)
804 {
805 	RR *rp, *first, **last;
806 
807 	assert(dp->magic == DNmagic);
808 
809 	first = 0;
810 	last = &first;
811 	lock(&dnlock);
812 
813 	/* try for an authoritative db entry */
814 	for(rp = dp->rr; rp; rp = rp->next){
815 		assert(rp->magic == RRmagic && rp->cached);
816 		if(rp->db)
817 		if(rp->auth)
818 		if(tsame(type, rp->type))
819 			last = rrcopy(rp, last);
820 	}
821 	if(first)
822 		goto out;
823 
824 	/* try for an living authoritative network entry */
825 	for(rp = dp->rr; rp; rp = rp->next){
826 		if(!rp->db)
827 		if(rp->auth)
828 		if(rp->ttl + 60 > now)
829 		if(tsame(type, rp->type)){
830 			if(flag == NOneg && rp->negative)
831 				goto out;
832 			last = rrcopy(rp, last);
833 		}
834 	}
835 	if(first)
836 		goto out;
837 
838 	/* try for an living unauthoritative network entry */
839 	for(rp = dp->rr; rp; rp = rp->next){
840 		if(!rp->db)
841 		if(rp->ttl + 60 > now)
842 		if(tsame(type, rp->type)){
843 			if(flag == NOneg && rp->negative)
844 				goto out;
845 			last = rrcopy(rp, last);
846 		}
847 	}
848 	if(first)
849 		goto out;
850 
851 	/* try for an unauthoritative db entry */
852 	for(rp = dp->rr; rp; rp = rp->next){
853 		if(rp->db)
854 		if(tsame(type, rp->type))
855 			last = rrcopy(rp, last);
856 	}
857 	if(first)
858 		goto out;
859 
860 	/* otherwise, settle for anything we got (except for negative caches)  */
861 	for(rp = dp->rr; rp; rp = rp->next){
862 		if(tsame(type, rp->type)){
863 			if(rp->negative)
864 				goto out;
865 			last = rrcopy(rp, last);
866 		}
867 	}
868 
869 out:
870 	unlock(&dnlock);
871 	unique(first);
872 	return first;
873 }
874 
875 /*
876  *  convert an ascii RR type name to its integer representation
877  */
878 int
879 rrtype(char *atype)
880 {
881 	int i;
882 
883 	for(i = 0; i <= Tall; i++)
884 		if(rrtname[i] && strcmp(rrtname[i], atype) == 0)
885 			return i;
886 
887 	/* make any a synonym for all */
888 	if(strcmp(atype, "any") == 0)
889 		return Tall;
890 	return atoi(atype);
891 }
892 
893 /*
894  *  convert an integer RR type to it's ascii name
895  */
896 char*
897 rrname(int type, char *buf, int len)
898 {
899 	char *t;
900 
901 	t = 0;
902 	if(type <= Tall)
903 		t = rrtname[type];
904 	if(t==0){
905 		snprint(buf, len, "%d", type);
906 		t = buf;
907 	}
908 	return t;
909 }
910 
911 /*
912  *  return 0 if not a supported rr type
913  */
914 int
915 rrsupported(int type)
916 {
917 	if(type < 0 || type >Tall)
918 		return 0;
919 	return rrtname[type] != 0;
920 }
921 
922 /*
923  *  compare 2 types
924  */
925 int
926 tsame(int t1, int t2)
927 {
928 	return t1 == t2 || t1 == Tall;
929 }
930 
931 /*
932  *  Add resource records to a list, duplicate them if they are cached
933  *  RR's since these are shared.
934  */
935 RR*
936 rrcat(RR **start, RR *rp)
937 {
938 	RR **last;
939 
940 	last = start;
941 	while(*last != 0)
942 		last = &(*last)->next;
943 
944 	*last = rp;
945 	return *start;
946 }
947 
948 /*
949  *  remove negative cache rr's from an rr list
950  */
951 RR*
952 rrremneg(RR **l)
953 {
954 	RR **nl, *rp;
955 	RR *first;
956 
957 	first = nil;
958 	nl = &first;
959 	while(*l != nil){
960 		rp = *l;
961 		if(rp->negative){
962 			*l = rp->next;
963 			*nl = rp;
964 			nl = &rp->next;
965 			*nl = nil;
966 		} else
967 			l = &rp->next;
968 	}
969 
970 	return first;
971 }
972 
973 /*
974  *  remove rr's of a particular type from an rr list
975  */
976 RR*
977 rrremtype(RR **l, int type)
978 {
979 	RR **nl, *rp;
980 	RR *first;
981 
982 	first = nil;
983 	nl = &first;
984 	while(*l != nil){
985 		rp = *l;
986 		if(rp->type == type){
987 			*l = rp->next;
988 			*nl = rp;
989 			nl = &rp->next;
990 			*nl = nil;
991 		} else
992 			l = &(*l)->next;
993 	}
994 
995 	return first;
996 }
997 
998 /*
999  *  print conversion for rr records
1000  */
1001 int
1002 rrfmt(Fmt *f)
1003 {
1004 	RR *rp;
1005 	char *strp;
1006 	Fmt fstr;
1007 	int rv;
1008 	char buf[Domlen];
1009 	Server *s;
1010 	Txt *t;
1011 
1012 	fmtstrinit(&fstr);
1013 
1014 	rp = va_arg(f->args, RR*);
1015 	if(rp == 0){
1016 		fmtprint(&fstr, "<null>");
1017 		goto out;
1018 	}
1019 
1020 	fmtprint(&fstr, "%s %s", rp->owner->name,
1021 		rrname(rp->type, buf, sizeof buf));
1022 
1023 	if(rp->negative){
1024 		fmtprint(&fstr, "\tnegative - rcode %d", rp->negrcode);
1025 		goto out;
1026 	}
1027 
1028 	switch(rp->type){
1029 	case Thinfo:
1030 		fmtprint(&fstr, "\t%s %s", rp->cpu->name, rp->os->name);
1031 		break;
1032 	case Tcname:
1033 	case Tmb:
1034 	case Tmd:
1035 	case Tmf:
1036 	case Tns:
1037 		fmtprint(&fstr, "\t%s", rp->host->name);
1038 		break;
1039 	case Tmg:
1040 	case Tmr:
1041 		fmtprint(&fstr, "\t%s", rp->mb->name);
1042 		break;
1043 	case Tminfo:
1044 		fmtprint(&fstr, "\t%s %s", rp->mb->name, rp->rmb->name);
1045 		break;
1046 	case Tmx:
1047 		fmtprint(&fstr, "\t%lud %s", rp->pref, rp->host->name);
1048 		break;
1049 	case Ta:
1050 	case Taaaa:
1051 		fmtprint(&fstr, "\t%s", rp->ip->name);
1052 		break;
1053 	case Tptr:
1054 /*		fmtprint(&fstr, "\t%s(%lud)", rp->ptr->name, rp->ptr->ordinal); */
1055 		fmtprint(&fstr, "\t%s", rp->ptr->name);
1056 		break;
1057 	case Tsoa:
1058 		fmtprint(&fstr, "\t%s %s %lud %lud %lud %lud %lud", rp->host->name,
1059 			rp->rmb->name, rp->soa->serial, rp->soa->refresh, rp->soa->retry,
1060 			rp->soa->expire, rp->soa->minttl);
1061 		for(s = rp->soa->slaves; s != nil; s = s->next)
1062 			fmtprint(&fstr, " %s", s->name);
1063 		break;
1064 	case Tnull:
1065 		fmtprint(&fstr, "\t%.*H", rp->null->dlen, rp->null->data);
1066 		break;
1067 	case Ttxt:
1068 		fmtprint(&fstr, "\t");
1069 		for(t = rp->txt; t != nil; t = t->next)
1070 			fmtprint(&fstr, "%s", t->p);
1071 		break;
1072 	case Trp:
1073 		fmtprint(&fstr, "\t%s %s", rp->rmb->name, rp->rp->name);
1074 		break;
1075 	case Tkey:
1076 		fmtprint(&fstr, "\t%d %d %d", rp->key->flags, rp->key->proto,
1077 			rp->key->alg);
1078 		break;
1079 	case Tsig:
1080 		fmtprint(&fstr, "\t%d %d %d %lud %lud %lud %d %s",
1081 			rp->sig->type, rp->sig->alg, rp->sig->labels, rp->sig->ttl,
1082 			rp->sig->exp, rp->sig->incep, rp->sig->tag, rp->sig->signer->name);
1083 		break;
1084 	case Tcert:
1085 		fmtprint(&fstr, "\t%d %d %d",
1086 			rp->sig->type, rp->sig->tag, rp->sig->alg);
1087 		break;
1088 	default:
1089 		break;
1090 	}
1091 out:
1092 	strp = fmtstrflush(&fstr);
1093 	rv = fmtstrcpy(f, strp);
1094 	free(strp);
1095 	return rv;
1096 }
1097 
1098 /*
1099  *  print conversion for rr records in attribute value form
1100  */
1101 int
1102 rravfmt(Fmt *f)
1103 {
1104 	RR *rp;
1105 	char *strp;
1106 	Fmt fstr;
1107 	int rv;
1108 	Server *s;
1109 	Txt *t;
1110 	int quote;
1111 
1112 	fmtstrinit(&fstr);
1113 
1114 	rp = va_arg(f->args, RR*);
1115 	if(rp == 0){
1116 		fmtprint(&fstr, "<null>");
1117 		goto out;
1118 	}
1119 
1120 	if(rp->type == Tptr)
1121 		fmtprint(&fstr, "ptr=%s", rp->owner->name);
1122 	else
1123 		fmtprint(&fstr, "dom=%s", rp->owner->name);
1124 
1125 	switch(rp->type){
1126 	case Thinfo:
1127 		fmtprint(&fstr, " cpu=%s os=%s", rp->cpu->name, rp->os->name);
1128 		break;
1129 	case Tcname:
1130 		fmtprint(&fstr, " cname=%s", rp->host->name);
1131 		break;
1132 	case Tmb:
1133 	case Tmd:
1134 	case Tmf:
1135 		fmtprint(&fstr, " mbox=%s", rp->host->name);
1136 		break;
1137 	case Tns:
1138 		fmtprint(&fstr,  " ns=%s", rp->host->name);
1139 		break;
1140 	case Tmg:
1141 	case Tmr:
1142 		fmtprint(&fstr, " mbox=%s", rp->mb->name);
1143 		break;
1144 	case Tminfo:
1145 		fmtprint(&fstr, " mbox=%s mbox=%s", rp->mb->name, rp->rmb->name);
1146 		break;
1147 	case Tmx:
1148 		fmtprint(&fstr, " pref=%lud mx=%s", rp->pref, rp->host->name);
1149 		break;
1150 	case Ta:
1151 	case Taaaa:
1152 		fmtprint(&fstr, " ip=%s", rp->ip->name);
1153 		break;
1154 	case Tptr:
1155 		fmtprint(&fstr, " dom=%s", rp->ptr->name);
1156 		break;
1157 	case Tsoa:
1158 		fmtprint(&fstr, " ns=%s mbox=%s serial=%lud refresh=%lud retry=%lud expire=%lud ttl=%lud",
1159 			rp->host->name, rp->rmb->name, rp->soa->serial,
1160 			rp->soa->refresh, rp->soa->retry,
1161 			rp->soa->expire, rp->soa->minttl);
1162 		for(s = rp->soa->slaves; s != nil; s = s->next)
1163 			fmtprint(&fstr, " dnsslave=%s", s->name);
1164 		break;
1165 	case Tnull:
1166 		fmtprint(&fstr, " null=%.*H", rp->null->dlen, rp->null->data);
1167 		break;
1168 	case Ttxt:
1169 		fmtprint(&fstr, " txt=");
1170 		quote = 0;
1171 		for(t = rp->txt; t != nil; t = t->next)
1172 			if(strchr(t->p, ' '))
1173 				quote = 1;
1174 		if(quote)
1175 			fmtprint(&fstr, "\"");
1176 		for(t = rp->txt; t != nil; t = t->next)
1177 			fmtprint(&fstr, "%s", t->p);
1178 		if(quote)
1179 			fmtprint(&fstr, "\"");
1180 		break;
1181 	case Trp:
1182 		fmtprint(&fstr, " rp=%s txt=%s", rp->rmb->name, rp->rp->name);
1183 		break;
1184 	case Tkey:
1185 		fmtprint(&fstr, " flags=%d proto=%d alg=%d",
1186 			rp->key->flags, rp->key->proto, rp->key->alg);
1187 		break;
1188 	case Tsig:
1189 		fmtprint(&fstr, " type=%d alg=%d labels=%d ttl=%lud exp=%lud incep=%lud tag=%d signer=%s",
1190 			rp->sig->type, rp->sig->alg, rp->sig->labels, rp->sig->ttl,
1191 			rp->sig->exp, rp->sig->incep, rp->sig->tag, rp->sig->signer->name);
1192 		break;
1193 	case Tcert:
1194 		fmtprint(&fstr, " type=%d tag=%d alg=%d",
1195 			rp->sig->type, rp->sig->tag, rp->sig->alg);
1196 		break;
1197 	default:
1198 		break;
1199 	}
1200 out:
1201 	strp = fmtstrflush(&fstr);
1202 	rv = fmtstrcpy(f, strp);
1203 	free(strp);
1204 	return rv;
1205 }
1206 
1207 void
1208 warning(char *fmt, ...)
1209 {
1210 	char dnserr[128];
1211 	va_list arg;
1212 
1213 	va_start(arg, fmt);
1214 	vseprint(dnserr, dnserr+sizeof(dnserr), fmt, arg);
1215 	va_end(arg);
1216 	syslog(1, "dns", dnserr);
1217 }
1218 
1219 /*
1220  *  chasing down double free's
1221  */
1222 void
1223 dncheck(void *p, int dolock)
1224 {
1225 	DN *dp;
1226 	int i;
1227 	RR *rp;
1228 
1229 	if(p != nil){
1230 		dp = p;
1231 		assert(dp->magic == DNmagic);
1232 	}
1233 
1234 	if(!testing)
1235 		return;
1236 
1237 	if(dolock)
1238 		lock(&dnlock);
1239 	for(i = 0; i < HTLEN; i++)
1240 		for(dp = ht[i]; dp; dp = dp->next){
1241 			assert(dp != p);
1242 			assert(dp->magic == DNmagic);
1243 			for(rp = dp->rr; rp; rp = rp->next){
1244 				assert(rp->magic == RRmagic);
1245 				assert(rp->cached);
1246 				assert(rp->owner == dp);
1247 			}
1248 		}
1249 	if(dolock)
1250 		unlock(&dnlock);
1251 }
1252 
1253 static int
1254 rrequiv(RR *r1, RR *r2)
1255 {
1256 	return r1->owner == r2->owner
1257 		&& r1->type == r2->type
1258 		&& r1->arg0 == r2->arg0
1259 		&& r1->arg1 == r2->arg1;
1260 }
1261 
1262 void
1263 unique(RR *rp)
1264 {
1265 	RR **l, *nrp;
1266 
1267 	for(; rp; rp = rp->next){
1268 		l = &rp->next;
1269 		for(nrp = *l; nrp; nrp = *l){
1270 			if(rrequiv(rp, nrp)){
1271 				*l = nrp->next;
1272 				rrfree(nrp);
1273 			} else
1274 				l = &nrp->next;
1275 		}
1276 	}
1277 }
1278 
1279 /*
1280  *  true if second domain is subsumed by the first
1281  */
1282 int
1283 subsume(char *higher, char *lower)
1284 {
1285 	int hn, ln;
1286 
1287 	ln = strlen(lower);
1288 	hn = strlen(higher);
1289 	if(ln < hn)
1290 		return 0;
1291 
1292 	if(cistrcmp(lower + ln - hn, higher) != 0)
1293 		return 0;
1294 
1295 	if(ln > hn && hn != 0 && lower[ln - hn - 1] != '.')
1296 		return 0;
1297 
1298 	return 1;
1299 }
1300 
1301 /*
1302  *  randomize the order we return items to provide some
1303  *  load balancing for servers.
1304  *
1305  *  only randomize the first class of entries
1306  */
1307 RR*
1308 randomize(RR *rp)
1309 {
1310 	RR *first, *last, *x, *base;
1311 	ulong n;
1312 
1313 	if(rp == nil || rp->next == nil)
1314 		return rp;
1315 
1316 	/* just randomize addresses and mx's */
1317 	for(x = rp; x; x = x->next)
1318 		if(x->type != Ta && x->type != Tmx && x->type != Tns)
1319 			return rp;
1320 
1321 	base = rp;
1322 
1323 	n = rand();
1324 	last = first = nil;
1325 	while(rp != nil){
1326 		/* stop randomizing if we've moved past our class */
1327 		if(base->auth != rp->auth || base->db != rp->db){
1328 			last->next = rp;
1329 			break;
1330 		}
1331 
1332 		/* unchain */
1333 		x = rp;
1334 		rp = x->next;
1335 		x->next = nil;
1336 
1337 		if(n&1){
1338 			/* add to tail */
1339 			if(last == nil)
1340 				first = x;
1341 			else
1342 				last->next = x;
1343 			last = x;
1344 		} else {
1345 			/* add to head */
1346 			if(last == nil)
1347 				last = x;
1348 			x->next = first;
1349 			first = x;
1350 		}
1351 
1352 		/* reroll the dice */
1353 		n >>= 1;
1354 	}
1355 	return first;
1356 }
1357 
1358 static int
1359 sencodefmt(Fmt *f)
1360 {
1361 	char *out;
1362 	char *buf;
1363 	int i, len;
1364 	int ilen;
1365 	int rv;
1366 	uchar *b;
1367 	char obuf[64];	/* rsc optimization */
1368 
1369 	if(!(f->flags&FmtPrec) || f->prec < 1)
1370 		goto error;
1371 
1372 	b = va_arg(f->args, uchar*);
1373 	if(b == nil)
1374 		goto error;
1375 
1376 	/* if it's a printable, go for it */
1377 	len = f->prec;
1378 	for(i = 0; i < len; i++)
1379 		if(!isprint(b[i]))
1380 			break;
1381 	if(i == len){
1382 		if(len >= sizeof obuf)
1383 			len = sizeof(obuf)-1;
1384 		memmove(obuf, b, len);
1385 		obuf[len] = 0;
1386 		fmtstrcpy(f, obuf);
1387 		return 0;
1388 	}
1389 
1390 	ilen = f->prec;
1391 	f->prec = 0;
1392 	f->flags &= ~FmtPrec;
1393 	switch(f->r){
1394 	case '<':
1395 		len = (8*ilen+4)/5 + 3;
1396 		break;
1397 	case '[':
1398 		len = (8*ilen+5)/6 + 4;
1399 		break;
1400 	case 'H':
1401 		len = 2*ilen + 1;
1402 		break;
1403 	default:
1404 		goto error;
1405 	}
1406 
1407 	if(len > sizeof(obuf)){
1408 		buf = malloc(len);
1409 		if(buf == nil)
1410 			goto error;
1411 	} else
1412 		buf = obuf;
1413 
1414 	/* convert */
1415 	out = buf;
1416 	switch(f->r){
1417 	case '<':
1418 		rv = enc32(out, len, b, ilen);
1419 		break;
1420 	case '[':
1421 		rv = enc64(out, len, b, ilen);
1422 		break;
1423 	case 'H':
1424 		rv = enc16(out, len, b, ilen);
1425 		break;
1426 	default:
1427 		rv = -1;
1428 		break;
1429 	}
1430 	if(rv < 0)
1431 		goto error;
1432 
1433 	fmtstrcpy(f, buf);
1434 	if(buf != obuf)
1435 		free(buf);
1436 	return 0;
1437 
1438 error:
1439 	return fmtstrcpy(f, "<encodefmt>");
1440 
1441 }
1442 
1443 void*
1444 emalloc(int size)
1445 {
1446 	char *x;
1447 
1448 	x = mallocz(size, 1);
1449 	if(x == nil)
1450 		abort();
1451 	setmalloctag(x, getcallerpc(&size));
1452 	return x;
1453 }
1454 
1455 char*
1456 estrdup(char *s)
1457 {
1458 	int size;
1459 	char *p;
1460 
1461 	size = strlen(s)+1;
1462 	p = mallocz(size, 0);
1463 	if(p == nil)
1464 		abort();
1465 	memmove(p, s, size);
1466 	setmalloctag(p, getcallerpc(&s));
1467 	return p;
1468 }
1469 
1470 /*
1471  *  create a pointer record
1472  */
1473 static RR*
1474 mkptr(DN *dp, char *ptr, ulong ttl)
1475 {
1476 	DN *ipdp;
1477 	RR *rp;
1478 
1479 	ipdp = dnlookup(ptr, Cin, 1);
1480 
1481 	rp = rralloc(Tptr);
1482 	rp->ptr = dp;
1483 	rp->owner = ipdp;
1484 	rp->db = 1;
1485 	if(ttl)
1486 		rp->ttl = ttl;
1487 	return rp;
1488 }
1489 
1490 /*
1491  *  look for all ip addresses in this network and make
1492  *  pointer records for them.
1493  */
1494 void
1495 dnptr(uchar *net, uchar *mask, char *dom, int bytes, int ttl)
1496 {
1497 	int i, j;
1498 	DN *dp;
1499 	RR *rp, *nrp, *first, **l;
1500 	uchar ip[IPaddrlen];
1501 	uchar nnet[IPaddrlen];
1502 	char ptr[Domlen];
1503 	char *p, *e;
1504 
1505 	l = &first;
1506 	first = nil;
1507 	for(i = 0; i < HTLEN; i++){
1508 		for(dp = ht[i]; dp; dp = dp->next){
1509 			for(rp = dp->rr; rp; rp = rp->next){
1510 				if(rp->type != Ta || rp->negative)
1511 					continue;
1512 				parseip(ip, rp->ip->name);
1513 				maskip(ip, mask, nnet);
1514 				if(ipcmp(net, nnet) != 0)
1515 					continue;
1516 				p = ptr;
1517 				e = ptr+sizeof(ptr);
1518 				for(j = IPaddrlen-1; j >= IPaddrlen-bytes; j--)
1519 					p = seprint(p, e, "%d.", ip[j]);
1520 				seprint(p, e, "%s", dom);
1521 				nrp = mkptr(dp, ptr, ttl);
1522 				*l = nrp;
1523 				l = &nrp->next;
1524 			}
1525 		}
1526 	}
1527 
1528 	for(rp = first; rp != nil; rp = nrp){
1529 		nrp = rp->next;
1530 		rp->next = nil;
1531 		rrattach(rp, 1);
1532 	}
1533 }
1534 
1535 void
1536 freeserverlist(Server *s)
1537 {
1538 	Server *next;
1539 
1540 	for(; s != nil; s = next){
1541 		next = s->next;
1542 		free(s);
1543 	}
1544 }
1545 
1546 void
1547 addserver(Server **l, char *name)
1548 {
1549 	Server *s;
1550 
1551 	while(*l)
1552 		l = &(*l)->next;
1553 	s = malloc(sizeof(Server)+strlen(name)+1);
1554 	if(s == nil)
1555 		return;
1556 	s->name = (char*)(s+1);
1557 	strcpy(s->name, name);
1558 	s->next = nil;
1559 	*l = s;
1560 }
1561 
1562 Server*
1563 copyserverlist(Server *s)
1564 {
1565 	Server *ns;
1566 
1567 
1568 	for(ns = nil; s != nil; s = s->next)
1569 		addserver(&ns, s->name);
1570 	return ns;
1571 }