/*

  Portions copyright (c) Nils McCarthy
  Portions copyright (c) MainNerve, Inc.
  Portions copyright (c) Ugen Antsilevitch
  Portions copyright (c) Genuity, Inc. 


  This file is part of LFT.

  The LFT software provided in this Distribution is
  Copyright 2002 MainNerve, Inc.

  The full text of our legal notices is contained in the file called
  COPYING, included with this Distribution.
 
  Authors: 

         -  MainNerve Staff <software@mainnerve.com> 
         -  Ugen Antsilevitch <ugen@xonix.com>
         -  Nils McCarthy <nils@shkoo.com> 
*/


#include "acconfig.h"
#include <assert.h>

#ifdef __CYGWIN__
#define __USE_W32_SOCKETS
#include "windows.h"
#include <ws2tcpip.h>
#include <sys/types.h>
#define LITTLE_ENDIAN 1
#define BYTE_ORDER 1
typedef signed long n_long;
typedef signed short n_short;
typedef signed long n_time;
#include <stdio.h>
#include <math.h>
#include <sys/time.h>
#include <getopt.h>
#include "linux-include/net/if_arp.h"
#include "linux-include/netinet/if_ether.h"
#include "linux-include/netinet/ip.h"
#include "linux-include/netinet/ip_icmp.h"
#include "linux-include/netinet/tcp.h"
#else
#include <sys/types.h>
#if TIME_WITH_SYS_TIME
# include <sys/time.h>
# include <time.h>
#else
# if HAVE_SYS_TIME_H
#  include <sys/time.h>
# else
#  include <time.h>
# endif
#endif
#include <stdio.h>
#include <math.h>
#include <sys/socket.h>
#include <net/if.h>
#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#include <netinet/ip_icmp.h>
#include <netinet/tcp.h>
#include <netinet/if_ether.h>
#include <assert.h>
#include <netdb.h>
#include <pcap.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <arpa/inet.h>
#ifdef BSD
#include <machine/limits.h>
#endif

#ifdef sun
#include <limits.h>
#include <strings.h>
#endif

#endif

#include "lft_ifname.h"
#include "lft_lsrr.h"
#include "whois.h"

/* Standard include on FreeBSD in system file "queue.h" but */
/* not on other systems */

/* #ifndef BSD */
#include "lft_queue.h"
/* #endif */

static char *hostname = NULL;
static char *hostname_lsrr[9];
static int hostname_lsrr_size = 0;
static int dflag = 0;
static int hop_info_size = 0;
static int hop_info_length = 0;

static int seq_start = 0; 
static int dport = 80;
static int sport = 53;		/* now we use tcp/53 dns-xfer */

static int win_len = 32768;

static int timeout_ms = 1000;	/* timeout between retries */
static int retry_max = 3;	/* number of retries before giving up */
static int retry_min = 1;	/* minimum number of checks per hop */
static double scatter_ms = 20;	/* milleseconds between sends */
static int ahead_limit = 5;	/* number of probes we can send
				 * without replies if we don't know
				 * the number of hops */
static int ttl_limit = 30;	/* max # hops */
static int ttl_min = 0;
static int break_on_icmp = 1;	/* break on icmp other than time exceeded */
static int noisy = 0;
static int nostatus = 0;
static int userdevsel = 0;
static int resolve_names = 1;
static int timetrace = 0;
static int max_net_dev_input = 32;
static int smart = 0;
static int do_netlookup = 0;
static int do_aslookup = 0;

struct in_addr local_address;
struct in_addr remote_address;

struct timeval ts_last_sent, now, begin_time, trace_done_time;

int send_sock;
int skip_header_len;

#ifdef __CYGWIN__
int recv_sock;
#endif

unsigned short ip_id;
unsigned char tcp_flags = TH_SYN;

int num_hops = 0;

static char *icmp_messages[] = {
  "endpoint",
  "unreachable net",
  "unreachable host",
  "unreachable protocol",
  "unreachable port",
  "need fragment",
  "source fail",
  "net unknown",
  "host unknown",
  "src isolated",
  "net prohib",
  "host prohib",
  "bad tos/net",
  "bad tos/hst",
  "prohibited",
  "precedence violation",
  "precedence cutoff"
};

/* The actual packet data */
struct trace_packet_s
{
  struct ip ip_hdr;
  struct ip_lsrr lsrr;		/* must go here for ip checksum to work */
  struct tcphdr tcp_hdr;
  int size;
}
trace_packet;


/* Packet container with additional info */
struct trace_packet_info_s
{
  int icmp_type;		/* ICMP_UNREACH code, -1 if RST reply */
  int is_done;			/* is this a final hop? */
  short hopno;
  unsigned int   seq;
  struct timeval sent;
  struct timeval recv;		/* 0 if unreceived */
  struct in_addr hopaddr;		/* IP address of router */
  struct trace_packet_s	packet;
  SLIST_ENTRY(trace_packet_info_s) next_by_hop;
  SLIST_ENTRY(trace_packet_info_s) next;
}
*trace_packet_info;		/* indexed by dport - dport */

/* list of packet containers */
static SLIST_HEAD(packets_s, trace_packet_info_s) trace_packets;
static int trace_packets_num = 0;

