Qt: modify RTT graph (handle GSO, SACK, etc), plus bug fixes

Modifications to RTT graph:
 - change x-axis to time (s) rather than sequence number
    [ avoids sequence number wraparound ambiguity, plus
       easier to correlate RTT changes to tcptrace graph ]
 - change RTT computation to properly handle acks to GSO packets
 - change RTT computation to take SACK blocks into account

Bug fixes:
 - eliminate potential memory leak if some packets are unacked
 - ensure RTT graph is shown if TCPGraph window is opened to it directly

Change-Id: I2bdcab97399ebde0f15c78fa19c882529a814580
Reviewed-on: https://code.wireshark.org/review/19662
Petri-Dish: Alexis La Goutte <alexis.lagoutte@gmail.com>
Tested-by: Petri Dish Buildbot <buildbot-no-reply@wireshark.org>
Reviewed-by: Alexis La Goutte <alexis.lagoutte@gmail.com>
Reviewed-by: Anders Broman <a.broman58@gmail.com>

5 files changed, 224 insertions, 57 deletions

diff --git a/ui/gtk/tcp_graph.c b/ui/gtk/tcp_graph.c
index 5c57cd2d41..e7658ee878 100644
--- a/ui/gtk/tcp_graph.c
+++ b/ui/gtk/tcp_graph.c
@@ -4230,7 +4230,7 @@ static void rtt_read_config(struct gtk_graph *g)
 static void rtt_initialize(struct gtk_graph *g)
 {
     struct segment *tmp, *first = NULL;
-    struct unack   *unack       = NULL, *u;
+    struct rtt_unack   *unack   = NULL, *u;
     double          rttmax      = 0;
     double          xx0, yy0, ymax;
     guint32         xmax        = 0;
@@ -4255,7 +4255,7 @@ static void rtt_initialize(struct gtk_graph *g)
             seqno -= seq_base;
             if (tmp->th_seglen && !rtt_is_retrans(unack, seqno)) {
                 double time_val = tmp->rel_secs + tmp->rel_usecs / 1000000.0;
-                u = rtt_get_new_unack(time_val, seqno);
+                u = rtt_get_new_unack(time_val, seqno, tmp->th_seglen);
                 if (!u) return;
                 rtt_put_unack_on_list(&unack, u);
             }
@@ -4263,22 +4263,33 @@ static void rtt_initialize(struct gtk_graph *g)
             if (seqno + tmp->th_seglen > xmax)
                 xmax = seqno + tmp->th_seglen;
         } else if (first) {
-            guint32       ackno    = tmp->th_ack -seq_base;
+            guint32       ackno    = tmp->th_ack - seq_base;
             double        time_val = tmp->rel_secs + tmp->rel_usecs / 1000000.0;
-            struct unack *v;
+            struct rtt_unack *v;
 
             for (u=unack; u; u=v) {
-                if (ackno > u->seqno) {
+                if (tcp_seq_after(ackno, u->seqno)) {
                     double rtt = time_val - u->time;
                     if (rtt > rttmax)
                         rttmax = rtt;
+                    if (tcp_seq_eq_or_after(ackno, u->end_seqno)) {
+                        // fully acked segment - can safely be deleted
+                        v = u->next;
+                        rtt_delete_unack_from_list(&unack, u);
+                    } else {
+                        // partial ACK of GSO segment -
+                        //   just modify segment to reflect ACKed bytes
+                        u->seqno = ackno;
+                    }
+                } else {
+                    // nothing was acked in this seg - just move along
                     v = u->next;
-                    rtt_delete_unack_from_list(&unack, u);
-                } else
-                    v = u->next;
+                }
             }
         }
     }
+    // it's possible there's still unacked segs - so be sure to free list!
+    rtt_destroy_unack_list(&unack);
 
     xx0  = seq_base;
     yy0  = 0;
