implement Dnsd;

include "sys.m";
	sys: Sys;
	sprint: import sys;
include "draw.m";
include "exception.m";
include "arg.m";
include "sh.m";
include "dial.m";
	dial: Dial;
include "string.m";
	str: String;
include "lists.m";
	lists: Lists;
include "ip.m";
	ip: IP;
	IPaddr, Udphdr: import ip;
include "bufio.m";
include "attrdb.m";
	attrdb: Attrdb;
	Db, Dbentry, Tuples: import attrdb;

Dnsd: module {
	init:	fn(nil: ref Draw->Context, nil: list of string);
};

# rfc 1035 § 4.1.1
Msg: adt {
	id:	int;
	flags:	int;
	qds:	list of QD;
	ans:	list of RR;
	nses:	list of RR;
	ars:	list of RR;

	size:	fn(nil: self Msg): int;
	pack:	fn(nil: self Msg, buf: array of byte): int;
	unpack:	fn(buf: array of byte): (Msg, string);
};

# rfc 1035 § 4.1.2
QD: adt {
	name:	string;	# no final .
	qtype:	int;
	class:	int;

	size:	fn(nil: self QD): int;
	pack:	fn(nil: self QD, buf: array of byte): int;
	unpack:	fn(buf: array of byte, lbase: int, labels: Labels): (QD, Labels, int, string);
};

# rfc 1035 § 4.1.3
RR: adt {
	name:	string;	# no final .
	rtype:	int;
	class:	int;
	ttl:	int;
	rdata:	array of byte;	# rdlength = len rdata

	size:	fn(nil: self RR): int;
	pack:	fn(nil: self RR, buf: array of byte): int;
	unpack:	fn(buf: array of byte, lbase: int, labels: Labels): (RR, Labels, int, string);
};

Labels: type list of (int, string);

Zone: adt {
	name:	string;
	ttl:	int;
	soa:	RR;
	nses:	list of RR;
	hints:	list of RR;
};

Fname, Fi16, Fi32, Fstring, Fip, Fipv6: con iota;

Ta:	con 1;	# rfc 1035 § 3.2.2
Tns:	con 2;
Tmd:	con 3;
Tmf:	con 4;
Tcname:	con 5;
Tsoa:	con 6;
Tmb:	con 7;
Tmg:	con 8;
Tmr:	con 9;
Tnull:	con 10;
Twks:	con 11;
Tptr:	con 12;
Thinfo:	con 13;
Tminfo:	con 14;
Tmx:	con 15;
Ttxt:	con 16;
Taaaa:	con 28;	# rfc 1886 § 2.1
Tsrv:	con 33;	# rfc 2782

Tixfr:	con 251;	# rfc 1995 § 2
Taxfr:	con 252;	# rfc 1035 § 3.2.3
Tmailb:	con 253;
Tmaila:	con 254;
Tall:	con 255;

Taddr:	con 2<<16;	# for internal use only
Tqmask:	con 16r80;

Cin:	con 1;	# rfc 1035 § 3.2.4
Ccs:	con 2;
Cch:	con 3;
Chs:	con 4;

Cnone:	con 254;	# rfc 2136 § 1.3
Call:	con 255;	# rfc 1035 § 3.2.5

Oquery:	con 0<<11;	# rfc 1035 § 4.1.1
Oinverse:	con 1<<11;
Ostatus:	con 2<<11;
Onotify:	con 4<<11;	# rfc 1996 § 4.5
Oupdate:	con 5<<11;	# rfc 2136 § 1.3
Omask:	con 16r7800;

Fresp:	con 1<<15;	# rfc 1035 § 4.1.1
Fauth:	con 1<<10;
Ftrunc:	con 1<<9;
Frecurse:	con 1<<8;
Fcanrec:	con 1<<7;

Rok:	con 0;	# rfc 1035 § 4.1.1
Rformat:	con 1;
Rserver:	con 2;
Rname:	con 3;
Runimplemented:	con 4;
Rrefused:	con 5;
Ryxdomain:	con 6;	# rfc 2136 § 1.3
Ryxrrset:	con 7;
Rnxrrset:	con 8;
Rnotauth:	con 9;
Rnotzone:	con 10;
Rmask:	con 16r000f;

Etrunchdr:	con "truncated header";

Parser:	type ref fn(buf: array of byte, s: string): string;
Formatter:	type ref fn(rdata: array of byte): string;
fieldtab: array of (int, ref fn(nil: string): int, Parser, Formatter);
rattrtab: array of list of (string, int, string);

qtypetab := array[] of {
	(Ta,	"a"),
	(Ta,	"ip"),
	(Tns,	"ns"),
	(Tmd,	"md"),
	(Tmf,	"mf"),
	(Tcname,	"cname"),
	(Tsoa,	"soa"),
	(Tmb,	"mb"),
	(Tmg,	"mg"),
	(Tmr,	"mr"),
	(Tnull,	"null"),
	(Twks,	"wks"),
	(Tptr,	"ptr"),
	(Thinfo,	"hinfo"),
	(Tminfo,	"minfo"),
	(Tmx,	"mx"),
	(Ttxt,	"txt"),
	(Taaaa,	"aaaa"),
	(Taaaa,	"ipv6"),
	(Tsrv,	"srv"),
	(Tall,	"all"),
	(Tall,	"any"),
	(Taddr,	"addr"),
};

classtab := array[] of {
	(Cin,	"in"),
	(Ccs,	"cs"),
	(Cch,	"ch"),
	(Chs,	"hs"),
	(Cnone,	"none"),
	(Call,	"all"),
};

