//
// $Id: dnstracer.c,v 1.31 2002/02/24 21:59:23 mavetju Exp $
//

//
// Copyright (c) 2002 by Edwin Groothuis, edwin@mavetju.org.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY FATAL DIMENSIONS AND CONTRIBUTORS ``AS
// IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
// STAFF OF FATAL DIMENSIONS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
// INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
// OF THE POSSIBILITY OF SUCH DAMAGE.
//

#ifdef WIN32
    #include <winsock.h>
    #include <io.h>
    #include "getopt.h"
    // To reduce the amount of #ifdef's, these two are defined.
    // rand()/srand() is ISO C89 naming but it's obsoleted according
    // to the man-page.
    #define random	rand
    #define srandom	srand
#else
    #include <unistd.h>
    #include <sys/time.h>
    #include <sys/param.h>
    #include <sys/socket.h>
    #include <netinet/in.h>
    #include <arpa/inet.h>
    #include <arpa/nameser.h>
    #include <netdb.h>
    #include <resolv.h>
#endif

#include <sys/types.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include "dnstracer_broken.h"
#include "config.h"

#define DEFAULT_RETRIES	3
#define DEFAULT_TIMEOUT	15
#define DEFAULT_CACHING	1
#define DEFAULT_OVERVIEW	0
#define DEFAULT_QUERYTYPE	ns_t_a

int	verbose=0;
int	global_overview=DEFAULT_OVERVIEW;
int	global_retries=DEFAULT_RETRIES;
int	global_timeout=DEFAULT_TIMEOUT;
int	global_caching=DEFAULT_CACHING;
int	global_querytype=DEFAULT_QUERYTYPE;

/*****************************************************************************/

struct arecord {
    char *		server_name;
    char *		server_ip;
    int			type;
    char *		rr_name;
    char *		rr_data;
    struct arecord *	next;
};

struct busy {
    char *		server;
    struct busy *	next;
};

struct answer {
    char *		server;
    struct answer *	next;
};

struct dnssession {
    struct dnsheader *		send_header;	// The DNS header being sent
    struct dnsquestion *	send_question;	// The DNS question being sent
    struct dnsheader *		recv_header;	// The DNS header received
    struct dnsquestion *	recv_question;	// The DNS question received
    struct dnsrr *		answer;		// First Answer RR received
    struct dnsrr *		authority;	// First Authority RR received
    struct dnsrr *		additional;	// First Additional RR received
    struct dnssession *		next;

    char *			server;		// First server being queried
    char *			host;		// Hostname being queried

    int				recv_len;		// Raw packet with
    char *			recv_pkt;		// with pointers to...
    char *			recv_pkt_header;	// - header
    char *			recv_pkt_question;	// - question
    char *			recv_pkt_answer;	// - first answer RR
    char *			recv_pkt_authority;	// - first authority RR
    char *			recv_pkt_additional;	// - first additional RR

    int				socket;
};

struct dnsheader {
	unsigned short	identification;
	union {
	    unsigned short	flags;
	    struct bit {
#ifdef WORDS_BIGENDIAN
		unsigned char qr:1;
		unsigned char opcode:4;
		unsigned char aa:1;
		unsigned char tc:1;
		unsigned char rd:1;
		unsigned char ra:1;
		unsigned char zero:3;
		unsigned char rcode:4;
#else
		unsigned char rcode:4;
		unsigned char zero:3;
		unsigned char ra:1;
		unsigned char rd:1;
		unsigned char tc:1;
		unsigned char aa:1;
		unsigned char opcode:4;
		unsigned char qr:1;
#endif
	    } bit;
	} flags;
	unsigned short	nquestions;
	unsigned short	nanswerRR;
	unsigned short	nauthorityRR;
	unsigned short	nadditionalRR;
};

struct dnsquestion {
	unsigned int	querylength;
	unsigned char *	query;
	unsigned short	type;
	unsigned short	class;
};

struct dnsrr {
	unsigned char *	domainname;
	unsigned char *	domainname_string;
	unsigned short	type;
	unsigned short	class;
	unsigned int	ttl;
	unsigned short	datalength;
	unsigned char *	data;
	unsigned char * data_string;	// parsed version of data if possible
	struct dnsrr *	next;
};

/*****************************************************************************/

char *get_resource(int type,struct dnssession *session,char *buffer,int dots);
char *printablename(char *name,int withdots);

/*****************************************************************************/

//
// Extract information from received packets.
//

unsigned int getlong(unsigned char *s) {
    return 256*256*256*s[0]+256*256*s[1]+256*s[2]+s[3];
}

unsigned short getshort(unsigned char *s) {
    return 256*s[0]+s[1];
}

