#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>
#include <errno.h>
#include <fcntl.h>
#include <signal.h>
#include <stdlib.h>


/*	Auteur: Benoit Papillault
	Creation: Vendredi 14 Novembre 1997

	But: meme fonctionalite que traceroute, mais avec des paquets TCP
	qui franchissent les firewalls. A noter que cet outil permet de
	savoir que certains routeurs de routent pas tout les types de paquets.

	Sites interressants:
		www.ftp.com		port 21
		www.microsoft.com	port 80
		134.24.252.3		port 79
		www.alcatel.ch		port 21/23
		www.alcatel.dk		port 80
		pc-krace.rennes.enst-bretagne.fr	port 1039

	Le site le plus loing:
		math.holycross.edu	ttl 27
		rm17al.virginia.smu.edu ttl 28
		www.cygnus.com		ttl 29

	Ne marche pas:
		www.bsf.alcatel.fr	tester port 80 impossible a maisel
		laposte.bsf.alcatel.fr	port 25, il manque le prec. gateway

	Ne marche pas avec traceroute:
		altavista.telia.com, bouclage sur le router d'avant
		www.sid-dis.com, s'arrete au router d'avant
		www.alcatel.de, blocage en 149.204.44.241
		www.ftp.com,	blocage en router-4a.ftp.com
		134.24.252.3,	se trompe de machine
		laposte.bsf.alcatel.fr

	Ne marche pas avec tracer2:
		entcweb.tamu.edu	Manque la fin de la route.

	Historique:
	18/11/1997: copie de tracer.c en tracer2.c afin d'experimenter
		une technique parallele qui consiste a envoyer des paquets
		au hasard avec tout les ttl possibles et a regarder en
		parallele ce qui revient.

	A faire: envoyer de vrai paquet TCP et non pas utiliser le connect
		pour le faire.

	19/11/1997: select provoque parfois l'erreur Bad file
		number. Ceci est du au fait que on differencie les
		paquets ICMP par le port tcp source, or il se peut que
		deux sockets est le meme port tcp si on les cree/detruits
		successivement. Pour eviter ce probleme, on ne detruit
		pas les sockets que l'on cree (pb du nombre de
		descripteurs limites dans ce cas).

	18/12/1997: ajout du protocole udp, comme dans la version originale
	de traceroute. Le principe reste le meme. Cependant, comme le routeur
	de l'ecole ne laisse pas passer les paquets udp de l'exterieur, il
	est preferable de choisir un port udp inexistant car dans ce cas,
	lorsque le paquet atteindra sa destination, un message ICMP Port
	Unreachable sera emis (et on pourra le recevoir)

	26/01/1998: ajout des options -notcp et -noudp.
*/

#define	DEFAULT_PORT_TCP	23
#define	DEFAULT_PORT_UDP	1234
#define MAX_TTL 30
#define	MAX_PORT 65000

/* a adapter a la machine, pour avoir des types de 1,2 et 4 octets
	respectivement */

typedef unsigned char byte;
typedef unsigned short word;
typedef unsigned long dword;

/* la premiere entete des paquets */

struct ip
{
	byte	ip_hl_v;
	byte	ip_tos;
	word	ip_len;
	word	ip_id;
	word	ip_off;
	byte	ip_ttl;
	byte	ip_p;
	word	ip_cksum;
	struct in_addr ip_src;
	struct in_addr ip_dst;
};

/* la seconde entete si ip_p == IPPROTO_ICMP (et troisieme entete)*/

struct icmp
{
	byte	icmp_type;
	byte	icmp_code;
	word	icmp_cksum;
	struct in_addr icmp_gw;
	struct ip icmp_ip;
};

/* pour le champ icmp_type */

#define	ICMP_ECHO_REPLY		0
#define	ICMP_UNREACH		3
#define	ICMP_TIME_EXCEEDED	11

/* dans le cas ou icmp_type==ICMP_UNREACH */

#define	ICMP_UNREACH_PORT	3

/* la quatrieme entete */

