src: rework of the hash-cache infrastructure

Currently, the caching system is implemented in a two layer
architecture: hashtable (inner layer) and cache (upper layer).
This patch reworks the hash-cache infrastructure to solve some
initial design problems to make it more flexible, the main strong
points of this patch are:

* Memory handling is done in the cache layer, not in the inner
hashtable layer. This removes one of the main dependencies between
the hashtable and the cache classes.
* Remove excessive encapsulation: the former cache used to hide a
lot of details of the inner hashtable implementation.
* Fix over-hashing of some operations: lookup-delete-add required
three hash calculations. Similarly, the update-or-add operation
required two hash calculations. Now, we calculate the hash once
and re-use the value how many times as we need.

This patch simplifies the caching system. As a result, we save ~130
lines of code. Small code means and less complexity means less
chance to have bugs.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

8 files changed, 50 insertions, 90 deletions

diff --git a/include/Makefile.am b/include/Makefile.am
index 13f7e37..c3f8904 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -1,6 +1,6 @@
 
-noinst_HEADERS = alarm.h jhash.h slist.h cache.h linux_list.h linux_rbtree.h \
-		 sync.h conntrackd.h local.h us-conntrack.h \
+noinst_HEADERS = alarm.h jhash.h cache.h linux_list.h linux_rbtree.h \
+		 sync.h conntrackd.h local.h \
 		 debug.h log.h hash.h mcast.h conntrack.h \
 		 network.h filter.h queue.h vector.h cidr.h \
 		 traffic_stats.h netlink.h fds.h event.h bitops.h
diff --git a/include/cache.h b/include/cache.h
index ebed70a..dcd6bcd 100644
--- a/include/cache.h
+++ b/include/cache.h
@@ -3,6 +3,8 @@
 
 #include <stdint.h>
 #include <stddef.h>
