RFC 1035 - DNS Client Implementation

dns-client.c

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdbool.h>
#include <arpa/inet.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>

#define PROTO_UDP 17

#define ROOT_SERVER "198.41.0.4"
#define HEADER_SIZE (6 * sizeof(uint16_t))
#define MIN_BUFFER_SIZE 4096

/** FLAGS **/

// Message Type
#define FLAG_QR_QUERY 0x0000
#define FLAG_QR_RESPONSE 0x8000

// Query Type
#define FLAG_OPCODE_QUERY 0x0000
#define FLAG_OPCODE_IQUERY 0x0800
#define FLAG_OPCODE_STATUS 0x1000

// Authoritative Answer
#define FLAG_AA_NO 0x0000
#define FLAG_AA_YES 0x0400

// Truncation
#define FLAG_TC_NO 0x0000
#define FLAG_TC_YES 0x0200

// Recursion Desired
#define FLAG_RD_NO 0x0000
#define FLAG_RD_YES 0x0100

// Recursion Available
#define FLAG_RA_NO 0x0000
#define FLAG_RA_YES 0x0080

// Response Code
#define FLAG_RCODE_OK 0x0000
#define FLAG_RCODE_FORMAT_ERROR 0x0001
#define FLAG_RCODE_SERVER_FAILURE 0x0002
#define FLAG_RCODE_NAME_ERROR 0x0003
#define FLAG_RCODE_NOT_IMPLEMENTED 0x0004
#define FLAG_RCODE_REFUSED 0x0005

/** QTYPE ~S **/
#define QTYPE_A 1
#define QTYPE_NS 2
#define QTYPE_MD 3
#define QTYPE_MF 4
#define QTYPE_CNAME 5
#define QTYPE_SOA 6
#define QTYPE_MB 7
#define QTYPE_MG 8
#define QTYPE_MR 9
#define QTYPE_NULL 10
#define QTYPE_WKS 11
#define QTYPE_PTR 12
#define QTYPE_HINFO 13
#define QTYPE_MINFO 14
#define QTYPE_MX 15
#define QTYPE_TXT 16

#define QTYPE_AAAA 28
#define QTYPE_OPT 41

#define QTYPE_AFXR 252
#define QTYPE_MAILB 253
#define QTYPE_MAILA 254
#define QTYPE_ALL 255

/** QCLASS ~S **/
#define QCLASS_IN 1
#define QCLASS_CS 2
#define QCLASS_CH 3
#define QCLASS_HS 4

#define QCLASS_ANY 255

typedef struct {
	uint16_t id;
	uint16_t flags;
	uint16_t qd_count;
	uint16_t an_count;
	uint16_t ns_count;
	uint16_t ar_count;
} dns_header_t;

typedef struct {
	uint8_t len;
	char *chars;
} dns_label_t;

typedef struct {
	uint8_t qnamelen;
	dns_label_t *qname;
	uint16_t qtype;
	uint16_t qclass;
} dns_question_t;

typedef struct {
	uint8_t namelen;
	dns_label_t *name;
	uint16_t type;
	uint16_t class;
	uint32_t ttl;
	uint16_t rdlen;
	char *rdata;

	int _gdo;
} dns_rr_t;

typedef struct {
	dns_header_t hdr;
	dns_question_t qst;
	dns_rr_t *ans;
	dns_rr_t *aut;
	dns_rr_t *add;
} dns_message_t;

typedef struct {
	size_t len;
	char** strings;
} string_list_t;

/** GLOBALS */
int sock;

// Encode header structure
// Returns - number of bytes
int hencode(dns_header_t h, char *buf) {
	uint16_t packed[6] = { htons(h.id), htons(h.flags), htons(h.qd_count), htons(h.an_count), htons(h.ns_count), htons(h.ar_count) };

	memcpy(buf, packed, sizeof(packed));

	return sizeof(packed);
}