char *getname(struct dnssession *session,char **thisname) {
    int		compressing=0;
    char *	p;
    static char	hostname[NS_MAXDNAME];

    //
    // Copy the name out of a received packet. It can be compressed.
    //

    //
    // If the name is empty, just return a dot.
    //
    if (*thisname[0]==0) {
	strcpy(hostname,"\1.");
	(*thisname)++;
	return hostname;
    }

    p=*thisname;
    memset(hostname,0,sizeof(hostname));
    while (p[0]!=0) {
	//
	// If a name is being compressed, set the pointer to the start of
	// the packet plus the offset. If this is the first compression,
	// move the end-of-this-name pointer two places further and stop
	// changing it from now.
	//
	if ((p[0]&0xc0)!=0) {
	    unsigned int offset;
	    char oldp;

	    oldp=p[0];
	    p[0]&=0x3f;
	    offset=getshort(p);
	    p[0]=oldp;
	    p=session->recv_pkt+offset;
	    if (compressing==0) *thisname+=2;

	    compressing=1;
	    continue;
	}

	//
	// Just copy p[0]+1 bytes (+1 to save the length-byte). If
	// compression is not going on, move the end-of-this-name
	// pointer. The check for the next character being 0 is a
	// hack to make sure the end-of-name marked is skipped over
	// before returning the packet.
	// 
	//
	memcpy(hostname+strlen(hostname),p,p[0]+1);
	if (compressing==0) {
	    *thisname+=p[0]+1;
	    if (*thisname[0]==0) *thisname+=1;
	}
	p+=p[0]+1;
    }

    return hostname;
}

char *extract_rr(struct dnssession *session,char *thisrr,struct dnsrr **rr) {
    struct dnsrr *	RR;
    char *		domainname;
    char *		p;

    RR=(struct dnsrr *)calloc(1,sizeof(struct dnsrr));
    RR->next=*rr;

    //
    // Extract just one resource-record.
    // If the record is a ns_t_ns or ns_t_cname, cache the name 
    // into data_string.
    //
    domainname=getname(session,&thisrr);
    RR->domainname=strdup(domainname);
    RR->domainname_string=strdup(printablename(domainname,1));
    RR->type=getshort(thisrr);
    RR->class=getshort(thisrr+2);
    RR->ttl=getlong(thisrr+4);
    RR->datalength=getshort(thisrr+8);
    RR->data=(unsigned char *)calloc(1,RR->datalength);
    memcpy(RR->data,thisrr+10,RR->datalength);

    p=thisrr+10;
    RR->data_string=strdup(get_resource(RR->type,session,p,1));
    thisrr+=10+RR->datalength;

    *rr=RR;
    return thisrr;
}

void extract_data(struct dnssession *session) {
    struct dnsheader *	header=NULL;
    struct dnsquestion *question=NULL;
    struct dnsrr *	answer=NULL;
    struct dnsrr *	authority=NULL;
    struct dnsrr *	additional=NULL;

    char *	pheader;
    char *	pquestion;
    char *	panswer;
    char *	pauthority;
    char *	padditional;

    char *pbuffer;
    int i;

    pbuffer=session->recv_pkt;

    //
    // Extract the header.
    //
    session->recv_pkt_header=pbuffer;
    pheader=pbuffer;
    header=(struct dnsheader *)calloc(1,sizeof(struct dnsheader));
    memcpy(header,session->recv_pkt,sizeof(struct dnsheader));
    header->identification=ntohs(header->identification);
    header->flags.flags=ntohs(header->flags.flags);
    header->nquestions=ntohs(header->nquestions);
    header->nanswerRR=ntohs(header->nanswerRR);
    header->nauthorityRR=ntohs(header->nauthorityRR);
    header->nadditionalRR=ntohs(header->nadditionalRR);
    pbuffer+=sizeof(struct dnsheader);

    //
    // Extract the questions RR.
    //
    session->recv_pkt_question=pbuffer;
    pquestion=pbuffer;
    question=(struct dnsquestion *)calloc(1,sizeof(struct dnsquestion));
    question->query=getname(session,&pquestion);
    question->type=getshort(pquestion);
    question->class=getshort(pquestion+2);
    pbuffer=pquestion+4;

    //
    // Extract the answer RR
    //
    session->recv_pkt_answer=pbuffer;
    for (i=0;i<header->nanswerRR;i++) {
	panswer=pbuffer;
	pbuffer=extract_rr(session,panswer,&answer);
    }

    //
    // Extract the authority RR
    //
    session->recv_pkt_authority=pbuffer;
    for (i=0;i<header->nauthorityRR;i++) {
	pauthority=pbuffer;
	pbuffer=extract_rr(session,pauthority,&authority);
    }

    //
    // Extract the additional RR
    //
    session->recv_pkt_additional=pbuffer;
    for (i=0;i<header->nadditionalRR;i++) {
	padditional=pbuffer;
	pbuffer=extract_rr(session,padditional,&additional);
    }

    session->recv_header=header;
    session->recv_question=question;
    session->answer=answer;
    session->additional=additional;
    session->authority=authority;
}