/* hop information, by ttl */
struct hop_info_s
{
  int num_sent;
  int all_sent, all_rcvd;
  struct timeval ts_last_sent;
  struct timeval ts_last_recv;	
  unsigned short state;
  unsigned short flags;
  SLIST_HEAD(hop_packets_s, trace_packet_info_s) packets;
}
*hop_info;

/* As the trace progresses, each hope will attempt
   to work through the states one by one until it
   receives an answer (2 attempts per state).
   Whatever state "works" - will be then set up on 
   following hops to continue from.
*/
#define HS_SEND_FIN		0x00
#define HS_SEND_SYN		0x01
#define HS_SEND_SYN_FIN		0x02
#define HS_MAX			(HS_SEND_SYN)

#define HF_ENDPOINT		0x01


#if defined(BSD_IP_STACK)
#define SCREWED_IP_LEN
#endif

#ifndef SCREWED_IP_LEN
static u_int32_t
ip_cksum (const struct ip *ip)
{
  register const u_short *sp = (u_short *) ip;
  register u_int32_t sum = 0; 
  register int count;

  /*
   * No need for endian conversions.
   */
  for (count = ip->ip_hl * 2; --count >= 0;)
    sum += *sp++;
  while (sum > 0xffff)
    sum = (sum & 0xffff) + (sum >> 16);
  sum = ~sum & 0xffff;

  return (sum);
}
#endif

static int
lft_resolve_port (const char *strport)
{

  struct servent *se;

  if ((se = getservbyname (strport, "tcp")))
    return (ntohs (se->s_port));

  return atoi (strport);
}

static u_int32_t
tcp_cksum (struct ip *ip, struct tcphdr *tcp)
{
  u_int32_t sum = 0; 
  register int count;
  u_short *sp;
  int old_ttl;

  sp = (u_short *) tcp;
  for (count = sizeof (struct tcphdr) / 2; --count >= 0;)
    sum += *sp++;

  sp = (u_short *) & ip->ip_src;
  for (count = 2; --count >= 0;)
    sum += *sp++;

  sp = (u_short *) & ip->ip_dst;
  for (count = 2; --count >= 0;)
    sum += *sp++;

  old_ttl = ip->ip_ttl;
  ip->ip_ttl = 0;
  sp = (u_short *) & ip->ip_ttl;	/* protocol comes right after this */
  for (count = 1; --count >= 0;)
    sum += *sp++;
  ip->ip_ttl = old_ttl;

  sum += htons (sizeof (struct tcphdr));

  while (sum > 0xffff)
    sum = (sum & 0xffff) + (sum >> 16);
  sum = ~sum & 0xffff;

  return (sum);
}


void
print_host (struct in_addr addr)
{
  struct hostent *h;

  if (!resolve_names)
    printf ("%s", inet_ntoa (addr));
  if (resolve_names) {
    h = gethostbyaddr ((void *) &addr, 4, AF_INET);
    if (h)
      printf ("%s (%s)", h->h_name, inet_ntoa (addr));
    else
      printf ("%s", inet_ntoa (addr));
  }
}

unsigned int
get_address(char *host)
{
  struct hostent *h;
  struct in_addr *addr;

  h = gethostbyname (host);
  if (!h) {
    fprintf (stderr, "Unknown host: %s\n", host);
    exit (1);
  }
  addr = (struct in_addr *) h->h_addr;
  return addr->s_addr;
}

static void
init_address (char *remote, char *pcap_dev)
{

  struct hostent *h;

  local_address.s_addr = lft_getifaddr (pcap_dev);	/* LJD */

  h = gethostbyname (remote);
  if (!h) {
    fprintf (stderr, "Unknown host: %s\n", remote);
    exit (1);
  }
  remote_address = *(struct in_addr *) h->h_addr;
  if (noisy && !nostatus) {
    print_host (local_address);
    printf (":%d", sport);
  }
  if (!nostatus)
    printf ("\n");
}