// Decode header structure
dns_header_t hdecode(char *buf) {
	uint16_t packed[6] = {0};

	memcpy(packed, buf, sizeof(packed));

	dns_header_t h = {
		.id = ntohs(packed[0]),
		.flags = ntohs(packed[1]),
		.qd_count = ntohs(packed[2]),
		.an_count = ntohs(packed[3]),
		.ns_count = ntohs(packed[4]),
		.ar_count = ntohs(packed[5]),
	};

	return h;
}

// Decode array of labels
// gbuf - global buffer
// soffset - labels start offset in global buffer
// len - size of gbuf
// lensout -> labels size
// out -> next offset
dns_label_t* labelsdecode(char *gbuf, int len, int soffset, int *lenout, int *out) {
	int total = 0;
	dns_label_t *labels = NULL;

	char *buf = gbuf+soffset;

	int i = 0;
	char llen = buf[i];
	bool isptr = false;
	while (i < len && llen != 0) {
		isptr = (llen & 0xc0) == 0xc0;
		if (isptr) {
			uint16_t goffset;
			char packed[2] = { llen & 0x3f, buf[i+1] };
			memcpy(&goffset, packed, sizeof(uint16_t));
			goffset = ntohs(goffset);

			int _total = 0, _skip = 0;
			dns_label_t *_labels = labelsdecode(gbuf, len, goffset, &_total, &_skip);

			for (int k = 0; k < _total; k++) {
				total += 1;
				labels = realloc(labels, sizeof(dns_label_t) * total);

				dns_label_t *_lbl = &_labels[k];
				dns_label_t *label = &labels[total - 1];

				label->len = _lbl->len;
				label->chars = _lbl->chars;
			}

			free(_labels);

			i += 2;
			llen = buf[i];
			break;
		}

		total += 1;
		labels = realloc(labels, sizeof(dns_label_t) * total);

		dns_label_t *label = &labels[total-1];

		label->len = llen;
		label->chars = malloc(sizeof(char) * label->len);

		memset(label->chars, 0, sizeof(char) * label->len);

		memcpy(label->chars, buf+i+1, label->len);

		i += llen + 1;
		llen = buf[i];
	}

	// root zone [zero byte]
	if (isptr == false) i++;

	*out = i;
	*lenout = total;

	return labels;
}

dns_label_t charstringdecode(char *buf) {
	dns_label_t l = {0};

	l.len = buf[0];
	l.chars = malloc(sizeof(char) * l.len + 1);

	memset(l.chars, 0, sizeof(char) * l.len + 1);

	memcpy(l.chars, buf+1, sizeof(char) * l.len);

	return l;
}

// Free labels structure
void labelsfree(dns_label_t *labels, int len) {
	for (int i = 0; i < len; i++) {
		free(labels[i].chars);
	}

	free(labels);
}

// Encode question structure
// Returns - number of bytes
int qencode(dns_question_t q, char *buf) {
	int offset = 0;

	for (int i = 0; i < q.qnamelen; i++) {
		dns_label_t l = q.qname[i];

		buf[offset] = l.len;
		offset++;

		memcpy(buf+offset, l.chars, l.len);
		offset += l.len;
	}

	// root zone [zero byte]
	buf[offset] = 0;
	offset++;

	uint16_t packed[2] = { htons(q.qtype), htons(q.qclass) };

	memcpy(buf+offset, packed, sizeof(packed));
	offset += sizeof(packed);

	return offset;
}

// Decode question structure
dns_question_t qdecode(char *buf, int len, int *out) {
	dns_question_t q = {0};

	// read all qname labels
	int i = 0, namelen = 0;
	q.qname = labelsdecode(buf, len, 0, &namelen, &i);
	q.qnamelen = namelen;

	memcpy(&q.qtype, buf+i, sizeof(uint16_t));
	i += sizeof(uint16_t);

	memcpy(&q.qclass, buf+i, sizeof(uint16_t));
	i += sizeof(uint16_t);

	*out = i;

	q.qtype = ntohs(q.qtype);
	q.qclass = ntohs(q.qclass);

	return q;
}

// Free question structure
void qfree(dns_question_t q) {
	if (q.qname != NULL) labelsfree(q.qname, q.qnamelen);
}

