Skip to contentSkip to conversation

ipt_hashlimit.c: hash only once

PATCH Applied Samuel Jean 3 participants 3 messages Feb 17, 2005 – Feb 22, 2005

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 2/2 ipt_hashlimit.c: hash only once

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]

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.

net/ipv4/netfilter/ipt_hashlimit.c 2005-02-16 23:49:46.000000000 -0500 renamed from net/ipv4/netfilter/ipt_hashlimit.c 2005-02-16 23:31:50.000000000 -0500 +14 -10
@@ -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 */
net/ipv4/netfilter/ipt_hashlimit.c +14 -10
@@ -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 */
#1 lore raw
Quoted 9 lines · Samuel Jean

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]

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

#2 lore raw
In reply to Samuel Jean
Quoted 10 lines · Samuel Jean

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]

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.

Quoted 2 lines

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 ;)

Quoted 2 lines

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.

Signature · 5 lines
- Harald Welte <[email protected]>                 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