static void
open_sockets ()
{
#ifdef __CYGWIN__
  int optval = 1;
  DWORD dwBytesRet = 2048;
#endif
#ifdef IP_HDRINCL
  int on = 1;
#endif
  int i;
#if defined(sun) || defined(__CYGWIN__)
  struct sockaddr_in local_bind;
#endif

#if defined(sun)
  send_sock = socket (PF_INET, SOCK_RAW, IPPROTO_IP);
#elif defined(BSD_IP_STACK)
  send_sock = socket (PF_INET, SOCK_RAW, IPPROTO_TCP);
#elif defined(__CYGWIN__)
  send_sock = socket (PF_INET, SOCK_RAW, IPPROTO_RAW);
  recv_sock = socket (PF_INET, SOCK_RAW, IPPROTO_IP);
  
  if (recv_sock < 0) {
    perror ("raw socket");
    exit (1);
  }
  local_bind.sin_addr = local_address;
  local_bind.sin_port = 0;
  local_bind.sin_family = AF_INET;
  if (bind(recv_sock, (struct sockaddr *)&local_bind, sizeof(local_bind)) < 0) {
    perror("winsock bind");
  }
  /* apparently the cygwin include files don't define this: */
# define SIO_RCVALL 0x98000001
  if (WSAIoctl(recv_sock, SIO_RCVALL, &optval, sizeof(optval), NULL, 0, &dwBytesRet, NULL, NULL) < 0)
    perror("WSAIoctl");
#else
  send_sock = socket (PF_INET, SOCK_RAW, IPPROTO_RAW);
#endif
  if (send_sock < 0) {
    perror ("raw socket");
    exit (1);
  }
#ifdef IP_HDRINCL
  if (setsockopt (send_sock, IPPROTO_IP, IP_HDRINCL, (char *) &on,
		  sizeof (on)) < 0) {
    perror ("IP_HDRINCL");
    exit (1);
  }
#endif
#ifdef sun
  local_bind.sin_addr = local_address;
  local_bind.sin_port = 0;
  local_bind.sin_family = AF_INET;
  if (bind (send_sock, (struct sockaddr *)&local_bind, sizeof (local_bind)) < 0) {
    perror ("bind");
    exit (1);
  }
#endif

  /* set up initial ip headers, etc. */
  memset (&trace_packet, 0, sizeof (trace_packet));

  if (hostname_lsrr_size > 0) {
    for (i = 0; i < hostname_lsrr_size; i++) {
      trace_packet.lsrr.data[i] = get_address(hostname_lsrr[i]);
    }
    trace_packet.lsrr.ipl_code = IPOPT_LSRR;
    trace_packet.lsrr.ipl_len = hostname_lsrr_size * 4 + 3;
    trace_packet.lsrr.ipl_ptr = 4;
  }
  trace_packet.ip_hdr.ip_v = 4;
  if (hostname_lsrr_size > 0) {
    trace_packet.ip_hdr.ip_hl = 6 + hostname_lsrr_size; /* 5 + 3byte lsrr + addresses + padding */
    trace_packet.ip_hdr.ip_len = sizeof (struct ip) + sizeof(struct tcphdr) + trace_packet.lsrr.ipl_len + 1;
  } else {
    trace_packet.ip_hdr.ip_hl = 5;
    trace_packet.ip_hdr.ip_len = sizeof (struct ip) + sizeof(struct tcphdr);
  }

#ifdef SCREWED_IP_LEN
  /*  trace_packet.ip_hdr.ip_len = sizeof (struct ip) + sizeof(struct tcphdr); */
#else
  trace_packet.ip_hdr.ip_len = htons (trace_packet.ip_hdr.ip_len);
#endif
#ifndef IPDEFTTL
#define IPDEFTTL 64
#endif
  trace_packet.ip_hdr.ip_ttl = IPDEFTTL;
  trace_packet.ip_hdr.ip_p = IPPROTO_TCP;

  trace_packet.tcp_hdr.th_win = htons (win_len);
  trace_packet.tcp_hdr.th_off = sizeof (struct tcphdr) / 4;

  /* 
   * Init hop storage (array)
   * Init global packet info storage (SLIST)
   * Init per-hop packet info storage (SLIST)
   */
  hop_info_size = 255; /* can't be more then this */
  hop_info = malloc (sizeof (struct hop_info_s) * hop_info_size);
  for (i = 0; i < 255; i++) {
    bzero(&hop_info[i], sizeof(struct hop_info_s));
    hop_info[i].state = 0;
    SLIST_INIT(&(hop_info[i].packets));
  }

  SLIST_INIT(&trace_packets);
}

static unsigned int
new_seq()
{
  if (smart) {
    return rand();
  } else {
    return seq_start + trace_packets_num;
  }
}
	

static unsigned int
send_packet (short nhop, unsigned short ttl, unsigned int seq, unsigned char flags)
{
  struct sockaddr_in dest;
  unsigned int tseq;
  unsigned short tttl;
  char buf[sizeof(struct trace_packet_s) + 2], *bptr;
  int blen;

  struct trace_packet_info_s	*pinfo;
  struct trace_packet_s *packet;

  if (!(pinfo = malloc(sizeof(struct trace_packet_info_s)))) {
    perror("malloc");
    exit(1);
  }

  bzero(pinfo, sizeof(struct trace_packet_info_s));
  packet = &(pinfo->packet);
  memcpy(packet, &trace_packet, sizeof(struct trace_packet_s));

  /*
   * XXX change sequence generation method here
   */
  if (seq == 0)
    tseq = new_seq();
  else
    tseq = seq;

  if (nhop == -1)
    tttl = ttl;
  else
    tttl = nhop + 1;

  /* XXX DO NOT INSERT ANY CODE HERE THAT IS NOT DIRECTLY  *
   * RELATED TO PACKET GENERATION!!!!                      */

  if (noisy) 
    printf("SEND TTL=%d TSEQ=%u FLAGS=%x\n", nhop, tseq, flags);
  else {
    if (!nostatus)
      printf("_");
  }

  ts_last_sent = now;

  packet->ip_hdr.ip_ttl = tttl;
  packet->ip_hdr.ip_src = local_address;
  packet->ip_hdr.ip_dst = remote_address;

  packet->ip_hdr.ip_sum = 0;
#if !defined(SCREWED_IP_LEN)
  packet->ip_hdr.ip_sum = ip_cksum (&(packet->ip_hdr));
#endif

  packet->tcp_hdr.th_dport = htons (dport);
  /*
    trace_packet.tcp_hdr.th_seq = htonl (seq_start + trace_packet_info_length);
  */
  packet->tcp_hdr.th_seq = htonl (tseq);
  packet->tcp_hdr.th_sport = htons (sport);
  packet->tcp_hdr.th_flags = flags;

#if defined(SOLARIS_LENGTH_IN_CHECKSUM)
  packet->tcp_hdr.th_sum = htons (sizeof (struct tcphdr));
#else
  packet->tcp_hdr.th_sum = 0;
  packet->tcp_hdr.th_sum = tcp_cksum (&(packet->ip_hdr), &(packet->tcp_hdr));
#endif

  dest.sin_family = AF_INET;
  dest.sin_addr = remote_address;
  dest.sin_port = 0;

  bptr = buf;
  memcpy(bptr, &(packet->ip_hdr), sizeof(struct ip));
  bptr += sizeof(struct ip);
  if (packet->lsrr.ipl_len > 0) {
    memcpy(bptr, &(packet->lsrr), packet->lsrr.ipl_len + 1);
    bptr += (packet->lsrr.ipl_len + 1); /* PADDING !!! */
  }
  memcpy(bptr, &(packet->tcp_hdr), sizeof(struct tcphdr));
  blen = sizeof(struct ip) + packet->lsrr.ipl_len + sizeof(struct tcphdr);

  if (sendto (send_sock, buf, blen, 0, (struct sockaddr *)&dest, sizeof (dest)) < 0) {
    perror ("sendto");
    exit (1);
  }
 
  pinfo->hopno = nhop;
  pinfo->seq = tseq;
  pinfo->sent = now;
  SLIST_INSERT_HEAD(&trace_packets, pinfo, next);
  trace_packets_num++;

  if (nhop != -1) {
    SLIST_INSERT_HEAD(&hop_info[nhop].packets, pinfo, next_by_hop);
    hop_info[nhop].num_sent++;
    hop_info[nhop].all_sent++;
    hop_info[nhop].ts_last_sent = now;
  }

  return tseq;
}