optab := array[] of {
	(Oquery,	"query"),
	(Oinverse,	"inverse"),
	(Ostatus,	"status"),
	(Onotify,	"notify"),
	(Oupdate,	"update"),
};

rcodetab := array[] of {
	(Rok,	"ok"),
	(Rformat,	"malformed"),
	(Rserver,	"server failure"),
	(Rname,	"bad name"),
	(Runimplemented,	"unimplemented"),
	(Rrefused,	"refused"),
	(Ryxdomain,	"name exists"),
	(Ryxrrset,	"rrset exists"),
	(Rnxrrset,	"rrset doesn't exist"),
	(Rnotauth,	"above my pay grade"),
	(Rnotzone,	"out of bailiwick"),
};

Logdata: type (int, string, big, big, Msg, Msg, int, int, int);

progname: string;
DefaultTTL: con 1800;
ndb: ref Db;
zones: list of Zone;
domcache: array of (string, ref Dbentry);
seqc: chan of int;
devtime: ref Sys->FD;
logdir: string;

init(nil: ref Draw->Context, args: list of string)
{
	sys = load Sys Sys->PATH;
	dial = load Dial Dial->PATH;
	str = load String String->PATH;
	lists = load Lists Lists->PATH;
	ip = load IP IP->PATH;
	attrdb = load Attrdb Attrdb->PATH;
	ip->init();
	if((initerr := attrdb->init()) != nil)
		fail("attrdb: " + initerr);

	sys->pctl(Sys->NEWPGRP, nil);

	exc := load Exception Exception->PATH;
	if(exc->setexcmode(Exception->PROPAGATE) < 0)
		fail(sprint("setexcmode: %r"));
	exc = nil;

	arg := load Arg Arg->PATH;
	arg->init(args);
	arg->setusage(hd args + " [-s] [-l logdir] [ndbfile]");

	reqlog: chan of Logdata;
	loiter := 0;
	dbname := "ndb";
	while((c := arg->opt()) != '\0') {
		case c {
		'l' =>
			logdir = arg->earg();
			reqlog = chan of Logdata;
			spawn logpipe((fdc := chan of ref Sys->FD));
			spawn logfmt(<-fdc, reqlog);
		's' =>
			loiter = 1;
		* =>
			arg->usage();
		}
	}
	progname = arg->progname();
	args = arg->argv();
	case len args {
	0 =>
		;
	1 =>
		dbname = hd args;
	* =>
		arg->usage();
	}
	arg = nil;

	fieldtab = array[] of {
		Fname	=>	(0,	sizename,	parsename,	fmtname),
		Fi16	=>	(2,	nil,	parsei16,	fmti16),
		Fi32	=>	(4,	nil,	parsei32,	fmti32),
		Fstring	=>	(0,	sizestring,	parsestring,	fmtstring),
		Fip	=>	(4,	nil,	parseip,	fmtip),
		Fipv6	=>	(16,	nil, parseipv6,	fmtipv6),
	};

	rattrtab = array[] of {
		Tns	=>	("ns", Fname, "") :: nil,
		Tcname	=>	("cname", Fname, nil) :: nil,
		Thinfo	=>	("hcpu", Fstring, nil) :: ("hos", Fstring, nil) :: nil,
		Tmx	=>	("pref", Fi16, "10") :: ("mx", Fname, nil) :: nil,
		Tsrv	=>	("pri", Fi16, "10") :: ("weight", Fi16, "10") ::
			("port", Fi16, nil) :: ("srv", Fname, nil) :: nil,
	};

	dbreqs := chan of chan of (int, Msg);
	spawn dbproc(dbname, dbreqs);

	if((udpfd := udpannounce("udp!*!dns")) == nil)
		fail(sprint("announce udp: %r"));
	if((aconn := dial->announce("tcp!*!dns")) == nil)
		fail(sprint("announce tcp: %r"));

	if((devtime = sys->open("/dev/time", Sys->OREAD)) == nil)
		fail(sprint("open /dev/time: %r"));

	(seqc = chan[1] of int) <-= 1;
	spawn udpproc(udpfd, dbreqs, reqlog);
	spawn tcpproc(aconn, dbreqs, reqlog);

	warn("ready " + string sys->pctl(0, nil));
	if(loiter)
		<-chan of int;
}

warn(msg: string)
{
	sys->fprint(sys->fildes(2), "%s: %s\n", progname, msg);
}

fail(msg: string)
{
	for(i := 0; i < len msg; i++) {
		if(msg[i] == ':')
			break;
	}
	fmsg := msg[:i];
	warn(msg);
	raise "fail:" + fmsg;
}

udpannounce(addr: string): ref Sys->FD
{
	if((conn := dial->announce(addr)) == nil)
		fail(sprint("announce: %r"));
	if(sys->fprint(conn.cfd, "headers") < 0)
		fail(sprint("udp ctl headers: %r"));
	if((conn.dfd = sys->open(conn.dir + "/data", Sys->ORDWR)) == nil)
		fail(sprint("open udp data: %r"));
	return conn.dfd;
}

