Patricia tree, Ahocarasick automa, LRU cache: add statistics (#1683)

Add (basic) internal stats to the main data structures used by the
library; they might be usefull to check how effective these structures
are.

Add an option to `ndpiReader` to dump them; enabled by default in the
unit tests.
This new option enables/disables dumping of "num dissectors calls"
values, too (see b4cb14ec).

1 files changed, 141 insertions, 9 deletions

diff --git a/example/ndpiReader.c b/example/ndpiReader.c
index de1c9325f..930220801 100644
--- a/example/ndpiReader.c
+++ b/example/ndpiReader.c
@@ -123,6 +123,7 @@ extern u_int8_t enable_doh_dot_detection, enable_ja3_plus;
 extern u_int32_t max_num_packets_per_flow, max_packet_payload_dissection, max_num_reported_top_payloads;
 extern u_int16_t min_pattern_len, max_pattern_len;
 extern void ndpi_self_check_host_match(); /* Self check function */
+u_int8_t dump_internal_stats;
 
 struct flow_info {
   struct ndpi_flow_info *flow;
@@ -501,6 +502,7 @@ static void help(u_int long_help) {
          "  -x <domain>               | Check domain name [Test only]\n"
          "  -I                        | Ignore VLAN id for flow hash calculation\n"
          "  -z                        | Enable JA3+\n"
+         "  -A                        | Dump internal statistics (LRU caches / Patricia trees / Ahocarasick automas / ...\n"
          ,
          human_readeable_string_len,
          min_pattern_len, max_pattern_len, max_num_packets_per_flow, max_packet_payload_dissection,
@@ -798,7 +800,7 @@ static void parseOptions(int argc, char **argv) {
   }
 #endif
 
-  while((opt = getopt_long(argc, argv, "a:b:e:c:C:dDf:g:i:Ij:k:K:S:hHp:pP:l:r:s:tu:v:V:n:Jrp:x:w:zq0123:456:7:89:m:T:U:",
+  while((opt = getopt_long(argc, argv, "a:Ab:e:c:C:dDf:g:i:Ij:k:K:S:hHp:pP:l:r:s:tu:v:V:n:Jrp:x:w:zq0123:456:7:89:m:T:U:",
                            longopts, &option_idx)) != EOF) {
 #ifdef DEBUG_TRACE
     if(trace) fprintf(trace, " #### Handling option -%c [%s] #### \n", opt, optarg ? optarg : "");
@@ -809,6 +811,10 @@ static void parseOptions(int argc, char **argv) {
       ndpi_generate_options(atoi(optarg));
       break;
 
+    case 'A':
+      dump_internal_stats = 1;
+      break;
+
     case 'b':
       if((num_bin_clusters = atoi(optarg)) > 32)
         num_bin_clusters = 32;
@@ -3491,6 +3497,18 @@ static void printResults(u_int64_t processing_time_usec, u_int64_t setup_time_us
       cumulative_stats.flow_confidence[i] += ndpi_thread_info[thread_id].workflow->stats.flow_confidence[i];
 
     cumulative_stats.num_dissector_calls += ndpi_thread_info[thread_id].workflow->stats.num_dissector_calls;
+
+    /* LRU caches */
+    for(i = 0; i < NDPI_LRUCACHE_MAX; i++)
+      ndpi_get_lru_cache_stats(ndpi_thread_info[thread_id].workflow->ndpi_struct, i, &cumulative_stats.lru_stats[i]);
+
+    /* Automas */
+    for(i = 0; i < NDPI_AUTOMA_MAX; i++)
+      ndpi_get_automa_stats(ndpi_thread_info[thread_id].workflow->ndpi_struct, i, &cumulative_stats.automa_stats[i]);
+
+    /* Patricia trees */
+    for(i = 0; i < NDPI_PTREE_MAX; i++)
+      ndpi_get_patricia_stats(ndpi_thread_info[thread_id].workflow->ndpi_struct, i, &cumulative_stats.patricia_stats[i]);
   }
 
   if(cumulative_stats.total_wire_bytes == 0)
@@ -3599,10 +3617,67 @@ static void printResults(u_int64_t processing_time_usec, u_int64_t setup_time_us
 		 (long long unsigned int)cumulative_stats.flow_confidence[i]);
       }
 
-      if(cumulative_stats.ndpi_flow_count)
-	printf("\tNum dissector calls:   %-13llu (%.2f diss/flow)\n",
-	       (long long unsigned int)cumulative_stats.num_dissector_calls,
-	       cumulative_stats.num_dissector_calls / (float)cumulative_stats.ndpi_flow_count);
+      if(dump_internal_stats) {
+	if(cumulative_stats.ndpi_flow_count)
+	  printf("\tNum dissector calls:   %-13llu (%.2f diss/flow)\n",
+	         (long long unsigned int)cumulative_stats.num_dissector_calls,
+	         cumulative_stats.num_dissector_calls / (float)cumulative_stats.ndpi_flow_count);
+
+	printf("\tLRU cache ookla:      %llu/%llu/%llu (insert/search/found)\n",
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_OOKLA].n_insert,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_OOKLA].n_search,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_OOKLA].n_found);
+	printf("\tLRU cache bittorrent: %llu/%llu/%llu (insert/search/found)\n",
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_BITTORRENT].n_insert,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_BITTORRENT].n_search,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_BITTORRENT].n_found);
+	printf("\tLRU cache zoom:       %llu/%llu/%llu (insert/search/found)\n",
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_ZOOM].n_insert,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_ZOOM].n_search,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_ZOOM].n_found);
+	printf("\tLRU cache stun:       %llu/%llu/%llu (insert/search/found)\n",
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_STUN].n_insert,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_STUN].n_search,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_STUN].n_found);
+	printf("\tLRU cache tls_cert:   %llu/%llu/%llu (insert/search/found)\n",
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_TLS_CERT].n_insert,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_TLS_CERT].n_search,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_TLS_CERT].n_found);
+	printf("\tLRU cache mining:     %llu/%llu/%llu (insert/search/found)\n",
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MINING].n_insert,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MINING].n_search,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MINING].n_found);
+	printf("\tLRU cache msteams:    %llu/%llu/%llu (insert/search/found)\n",
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MSTEAMS].n_insert,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MSTEAMS].n_search,
+	       (long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MSTEAMS].n_found);
+
+	printf("\tAutoma host:          %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_HOST].n_search,
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_HOST].n_found);
+	printf("\tAutoma domain:        %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_DOMAIN].n_search,
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_DOMAIN].n_found);
+	printf("\tAutoma tls cert:      %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_TLS_CERT].n_search,
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_TLS_CERT].n_found);
+	printf("\tAutoma risk mask:     %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_RISK_MASK].n_search,
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_RISK_MASK].n_found);
+	printf("\tAutoma common alpns:  %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_COMMON_ALPNS].n_search,
+	       (long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_COMMON_ALPNS].n_found);
+
+	printf("\tPatricia risk mask:   %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK_MASK].n_search,
+	       (long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK_MASK].n_found);
+	printf("\tPatricia risk:        %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK].n_search,
+	       (long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK].n_found);
+	printf("\tPatricia protocols:   %llu/%llu (search/found)\n",
+	       (long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_PROTOCOLS].n_search,
+	       (long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_PROTOCOLS].n_found);
+      }
     }
 
     if(results_file) {
@@ -3629,10 +3704,67 @@ static void printResults(u_int64_t processing_time_usec, u_int64_t setup_time_us
 		  (long long unsigned int)cumulative_stats.flow_confidence[i]);
       }
 