static double
timediff_ms (struct timeval prior, struct timeval latter)
{
  return
    (latter.tv_usec - prior.tv_usec) / 1000. +
    (latter.tv_sec - prior.tv_sec) * 1000.;
}

static unsigned int
send_hop (short nhop)
{
  struct hop_info_s *h = &hop_info[nhop];

  if (!smart)
    return send_packet (nhop , 0, 0, tcp_flags);

  if (h->state == HS_SEND_FIN) {
    return send_packet(nhop, 0, 0, TH_FIN);
  }

  if (h->state == HS_SEND_SYN) {
    return send_packet(nhop, 0, 0, TH_SYN);
  }

  printf("Bad state %d for hop %d\n", h->state, nhop);
  return -1;
}

static int
hop_state_up (short nhop)
{
  struct hop_info_s *h = &hop_info[nhop];

  if (h->state == HS_MAX)
    return -1;

  h->state++;
  h->num_sent = 0; /* for this state that is */
  return 0;
}

static int
hop_state_copy(short nhop)
{
  int i;
	
  if (noisy > 2)
    printf("Upping states of the hops following %d\n", nhop);
  for (i = (nhop+1); i <= 255; i++)
    if (hop_info[i].state < hop_info[nhop].state) {
      hop_info[i].state = hop_info[nhop].state;
      hop_info[i].num_sent = 0;
    }

  return 0;
}