udpproc(fd: ref Sys->FD, dbreqs: chan of chan of (int, Msg), reqlog: chan of Logdata)
{
	buf := array[IP->Udphdrlen + 512] of byte;
	while((n := sys->read(fd, buf, len buf)) > 0) {
		if(n < IP->Udphdrlen)
			fail(sprint("short udp header: %d/%d", n, IP->Udphdrlen));
		hdr := Udphdr.unpack(buf, IP->Udphdrlen);
		raddr := "udp!" + hdr.raddr.text() + "!" + string hdr.rport;

		t0 := nowμs();
		seq := <-seqc;
		seqc <-= seq + 1;

		(ok, q, r) := asdf(buf[IP->Udphdrlen:n], raddr, dbreqs);
		if(ok < 0)
			continue;

		fullsize := r.size();
		packedsize := r.pack(buf[IP->Udphdrlen:]);
		if(sys->write(fd, buf, IP->Udphdrlen + packedsize) != IP->Udphdrlen + packedsize)
			warn(sprint("%s: write: %r", raddr));

		if(reqlog != nil)
			reqlog <-= (seq, raddr, t0, nowμs(), q, r, n, packedsize, fullsize);
	}
	fail(sprint("udp read: %r"));
}

tcpproc(aconn: ref Dial->Connection, dbreqs: chan of chan of (int, Msg), reqlog: chan of Logdata)
{
	while((conn := dial->listen(aconn)) == nil) {
		warn(sprint("listen %s: %r", aconn.dir));
		sys->sleep(90*1000);
	}
	spawn tcpproc(aconn, dbreqs, reqlog);

	if((fd := dial->accept(conn)) == nil) {
		warn(sprint("accept %s: %r", conn.dir));
		sys->sleep(90*1000);
		return;
	}
	t0 := nowμs();
	seq := <-seqc;
	seqc <-= seq + 1;

	if((info := dial->netinfo(conn)) == nil) {
		warn(sprint("netinfo %s: %r", conn.dir));
		sys->sleep(90*1000);
		return;
	}

	buf := array[2] of byte;
	if((n := sys->read(fd, buf, len buf)) != len buf)
		return warn(sprint("%s: read len: %r", info.raddr));

	Maxmsg: con 2048;
	if((msgsize := get16(buf)) > Maxmsg)
		return warn(sprint("%s: too big: %d/%d", info.raddr, msgsize, Maxmsg));
	buf = array[msgsize] of byte;

	if((n = sys->read(fd, buf, len buf)) != len buf)
		return warn(sprint("%s: short read: %d/%d", info.raddr, n, msgsize));

	(ok, q, r) := asdf(buf, info.raddr, dbreqs);
	if(ok < 0)
		return;

	msgsize = r.size();
	buf = array[2 + msgsize] of byte;
	put16(buf, msgsize);
	r.pack(buf[2:]);
	sys->write(fd, buf, len buf);

	if(reqlog != nil)
		reqlog <-= (seq, info.raddr, t0, nowμs(), q, r, n, msgsize, msgsize);
}

asdf(buf: array of byte, raddr: string, dbreqs: chan of chan of (int, Msg)): (int, Msg, Msg)
{
	(q, err) := Msg.unpack(buf);
	if(err != nil) {
		if(err == Etrunchdr) {
			x: Msg;
			return (-1, x, x);
		}
		warn(sprint("%s: unpack: %s", raddr, err));
		badmsg(buf);
		return (0, q, Msg(q.id, Fresp | Rformat, nil, nil, nil, nil));
	}

	dbreq := chan of (int, Msg);
	dbreqs <-= dbreq;
	dbreq <-= (69105, q);
	(ok, r) := <-dbreq;
	if(ok < 0)
		badmsg(buf);
	return (0, q, r);
}

badmsg(msg: array of byte)
{
	if(logdir == nil)
		return;
	name := logdir + "/bad/" + string nowμs();
	if((fd := sys->create(name, Sys->OWRITE, 8r444)) != nil)
		sys->write(fd, msg, len msg);
}

nowμs(): big
{
	buf := array[32] of byte;
	n := sys->pread(devtime, buf, len buf, big 0);
	if(n < 0)
		fail(sprint("nowμs: %r"));
	return big (string buf[:n]);
}

logfmt(fd: ref Sys->FD, c: chan of Logdata)
{
	for(;;) {
		(seq, raddr, t0, t1, q, r, qsize, rsize, fullsize) := <-c;
		s := sprint("%ud	%#.6f	%s	%d", seq, real(t1-t0) / 1e6, raddr, q.id);
		s += sprint("	%04ux %d %d %d %d", q.flags, len q.qds, len q.ans, len q.nses, len q.ars);
		if(q.qds != nil) {
			s += sprint("	%s	%q	%s	%s", opstr(q.flags), (hd q.qds).name,
				qtypestr((hd q.qds).qtype), classstr((hd q.qds).class) );
		} else {
			s += "	0	''	0	0";
		}
		s += sprint("	%04ux %d %d %d %d", r.flags, len r.qds, len r.ans, len r.nses, len r.ars);
		s += sprint("	%d	%d	%d	%q\n", qsize, rsize, fullsize, rcodestr(r.flags));

		{	sys->write(fd, (a := array of byte s), len a);
		} exception e {
		"*" =>
			fail("logfmt: " + e);
		}
	}
}

logpipe(fdc: chan of ref Sys->FD)
{
	p := array[2] of ref Sys->FD;
	if(sys->pipe(p) < 0)
		fail(sprint("logpipe: pipe: %r"));
	fdc <-= p[1];

	sys->pctl(Sys->NEWFD | Sys->FORKNS | Sys->FORKENV, p[0].fd :: 1 :: 2 :: nil);
	if(sys->dup(p[0].fd, 0) < 0)
		fail(sprint("logpipe: dup 0: %r"));

	sh := load Sh Sh->PATH;
	fail(sh->system(nil, sprint("stamp μs | rotate day %#q", logdir + "/req")));
}