// Encode RR structure
// Returns - number of bytes
int rrencode(dns_rr_t rr, char *buf) {
	int offset = 0;

	for (int i = 0; i < rr.namelen; i++) {
		dns_label_t l = rr.name[i];

		buf[offset] = l.len;
		offset++;

		memcpy(buf+offset, l.chars, l.len);
		offset += l.len;
	}

	// root zone [zero byte]
	buf[offset] = 0;
	offset++;

	uint16_t packed[2] = { htons(rr.type), htons(rr.class) };

	memcpy(buf+offset, packed, sizeof(packed));
	offset += sizeof(packed);

	uint32_t ttl = htonl(rr.ttl);
	memcpy(buf+offset, &ttl, sizeof(uint32_t));
	offset += sizeof(uint32_t);

	uint16_t rdlen = htons(rr.rdlen);
	memcpy(buf+offset, &rdlen, sizeof(uint16_t));
	offset += sizeof(uint16_t);

	memcpy(buf+offset, rr.rdata, sizeof(char) * rr.rdlen);
	offset += sizeof(char) * rr.rdlen;

	return offset;
}

// Decode RR structure
// gbuf - global buffer
// soffset - RR section start offset in global buffer
// len - size of gbuf
// out -> next offset
dns_rr_t rrdecode(char *gbuf, int len, int soffset, int *out) {
	dns_rr_t rr = {0};

	char *buf = gbuf+soffset;

	// read all qname labels
	int i = 0, namelen = 0;
	rr.name = labelsdecode(gbuf, len, soffset, &namelen, &i);
	rr.namelen = namelen;

	memcpy(&rr.type, buf+i, sizeof(uint16_t));
	i += sizeof(uint16_t);

	memcpy(&rr.class, buf+i, sizeof(uint16_t));
	i += sizeof(uint16_t);

	memcpy(&rr.ttl, buf+i, sizeof(uint32_t));
	i += sizeof(uint32_t);

	memcpy(&rr.rdlen, buf+i, sizeof(uint16_t));
	i += sizeof(uint16_t);

	rr.ttl = ntohl(rr.ttl);
	rr.type = ntohs(rr.type);
	rr.class = ntohs(rr.class);
	rr.rdlen = ntohs(rr.rdlen);

	// read rdata
	rr._gdo = i + soffset;
	rr.rdata = malloc(sizeof(char) * rr.rdlen);
	memset(rr.rdata, 0, sizeof(char) * rr.rdlen);
	memcpy(rr.rdata, buf+i, sizeof(char) * rr.rdlen);

	i += sizeof(char) * rr.rdlen;

	*out = i;

	return rr;
}

// Free RR structure
void rrfree(dns_rr_t rr) {
	if (rr.rdata != NULL) free(rr.rdata);
	if (rr.name != NULL) labelsfree(rr.name, rr.namelen);
}

// Encode message structure
int mencode(dns_message_t m, char *buf) {
	int offset = 0;

	offset += hencode(m.hdr, buf);
	offset += qencode(m.qst, buf+offset);

	// encode additional section
	for (int i = 0; i < m.hdr.ar_count; i++) {
		offset += rrencode(m.add[i], buf+offset);
	}

	return offset;
}

// Decode message structure
dns_message_t mdecode(char *buf, int len) {
	int offset = 0;
	dns_message_t m = {0};

	m.hdr = hdecode(buf);

	offset += HEADER_SIZE;

	int rsize = 0;
	m.qst = qdecode(buf+offset, len - offset, &rsize);

	offset += rsize;

	// answer section
	m.ans = malloc(sizeof(dns_rr_t) * m.hdr.an_count);
	memset(m.ans, 0, sizeof(dns_rr_t) * m.hdr.an_count);

	for (int i = 0; i < m.hdr.an_count; i++) {
		m.ans[i] = rrdecode(buf, len, offset, &rsize);

		offset += rsize;
	}

	// authority section
	m.aut = malloc(sizeof(dns_rr_t) * m.hdr.ns_count);
	memset(m.aut, 0, sizeof(dns_rr_t) * m.hdr.ns_count);

	for (int i = 0; i < m.hdr.ns_count; i++) {
		m.aut[i] = rrdecode(buf, len, offset, &rsize);
		
		offset += rsize;
	}

	// additional section
	m.add = malloc(sizeof(dns_rr_t) * m.hdr.ar_count);
	memset(m.add, 0, sizeof(dns_rr_t) * m.hdr.ar_count);

	for (int i = 0; i < m.hdr.ar_count; i++) {
		m.add[i] = rrdecode(buf, len, offset, &rsize);

		offset += rsize;
	}

	return m;
}