void
finish ()
{
  int hopno;
  int maxhop;
  int reply, noreply;
  int noreply_hop_first = 0;
  struct trace_packet_info_s 	*tp;
  char *netname;
  char ind;
  /*  int last_state = -1; */

  gettimeofday (&trace_done_time, NULL);

  if (noisy) printf ("Concluding with %d hops.\n", (num_hops+1));
  if (num_hops) {
    maxhop = num_hops;
    /* if we got a bunch of hits for the end host, display them all */
    SLIST_FOREACH(tp, &trace_packets, next)
      if (tp->is_done)
	tp->hopno = maxhop;
  } else {
    maxhop = hop_info_length - 1;
  }

  if (num_hops && !nostatus)
    printf (".\n\nTTL  LFT trace to ");
  else {
    if (!nostatus)
      printf ("\n\nTTL  LFT trace to ");
    if (nostatus)
      printf ("\nTTL  LFT trace to ");
  };

  print_host (remote_address);
  printf(":%d/tcp\n",dport);

  noreply = 0;
  reply = 0;
  for (hopno = ttl_min; hopno <= maxhop; hopno++) {
    struct in_addr last_hop;

    if (hop_info[hopno].all_rcvd != 0) {
      if (noreply == 1)
	printf("**   [neglected] no reply packets received from TTL %d\n", hopno);
      if (noreply > 1)
	printf("**   [neglected] no reply packets received from TTLs %d through %d\n", hopno - noreply + 1, hopno);

      noreply_hop_first = 0;
    }

    last_hop.s_addr = 0;
    if ((hop_info[hopno].state == HS_SEND_FIN) && (hop_info[hopno+1].state == HS_SEND_SYN)) {
      printf("**   [firewall] the next gateway may statefully inspect packets\n");
    }

    if ((hop_info[hopno].flags & HF_ENDPOINT) && (noreply >= ((maxhop - ttl_min)/2))) {
      printf("**   [4.2-3 BSD bug] the next gateway may errantly reply with reused TTLs\n");
    }


    if (hop_info[hopno].all_rcvd == 0) {
      reply = 0;
    } else {

      printf ("%2d  ", hopno + 1);
      ind = ' ';

      SLIST_FOREACH(tp, &(hop_info[hopno].packets), next_by_hop) {
	
	if (tp->recv.tv_sec) {
	  reply = 1;
	
	  if (tp->icmp_type < -2 || tp->icmp_type > 15)
	    printf (" [icmp code %d]", tp->icmp_type);
	  else if (tp->icmp_type >= 0)
	    printf (" [%s]", icmp_messages[tp->icmp_type + 1]);
	
	  if (last_hop.s_addr != tp->hopaddr.s_addr) {
	    ind = ' ';
	    if (do_aslookup) {
	      netname = w_lookup_as(inet_ntoa(tp->hopaddr));
	      if (netname)
		printf(" [%s]", netname);
	      else
		printf(" [ASN?]");
	    }
			
	    if (do_netlookup) {
	      netname = w_lookup_netname(inet_ntoa(tp->hopaddr));
	      if (netname)
		printf(" [%s]", netname);
	      else
		printf(" [unknown]");
	    }

	    if (tp->icmp_type == -1) {
	      printf(" [target]");
	    }

	    printf(" ");
	    print_host (tp->hopaddr);
	    if (tp->icmp_type == -1) {
	      printf(":%d",dport);
	    }
	  }
	
	  last_hop = tp->hopaddr;
	  printf ("%c%.1f", ind, timediff_ms(tp->sent, tp->recv));
	} else {
	  printf ("%c*", ind);
	}
	ind = '/';
      }
      printf ("ms\n");
    }
    if (reply)
      noreply = 0;
    else
      noreply++;
    reply = 0;
  }
  /*  printf ("\n"); */

  if (!num_hops) 
    printf("**   [%d/tcp failed]  Try alternate options or use -V to see packets.\n", dport);
  if (timetrace) {
    gettimeofday (&now, NULL);
    printf ("\nLFT\'s trace took %.2f seconds.  ", 
	    (timediff_ms(begin_time, trace_done_time) / 1000));
    if (resolve_names || do_aslookup || do_netlookup) 
      printf("Resolution required %.2f seconds.", (timediff_ms(trace_done_time, now) / 1000));
    printf("\n");
  }
  printf("\n"); 
  exit (0);
} 

void
check_timeouts ()
{
  int nhop;
  int need_reply = 0;
  int no_reply = 0;
  int last_return = 0;
  unsigned int tseq;

  tseq = 0;

  gettimeofday (&now, NULL);
  if (timediff_ms (ts_last_sent, now) < scatter_ms)
    return;			/* not ready to send another packet yet */

  for (nhop = ttl_min; nhop < hop_info_length; nhop++) {
    if (!hop_info[nhop].num_sent) {
      if (noisy) printf("Sending FIRST PACKET for hop %d\n", nhop);
      send_hop(nhop);
      return;
    }
  }

  for (nhop = ttl_min; nhop < hop_info_length; nhop++) {
    if (hop_info[nhop].num_sent <= retry_max && !hop_info[nhop].ts_last_recv.tv_sec) {
      if (noisy == 2) printf("No reply on TTL %d; ", nhop);
      if (timediff_ms (hop_info[nhop].ts_last_sent, now) >= timeout_ms) {
	/* we timed out waiting for this hop -- retry if we have any
	 * more tries */
	if (hop_info[nhop].num_sent < retry_max) {
	  if (noisy == 2) printf("timed out, resending\n");
	  send_hop(nhop);
	  return;
	} else {
	  if (!smart || hop_state_up(nhop)) {
	    if (noisy == 2) printf("timed out, no reply\n");
	    no_reply++;
	  }
	}
      } else {
	if (noisy == 2) printf("not timed out\n");
	need_reply++;		/* we have to wait for this one to timeout */
      }
    } else { /* have reply */
      last_return = nhop;
    }
  }

  if (noisy == 2) {
    printf ("hop_info_length %d, last_return %d\n", hop_info_length, last_return);
    printf ("no_reply %d, ahead_limit %d\n", no_reply, ahead_limit);
    printf ("num_hops %d\n", num_hops);
    printf ("need_reply %d\n", need_reply);
  }
  if (no_reply >= ahead_limit) {	/* we timed out. */
    if ((last_return + 3) * 2 < hop_info_length) {
      printf("\n\nLFT can\'t seem to round-trip.  Local packet filter in the way?");
      if (noisy == 2) printf("Will finish ONE\n");
      finish ();
    }
    /* otherwise search out for weird ttl's on return packets */
    /* retry_max = 1; */
    /* retry_min = 1; */
  }

  if ((!num_hops || hop_info_length < num_hops || need_reply) && hop_info_length < ttl_limit) { 
    if (noisy == 2) printf("I still have unanswered hops.\n");
    if (need_reply >= ahead_limit) {
      if (noisy == 2) printf("\tI\'m too far ahead, recycling.\n");
      return;			/* wait for some replies before we go on */
    }

    if (num_hops > 0 && hop_info_length >= num_hops) {
      if (noisy == 2) printf("I have blanks to fill -  RETURN \n");
      return;			/* we know how long the path is --
				 * wait to fill in the blanks */
    }

    nhop = hop_info_length++;
    send_hop(nhop);
  } else { 
    if (noisy) printf("Everyone responded.  Moving on...\n");
    for (nhop = ttl_min; nhop < hop_info_length; nhop++) {
      if (hop_info[nhop].num_sent < retry_min && hop_info[nhop].num_sent <= retry_max /*&& hop_info[nhop].ts_last_recv.tv_sec*/) {
	send_hop(nhop);
	return;
      }
    }

    if (noisy) printf("Will finish TWO\n");
    finish ();
  } 
}

