Follow Stream: ensure linear performance with many packets

Reverse the payload chunks list to achieve a running time of O(n) rather
than O(n²) for insertion of all chunks. Executing a RelWithDebInfo+ASAN
build with `tshark -r chargen-session.pcapng.gz -qz follow,tcp,hex,0`
previously took 11m5s to complete, but now finishes in 16 seconds.

Tested using a capture file with 152k TCP packets (from bug 11777).
Backport note: must update ui/gtk/follow_stream.c too.

Change-Id: Icf70d45f33d4399e53209fb6199d3809608c8d99
Reviewed-on: https://code.wireshark.org/review/28595
Petri-Dish: Peter Wu <peter@lekensteyn.nl>
Tested-by: Petri Dish Buildbot
Reviewed-by: Anders Broman <a.broman58@gmail.com>

diff --git a/epan/dissectors/packet-ssl.c b/epan/dissectors/packet-ssl.c
index ec98259155722d720932a9bfee1f7dc7395f8b3f..77413fcd4784a78212ad8de815c490dd70a78c24 100644 (file)
--- a/epan/dissectors/packet-ssl.c
+++ b/epan/dissectors/packet-ssl.c
@@ -514,8 +514,8 @@ ssl_follow_tap_listener(void *tapdata, packet_info *pinfo, epan_dissect_t *edt _
                                               appl_data->plain_data,
                                               appl_data->data_len);
 
-        /* Append the record to the follow_info structure. */
-        follow_info->payload = g_list_append(follow_info->payload, follow_record);
+        /* Add the record to the follow_info structure. */
+        follow_info->payload = g_list_prepend(follow_info->payload, follow_record);
         follow_info->bytes_written[from] += appl_data->data_len;
     }
 

diff --git a/epan/dissectors/packet-tcp.c b/epan/dissectors/packet-tcp.c
index fa3abaee6b7d5937101e6683788742f688ba3989..db1281aa0bc5d0b2ec9522927abd5b8e4bbcce4e 100644 (file)
--- a/epan/dissectors/packet-tcp.c
+++ b/epan/dissectors/packet-tcp.c
@@ -1001,7 +1001,7 @@ check_follow_fragments(follow_info_t *follow_info, gboolean is_server, guint32 a
                                                               fragment->data->data + new_pos,
                                                               new_frag_size);
 
-                    follow_info->payload = g_list_append(follow_info->payload, follow_record);
+                    follow_info->payload = g_list_prepend(follow_info->payload, follow_record);
                 }
 
                 follow_info->seq[is_server] += (fragment->data->len - new_pos);