// Free message structure
void mfree(dns_message_t m) {
	qfree(m.qst);

	for (int i = 0; i < m.hdr.an_count; i++) {
		rrfree(m.ans[i]);
	}

	if (m.ans != NULL) free(m.ans);

	for (int i = 0; i < m.hdr.ns_count; i++) {
		rrfree(m.aut[i]);
	}

	if (m.aut != NULL) free(m.aut);

	for (int i = 0; i < m.hdr.ar_count; i++) {
		rrfree(m.add[i]);
	}

	if (m.add != NULL) free(m.add);
}

char* strclone(char *s) {
	char *str = malloc(strlen(s) + 1);

	memset(str, 0, strlen(s) + 1);
	strcpy(str, s);

	return str;
}

string_list_t strdotsplit(char *s) {
	string_list_t l = {
		.len = 0,
		.strings = NULL,
	};

	char *str = strclone(s);

	char *next = strtok(str, ".");
	while (next != NULL) {
		l.len++;
		l.strings = realloc(l.strings, sizeof(char**) * l.len);

		l.strings[l.len - 1] = strclone(next);

		next = strtok(NULL, ".");
	}

	free(str);

	return l;
}

void slfree(string_list_t l) {
	for (int i = 0; i < l.len; i++) {
		free(l.strings[i]);
	}

	if (l.strings != NULL) free(l.strings);
}

char* strdotreverse(char *s) {
	int o = 0;
	char *ns = strclone(s);
	string_list_t sl = strdotsplit(s);

	if (sl.strings == NULL) goto bad;

	memset(ns, 0, strlen(ns) + 1);

	for (int i = sl.len-1; i >= 0; i--) {
		int _len = strlen(sl.strings[i]);

		memcpy(ns+o, sl.strings[i], _len);

		o += _len;

		if (i != 0) {
			ns[o] = '.';
			o ++;
		}
	}

	slfree(sl);

	goto good;

bad:
	free(ns);
	return NULL;

good:
	return ns;

}

// Question creation utility
dns_question_t qcreate(char *name, char *type) {
	dns_question_t q = {0};
	string_list_t hosts = strdotsplit(name);

	for (int i = 0; i < hosts.len; i++) {
		char *str = hosts.strings[i];

		q.qnamelen += 1;
		q.qname = realloc(q.qname, sizeof(dns_label_t) * q.qnamelen);

		dns_label_t *label = &q.qname[q.qnamelen - 1];

		label->len = strlen(str);
		label->chars = strclone(str);
	}

	slfree(hosts);

	q.qtype = QTYPE_A;
	q.qclass = QCLASS_IN;

	if (strcmp(type, "A") == 0) q.qtype = QTYPE_A;
	if (strcmp(type, "NS") == 0) q.qtype = QTYPE_NS;
	if (strcmp(type, "MX") == 0) q.qtype = QTYPE_MX;
	if (strcmp(type, "PTR") == 0) q.qtype = QTYPE_PTR;
	if (strcmp(type, "TXT") == 0) q.qtype = QTYPE_TXT;
	if (strcmp(type, "SOA") == 0) q.qtype = QTYPE_SOA;
	if (strcmp(type, "AAAA") == 0) q.qtype = QTYPE_AAAA;
	if (strcmp(type, "CNAME") == 0) q.qtype = QTYPE_CNAME;

	return q;
}

