From 73b5e3d0082cc7ca65e5a085bd80264e5a0b1082 Mon Sep 17 00:00:00 2001 From: Kevin Hogan Date: Tue, 17 Jan 2017 20:30:26 -0800 Subject: 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 Tested-by: Petri Dish Buildbot Reviewed-by: Alexis La Goutte Reviewed-by: Anders Broman --- ui/gtk/tcp_graph.c | 55 ++++++++++----- ui/qt/tcp_stream_dialog.cpp | 165 +++++++++++++++++++++++++++++++++++++------- ui/qt/tcp_stream_dialog.h | 1 - ui/tap-tcp-stream.c | 31 ++++++--- ui/tap-tcp-stream.h | 29 ++++++-- 5 files changed, 224 insertions(+), 57 deletions(-) (limited to 'ui') 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& rel_times, QVector& 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 seq_no, rtt; + QVector 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 time_stamp_map_; double ts_offset_; bool ts_origin_conn_; - QMap 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) { -- cgit v1.2.1