@@ -4295,7 +4306,7 @@ static void rtt_initialize(struct gtk_graph *g)
 static void rtt_make_elmtlist(struct gtk_graph *g)
 {
     struct segment *tmp;
-    struct unack   *unack    = NULL, *u;
+    struct rtt_unack  *unack = NULL, *u;
     struct element *elements, *e;
     guint32         seq_base = (guint32) g->bounds.x0;
 
@@ -4318,17 +4329,17 @@ static void rtt_make_elmtlist(struct gtk_graph *g)
 
             if (tmp->th_seglen && !rtt_is_retrans(unack, seqno)) {
                 double time_val = tmp->rel_secs + tmp->rel_usecs / 1000000.0;
-                u = rtt_get_new_unack(time_val, seqno);
+                u = rtt_get_new_unack(time_val, seqno, tmp->th_seglen);
                 if (!u) return;
                 rtt_put_unack_on_list(&unack, u);
             }
         } else {
-            guint32       ackno    = tmp->th_ack -seq_base;
+            guint32       ackno    = tmp->th_ack - seq_base;
             double        time_val = tmp->rel_secs + tmp->rel_usecs / 1000000.0;
-            struct unack *v;
+            struct rtt_unack *v;
 
             for (u=unack; u; u=v) {
-                if (ackno > u->seqno) {
+                if (tcp_seq_after(ackno, u->seqno)) {
                     double rtt = time_val - u->time;
 
                     e->type   = ELMT_ELLIPSE;
@@ -4339,13 +4350,25 @@ static void rtt_make_elmtlist(struct gtk_graph *g)
                     e->p.ellipse.dim.y      = g->zoom.y * rtt + g->s.rtt.height/2.0;
                     e++;
 
+                    if (tcp_seq_eq_or_after(ackno, u->end_seqno)) {
+                        // fully acked segment - can safely be deleted
+                        v = u->next;
+                        rtt_delete_unack_from_list(&unack, u);
+                    } else {
+                        // partial ACK of GSO segment -
+                        //   just modify segment to reflect ACKed bytes
+                        u->seqno = ackno;
+                    }
+                } else {
+                    // nothing was acked in this seg - just move along
                     v = u->next;
-                    rtt_delete_unack_from_list(&unack, u);
-                } else
-                    v = u->next;
+                }
             }
         }
     }
+    // it's possible there's still unacked segs - so be sure to free list!
+    rtt_destroy_unack_list(&unack);
+
     e->type = ELMT_NONE;
     g->elists->elements = elements;
 }
diff --git a/ui/qt/tcp_stream_dialog.cpp b/ui/qt/tcp_stream_dialog.cpp
index 4230b3820f..8d785274ba 100644
--- a/ui/qt/tcp_stream_dialog.cpp
+++ b/ui/qt/tcp_stream_dialog.cpp
@@ -254,8 +254,13 @@ TCPStreamDialog::TCPStreamDialog(QWidget *parent, capture_file *cf, tcp_graph_ty
     tracer_ = new QCPItemTracer(sp);
     sp->addItem(tracer_);
 
-    // Triggers fillGraph().
-    ui->graphTypeComboBox->setCurrentIndex(graph_idx);
+    // Triggers fillGraph() [ UNLESS the index is already graph_idx!! ]
+    if (graph_idx != ui->graphTypeComboBox->currentIndex())
+        // changing the current index will call fillGraph
+        ui->graphTypeComboBox->setCurrentIndex(graph_idx);
+    else
+        // the current index is what we want - so fillGraph() manually
+        fillGraph();
 
     sp->setMouseTracking(true);
 
@@ -870,24 +875,109 @@ void TCPStreamDialog::fillThroughput()
     tput_graph_->setData(tput_time, tput);
 }
 
