path: root/libglouglou/libggnet_traceroute.c

/*
 * Traceroute library using libevent, libdnet and libpcap
 *
 * 2012 Laurent Ghigonis <laurent@gouloum.fr>
 *
 * Inspired from jtrace
 *   http://monkey.org/~jose/software/jtrace/
 *   Copyright (c) 2003-2004 Jose Nazario <jose@monkey.org>
 *   All rights reserved.
 * Inspired from OpenBSD's traceroute
 *   http://www.openbsd.org/cgi-bin/cvsweb/src/usr.sbin/traceroute/traceroute.c?rev=HEAD
 *   Copyright (c) 1990, 1993
 *   The Regents of the University of California.  All rights reserved.
 *   This code is derived from software contributed to Berkeley by
 *   Van Jacobson.
 * Inspired from netsniff-ng's astraceroute
 *   http://www.netsniff-ng.org/
 *   https://github.com/gnumaniacs/netsniff-ng/blob/master/src/astraceroute.c
 *   By Daniel Borkmann <daniel@netsniff-ng.org>
 *   Copyright 2011 Daniel Borkmann.
 */

/*
 * Traceroute algorithm
 *
 * Send algo (_cb_send) :
 *
 * send 3 * 15 packets to next 15 ttls
 * add packets in hops_list
 * set recv timeout in 3s
 *
 * Recv algo (_cb_recv) :
 *
 * check if dst IP is for us
 * check if src IP is for us in hop_list
 * tcp / udp
 *   is it answer from the target ?
 XXX we might still want to continue a few hops after target
 *     target info write in hop_list
 *     recv timeout in 0.5s
 * icmp unreach / exceed :
 *   did we send the inner pkt ?
 *     hop info write in hop_list
 *     which ttl ?
 *     is it answer from the target ?
 *       recv timeout in 0.5s
 * did we receive all answers ?
 *   send more !
 */

/* TODO
 * * hop store 3 answer results
 * * send more packets of 15th answer
 * * LATER hability to intrace all captured TCP session
 *   check for no incidence on the TCP connection
 *   can do on UDP ?
 */

#include <sys/param.h>
#include <sys/time.h>
#include <sys/types.h>

#include <netinet/in.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#include "libggnet_traceroute.h"

#define TRACE_DPORT 80
#define TIMEOUT_TOTAL_S 3
#define TIMEOUT_AFTERTARGET_US 500000

static void _req_free(struct ggnet_traceroute_req *);
static void _cb_send(evutil_socket_t, short, void *);
static void _cb_recv(evutil_socket_t, short, void *);
static void _cb_trace_timeout(evutil_socket_t, short, void *);
static void _timeout_set(struct ggnet_traceroute_req *, int, int);
static struct ggnet_traceroute_hop *
	_hop_ip_id(struct ggnet_traceroute_req *, int);
static struct ggnet_traceroute_hop *
	_hop_sport(struct ggnet_traceroute_req *, int);
static void _trace_done(struct ggnet_traceroute_req *);
static int pcap_dloff(pcap_t *); // XXX move to libggnet_utils ?
double timeval_diff(struct timeval *, struct timeval *);

struct trace_pkt {
	union {
		struct ip_hdr ip;
	} pkt_hdr_i;
	union {
		struct tcp_hdr tcp;
		struct icmp_hdr icmp;
	} pkt_hdr_t;
};

struct ggnet_traceroute *
ggnet_traceroute_new(struct event_base *ev_base, char *iface, int verbose)
{
	struct ggnet_traceroute *ggtr;
	char ebuff[PCAP_ERRBUF_SIZE];

	ggtr = calloc(1, sizeof(struct ggnet_traceroute));
	if (!ggtr) {
		printf("could not allocate ggnet_traceroute\n");
		exit(1);
	}
	ggtr->ev_base = ev_base;
	ggtr->pkt_ip = ip_open();
	if (!ggtr->pkt_ip) {
		printf("ip_open() failed\n");
		ggnet_traceroute_free(ggtr);
		return NULL;
	}
	ggtr->pkt_rand = rand_open();
	ggtr->intf = intf_open();
	if (!ggtr->intf) {
		printf("intf_open() failed\n");
		ggnet_traceroute_free(ggtr);
		return NULL;
	}

	ggtr->pcap = pcap_open_live(iface, 1500, 1, 500, ebuff);
	if (ggtr->pcap == NULL)
		err(1, "pcap_open_live(%s)", iface);
	ggtr->pcap_dllen = pcap_dloff(ggtr->pcap);
	ggtr->pcap_fd = pcap_fileno(ggtr->pcap);
	ggtr->verbose = verbose;

	return ggtr;
}