+#include "hash.h"
+#include "alarm.h"
 
 /* cache features */
 enum {
@@ -22,14 +24,20 @@ enum {
 #define CACHE_MAX_FEATURE __CACHE_MAX_FEATURE
 
 struct cache;
-struct us_conntrack;
+struct cache_object {
+	struct	hashtable_node hashnode;
+	struct	nf_conntrack *ct;
+	struct	cache *cache;
+	struct	alarm_block alarm;
+	char	data[0];
+};
 
 struct cache_feature {
 	size_t size;
-	void (*add)(struct us_conntrack *u, void *data);
-	void (*update)(struct us_conntrack *u, void *data);
-	void (*destroy)(struct us_conntrack *u, void *data);
-	int  (*dump)(struct us_conntrack *u, void *data, char *buf, int type);
+	void (*add)(struct cache_object *obj, void *data);
+	void (*update)(struct cache_object *obj, void *data);
+	void (*destroy)(struct cache_object *obj, void *data);
+	int  (*dump)(struct cache_object *obj, void *data, char *buf, int type);
 };
 
 extern struct cache_feature lifetime_feature;
@@ -48,6 +56,7 @@ struct cache {
 	unsigned int *feature_offset;
 	struct cache_extra *extra;
 	unsigned int extra_offset;
+	size_t object_size;
 
         /* statistics */
 	struct {
@@ -77,9 +86,9 @@ struct cache {
 struct cache_extra {
 	unsigned int size;
 
-	void (*add)(struct us_conntrack *u, void *data);
-	void (*update)(struct us_conntrack *u, void *data);
-	void (*destroy)(struct us_conntrack *u, void *data);
+	void (*add)(struct cache_object *obj, void *data);
+	void (*update)(struct cache_object *obj, void *data);
+	void (*destroy)(struct cache_object *obj, void *data);
 };
 
 struct nf_conntrack;
@@ -87,16 +96,18 @@ struct nf_conntrack;
 struct cache *cache_create(const char *name, unsigned int features, struct cache_extra *extra);
 void cache_destroy(struct cache *e);
 
-struct us_conntrack *cache_add(struct cache *c, struct nf_conntrack *ct);
-struct us_conntrack *cache_update(struct cache *c, struct nf_conntrack *ct);
-struct us_conntrack *cache_update_force(struct cache *c, struct nf_conntrack *ct);
-int cache_del(struct cache *c, struct nf_conntrack *ct);
-int __cache_del_timer(struct cache *c, struct us_conntrack *u, int timeout);
-struct us_conntrack *cache_find(struct cache *c, struct nf_conntrack *ct);
-int cache_test(struct cache *c, struct nf_conntrack *ct);
+struct cache_object *cache_object_new(struct cache *c, struct nf_conntrack *ct);
+void cache_object_free(struct cache_object *obj);
+
+int cache_add(struct cache *c, struct cache_object *obj, int id);
+void cache_update(struct cache *c, struct cache_object *obj, int id, struct nf_conntrack *ct);
+struct cache_object *cache_update_force(struct cache *c, struct nf_conntrack *ct);
+void cache_del(struct cache *c, struct cache_object *obj);
+int cache_del_timer(struct cache *c, struct cache_object *obj, int timeout);
+struct cache_object *cache_find(struct cache *c, struct nf_conntrack *ct, int *pos);
 void cache_stats(const struct cache *c, int fd);
 void cache_stats_extended(const struct cache *c, int fd);
-struct us_conntrack *cache_get_conntrack(struct cache *, void *);
+struct cache_object *cache_data_get_object(struct cache *c, void *data);
 void *cache_get_extra(struct cache *, void *);
 void cache_iterate(struct cache *c, void *data, int (*iterate)(void *data1, void *data2));
 
diff --git a/include/filter.h b/include/filter.h
index 9c2cf66..72c2aa4 100644
--- a/include/filter.h
+++ b/include/filter.h
@@ -4,6 +4,7 @@
 #include <stdint.h>
 #include <string.h>
 #include <netinet/in.h>
+#include <hash.h>
 
 enum ct_filter_type {
 	CT_FILTER_L4PROTO,
@@ -17,6 +18,16 @@ enum ct_filter_logic {
 	CT_FILTER_POSITIVE = 1,
 };
 
+struct ct_filter_ipv4_hnode {
+	struct hashtable_node node;
+	uint32_t ip;
+};
+
+struct ct_filter_ipv6_hnode {
+	struct hashtable_node node;
+	uint32_t ipv6[4];
+};
+
 struct ct_filter_netmask_ipv4 {
 	uint32_t ip;
 	uint32_t mask;
diff --git a/include/hash.h b/include/hash.h
index 2fb0a27..68d618b 100644
--- a/include/hash.h
+++ b/include/hash.h
@@ -2,7 +2,6 @@
 #define _NF_SET_HASH_H_
 
 #include <unistd.h>
-#include "slist.h"
 #include "linux_list.h"
 
 #include <stdint.h>
@@ -15,35 +14,30 @@ struct hashtable {
 	uint32_t limit;
 	uint32_t count;
 	uint32_t initval;
-	uint32_t datasize;
 	
 	uint32_t (*hash)(const void *data, const struct hashtable *table);
 	int	 (*compare)(const void *data1, const void *data2);
 
-	struct slist_head 	members[0];
+	struct list_head 	members[0];
 };
 
 struct hashtable_node {
-	struct slist_head head;
-	char data[0];
+	struct list_head head;
 };
 
-struct hashtable_node *hashtable_alloc_node(int datasize, void *data);
-void hashtable_destroy_node(struct hashtable_node *h);
-
 struct hashtable *
-hashtable_create(int hashsize, int limit, int datasize,
+hashtable_create(int hashsize, int limit,
 		 uint32_t (*hash)(const void *data,
 		 		  const struct hashtable *table),
 		 int (*compare)(const void *data1, const void *data2));
 void hashtable_destroy(struct hashtable *h);
-
-void *hashtable_add(struct hashtable *table, void *data);
-void *hashtable_find(struct hashtable *table, const void *data);
-int hashtable_del(struct hashtable *table, void *data);
+int hashtable_hash(const struct hashtable *table, const void *data);
+struct hashtable_node *hashtable_find(const struct hashtable *table, const void *data, int id);
+int hashtable_add(struct hashtable *table, struct hashtable_node *n, int id);
+void hashtable_del(struct hashtable *table, struct hashtable_node *node);
 int hashtable_flush(struct hashtable *table);
 int hashtable_iterate(struct hashtable *table, void *data,
-		      int (*iterate)(void *data1, void *data2));
+		      int (*iterate)(void *data, struct hashtable_node *n));
 unsigned int hashtable_counter(const struct hashtable *table);
 
 #endif
diff --git a/include/network.h b/include/network.h
index 40bb2b2..619ce3e 100644
--- a/include/network.h
+++ b/include/network.h
@@ -75,7 +75,6 @@ enum {
 	__hdr;							\
 })
 
-struct us_conntrack;
 struct mcast_sock;
 
 enum {
diff --git a/include/slist.h b/include/slist.h
deleted file mode 100644
index 257b627..0000000
--- a/include/slist.h
+++ /dev/null
@@ -1,41 +0,0 @@
-#ifndef _SLIST_H_
-#define _SLIST_H_
-
-#include "linux_list.h"
-
-#define INIT_SLIST_HEAD(ptr) ((ptr).next = NULL)
-
-struct slist_head {
-	struct slist_head *next;
-};
-
-static inline int slist_empty(const struct slist_head *h)
-{
-	return !h->next;
-}
-
-static inline void slist_del(struct slist_head *t, struct slist_head *prev)
-{
-	prev->next = t->next;
-	t->next = LIST_POISON1;
-}
-
-static inline void slist_add(struct slist_head *head, struct slist_head *t)
-{
-	struct slist_head *tmp = head->next;
-	head->next = t;
-	t->next = tmp;
-}
-
-#define slist_entry(ptr, type, member) container_of(ptr,type,member)
-
-#define slist_for_each(pos, head) \
-	for (pos = (head)->next; pos; \
-	     pos = pos->next)
-
-#define slist_for_each_safe(pos, prev, next, head) \
-	for (pos = (head)->next, prev = (head); \
-	     pos && ({ next = pos->next; 1; }); \
-	     ({ prev = (prev->next != next) ? prev->next : prev; }), pos = next)
-
-#endif
diff --git a/include/sync.h b/include/sync.h
index fc06c93..60c9fae 100644
--- a/include/sync.h
+++ b/include/sync.h
@@ -2,7 +2,7 @@
 #define _SYNC_HOOKS_H_
 
 struct nethdr;
-struct us_conntrack;
+struct cache_object;
 
 struct sync_mode {
 	int internal_cache_flags;
@@ -14,7 +14,7 @@ struct sync_mode {
 	void (*kill)(void);
 	int  (*local)(int fd, int type, void *data);
 	int  (*recv)(const struct nethdr *net);
-	void (*send)(struct nethdr *net, struct us_conntrack *u);
+	void (*send)(struct nethdr *net, struct cache_object *obj);
 	void (*run)(void);
 };
 
diff --git a/include/us-conntrack.h b/include/us-conntrack.h
deleted file mode 100644
index 9eafa3b..0000000
--- a/include/us-conntrack.h
+++ /dev/null
@@ -1,14 +0,0 @@
-#ifndef _US_CONNTRACK_H_
-#define _US_CONNTRACK_H_
-
-#include "alarm.h"
-#include <libnetfilter_conntrack/libnetfilter_conntrack.h>
-
-struct us_conntrack {
-	struct 	nf_conntrack *ct;
-	struct  cache *cache; 
-	struct	alarm_block alarm;
-	char 	data[0];
-};
-
-#endif