ipt_hashlimit.c: hash only once
Subsystems (2)
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 *skunsigned 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 */
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 previoushlist_headpatch [1/2]Signed-off-by Samuel Jean <[email protected]>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
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 previoushlist_headpatch [1/2]Signed-off-by Samuel Jean <[email protected]>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