struct tcp
{
	word	tcp_srcport;
	word	tcp_dstport;
	dword	tcp_seq;
	dword	tcp_ack;
	byte	tcp_off;
	byte	tcp_flags;
	word	tcp_win;
	word	tcp_cksum;
	word	tcp_urp;
};

struct udp
{
	word	udp_srcport;
	word	udp_dstport;
	word	udp_len;
	word	udp_cksum;
};

/* pour stocker les infos recu pour chaque ttl */

struct info_ttl
{
	int	ttl;
	struct in_addr gateway;
	struct timeval debut;	/* heure d'envoi du paquet, au moment du
					connect */
	struct timeval fin; 	/* heure de reception du paquet */
	int	recu;		/* si un paquet est recu */
	int	affiche;	/* si la ligne est affichee */
	int	connecte;	/* indique si la connexion a reussie */
	int	drop;		/* le nombre de paquets perdus */
	int	s_tcp;		/* la socket associee a chaque ttl */
	int	port_tcp;	/* le port de la socket source */
	int	s_udp;
	int	port_udp;
};

struct requete
{
	int	ttl;
	struct in_addr dst;
	int	port_tcp;
	int	port_udp;
	int	socket_icmp;
};

/* les variables globales */

int option_afficher_ip = 0;
int option_debug = 0;
int	option_tcp = 1;
int	option_udp = 1;
int nqueries = 3;
int max_ttl = MAX_TTL;

int next_port_tcp = 0;
int next_port_udp = 0;

struct info_ttl info[MAX_TTL];

void init()
{
	int i;

	for (i=0;i<MAX_TTL;i++)
	{
		info[i].ttl = i+1;
		info[i].recu = 0;
		info[i].affiche = 0;
		info[i].drop = 0;
		info[i].connecte = 0;
	}
}

void print_host(struct in_addr *in)
{
	struct hostent *hp = NULL;

	if (!option_afficher_ip)
		hp = gethostbyaddr((char *)in,sizeof(in),AF_INET);

	if (hp != NULL)
		printf("%-15s (%s)",inet_ntoa(*in),hp->h_name);
	else
		printf("%-15s",inet_ntoa(*in));
}

/* calcule la difference entre deux moments */

double diff_time(struct timeval *debut,struct timeval *fin)
{
	double duree;

	duree = (fin->tv_sec - debut->tv_sec) * 1000.0
		+ (fin->tv_usec - debut->tv_usec) / 1000.0;

	return duree;

	printf("%8.3f ms",duree);
}

void print_line(struct info_ttl *p)
{
	printf("%2d ",p->ttl);
	if (p->drop < nqueries)
	{
		printf("%8.3f ms ",diff_time(&p->debut,&p->fin));
		print_host(&p->gateway);
		if (p->drop != 0)
			printf(" (%d lost)",p->drop);
	}
	else
		printf("???");
	printf("\n");

	p->affiche = 1;
}

void usage()
{
	printf("usage: tracert [-d] [-n] [-q nqueries] host [-tcp port_tcp]"
		" [-udp port_udp] [-notcp] [-noudp]\n");
	printf("trace la liste des routeurs pour atteindre une machine\n");
	printf("Auteur: Benoit.Papillault@enst-bretagne.fr, Novembre 1997\n");
	exit (-1);
}

void print_type(int type)
{
	switch (type)
	{
	case ICMP_TIME_EXCEEDED:
		printf("ICMP_TIME_EXCEEDED");
		break;
	case ICMP_ECHO_REPLY:
		printf("ICMP_ECHO_REPLY");
		break;
	case ICMP_UNREACH:
		printf("ICMP_UNREACH");
		break;
	default:
		printf("ICMP type %d",type);
		break;
	}
}

void afficher_ip(struct ip *ip)
{
	struct tcp *tcp = (struct tcp *)(ip+1);
	/* struct udp *udp = (struct udp *)(ip+1); */

	printf(" from ");
	print_host(&ip->ip_src);
	printf(" port %u to ",ntohs(tcp->tcp_srcport));
	print_host(&ip->ip_dst);
	printf(" ");
	switch (ip->ip_p)
	{
	case IPPROTO_TCP: printf("tcp"); break;
	case IPPROTO_UDP: printf("udp"); break;
	case IPPROTO_ICMP: printf("icmp"); break;
	default: printf("prot %d",ip->ip_p); break;
	}
	printf(" port %u ttl %d",ntohs(tcp->tcp_dstport),
			ip->ip_ttl);
}