// Query message creation utility
dns_message_t qmcreate(char *name, char *type) {
	dns_message_t m = {0};

	m.qst = qcreate(name, type);

	m.hdr.id = 21;
	m.hdr.flags = FLAG_QR_QUERY | FLAG_OPCODE_QUERY | FLAG_TC_NO | FLAG_RD_YES;
	m.hdr.qd_count = 1;

	// EDNS
	m.hdr.ar_count = 1;
	m.add = malloc(sizeof(dns_rr_t));

	memset(m.add, 0, sizeof(dns_rr_t));

	m.add->type = QTYPE_OPT;
	m.add->class = MIN_BUFFER_SIZE;

	return m;
}

struct sockaddr_in dnshost(const char* host, uint16_t port) {
	struct sockaddr_in h = {0};

	if (inet_pton(AF_INET, host, &h.sin_addr) != 1) {
		puts("dnshost: invalid host");
		exit(1);
	}

	h.sin_port = htons(port);
	h.sin_family = AF_INET;

	return h;
}

void bytesprint(char *buf, int len) {
	for (int i = 0; i < len; i++) {
		printf("%2X ", (unsigned char)buf[i]);
	}

	printf("\ntotal_bytes=%d\n\n", len);
}

int checkstatus(int flags) {
	if ((flags & FLAG_RCODE_REFUSED) != 0) {
		puts(";; RCODE=REFUSED");
		return FLAG_RCODE_REFUSED;
	}
	if ((flags & FLAG_RCODE_NOT_IMPLEMENTED) != 0) {
		puts(";; RCODE=NOT_IMPLEMENTED");
		return FLAG_RCODE_NOT_IMPLEMENTED;
	}
	if ((flags & FLAG_RCODE_NAME_ERROR) != 0) {
		puts(";; RCODE=NAME_ERROR");
		return FLAG_RCODE_NAME_ERROR;
	}
	if ((flags & FLAG_RCODE_SERVER_FAILURE) != 0) {
		puts(";; RCODE=SERVER_FAILURE");
		return FLAG_RCODE_SERVER_FAILURE;
	}
	if ((flags & FLAG_RCODE_FORMAT_ERROR) != 0) {
		puts(";; RCODE=FORMAT_ERROR");
		return FLAG_RCODE_FORMAT_ERROR;
	}

	puts(";; RCODE=NOSTATUS");
	return FLAG_RCODE_OK;
}

int checktrucated(int flags) {
	if ((flags & FLAG_TC_YES) != 0) {
		puts(";; TRUNCATED=YES");
		return FLAG_TC_YES;
	}

	puts(";; TRUNCATED=NO");
	return FLAG_TC_NO;
}

char *striplabels(dns_label_t *labels, int len) {
	int nobytes = 1;
	for (int i = 0; i < len; i++) nobytes += labels[i].len + 1;

	char *str = malloc(sizeof(char) * nobytes);

	memset(str, 0, sizeof(char) * nobytes);

	int offset = 0;
	for (int i = 0; i < len; i++) {
		memcpy(str+offset, labels[i].chars, labels[i].len);
		offset += labels[i].len;

		str[offset] = '.';
		offset++;
	}

	return str;
}

char* stripaddr4(char *buf) {
	uint32_t ipv4;
	char *str = malloc(sizeof(char) * INET_ADDRSTRLEN);

	memcpy(&ipv4, buf, sizeof(uint32_t));
	memset(str, 0, sizeof(char) * INET_ADDRSTRLEN);

	inet_ntop(AF_INET, &ipv4, str, INET_ADDRSTRLEN);

	return str;
}

char *stripns(dns_rr_t rr, char *gbuf, int gbuflen) {
	int len = 0, _o = 0;
	dns_label_t *labels = labelsdecode(gbuf, gbuflen, rr._gdo, &len, &_o);

	char *str = striplabels(labels, len);

	labelsfree(labels, len);

	return str;
}