void
recv_packet (unsigned int seq, struct in_addr ipaddr, int icmp_type)
{
  double ms;
  struct trace_packet_info_s *tp = NULL;

  gettimeofday (&now, NULL);

  SLIST_FOREACH(tp, &trace_packets, next) {
    if (tp->seq == seq)
      break;
  }

  if (!tp) {
    if (noisy)
      printf("Not for us?\n");
    else
      if (!nostatus) printf("?");
	
    return;
  }

  if (tp->recv.tv_sec) {
    if (noisy)
      printf ("duplicate?\n");
    else
      if (!nostatus) printf("!");
    return;
  }

  if (noisy) {
    printf ("RECV RSEQ=%u\n", seq);
  } else {
    if (!nostatus) printf("_");
  }

  tp->recv = now;
  if (tp->hopno != -1) {
    hop_info[tp->hopno].ts_last_recv = now;
    hop_info[tp->hopno].all_rcvd++;
    hop_state_copy(tp->hopno);

    if (icmp_type == -1)
      hop_info[tp->hopno].flags |= HF_ENDPOINT;
  }

  tp->hopaddr = ipaddr;
  tp->icmp_type = icmp_type;
  if (icmp_type != -2 && (!num_hops || num_hops > tp->hopno))
    if (break_on_icmp || (icmp_type == -1)) {
      if (tp->hopno != -1) { /* we set fake type -1 when we get actual
			      * tcp packet in return - meaning destination */
      	num_hops = tp->hopno;
      	tp->is_done = 1;
       	if (noisy) printf ("Looks like we made it.\n");
      }
    }

  /* adjust scatter if we have fast reply times */
  ms = timediff_ms (tp->sent, tp->recv);
  scatter_ms = (scatter_ms * (ahead_limit - 1) + ms) / ahead_limit;

}

void process_packet (const u_char *packet)
{
  const struct ip *ip, *orig_ip;
  const struct tcphdr *tcp;
  const struct icmp *icmp;

  if (noisy == 3) printf("New data from pcap!\n");
  check_timeouts ();

  packet += skip_header_len;
  ip = (void *) packet;

  packet += 4 * ip->ip_hl;
  switch (ip->ip_p) {
  case IPPROTO_ICMP:
    orig_ip = ip;
    icmp = (void *) packet;
    if (icmp->icmp_type != ICMP_UNREACH && icmp->icmp_type != ICMP_TIMXCEED)
      return;
    ip = &icmp->icmp_ip;
    if (ip->ip_p != IPPROTO_TCP)
      return;			/* not a response to our tcp probe */
    packet = (void *) ip;
    packet += 4 * ip->ip_hl;
    tcp = (void *) packet;
    if (ntohs (tcp->th_dport) != dport || ip->ip_src.s_addr != local_address.s_addr || ip->ip_dst.s_addr != remote_address.s_addr)
      return;			/* not for us */
    /*if (ntohl(tcp->th_seq) < seq_start || ntohl(tcp->th_seq) > seq_start + trace_packet_info_length)
      	return; * not for us */


    if (noisy) printf ("ICMP SEQ=%u received\n", ntohl (tcp->th_seq));
    recv_packet (ntohl (tcp->th_seq) , orig_ip->ip_src,
		 (icmp->icmp_type == ICMP_TIMXCEED) ? -2 : icmp->icmp_code);
    break;

  case IPPROTO_TCP:
    /* check for RST reply */
    tcp = (void *) packet;
    if (!(tcp->th_flags & TH_RST) && !(tcp->th_flags & TH_ACK) && !(tcp->th_flags & TH_SYN))
      return;			/* not what we're looking rfor */

    if (ntohs (tcp->th_sport) != dport || ip->ip_src.s_addr != remote_address.s_addr || ip->ip_dst.s_addr != local_address.s_addr) {
      return;			/* not the right connection */
    }

    if (noisy)
      printf("TCP flags= ");
    if (tcp->th_flags & TH_RST)
      if (noisy) printf ("RST ");
    if (tcp->th_flags & TH_ACK)
      if (noisy) printf ("ACK ");
    if (tcp->th_flags & TH_SYN)
      if (noisy) printf ("SYN ");
    if (noisy) printf (" SEQ=%lu ACK=%lu ", ntohl (tcp->th_seq), ntohl (tcp->th_ack));
    if (noisy) printf ("from %s\n", inet_ntoa (ip->ip_src));

    /*if (ntohl(tcp->th_ack) < seq_start || ntohl(tcp->th_ack) > seq_start + trace_packet_info_length + 1)
    	return; * not for us */
    recv_packet (ntohl (tcp->th_ack) - 1, ip->ip_src, -1);
    /*
      send_packet(-1, IPDEFTTL, ntohl(tcp->th_ack) + 1, TH_RST);
    */
    return;
  }
}

#ifndef __CYGWIN__
void
pcap_process_packet (u_char * user_data, const struct pcap_pkthdr *hdr,
		     const u_char * packet)
{
  process_packet(packet);
}
#endif

