#!/usr/bin/perl -w
# requires perl5
#
# a script to find routing loop in tcpdump output
#   algorithm:
#	- extract TCP SYN packets (to reduce data sets)
#	- find packets with the same initial sequence number but a different
#	  ttl (or hoplimit) value.
#
# usage: tcpdump -n -v 'tcp[13] & 2 != 0' | findloop.pl
#	 "tcpdump -n -v" or "tcpdump -n -v tcp" also works
#	 but it's less efficient
#
# 2000/01/28 initial version written by kjc@csl.sony.co.jp
#
# $Id: findloop.pl,v 1.2 2000/01/28 16:13:25 kjc Exp $
#
use strict;

my(@sessions, $listsize);
my($src, $dst, $flags, $seqno, $ttlname, $ttl, $rest);
my($sref, $ip4id, $i, $offset);

# set the LRU session list size to 100
$listsize = 100;

@sessions = ();

while (<>) {

    # tcpdump output:
    # timestamp src > dst: flags seqno win urgent options (ttl dd, id dd)
    if (/\S+\s+(\S+)\s+>\s+(\S+):\s+(\w+)\s+(\d+).*(ttl|hlim)\s+(\d+)(.*)/) {
	$src     = $1;
	$dst     = $2;
	$flags   = $3;
	$seqno   = $4;
	$ttlname = $5;
	$ttl     = $6;
	$rest    = $7;

	# handle only SYN packets
	next if ($flags ne "S");

	# only ipv4 has id
	$ip4id = 0;
	if ($ttlname eq "ttl") {
	    if ($rest =~ /id\s+(\d+)/) {
		$ip4id = $1;
	    }
	}

	#
	# go through the LRU session list
	#
	$offset = -1;
	for $i (0 .. $#sessions) {
	    $sref = $sessions[$i];
	    if ($sref->[0] == $seqno) {

		next if $sref->[2] ne $src;
		next if $sref->[3] ne $dst;

		# entry matched (same TCP SYN packet)
		$offset = $i;

		if ($ip4id != 0 && $sref->[4] != $ip4id) {
		    # this has a different ipv4 id field value
		    last;
		}

		if ($sref->[1] <= $ttl) {
		    # same or larger ttl; this is retransmission
		    # print "rexmit! $src > $dst: seqno:$seqno ttl:$ttl\n";
		    last;
		}

		if ($sref->[1] == $ttl + 1) {
		    # this is redirect
		    # print "redirect! $src > $dst: seqno:$seqno ttl:$ttl\n";
		    last;
		}

		# warn possible loop
		print "\npossible loop! ttl changed:$sref->[1] to $ttl\n";
		print $sref->[5];
		print $_;
		last;
	    }
	}
    
	#
	# maintain the LRU list
	#
	if ($offset >= 0) {
	    # the matching entry found.  remove this one from the list.
	    splice @sessions, $offset, 1 ;
	}
	elsif ($#sessions >= $listsize) {
	    # discard the least-recently-used entry
	    pop @sessions;
	}
	# append this entry
	unshift(@sessions, [ $seqno, $ttl, $src, $dst, $ip4id, $_ ]);
    }
}