void afficher_paquet(byte *p)
{
	struct ip *ip = (struct ip *)p;
	struct icmp *icmp = (struct icmp *)(ip+1);
	/* struct tcp *tcp = (struct tcp *)(icmp+1);
	struct udp *udp = (struct udp *)(icmp+1); */

/*	if (ip->ip_p != IPPROTO_ICMP)
		return;
*/
	print_type(icmp->icmp_type);
	switch (icmp->icmp_type)
	{
	case ICMP_TIME_EXCEEDED:
		afficher_ip(&icmp->icmp_ip);
		printf(" by ");
		print_host(&ip->ip_src);
		printf("\n");
		break;
	case ICMP_UNREACH:
		switch (icmp->icmp_code)
		{
		case 0: printf("(net)"); break;
		case 1: printf("(host)"); break;
		case 2: printf("(protocol)"); break;
		case 3: printf("(port)"); break;
		case 4: printf("(fragmentation)"); break;
		case 5: printf("(source route)"); break;
		default: printf("(code %d)",icmp->icmp_code); break;
		}
		afficher_ip(&icmp->icmp_ip);
		printf(" by ");
		print_host(&ip->ip_src);
		printf("\n");
		break;
	case ICMP_ECHO_REPLY:
		printf("\n");
		break;
	default:
		printf("\n");
		break;
	}
}

/* retourne 1 si le paquet nous concerne */

int analyser_paquet(struct requete *request,byte *pckt)
{
	struct ip *pckt_ip = (struct ip *)pckt;
	struct icmp *pckt_icmp = (struct icmp  *)(pckt_ip+1);
	struct tcp *pckt_tcp = (struct tcp *)(pckt_icmp+1);
	struct udp *pckt_udp = (struct udp *)(pckt_icmp+1);
	int i;
	struct timeval tps;

	if (gettimeofday(&tps,NULL) < 0)
		perror("gettimeofday");

	if (option_debug)
		afficher_paquet(pckt);

	if (pckt_ip->ip_p != IPPROTO_ICMP)
	{
		printf("Attention: packet non ICMP\n");
		return 0;
	}


	/* on ne s'interresse qu'au paquet ICMP_UNREACH et
		ICMP_TIME_EXCEEDED */

	if (pckt_icmp->icmp_type != ICMP_UNREACH &&
		pckt_icmp->icmp_type != ICMP_TIME_EXCEEDED)
		return 0;

	if (pckt_icmp->icmp_type == ICMP_UNREACH &&
		pckt_icmp->icmp_code != ICMP_UNREACH_PORT)
		return 0;

	/* on elimine les paquets non TCP */

	if (pckt_icmp->icmp_ip.ip_p != IPPROTO_TCP &&
		pckt_icmp->icmp_ip.ip_p != IPPROTO_UDP)
		return 0;

	/* on cherche la socket corespondant au port */
	for (i=0;i<MAX_TTL;i++)
	{
		if ((option_tcp && pckt_tcp->tcp_srcport == info[i].port_tcp)
		    ||(option_udp && pckt_udp->udp_srcport==info[i].port_udp))
		{
			if (option_debug)
				printf("%2d ok\n",info[i].ttl);
		if (!info[i].recu)
		{
			info[i].gateway = pckt_ip->ip_src;
			info[i].fin = tps;
			info[i].recu = 1;
			if (option_tcp) close(info[i].s_tcp);
			if (option_udp) close(info[i].s_udp);

			/* dans le cas d'un message Port Unreachable, on
				considere que l'on a atteinds la destination */
			if (pckt_icmp->icmp_type == ICMP_UNREACH
				&& pckt_icmp->icmp_code == ICMP_UNREACH_PORT)
				info[i].connecte = 1;

			return 1;
		}
		}
	}

	return 0;
}