dbproc(ndbname: string, reqs: chan of chan of (int, Msg))
{
	opendb(ndbname);
	alarm := chan of int;
	snooze := chan of int;
	alarmed := 1;
	spawn alarmproc(alarm, snooze);

	for(;;) alt {
	<-alarm =>
		alarmed = 1;

	req := <-reqs =>
		if(alarmed) {
			if(ndb.changed()) {
				warn("db changed");
				opendb(ndbname);
			}
			snooze <-= 10000;
			alarmed = 0;
		}

		(nil, q) := <-req;
		{	req <-= (0, response(q));
		} exception e {
		"*" =>
			warn("dbproc: " + e);
			req <-= (-1, Msg(q.id, Fresp | Rserver, nil, nil, nil, nil));
		}
	}
}

alarmproc(alarm: chan of int, snooze: chan of int)
{
	for(;;)
		alarm <-= sys->sleep(<-snooze);
}

opendb(name: string)
{
	if(ndb == nil) {
		if((ndb = Db.open(name)) == nil)
			fail(sprint("opendb: open: %r"));
	}

	if(ndb.reopen() < 0)
		warn(sprint("opendb: reopen: %r"));
	domcache = array[128] of (string, ref Dbentry);
	readzones();
}

readzones()
{
	e: ref Dbentry;
	ptr: ref Attrdb->Dbptr;
	newzones: list of Zone;
	for(;;) {
		(e, ptr) = ndb.find(ptr, "soa");
		if(e == nil)
			break;

		ttl := DefaultTTL;
		if((ttlstr := e.findfirst("ttl")) != nil) {
			(x, remainder) := str->toint(ttlstr, 10);
			if(remainder == nil)
				ttl = x;
		}

		if((name := e.findfirst("dom")) == nil) {
			warn("no dom in soa");
			continue;
		}

		(nses, hints, rcode) := findrr(QD(name, Tns, Cin), name, ttl, 0, nil);
		if(rcode != Rok) {
			warn(sprint("readzones %q ns: %s", name, rcodestr(rcode)));
			continue;
		}
		if(nses == nil)
			warn(sprint("no ns in soa: %q", name));
		nses = reverserrs(nses);
		hints = reverserrs(hints);

		soas: list of RR;
		(soas, nil, rcode) = findrr(QD(name, Tsoa, Cin), name, ttl, 0, nil);
		if(rcode != Rok) {
			warn(sprint("readzones %q soa: %s", name, rcodestr(rcode)));
			continue;
		}
		if(soas == nil)
			warn(sprint("no soa in soa: %q", name));
		if(len soas != 1)
			warn(sprint("usual number of soas in soa: %q", name));
		soa := hd soas;

		newzones = Zone(str->tolower(name), ttl, soa, nses, hints) :: newzones;
	}
	zones = newzones;
}

findzone(name: string): (int, Zone)
{
	name = str->tolower(name);
	n := 0;
	zone: Zone;
	for(zs := zones; zs != nil; zs = tl zs) {
		z := hd zs;
		if(hassuffix(name, z.name) && (m := len z.name) > n) {
			n = m;
			zone = z;
		}
	}

	if(n == 0)
		return (-1, zone);
	return (0, zone);
}

hassuffix(s, sfx: string): int
{
	if((n := len s) < (m := len sfx))
		return 0;
	if(s[n-m:] == sfx)
		return 1;
	return 0;
}

findstr(tab: array of (int, string), key: int): string
{
	for(i := 0; i < len tab; i++) {
		(k, s) := tab[i];
		if(k == key)
			return s;
	}
	return string key;
}

qtypestr(qtype: int): string
{
	return findstr(qtypetab, qtype);
}

classstr(class: int): string
{
	return findstr(classtab, class);
}

opstr(flags: int): string
{
	return findstr(optab, flags & Omask);
}

rcodestr(flags: int): string
{
	return findstr(rcodetab, flags & Rmask);
}

getbe(buf: array of byte, n: int): int
{
	x := 0;
	for(i := 0; i < n; i++)
		x = x<<8 | int buf[i];
	return x;
}

putbe(buf: array of byte, n: int, x: int)
{
	for(i := n-1; i >= 0; i--) {
		buf[i] = byte x;
		x = x >> 8;
	}
}

get16(buf: array of byte): int
{
	return getbe(buf, 2);
}

put16(buf: array of byte, x: int)
{
	return putbe(buf, 2, x);
}

get32(buf: array of byte): int
{
	return getbe(buf, 4);
}

put32(buf: array of byte, x: int)
{
	return putbe(buf, 4, x);
}

getname(buf: array of byte, lbase: int, labels: Labels): (string, Labels, int, string)
{
	name: string;
	newlabels: Labels;

Loop:
	for(i := 0; i < len buf && (n := int buf[i++]) != 0; i += n) {
		case ltype := (n>>6) & 3 {
		0 =>
			if(n > 63)
				return (nil, nil, -1, "long label: " + string n + "/63");
			if(i+n > len buf)
				return (nil, nil, -1, "truncated");
			l := string buf[i:i+n];
			newlabels = (lbase+i, l) :: newlabels;
		3 =>
			addr := n & 16r3F;
			for(ls := labels; ls != nil; ls = tl ls) {
				(a, l) := hd ls;
				if(a == addr) {
					newlabels = (lbase+i, l) :: newlabels;
					break Loop;
				}
			}
			return (nil, nil, -1, "bad label pointer");
		* =>
			return (nil, nil, -1, "unknown label type: " + string ltype);
		}
	}

	for(ls := newlabels; ls != nil; ls = tl ls) {
		(nil, l) := hd ls;
		name = l + "." + name;
		labels = hd ls :: labels;
	}

	if(name != "")
		name = name[:len name - 1];
	if(sizename(name) > 255)
		return (nil, nil, -1, "long name: " + string len name + "/255");
	return (name, labels, i, nil);
}