+// rtt_selectively_ack_range:
+//    "Helper" function for fillRoundTripTime
+//    given an rtt_unack list, two pointers to a range of segments in the list,
+//    and the [left,right) edges of a SACK block, selectively ACKs the range
+//    from "begin" to "end" - possibly splitting one segment in the range
+//    into two (and relinking the new segment in order after the first)
+//
+// Assumptions:
+//    "begin must be non-NULL
+//    "begin" must precede "end" (or "end" must be NULL)
+//    [ there are minor optimizations that could be added if
+//        the range from "begin" to "end" are in sequence number order.
+//        (this function would preserve that as an invariant). ]
+static struct rtt_unack *
+rtt_selectively_ack_range(QVector<double>& rel_times, QVector<double>& rtt,
+                    struct rtt_unack **list,
+                    struct rtt_unack *begin, struct rtt_unack *end,
+                    unsigned int left, unsigned int right, double rt_val) {
+    struct rtt_unack *cur, *next;
+    // sanity check:
+    if (tcp_seq_eq_or_after(left, right))
+        return begin;
+    // real work:
+    for (cur = begin; cur != end; cur = next) {
+        next = cur->next;
+        // check #1: does [left,right) intersect current unack at all?
+        //   (if not, we can just move on to the next unack)
+        if (tcp_seq_eq_or_after(cur->seqno, right) ||
+            tcp_seq_eq_or_after(left, cur->end_seqno)) {
+            // no intersection - just skip this.
+            continue;
+        }
+        // yes, we intersect!
+        int left_end_acked = tcp_seq_eq_or_after(cur->seqno, left);
+        int right_end_acked = tcp_seq_eq_or_after(right, cur->end_seqno);
+        // check #2 - did we fully ack the current unack?
+        //   (if so, we can delete it and move on)
+        if (left_end_acked && right_end_acked) {
+            // ACK the whole segment
+            rel_times.append(cur->time);
+            rtt.append((rt_val - cur->time) * 1000.0);
+            // in this case, we will delete current unack
+            // [ update "begin" if necessary - we will return it to the
+            //     caller to let them know we deleted it ]
+            if (cur == begin)
+                begin = next;
+             rtt_delete_unack_from_list(list, cur);
+             continue;
+        }
+        // check #3 - did we ACK the left-hand side of the current unack?
+        //   (if so, we can just modify it and move on)
+        if (left_end_acked) { // and right_end_not_acked
+            // ACK the left end
+            rel_times.append(cur->time);
+            rtt.append((rt_val - cur->time) * 1000.0);
+            // in this case, "right" marks the start of remaining bytes
+            cur->seqno = right;
+            continue;
+        }
+        // check #4 - did we ACK the right-hand side of the current unack?
+        //   (if so, we can just modify it and move on)
+        if (right_end_acked) { // and left_end_not_acked
+            // ACK the right end
+            rel_times.append(cur->time);
+            rtt.append((rt_val - cur->time) * 1000.0);
+            // in this case, "left" is just beyond the remaining bytes
+            cur->end_seqno = left;
+            continue;
+        }
+        // at this point, we know:
+        //   - the SACK block does intersect this unack, but
+        //   - it does not intersect the left or right endpoints
+        // Therefore, it must intersect the middle, so we must split the unack
+        //   into left and right unacked segments:
+        // ACK the SACK block
+        rel_times.append(cur->time);
+        rtt.append((rt_val - cur->time) * 1000.0);
+        // then split cur into two unacked segments
+        //   (linking the right-hand unack after the left)
+        cur->next = rtt_get_new_unack(cur->time, right, cur->end_seqno - right);
+        cur->next->next = next;
+        cur->end_seqno = left;
+    }
+    return begin;
+}
+
 void TCPStreamDialog::fillRoundTripTime()
 {
     QString dlg_title = QString(tr("Round Trip Time")) + streamDescription();
     setWindowTitle(dlg_title);
     title_->setText(dlg_title);
-    sequence_num_map_.clear();
 
     QCustomPlot *sp = ui->streamPlot;
-    sp->xAxis->setLabel(sequence_number_label_);
-    sp->xAxis->setNumberFormat("f");
-    sp->xAxis->setNumberPrecision(0);
+
     sp->yAxis->setLabel(round_trip_time_ms_label_);
+    sp->yAxis->setNumberFormat("gb");
+    sp->yAxis->setNumberPrecision(3);
 
     base_graph_->setLineStyle(QCPGraph::lsLine);
 
-    QVector<double> seq_no, rtt;
+    QVector<double> rel_times, rtt;
     guint32 seq_base = 0;
-    struct unack *unack = NULL, *u = NULL;
+    struct rtt_unack *unack_list = NULL, *u = NULL;
     for (struct segment *seg = graph_.segments; seg != NULL; seg = seg->next) {
         if (compareHeaders(seg)) {
             seq_base = seg->th_seq;
@@ -897,31 +987,59 @@ void TCPStreamDialog::fillRoundTripTime()
     for (struct segment *seg = graph_.segments; seg != NULL; seg = seg->next) {
         if (compareHeaders(seg)) {
             guint32 seqno = seg->th_seq - seq_base;
-            if (seg->th_seglen && !rtt_is_retrans(unack, seqno)) {
+            if (seg->th_seglen && !rtt_is_retrans(unack_list, seqno)) {
                 double rt_val = seg->rel_secs + seg->rel_usecs / 1000000.0;
-                u = rtt_get_new_unack(rt_val, seqno);
-                if (!u) return;
-                rtt_put_unack_on_list(&unack, u);
+                u = rtt_get_new_unack(rt_val, seqno, seg->th_seglen);
+                if (!u) {
+                    // make sure to free list before returning!
+                    rtt_destroy_unack_list(&unack_list);
+                    return;
+                }
+                rtt_put_unack_on_list(&unack_list, u);
             }
         } else {
             guint32 ack_no = seg->th_ack - seq_base;
             double rt_val = seg->rel_secs + seg->rel_usecs / 1000000.0;
-            struct unack *v;
+            struct rtt_unack *v;
 
-            for (u = unack; u; u = v) {
-                if (ack_no > u->seqno) {
-                    seq_no.append(u->seqno);
+            for (u = unack_list; u; u = v) {
+                if (tcp_seq_after(ack_no, u->seqno)) {
+                    // full or partial ack of seg by ack_no
+                    rel_times.append(u->time);
                     rtt.append((rt_val - u->time) * 1000.0);
-                    sequence_num_map_.insert(u->seqno, seg);
-                    v = u->next;
-                    rtt_delete_unack_from_list(&unack, u);
-                } else {
-                    v = u->next;
+                    if (tcp_seq_eq_or_after(ack_no, u->end_seqno)) {
+                        // fully acked segment - nothing more to see here
+                        v = u->next;
+                        rtt_delete_unack_from_list(&unack_list, u);
+                        // no need to compare SACK blocks for fully ACKed seg
+                        continue;
+                    } else {
+                        // partial ack of GSO seg
+                        u->seqno = ack_no;
+                        // (keep going - still need to compare SACK blocks...)
+                    }
+                }
+                v = u->next;
+                // selectively acking u more than once
+                //   can shatter it into multiple intervals.
+                //   If we link those back into the list between u and v,
+                //   then each subsequent SACK selectively ACKs that range.
+                for (int i = 0; i < seg->num_sack_ranges; ++i) {
+                    guint32 left = seg->sack_left_edge[i] - seq_base;
+                    guint32 right = seg->sack_right_edge[i] - seq_base;
+                    u = rtt_selectively_ack_range(rel_times, rtt,
+                                                  &unack_list, u, v,
+                                                  left, right, rt_val);
+                    // if range is empty after selective ack, we can
+                    //   skip the rest of the SACK blocks
+                    if (u == v) break;
                 }
             }
         }
     }
-    base_graph_->setData(seq_no, rtt);
+    // it's possible there's still unacked segs - so be sure to free list!
+    rtt_destroy_unack_list(&unack_list);
+    base_graph_->setData(rel_times, rtt);
 }
 
 void TCPStreamDialog::fillWindowScale()
@@ -1144,10 +1262,9 @@ void TCPStreamDialog::mouseMoved(QMouseEvent *event)
             case GRAPH_TSEQ_TCPTRACE:
             case GRAPH_THROUGHPUT:
             case GRAPH_WSCALE:
+            case GRAPH_RTT:
                 packet_seg = time_stamp_map_.value(tr_key, NULL);
                 break;
-            case GRAPH_RTT:
-                packet_seg = sequence_num_map_.value(tr_key, NULL);
             default:
                 break;
             }
diff --git a/ui/qt/tcp_stream_dialog.h b/ui/qt/tcp_stream_dialog.h
index 012b865d81..e313056c8e 100644
--- a/ui/qt/tcp_stream_dialog.h
+++ b/ui/qt/tcp_stream_dialog.h
@@ -68,7 +68,6 @@ private:
     QMap<double, struct segment *> time_stamp_map_;
     double ts_offset_;
     bool ts_origin_conn_;
-    QMap<double, struct segment *> sequence_num_map_;
     double seq_offset_;
     bool seq_origin_zero_;
     struct tcp_graph graph_;
diff --git a/ui/tap-tcp-stream.c b/ui/tap-tcp-stream.c
index abf357683d..44115aa99f 100644
--- a/ui/tap-tcp-stream.c
+++ b/ui/tap-tcp-stream.c
@@ -364,31 +364,34 @@ select_tcpip_session(capture_file *cf, struct segment *hdrs)
     return th.tcphdrs[0];
 }
 
-int rtt_is_retrans(struct unack *list, unsigned int seqno)
+int rtt_is_retrans(struct rtt_unack *list, unsigned int seqno)
 {
-    struct unack *u;
+    struct rtt_unack *u;
 
     for (u=list; u; u=u->next) {
-        if (u->seqno == seqno)
+        if (tcp_seq_eq_or_after(seqno, u->seqno) &&
+            tcp_seq_before(seqno, u->end_seqno))
             return TRUE;
     }
     return FALSE;
 }
 
-struct unack *rtt_get_new_unack(double time_val, unsigned int seqno)
+struct rtt_unack *
+rtt_get_new_unack(double time_val, unsigned int seqno, unsigned int seglen)
 {
-    struct unack *u;
+    struct rtt_unack *u;
 
-    u = (struct unack * )g_malloc(sizeof(struct unack));
+    u = (struct rtt_unack * )g_malloc(sizeof(struct rtt_unack));
     u->next  = NULL;
     u->time  = time_val;
     u->seqno = seqno;
+    u->end_seqno = seqno + seglen;
     return u;
 }
 
-void rtt_put_unack_on_list(struct unack **l, struct unack *new_unack)
+void rtt_put_unack_on_list(struct rtt_unack **l, struct rtt_unack *new_unack)
 {
-    struct unack *u, *list = *l;
+    struct rtt_unack *u, *list = *l;
 
     for (u=list; u; u=u->next) {
         if (!u->next)
@@ -400,9 +403,9 @@ void rtt_put_unack_on_list(struct unack **l, struct unack *new_unack)
         *l = new_unack;
 }
 
-void rtt_delete_unack_from_list(struct unack **l, struct unack *dead)
+void rtt_delete_unack_from_list(struct rtt_unack **l, struct rtt_unack *dead)
 {
-    struct unack *u, *list = *l;
+    struct rtt_unack *u, *list = *l;
 
     if (!dead || !list)
         return;
@@ -421,6 +424,14 @@ void rtt_delete_unack_from_list(struct unack **l, struct unack *dead)
     }
 }
 
+void rtt_destroy_unack_list(struct rtt_unack **l ) {
+    while (*l) {
+        struct rtt_unack *head = *l;
+        *l = head->next;
+        g_free(head);
+    }
+}
+
 /*
  * Editor modelines
  *
diff --git a/ui/tap-tcp-stream.h b/ui/tap-tcp-stream.h
index 360f4af016..a29e04dedc 100644
--- a/ui/tap-tcp-stream.h
+++ b/ui/tap-tcp-stream.h
@@ -103,16 +103,33 @@ int get_num_acks(struct tcp_graph *, int * );
 struct tcpheader *select_tcpip_session(capture_file *, struct segment * );
 
 /* This is used by rtt module only */
-struct unack {
-    struct unack *next;
+struct rtt_unack {
+    struct rtt_unack *next;
     double        time;
     unsigned int  seqno;
+    unsigned int  end_seqno;
 };
 
-int rtt_is_retrans(struct unack * , unsigned int );
-struct unack *rtt_get_new_unack(double , unsigned int );
-void rtt_put_unack_on_list(struct unack ** , struct unack * );
-void rtt_delete_unack_from_list(struct unack ** , struct unack * );
+int rtt_is_retrans(struct rtt_unack * , unsigned int );
+struct rtt_unack *rtt_get_new_unack(double , unsigned int , unsigned int );
+void rtt_put_unack_on_list(struct rtt_unack ** , struct rtt_unack * );
+void rtt_delete_unack_from_list(struct rtt_unack ** , struct rtt_unack * );
+void rtt_destroy_unack_list(struct rtt_unack ** );
+
+static inline int
+tcp_seq_before(guint32 s1, guint32 s2) {
+    return (gint32)(s1 - s2) < 0;
+}
+
+static inline int
+tcp_seq_eq_or_after(guint32 s1, guint32 s2) {
+    return !tcp_seq_before(s1, s2);
+}
+
+static inline int
+tcp_seq_after(guint32 s1, guint32 s2) {
+    return (s1 != s2) && !tcp_seq_before(s1, s2);
+}
 
 static inline int
 tcp_seq_before(guint32 s1, guint32 s2) {