/*****************************************************************************/

//
// Dump verbose data to the screen
//

char *printablename(char *name,int withdots) {
    static char hostname[NS_MAXDNAME];
    char *p,q;

    //
    // Convert the name from label-format into 'human' readable format,
    // either with dots or the size of the label as seperators.
    //
    if (name==NULL || name[0]==0) {
	if (withdots==0)
	    strcpy(hostname,"(0)root");
	else
	    strcpy(hostname,".");
	return hostname;
    }

    hostname[0]=0;
    p=name;
    while (p[0]!=0) {
	if (withdots==0)
	    sprintf(hostname+strlen(hostname),"(%d)",p[0]);
	else
	    strcat(hostname,".");
	q=p[p[0]+1];
	p[p[0]+1]=0;
	sprintf(hostname+strlen(hostname),"%s",p+1);
	p=p+p[0]+1;
	p[0]=q;
    }

    if (withdots==0)
	return hostname;
    else
	return hostname+1;	// ignore the dot at the beginning of the string
}

char *get_class(int class) {
    switch (class) {
    case ns_c_in:	return "Internet";
    case ns_c_chaos:	return "MIT Chaos-net";
    case ns_c_hs:	return "MIT Hesiod";
    case ns_c_none:	return "Pre-req in update";
    case ns_c_any:	return "Wildcard";
    default:		return "unknown";
    }
}

char *get_type(int type) {
    switch (type) {
    case ns_t_a:	return "A";
    case ns_t_ns:	return "NS";
    case ns_t_cname:	return "CNAME";
    case ns_t_soa:	return "SOA";
    case ns_t_ptr:	return "PTR";
    default:		return "unknown";
    }
}

char *get_ttl(int ttl) {
    static char retval[NS_MAXDNAME];

    //
    // Return the TTL as a weeks/days/hours/minuts/seconds value
    //

    retval[0]=0;
    if (ttl>7*24*60*60) {
	sprintf(retval,"%dw",ttl/(7*24*60*60));
	ttl%=7*24*60*60;
    }
    if (ttl>24*60*60) {
	sprintf(retval+strlen(retval),"%dd",ttl/(24*60*60));
	ttl%=24*60*60;
    }
    if (ttl>60*60) {
	sprintf(retval+strlen(retval),"%dh",ttl/(60*60));
	ttl%=60*60;
    }
    if (ttl>60) {
	sprintf(retval+strlen(retval),"%dm",ttl/(60));
	ttl%=60;
    }
    if (ttl>0) {
	sprintf(retval+strlen(retval),"%ds",ttl);
    }

    return retval;
}

char *get_resource(int type,struct dnssession *session,char *buffer,int dots) {
    static char retval[NS_MAXDNAME];

    //
    // Returns a parsed resource-data string. Only needed for
    // A, NS and CNAME records.
    //

    switch (type) {
    case  ns_t_a:
	sprintf(retval,"%hu.%hu.%hu.%hu",
		(unsigned char)buffer[0],
		(unsigned char)buffer[1],
		(unsigned char)buffer[2],
		(unsigned char)buffer[3]);
	return retval;

    case ns_t_aaaa:
	sprintf(retval,"%02x%02x:%02x%02x:%02x%02x:%02x%02x:"
		       "%02x%02x:%02x%02x:%02x%02x:%02x%02x",
		(unsigned char)buffer[ 0],(unsigned char)buffer[ 1],
		(unsigned char)buffer[ 2],(unsigned char)buffer[ 3],
		(unsigned char)buffer[ 4],(unsigned char)buffer[ 5],
		(unsigned char)buffer[ 6],(unsigned char)buffer[ 7],
		(unsigned char)buffer[ 8],(unsigned char)buffer[ 9],
		(unsigned char)buffer[10],(unsigned char)buffer[11],
		(unsigned char)buffer[12],(unsigned char)buffer[13],
		(unsigned char)buffer[14],(unsigned char)buffer[15]
		);
	return retval;

    case ns_t_cname:
	sprintf(retval,printablename(getname(session,&buffer),dots));
	return retval;

    case ns_t_txt:
	sprintf(retval,printablename(getname(session,&buffer),dots));
	return retval;

    case ns_t_mx:
    {
	unsigned short us;

	us=getshort(buffer);
	buffer+=2;
	sprintf(retval,"%hu %s",us,printablename(getname(session,&buffer),dots));
	return retval;
    }

    case ns_t_hinfo:
	sprintf(retval,printablename(getname(session,&buffer),dots));
	return retval;

    case ns_t_ns:
	sprintf(retval,printablename(getname(session,&buffer),dots));
	return retval;

    default: return "unknown";
    }

}

void dump_question(struct dnsquestion *question) {
    printf("- Queryname:            %s\n",printablename(question->query,0));
    printf("- Type:                 %hu (%s)\n",
				    question->type,get_type(question->type));
    printf("- Class:                %hu (%s)\n",
				    question->class,get_class(question->class));
}