// Prints dns_label_t[]
void labelprint(dns_label_t *labels, int len) {
	char *str = striplabels(labels, len);
	printf("%s", str);
	free(str);
}

// Prints question
void qprint(dns_question_t qst) {
	printf(";; QUESTION=");

	// print class
	if (qst.qclass == QCLASS_IN) printf("IN ");
	if (qst.qclass == QCLASS_CH) printf("CH ");
	if (qst.qclass == QCLASS_CS) printf("CS ");
	if (qst.qclass == QCLASS_HS) printf("HS ");

	// print type
	if (qst.qtype == QTYPE_A) printf("A ");
	if (qst.qtype == QTYPE_NS) printf("NS ");
	if (qst.qtype == QTYPE_MX) printf("MX ");
	if (qst.qtype == QTYPE_PTR) printf("PTR ");
	if (qst.qtype == QTYPE_TXT) printf("TXT ");
	if (qst.qtype == QTYPE_SOA) printf("SOA ");
	if (qst.qtype == QTYPE_AAAA) printf("AAAA ");
	if (qst.qtype == QTYPE_CNAME) printf("CNAME ");
	
	// print qname
	labelprint(qst.qname, qst.qnamelen);

	printf("\n");
}

// Prints RR
// gbuf - full message raw bytes
// gbuflen - size of gbuf
void rrprint(dns_rr_t rr, char* gbuf, int gbuflen) {
	// print name
	labelprint(rr.name, rr.namelen);

	// print ttl
	printf("\t%10d ", rr.ttl);

	// print class
	if (rr.class == QCLASS_IN) printf("IN ");
	if (rr.class == QCLASS_CH) printf("CH ");
	if (rr.class == QCLASS_CS) printf("CS ");
	if (rr.class == QCLASS_HS) printf("HS ");

	// print type
	if (rr.type == QTYPE_A) printf("A ");
	if (rr.type == QTYPE_NS) printf("NS ");
	if (rr.type == QTYPE_MX) printf("MX ");
	if (rr.type == QTYPE_PTR) printf("PTR ");
	if (rr.type == QTYPE_TXT) printf("TXT ");
	if (rr.type == QTYPE_SOA) printf("SOA ");
	if (rr.type == QTYPE_AAAA) printf("AAAA ");
	if (rr.type == QTYPE_CNAME) printf("CNAME ");
	
	// print answer
	if (rr.class == QCLASS_IN) {
		switch (rr.type) {
			case QTYPE_A:
				{
					char *ipv4str = stripaddr4(rr.rdata);
					printf("\t%s", ipv4str);

					free(ipv4str);
				}
				break;
			case QTYPE_AAAA:
				{
					struct in6_addr ipv6 = {0};
					char ipv6_str[INET6_ADDRSTRLEN];
					memcpy(&ipv6, rr.rdata, sizeof(struct in6_addr));

					if (inet_ntop(AF_INET6, &ipv6, ipv6_str, INET6_ADDRSTRLEN) != NULL) {
						printf("\t%s", ipv6_str);
					}
				}
				break;
			case QTYPE_NS:
			case QTYPE_PTR:
			case QTYPE_CNAME:
				{
					int len = 0, _o = 0;
					dns_label_t *labels = labelsdecode(gbuf, gbuflen, rr._gdo, &len, &_o);

					printf("\t");
					labelprint(labels, len);
					labelsfree(labels, len);
				}
				break;
			case QTYPE_MX:
				{
					uint16_t pref = 0;
					memcpy(&pref, rr.rdata, sizeof(uint16_t));

					int len = 0, _o = 0;
					dns_label_t *labels = labelsdecode(gbuf, gbuflen, rr._gdo+sizeof(uint16_t), &len, &_o);

					printf("\t %2d ", ntohs(pref));
					labelprint(labels, len);
					labelsfree(labels, len);
				}
				break;
			case QTYPE_SOA:
				{
					// MNAME
					int len = 0, _o = 0, _offs = 0;
					dns_label_t *labels = labelsdecode(gbuf, gbuflen, rr._gdo, &len, &_o);

					printf("\t");
					labelprint(labels, len);
					labelsfree(labels, len);

					// RNAME
					_offs += _o;
					labels = labelsdecode(gbuf, gbuflen, rr._gdo+_offs, &len, &_o);

					printf("\t");
					labelprint(labels, len);
					labelsfree(labels, len);

					// SERIAL, REFRESH, RETRY, MINIMUM, EXPIRE
					_offs += _o;
					uint32_t serial, refresh, retry, expire, minimum;

					serial = refresh = retry = expire = minimum = 0;

					memcpy(&serial, rr.rdata+_offs, sizeof(uint32_t));
					_offs += sizeof(uint32_t);

					memcpy(&refresh, rr.rdata+_offs, sizeof(uint32_t));
					_offs += sizeof(uint32_t);

					memcpy(&retry, rr.rdata+_offs, sizeof(uint32_t));
					_offs += sizeof(uint32_t);

					memcpy(&expire, rr.rdata+_offs, sizeof(uint32_t));
					_offs += sizeof(uint32_t);

					memcpy(&minimum, rr.rdata+_offs, sizeof(uint32_t));
					_offs += sizeof(uint32_t);

					serial = ntohl(serial);
					refresh = ntohl(refresh);
					retry = ntohl(retry);
					expire = ntohl(expire);
					minimum = ntohl(minimum);

					printf(" %d %d %d %d %d", serial, refresh, retry, expire, minimum);
				}
				break;
			case QTYPE_TXT:
				{
					dns_label_t l = charstringdecode(rr.rdata);

					printf("\t\"%s\"", l.chars);
					free(l.chars);
				}
				break;
		}
	}

	printf("\n");
}

