tcptrace-bugs patch included: big performance improvement for long-lived conns w/ loss

From: Mike Lowell (m.lowell@f5.com)
Date: 09/01/05 

Message-ID: <4317AD6D.4020002@f5.com>
Date: Thu, 01 Sep 2005 18:39:57 -0700
From: Mike Lowell <m.lowell@f5.com>
Subject: tcptrace-bugs patch included: big performance improvement for long-lived conns w/ loss
Hi,

While trying to analyze a 302Byte tcpdump file with tcptrace, I found that tcptrace was taking an unusually long time (about 7 hours).  After a closer inspection, I realized that the tcpdump file contained only a few connections, and that each connection was VERY long (hundreds of thousands of packets).  I profiled tcptrace, and to my surprise the problem was immediately evident:

                                    
slak2:~$ gprof tcptrace-6.6.7/tcptrace
Flat profile:
                                 
Each sample counts as 0.01 seconds.              
  %   cumulative   self              self     total     
 time   seconds   seconds    calls   s/call   s/call  name
 98.11      3.63     3.63    25945     0.00     0.00  IsRTO
  0.81      3.66     0.03    32000     0.00     0.00  dotrace  
  0.54      3.68     0.02        1     0.02     3.70  ProcessFile
  0.27      3.69     0.01    32000     0.00     0.00  FindTTP
  0.27      3.70     0.01    32000     0.00     0.00  callback
[ ... ]

 
As you can see, IsRTO() was murdering the performance.  For my initial analysis of the 302Mbyte file, retransmit information was not necessary so I commented out the code which calls IsRTO(), and realize a performance gain of several orders of magnitude -- my 7 hour analysis only took 54 seconds. ;)
 
The problem: IsRTO() is walking a linked list of every single packet in my obscenely long TCP connections after a single retransmit is found.  Given that the first retransmit occurs at about packet #100 (of about 200000), the processing required becomes essentially O(n^2).

The fix: modify IsRTO() to walk the list from the tail end backwards.  On long TCP connections it's substantially more likely the packet you're looking for is near the end of the segment list rather than beginning.  In fact, in all cases it should be as fast or faster to start from the tail end of the segment list.  My proposed change takes 1 minute 15 seconds to complete.

There are obviously more efficient solutions by changing the higher-level algorithms of tcptrace, but this patch is only 1 line (i.e. very low risk), and given the huge performance benefit for this fairly obscure case, it seems good enough for now.


The patch is attached, and is inline:

########## CUT HERE START ##########
diff -ur tcptrace-6.6.7-orig/rexmit.c tcptrace-6.6.7/rexmit.c
--- tcptrace-6.6.7-orig/rexmit.c        2003-11-19 06:38:05.000000000 -0800
+++ tcptrace-6.6.7/rexmit.c     2005-09-01 18:20:57.000000000 -0700
@@ -780,7 +780,7 @@
   quadrant *pquad = whichquad(ptcb->ss,s);
   segment *pseg;
 
-  for (pseg = pquad->seglist_head; pseg != NULL; pseg = pseg->next) {
+  for (pseg = pquad->seglist_tail; pseg != NULL; pseg = pseg->prev) {
     if (s == (pseg->seq_lastbyte+1)) {
       if (pseg->acked < 4) return TRUE;
       else return FALSE;
########## CUT HERE END ##########


If this patch is okay, can it be included in a later stable version of tcptrace?

Thanks!
 
-- 

Mike Lowell
Product Management Engineer
F5 Networks - Product Management
(206) 272-6566
m.lowell@f5.com
Support: 1-888-88-BIGIP (24447)
AskF5: http://tech.f5.com/

diff -ur tcptrace-6.6.7-orig/rexmit.c tcptrace-6.6.7/rexmit.c
--- tcptrace-6.6.7-orig/rexmit.c 2003-11-19 06:38:05.000000000 -0800
+++ tcptrace-6.6.7/rexmit.c 2005-09-01 18:20:57.000000000 -0700
@@ -780,7 +780,7 @@
   quadrant *pquad = whichquad(ptcb->ss,s);
   segment *pseg;
 
- for (pseg = pquad->seglist_head; pseg != NULL; pseg = pseg->next) {
+ for (pseg = pquad->seglist_tail; pseg != NULL; pseg = pseg->prev) {
     if (s == (pseg->seq_lastbyte+1)) {
       if (pseg->acked < 4) return TRUE;
       else return FALSE;

This archive was generated by hypermail 2.1.7 : 09/02/05 EDT