void dump_header(struct dnsheader *header) {
    printf("- Identifier:           0x%04hX\n",header->identification);
    printf("- Flags:                0x%02hX (",header->flags.flags);

    if (header->flags.bit.qr) printf("R "); else printf("Q ");
    if (header->flags.bit.aa) printf("AA ");
    if (header->flags.bit.tc) printf("TC ");
    if (header->flags.bit.rd) printf("RD ");
    if (header->flags.bit.ra) printf("RA ");
    printf(")\n");

    printf("- Opcode:               %hu ",header->flags.bit.opcode);
    switch (header->flags.bit.opcode) {
    case 0: printf("(Standard query)\n");break;
    case 1: printf("(Inverse query)\n");break;
    case 2: printf("(Server status request)\n");break;
    case 4: printf("(Notify)\n");break;
    case 5: printf("(Update)\n");break;
    default: printf("(unknown)\n");
    }

    printf("- Return code:          %hu ",header->flags.bit.rcode);
    switch (header->flags.bit.rcode) {
    case 0: printf("(No error)\n");break;
    case 1: printf("(Format error)\n");break;
    case 2: printf("(Server failure)\n");break;
    case 3: printf("(Name error)\n");break;
    case 4: printf("(Not implemented)\n");break;
    case 5: printf("(Refused)\n");break;
    case 6: printf("(Name exists)\n");break;
    case 7: printf("(RRset exists)\n");break;
    case 8: printf("(RRset does not exist)\n");break;
    case 9: printf("(Not authoritive)\n");break;
    case 10: printf("(Zone of record different from zone section)\n");break;
    default: printf("(unknown)\n");break;
    }

    printf("- Number questions:     %hu\n",header->nquestions);
    printf("- Number answer RR:     %hu\n",header->nanswerRR);
    printf("- Number authority RR:  %hu\n",header->nauthorityRR);
    printf("- Number additional RR: %hu\n",header->nadditionalRR);
}

void dump_rr(struct dnsrr *rr,struct dnssession *session) {
    printf("- Domainname:           %s\n",printablename(rr->domainname,0));
    printf("- Type:                 %hu (%s)\n",
				    rr->type,get_type(rr->type));
    printf("- Class:                %hu (%s)\n",
				    rr->class,get_class(rr->class));
    printf("- TTL:                  %u (%s)\n",
				    rr->ttl,get_ttl(rr->ttl));
    printf("- Resource length:      %hu\n",rr->datalength);
    printf("- Resource data:        %s\n",
				    get_resource(rr->type,session,rr->data,0));
}

void dump_data( struct sockaddr_in *dest,struct dnssession *session) {
    struct dnsrr *answerrr;
    struct dnsrr *authorityrr;
    struct dnsrr *additionalrr;

    if (verbose==0) return;

    //
    // Dumps the output of session on the screen.
    //

    if (dest!=NULL) {
	printf("IP HEADER\n");
	printf("- Destination address:  %s\n",inet_ntoa(dest->sin_addr));
    }

    if (session->send_header!=NULL && session->recv_header==NULL) {
	printf("DNS HEADER (send)\n");
	dump_header(session->send_header);
    }

    if (session->recv_header!=NULL) {
	printf("DNS HEADER (recv)\n");
	dump_header(session->recv_header);
    }

    if (session->send_question!=NULL && session->recv_question==NULL) {
	printf("QUESTIONS (send)\n");
	dump_question(session->send_question);
    }
    if (session->recv_question!=NULL) {
	printf("QUESTIONS (recv)\n");
	dump_question(session->recv_question);
    }

    answerrr=session->answer;
    while (answerrr!=NULL) {
	printf("ANSWER RR\n");
	dump_rr(answerrr,session);
	answerrr=answerrr->next;
    }

    authorityrr=session->authority;
    while (authorityrr!=NULL) {
	printf("AUTHORITY RR\n");
	dump_rr(authorityrr,session);
	authorityrr=authorityrr->next;
    }

    additionalrr=session->additional;
    while (additionalrr!=NULL) {
	printf("ADDITIONAL RR\n");
	dump_rr(additionalrr,session);
	additionalrr=additionalrr->next;
    }
}

/*****************************************************************************/

//
// Packet creation routines
//