void
ggnet_traceroute_free(struct ggnet_traceroute *ggtr)
{
	struct ggnet_traceroute_req *req;

	if (ggtr->pcap)
		pcap_close(ggtr->pcap);
	if (ggtr->pkt_ip)
		ip_close(ggtr->pkt_ip);
	if (ggtr->pkt_rand)
		rand_close(ggtr->pkt_rand);
	LIST_FOREACH(req, &ggtr->req_list, entry)
		_req_free(req);
	free(ggtr);
}

struct ggnet_traceroute_req *
ggnet_traceroute_trace_tcp(struct ggnet_traceroute *ggtr,
		struct addr *ip, int dport,
		void (*cb_done)(struct ggnet_traceroute_req *, void *),
		void (*cb_hop)(struct ggnet_traceroute_req *,
			struct ggnet_traceroute_hop *, void *),
		void *data)
{
	struct ggnet_traceroute_req_params *params;

	params = calloc(1, sizeof(struct ggnet_traceroute_req_params));
	if (!params)
		err(1, "could not allocate ggnet_traceroute_req_params\n");
	params->mode = TRACEMODE_TCP;
	params->tcp.dport = dport;

	return ggnet_traceroute_trace(ggtr, ip, params, cb_done, cb_hop, data);
}

struct ggnet_traceroute_req *
ggnet_traceroute_trace_tcp_intrace(struct ggnet_traceroute *ggtr,
		struct addr *ip, int sport, int dport, int ip_id,
		void (*cb_done)(struct ggnet_traceroute_req *, void *),
		void (*cb_hop)(struct ggnet_traceroute_req *,
			struct ggnet_traceroute_hop *, void *),
		void *data)
{
	struct ggnet_traceroute_req_params *params;

	params = calloc(1, sizeof(struct ggnet_traceroute_req_params));
	if (!params)
		err(1, "could not allocate ggnet_traceroute_req_params\n");
	params->mode = TRACEMODE_TCP_INTRACE;
	params->ip.id = ip_id;
	params->tcp.dport = dport;
	params->tcp.sport = sport;

	return ggnet_traceroute_trace(ggtr, ip, params, cb_done, cb_hop, data);
}

struct ggnet_traceroute_req *
ggnet_traceroute_trace(struct ggnet_traceroute *ggtr, struct addr *ip,
		struct ggnet_traceroute_req_params *params,
		void (*cb_done)(struct ggnet_traceroute_req *, void *),
		void (*cb_hop)(struct ggnet_traceroute_req *,
			struct ggnet_traceroute_hop *, void *),
		void *data)
{
	struct ggnet_traceroute_req *req;
	struct intf_entry *intfentry;
	char buf[1024];

	req = calloc(1, sizeof(struct ggnet_traceroute_req));
	if (!req) {
		printf("could not allocate ggnet_traceroute_req\n");
		exit(1);
	}
	req->target = calloc(1, sizeof(struct ggnet_traceroute_hop));
	if (!req->target) {
		printf("cannot allocate ggnet_traceroute_hop\n");
		exit(1);
	}

	intfentry = (struct intf_entry *)buf;
	memset(intfentry, 0, sizeof(struct intf_entry));
	intfentry->intf_len = sizeof(buf);
	memcpy(&req->target->ip, ip, sizeof(struct addr));
	if (intf_get_dst(ggtr->intf, intfentry, &req->target->ip) < 0) {
		printf("error getting source IP for dest IP %s (%p)\n",
				addr_ntoa(&req->target->ip), ggtr->intf);
		goto err;
	}
	printf("XXX intfentry->intf_addr %s\n", addr_ntoa(&intfentry->intf_addr));
	memcpy(&req->srcip, &intfentry->intf_addr, sizeof(struct addr));
	req->params = params;
	TAILQ_INIT(&req->hops_list);

	printf("XXX tracing to %s\n", addr_ntoa(&req->target->ip));

	req->run.ev_recv = event_new(ggtr->ev_base,
			ggtr->pcap_fd, EV_READ, _cb_recv, req);
	event_add(req->run.ev_recv, NULL);
	req->run.ev_send = event_new(ggtr->ev_base,
			ggtr->pcap_fd, EV_WRITE, _cb_send, req);
	event_add(req->run.ev_send, NULL);
	req->run.ev_timeout = evtimer_new(ggtr->ev_base,
			_cb_trace_timeout, req);
	event_add(req->run.ev_timeout, NULL);

	req->cb_done = cb_done;
	req->cb_hop = cb_hop;
	req->data = data;
	req->ggtr = ggtr;

	LIST_INSERT_HEAD(&ggtr->req_list, req, entry);
	ggtr->req_pending++;
	return req;

err:
	if (req)
		_req_free(req);
	return NULL;
}