/* attends de recevoir un paquet du port TCP port (port_tcp en representation
	reseau). On attends tout les paquets jusqu'a avoir le bon, auquel
	cas on renvoie 1. L'agorithme ici pourrait etre ameliorer, car
	celui est trop perturbe en temps pas d'autres paquets "etrangers" */

int recevoir_paquet_icmp(struct requete *request)
{
	byte buffer[512];
	int fromlen;
	struct sockaddr_in from;

	/* on lit un paquet a la fois */

	fromlen = sizeof(from);
	if (recvfrom(request->socket_icmp,buffer,
		sizeof(buffer),0,(struct sockaddr *)&from,&fromlen) < 0)
	{
		perror("recvfrom");
		return 0;
	}
	else
		return analyser_paquet(request,buffer);
}

#define	DATA_SIZE	10

/* gateway est la machine destinatrice */

void dst_tcp_ok(struct info_ttl *p)
{
	char buffer[DATA_SIZE] = "Coucou\n";

	gettimeofday(&p->fin,NULL);

	if (option_debug)
		printf("%2d dst_tcp_ok\n",p->ttl);

	if (write(p->s_tcp,buffer,sizeof(buffer)) != sizeof(buffer))
	{
		if (option_debug)
			perror("write");
		return;
	}

	close(p->s_tcp);
	if (option_udp) close(p->s_udp);

	p->recu = 1;
	p->connecte = 1;
}

void dst_udp_ok(struct info_ttl *p)
{
	char buffer[DATA_SIZE] = "Coucou\n";

	gettimeofday(&p->fin,NULL);

	if (option_debug)
		printf("%2d dst_udp_ok\n",p->ttl);

	if (read(p->s_udp,buffer,sizeof(buffer)) != sizeof(buffer))
	{
		if (option_debug)
			perror("write");
		return;
	}

	if (option_tcp) close(p->s_tcp);
	close(p->s_udp);

	p->recu = 1;
	p->connecte = 1;
}

/* cree une socket du type demandee et renvoie 1 si tout est ok, 
	0 sinon */

int preparer_socket(struct requete *request,int type,struct info_ttl *p)
{
	struct sockaddr_in sin;
	int i,sinlen,next_port;
	int s;

	s = socket(AF_INET,type,0);
	if (s < 0)
	{
		perror("socket");
		return 0;
	}

	/* on cherche un port de libre */

	if (type == SOCK_DGRAM)
		next_port = next_port_udp;
	else
		next_port = next_port_tcp;

	for (i=next_port;i<MAX_PORT;i++)
	{
		sin.sin_family = AF_INET;
		sin.sin_addr.s_addr = htonl(INADDR_ANY);
		sin.sin_port = htons(i);
		memset(sin.sin_zero,0,8);

		if (bind(s,(struct sockaddr *)&sin,sizeof(sin))==0)
			break;
	}

	if (i==MAX_PORT)
	{
		perror("bind");
		close(s);
		return 0;
	}

	sinlen = sizeof(sin);
	if (getsockname(s,(struct sockaddr *)&sin,&sinlen) < 0)
	{
		perror("getsockname");
		close(s);
		return 0;
	}

	next_port = ntohs(sin.sin_port)+1;
	if (type == SOCK_DGRAM)
	{
		p->s_udp = s;
		p->port_udp = sin.sin_port;
		next_port_udp = next_port;
	}
	else
	{
		p->s_tcp = s;
		p->port_tcp = sin.sin_port;
		next_port_tcp = next_port;
	}

	if (setsockopt(s,IPPROTO_IP,IP_TTL,(char *)&p->ttl,
		sizeof(p->ttl)) < 0)
	{
		perror("setsockopt");
		close(s);
		return 0;
	}

	return 1;
}

int preparer_sockets(struct requete *request,struct info_ttl *p)
{
	if (option_tcp && !preparer_socket(request,SOCK_STREAM,p))
		return 0;
	if (option_udp && !preparer_socket(request,SOCK_DGRAM,p))
		return 0;
	return 1;
}