unsigned char *create_packet(struct dnssession *session) {
    unsigned char *	pkt;
    struct dnsheader	nheader;	// networked header
    struct dnsquestion	nquestion;	// networked question
    int			len;

    //
    // Transform a "host" packet into a "network" packet.
    // In other words, copy everything and byte-swap some field.
    //

    len=sizeof(struct dnsheader)+session->send_question->querylength+4;
    pkt=(unsigned char *)calloc(1,len);

    memcpy(&nheader,session->send_header,sizeof(struct dnsheader));
    memcpy(&nquestion,session->send_question,sizeof(struct dnsquestion));

    nheader.identification=htons(session->send_header->identification);
    nheader.flags.flags=htons(session->send_header->flags.flags);
    nheader.nquestions=htons(session->send_header->nquestions);
    nheader.nanswerRR=htons(session->send_header->nanswerRR);
    nheader.nauthorityRR=htons(session->send_header->nauthorityRR);
    nheader.nadditionalRR=htons(session->send_header->nadditionalRR);

    nquestion.type=htons(session->send_question->type);
    nquestion.class=htons(session->send_question->class);

    memcpy(pkt,&nheader,sizeof(struct dnsheader));
    memcpy(pkt+sizeof(struct dnsheader),nquestion.query,nquestion.querylength);
    memcpy(pkt+sizeof(struct dnsheader)+nquestion.querylength,&(nquestion.type),4);

    return pkt;
}

/*****************************************************************************/

//
// Network routines
//

int create_socket(void) {
    int	s;

    if ((s=socket(PF_INET,SOCK_DGRAM,0))<0) {
	perror("create_socket/socket");
	exit(1);
    }

    return s;
}

int send_data(char *server,struct dnssession *session) {
    int		cc;
    char *	pkt;
    int		len;
    struct sockaddr_in dest;

    len=sizeof(struct dnsheader)+session->send_question->querylength+4;

    memset(&dest,0,sizeof(struct sockaddr_in));
    dest.sin_family=AF_INET;
    dest.sin_port=htons(53);
    dest.sin_addr.s_addr=inet_addr(server);

    dump_data(&dest,session);
    pkt=create_packet(session);

    if ((cc=sendto(session->socket,pkt,len,0,
		(struct sockaddr *)&dest,sizeof(struct sockaddr_in)))==-1) {
	perror("send_data/sendto");
//	exit(1);
    }

    free(pkt);

    return cc;
}

int receive_data(struct dnssession *session) {
    char		buffer[2048];
    int			len;
    fd_set		in_set;
    struct timeval	timeout;

    timeout.tv_sec=global_timeout;
    timeout.tv_usec=0;

    FD_ZERO(&in_set);
    FD_SET(session->socket,&in_set);

    if (select(session->socket+1,&in_set,NULL,NULL,&timeout)<0)
	return 2;
    if (!FD_ISSET(session->socket,&in_set))
	return 3;
    if ((len=recv(session->socket,buffer,sizeof(buffer),0))==-1)
	return 1;

    if (getshort(buffer)!=session->send_header->identification) {
	fprintf(stderr,"Expected id: %hx, received id: %hx\n",
	    session->send_header->identification,getshort(buffer));
	return 4;
    }

    session->recv_len=len;
    session->recv_pkt=(char *)calloc(1,len);
    memcpy(session->recv_pkt,buffer,len);
    extract_data(session);
    dump_data(NULL,session);
    return 0;
}

/*****************************************************************************/

//
// Record creation routines
//

void create_header(struct dnssession *session) {

    session->send_header=(struct dnsheader *)calloc(1,sizeof(struct dnsheader));

    //
    // Create a random identifier between 0 and 32675. It could be up to
    // 65535, but the high bit sometimes screws things up when comparing
    // the value received. Looks like it has something to do with
    // one-complement and two-complement, but don't know how to solve it.
    //
    session->send_header->identification    =random() & 0x7F7F;
    session->send_header->nquestions	    =1;
}

void create_question(struct dnssession *session,char *name) {
    char *p,*q;

    session->send_question=
	(struct dnsquestion *)calloc(1,sizeof(struct dnsquestion));

    session->send_question->querylength=strlen(name)+2;
    session->send_question->query=
	(unsigned char *)calloc(1,session->send_question->querylength+2);
    strcpy(session->send_question->query+1,name);

    p=session->send_question->query+1;
    q=session->send_question->query;
    while (p[0]!=0) {
	if (p[0]=='.') {
	    q[0]=p-q-1;
	    q=p;
	}
	p++;
    }
    q[0]=p-q-1;

    session->send_question->type=global_querytype;
    session->send_question->class=ns_c_in;
}

/*****************************************************************************/

//
// A record caching routines.
// It's just a linked list which hold a bunch of IP address from which
// we have gotten answers.
//

struct arecord *arecords=NULL;

void add_arecord(struct dnssession *session,struct dnsrr *rr,
		 char *server_name,char *server_ip) {
    struct arecord *	arecord;

    arecord=(struct arecord *)calloc(1,sizeof(struct arecord));
    arecord->server_name=strdup(server_name);
    arecord->server_ip=strdup(server_ip);
    arecord->rr_name=strdup(printablename(rr->domainname,1));

    if (rr->data_string==NULL)
	arecord->rr_data=NULL;
    else
	arecord->rr_data=strdup(rr->data_string);

    arecord->next=arecords;
    arecords=arecord;
}