void
ggnet_traceroute_trace_free(struct ggnet_traceroute_req *req)
{

	struct ggnet_traceroute_req *r;

	LIST_FOREACH(r, &req->ggtr->req_list, entry) {
		if (r == req) {
			LIST_REMOVE(req, entry);
			req->ggtr->req_pending--;
		}
	}
	_req_free(req);
}


char *
ggnet_traceroute_report(struct ggnet_traceroute_req *req) {
	struct ggnet_traceroute_hop *hop;
	static char report[16384];
	static char *p;
#define left (sizeof(report) - (p - report))

	p = report;
	if (req->target->ttl > 0)
		p += (u_char)snprintf(p, left, "target:\t\tanswering\n");
	else
		p += (u_char)snprintf(p, left, "target:\t\tnot answering\n");
	p += (u_char)snprintf(p, left, "hops total:\t%d\n", req->hopcount_total);
	p += (u_char)snprintf(p, left, "hops answering:\t%d\n", req->hopcount_answering);
	TAILQ_FOREACH(hop, &req->hops_list, entry) {
		p += (u_char)snprintf(p, left, "%.2d: %s %s %.2f [XXX %p]\n", hop->ttl, addr_ntoa(&hop->ip), hop->answer, hop->delay, hop);
	}

#undef left
	return report;
}

static void
_req_free(struct ggnet_traceroute_req *req)
{
	if (req->target)
		free(req->target);
	if (req->params)
		free(req->params);
	if (req->run.ev_recv)
		event_free(req->run.ev_recv);
	if (req->run.ev_send)
		event_free(req->run.ev_send);
	free(req);
}