@@ -1019,7 +1019,7 @@ check_follow_fragments(follow_info_t *follow_info, gboolean is_server, guint32 a
         if( EQ_SEQ(fragment->seq, follow_info->seq[is_server]) ) {
             /* this fragment fits the stream */
             if( fragment->data->len > 0 ) {
-                follow_info->payload = g_list_append(follow_info->payload, fragment);
+                follow_info->payload = g_list_prepend(follow_info->payload, fragment);
             }
 
             follow_info->seq[is_server] += fragment->data->len;
@@ -1047,7 +1047,7 @@ check_follow_fragments(follow_info_t *follow_info, gboolean is_server, guint32 a
         follow_record->seq = lowest_seq;
 
         follow_info->seq[is_server] = lowest_seq;
-        follow_info->payload = g_list_append(follow_info->payload, follow_record);
+        follow_info->payload = g_list_prepend(follow_info->payload, follow_record);
         return TRUE;
     }
 
@@ -1094,7 +1094,7 @@ follow_tcp_tap_listener(void *tapdata, packet_info *pinfo,
             follow_info->seq[follow_record->is_server]++;
 
         follow_info->bytes_written[follow_record->is_server] += follow_record->data->len;
-        follow_info->payload = g_list_append(follow_info->payload, follow_record);
+        follow_info->payload = g_list_prepend(follow_info->payload, follow_record);
         return FALSE;
     }
 
@@ -1141,7 +1141,7 @@ follow_tcp_tap_listener(void *tapdata, packet_info *pinfo,
             follow_info->seq[follow_record->is_server]++;
         if (data_length > 0) {
             follow_info->bytes_written[follow_record->is_server] += follow_record->data->len;
-            follow_info->payload = g_list_append(follow_info->payload, follow_record);
+            follow_info->payload = g_list_prepend(follow_info->payload, follow_record);
             added_follow_record = TRUE;
         }
 

diff --git a/epan/follow.c b/epan/follow.c
index 22d756799aef08fa0afba9ca4619bf59fe3e8ec0..cf3d12cb6dd648f50e0066fd2abab1c5f7c07345 100644 (file)
--- a/epan/follow.c
+++ b/epan/follow.c
@@ -142,7 +142,7 @@ follow_info_free(follow_info_t* follow_info)
     GList *cur;
     follow_record_t *follow_record;
 
-    for(cur = follow_info->payload; cur; cur = g_list_next(cur)) {
+    for (cur = follow_info->payload; cur; cur = g_list_next(cur)) {
         if(cur->data) {
             follow_record = (follow_record_t *)cur->data;
             if(follow_record->data)
@@ -206,7 +206,7 @@ follow_tvb_tap_listener(void *tapdata, packet_info *pinfo,
     /* update stream counter */
     follow_info->bytes_written[follow_record->is_server] += follow_record->data->len;
 
-    follow_info->payload = g_list_append(follow_info->payload, follow_record);
+    follow_info->payload = g_list_prepend(follow_info->payload, follow_record);
     return FALSE;
 }
 

diff --git a/epan/follow.h b/epan/follow.h
index e3301fee24fce1044747f6a4a5a1844a162867cd..99b2050a8a1af146bc78b1ca5fab43435fd3bf9c 100644 (file)
--- a/epan/follow.h
+++ b/epan/follow.h
@@ -84,7 +84,7 @@ typedef struct {
 typedef struct _follow_info {
     show_stream_t   show_stream;
     char            *filter_out_filter;
-    GList           *payload;
+    GList           *payload;   /* "follow_record_t" entries, in reverse order. */
     guint           bytes_written[2]; /* Index with FROM_CLIENT or FROM_SERVER for readability. */
     guint32         seq[2]; /* TCP only */
     GList           *fragments[2]; /* TCP only */

diff --git a/sharkd_session.c b/sharkd_session.c
index 2a77168870a86704f55e927c02cf5304d6faeffa..f2538f15fdf127ae9ede95a2e6e501a5f65f3e3c 100644 (file)
--- a/sharkd_session.c
+++ b/sharkd_session.c
@@ -2564,7 +2564,7 @@ sharkd_session_process_follow(char *buf, const jsmntok_t *tokens, int count)
 
                printf(",\"payloads\":[");
 
-               for (cur = follow_info->payload; cur; cur = g_list_next(cur))
+               for (cur = g_list_last(follow_info->payload); cur; cur = g_list_previous(cur))
                {
                        follow_record = (follow_record_t *) cur->data;
 

diff --git a/ui/cli/tap-follow.c b/ui/cli/tap-follow.c
index e00cdcd2172d728de5c071198c0bc1eb35116064..f1a574224dcae1aa7696011aa64a0bea787c42cc 100644 (file)
--- a/ui/cli/tap-follow.c
+++ b/ui/cli/tap-follow.c
@@ -184,9 +184,9 @@ static void follow_draw(void *contextp)
   else
     printf("Node 1: %s:%u\n", buf, follow_info->server_port);
 
-  for (cur = follow_info->payload, chunk = 1;
+  for (cur = g_list_last(follow_info->payload), chunk = 1;
        cur != NULL;
-       cur = g_list_next(cur), chunk++)
+       cur = g_list_previous(cur), chunk++)
   {
     follow_record = (follow_record_t *)cur->data;
     if (!follow_record->is_server) {

diff --git a/ui/qt/follow_stream_dialog.cpp b/ui/qt/follow_stream_dialog.cpp
index a43b3827251cadf169035b8fbee774fd25046593..7f79e6a67ee610f1990f6dcd279c0ff26c87c5bd 100644 (file)
--- a/ui/qt/follow_stream_dialog.cpp
+++ b/ui/qt/follow_stream_dialog.cpp
@@ -1004,7 +1004,7 @@ FollowStreamDialog::readFollowStream()
 
     elapsed_timer.start();
 
-    for (cur = follow_info_.payload; cur; cur = g_list_next(cur)) {
+    for (cur = g_list_last(follow_info_.payload); cur; cur = g_list_previous(cur)) {
         if (dialogClosed()) break;
 
         follow_record = (follow_record_t *)cur->data;