Added Ookla cache

8 files changed, 452 insertions, 15 deletions

diff --git a/src/include/ndpi_protocols.h b/src/include/ndpi_protocols.h
index 8ac7d7247..5349237d4 100644
--- a/src/include/ndpi_protocols.h
+++ b/src/include/ndpi_protocols.h
@@ -362,4 +362,5 @@ void init_ajp_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int3
 void init_fbzero_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
 void init_memcached_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
 void init_nest_log_sink_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
+void init_ookla_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
 #endif /* __NDPI_PROTOCOLS_H__ */
diff --git a/src/include/ndpi_typedefs.h b/src/include/ndpi_typedefs.h
index d48453baf..294af22b3 100644
--- a/src/include/ndpi_typedefs.h
+++ b/src/include/ndpi_typedefs.h
@@ -996,7 +996,10 @@ struct ndpi_detection_module_struct {
   struct bt_announce *bt_ann;
   int    bt_ann_len;
 
-/* NDPI_PROTOCOL_TINC */
+  /* NDPI_PROTOCOL_OOKLA */
+  void *ookla_cache;
+
+  /* NDPI_PROTOCOL_TINC */
   struct cache *tinc_cache;
 
   ndpi_proto_defaults_t proto_defaults[NDPI_MAX_SUPPORTED_PROTOCOLS+NDPI_MAX_NUM_CUSTOM_PROTOCOLS];
diff --git a/src/lib/ndpi_main.c b/src/lib/ndpi_main.c
index b5b3c9c6b..e882feaa6 100644
--- a/src/lib/ndpi_main.c
+++ b/src/lib/ndpi_main.c
@@ -30,6 +30,7 @@
 #include <sys/types.h>
 #include "ahocorasick.h"
 #include "libcache.h"
+#include "lruc.h"
 
 #define NDPI_CURRENT_PROTO NDPI_PROTOCOL_UNKNOWN
 
@@ -2427,14 +2428,16 @@ void ndpi_exit_detection_module(struct ndpi_detection_module_struct *ndpi_struct
 	ndpi_free(ndpi_struct->proto_defaults[i].protoName);
     }
 
-/* NDPI_PROTOCOL_TINC */
+    /* NDPI_PROTOCOL_TINC */
     if(ndpi_struct->tinc_cache)
       cache_free((cache_t)(ndpi_struct->tinc_cache));
 
-    if(ndpi_struct->protocols_ptree)
-      ndpi_Destroy_Patricia((patricia_tree_t*)ndpi_struct->protocols_ptree,
-      free_ptree_data);
+    if(ndpi_struct->ookla_cache)
+      lruc_free((lruc*)ndpi_struct->ookla_cache);
 
+    if(ndpi_struct->protocols_ptree)
+      ndpi_Destroy_Patricia((patricia_tree_t*)ndpi_struct->protocols_ptree, free_ptree_data);
+    
     if(ndpi_struct->udpRoot != NULL)
       ndpi_tdestroy(ndpi_struct->udpRoot, ndpi_free);
     if(ndpi_struct->tcpRoot != NULL)
@@ -3293,6 +3296,9 @@ void ndpi_set_protocol_detection_bitmask2(struct ndpi_detection_module_struct *n
   /* WHATSAPP */
   init_whatsapp_dissector(ndpi_struct, &a, detection_bitmask);
 
+  /* OOKLA */
+  init_ookla_dissector(ndpi_struct, &a, detection_bitmask);
+
   /* AMQP */
   init_amqp_dissector(ndpi_struct, &a, detection_bitmask);
 
diff --git a/src/lib/protocols/http.c b/src/lib/protocols/http.c
index 94d918e76..09b816129 100644
--- a/src/lib/protocols/http.c
+++ b/src/lib/protocols/http.c
@@ -26,7 +26,7 @@
 #define NDPI_CURRENT_PROTO NDPI_PROTOCOL_HTTP
 
 #include "ndpi_api.h"
-
+#include "lruc.h"
 
 /* global variables used for 1kxun protocol and iqiyi service */
 
@@ -613,7 +613,23 @@ static void ndpi_check_http_tcp(struct ndpi_detection_module_struct *ndpi_struct
           <allow-access-from domain="*.speedtest.net" to-ports="8080"/>
           </cross-domain-policy>
         */
+      ookla_found:
         ndpi_set_detected_protocol(ndpi_struct, flow, NDPI_PROTOCOL_OOKLA, NDPI_PROTOCOL_UNKNOWN);
+
+	if(ndpi_struct->ookla_cache == NULL)
+	  ndpi_struct->ookla_cache = lruc_new(4*1024, 1024);	 	
+	
+	if(ndpi_struct->ookla_cache != NULL) {
+	  u_int8_t *dummy = (u_int8_t*)ndpi_malloc(sizeof(u_int8_t));
+
+	  if(dummy) {
+	    if(packet->tcp->source == htons(8080))
+	      lruc_set((lruc*)ndpi_struct->ookla_cache, (void*)&packet->iph->saddr, 4, dummy, 1);
+	    else
+	      lruc_set((lruc*)ndpi_struct->ookla_cache, (void*)&packet->iph->daddr, 4, dummy, 1);
+	  }
+	}
+	
         return;
       }
       
@@ -663,9 +679,8 @@ static void ndpi_check_http_tcp(struct ndpi_detection_module_struct *ndpi_struct
 
       /* Check for Ookla */
       if((packet->referer_line.len > 0)
-	      && ndpi_strnstr((const char *)packet->referer_line.ptr, "www.speedtest.net", packet->referer_line.len)) {
-	    ndpi_set_detected_protocol(ndpi_struct, flow, NDPI_PROTOCOL_OOKLA, NDPI_PROTOCOL_HTTP);
-	    return;
+	 && ndpi_strnstr((const char *)packet->referer_line.ptr, "www.speedtest.net", packet->referer_line.len)) {
+	goto ookla_found;
       }
 
       /* Check for additional field introduced by Steam */
@@ -782,17 +797,15 @@ static void ndpi_check_http_tcp(struct ndpi_detection_module_struct *ndpi_struct
     
     if((packet->payload_packet_len == 34) && (flow->l4.tcp.http_stage == 1)) {
       if((packet->payload[5] == ' ') && (packet->payload[9] == ' ')) {
-	      ndpi_int_http_add_connection(ndpi_struct, flow, NDPI_PROTOCOL_OOKLA);
-	      return;
+	goto ookla_found;
       }
     }
     
     if((packet->payload_packet_len > 6) && memcmp(packet->payload, "HELLO ", 6) == 0) {
        /* This looks like Ookla */
-      ndpi_set_detected_protocol(ndpi_struct, flow, NDPI_PROTOCOL_OOKLA, NDPI_PROTOCOL_UNKNOWN);
-      return;
+      goto ookla_found;
     } else
-	    NDPI_ADD_PROTOCOL_TO_BITMASK(flow->excluded_protocol_bitmask, NDPI_PROTOCOL_OOKLA);    
+      NDPI_ADD_PROTOCOL_TO_BITMASK(flow->excluded_protocol_bitmask, NDPI_PROTOCOL_OOKLA);    
     
     /**
        At first check, if this is for sure a response packet (in another direction. If not, if HTTP is detected do nothing now and return,
diff --git a/src/lib/protocols/ookla.c b/src/lib/protocols/ookla.c
new file mode 100644
index 000000000..b1eb295a7
--- /dev/null
+++ b/src/lib/protocols/ookla.c
@@ -0,0 +1,66 @@
+/*
+ * ookla.c
+ *
+ * Copyright (C) 2018 - ntop.org
+ *
+ * nDPI is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * nDPI is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with nDPI.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+#include "ndpi_protocol_ids.h"
+
+#define NDPI_CURRENT_PROTO NDPI_PROTOCOL_OOKLA
+
+#include "ndpi_api.h"
+#include "lruc.h"
+
+
+void ndpi_search_ookla(struct ndpi_detection_module_struct* ndpi_struct, struct ndpi_flow_struct* flow) {
+  struct ndpi_packet_struct* packet = &flow->packet;
+  u_int32_t addr = 0;
+  void *value;
+  
+  NDPI_LOG_DBG(ndpi_struct, "Ookla detection\n");
+  
+  if(packet->tcp->source == htons(8080))
+    addr = packet->iph->saddr;
+  else if(packet->tcp->dest == htons(8080))
+    addr = packet->iph->daddr;
+  else
+    goto ookla_exclude;
+  
+  if(ndpi_struct->ookla_cache != NULL) {
+    if(lruc_get(ndpi_struct->ookla_cache, &addr, sizeof(addr), &value) == LRUC_NO_ERROR) {
+      /* Don't remove it as it can be used for other connections */
+      NDPI_LOG_INFO(ndpi_struct, "found ookla tcp connection\n");
+      ndpi_set_detected_protocol(ndpi_struct, flow, NDPI_PROTOCOL_OOKLA, NDPI_PROTOCOL_UNKNOWN);
+      return;
+    }	
+  }
+
+ ookla_exclude:
+  NDPI_EXCLUDE_PROTO(ndpi_struct, flow);  
+}
+
+void init_ookla_dissector(struct ndpi_detection_module_struct *ndpi_struct,
+			  u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask) {
+  ndpi_set_bitmask_protocol_detection("Ookla", ndpi_struct, detection_bitmask, *id,
+				      NDPI_PROTOCOL_OOKLA,
+				      ndpi_search_ookla,
+				      NDPI_SELECTION_BITMASK_PROTOCOL_TCP,
+				      SAVE_DETECTION_BITMASK_AS_UNKNOWN,
+				      ADD_TO_DETECTION_BITMASK);
+
+  *id += 1;
+}
+
diff --git a/src/lib/protocols/snmp_proto.c b/src/lib/protocols/snmp_proto.c
index 759d6bae0..77ad4d233 100644
--- a/src/lib/protocols/snmp_proto.c
+++ b/src/lib/protocols/snmp_proto.c
@@ -123,7 +123,6 @@ void ndpi_search_snmp(struct ndpi_detection_module_struct *ndpi_struct, struct n
   }
  excl:
   NDPI_EXCLUDE_PROTO(ndpi_struct, flow);
-
 }
 
 