static void
_cb_send(evutil_socket_t fd, short what, void *arg)
{
	struct ggnet_traceroute_req *req;
	struct ggnet_traceroute_hop *hop;
	struct ggnet_traceroute *ggtr;
	u_char buf[BUFSIZ];
	struct trace_pkt *pkt;
	int len, lensent, ttl, i;
	int ip_id = -1;
	int sport = -1;

	req = arg;
	ggtr = req->ggtr;
	if (ggtr->verbose)
		printf("XXX cbggnet_traceroute cb_send %s -> %s\n",
			addr_ntoa(&req->srcip), addr_ntoa(&req->target->ip));
	pkt = (struct trace_pkt *)buf;
	len = IP_HDR_LEN + TCP_HDR_LEN;

	for (ttl=req->run.last_ttl_sent; ttl<15; ttl++) {
		hop = calloc(1, sizeof(struct ggnet_traceroute_hop));
		if (!hop) {
			printf("cannot allocate ggnet_traceroute_hop\n");
			exit(1);
		}
		hop->ttl = ttl;
		//addr_pack(hop->ip, ADDR_TYPE_IP, IP_ADDR_BITS, ip, IP_ADDR_LEN);
		switch (req->params->mode) {
		case TRACEMODE_TCP:
		case TRACEMODE_TCP_INTRACE:
			if (req->params->mode == TRACEMODE_TCP) {
				ip_id = rand_uint16(ggtr->pkt_rand);
				sport = rand_uint16(ggtr->pkt_rand);
			} else {
				ip_id = req->params->ip.id;
				sport = req->params->tcp.sport;
			}
			ip_pack_hdr(&pkt->pkt_hdr_i.ip, IP_TOS_LOWDELAY, len,
				ip_id, 0, ttl, IP_PROTO_TCP, 
				req->srcip.addr_ip, req->target->ip.addr_ip);
			tcp_pack_hdr(&pkt->pkt_hdr_t.tcp,
				sport, req->params->tcp.dport, 
				rand_uint32(ggtr->pkt_rand), 0, 
				TH_SYN, rand_uint16(ggtr->pkt_rand), 0);
			break;
		case TRACEMODE_ICMP:
			ip_id = rand_uint16(ggtr->pkt_rand);
			ip_pack_hdr(&pkt->pkt_hdr_i.ip, IP_TOS_LOWDELAY, len,
				ip_id, 0, ttl, IP_PROTO_ICMP, 
				req->srcip.addr_ip, req->target->ip.addr_ip);
			icmp_pack_hdr(&pkt->pkt_hdr_t.icmp, ICMP_ECHO, 8);
			break;
		}
		ip_checksum(pkt, len);
		TAILQ_INSERT_TAIL(&req->hops_list, hop, entry);
		gettimeofday(&hop->sendtime, NULL);
		for (i=0; i<TRACEROUTE_NB_PROBES; i++) {
			hop->ip_ids[i] = ip_id;
			hop->sports[i] = sport;
			lensent = ip_send(ggtr->pkt_ip, pkt, len);
			if (len < 0)
				warn("_cb_send : ip_send error");
			if (lensent < len)
				warn("_cb_send : ip_send short send (%d < %d",
						lensent, len);
		}
	}
	req->run.last_ttl_sent = ttl;
	_timeout_set(req, TIMEOUT_TOTAL_S, 0);
}