void display_arecords(void) {
    struct arecord *	arecord;
    int			i;
    char		s[10];

    arecord=arecords;
    while (arecord!=NULL) {
	printf("%s (%s)%n",
	    arecord->server_name,arecord->server_ip,&i);
	if (40-i<1)
	    printf(" ");
	else {
	    sprintf(s,"%%%ds",40-i);
	    printf(s," ");
	}
	printf("%s -> %s\n",arecord->rr_name,arecord->rr_data);
	arecord=arecord->next;
    }
}

/*****************************************************************************/

//
// Answer caching routines.
// It's just a linked list which hold a bunch of IP address from which
// we have gotten answers.
//

struct answer *answers=NULL;

void add_answer(char *server) {
    struct answer *answer;

    answer=(struct answer *)calloc(1,sizeof(struct answer));
    answer->server=strdup(server);
    answer->next=answers;
    answers=answer;
}

int has_answer(char *server) {
    struct answer *answer;

    answer=answers;
    while (answer!=NULL) {
	if (strcmp(answer->server,server)==0)
	    return 1;
	answer=answer->next;
    }
    return 0;
}

/*****************************************************************************/

//
// Busy signal routines.
// It's just a linked list which hold a bunch of IP address of servers
// we are currently querying. Just to prevent that we query until we're
// out of memory.
//

struct busy *busies=NULL;

void add_busy(char *server) {
    struct busy *busy;

    busy=(struct busy *)calloc(1,sizeof(struct busy));
    busy->server=strdup(server);
    busy->next=busies;
    busies=busy;
}

void remove_busy(char *server) {
    struct busy *busy,*prev;

    if (strcmp(busies->server,server)==0) {
	busy=busies;
	busies=busies->next;
	free(busy);
	return;
    }

    prev=busies;
    busy=prev->next;
    while (busy!=NULL) {
	if (strcmp(busy->server,server)==0) {
	    prev->next=busy->next;
	    free(busy);
	    return;
	}
    }
}

int is_busy(char *server) {
    struct busy *busy;

    busy=busies;
    while (busy!=NULL) {
	if (strcmp(busy->server,server)==0)
	    return 1;
	busy=busy->next;
    }
    return 0;
}

/*****************************************************************************/

//
// The core of this program
//