putname(buf: array of byte, name: string): int
{
	i := 0;
	(nil, ls) := sys->tokenize(name, ".");
	for(; ls != nil; ls = tl ls) {
		l := hd ls;
		n := len l;
		buf[i] = byte n;
		buf[i+1:] = array of byte l;
		i += 1 + n;
	}
	buf[i++] = byte 0;

	return i;
}

Msg.size(m: self Msg): int
{
	n := 2 + 2 + 2+2+2+2;
	for(qds := m.qds; qds != nil; qds = tl qds)
		n += (hd qds).size();
	for(rrs := m.ans; rrs != nil; rrs = tl rrs)
		n += (hd rrs).size();
	for(rrs = m.nses; rrs != nil; rrs = tl rrs)
		n += (hd rrs).size();
	for(rrs = m.ars; rrs != nil; rrs = tl rrs)
		n += (hd rrs).size();
	return n;
}

Msg.pack(m: self Msg, buf: array of byte): int
{
	put16(buf, m.id);
	put16(buf[2:], m.flags);
	put16(buf[4:], 0);	# qd
	put16(buf[6:], 0);	# ans
	put16(buf[8:], 0);	# ns
	put16(buf[10:], 0);	# ars
	o := 12;

	n := 0;
	for(qds := m.qds; qds != nil; qds = tl qds) {
		qd := hd qds;
		if(o + qd.size() > len buf) {
			m.flags |= Ftrunc;
			put16(buf[4:], n);
			return o;
		}
		o += qd.pack(buf[o:]);
		n++;
	}
	put16(buf[4:], n);

	n = 0;
	for(rrs := m.ans; rrs != nil; rrs = tl rrs) {
		rr := hd rrs;
		if(o + rr.size() > len buf) {
			m.flags |= Ftrunc;
			put16(buf[6:], n);
			return o;
		}
		o += rr.pack(buf[o:]);
		n++;
	}
	put16(buf[6:], n);

	n = 0;
	for(rrs = m.nses; rrs != nil; rrs = tl rrs) {
		rr := hd rrs;
		if(o + rr.size() > len buf) {
			m.flags |= Ftrunc;
			put16(buf[8:], n);
			return o;
		}
		o += rr.pack(buf[o:]);
		n++;
	}
	put16(buf[8:], n);

	n = 0;
	for(rrs = m.ars; rrs != nil; rrs = tl rrs) {
		rr := hd rrs;
		if(o + rr.size() > len buf) {
			m.flags |= Ftrunc;
			put16(buf[10:], n);
			return o;
		}
		o += rr.pack(buf[o:]);
		n++;
	}
	put16(buf[10:], n);

	return o;
}

Msg.unpack(buf: array of byte): (Msg, string)
{
	m: Msg;
	labels: list of (int, string);

	if(len buf < 12)
		return (m, Etrunchdr);
	m.id = get16(buf);
	m.flags = get16(buf[2:]);
	nqds := get16(buf[4:]);
	nans := get16(buf[6:]);
	nnses := get16(buf[8:]);
	nars := get16(buf[10:]);
	o := 12;

	for(i := 0; i < nqds; i++) {
		(qd, ls, n, err) := QD.unpack(buf[o:], o, labels);
		if(err != nil)
			return (m, "qd " + string i + ": " + err);
		o += n;
		labels = ls;
		m.qds = qd :: m.qds;
	}
	m.qds = reverseqds(m.qds);

	for(i = 0; i < nans; i++) {
		(an, ls, n, err) := RR.unpack(buf[o:], o, labels);
		if(err != nil)
			return (m, "an " + string i + ": " + err);
		o += n;
		labels = ls;
		m.ans = an :: m.ans;
	}
	m.ans = reverserrs(m.ans);

	for(i = 0; i < nnses; i++) {
		(ns, ls, n, err) := RR.unpack(buf[o:], o, labels);
		if(err != nil)
			return (m, "ns " + string i + ": " + err);
		o += n;
		labels = ls;
		m.nses = ns :: m.nses;
	}
	m.nses = reverserrs(m.nses);

	for(i = 0; i < nars; i++) {
		(ar, ls, n, err) := RR.unpack(buf[o:], o, labels);
		if(err != nil)
			return (m, "ar " + string i + ": " + err);
		o += n;
		labels = ls;
		m.ars = ar :: m.ars;
	}
	m.ars = reverserrs(m.ars);

	return (m, nil);
}

QD.size(qd: self QD): int
{
	return sizename(qd.name) + 2 + 2;
}

QD.pack(qd: self QD, buf: array of byte): int
{
	o := putname(buf, qd.name);
	put16(buf[o:], qd.qtype);
	put16(buf[o+2:], qd.class);

	return o + 4;
}