static void
_cb_recv(evutil_socket_t fd, short what, void *arg)
{
	struct ggnet_traceroute_req *req;
	struct ggnet_traceroute_hop *hop = NULL;
	struct ggnet_traceroute *ggtr;
	struct pcap_pkthdr ph;
	u_char *pread;
	struct ip_hdr  *ip, *ip_in;
	struct tcp_hdr *tcp;
	struct icmp_hdr *icmp;
	struct addr ip_src;
	struct timeval recvtime;
	char  *p, *flags;

	req = arg;
	ggtr = req->ggtr;
	if (ggtr->verbose)
		printf("XXX cbggnet_traceroute cb_recv %s -> %s\n",
			addr_ntoa(&req->srcip), addr_ntoa(&req->target->ip));
	// XXX call cb_hop if hop successfuly detected
	// req->cb_hop(req, hop, req->data);

	if ((pread = (u_char *) pcap_next(ggtr->pcap, &ph)) == NULL) {
		printf("libggnet_traceroute _cb_recv: read error\n");
		goto reschedule_recv;
	}

	if (ggtr->verbose)
		printf("XXX packet received\n");
	/* decode the current packet : ttl, ip, ... */
	ip = (struct ip_hdr *) (pread + ggtr->pcap_dllen);
	if (ip->ip_v != 4)
		goto reschedule_recv;
	p = ip_ntoa(&ip->ip_src);
	if ((addr_aton(p, &ip_src)) == -1)
		goto reschedule_recv;
	if (ggtr->verbose)
		printf("XXX packet IP received from %s, ip_id %d\n",
			addr_ntoa(&ip_src), ntohs(ip->ip_id));

	switch(ip->ip_p) {

		case IP_PROTO_TCP:
			if (addr_cmp(&ip_src, &(req->target->ip)) != 0) 
				goto reschedule_recv;
			tcp = (struct tcp_hdr *)((u_char *)ip + IP_HDR_LEN);
			if (ggtr->verbose)
				printf("XXX TCP %d %d %d\n", ntohs(tcp->th_sport),
					req->params->tcp.dport, tcp->th_seq);
			if (((tcp->th_flags == TH_SYN + TH_ACK) || 
					(tcp->th_flags == TH_RST + TH_ACK)) &&
					(ntohs(tcp->th_sport) == req->params->tcp.dport))  {
				/* target answer */
				if (ggtr->verbose)
					printf("XXX found target !\n");
				hop = _hop_sport(req, ntohs(tcp->th_dport));
				if (!hop) {
					printf("libggnet_traceroute _cb_recv: WARNING: TCP answer with dport not matching sent sport (%d) not found !\n",
						ntohs(tcp->th_dport));
					goto reschedule_recv;
				}

				memcpy(&hop->ip, &ip_src, sizeof(struct addr));
				hop->answer_count++;
				flags = "SA";
				if (tcp->th_flags == TH_RST + TH_ACK)
					flags = "R";
				strncpy(hop->answer, flags, sizeof(hop->answer));
				_timeout_set(req, 0, TIMEOUT_AFTERTARGET_US);
			}
			break;

		case IP_PROTO_ICMP:
			if (ggtr->verbose)
				printf("XXX is ICMP\n");
			/* answer from a hop */
			icmp = (struct icmp_hdr *)((u_char *)ip + IP_HDR_LEN);
			/* XXX ? look for TTL_EXPIRED, PROHIBITED msgs */
			ip_in = (struct ip_hdr *)
				((u_char *)ip + IP_HDR_LEN + ICMP_LEN_MIN);
			hop = _hop_ip_id(req, ntohs(ip_in->ip_id));
			if (!hop) {
				printf("libggnet_traceroute _cb_recv: WARNING: ICMP answer with IP ID not matching sent IP ID (%x) not found !\n",
						ntohs(ip_in->ip_id));
				goto reschedule_recv;
			}
			memcpy(&hop->ip, &ip_src, sizeof(struct addr));
			hop->answer_count++;
			if (icmp->icmp_type == ICMP_UNREACH) {
				switch (icmp->icmp_code) {
					case ICMP_UNREACH_NET:
						strncpy(hop->answer, "N!", sizeof(hop->answer));
						break;
					case ICMP_UNREACH_HOST:
						strncpy(hop->answer, "H!", sizeof(hop->answer));
						break;
					case ICMP_UNREACH_PROTO:
						strncpy(hop->answer, "P!", sizeof(hop->answer));
						break;
					case ICMP_UNREACH_NET_PROHIB:
					case ICMP_UNREACH_HOST_PROHIB:
						strncpy(hop->answer, "A!", sizeof(hop->answer));
						break;
				}
			} else if (icmp->icmp_type == ICMP_TIMEXCEED) {
				strncpy(hop->answer, "X!", sizeof(hop->answer));
			}
			if (hop->ttl == req->run.last_ttl_sent &&
					addr_cmp(&hop->ip, &req->target->ip)) {
				/* send more probes */
				event_add(req->run.ev_send, NULL);
			}
			break;
	}

reschedule_recv:
	event_add(req->run.ev_recv, NULL);

	if (hop) {
		gettimeofday(&recvtime, NULL);
		hop->delay = timeval_diff(&hop->sendtime, &recvtime) / 1000;
	}
}

static void
_cb_trace_timeout(evutil_socket_t fd, short what, void *arg)
{
	struct ggnet_traceroute_req *req;

	req = arg;

	if (req->ggtr->verbose)
		printf("XXX cbggnet_traceroute cb_trace_timeout (%s -> %s)\n",
			addr_ntoa(&req->srcip), addr_ntoa(&req->target->ip));
	_trace_done(req);
}

static void
_timeout_set(struct ggnet_traceroute_req *req, int sec, int usec)
{
	evtimer_del(req->run.ev_timeout);
	req->run.tv_timeout.tv_sec = sec;
	req->run.tv_timeout.tv_usec = usec;
	evtimer_add(req->run.ev_timeout, &req->run.tv_timeout);
}