int create_session(char *host,
		    char *server_ip,char *server_name,char *server_authfor,
		    int depth,char *prefix,int last) {
    struct dnssession * session;
    struct dnsrr *	rrauth;
    struct dnsrr *	rradd;
    int			i,retval,errorcode;
    char		s[NS_MAXDNAME];

    //
    // Print the graphs in front of the servernames
    //
    if (depth!=0) {
	printf("%s%c",prefix,last==1?' ':'|');
	printf("\\___ ");
    }

    printf("%s ",server_name);

    if (server_authfor!=NULL)
	printf("[%s] ",server_authfor);

    if (server_ip[0]==0) {
	printf("(No IP address)");
	return 1;
    }

    printf("(%s) ",server_ip);
    fflush(stdout);

    //
    // If this address is already being queried, ignore it to prevent
    // recursion. Do not add it as being cached, because one or more 
    // records in it might be unreachable.
    //
    if (is_busy(server_ip)==1) {
	printf("Lame server ");
	fflush(stdout);
	return 0;
    }

    //
    // Ignore things we have already displayed
    //
    if (global_caching && has_answer(server_ip)) {
	printf("(cached)");
	return 0;
    }

    //
    // To prevent infinite recursion, mark this server as being probed
    //
    add_busy(server_ip);

    //
    // Create a nice DNS packet. Each session has its own port, so we
    // don't have to worry about packets received from previous sessions.
    //
    session=(struct dnssession *)calloc(1,sizeof(struct dnssession));
    session->socket=create_socket();
    session->server=strdup(server_ip);
    session->host=strdup(host);
    create_header(session);
    create_question(session,host);

    //
    // Send the packet and wait for an answer.
    //
    errorcode=0;
    for (i=0;i<global_retries;i++) {
	send_data(server_ip,session);
	if ((errorcode=receive_data(session))==0)
	    break;
	printf("* ");
	fflush(stdout);
    }
    close(session->socket);

    //
    // Timeouts and other weird stuff. Make sure we remove the busy-flag.
    //
    if (errorcode!=0) {
	remove_busy(server_ip);
	return 1;
    }

    //
    // We have an answerRR from this server, print a message.
    // Also cache it for later.
    //
    if (session->recv_header->nanswerRR!=0) {
	struct dnsrr *answer;

	if (session->recv_header->flags.bit.aa)
	    printf("Got authoritative answer ");
	else
	    printf("Got answer ");

	answer=session->answer;
	while (answer!=NULL) {
	    add_arecord(session,answer,server_name,server_ip);
	    answer=answer->next;
	}
	if (global_caching) add_answer(server_ip);
    }

    //
    // If the domainname in the authority section is the same as
    // the one from this server, mark it as lame.
    //
    if (session->authority!=NULL && server_authfor!=NULL) {
	if (session->recv_header->flags.bit.aa==0 &&
	    strcasecmp(server_authfor,
		       session->authority->domainname_string)==0) {
	    printf("Lame server ");
	    remove_busy(server_ip);
	    return 0;
	}
    }


    //
    // If the current server has an authoritative answer, don't go
    // further.
    //
    if (session->recv_header->flags.bit.aa) {
	remove_busy(server_ip);
	return 0;
    }

    //
    // When no answers were received, go through the list of authorities
    // and ask them for it. Maybe the IP address of the authority was
    // in the additional RRs, maybe there are two IP address in
    // the list of additional RRs, maybe there are none and a
    // gethostbyname() has to be done.
    //
    retval=0;
    rrauth=session->authority;
    while (rrauth!=NULL) {
	int	found=0;
	char	nextserver_ip[NS_MAXDNAME];
	char	nextserver_name[NS_MAXDNAME];

	//
	// Only serve NS records
	//
	if (rrauth->type!=ns_t_ns) {
	    rrauth=rrauth->next;
	    continue;
	}

	//
	// If the domainname in the authority section is not a postfix
	// of what we have, don't go there. This might happen if we are
	// looking through cnames from different domains.
	//
	if (strcasecmp(rrauth->domainname_string,
		host+strlen(host)-strlen(rrauth->domainname_string))!=0) {
	    rrauth=rrauth->next;
	    continue;
	}

	//
	// Count the number of IP addresses in the additionalRR
	// for this authorityRR
	//
	rradd=session->additional;
	while (rradd!=NULL) {
	   if (strcmp(printablename(rradd->domainname,1),
						    rrauth->data_string)==0)
		found++;
	    rradd=rradd->next;
	}

	rradd=session->additional;
	do {
	    //
	    // Find the first IP address
	    //
	    while (rradd!=NULL) {
		if (strcmp(printablename(rradd->domainname,1),
			   rrauth->data_string)==0)
		    break;
		rradd=rradd->next;
	    }

	    //
	    // Prepare the graphs in front of the servers name
	    //
	    sprintf(s,"%s%c%s",
		prefix,last==1?' ':'|',depth==0?"":"     ");

	    //
	    // Recurse into this server...
	    //
	    if (rradd!=NULL) {
		// This is easy, we got the IP address in the additional
		// section. Don't worry about additional records with the
		// same name, they're done automaticly after this one.

		printf("\n");

		strcpy(nextserver_name,printablename(rradd->domainname,1));
		strcpy(nextserver_ip,rradd->data_string);
		retval+=create_session(host,
			    nextserver_ip,nextserver_name,rrauth->domainname_string,
			    depth+1,s,(rrauth->next==NULL && found<=1)?1:0);
	    } else {
		struct hostent *h;

		strcpy(nextserver_name,rrauth->data_string);

		if ((h=gethostbyname(nextserver_name))==NULL) {
		    //
		    // No IP address was found for this hostname.
		    // Just call the function and let them print
		    // an error.
		    //
		    printf("\n");
		    nextserver_ip[0]=0;
		    retval+=create_session(host,
			nextserver_ip,nextserver_name,rrauth->domainname_string,
			depth+1,s,(rrauth->next==NULL && found<=1)?1:0);
		} else {
		    int count,i;
		    char **addr_list;

		    //
		    // One or more IP address were found. Go through all
		    // of them (make sure they're saved before calling
		    // gethostbyname() again).
		    //
		    count=0;
		    while (h->h_addr_list[count]!=NULL) count++;

		    addr_list=(char **)calloc(count,sizeof(char *));
		    for (i=0;i<count;i++) {
			addr_list[i]=(char *)calloc(1,h->h_length);
			memcpy(addr_list[i],h->h_addr_list[i],h->h_length);
		    }

		    for (i=0;i<count;i++) {
			printf("\n");
			sprintf(nextserver_ip,"%hu.%hu.%hu.%hu",
			    (unsigned char)addr_list[i][0],
			    (unsigned char)addr_list[i][1],
			    (unsigned char)addr_list[i][2],
			    (unsigned char)addr_list[i][3]);

			retval+=create_session(host,
			    nextserver_ip,nextserver_name,rrauth->domainname_string,
			    depth+1,s,(rrauth->next==NULL && found<=1)?1:0);
		    }
		}
	    }

	    //
	    // If there are no more IP addresses, then do the next
	    // authorityRR.
	    //
	    if (--found<=0)
		break;
	    if (rradd!=NULL)
		rradd=rradd->next;
	} while (rradd!=NULL);
	rrauth=rrauth->next;
    }

    //
    // Cache it for later if there were no servers which went wrong.
    // Also remove the busy flag.
    //
    if (global_caching && retval==0) add_answer(server_ip);
    remove_busy(server_ip);

    return retval;
}