void connecter_socket(struct requete *request,struct info_ttl *p)
{
	struct sockaddr_in sin;
	char buffer[] = "coucou";

	sin.sin_family = AF_INET;
	sin.sin_addr = request->dst;
	sin.sin_port = htons(request->port_tcp);
	memset(sin.sin_zero,0,8);

	if (gettimeofday(&p->debut,NULL) < 0)
		perror("gettimeofday");

	/* on rends les sockets non bloquantes */

	if (option_tcp)
	if (fcntl(p->s_tcp,F_SETFL,fcntl(p->s_tcp,F_GETFL,0) | O_NONBLOCK) < 0)
		perror("fcntl");

/*	if (fcntl(p->s_udp,F_SETFL,fcntl(p->s_udp,F_GETFL,0) | O_NONBLOCK) < 0)
		perror("fcntl");
*/

	if (option_tcp)
	if (connect(p->s_tcp,(struct sockaddr *)&sin,sizeof(sin)) == 0)
	{
		p->gateway = request->dst;
		dst_tcp_ok(p);
	 }
	 else if (errno != EINPROGRESS)
		perror("connect");

	/* on rends la socket tcp a nouveau bloquante */

	if (option_tcp)
	if (fcntl(p->s_tcp,F_SETFL,fcntl(p->s_tcp,F_GETFL,0) & ~O_NONBLOCK) < 0)
		perror("fcntl");

	sin.sin_family = AF_INET;
	sin.sin_addr = request->dst;
	sin.sin_port = htons(request->port_udp);
	memset(sin.sin_zero,0,8);

	if (option_udp)
	if (sendto(p->s_udp,buffer,sizeof(buffer),0,
		(struct sockaddr *)&sin,sizeof(sin)) < 0)
		perror("sendto");
}

void fermer_socket(struct info_ttl *p)
{
	if (option_tcp) close(p->s_tcp);
	if (option_udp) close(p->s_udp);
}

/* renvoie 1 si l'algorithme est termine, 0 sinon.
	L'algorithme se termine lorsque: on a atteinds la destination et
	tout les routeurs qui precedent sont soient resolus, soit le
	nombre de paquet envoye est atteinds, soit aucune reponse n'est recue
*/

int fini()
{
	int i;

	for (i=0;i<MAX_TTL;i++)
	{
		if (info[i].connecte)
			return 1;
		if (!info[i].recu)
			return 0;
	}

	return 1;
}

void doit(struct requete *request)
{
	int i, result;
	fd_set fd_read, fd_write;
	struct timeval tps;

	init();

	/* on commence par creer toutes les sockets dont on a besoin */

	for (i=0;i<MAX_TTL;i++)
		preparer_sockets(request,&info[i]);

	/* on envoie tout les paquets en meme temps */

	for (i=MAX_TTL-1;i>=0;i--)
		connecter_socket(request,&info[i]);

	/* on attends que ca revienne, on que les connexions se fassent */

	do
	{

		FD_ZERO(&fd_read);
		FD_SET(request->socket_icmp,&fd_read);
		FD_ZERO(&fd_write);
		for (i=0;i<MAX_TTL;i++)
			if (!info[i].recu)
			{
				if(option_tcp) FD_SET(info[i].s_tcp, &fd_write);
				if(option_udp) FD_SET(info[i].s_udp, &fd_read);
			}

		tps.tv_sec = 1;
		tps.tv_usec = 0;

		result = select(FD_SETSIZE,&fd_read,&fd_write,NULL,&tps);
		if (result > 0)
		{
			if (FD_ISSET(request->socket_icmp,&fd_read))
				if (recevoir_paquet_icmp(request))
					continue;

			/* si le paquet nous concernait, on essaye le
				plus vite possible de lire le suivant */

			for (i=0;i<MAX_TTL;i++)
				if (!info[i].recu)
				{
					if (option_tcp &&
					   FD_ISSET(info[i].s_tcp,&fd_write))
					{
						info[i].gateway = request->dst;
						dst_tcp_ok(&info[i]);
					}
					if (option_udp &&
					    FD_ISSET(info[i].s_udp,&fd_read))
					{
						info[i].gateway = request->dst;
						dst_udp_ok(&info[i]);
					}
				}
		}
		if (result < 0)
		{
			fflush(stdout);
			perror("select1");
		}

		/* on gere les time-out au cas par cas */

		if (gettimeofday(&tps,NULL) < 0)
			perror("gettimeofday");

		for (i=0;i<MAX_TTL;i++)
			if (!info[i].recu &&
				diff_time(&info[i].debut,&tps) > 2000.0)
			{
				info[i].drop ++;
				if (info[i].drop >= nqueries)
					info[i].recu = 1;
				else
				{
					if (option_debug)
						printf("reemission ttl %d",i+1);
					fermer_socket(&info[i]);
					preparer_sockets(request,&info[i]);
					connecter_socket(request,&info[i]);
				}
			}
	}
	while (!fini());

	/* on affiche tout */
	for (i=0;i<MAX_TTL;i++)
	{
		if (info[i].recu)
			print_line(&info[i]);
		if (info[i].connecte)
			break;
	}
}