static struct ggnet_traceroute_hop *
_hop_ip_id(struct ggnet_traceroute_req *req, int ip_id)
{
	struct ggnet_traceroute_hop *h;
	int i;

	TAILQ_FOREACH_REVERSE(h, &req->hops_list, tailhead, entry) {
		for (i = 0; i<TRACEROUTE_NB_PROBES; i++)
			if (h->ip_ids[i] == ip_id)
				return h;
	}
	return NULL;
}

static struct ggnet_traceroute_hop *
_hop_sport(struct ggnet_traceroute_req *req, int sport)
{
	struct ggnet_traceroute_hop *h;
	int i;

	TAILQ_FOREACH_REVERSE(h, &req->hops_list, tailhead, entry) {
		for (i = 0; i<TRACEROUTE_NB_PROBES; i++)
			if (h->sports[i] == sport)
				return h;
	}
	return NULL;
}

/** Called at the end of a traceroute
 * - Clean the hops_list by removing last non-answering hops
 * - Updates target ttl
 * - Count answering and total hops
 * - Calls user callback
 */
static void
_trace_done(struct ggnet_traceroute_req *req)
{
	struct ggnet_traceroute_hop *h, *ht, *hp;
	int hopcount_total = 0;
	int hopcount_answering = 0;

	TAILQ_FOREACH_REVERSE_SAFE(h, &req->hops_list, tailhead, entry, ht) {
		if (h->answer_count) {
			if (addr_cmp(&h->ip, &req->target->ip) == 0) {
				req->target->ttl = h->ttl + 1;
				hp = TAILQ_PREV(h, tailhead, entry);
				if (hp && (addr_cmp(&hp->ip, &req->target->ip) == 0)) {
					TAILQ_REMOVE(&req->hops_list, h, entry);
					continue;
				}
			}
			hopcount_answering++;
		}
		if (hopcount_answering > 0)
			hopcount_total++;
		else {
			TAILQ_REMOVE(&req->hops_list, h, entry);
		}
	}
	req->hopcount_total = hopcount_total;
	req->hopcount_answering = hopcount_answering;

	LIST_REMOVE(req, entry);
	req->ggtr->req_pending--;

	req->cb_done(req, req->data);
}

static int
pcap_dloff(pcap_t *pd)
{
	int i;

	i = pcap_datalink(pd);

	switch (i) {
		case DLT_EN10MB:
			i = 14;
			break;
		case DLT_IEEE802:
			i = 22;
			break;
		case DLT_FDDI:
			i = 21;
			break;
		case DLT_NULL:
			i = 4;
			break;
		default:
			i = -1;
			break;
	}
	return (i);
}

/* XXX do it with evdns
   static int
   get_asn(struct in_addr in)
   {
   const u_char *uaddr = (const u_char *)&in.s_addr;
   int i, counter;
   struct rrsetinfo *answers = NULL;
   char qbuf[MAXDNAME];
   int asn = -1;

   if (snprintf(qbuf, sizeof qbuf, "%u.%u.%u.%u.origin.asn.cymru.com",
   (uaddr[3] & 0xff), (uaddr[2] & 0xff),
   (uaddr[1] & 0xff), (uaddr[0] & 0xff)) >= sizeof (qbuf))
   return;
   if (getrrsetbyname(qbuf, C_IN, T_TXT, 0, &answers) != 0)
   return;
   for (counter = 0; counter < answers->rri_nrdatas; counter++) {
   char *p, *as = answers->rri_rdatas[counter].rdi_data;
   as++; // skip first byte, it contains length
   if (p = strchr(as,'|')) {
   p[-1] = 0;
   asn = atoi(as);
   goto ret;
   }
   }

ret:
freerrset(answers);
return asn;
}
*/

double
timeval_diff(struct timeval *x, struct timeval *y)
{
    double x_ms , y_ms , diff;
     
    x_ms = (double)x->tv_sec*1000000 + (double)x->tv_usec;
    y_ms = (double)y->tv_sec*1000000 + (double)y->tv_usec;
    diff = (double)y_ms - (double)x_ms;
     
    return diff;
}