Added tinc protocol detection

8 files changed, 561 insertions, 6 deletions

diff --git a/src/include/ndpi_protocol_ids.h b/src/include/ndpi_protocol_ids.h
index 726736a06..4fce98b14 100644
--- a/src/include/ndpi_protocol_ids.h
+++ b/src/include/ndpi_protocol_ids.h
@@ -247,10 +247,7 @@
 #define NDPI_PROTOCOL_SMPP 	         207 /* Damir Franusic <df@release14.org> */
 
 #define NDPI_PROTOCOL_DNSCRYPT           208
-
-/* 209 free */
-#define NDPI_PROTOCOL_FREE_209           209
-
+#define NDPI_PROTOCOL_TINC	         209 /* William Guglielmo <william@deselmo.com> */
 #define NDPI_PROTOCOL_DEEZER 	         210
 #define NDPI_PROTOCOL_INSTAGRAM 	 211 /* Andrea Buscarinu <andrea.buscarinu@gmail.com> */
 #define NDPI_PROTOCOL_MICROSOFT 	 212
diff --git a/src/include/ndpi_protocols.h b/src/include/ndpi_protocols.h
index b3b4092b4..c0bce974e 100644
--- a/src/include/ndpi_protocols.h
+++ b/src/include/ndpi_protocols.h
@@ -196,6 +196,7 @@ void ndpi_search_drda(struct ndpi_detection_module_struct *ndpi_struct, struct n
 void ndpi_search_bjnp(struct ndpi_detection_module_struct *ndpi_struct, struct ndpi_flow_struct *flow);
 void ndpi_search_kxun(struct ndpi_detection_module_struct *ndpi_struct, struct ndpi_flow_struct *flow);
 void ndpi_search_smpp(struct ndpi_detection_module_struct *ndpi_struct, struct ndpi_flow_struct *flow);
+void ndpi_search_tinc(struct ndpi_detection_module_struct *ndpi_struct, struct ndpi_flow_struct *flow);
 /* --- INIT FUNCTIONS --- */
 void init_afp_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
 void init_aimini_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
@@ -339,4 +340,5 @@ void init_drda_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int
 void init_bjnp_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
 void init_kxun_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
 void init_smpp_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask);
+void init_tinc_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 e1fbeb71c..906268b62 100644
--- a/src/include/ndpi_typedefs.h
+++ b/src/include/ndpi_typedefs.h
@@ -25,6 +25,7 @@
 #define __NDPI_TYPEDEFS_H__
 
 #include "ndpi_define.h"
+#include "../lib/third_party/include/libcache.h"
 
 #define BT_ANNOUNCE
 #define SNAP_EXT
@@ -330,6 +331,18 @@ struct bt_announce {              // 192 bytes
 };
 #endif
 
