From f72bf0ed59d14270d7b820626f9c7a7c67f40c00 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Mon, 2 Jun 2008 01:36:48 +0200 Subject: rework NFCT to use a generic hashtable This patch introduces a generic hashtable to store the nf_conntrack objects. The objects are identified by the original and reply tuples instead of the conntrack ID which is not dumped in the event message of linux kernel < 2.6.25. This patch also fixes the NFCT_MSG_* by NFCT_T_* which is the appropriate message type tag. --- include/ulogd/hash.h | 48 +++++++++++++++++ include/ulogd/jhash.h | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++ include/ulogd/slist.h | 40 ++++++++++++++ 3 files changed, 234 insertions(+) create mode 100644 include/ulogd/hash.h create mode 100644 include/ulogd/jhash.h create mode 100644 include/ulogd/slist.h (limited to 'include') diff --git a/include/ulogd/hash.h b/include/ulogd/hash.h new file mode 100644 index 0000000..45d2f48 --- /dev/null +++ b/include/ulogd/hash.h @@ -0,0 +1,48 @@ +#ifndef _NF_SET_HASH_H_ +#define _NF_SET_HASH_H_ + +#include +#include "slist.h" +#include + +#include + +struct hashtable; +struct hashtable_node; + +struct hashtable { + uint32_t hashsize; + uint32_t limit; + uint32_t count; + uint32_t initval; + uint32_t datasize; + + uint32_t (*hash)(const void *data, struct hashtable *table); + int (*compare)(const void *data1, const void *data2); + + struct slist_head members[0]; +}; + +struct hashtable_node { + struct slist_head head; + char data[0]; +}; + +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, + uint32_t (*hash)(const void *data, 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_get(struct hashtable *table, const void *data); +int hashtable_del(struct hashtable *table, void *data); +int hashtable_flush(struct hashtable *table); +int hashtable_iterate(struct hashtable *table, void *data, + int (*iterate)(void *data1, void *data2)); +unsigned int hashtable_counter(const struct hashtable *table); + +#endif diff --git a/include/ulogd/jhash.h b/include/ulogd/jhash.h new file mode 100644 index 0000000..38b8780 --- /dev/null +++ b/include/ulogd/jhash.h @@ -0,0 +1,146 @@ +#ifndef _LINUX_JHASH_H +#define _LINUX_JHASH_H + +#define u32 unsigned int +#define u8 char + +/* jhash.h: Jenkins hash support. + * + * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net) + * + * http://burtleburtle.net/bob/hash/ + * + * These are the credits from Bob's sources: + * + * lookup2.c, by Bob Jenkins, December 1996, Public Domain. + * hash(), hash2(), hash3, and mix() are externally useful functions. + * Routines to test the hash are included if SELF_TEST is defined. + * You can use this free for any purpose. It has no warranty. + * + * Copyright (C) 2003 David S. Miller (davem@redhat.com) + * + * I've modified Bob's hash to be useful in the Linux kernel, and + * any bugs present are surely my fault. -DaveM + */ + +/* NOTE: Arguments are modified. */ +#define __jhash_mix(a, b, c) \ +{ \ + a -= b; a -= c; a ^= (c>>13); \ + b -= c; b -= a; b ^= (a<<8); \ + c -= a; c -= b; c ^= (b>>13); \ + a -= b; a -= c; a ^= (c>>12); \ + b -= c; b -= a; b ^= (a<<16); \ + c -= a; c -= b; c ^= (b>>5); \ + a -= b; a -= c; a ^= (c>>3); \ + b -= c; b -= a; b ^= (a<<10); \ + c -= a; c -= b; c ^= (b>>15); \ +} + +/* The golden ration: an arbitrary value */ +#define JHASH_GOLDEN_RATIO 0x9e3779b9 + +/* The most generic version, hashes an arbitrary sequence + * of bytes. No alignment or length assumptions are made about + * the input key. + */ +static inline u32 jhash(const void *key, u32 length, u32 initval) +{ + u32 a, b, c, len; + const u8 *k = key; + + len = length; + a = b = JHASH_GOLDEN_RATIO; + c = initval; + + while (len >= 12) { + a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24)); + b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24)); + c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24)); + + __jhash_mix(a,b,c); + + k += 12; + len -= 12; + } + + c += length; + switch (len) { + case 11: c += ((u32)k[10]<<24); + case 10: c += ((u32)k[9]<<16); + case 9 : c += ((u32)k[8]<<8); + case 8 : b += ((u32)k[7]<<24); + case 7 : b += ((u32)k[6]<<16); + case 6 : b += ((u32)k[5]<<8); + case 5 : b += k[4]; + case 4 : a += ((u32)k[3]<<24); + case 3 : a += ((u32)k[2]<<16); + case 2 : a += ((u32)k[1]<<8); + case 1 : a += k[0]; + }; + + __jhash_mix(a,b,c); + + return c; +} + +/* A special optimized version that handles 1 or more of u32s. + * The length parameter here is the number of u32s in the key. + */ +static inline u32 jhash2(u32 *k, u32 length, u32 initval) +{ + u32 a, b, c, len; + + a = b = JHASH_GOLDEN_RATIO; + c = initval; + len = length; + + while (len >= 3) { + a += k[0]; + b += k[1]; + c += k[2]; + __jhash_mix(a, b, c); + k += 3; len -= 3; + } + + c += length * 4; + + switch (len) { + case 2 : b += k[1]; + case 1 : a += k[0]; + }; + + __jhash_mix(a,b,c); + + return c; +} + + +/* A special ultra-optimized versions that knows they are hashing exactly + * 3, 2 or 1 word(s). + * + * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally + * done at the end is not done here. + */ +static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval) +{ + a += JHASH_GOLDEN_RATIO; + b += JHASH_GOLDEN_RATIO; + c += initval; + + __jhash_mix(a, b, c); + + return c; +} + +static inline u32 jhash_2words(u32 a, u32 b, u32 initval) +{ + return jhash_3words(a, b, 0, initval); +} + +static inline u32 jhash_1word(u32 a, u32 initval) +{ + return jhash_3words(a, 0, 0, initval); +} + +#endif /* _LINUX_JHASH_H */ diff --git a/include/ulogd/slist.h b/include/ulogd/slist.h new file mode 100644 index 0000000..3159056 --- /dev/null +++ b/include/ulogd/slist.h @@ -0,0 +1,40 @@ +#ifndef _SLIST_H_ +#define _SLIST_H_ + +#include "linuxlist.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; +} + +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 -- cgit v1.2.3