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 	static ulong lastclean;
466 
467 	if(traceactivity) syslog(0, "dns", "put %d by %d.%d", dnvars.active, getpid(), threadid());
468 	lock(&dnvars.lk);
469 	dnvars.active--;
470 	assert(dnvars.active >= 0); /* "dnvars.active %d", dnvars.active */;
471 
472 	/*
473 	 *  clean out old entries and check for new db periodicly
474 	 */
475 	if(dnvars.mutex || (needrefresh == 0 && dnvars.active > 0)){
476 		unlock(&dnvars.lk);
477 		return;
478 	}
479 
480 	/* wait till we're alone */
481 	dnvars.mutex = 1;
482 	while(dnvars.active > 0){
483 		unlock(&dnvars.lk);
484 		sleep(100);
485 		lock(&dnvars.lk);
486 	}
487 	unlock(&dnvars.lk);
488 
489 	db2cache(needrefresh);
490 	dnageall(0);
491 
492 	/* let others back in */
493 	lastclean = now;
494 	needrefresh = 0;
495 	dnvars.mutex = 0;
496 }
497 
498 /*
499  *  Attach a single resource record to a domain name.
500  *	- Avoid duplicates with already present RR's
501  *	- Chain all RR's of the same type adjacent to one another
502  *	- chain authoritative RR's ahead of non-authoritative ones
503  */
504 static void
505 rrattach1(RR *new, int auth)
506 {
507 	RR **l;
508 	RR *rp;
509 	DN *dp;
510 
511 	assert(new->magic == RRmagic && !new->cached);
512 
513 	if(!new->db)
514 		new->expire = new->ttl;
515 	else
516 		new->expire = now + Year;
517 	dp = new->owner;
518 	assert(dp->magic == DNmagic);
519 	new->auth |= auth;
520 	new->next = 0;
521 
522 	/*
523 	 *  find first rr of the right type
524 	 */
525 	l = &dp->rr;
526 	for(rp = *l; rp; rp = *l){
527 		assert(rp->magic == RRmagic && rp->cached);
528 		if(rp->type == new->type)
529 			break;
530 		l = &rp->next;
531 	}
532 
533 	/*
534 	 *  negative entries replace positive entries
535 	 *  positive entries replace negative entries
536 	 *  newer entries replace older entries with the same fields
537 	 */
538 	for(rp = *l; rp; rp = *l){
539 		assert(rp->magic == RRmagic && rp->cached);
540 		if(rp->type != new->type)
541 			break;
542 
543 		if(rp->db == new->db && rp->auth == new->auth){
544 			/* negative drives out positive and vice versa */
545 			if(rp->negative != new->negative){
546 				*l = rp->next;
547 				rp->cached = 0;
548 				rrfree(rp);
549 				continue;
550 			}
551 
552 			/* all things equal, pick the newer one */
553 			if(rp->arg0 == new->arg0 && rp->arg1 == new->arg1){
554 				/* new drives out old */
555 				if(new->ttl > rp->ttl || new->expire > rp->expire){
556 					*l = rp->next;
557 					rp->cached = 0;
558 					rrfree(rp);
559 					continue;
560 				} else {
561 					rrfree(new);
562 					return;
563 				}
564 			}
565 
566 			/*  Hack for pointer records.  This makes sure
567 			 *  the ordering in the list reflects the ordering
568 			 *  received or read from the database
569 			 */
570 			if(rp->type == Tptr){
571 				if(!rp->negative && !new->negative
572 				&& rp->ptr->ordinal > new->ptr->ordinal)
573 					break;
574 			}
575 		}
576 		l = &rp->next;
577 	}
578 
579 	/*
580 	 *  add to chain
581 	 */
582 	new->cached = 1;
583 	new->next = *l;
584 	*l = new;
585 }
586 
587 /*
588  *  Attach a list of resource records to a domain name.
589  *	- Avoid duplicates with already present RR's
590  *	- Chain all RR's of the same type adjacent to one another
591  *	- chain authoritative RR's ahead of non-authoritative ones
592  *	- remove any expired RR's
593  */
594 void
595 rrattach(RR *rp, int auth)
596 {
597 	RR *next;
598 
599 	lock(&dnlock);
600 	for(; rp; rp = next){
601 		next = rp->next;
602 		rp->next = 0;
603 
604 		/* avoid any outside spoofing */
605 		if(cachedb && !rp->db && inmyarea(rp->owner->name))
606 			rrfree(rp);
607 		else
608 			rrattach1(rp, auth);
609 	}
610 	unlock(&dnlock);
611 }
612 
613 /*
614  *  allocate a resource record of a given type
615  */
616 RR*
617 rralloc(int type)
618 {
619 	RR *rp;
620 
621 	rp = emalloc(sizeof(*rp));
622 	rp->magic = RRmagic;
623 	rp->pc = getcallerpc(&type);
624 	rp->type = type;
625 	switch(type){
626 	case Tsoa:
627 		rp->soa = emalloc(sizeof(*rp->soa));
628 		rp->soa->slaves = nil;
629 		break;
630 	case Tkey:
631 		rp->key = emalloc(sizeof(*rp->key));
632 		break;
633 	case Tcert:
634 		rp->cert = emalloc(sizeof(*rp->cert));
635 		break;
636 	case Tsig:
637 		rp->sig = emalloc(sizeof(*rp->sig));
638 		break;
639 	case Tnull:
640 		rp->null = emalloc(sizeof(*rp->null));
641 		break;
642 	}
643 	rp->ttl = 0;
644 	rp->expire = 0;
645 	rp->next = 0;
646 	return rp;
647 }
648 
649 /*
650  *  free a resource record and any related structs
651  */
652 void
653 rrfree(RR *rp)
654 {
655 	DN *dp;
656 	RR *nrp;
657 	Txt *t;
658 
659 	assert(rp->magic = RRmagic);
660 	assert(!rp->cached);
661 
662 	dp = rp->owner;
663 	if(dp){
664 		assert(dp->magic == DNmagic);
665 		for(nrp = dp->rr; nrp; nrp = nrp->next)
666 			assert(nrp != rp); /* "rrfree of live rr" */;
667 	}
668 
669 	switch(rp->type){
670 	case Tsoa:
671 		freeserverlist(rp->soa->slaves);
672 		free(rp->soa);
673 		break;
674 	case Tkey:
675 		free(rp->key->data);
676 		free(rp->key);
677 		break;
678 	case Tcert:
679 		free(rp->cert->data);
680 		free(rp->cert);
681 		break;
682 	case Tsig:
683 		free(rp->sig->data);
684 		free(rp->sig);
685 		break;
686 	case Tnull:
687 		free(rp->null->data);
688 		free(rp->null);
689 		break;
690 	case Ttxt:
691 		while(rp->txt != nil){
692 			t = rp->txt;
693 			rp->txt = t->next;
694 			free(t->p);
695 			free(t);
696 		}
697 		break;
698 	}
699 
700 	rp->magic = ~rp->magic;
701 	free(rp);
702 }
703 
704 /*
705  *  free a list of resource records and any related structs
706  */
707 void
708 rrfreelist(RR *rp)
709 {
710 	RR *next;
711 
712 	for(; rp; rp = next){
713 		next = rp->next;
714 		rrfree(rp);
715 	}
716 }
717 
718 extern RR**
719 rrcopy(RR *rp, RR **last)
720 {
721 	RR *nrp;
722 	SOA *soa;
723 	Key *key;
724 	Cert *cert;
725 	Sig *sig;
726 	Null *null;
727 	Txt *t, *nt, **l;
728 
729 	nrp = rralloc(rp->type);
730 	switch(rp->type){
731 	case Ttxt:
732 		*nrp = *rp;
733 		l = &nrp->txt;
734 		*l = nil;
735 		for(t = rp->txt; t != nil; t = t->next){
736 			nt = emalloc(sizeof(*nt));
737 			nt->p = estrdup(t->p);
738 			nt->next = nil;
739 			*l = nt;
740 			l = &nt->next;
741 		}
742 		break;
743 	case Tsoa:
744 		soa = nrp->soa;
745 		*nrp = *rp;
746 		nrp->soa = soa;
747 		*nrp->soa = *rp->soa;
748 		nrp->soa->slaves = copyserverlist(rp->soa->slaves);
749 		break;
750 	case Tkey:
751 		key = nrp->key;
752 		*nrp = *rp;
753 		nrp->key = key;
754 		*key = *rp->key;
755 		key->data = emalloc(key->dlen);
756 		memmove(key->data, rp->key->data, rp->key->dlen);
757 		break;
758 	case Tsig:
759 		sig = nrp->sig;
760 		*nrp = *rp;
761 		nrp->sig = sig;
762 		*sig = *rp->sig;
763 		sig->data = emalloc(sig->dlen);
764 		memmove(sig->data, rp->sig->data, rp->sig->dlen);
765 		break;
766 	case Tcert:
767 		cert = nrp->cert;
768 		*nrp = *rp;
769 		nrp->cert = cert;
770 		*cert = *rp->cert;
771 		cert->data = emalloc(cert->dlen);
772 		memmove(cert->data, rp->cert->data, rp->cert->dlen);
773 		break;
774 	case Tnull:
775 		null = nrp->null;
776 		*nrp = *rp;
777 		nrp->null = null;
778 		*null = *rp->null;
779 		null->data = emalloc(null->dlen);
780 		memmove(null->data, rp->null->data, rp->null->dlen);
781 		break;
782 	default:
783 		*nrp = *rp;
784 		break;
785 	}
786 	nrp->cached = 0;
787 	nrp->next = 0;
788 	*last = nrp;
789 	return &nrp->next;
790 }
791 
792 /*
793  *  lookup a resource record of a particular type and
794  *  class attached to a domain name.  Return copies.
795  *
796  *  Priority ordering is:
797  *	db authoritative
798  *	not timed out network authoritative
799  *	not timed out network unauthoritative
800  *	unauthoritative db
801  *
802  *  if flag NOneg is set, don't return negative cached entries.
803  *  return nothing instead.
804  */
805 RR*
806 rrlookup(DN *dp, int type, int flag)
807 {
808 	RR *rp, *first, **last;
809 
810 	assert(dp->magic == DNmagic);
811 
812 	first = 0;
813 	last = &first;
814 	lock(&dnlock);
815 
816 	/* try for an authoritative db entry */
817 	for(rp = dp->rr; rp; rp = rp->next){
818 		assert(rp->magic == RRmagic && rp->cached);
819 		if(rp->db)
820 		if(rp->auth)
821 		if(tsame(type, rp->type))
822 			last = rrcopy(rp, last);
823 	}
824 	if(first)
825 		goto out;
826 
827 	/* try for an living authoritative network entry */
828 	for(rp = dp->rr; rp; rp = rp->next){
829 		if(!rp->db)
830 		if(rp->auth)
831 		if(rp->ttl + 60 > now)
832 		if(tsame(type, rp->type)){
833 			if(flag == NOneg && rp->negative)
834 				goto out;
835 			last = rrcopy(rp, last);
836 		}
837 	}
838 	if(first)
839 		goto out;
840 
841 	/* try for an living unauthoritative network entry */
842 	for(rp = dp->rr; rp; rp = rp->next){
843 		if(!rp->db)
844 		if(rp->ttl + 60 > now)
845 		if(tsame(type, rp->type)){
846 			if(flag == NOneg && rp->negative)
847 				goto out;
848 			last = rrcopy(rp, last);
849 		}
850 	}
851 	if(first)
852 		goto out;
853 
854 	/* try for an unauthoritative db entry */
855 	for(rp = dp->rr; rp; rp = rp->next){
856 		if(rp->db)
857 		if(tsame(type, rp->type))
858 			last = rrcopy(rp, last);
859 	}
860 	if(first)
861 		goto out;
862 
863 	/* otherwise, settle for anything we got (except for negative caches)  */
864 	for(rp = dp->rr; rp; rp = rp->next){
865 		if(tsame(type, rp->type)){
866 			if(rp->negative)
867 				goto out;
868 			last = rrcopy(rp, last);
869 		}
870 	}
871 
872 out:
873 	unlock(&dnlock);
874 	unique(first);
875 	return first;
876 }
877 
878 /*
879  *  convert an ascii RR type name to its integer representation
880  */
881 int
882 rrtype(char *atype)
883 {
884 	int i;
885 
886 	for(i = 0; i <= Tall; i++)
887 		if(rrtname[i] && strcmp(rrtname[i], atype) == 0)
888 			return i;
889 
890 	/* make any a synonym for all */
891 	if(strcmp(atype, "any") == 0)
892 		return Tall;
893 	return atoi(atype);
894 }
895 
896 /*
897  *  convert an integer RR type to it's ascii name
898  */
899 char*
900 rrname(int type, char *buf, int len)
901 {
902 	char *t;
903 
904 	t = 0;
905 	if(type <= Tall)
906 		t = rrtname[type];
907 	if(t==0){
908 		snprint(buf, len, "%d", type);
909 		t = buf;
910 	}
911 	return t;
912 }
913 
914 /*
915  *  return 0 if not a supported rr type
916  */
917 int
918 rrsupported(int type)
919 {
920 	if(type < 0 || type >Tall)
921 		return 0;
922 	return rrtname[type] != 0;
923 }
924 
925 /*
926  *  compare 2 types
927  */
928 int
929 tsame(int t1, int t2)
930 {
931 	return t1 == t2 || t1 == Tall;
932 }
933 
934 /*
935  *  Add resource records to a list, duplicate them if they are cached
936  *  RR's since these are shared.
937  */
938 RR*
939 rrcat(RR **start, RR *rp)
940 {
941 	RR **last;
942 
943 	last = start;
944 	while(*last != 0)
945 		last = &(*last)->next;
946 
947 	*last = rp;
948 	return *start;
949 }
950 
951 /*
952  *  remove negative cache rr's from an rr list
953  */
954 RR*
955 rrremneg(RR **l)
956 {
957 	RR **nl, *rp;
958 	RR *first;
959 
960 	first = nil;
961 	nl = &first;
962 	while(*l != nil){
963 		rp = *l;
964 		if(rp->negative){
965 			*l = rp->next;
966 			*nl = rp;
967 			nl = &rp->next;
968 			*nl = nil;
969 		} else
970 			l = &rp->next;
971 	}
972 
973 	return first;
974 }
975 
976 /*
977  *  remove rr's of a particular type from an rr list
978  */
979 RR*
980 rrremtype(RR **l, int type)
981 {
982 	RR **nl, *rp;
983 	RR *first;
984 
985 	first = nil;
986 	nl = &first;
987 	while(*l != nil){
988 		rp = *l;
989 		if(rp->type == type){
990 			*l = rp->next;
991 			*nl = rp;
992 			nl = &rp->next;
993 			*nl = nil;
994 		} else
995 			l = &(*l)->next;
996 	}
997 
998 	return first;
999 }
1000 
1001 /*
1002  *  print conversion for rr records
1003  */
1004 int
1005 rrfmt(Fmt *f)
1006 {
1007 	RR *rp;
1008 	char *strp;
1009 	Fmt fstr;
1010 	int rv;
1011 	char buf[Domlen];
1012 	Server *s;
1013 	Txt *t;
1014 
1015 	fmtstrinit(&fstr);
1016 
1017 	rp = va_arg(f->args, RR*);
1018 	if(rp == 0){
1019 		fmtprint(&fstr, "<null>");
1020 		goto out;
1021 	}
1022 
1023 	fmtprint(&fstr, "%s %s", rp->owner->name,
1024 		rrname(rp->type, buf, sizeof buf));
1025 
1026 	if(rp->negative){
1027 		fmtprint(&fstr, "\tnegative - rcode %d", rp->negrcode);
1028 		goto out;
1029 	}
1030 
1031 	switch(rp->type){
1032 	case Thinfo:
1033 		fmtprint(&fstr, "\t%s %s", rp->cpu->name, rp->os->name);
1034 		break;
1035 	case Tcname:
1036 	case Tmb:
1037 	case Tmd:
1038 	case Tmf:
1039 	case Tns:
1040 		fmtprint(&fstr, "\t%s", rp->host->name);
1041 		break;
1042 	case Tmg:
1043 	case Tmr:
1044 		fmtprint(&fstr, "\t%s", rp->mb->name);
1045 		break;
1046 	case Tminfo:
1047 		fmtprint(&fstr, "\t%s %s", rp->mb->name, rp->rmb->name);
1048 		break;
1049 	case Tmx:
1050 		fmtprint(&fstr, "\t%lud %s", rp->pref, rp->host->name);
1051 		break;
1052 	case Ta:
1053 	case Taaaa:
1054 		fmtprint(&fstr, "\t%s", rp->ip->name);
1055 		break;
1056 	case Tptr:
1057 /*		fmtprint(&fstr, "\t%s(%lud)", rp->ptr->name, rp->ptr->ordinal); */
1058 		fmtprint(&fstr, "\t%s", rp->ptr->name);
1059 		break;
1060 	case Tsoa:
1061 		fmtprint(&fstr, "\t%s %s %lud %lud %lud %lud %lud", rp->host->name,
1062 			rp->rmb->name, rp->soa->serial, rp->soa->refresh, rp->soa->retry,
1063 			rp->soa->expire, rp->soa->minttl);
1064 		for(s = rp->soa->slaves; s != nil; s = s->next)
1065 			fmtprint(&fstr, " %s", s->name);
1066 		break;
1067 	case Tnull:
1068 		fmtprint(&fstr, "\t%.*H", rp->null->dlen, rp->null->data);
1069 		break;
1070 	case Ttxt:
1071 		fmtprint(&fstr, "\t");
1072 		for(t = rp->txt; t != nil; t = t->next)
1073 			fmtprint(&fstr, "%s", t->p);
1074 		break;
1075 	case Trp:
1076 		fmtprint(&fstr, "\t%s %s", rp->rmb->name, rp->rp->name);
1077 		break;
1078 	case Tkey:
1079 		fmtprint(&fstr, "\t%d %d %d", rp->key->flags, rp->key->proto,
1080 			rp->key->alg);
1081 		break;
1082 	case Tsig:
1083 		fmtprint(&fstr, "\t%d %d %d %lud %lud %lud %d %s",
1084 			rp->sig->type, rp->sig->alg, rp->sig->labels, rp->sig->ttl,
1085 			rp->sig->exp, rp->sig->incep, rp->sig->tag, rp->sig->signer->name);
1086 		break;
1087 	case Tcert:
1088 		fmtprint(&fstr, "\t%d %d %d",
1089 			rp->sig->type, rp->sig->tag, rp->sig->alg);
1090 		break;
1091 	default:
1092 		break;
1093 	}
1094 out:
1095 	strp = fmtstrflush(&fstr);
1096 	rv = fmtstrcpy(f, strp);
1097 	free(strp);
1098 	return rv;
1099 }
1100 
1101 /*
1102  *  print conversion for rr records in attribute value form
1103  */
1104 int
1105 rravfmt(Fmt *f)
1106 {
1107 	RR *rp;
1108 	char *strp;
1109 	Fmt fstr;
1110 	int rv;
1111 	Server *s;
1112 	Txt *t;
1113 	int quote;
1114 
1115 	fmtstrinit(&fstr);
1116 
1117 	rp = va_arg(f->args, RR*);
1118 	if(rp == 0){
1119 		fmtprint(&fstr, "<null>");
1120 		goto out;
1121 	}
1122 
1123 	if(rp->type == Tptr)
1124 		fmtprint(&fstr, "ptr=%s", rp->owner->name);
1125 	else
1126 		fmtprint(&fstr, "dom=%s", rp->owner->name);
1127 
1128 	switch(rp->type){
1129 	case Thinfo:
1130 		fmtprint(&fstr, " cpu=%s os=%s", rp->cpu->name, rp->os->name);
1131 		break;
1132 	case Tcname:
1133 		fmtprint(&fstr, " cname=%s", rp->host->name);
1134 		break;
1135 	case Tmb:
1136 	case Tmd:
1137 	case Tmf:
1138 		fmtprint(&fstr, " mbox=%s", rp->host->name);
1139 		break;
1140 	case Tns:
1141 		fmtprint(&fstr,  " ns=%s", rp->host->name);
1142 		break;
1143 	case Tmg:
1144 	case Tmr:
1145 		fmtprint(&fstr, " mbox=%s", rp->mb->name);
1146 		break;
1147 	case Tminfo:
1148 		fmtprint(&fstr, " mbox=%s mbox=%s", rp->mb->name, rp->rmb->name);
1149 		break;
1150 	case Tmx:
1151 		fmtprint(&fstr, " pref=%lud mx=%s", rp->pref, rp->host->name);
1152 		break;
1153 	case Ta:
1154 	case Taaaa:
1155 		fmtprint(&fstr, " ip=%s", rp->ip->name);
1156 		break;
1157 	case Tptr:
1158 		fmtprint(&fstr, " dom=%s", rp->ptr->name);
1159 		break;
1160 	case Tsoa:
1161 		fmtprint(&fstr, " ns=%s mbox=%s serial=%lud refresh=%lud retry=%lud expire=%lud ttl=%lud",
1162 			rp->host->name, rp->rmb->name, rp->soa->serial,
1163 			rp->soa->refresh, rp->soa->retry,
1164 			rp->soa->expire, rp->soa->minttl);
1165 		for(s = rp->soa->slaves; s != nil; s = s->next)
1166 			fmtprint(&fstr, " dnsslave=%s", s->name);
1167 		break;
1168 	case Tnull:
1169 		fmtprint(&fstr, " null=%.*H", rp->null->dlen, rp->null->data);
1170 		break;
1171 	case Ttxt:
1172 		fmtprint(&fstr, " txt=");
1173 		quote = 0;
1174 		for(t = rp->txt; t != nil; t = t->next)
1175 			if(strchr(t->p, ' '))
1176 				quote = 1;
1177 		if(quote)
1178 			fmtprint(&fstr, "\"");
1179 		for(t = rp->txt; t != nil; t = t->next)
1180 			fmtprint(&fstr, "%s", t->p);
1181 		if(quote)
1182 			fmtprint(&fstr, "\"");
1183 		break;
1184 	case Trp:
1185 		fmtprint(&fstr, " rp=%s txt=%s", rp->rmb->name, rp->rp->name);
1186 		break;
1187 	case Tkey:
1188 		fmtprint(&fstr, " flags=%d proto=%d alg=%d",
1189 			rp->key->flags, rp->key->proto, rp->key->alg);
1190 		break;
1191 	case Tsig:
1192 		fmtprint(&fstr, " type=%d alg=%d labels=%d ttl=%lud exp=%lud incep=%lud tag=%d signer=%s",
1193 			rp->sig->type, rp->sig->alg, rp->sig->labels, rp->sig->ttl,
1194 			rp->sig->exp, rp->sig->incep, rp->sig->tag, rp->sig->signer->name);
1195 		break;
1196 	case Tcert:
1197 		fmtprint(&fstr, " type=%d tag=%d alg=%d",
1198 			rp->sig->type, rp->sig->tag, rp->sig->alg);
1199 		break;
1200 	default:
1201 		break;
1202 	}
1203 out:
1204 	strp = fmtstrflush(&fstr);
1205 	rv = fmtstrcpy(f, strp);
1206 	free(strp);
1207 	return rv;
1208 }
1209 
1210 void
1211 warning(char *fmt, ...)
1212 {
1213 	char dnserr[128];
1214 	va_list arg;
1215 
1216 	va_start(arg, fmt);
1217 	vseprint(dnserr, dnserr+sizeof(dnserr), fmt, arg);
1218 	va_end(arg);
1219 	syslog(1, "dns", dnserr);
1220 }
1221 
1222 /*
1223  *  chasing down double free's
1224  */
1225 void
1226 dncheck(void *p, int dolock)
1227 {
1228 	DN *dp;
1229 	int i;
1230 	RR *rp;
1231 
1232 	if(p != nil){
1233 		dp = p;
1234 		assert(dp->magic == DNmagic);
1235 	}
1236 
1237 	if(!testing)
1238 		return;
1239 
1240 	if(dolock)
1241 		lock(&dnlock);
1242 	for(i = 0; i < HTLEN; i++)
1243 		for(dp = ht[i]; dp; dp = dp->next){
1244 			assert(dp != p);
1245 			assert(dp->magic == DNmagic);
1246 			for(rp = dp->rr; rp; rp = rp->next){
1247 				assert(rp->magic == RRmagic);
1248 				assert(rp->cached);
1249 				assert(rp->owner == dp);
1250 			}
1251 		}
1252 	if(dolock)
1253 		unlock(&dnlock);
1254 }
1255 
1256 static int
1257 rrequiv(RR *r1, RR *r2)
1258 {
1259 	return r1->owner == r2->owner
1260 		&& r1->type == r2->type
1261 		&& r1->arg0 == r2->arg0
1262 		&& r1->arg1 == r2->arg1;
1263 }
1264 
1265 void
1266 unique(RR *rp)
1267 {
1268 	RR **l, *nrp;
1269 
1270 	for(; rp; rp = rp->next){
1271 		l = &rp->next;
1272 		for(nrp = *l; nrp; nrp = *l){
1273 			if(rrequiv(rp, nrp)){
1274 				*l = nrp->next;
1275 				rrfree(nrp);
1276 			} else
1277 				l = &nrp->next;
1278 		}
1279 	}
1280 }
1281 
1282 /*
1283  *  true if second domain is subsumed by the first
1284  */
1285 int
1286 subsume(char *higher, char *lower)
1287 {
1288 	int hn, ln;
1289 
1290 	ln = strlen(lower);
1291 	hn = strlen(higher);
1292 	if(ln < hn)
1293 		return 0;
1294 
1295 	if(cistrcmp(lower + ln - hn, higher) != 0)
1296 		return 0;
1297 
1298 	if(ln > hn && hn != 0 && lower[ln - hn - 1] != '.')
1299 		return 0;
1300 
1301 	return 1;
1302 }
1303 
1304 /*
1305  *  randomize the order we return items to provide some
1306  *  load balancing for servers.
1307  *
1308  *  only randomize the first class of entries
1309  */
1310 RR*
1311 randomize(RR *rp)
1312 {
1313 	RR *first, *last, *x, *base;
1314 	ulong n;
1315 
1316 	if(rp == nil || rp->next == nil)
1317 		return rp;
1318 
1319 	/* just randomize addresses and mx's */
1320 	for(x = rp; x; x = x->next)
1321 		if(x->type != Ta && x->type != Tmx && x->type != Tns)
1322 			return rp;
1323 
1324 	base = rp; 
1325 
1326 	n = rand();
1327 	last = first = nil;
1328 	while(rp != nil){
1329 		/* stop randomizing if we've moved past our class */
1330 		if(base->auth != rp->auth || base->db != rp->db){
1331 			last->next = rp;
1332 			break;
1333 		}
1334 
1335 		/* unchain */
1336 		x = rp;
1337 		rp = x->next;
1338 		x->next = nil;
1339 
1340 		if(n&1){
1341 			/* add to tail */
1342 			if(last == nil)
1343 				first = x;
1344 			else
1345 				last->next = x;
1346 			last = x;
1347 		} else {
1348 			/* add to head */
1349 			if(last == nil)
1350 				last = x;
1351 			x->next = first;
1352 			first = x;
1353 		}
1354 
1355 		/* reroll the dice */
1356 		n >>= 1;
1357 	}
1358 	return first;
1359 }
1360 
1361 static int
1362 sencodefmt(Fmt *f)
1363 {
1364 	char *out;
1365 	char *buf;
1366 	int i, len;
1367 	int ilen;
1368 	int rv;
1369 	uchar *b;
1370 	char obuf[64];	/* rsc optimization */
1371 
1372 	if(!(f->flags&FmtPrec) || f->prec < 1)
1373 		goto error;
1374 
1375 	b = va_arg(f->args, uchar*);
1376 	if(b == nil)
1377 		goto error;
1378 
1379 	/* if it's a printable, go for it */
1380 	len = f->prec;
1381 	for(i = 0; i < len; i++)
1382 		if(!isprint(b[i]))
1383 			break;
1384 	if(i == len){
1385 		if(len >= sizeof obuf)
1386 			len = sizeof(obuf)-1;
1387 		memmove(obuf, b, len);
1388 		obuf[len] = 0;
1389 		fmtstrcpy(f, obuf);
1390 		return 0;
1391 	}
1392 
1393 	ilen = f->prec;
1394 	f->prec = 0;
1395 	f->flags &= ~FmtPrec;
1396 	switch(f->r){
1397 	case '<':
1398 		len = (8*ilen+4)/5 + 3;
1399 		break;
1400 	case '[':
1401 		len = (8*ilen+5)/6 + 4;
1402 		break;
1403 	case 'H':
1404 		len = 2*ilen + 1;
1405 		break;
1406 	default:
1407 		goto error;
1408 	}
1409 
1410 	if(len > sizeof(obuf)){
1411 		buf = malloc(len);
1412 		if(buf == nil)
1413 			goto error;
1414 	} else
1415 		buf = obuf;
1416 
1417 	/* convert */
1418 	out = buf;
1419 	switch(f->r){
1420 	case '<':
1421 		rv = enc32(out, len, b, ilen);
1422 		break;
1423 	case '[':
1424 		rv = enc64(out, len, b, ilen);
1425 		break;
1426 	case 'H':
1427 		rv = enc16(out, len, b, ilen);
1428 		break;
1429 	default:
1430 		rv = -1;
1431 		break;
1432 	}
1433 	if(rv < 0)
1434 		goto error;
1435 
1436 	fmtstrcpy(f, buf);
1437 	if(buf != obuf)
1438 		free(buf);
1439 	return 0;
1440 
1441 error:
1442 	return fmtstrcpy(f, "<encodefmt>");
1443 
1444 }
1445 
1446 void*
1447 emalloc(int size)
1448 {
1449 	char *x;
1450 
1451 	x = mallocz(size, 1);
1452 	if(x == nil)
1453 		abort();
1454 	setmalloctag(x, getcallerpc(&size));
1455 	return x;
1456 }
1457 
1458 char*
1459 estrdup(char *s)
1460 {
1461 	int size;
1462 	char *p;
1463 
1464 	size = strlen(s)+1;
1465 	p = mallocz(size, 0);
1466 	if(p == nil)
1467 		abort();
1468 	memmove(p, s, size);
1469 	setmalloctag(p, getcallerpc(&s));
1470 	return p;
1471 }
1472 
1473 /*
1474  *  create a pointer record
1475  */
1476 static RR*
1477 mkptr(DN *dp, char *ptr, ulong ttl)
1478 {
1479 	DN *ipdp;
1480 	RR *rp;
1481 
1482 	ipdp = dnlookup(ptr, Cin, 1);
1483 
1484 	rp = rralloc(Tptr);
1485 	rp->ptr = dp;
1486 	rp->owner = ipdp;
1487 	rp->db = 1;
1488 	if(ttl)
1489 		rp->ttl = ttl;
1490 	return rp;
1491 }
1492 
1493 /*
1494  *  look for all ip addresses in this network and make
1495  *  pointer records for them.
1496  */
1497 void
1498 dnptr(uchar *net, uchar *mask, char *dom, int bytes, int ttl)
1499 {
1500 	int i, j;
1501 	DN *dp;
1502 	RR *rp, *nrp, *first, **l;
1503 	uchar ip[IPaddrlen];
1504 	uchar nnet[IPaddrlen];
1505 	char ptr[Domlen];
1506 	char *p, *e;
1507 
1508 	l = &first;
1509 	first = nil;
1510 	for(i = 0; i < HTLEN; i++){
1511 		for(dp = ht[i]; dp; dp = dp->next){
1512 			for(rp = dp->rr; rp; rp = rp->next){
1513 				if(rp->type != Ta || rp->negative)
1514 					continue;
1515 				parseip(ip, rp->ip->name);
1516 				maskip(ip, mask, nnet);
1517 				if(ipcmp(net, nnet) != 0)
1518 					continue;
1519 				p = ptr;
1520 				e = ptr+sizeof(ptr);
1521 				for(j = IPaddrlen-1; j >= IPaddrlen-bytes; j--)
1522 					p = seprint(p, e, "%d.", ip[j]);
1523 				seprint(p, e, "%s", dom);
1524 				nrp = mkptr(dp, ptr, ttl);
1525 				*l = nrp;
1526 				l = &nrp->next;
1527 			}
1528 		}
1529 	}
1530 
1531 	for(rp = first; rp != nil; rp = nrp){
1532 		nrp = rp->next;
1533 		rp->next = nil;
1534 		rrattach(rp, 1);
1535 	}
1536 }
1537 
1538 void
1539 freeserverlist(Server *s)
1540 {
1541 	Server *next;
1542 
1543 	for(; s != nil; s = next){
1544 		next = s->next;
1545 		free(s);
1546 	}
1547 }
1548 
1549 void
1550 addserver(Server **l, char *name)
1551 {
1552 	Server *s;
1553 
1554 	while(*l)
1555 		l = &(*l)->next;
1556 	s = malloc(sizeof(Server)+strlen(name)+1);
1557 	if(s == nil)
1558 		return;
1559 	s->name = (char*)(s+1);
1560 	strcpy(s->name, name);
1561 	s->next = nil;
1562 	*l = s;
1563 }
1564 
1565 Server*
1566 copyserverlist(Server *s)
1567 {
1568 	Server *ns;
1569 
1570 	
1571 	for(ns = nil; s != nil; s = s->next)
1572 		addserver(&ns, s->name);
1573 	return ns;
1574 }