QD.unpack(buf: array of byte, lbase: int, labels: Labels): (QD, Labels, int, string)
{
	qd: QD;
	o: int;
	err: string;

	(qd.name, labels, o, err) = getname(buf, lbase, labels);
	if(err != nil)
		return (qd, nil, -1, "name: " + err);

	if(len buf - o < 4)
		return (qd, nil, -1, "truncated");
	qd.qtype = get16(buf[o:]);
	qd.class = get16(buf[o+2:]);
	return (qd, labels, o+4, nil);
}

RR.size(rr: self RR): int
{
	return sizename(rr.name) + 2 + 2 + 4 + 2 + len rr.rdata;
}

RR.pack(rr: self RR, buf: array of byte): int
{
	o := putname(buf, rr.name);
	put16(buf[o:], rr.rtype);
	put16(buf[o+2:], rr.class);
	put32(buf[o+4:], rr.ttl);
	put16(buf[o+8:], len rr.rdata);
	buf[o+10:] = rr.rdata;

	return o + 10 + len rr.rdata;
}

RR.unpack(buf: array of byte, lbase: int, labels: Labels): (RR, Labels, int, string)
{
	rr: RR;
	o: int;
	err: string;

	(rr.name, labels, o, err) = getname(buf, lbase, labels);
	if(err != nil)
		return (rr, nil, -1, "name: " + err);

	if(len buf - o < 10)
		return (rr, nil, -1, "truncated");
	rr.rtype = get16(buf[o:]);
	rr.class = get16(buf[o+2:]);
	rr.ttl = get32(buf[o+4:]);
	rdlen := get16(buf[o+8:]);
	if(o+10+rdlen > len buf)
		return (rr, nil, -1, "truncated rdata");
	rr.rdata = buf[o+10:o+10+rdlen];
	return (rr, labels, o+10+rdlen, nil);
}

reverseqds(xs: list of QD): list of QD
{
	ys: list of QD;
	for(; xs != nil; xs = tl xs)
		ys = hd xs :: ys;
	return ys;
}

reverserrs(xs: list of RR): list of RR
{
	ys: list of RR;
	for(; xs != nil; xs = tl xs)
		ys = hd xs :: ys;
	return ys;
}

concatrrs(xs, ys: list of RR): list of RR
{
	xs = reverserrs(xs);
	for(; xs != nil; xs = tl xs)
		ys = hd xs :: ys;
	return ys;
}

response(q: Msg): Msg
{
	r: Msg;

	r.id = q.id;
	r.flags = q.flags | Fresp | Fauth;
	r.flags &= ~Fcanrec;
	r.flags &= ~Rmask;

	if(q.flags & Omask != Oquery) {
		r.flags |= Runimplemented;
		return r;
	}

	if(len q.qds != 1) {
		r.flags |= Rformat;
		return r;
	}
	r.qds = q.qds;
	qd := hd q.qds;

	(ok, zone) := findzone(qd.name);
	if(ok < 0) {
		r.flags |= Rrefused;
		return r;
	}

	hints: list of RR;
	rcode: int;
	(r.ans, hints, rcode) = findrr(qd, zone.name, zone.ttl, 1, nil);
	r.ans = reverserrs(r.ans);
	r.flags |= rcode;

	# rfc 2308 § 3	Negative Answers from Authoritative Servers
	if(len r.ans == 0 || rcode == Rname)
		hints = zone.soa :: hints;

	for(; hints != nil; hints = tl hints)
		r.ars = hd hints :: r.ars;

	return r;
}

sizename(s: string): int
{
	if((n := len s) == 0)
		return 1;
	else
		return 1 + n + 1;
}

parsename(buf: array of byte, s: string): string
{
	if((n := len s) > 0 && s[n-1] == '.')
		s = s[:n-1];
	if((n = len s) > 255)
		return "long name: " + string n + "/255";
	for(i := 0; i < n; i++) {
		for(j := i; j < n && s[j] != '.'; j++)
			;
		if(j - i > 63)
			return "long label: " + string (j - i) + "/63";
	}
	putname(buf, s);
	return nil;
}

fmtname(buf: array of byte): string
{
	(s, nil, nil, err) := getname(buf, 0, nil);
	if(err != nil)
		fail("fmtname: " + err);
	return s;
}

parsei16(buf: array of byte, s: string): string
{
	(x, remainder) := str->toint(s, 10);
	if(remainder != nil)
		return "malformed";
	if(x < 0 || x > 65535)
		return "out of range";
	put16(buf, x);
	return nil;
}

fmti16(buf: array of byte): string
{
	return sys->sprint("%ud", get16(buf));
}

parsei32(buf: array of byte, s: string): string
{
	(x, remainder) := str->toint(s, 10);
	if(remainder != nil)
		return "malformed";
	put32(buf, x);
	return nil;
}

fmti32(buf: array of byte): string
{
	return sys->sprint("%ud", get32(buf));
}

sizestring(s: string): int
{
	return 1 + len array of byte s;
}

parsestring(buf: array of byte, s: string): string
{
	bytestr := array of byte s;
	if((n := len bytestr) > 255)
		return "too long: " + string n + "/255";
	buf[0] = byte n;
	buf[1:] = bytestr;
	return nil;
}

fmtstring(buf: array of byte): string
{
	n := int buf[0];
	return string buf[1:n];
}

parseip(buf: array of byte, s: string): string
{
	(ok, addr) := IPaddr.parse(s);
	if(ok < 0 || !addr.isv4())
		return "malformed";
	buf[:] = addr.v4();
	return nil;
}

fmtip(buf: array of byte): string
{
	return IPaddr.newv4(buf).text();
}