static void
usage (char *prog)
{
  fprintf (stderr,
	   "\nLFT - the alternative traceroute tool for network (reverse) engineers\n\nUsage: %s [<options>] [<gateway> <...>] <hostname:dport>\n"
	   "\nOptions are:\n"
	   "  -d <dport>       destination port number\n"
	   "  -s <sport>       source port number\n"
	   "  -m <min>         minimum number of probes to send per host\n"
	   "  -M <max>         maximum number of probes to send per host\n"
	   "  -a <ahead>       number of hops forward to query before receiving replies\n"
	   "  -c <scatter ms>  minimum number of milliseconds between subsequent queries\n"
	   "  -t <timeout ms>  maximum RTT before assuming packet was dropped\n"
	   "  -l <min ttl>     minimum TTL to use on outgoing packets\n"
	   "  -q <sequence>    set the initial sequence number (ISN)\n"
           "  -D <device/ip>   network device (name or IP address) to use (e.g., \"en1\")\n"
           "  -H <ttl>         maximum number of hops to traverse (max TTL of packets)\n"
           "  -i               disable \"stop on ICMP\" other than TTL expired\n"
           "  -n               disable use of the DNS resolver to display hostnames\n"
           "  -F               enable use of FIN packets only (defaults are SYN)\n"
           "  -N               enable lookup and display of network names\n"
           "  -A               enable lookup and display of Autonomous System numbers\n"
           "  -T               enable display of LFT's execution timer\n"
           "  -S               suppress the status bar (only show the completed trace)\n"
           "  -V               print a lot of debugging garbage including packets\n"
           "  -E               enable LFT's stateful Engine to detect firewalls\n"
	   "  -v               show version information\n"  "\n"
	   "Default is: %s -d %d -m %d -M %d -a %d -c %.0f -t %d -H %d -s %d\n\n",
	   prog, prog, dport, retry_min, retry_max, ahead_limit,
	   scatter_ms, timeout_ms, ttl_limit, sport);
  exit (1);
}

static void
version (void)
{
  fprintf (stderr, "\n"
	   "LFT version 2.2 2003/05/07 compiled for " HOST_SYSTEM_TYPE "\n\n"
	   "    Compile-time options:\n\n"
#if defined(BSD_IP_STACK)
	   "      + BSD\n"
#endif
#if defined(linux)
	   "      + Linux\n"
#endif
#if defined(sun)
	   "      + SUN\n"
#endif
#if !defined(sun) && !defined(linux) && !defined(BSD_IP_STACK)
	   "      (unknown architecture)\n"
#endif
#if defined(SCREWED_IP_LEN)
	   "      + backwards IP length field\n"
#else
	   "      + forwards IP length field\n"
#endif
#if defined(IP_HDRINCL)
	   "      + IP_HDRINCL\n"
#else
	   "      + no IP_HDRINCL\n"
#endif
	   "\n");
  exit (0);
}

#ifdef __CYGWIN__
void cygwin_process()
{
  fd_set fds;
  FD_ZERO(&fds);
  FD_SET(recv_sock, &fds);
  struct timeval tm;
  tm.tv_sec = 0;
  tm.tv_usec = 100000;
  if (select(recv_sock+1, &fds, 0, 0, &tm) < 0) {
    perror("select");
    exit(1);
  }
  if (FD_ISSET(recv_sock, &fds)) {
    /* read packet */
    char packetbuf[2048];
    memset(packetbuf, 0, sizeof(packetbuf));
    int nread = recv(recv_sock, packetbuf, sizeof(packetbuf), 0);
    if (nread <= 0) {
      perror("read");
      exit(1);
    }
    process_packet(packetbuf);
  }
}

#endif