/*****************************************************************************/

//
// Startup, usage and win32-initialization
// Win32-initialization by Mike Black <mblack@csihq.com>
//

void usage(void) {
    fprintf(stderr,
	"DNSTRACER version 1.4 - (c) Edwin Groothuis - http://www.mavetju.org\n"
	"Usage: dnstracer [options] [host]\n"
	"\t-c: disable local caching, default enabled\n"
	"\t-o: enable overview of received answers, default disabled\n"
	"\t-q <querytype>: query-type to use for the DNS requests, default A\n"
	"\t-r <retries>: amount of retries for DNS requests, default 3\n"
	"\t-s <server>: use this server for the initial request, default localhost\n"
	"\t             If . is specified, A.ROOT-SERVERS.NET will be used.\n"
	"\t-t <timeout>: timeout for DNS requests, default 15 seconds\n"
	"\t-v: verbose\n"
    );
    exit(1);
}

#ifdef WIN32
int wsockinit(void) {
    WSADATA wsaData;		/* Structure for WinSock setup communication */

    if (WSAStartup(MAKEWORD(2, 0), &wsaData) != 0) { /* Load Winsock 2.0 DLL */
	fprintf(stderr, "WSAStartup() failed");
	exit(1);
    }
    return 1;
}
#endif


int main(int argc,char **argv) {
    int		ch;
    char *	server_name="127.0.0.1";
    char *	server_ip="127.0.0.1";
    char	ipaddress[NS_MAXDNAME];
    int		server_root=0;

#ifndef WIN32
    //
    // Get the first nameserver from /etc/resolv.conf
    //
    // This piece of code was donated by Moritz Barsnick. 
    //
    if (!(_res.options & RES_INIT))
	res_init();

    if (_res.nscount>0) {
	server_ip=strdup(inet_ntoa(_res.nsaddr_list[0].sin_addr));
	server_name=strdup(server_ip);
    }
#endif

#ifdef WIN32
    wsockinit();
#endif

    while ((ch=getopt(argc,argv,"coq:r:s:t:v"))!=-1) {
	switch (ch) {
	case 'c':
	    global_caching=0;
	    break;

	case 'o':
	    global_overview=1;
	    break;

	case 'q':
	    if ((global_querytype=atoi(optarg))<1) {
		#define compare(s,v) \
			if (strcmp(s,optarg)==0) global_querytype=v

		compare("a",	ns_t_a		);
		compare("aaaa",	ns_t_aaaa	);
		compare("a6",	ns_t_aaaa	);
		compare("cname",ns_t_cname	);
		compare("hinfo",ns_t_hinfo	);
		compare("mx",	ns_t_mx		);
		compare("ns",	ns_t_ns		);
		compare("txt",	ns_t_txt	);

		if (global_querytype<1) {
		    fprintf(stderr,
			"Strange querytype, setting to default\n");
		    global_querytype=DEFAULT_QUERYTYPE;
		}
	    }
	    break;

	case 'r':
	    if ((global_retries=atoi(optarg))<1) {
		fprintf(stderr,
		    "Strange amount of retries, setting to default\n");
		global_retries=DEFAULT_RETRIES;
	    }
	    break;

	case 's':
	    server_name=optarg;
	    if (strcmp(server_name,".")==0) {
		server_name=strdup("A.ROOT-SERVERS.NET");
		server_root=1;
	    }
	    break;

	case 't':
	    if ((global_timeout=atoi(optarg))<1) {
		fprintf(stderr,
		    "Strange timeout, setting to default\n");
		global_timeout=DEFAULT_TIMEOUT;
	    }
	    break;

	case 'v':
	    verbose=1;
	    break;

	default:
	    usage();
	}
    }
    argc-=optind;
    argv+=optind;

    if (argv[0]==NULL) usage();

    printf("Tracing to %s via %s, timeout %d seconds\n",
	argv[0],server_name,global_timeout);

    srandom(time(NULL));

    {
	struct hostent *h;
	if ((h=gethostbyname(server_name))==NULL) {
	    fprintf(stderr,"Cannot find IP address for %s\n",server_name);
	    return 1;
	}
	sprintf(ipaddress,"%hu.%hu.%hu.%hu",
	    (unsigned char)h->h_addr_list[0][0],
	    (unsigned char)h->h_addr_list[0][1],
	    (unsigned char)h->h_addr_list[0][2],
	    (unsigned char)h->h_addr_list[0][3]);
    }

    create_session(argv[0],ipaddress,server_name,server_root==0?NULL:".",0,"",1);

    printf("\n");

    if (global_overview!=0) {
	printf("\n");
	display_arecords();
    }

    return 0;
}