[PATCH 2/2] ipt_hashlimit.c: hash only once

[PATCH 2/2] ipt_hashlimit.c: hash only once

[Samuel Jean]

[-- Attachment #1: Type: text/plain, Size: 3564 bytes --]

Name: hash only once
Status: Tested on Linux 2.6.10.
          Patch against 2.6.11-rc4-bk2
          Incremental to previous hlist_head patch [1/2]
Signed-off-by: Samuel Jean <sjean@cookinglinux.org>

Harald: this patch might be crap.

I couldn't find the reason on why we initialize random seed only on first entry.
Making this obviously mean we hash to find the bucket. If entry's not in there,
we add it. To do so, we need to hash again, because we maybe initialized the seed.

This patch move the seed initializing at hashtable creation. So we can hash only
once to find and create.

Please review and comment. Thanks!

Patch is inlined and attached as I'm dumb and dunno how to inline the attachement.

--- a/net/ipv4/netfilter/ipt_hashlimit.c        2005-02-16 23:31:50.000000000 -0500
+++ b/net/ipv4/netfilter/ipt_hashlimit.c        2005-02-16 23:49:46.000000000 -0500
@@ -114,11 +114,12 @@ hash_dst(const struct ipt_hashlimit_htab
   }

   static inline struct dsthash_ent *
-__dsthash_find(const struct ipt_hashlimit_htable *ht, struct dsthash_dst *dst)
+__dsthash_find(const struct ipt_hashlimit_htable *ht,
+               struct dsthash_dst *dst,
+               u_int32_t hash)
   {
          struct dsthash_ent *ent = NULL;
          struct hlist_node *pos;
-       u_int32_t hash = hash_dst(ht, dst);

          if (!hlist_empty(&ht->hash[hash]))
                  hlist_for_each_entry(ent, pos, &ht->hash[hash], node) {
@@ -132,14 +133,12 @@ __dsthash_find(const struct ipt_hashlimi

   /* allocate dsthash_ent, initialize dst, put in htable and lock it */
   static struct dsthash_ent *
-__dsthash_alloc_init(struct ipt_hashlimit_htable *ht, struct dsthash_dst *dst)
+__dsthash_alloc_init(struct ipt_hashlimit_htable *ht,
+               struct dsthash_dst *dst,
+               u_int32_t hash)
   {
          struct dsthash_ent *ent;

-       /* initialize hash with random val at the time we allocate
-        * the first hashtable entry */
-       if (!ht->rnd)
-               get_random_bytes(&ht->rnd, 4);

          if (ht->cfg.max &&
              atomic_read(&ht->count) >= ht->cfg.max) {
@@ -166,7 +165,7 @@ __dsthash_alloc_init(struct ipt_hashlimi
          ent->dst.src_ip = dst->src_ip;
          ent->dst.src_port = dst->src_port;

-       hlist_add_head(&ent->node, &ht->hash[hash_dst(ht, dst)]);
+       hlist_add_head(&ent->node, &ht->hash[hash]);

          return ent;
   }
@@ -234,6 +233,8 @@ static int htable_create(struct ipt_hash
          hinfo->timer.function = htable_gc;
          add_timer(&hinfo->timer);

+       get_random_bytes(&hinfo->rnd, 4);
+
          LOCK_BH(&hashlimit_lock);
          hlist_add_head(&hinfo->node, &hashlimit_htables);
          UNLOCK_BH(&hashlimit_lock);
@@ -439,6 +440,7 @@ hashlimit_match(const struct sk_buff *sk
          unsigned long now = jiffies;
          struct dsthash_ent *dh;
          struct dsthash_dst dst;
+       u_int32_t hash;

          /* build 'dst' according to hinfo->cfg and current packet */
          memset(&dst, 0, sizeof(dst));
@@ -461,10 +463,12 @@ hashlimit_match(const struct sk_buff *sk
                          dst.dst_port = ports[1];
          }

+       hash = hash_dst(hinfo, &dst);
+
          spin_lock_bh(&hinfo->lock);
-       dh = __dsthash_find(hinfo, &dst);
+       dh = __dsthash_find(hinfo, &dst, hash);
          if (!dh) {
-               dh = __dsthash_alloc_init(hinfo, &dst);
+               dh = __dsthash_alloc_init(hinfo, &dst, hash);

                  if (!dh) {
                          /* enomem... don't match == DROP */



[-- Attachment #2: linux-2.6.11-rc4-bk2-incremental_hash-once.patch --]
[-- Type: text/x-patch, Size: 2432 bytes --]

--- a/net/ipv4/netfilter/ipt_hashlimit.c	2005-02-16 23:31:50.000000000 -0500
+++ b/net/ipv4/netfilter/ipt_hashlimit.c	2005-02-16 23:49:46.000000000 -0500
@@ -114,11 +114,12 @@ hash_dst(const struct ipt_hashlimit_htab
 }
 
 static inline struct dsthash_ent *
-__dsthash_find(const struct ipt_hashlimit_htable *ht, struct dsthash_dst *dst)
+__dsthash_find(const struct ipt_hashlimit_htable *ht,
+		struct dsthash_dst *dst,
+		u_int32_t hash)
 {
 	struct dsthash_ent *ent = NULL;
 	struct hlist_node *pos;
-	u_int32_t hash = hash_dst(ht, dst);
 
 	if (!hlist_empty(&ht->hash[hash]))
 		hlist_for_each_entry(ent, pos, &ht->hash[hash], node) {
@@ -132,14 +133,12 @@ __dsthash_find(const struct ipt_hashlimi
 
 /* allocate dsthash_ent, initialize dst, put in htable and lock it */
 static struct dsthash_ent *
-__dsthash_alloc_init(struct ipt_hashlimit_htable *ht, struct dsthash_dst *dst)
+__dsthash_alloc_init(struct ipt_hashlimit_htable *ht,
+		struct dsthash_dst *dst,
+		u_int32_t hash)
 {
 	struct dsthash_ent *ent;
 
-	/* initialize hash with random val at the time we allocate
-	 * the first hashtable entry */
-	if (!ht->rnd)
-		get_random_bytes(&ht->rnd, 4);
 
 	if (ht->cfg.max &&
 	    atomic_read(&ht->count) >= ht->cfg.max) {
@@ -166,7 +165,7 @@ __dsthash_alloc_init(struct ipt_hashlimi
 	ent->dst.src_ip = dst->src_ip;
 	ent->dst.src_port = dst->src_port;
 
-	hlist_add_head(&ent->node, &ht->hash[hash_dst(ht, dst)]);
+	hlist_add_head(&ent->node, &ht->hash[hash]);
 
 	return ent;
 }
@@ -234,6 +233,8 @@ static int htable_create(struct ipt_hash
 	hinfo->timer.function = htable_gc;
 	add_timer(&hinfo->timer);
 
+	get_random_bytes(&hinfo->rnd, 4);
+
 	LOCK_BH(&hashlimit_lock);
 	hlist_add_head(&hinfo->node, &hashlimit_htables);
 	UNLOCK_BH(&hashlimit_lock);
@@ -439,6 +440,7 @@ hashlimit_match(const struct sk_buff *sk
 	unsigned long now = jiffies;
 	struct dsthash_ent *dh;
 	struct dsthash_dst dst;
+	u_int32_t hash;
 
 	/* build 'dst' according to hinfo->cfg and current packet */
 	memset(&dst, 0, sizeof(dst));
@@ -461,10 +463,12 @@ hashlimit_match(const struct sk_buff *sk
 			dst.dst_port = ports[1];
 	} 
 
+	hash = hash_dst(hinfo, &dst);
+	
 	spin_lock_bh(&hinfo->lock);
-	dh = __dsthash_find(hinfo, &dst);
+	dh = __dsthash_find(hinfo, &dst, hash);
 	if (!dh) {
-		dh = __dsthash_alloc_init(hinfo, &dst);
+		dh = __dsthash_alloc_init(hinfo, &dst, hash);
 
 		if (!dh) {
 			/* enomem... don't match == DROP */

Re: [PATCH 2/2] ipt_hashlimit.c: hash only once

[Pablo Neira]

Samuel Jean wrote:

> Name: hash only once
> Status: Tested on Linux 2.6.10.
>          Patch against 2.6.11-rc4-bk2
>          Incremental to previous hlist_head patch [1/2]
> Signed-off-by: Samuel Jean <sjean@cookinglinux.org>
>
> Harald: this patch might be crap.
>
> I couldn't find the reason on why we initialize random seed only on 
> first entry.


I posted something similar some time ago, please read:

https://lists.netfilter.org/pipermail/netfilter-devel/2004-April/014969.html

--
Pablo

Re: [PATCH 2/2] ipt_hashlimit.c: hash only once

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 2049 bytes --]

On Thu, Feb 17, 2005 at 12:17:38AM -0500, Samuel Jean wrote:
> Name: hash only once
> Status: Tested on Linux 2.6.10.
>          Patch against 2.6.11-rc4-bk2
>          Incremental to previous hlist_head patch [1/2]
> Signed-off-by: Samuel Jean <sjean@cookinglinux.org>
> 
> Harald: this patch might be crap.
> 
> I couldn't find the reason on why we initialize random seed only on first 
> entry.

my reasoning is the same like for the ip_conntrack hash:  We don't have
random seed at immediate system startup.  However, at the point we see
the first packets, we have a higher probability of having collected
entropy.

Not sure whether it can be compared to ip_conntrack, which will create
it's hashtable definitely before any entropy is available when the
module is statically linked.

With ipt_hashlimit, we create the hash table at iptables rule loadtime,
which ideally should be after the rng has gathered some entropy.

On a side note:
The wohle entropy issue in embedded networking is a real problem.  A lot
of devices don't want to limit flash lifetime by writing the random seed
at shutdown into flash and re-read it at startup.  Also, a number of
network drivers doesn't set the SA_RANDOM (or whatever it's called) flag
for the netork interrupts. 

> This patch move the seed initializing at hashtable creation. So we can hash 
> only once to find and create.

I like the optimization, but am still undecided.  Let me first integrate
your hlist changes ;)

> Patch is inlined and attached as I'm dumb and dunno how to inline the 
> attachement.

I personally prefer attachments, and I think it's pretty standard these
days.

-- 
- Harald Welte <laforge@netfilter.org>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]