/* dans la fonction, on ne s'occupe que du decodage des arguments
	de la ligne de commande */

int main(int argc,char *argv[])
{
	char *host = NULL, *le_port_tcp = NULL, *le_nqueries = NULL;
	char *le_port_udp = NULL;
	struct hostent *hp;
	struct requete request;
	int i;
	struct protoent *prot;
	int proto_number;

	request.port_tcp = DEFAULT_PORT_TCP;
	request.port_udp = DEFAULT_PORT_UDP;

	signal(SIGPIPE,SIG_IGN);

	/*
	printf("size ip=%d\n",sizeof(struct ip));
	printf("size icmp=%d\n",sizeof(struct icmp));
	printf("size tcp=%d\n",sizeof(struct tcp));
	printf("size udp=%d\n",sizeof(struct udp));
	*/

	for (i=1;i<argc;i++)
	{
		if (strcmp(argv[i],"-n")==0)
		{
			option_afficher_ip = 1;
		}
		else if (strcmp(argv[i],"-d")==0)
		{
			option_debug = 1;
		}
		else if (strcmp(argv[i],"-q")==0 && i+1<argc)
		{
			if (le_nqueries != NULL)
				usage();
			le_nqueries = argv[i+1];
			i++;
		}
		else if (strcmp(argv[i],"-tcp")==0 && i+1<argc
			&& le_port_tcp==NULL)
		{
			le_port_tcp = argv[i+1];
			i++;
		}
		else if (strcmp(argv[i],"-udp")==0 && i+1<argc
			&& le_port_udp==NULL)
		{
			le_port_udp = argv[i+1];
			i++;
		}
		else if (strcmp(argv[i],"-noudp")==0)
			option_udp = 0;
		else if (strcmp(argv[i],"-notcp")==0)
			option_tcp = 0;
		else if (host == NULL)
		{
			host = argv[i];
		}
		else usage();
	}

	if (host == NULL)
		usage();

	if (!option_tcp && !option_udp)
		usage();

	if (le_port_tcp != NULL)
	{
		request.port_tcp = atoi(le_port_tcp);
		if (request.port_tcp == 0)
			usage();
	}

	if (le_port_udp != NULL)
	{
		request.port_udp = atoi(le_port_udp);
		if (request.port_udp == 0)
			usage();
	}

	if (le_nqueries != NULL)
	{
		nqueries = atoi(le_nqueries);
		if (nqueries == 0)
			usage();
	}

	hp = gethostbyname(host);
	if (hp == NULL)
	{
		printf("%s est inconnue\n",host);
		return -1;
	}

	memcpy(&request.dst,hp->h_addr,sizeof(request.dst));
	printf("traceroute to %s (%s) using tcp port %u and udp port %u\n",
		hp->h_name,inet_ntoa(request.dst),request.port_tcp,
		request.port_udp);

	prot = getprotobyname("icmp");
	if (prot == NULL)
	{
		printf("Warning: can't get icmp proto number, usign default\n");
		proto_number = IPPROTO_ICMP;
	}
	else
		proto_number = prot->p_proto;

	request.socket_icmp = socket(AF_INET,SOCK_RAW,proto_number);
	if (request.socket_icmp < 0)
	{
		perror("socket_icmp");
		return -1;
	}

	doit(&request);

	close(request.socket_icmp);

	return 0;
}