+#ifdef NDPI_PROTOCOL_TINC
+
+#define TINC_CACHE_MAX_SIZE 100
+
+typedef struct {
+  u_int32_t src_address;
+  u_int32_t dst_address;
+  u_int16_t dst_port;
+} tinc_cache_entry_t;
+
+#endif
+
 typedef enum {
   HTTP_METHOD_UNKNOWN = 0,
   HTTP_METHOD_OPTIONS,
@@ -878,6 +891,9 @@ struct ndpi_detection_module_struct {
   int    bt_ann_len;
 #endif
 #endif
+#ifdef NDPI_PROTOCOL_TINC
+  cache_t *tinc_cache;
+#endif
 
   ndpi_proto_defaults_t proto_defaults[NDPI_MAX_SUPPORTED_PROTOCOLS+NDPI_MAX_NUM_CUSTOM_PROTOCOLS];
 
@@ -1052,6 +1068,11 @@ struct ndpi_flow_struct {
   u_int8_t ovpn_session_id[8];
   u_int8_t ovpn_counter;
 #endif
+#ifdef NDPI_PROTOCOL_TINC
+  u_int8_t tinc_state;
+  tinc_cache_entry_t tinc_cache_entry;
+#endif
+
 
   /* internal structures to save functions calls */
   struct ndpi_packet_struct packet;
diff --git a/src/lib/Makefile.am b/src/lib/Makefile.am
index 3770c9cfc..d3bd19264 100644
--- a/src/lib/Makefile.am
+++ b/src/lib/Makefile.am
@@ -158,13 +158,16 @@ libndpi_la_SOURCES = ndpi_content_match.c.inc \
 		     protocols/zattoo.c \
 		     protocols/zeromq.c \
 		     protocols/smpp.c \
+		     protocols/tinc.c \
 		     third_party/include/actypes.h \
 		     third_party/include/ahocorasick.h \
 		     third_party/include/ndpi_patricia.h \
 		     third_party/include/node.h \
 		     third_party/include/sort.h \
+		     third_party/include/libcache.h \
 		     third_party/src/ahocorasick.c \
 		     third_party/src/node.c \
-		     third_party/src/sort.c
+		     third_party/src/sort.c \
+		     third_party/src/libcache.c
 
 EXTRA_DIST = third_party/src/ndpi_patricia.c
diff --git a/src/lib/ndpi_main.c b/src/lib/ndpi_main.c
index 040c54959..ef6393877 100644
--- a/src/lib/ndpi_main.c
+++ b/src/lib/ndpi_main.c
@@ -1621,9 +1621,13 @@ static void ndpi_init_protocol_defaults(struct ndpi_detection_module_struct *ndp
 			    no_master, "DNScrypt", NDPI_PROTOCOL_CATEGORY_NETWORK,
 			    ndpi_build_default_ports(ports_a, 0, 0, 0, 0, 0),   /* TCP */
 			    ndpi_build_default_ports(ports_b, 0, 0, 0, 0, 0));  /* UDP */
+    ndpi_set_proto_defaults(ndpi_mod, NDPI_PROTOCOL_SAFE, NDPI_PROTOCOL_TINC,
+			    no_master,
+			    no_master, "TINC", NDPI_PROTOCOL_CATEGORY_VPN,
+			    ndpi_build_default_ports(ports_a, 655, 0, 0, 0, 0) /* TCP */,
+			    ndpi_build_default_ports(ports_b, 655, 0, 0, 0, 0) /* UDP */);
     
 /* To be removed as soon as we define new protocols */
-    ndpi_init_placeholder_proto(ndpi_mod, ports_a, ports_b, no_master, NDPI_PROTOCOL_FREE_209);
     ndpi_init_placeholder_proto(ndpi_mod, ports_a, ports_b, no_master, NDPI_PROTOCOL_FREE_217);
     ndpi_init_placeholder_proto(ndpi_mod, ports_a, ports_b, no_master, NDPI_PROTOCOL_FREE_224);
 
@@ -1941,6 +1945,11 @@ void ndpi_exit_detection_module(struct ndpi_detection_module_struct *ndpi_struct
 	ndpi_free(ndpi_struct->proto_defaults[i].protoName);
     }
 
+#ifdef NDPI_PROTOCOL_TINC
+    if(ndpi_struct->tinc_cache)
+      cache_free(ndpi_struct->tinc_cache);
+#endif
+
     if(ndpi_struct->protocols_ptree)
       ndpi_Destroy_Patricia((patricia_tree_t*)ndpi_struct->protocols_ptree, free_ptree_data);
 
@@ -2709,6 +2718,9 @@ void ndpi_set_protocol_detection_bitmask2(struct ndpi_detection_module_struct *n
   /* SMPP */
   init_smpp_dissector(ndpi_struct, &a, detection_bitmask);
 
+  /* TINC */
+  init_tinc_dissector(ndpi_struct, &a, detection_bitmask);
+
   /*** Put false-positive sensitive protocols at the end ***/
 
   /* SKYPE */
diff --git a/src/lib/protocols/tinc.c b/src/lib/protocols/tinc.c
new file mode 100644
index 000000000..b25aff2e7
--- /dev/null
+++ b/src/lib/protocols/tinc.c
@@ -0,0 +1,160 @@
+/*
+ * tinc.c
+ *
+ * Copyright (C) 2017 - William Guglielmo <william@deselmo.com>
+ * Copyright (C) 2017 - 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_api.h"
+
+#ifdef NDPI_PROTOCOL_TINC
+
+static void ndpi_check_tinc(struct ndpi_detection_module_struct *ndpi_struct, struct ndpi_flow_struct *flow)
+{
+  struct ndpi_packet_struct *packet = &flow->packet;
+  const u_int8_t *packet_payload = packet->payload;
+  u_int32_t payload_len = packet->payload_packet_len;
+  struct ndpi_id_struct *src = flow->src;
+  struct ndpi_id_struct *dst = flow->dst;
+  
+  if(packet->udp != NULL) {
+    if(ndpi_struct->tinc_cache != NULL) {
+      tinc_cache_entry_t tinc_cache_entry1 = {
+        .src_address = packet->iph->saddr,
+        .dst_address = packet->iph->daddr,
+        .dst_port = packet->udp->dest
+      };
+
+      tinc_cache_entry_t tinc_cache_entry2 = {
+        .src_address = packet->iph->daddr,
+        .dst_address = packet->iph->saddr,
+        .dst_port = packet->udp->source
+      };
+
+      if( cache_remove(ndpi_struct->tinc_cache, &tinc_cache_entry1, sizeof(tinc_cache_entry1)) == CACHE_NO_ERROR ||
+          cache_remove(ndpi_struct->tinc_cache, &tinc_cache_entry2, sizeof(tinc_cache_entry2)) == CACHE_NO_ERROR)
+      {
+        cache_remove(ndpi_struct->tinc_cache, &tinc_cache_entry1, sizeof(tinc_cache_entry1));
+        cache_remove(ndpi_struct->tinc_cache, &tinc_cache_entry2, sizeof(tinc_cache_entry2));
+
+        // cache_free(ndpi_struct->tinc_cache);
+
+        NDPI_LOG(NDPI_PROTOCOL_TINC, ndpi_struct, NDPI_LOG_DEBUG, "Found tinc udp connection\n");
+        ndpi_set_detected_protocol(ndpi_struct, flow, NDPI_PROTOCOL_TINC, NDPI_PROTOCOL_UNKNOWN);
+      }
+    }
+
+    return;
+
+  } 
+  else if(packet->tcp != NULL) {
+
+    if(payload_len == 0) {
+      if(packet->tcp->syn == 1 && packet->tcp->ack == 0) {
+        flow->tinc_cache_entry.src_address = packet->iph->saddr;
+        flow->tinc_cache_entry.dst_address = packet->iph->daddr;
+        flow->tinc_cache_entry.dst_port = packet->tcp->dest;
+      }
+      return;
+    }
+
+    switch(flow->tinc_state) {
+      case 0:
+      case 1:
+        if(payload_len > 6 && memcmp(packet_payload, "0 ", 2) == 0 && packet_payload[2] != ' ') {
+          u_int16_t i = 3;
+          while(i < payload_len && packet_payload[i++] != ' ');
+          if(i+3 == payload_len && memcmp((packet_payload+i), "17\n", 3) == 0) {
+            flow->tinc_state++;
+            return;
+          }
+        }
+        break;
+
+      case 2:
+      case 3:
+        if(payload_len > 11 && memcmp(packet_payload, "1 ", 2) == 0 && packet_payload[2] != ' ') {
+          u_int16_t i = 3;
+          u_int8_t numbers_left = 4;
+          while(numbers_left) {
+            while(packet_payload[i] >= '0' && packet_payload[i] <= '9') {
+              i++;
+            }
+
+            if(packet_payload[i++] == ' ') {
+              numbers_left--;
+            }
+            else break;
+          }
+          
+          if(numbers_left) break;
+          
+          while((packet_payload[i] >= '0' && packet_payload[i] <= '9') ||
+                (packet_payload[i] >= 'A' && packet_payload[i] <= 'Z')) {
+            i++;
+          }
+          
+          if(packet_payload[i] == '\n') {
+            if(++flow->tinc_state > 3) {
+              if(ndpi_struct->tinc_cache == NULL) {
+                ndpi_struct->tinc_cache = cache_new(TINC_CACHE_MAX_SIZE);
+              }
+
+              cache_add(ndpi_struct->tinc_cache, &(flow->tinc_cache_entry), sizeof(flow->tinc_cache_entry));
+
+              NDPI_LOG(NDPI_PROTOCOL_TINC, ndpi_struct, NDPI_LOG_DEBUG, "Found tinc tcp connection\n");
+              ndpi_set_detected_protocol(ndpi_struct, flow, NDPI_PROTOCOL_TINC, NDPI_PROTOCOL_UNKNOWN);
+            }
+            return;
+          }
+        }
+        break;
+      
+      default: break;
+    }
+  }
+
+  NDPI_LOG(NDPI_PROTOCOL_TINC, ndpi_struct, NDPI_LOG_DEBUG, "exclude tinc.\n");
+  NDPI_ADD_PROTOCOL_TO_BITMASK(flow->excluded_protocol_bitmask, NDPI_PROTOCOL_TINC);
+}
+
+void ndpi_search_tinc(struct ndpi_detection_module_struct* ndpi_struct, struct ndpi_flow_struct* flow) {
+  struct ndpi_packet_struct* packet = &flow->packet;
+
+  NDPI_LOG(NDPI_PROTOCOL_TINC, ndpi_struct, NDPI_LOG_DEBUG, "tinc detection...\n");
+
+  if (packet->detected_protocol_stack[0] != NDPI_PROTOCOL_TINC) {
+    if (packet->tcp_retransmission == 0) {
+      ndpi_check_tinc(ndpi_struct, flow);
+    }
+  }
+}
+
+void init_tinc_dissector(struct ndpi_detection_module_struct *ndpi_struct, u_int32_t *id, NDPI_PROTOCOL_BITMASK *detection_bitmask)
+{
+  ndpi_set_bitmask_protocol_detection("TINC", ndpi_struct, detection_bitmask, *id,
+              NDPI_PROTOCOL_TINC,
+              ndpi_search_tinc,
+              NDPI_SELECTION_BITMASK_PROTOCOL_TCP_OR_UDP,
+              SAVE_DETECTION_BITMASK_AS_UNKNOWN,
+              ADD_TO_DETECTION_BITMASK);
+
+  *id += 1;
+}
+
+#endif
diff --git a/src/lib/third_party/include/libcache.h b/src/lib/third_party/include/libcache.h
new file mode 100644
index 000000000..f959b3a9c
--- /dev/null
+++ b/src/lib/third_party/include/libcache.h
@@ -0,0 +1,105 @@
+#ifndef __LIBCACHE_H__
+#define __LIBCACHE_H__
+
+#include <stdint.h>
+
+
+/* Codes representing the result of some functions */
+typedef enum {
+  CACHE_NO_ERROR = 0,
+  CACHE_CONTAINS_FALSE = 0,
+  CACHE_CONTAINS_TRUE,
+  CACHE_INVALID_INPUT,
+  CACHE_REMOVE_NOT_FOUND,
+  CACHE_MALLOC_ERROR
+} cache_result;
+
+/* CACHE_T */
+typedef struct cache_t cache_t;
+
+/* CACHE_ENTRY */
+typedef struct cache_entry cache_entry;
+
+/* CACHE_ENTRY_MAP */
+typedef struct cache_entry_map cache_entry_map;
+
+
+/* STRUCT CACHE_T */
+struct cache_t {
+  uint32_t size;
+  uint32_t max_size;
+  cache_entry *head;
+  cache_entry *tail;
+  cache_entry_map **map;
+};
+
+/* STRUCT CACHE_ENTRY */
+struct cache_entry_map {
+  cache_entry *entry;
+  cache_entry_map *next;
+};
+
+/* STRUCT CACHE_ENTRY_MAP */
+struct cache_entry {
+  void *item;
+  uint32_t item_size;
+  cache_entry *prev;
+  cache_entry *next;
+};
+
+
+/**
+ * Returns a new cache_t
+ * 
+ * @par    cache_max_size  = max number of item that the new cache_t can contain
+ * @return a new cache_t, or NULL if an error occurred
+ *
+ */
+cache_t *cache_new(uint32_t cache_max_size);
+
+
+/**
+ * Add an item in the specified cache_t
+ * 
+ * @par    cache      = the cache_t
+ * @par    item       = pointer to the item to add
+ * @par    item_size  = size of the item
+ * @return a code representing the result of the function
+ *
+ */
+cache_result cache_add(cache_t *cache, void *item, uint32_t item_size);
+
+
+/**
+ * Check if an item is in the specified cache_t
+ * 
+ * @par    cache      = the cache_t
+ * @par    item       = pointer to the item to check
+ * @par    item_size  = size of the item
+ * @return a code representing the result of the function
+ *
+ */
+cache_result cache_contains(cache_t *cache, void *item, uint32_t item_size);
+
+
+/**
+ * Remove an item in the specified cache_t
+ * 
+ * @par    cache      = the cache_t
+ * @par    item       = pointer to the item to remove
+ * @par    item_size  = size of the item
+ * @return a code representing the result of the function
+ *
+ */
+cache_result cache_remove(cache_t *cache, void *item, uint32_t item_size);
+
+/**
+ * Free the specified cache_t
+ * 
+ * @par alist  = the cache
+ *
+ */
+void cache_free(cache_t *cache);
+
+
+#endif
diff --git a/src/lib/third_party/src/libcache.c b/src/lib/third_party/src/libcache.c
new file mode 100644
index 000000000..dc4bf9460
--- /dev/null
+++ b/src/lib/third_party/src/libcache.c
@@ -0,0 +1,255 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "libcache.h"
+
+
+// https://en.wikipedia.org/wiki/Jenkins_hash_function
+uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
+  size_t i = 0;
+  uint32_t hash = 0;
+  while (i != length) {
+    hash += key[i++];
+    hash += hash << 10;
+    hash ^= hash >> 6;
+  }
+  hash += hash << 3;
+  hash ^= hash >> 11;
+  hash += hash << 15;
+  return hash;
+}
+
+cache_entry_map *cache_entry_map_new() {
+  return (cache_entry_map *) calloc(sizeof(cache_entry_map), 1);
+}
+cache_entry *cache_entry_new() {
+  return (cache_entry *) calloc(sizeof(cache_entry), 1);
+}
+
+cache_t *cache_new(uint32_t cache_max_size) {
+  if(!cache_max_size) {
+    return NULL;
+  }
+
+  cache_t *cache = (cache_t *) calloc(sizeof(cache_t), 1);
+  if(!cache) {
+    return NULL;
+  }
+  
+  cache->size = 0;
+  cache->max_size = cache_max_size;
+
+  cache->map = (cache_entry_map **) calloc(sizeof(cache_entry_map *), cache->max_size);
+
+  if(!cache->map) {
+    free(cache);
+    return NULL;
+  }
+
+  return cache;
+}
+
+cache_result cache_add(cache_t *cache, void *item, uint32_t item_size) {
+  if(!cache || !item || !item_size) {
+    return CACHE_INVALID_INPUT;
+  }
+
+  uint32_t hash = jenkins_one_at_a_time_hash(item, item_size) % cache->max_size;
+
+  if((cache->map)[hash]) {
+    cache_entry_map *hash_entry_map = cache->map[hash];
+    while(hash_entry_map) {
+      if(item_size == hash_entry_map->entry->item_size &&
+          !memcmp(hash_entry_map->entry->item, item, item_size)) {
+        break;
+      }
+      
+      hash_entry_map = hash_entry_map->next;
+    }
+
+    if(hash_entry_map) {
+      cache_entry *entry = hash_entry_map->entry;
+      if(entry->prev) {
+        if(entry->next) {
+          entry->prev->next = entry->next;
+          entry->next->prev = entry->prev;
+        } else {
+          entry->prev->next = NULL;
+          cache->tail = entry->prev;
+        }
+        entry->prev = NULL;
+        entry->next = cache->head;
+        cache->head->prev = entry;
+        cache->head = entry;
+      }
+
+      return CACHE_NO_ERROR;
+    }
+  }
+
+  
+  cache_entry *entry = cache_entry_new();
+  if(!entry) {
+    return CACHE_MALLOC_ERROR;
+  }
+
+  cache_entry_map *map_entry = cache_entry_map_new();
+  if(!map_entry) {
+    free(entry);
+    return CACHE_MALLOC_ERROR;
+  }
+
+
+  entry->item = malloc(item_size);
+  memcpy(entry->item, item, item_size);
+  entry->item_size = item_size;
+
+  entry->prev = NULL;
+  entry->next = cache->head;
+  if(cache->head) cache->head->prev = entry;
+  cache->head = entry;
+
+  map_entry->entry = entry;
+  map_entry->next = cache->map[hash];
+  cache->map[hash] = map_entry;
+
+  if(cache->max_size > cache->size) {
+    (cache->size)++;
+    if(cache->size == 1) {
+      cache->tail = entry;
+    }
+  } else {
+    cache_entry *tail = cache->tail;
+
+    uint32_t hash = jenkins_one_at_a_time_hash(tail->item, tail->item_size) % cache->max_size;
+    if(cache->map[hash]) {
+      cache_entry_map *hash_entry_map_prev = NULL;
+      cache_entry_map *hash_entry_map = cache->map[hash];
+      while(hash_entry_map) {
+        if(tail->item_size == hash_entry_map->entry->item_size &&
+            !memcmp(tail->item, hash_entry_map->entry->item, item_size)) {
+          break;
+        }
+        
+        hash_entry_map_prev = hash_entry_map;
+        hash_entry_map = hash_entry_map->next;
+      }
+
+      if(hash_entry_map_prev) {
+        hash_entry_map_prev->next = hash_entry_map->next;
+      } else {
+        cache->map[hash] = hash_entry_map->next;
+      }
+
+      tail->prev->next = NULL;
+      cache->tail = tail->prev;
+      
+      free(tail->item);
+      free(tail);
+      free(hash_entry_map);
+    }
+  }
+
+  return CACHE_NO_ERROR;
+}
+
+cache_result cache_contains(cache_t *cache, void *item, uint32_t item_size) {
+  if(!cache || !item || !item_size) {
+    return CACHE_INVALID_INPUT;
+  }
+
+  uint32_t hash = jenkins_one_at_a_time_hash(item, item_size) % cache->max_size;
+
+  if(cache->map[hash]) {
+    cache_entry_map *hash_entry_map = cache->map[hash];
+    while(hash_entry_map) {
+      if(item_size == hash_entry_map->entry->item_size &&
+          !memcmp(hash_entry_map->entry->item, item, item_size)) {
+        return CACHE_CONTAINS_TRUE;
+      }
+      
+      hash_entry_map = hash_entry_map->next;
+    }
+  }
+
+  return CACHE_CONTAINS_FALSE;
+}
+
+cache_result cache_remove(cache_t *cache, void *item, uint32_t item_size) {
+  if(!cache || !item || !item_size) {
+    return CACHE_INVALID_INPUT;
+  }
+
+  uint32_t hash = jenkins_one_at_a_time_hash(item, item_size) % cache->max_size;
+
+  if(cache->map[hash]) {
+    cache_entry_map *hash_entry_map_prev = NULL;
+    cache_entry_map *hash_entry_map = cache->map[hash];
+    while(hash_entry_map) {
+      if(item_size == hash_entry_map->entry->item_size &&
+          !memcmp(hash_entry_map->entry->item, item, item_size)) {
+        break;
+      }
+      
+      hash_entry_map_prev = hash_entry_map;
+      hash_entry_map = hash_entry_map->next;
+    }
+
+    if(hash_entry_map) {
+      
+      if(hash_entry_map_prev) {
+        hash_entry_map_prev->next = hash_entry_map->next;
+      } else {
+        cache->map[hash] = hash_entry_map->next;
+      }
+
+      cache_entry *entry = hash_entry_map->entry;
+
+      if(entry->prev) {
+        entry->prev->next = entry->next;
+      } else {
+        cache->head = entry->next;
+      }
+      if(entry->next) {
+        entry->next->prev = entry->prev;
+      } else {
+        cache->tail = entry->prev;
+      }
+
+      free(entry->item);
+      free(entry);
+      free(hash_entry_map);
+
+      (cache->size)--;
+      return CACHE_NO_ERROR;
+    }
+  }
+
+  return CACHE_REMOVE_NOT_FOUND;
+}
+
+void cache_free(cache_t *cache) {
+  if(!cache) {
+    return;
+  }
+
+  int i;
+  for(i = 0; i < cache->max_size; i++) {
+    cache_entry_map *prev = NULL;
+    cache_entry_map *curr = cache->map[i];
+    while(curr) {
+      prev = curr;
+      curr = curr->next;
+      free(prev->entry->item);
+      free(prev->entry);
+      free(prev);
+    }
+  }
+
+  free(cache->map);
+  free(cache);
+
+  return;
+}