// Prints message structure
void mprint(dns_message_t msg, char *gbuf, int gbuflen) {
	printf(";; QUERY=%d ;ANSWER=%d ;AUTHORITY=%d ;ADDITIONAL=%d\n\n", msg.hdr.qd_count, msg.hdr.an_count, msg.hdr.ns_count, msg.hdr.ar_count);

	printf(";; ID=%d\n", msg.hdr.id);
	checkstatus(msg.hdr.flags);
	checktrucated(msg.hdr.flags);

	qprint(msg.qst);

	if (msg.hdr.an_count > 0) {
		puts(";; ANSWER(S) ^|^" );
		for (int i = 0; i < msg.hdr.an_count; i++) rrprint(msg.ans[i], gbuf, gbuflen);
	}

	if (msg.hdr.ns_count > 0) {
		puts(";; AUTHORITY ^|^" );
		for (int i = 0; i < msg.hdr.ns_count; i++) rrprint(msg.aut[i], gbuf, gbuflen);
	}

	if (msg.hdr.ar_count > 0) {
		puts(";; ADDITIONAL ^|^" );
		for (int i = 0; i < msg.hdr.ar_count; i++) rrprint(msg.add[i], gbuf, gbuflen);
	}
}

// Returns number of bytes
int dnsrequest(dns_message_t *msg, char *bytes, char *host, char *name, char *type) {
	int nobytes = 0;
	struct sockaddr_in hostaddr = dnshost(host, 53);

	dns_message_t req = qmcreate(name, type);
	nobytes = mencode(req, bytes);

	mfree(req);

	#ifdef DEBUG
	bytesprint(bytes, nobytes);
	#endif

	if (sendto(sock, bytes, nobytes, MSG_NOSIGNAL, (const struct sockaddr *)&hostaddr, sizeof(hostaddr)) < 0) return -1;

	memset(bytes, 0, MIN_BUFFER_SIZE);
	if ((nobytes = recv(sock, bytes, MIN_BUFFER_SIZE, MSG_NOSIGNAL)) < 0) return -1;

	#ifdef DEBUG
	bytesprint(bytes, nobytes);
	#endif

	*msg = mdecode(bytes, nobytes);

	return nobytes;
}