-      if(cumulative_stats.ndpi_flow_count)
-	fprintf(results_file, "Num dissector calls: %llu (%.2f diss/flow)\n",
-	        (long long unsigned int)cumulative_stats.num_dissector_calls,
-	        cumulative_stats.num_dissector_calls / (float)cumulative_stats.ndpi_flow_count);
+      if(dump_internal_stats) {
+	if(cumulative_stats.ndpi_flow_count)
+	  fprintf(results_file, "Num dissector calls: %llu (%.2f diss/flow)\n",
+	          (long long unsigned int)cumulative_stats.num_dissector_calls,
+	          cumulative_stats.num_dissector_calls / (float)cumulative_stats.ndpi_flow_count);
+
+	fprintf(results_file, "LRU cache ookla:      %llu/%llu/%llu (insert/search/found)\n",
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_OOKLA].n_insert,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_OOKLA].n_search,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_OOKLA].n_found);
+	fprintf(results_file, "LRU cache bittorrent: %llu/%llu/%llu (insert/search/found)\n",
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_BITTORRENT].n_insert,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_BITTORRENT].n_search,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_BITTORRENT].n_found);
+	fprintf(results_file, "LRU cache zoom:       %llu/%llu/%llu (insert/search/found)\n",
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_ZOOM].n_insert,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_ZOOM].n_search,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_ZOOM].n_found);
+	fprintf(results_file, "LRU cache stun:       %llu/%llu/%llu (insert/search/found)\n",
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_STUN].n_insert,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_STUN].n_search,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_STUN].n_found);
+	fprintf(results_file, "LRU cache tls_cert:   %llu/%llu/%llu (insert/search/found)\n",
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_TLS_CERT].n_insert,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_TLS_CERT].n_search,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_TLS_CERT].n_found);
+	fprintf(results_file, "LRU cache mining:     %llu/%llu/%llu (insert/search/found)\n",
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MINING].n_insert,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MINING].n_search,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MINING].n_found);
+	fprintf(results_file, "LRU cache msteams:    %llu/%llu/%llu (insert/search/found)\n",
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MSTEAMS].n_insert,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MSTEAMS].n_search,
+		(long long unsigned int)cumulative_stats.lru_stats[NDPI_LRUCACHE_MSTEAMS].n_found);
+
+	fprintf(results_file, "Automa host:          %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_HOST].n_search,
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_HOST].n_found);
+	fprintf(results_file, "Automa domain:        %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_DOMAIN].n_search,
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_DOMAIN].n_found);
+	fprintf(results_file, "Automa tls cert:      %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_TLS_CERT].n_search,
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_TLS_CERT].n_found);
+	fprintf(results_file, "Automa risk mask:     %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_RISK_MASK].n_search,
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_RISK_MASK].n_found);
+	fprintf(results_file, "Automa common alpns:  %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_COMMON_ALPNS].n_search,
+		(long long unsigned int)cumulative_stats.automa_stats[NDPI_AUTOMA_COMMON_ALPNS].n_found);
+
+	fprintf(results_file, "Patricia risk mask:   %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK_MASK].n_search,
+		(long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK_MASK].n_found);
+	fprintf(results_file, "Patricia risk:        %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK].n_search,
+		(long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_RISK].n_found);
+	fprintf(results_file, "Patricia protocols:   %llu/%llu (search/found)\n",
+		(long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_PROTOCOLS].n_search,
+		(long long unsigned int)cumulative_stats.patricia_stats[NDPI_PTREE_PROTOCOLS].n_found);
+      }
 
       fprintf(results_file, "\n");
   }