extern int
main (int argc, char **argv)
{
#ifndef __CYGWIN__
  char ebuf[PCAP_ERRBUF_SIZE];
  static pcap_t *pd;
#endif
  char *pcap_dev, *userdev = NULL;
  int ch;
  int use_fins = 0;
  char *cp;
  struct timeval tb;

  setbuf (stdout, NULL);

  while ((ch = getopt (argc, argv, "EANc:FVq:d:M:l:H:m:a:s:t:D:p:vinSTw:")) != EOF)
    switch (ch) {
    case 'F':
      if (smart) {
	fprintf (stderr,
		 "\nLFT warning: TCP flags are selected automatically using (-E) option.\n             Ignoring FINs-only (-F) option and using smart Engine.\n\n");
	break;
      } 
      tcp_flags = TH_FIN;
      use_fins = 1;
      dport = 25000;
      break;
    case 'd':
      ++dflag;
      dport = atoi (optarg);
      break;
    case 'q':
      seq_start = atol (optarg);
      break;
    case 'w':
      win_len = atoi(optarg);
      break;
    case 'm':
      retry_min = atoi (optarg);
      break;
    case 'M':
      retry_max = atoi (optarg);
      break;
    case 'N':
      do_netlookup = 1;
      break;
    case 'A':
      do_aslookup = 1;
      break;
    case 'n':
      resolve_names = 0;
      break;
    case 'T':
      timetrace = 1;
      break;
    case 's':
      sport = lft_resolve_port (optarg);
      break;
    case 'E':
      if (use_fins) {
	fprintf (stderr,
		 "\nLFT warning: TCP flags are selected automatically using (-E) option.\n             Ignoring smart Engine (-E) option and using FINs-only (-F).\n\n");
	break;
      }
      smart = 1;
      break;
    case 'S':
      nostatus = 1;
      break;
    case 'D':
      {
	if (strlen (optarg) > max_net_dev_input) {
	  fprintf (stderr,
		   "Net interface names are limited to %d characters. (e.g., \"eth0\" or \"ppp0\")\n",
		   max_net_dev_input);
	  exit (1);
	}
	userdevsel = 1;
	userdev = optarg;
      }
      break;
    case 'a':
      ahead_limit = atoi (optarg);
      break;
    case 'c':
      scatter_ms = atoi (optarg);
      if (scatter_ms < 1)
	scatter_ms = 1;
      if (scatter_ms > 100)
	scatter_ms = 100;
      break;
    case 't':
      timeout_ms = atoi (optarg);
      break;
    case 'H':
      ttl_limit = atoi (optarg);
      break;
    case 'l':
      ttl_min = atoi(optarg);
      hop_info_length = ttl_min;
      if (ttl_min > 0)
	ttl_min--;
      break;
    case 'i':
      break_on_icmp = 0;
      break;
    case 'v':
      version ();
      break;
    case 'V':
      noisy++;
      break;
    default:
      usage (argv[0]);
    }

  if ((argc - optind) < 1)
    usage (argv[0]);


  gettimeofday (&tb, NULL);
  /* eventually this might want to use /dev/urandom or
   * something on machines that have it.  otherwise,
   * this does a fairly decent job of using the system
   * clock.
   *
   * multiply tv_usec (range 0-1000000) to be in range 0-2^31,
   * and xor to randomize the high bits of tv_sec that don't
   * change very much.
   */
  srand(tb.tv_sec ^ (tb.tv_usec * 2147));

  if (!seq_start) {
    seq_start = rand();
    if (noisy) printf("Setting my ISN = %d\n", seq_start);
  }

  hostname = argv[optind++];
  hostname_lsrr_size = 0;
  while (optind < argc) {
    hostname_lsrr[hostname_lsrr_size++] = argv[optind++];
    if (hostname_lsrr_size > IP_LSRR_DEST) {
      fprintf(stderr, "Too many LSRR hosts - maximum is 8\n");
      exit(1);
    }
  }
  if (hostname_lsrr_size > 0) {
    hostname_lsrr[hostname_lsrr_size++] = hostname;
    hostname = hostname_lsrr[0];
  }

  /* allow hostname:port if -d not specified */
  if ((cp = strchr (hostname, ':'))) {
    if (!dflag) {
      *cp++ = '\0';
      dport = lft_resolve_port (cp);
    }
  }

#ifdef __CYGWIN__
  WSADATA wsaData;
  if (WSAStartup(MAKEWORD(2, 1), &wsaData) != 0) {
    perror("WSAStartup");
    exit(1);
  }
#endif

  /* if not given network interface, select one automatically */
  if (!userdevsel) {
#ifdef __CYGWIN__
    pcap_dev = "none";
#else
    pcap_dev = pcap_lookupdev (ebuf);
    if (pcap_dev == NULL) {
      fprintf (stderr, "%s\n", ebuf);
      exit (1);
    };
#endif
  } else {
    struct in_addr addr;
    if (inet_aton(userdev, &addr)) {
      /* specified by ip address -- look up device. */
      pcap_dev = lft_getifname(addr);
      if (!pcap_dev) {
	fprintf (stderr, "Could not find matching interface with IP address %s\n", userdev);
	exit(1);
      }
    } else
      pcap_dev = userdev;
  };

#ifdef __CYGWIN__
  skip_header_len = 0;
  pcap_dev = "eth0";
#else
  /* now, fix pcap's linux implementation */
  if (!strncmp (pcap_dev, "lo:", 3) || !strcmp (pcap_dev, "lo")) {
    pcap_dev = "ppp0";
    skip_header_len = 0;
  } else if (!strncmp (pcap_dev, "ppp", 3))
    skip_header_len = 0;
  else				/* assume ethernet */
    skip_header_len = sizeof (struct ether_header);
#endif
  if (noisy && !nostatus)
    printf ("Using device %s, ", pcap_dev);
#ifndef __CYGWIN__
  pd = pcap_open_live (pcap_dev, 1600, 0, 20, ebuf);
  if (!pd) {
    fprintf (stderr, "%s\n", ebuf);
    exit (1);
  }
#endif
  init_address (hostname, pcap_dev);
  open_sockets ();

  if (do_netlookup || do_aslookup)
    w_init();

#ifndef __CYGWIN__
  setuid (getuid ());
#endif

  if (smart) {
    if (retry_min < 2)
      retry_min = 2;
    if (retry_max < retry_min)
      retry_max = retry_min;
  }

  gettimeofday (&begin_time, NULL);
  if (!nostatus && !noisy)
    printf("Tracing ");

#ifdef __CYGWIN__
  for (;;) {
    cygwin_process();
    check_timeouts();
  }
#else
  while (pcap_dispatch (pd, -1, pcap_process_packet, 0) >= 0) {
    if (noisy == 3) printf("OUTSIDE dispatch \n");
    check_timeouts ();
  }
#endif

  return 0;
}