diff --git a/src/lib/third_party/include/lruc.h b/src/lib/third_party/include/lruc.h
new file mode 100644
index 000000000..55fb271fe
--- /dev/null
+++ b/src/lib/third_party/include/lruc.h
@@ -0,0 +1,55 @@
+#include <pthread.h>
+#include <stdint.h>
+#include <time.h>
+
+#ifndef __lruc_header__
+#define __lruc_header__
+
+// ------------------------------------------
+// errors
+// ------------------------------------------
+typedef enum {
+  LRUC_NO_ERROR = 0,
+  LRUC_MISSING_CACHE,
+  LRUC_MISSING_KEY,
+  LRUC_MISSING_VALUE,
+  LRUC_PTHREAD_ERROR,
+  LRUC_VALUE_TOO_LARGE
+} lruc_error;
+
+
+// ------------------------------------------
+// types
+// ------------------------------------------
+typedef struct {
+  void      *value;
+  void      *key;
+  uint32_t  value_length;
+  uint32_t  key_length;
+  uint64_t  access_count;
+  void      *next;
+} lruc_item;
+
+typedef struct {
+  lruc_item **items;
+  uint64_t  access_count;
+  uint64_t  free_memory;
+  uint64_t  total_memory;
+  uint64_t  average_item_length;
+  uint32_t  hash_table_size;
+  time_t    seed;
+  lruc_item *free_items;
+  pthread_mutex_t *mutex;
+} lruc;
+
+
+// ------------------------------------------
+// api
+// ------------------------------------------
+lruc *lruc_new(uint64_t cache_size, uint32_t average_length);
+lruc_error lruc_free(lruc *cache);
+lruc_error lruc_set(lruc *cache, void *key, uint32_t key_length, void *value, uint32_t value_length);
+lruc_error lruc_get(lruc *cache, void *key, uint32_t key_length, void **value);
+lruc_error lruc_delete(lruc *cache, void *key, uint32_t key_length);
+
+#endif
diff --git a/src/lib/third_party/src/lruc.c b/src/lib/third_party/src/lruc.c
new file mode 100644
index 000000000..f08fb2ce1
--- /dev/null
+++ b/src/lib/third_party/src/lruc.c
@@ -0,0 +1,294 @@
+/* https://github.com/willcannings/C-LRU-Cache */
+
+#include "lruc.h"
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <err.h>
+
+// ------------------------------------------
+// private functions
+// ------------------------------------------
+// MurmurHash2, by Austin Appleby
+// http://sites.google.com/site/murmurhash/
+uint32_t lruc_hash(lruc *cache, void *key, uint32_t key_length) {
+  uint32_t m = 0x5bd1e995;
+  uint32_t r = 24;
+  uint32_t h = cache->seed ^ key_length;
+  char* data = (char *)key;
+
+  while(key_length >= 4) {
+    uint32_t k = *(uint32_t *)data;
+    k *= m;
+    k ^= k >> r;
+    k *= m;
+    h *= m;
+    h ^= k;
+    data += 4;
+    key_length -= 4;
+  }
+  
+  switch(key_length) {
+    case 3: h ^= data[2] << 16;
+    case 2: h ^= data[1] << 8;
+    case 1: h ^= data[0];
+            h *= m;
+  };
+
+  h ^= h >> 13;
+  h *= m;
+  h ^= h >> 15;
+  return h % cache->hash_table_size;
+}
+
+// compare a key against an existing item's key
+int lruc_cmp_keys(lruc_item *item, void *key, uint32_t key_length) {
+  if(key_length != item->key_length)
+    return 1;
+  else
+    return memcmp(key, item->key, key_length);
+}
+
+// remove an item and push it to the free items queue
+void lruc_remove_item(lruc *cache, lruc_item *prev, lruc_item *item, uint32_t hash_index) {
+  if(prev)
+    prev->next = item->next;
+  else
+    cache->items[hash_index] = (lruc_item *) item->next;
+  
+  // free memory and update the free memory counter
+  cache->free_memory += item->value_length;
+  free(item->value);
+  free(item->key);
+  
+  // push the item to the free items queue  
+  memset(item, 0, sizeof(lruc_item));
+  item->next = cache->free_items;
+  cache->free_items = item;
+}
+
+// remove the least recently used item
+// TODO: we can optimise this by finding the n lru items, where n = required_space / average_length
+void lruc_remove_lru_item(lruc *cache) {
+  lruc_item *min_item = NULL, *min_prev = NULL;
+  lruc_item *item = NULL, *prev = NULL;
+  uint32_t i = 0, min_index = -1;
+  uint64_t min_access_count = -1;
+  
+  for(; i < cache->hash_table_size; i++) {
+    item = cache->items[i];
+    prev = NULL;
+    
+    while(item) {
+      if(item->access_count < min_access_count || min_access_count == -1) {
+        min_access_count = item->access_count;
+        min_item  = item;
+        min_prev  = prev;
+        min_index = i;
+      }
+      prev = item;
+      item = item->next;
+    }
+  }
+  
+  if(min_item)
+    lruc_remove_item(cache, min_prev, min_item, min_index);
+}
+
+// pop an existing item off the free queue, or create a new one
+lruc_item *lruc_pop_or_create_item(lruc *cache) {
+  lruc_item *item = NULL;
+  
+  if(cache->free_items) {
+    item = cache->free_items;
+    cache->free_items = item->next;
+  } else {
+    item = (lruc_item *) calloc(sizeof(lruc_item), 1);
+  }
+  
+  return item;
+}
+
+// error helpers
+#define error_for(conditions, error)  if(conditions) {return error;}
+#define test_for_missing_cache()      error_for(!cache, LRUC_MISSING_CACHE)
+#define test_for_missing_key()        error_for(!key || key_length == 0, LRUC_MISSING_KEY)
+#define test_for_missing_value()      error_for(!value || value_length == 0, LRUC_MISSING_VALUE)
+#define test_for_value_too_large()    error_for(value_length > cache->total_memory, LRUC_VALUE_TOO_LARGE)
+
+// lock helpers
+#define lock_cache()    if(pthread_mutex_lock(cache->mutex)) {\
+  perror("LRU Cache unable to obtain mutex lock");\
+  return LRUC_PTHREAD_ERROR;\
+}
+
+#define unlock_cache()  if(pthread_mutex_unlock(cache->mutex)) {\
+  perror("LRU Cache unable to release mutex lock");\
+  return LRUC_PTHREAD_ERROR;\
+}
+
+
+// ------------------------------------------
+// public api
+// ------------------------------------------
+lruc *lruc_new(uint64_t cache_size, uint32_t average_length) {
+  // create the cache
+  lruc *cache = (lruc *) calloc(sizeof(lruc), 1);
+  if(!cache) {
+    perror("LRU Cache unable to create cache object");
+    return NULL;
+  }
+  cache->hash_table_size      = cache_size / average_length;
+  cache->average_item_length  = average_length;
+  cache->free_memory          = cache_size;
+  cache->total_memory         = cache_size;
+  cache->seed                 = time(NULL);
+  
+  // size the hash table to a guestimate of the number of slots required (assuming a perfect hash)
+  cache->items = (lruc_item **) calloc(sizeof(lruc_item *), cache->hash_table_size);
+  if(!cache->items) {
+    perror("LRU Cache unable to create cache hash table");
+    free(cache);
+    return NULL;
+  }
+  
+  // all cache calls are guarded by a mutex
+  cache->mutex = (pthread_mutex_t *) malloc(sizeof(pthread_mutex_t));
+  if(pthread_mutex_init(cache->mutex, NULL)) {
+    perror("LRU Cache unable to initialise mutex");
+    free(cache->items);
+    free(cache);
+    return NULL;
+  }
+  return cache;
+}
+
+
+lruc_error lruc_free(lruc *cache) {
+  test_for_missing_cache();
+  
+  // free each of the cached items, and the hash table
+  lruc_item *item = NULL, *next = NULL;
+  uint32_t i = 0;
+  if(cache->items) {
+    for(; i < cache->hash_table_size; i++) {
+      item = cache->items[i];    
+      while(item) {
+        next = (lruc_item *) item->next;
+        free(item);
+        item = next;
+      }
+    }
+    free(cache->items);
+  }
+  
+  // free the cache
+  if(cache->mutex) {
+    if(pthread_mutex_destroy(cache->mutex)) {
+      perror("LRU Cache unable to destroy mutex");
+      return LRUC_PTHREAD_ERROR;
+    }
+  }
+  free(cache);
+  
+  return LRUC_NO_ERROR;
+}
+
+
+lruc_error lruc_set(lruc *cache, void *key, uint32_t key_length, void *value, uint32_t value_length) {
+  test_for_missing_cache();
+  test_for_missing_key();
+  test_for_missing_value();
+  test_for_value_too_large();
+  lock_cache();
+  
+  // see if the key already exists
+  uint32_t hash_index = lruc_hash(cache, key, key_length), required = 0;
+  lruc_item *item = NULL, *prev = NULL;
+  item = cache->items[hash_index];
+  
+  while(item && lruc_cmp_keys(item, key, key_length)) {
+    prev = item;
+    item = (lruc_item *) item->next;
+  }
+  
+  if(item) {
+    // update the value and value_lengths
+    required = value_length - item->value_length;
+    free(item->value);
+    item->value = value;
+    item->value_length = value_length;
+    
+  } else {
+    // insert a new item
+    item = lruc_pop_or_create_item(cache);
+    item->value = value;
+    item->key = key;
+    item->value_length = value_length;
+    item->key_length = key_length;
+    required = value_length;
+    
+    if(prev)
+      prev->next = item;
+    else
+      cache->items[hash_index] = item;
+  }
+  item->access_count = ++cache->access_count;
+  
+  // remove as many items as necessary to free enough space
+  if(required > 0 && required > cache->free_memory) {
+    while(cache->free_memory < required)
+      lruc_remove_lru_item(cache);
+  }
+  cache->free_memory -= required;
+  unlock_cache();
+  return LRUC_NO_ERROR;
+}
+
+
+lruc_error lruc_get(lruc *cache, void *key, uint32_t key_length, void **value) {
+  test_for_missing_cache();
+  test_for_missing_key();
+  lock_cache();
+  
+  // loop until we find the item, or hit the end of a chain
+  uint32_t hash_index = lruc_hash(cache, key, key_length);
+  lruc_item *item = cache->items[hash_index];
+  
+  while(item && lruc_cmp_keys(item, key, key_length))
+    item = (lruc_item *) item->next;
+  
+  if(item) {
+    *value = item->value;
+    item->access_count = ++cache->access_count;
+  } else {
+    *value = NULL;
+  }
+  
+  unlock_cache();
+  return LRUC_NO_ERROR;
+}
+
+
+lruc_error lruc_delete(lruc *cache, void *key, uint32_t key_length) {
+  test_for_missing_cache();
+  test_for_missing_key();
+  lock_cache();
+  
+  // loop until we find the item, or hit the end of a chain
+  lruc_item *item = NULL, *prev = NULL;
+  uint32_t hash_index = lruc_hash(cache, key, key_length);
+  item = cache->items[hash_index];
+  
+  while(item && lruc_cmp_keys(item, key, key_length)) {
+    prev = item;
+    item = (lruc_item *) item->next;
+  }
+  
+  if(item) {
+    lruc_remove_item(cache, prev, item, hash_index);
+  }
+  
+  unlock_cache();
+  return LRUC_NO_ERROR;
+}