parseipv6(buf: array of byte, s: string): string
{
	(ok, addr) := IPaddr.parse(s);
	if(ok < 0)
		return "malformed";
	buf[:] = addr.v6();
	return nil;
}

fmtipv6(buf: array of byte): string
{
	return IPaddr.newv6(buf).text();
}

# rrs and hints are returned in reverse order
findrr(q: QD, zonename: string, zonettl: int, followrefs: int, refsfollowed: list of string):
	(list of RR, list of RR, int)
{
	e: ref Dbentry;
	rrs: list of RR;
	hints: list of RR;

	if(q.class != Cin && q.class != Call)
		return (nil, nil, Rname);

	dom := str->tolower(q.name);
	for(;;) {
		e = ndbfinddom(dom);
		if(e != nil || dom == "*")
			break;
		if(str->prefix("*.", dom))
			dom = dom[2:];
		if(len dom < len zonename)
			return (nil, nil, Rok);
		(nil, dom) = str->splitl(dom, ".");
		dom = "*" + dom;
	}
	if(e == nil)
		return (nil, nil, Rname);

	case(q.qtype) {
	Ta =>
		for(lines := e.find("ip"); lines != nil; lines = tl lines) {
			for((line, matches) := hd lines; matches != nil; matches = tl matches) {
				ipstr := (hd matches).val;
				(ok, addr) := IPaddr.parse(ipstr);
				if(ok < 0 || !addr.isv4())
					continue;
				(rdata, err) := parserdata(("ip", Fip, ipstr) :: nil);
				if(err != nil) {
					warn(sprint("findrr %q %s: %s", dom, qtypestr(q.qtype), err));
					return (nil, nil, Rserver);
				}
				ttl := int ndblookdef(e, line, "ttl", string zonettl);
				rrs = RR(q.name, q.qtype, q.class, ttl, rdata) :: rrs;
			}
		}

	Taaaa =>
		for(lines := e.find("ip"); lines != nil; lines = tl lines) {
			for((line, matches) := hd lines; matches != nil; matches = tl matches) {
				(rdata, err) := parserdata(("ip", Fipv6, (hd matches).val) :: nil);
				if(err != nil) {
					warn(sprint("findrr %q %s: %s", dom, qtypestr(q.qtype), err));
					return (nil, nil, Rserver);
				}
				ttl := int ndblookdef(e, line, "ttl", string zonettl);
				rrs = RR(q.name, q.qtype, q.class, ttl, rdata) :: rrs;
			}
		}

	Taddr =>
		as, aaaas: list of RR;
		rc: int;
		(as, nil, rc) = findrr(QD(q.name, Ta, q.class), zonename, zonettl, followrefs, refsfollowed);
		if(rc != Rok)
			return (nil, nil, rc);

		(aaaas, nil, rc) = findrr(QD(q.name, Taaaa, q.class), zonename, zonettl, followrefs, refsfollowed);
		if(rc != Rok)
			return (nil, nil, rc);

		# give a records priority over aaaa records
		rrs = concatrrs(as, rrs);
		rrs = concatrrs(aaaas, rrs);

	Tsoa =>
		if(e.find("soa") == nil)
			break;

		fields: list of (string, int, string);
		rs := ("ttl", Fi32, string DefaultTTL) :: ("expire", Fi32, "60") ::
			("retry", Fi32, "60") :: ("refresh", Fi32, "60") :: nil;
		for(; rs != nil; rs = tl rs) {
			(rattr, ftype, default) := hd rs;
			if((v := e.findfirst(rattr)) == nil)
				v = default;
			fields = (rattr, ftype, v) :: fields;
		}

		if((serial := e.findfirst("serial")) == nil) {
			if((dir := (hd ndb.dbs).dir) != nil)
				serial = string dir.mtime;	# this isn't a very good guess
			else
				serial = "1";	# and this isn't any better
		}
		fields = ("serial", Fi32, serial) :: fields;

		# accept mbox=person, mbox=person@dom, or mbox=person.dom
		if((mbox := e.findfirst("mbox")) == nil) {
			mbox = "postmaster." + q.name;
		} else {
			for(i := 0; i < len mbox; i++) {
				if(mbox[i] == '@')
					mbox[i] = '.';
			}
		}
		fields = ("mbox", Fname, mbox) :: fields;

		if((ns := e.findfirst("ns")) == nil)
			ns = q.name;
		fields = ("ns", Fname, ns) :: fields;

		(rdata, err) := parserdata(fields);
		if(err != nil) {
			warn(sprint("findrr %q %s: %s", dom, qtypestr(q.qtype), err));
			return (nil, nil, Rserver);
		}
		rrs = RR(q.name, q.qtype, q.class, zonettl, rdata) :: rrs;

	* =>
		if(q.qtype >= len rattrtab || (rattrs := rattrtab[q.qtype]) == nil) {
			if(q.qtype & Tqmask)
				return (nil, nil, Runimplemented);
			return (nil, nil, Rok);
		}

		if(len rattrs == 1) {	# ns cname
			(rattr, ftype, default) := hd rattrs;
			for(lines := e.find(rattr); lines != nil; lines = tl lines) {
				for((line, matches) := hd lines; matches != nil; matches = tl matches) {
					if((value := (hd matches).val) == nil && (value = default) == nil)
						continue;	# FIXME - print warning
					(rdata, err) := parserdata((rattr, ftype, value) :: nil);
					if(err != nil) {
						warn(sprint("findrr %q %s: %s", dom, qtypestr(q.qtype), err));
						return (nil, nil, Rserver);
					}
					ttl := int ndblookdef(e, line, "ttl", string zonettl);
					rrs = RR(q.name, q.qtype, q.class, ttl, rdata) :: rrs;

					if(ftype == Fname) {
						(ok, hzone) := findzone(value);
						if(ok == 0) {
							(hs, nil, rc) := findrr(QD(value, Taddr, q.class),
								hzone.name, hzone.ttl, followrefs, refsfollowed );
							if(rc == Rok)
								hints = concatrrs(hs, hints);
						}
					}
				}
			}
		} else {	# hinfo mx srv
			# try to find a mandatory attr
			rattr1 := "dom";
			for(rs := rattrs; rs != nil; rs = tl rs) {
				(r, nil, default) := hd rs;
				if(default == nil) {
					rattr1 = r;
					break;
				}
			}

			for(lines := e.find(rattr1); lines != nil; lines = tl lines) {
				fields, tmp: list of (string, int, string);
				(line, nil) := hd lines;
				for(rs = rattrs; rs != nil; rs = tl rs) {
					value: string;
					(rattr, ftype, default) := hd rs;
					if((attrs := line.find(rattr)) == nil && default != nil) {
						value = default;
					} else if(len attrs == 1) {
						value = (hd attrs).val;
					} else {
						warn(sprint("findrr %q %s: expected 1 %q field; saw %d",
							dom, qtypestr(q.qtype), rattr, len attrs ));
						return (nil, nil, Rserver);
					}
					tmp = (rattr, ftype, value) :: tmp;

					if(ftype == Fname) {
						(ok, hzone) := findzone(value);
						if(ok == 0) {
							(hs, nil, rc) := findrr(QD(value, Taddr, q.class),
								hzone.name, hzone.ttl, followrefs, refsfollowed );
							if(rc == Rok)
								hints = concatrrs(hs, hints);
						}
					}
				}
				for(; tmp != nil; tmp = tl tmp)
					fields = hd tmp :: fields;

				(rdata, err) := parserdata(fields);
				if(err != nil) {
					warn(sprint("findrr %q %s: %s", dom, qtypestr(q.qtype), err));
					return (nil, nil, Rserver);
				}

				ttl := int ndblookdef(e, line, "ttl", string zonettl);
				rrs = RR(q.name, q.qtype, q.class, ttl, rdata) :: rrs;
			}
		}
	}

	# look for a cname, add it to the rrs, find the new zone, and retry the query at the new name
	if(followrefs && rrs == nil && q.qtype != Tcname && (cname := e.findfirst("cname")) != nil) {
		if(len refsfollowed > 64) {
			warn("too many refs: " + string len refsfollowed);
			return (nil, nil, Rserver);
		}
		for(rfs := refsfollowed; rfs != nil; rfs = tl rfs) {
			if(hd rfs == cname) {
				warn("ref loop: " + cname);	# saying where the loop began would be nicer
				return (nil, nil, Rserver);
			}
		}

		(crrs, nil, rc) := findrr(QD(q.name, Tcname, q.class), zonename, zonettl, 0, nil);
		if(rc != Rok) {
			warn(sprint("findrr %q %s cname: %s", dom, qtypestr(q.qtype), rcodestr(rc)));
			return (rrs, hints, Rserver);
		}

		(ok, czone) := findzone(cname);
		if(ok < 0)
			return (crrs, hints, Rok);

		(rrs, hints, rc) = findrr(QD(cname, q.qtype, q.class),
			czone.name, czone.ttl, followrefs, cname :: refsfollowed );
		rrs = concatrrs(rrs, crrs);
		return (rrs, hints, rc);
	}

	return (rrs, hints, Rok);
}