char* resolvenshost(char *ns) {
	int nobytes = 0;
	dns_message_t res = {0};
	char buf[MIN_BUFFER_SIZE];

	char *host = ROOT_SERVER, *nshost = NULL;

	while (true) {
		nobytes = dnsrequest(&res, buf, host, ns, "A");

		mprint(res, buf, nobytes);
		puts("\n---\n---\n");

		if (res.hdr.an_count > 0) {
			for (int i = 0; i < res.hdr.an_count; i++) {
				if (res.ans[i].type == QTYPE_A) {
					nshost = stripaddr4(res.ans[i].rdata);
					break;
				}
			}

			mfree(res);
			break;
		}

		bool found_next_host = false;

		for (int i = 0; i < res.hdr.ar_count; i++) {
			if (res.add[i].type == QTYPE_A) {
				host = stripaddr4(res.add[i].rdata);
				found_next_host = true;
				break;
			}
		}

		if (found_next_host == false) {
			for (int i = 0; i < res.hdr.ns_count; i++) {
				if (res.aut[i].type == QTYPE_NS) {
					char *ns = stripns(res.aut[i], buf, nobytes);
					host = resolvenshost(ns);
					free(ns);
					break;
				}
			}
		}

		mfree(res);

		if (host == NULL) break;
	}

	return nshost;
}

int main(int argc, char **argv) {
	if ((sock = socket(PF_INET, SOCK_DGRAM, PROTO_UDP)) < 0) goto bad;

	char *name = ".";
	char *type = "A";
	char *host = "8.8.8.8";

	if (argc >= 2) name = argv[1];
	if (argc >= 3) type = argv[2];

	if (strcmp(name, "-x") == 0) {
		// convert to [ipv4].in-addr.arpa
		name = strdotreverse(type);
		name = realloc(name, strlen(name) + strlen(".in-addr.arpa") + 1);
		name = strcat(name, ".in-addr.arpa");

		type = "PTR";

		if (name == NULL) {
			errno = EINVAL;
			goto bad;
		}
	}

	int nobytes = 0;
	dns_message_t res = {0};
	char buf[MIN_BUFFER_SIZE];

	if (strcmp(name, "+trace") == 0) {
		name = type;
		type = "A";
		host = ROOT_SERVER;

		if (argc >= 4) type = argv[3];

		while (true) {
			nobytes = dnsrequest(&res, buf, host, name, type);

			mprint(res, buf, nobytes);
			puts("\n---\n---\n");

			if (res.hdr.an_count > 0) break; // if answer in response, break
			if ((res.hdr.flags & FLAG_AA_YES) == FLAG_AA_YES) break; // if response is authoritative, break

			bool next_host_found = false;

			// check additional section for A responses
			// if A found: replace host = <value>
			for (int i = 0; i < res.hdr.ar_count; i++) {
				if (res.add[i].type == QTYPE_A) {
					next_host_found = true;
					host = stripaddr4(res.add[i].rdata);
					break;
				}
			}

			// if no additional section, check authority section for NS
			// if NS found , make A request to host with name=ns
			// if A gotten back: replace host =<value>
			if (next_host_found == false) {
				bool name_server_found = false;

				for (int i = 0; i < res.hdr.ns_count; i++) {
					if (res.aut[i].type == QTYPE_NS) {
						name_server_found = true;

						char *ns = stripns(res.aut[i], buf, nobytes);

						printf("\n---\nRESOLVING %s\n---\n", ns);
						host = resolvenshost(ns);

						if (host == NULL) {
							printf("\n---\nFAILED TO RESOLVE %s\n---\n", ns);
							exit(1);
						}

						printf("\n---\nRESOLVED %s\n---\n", ns);

						free(ns);
						next_host_found = true;

						break;
					}
				}
			}

			if (next_host_found == false) break;

			mfree(res);
		}

		mfree(res);

		goto good;
	}

	if ((nobytes = dnsrequest(&res, buf, host, name, type)) < 0) goto bad;

	mprint(res, buf, nobytes);

	mfree(res);

	goto good;

bad:
	puts(strerror(errno));
	close(sock);
	return 1;

good:
	close(sock);
	return 0;
}