parserdata(rdfields: list of (string, int, string)): (array of byte, string)
{
	(rdlen, err) := parsefields(nil, rdfields);
	if(err != nil)
		return (nil, err);

	buf := array[rdlen] of byte;
	(nil, err) = parsefields(buf, rdfields);
	if(err != nil)
		return (nil, err);

	return (buf, nil);
}

parsefields(buf: array of byte, rdfields: list of (string, int, string)): (int, string)
{
	rdlen := 0;

	for(; rdfields != nil; rdfields = tl rdfields) {
		(name, ftype, f) := hd rdfields;
		(n, size, parse, nil) := fieldtab[ftype];

		if(buf != nil) {
			if((err := parse(buf[rdlen:], f)) != nil)
				return (-1, name + ": " + err);
		}

		if(size != nil)
			rdlen += size(f);
		else
			rdlen += n;
	}

	return (rdlen, nil);
}

ndblookdef(entry: ref Dbentry, line: ref Tuples, attr: string, default: string): string
{
	if((pairs := line.find(attr)) != nil)
		return (hd pairs).val;
	if((lines := entry.find(attr)) == nil)
		return default;
	(nil, pairs) = hd lines;
	return (hd pairs).val;
}

ndbfinddom(dom: string): ref Dbentry
{
	h := 5381;
	for(i := 0; i < len dom; i++)
		h = h*31 + dom[i];
	if(h < 0)
		h = int((big h & big 16rFFFFFFFF) % big len domcache);
	else
		h %= len domcache;

	(d, e) := domcache[h];
	if(d == dom)
		return e;

	(e, nil) = ndb.findpair(nil, "dom", dom);
	domcache[h] = (dom, e);
	return e;
}

# https://www.iana.org/assignments/dns-parameters/dns-parameters.xhtml