Re: [PATCH] improvement on net/sched/cls_fw.c's hash function

[Wang Jian <lark@linux.net.cn>]

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

Hi David S. Miller,

New patch attached. Hashsize is 256, the same as old one.


On Mon, 4 Apr 2005 22:37:44 -0700, "David S. Miller" <davem@davemloft.net> wrote:

> On Tue, 05 Apr 2005 13:35:02 +0800
> Wang Jian <lark@linux.net.cn> wrote:
> 
> > https://lists.netfilter.org/pipermail/netfilter-devel/2005-March/018762.html
> > 
> > I chose 509 for FW_FILTER_HSIZE. If you feel it is waste of memory, then
> > 251 is good too.
> 
> Please us a power of two, the "%" is expensive on some cpus.



-- 
  lark

[-- Attachment #2: hash-cls_fw-2.diff --]
[-- Type: application/octet-stream, Size: 1104 bytes --]

Index: linux-2.6.11-w/net/sched/cls_fw.c
===================================================================
--- linux-2.6.11-w/net/sched/cls_fw.c	(revision 1)
+++ linux-2.6.11-w/net/sched/cls_fw.c	(working copy)
@@ -45,10 +45,13 @@
 #include <net/sock.h>
 #include <net/act_api.h>
 #include <net/pkt_cls.h>
+#include <linux/jhash.h>
 
+#define FW_FILTER_HSIZE		256
+
 struct fw_head
 {
-	struct fw_filter *ht[256];
+	struct fw_filter *ht[FW_FILTER_HSIZE];
 };
 
 struct fw_filter
@@ -69,7 +72,7 @@
 
 static __inline__ int fw_hash(u32 handle)
 {
-	return handle&0xFF;
+	return (jhash_1word(handle, 0xF30A7129) % FW_FILTER_HSIZE);
 }
 
 static int fw_classify(struct sk_buff *skb, struct tcf_proto *tp,
@@ -152,7 +155,7 @@
 	if (head == NULL)
 		return;
 
-	for (h=0; h<256; h++) {
+	for (h=0; h<FW_FILTER_HSIZE; h++) {
 		while ((f=head->ht[h]) != NULL) {
 			head->ht[h] = f->next;
 			fw_delete_filter(tp, f);
@@ -291,7 +294,7 @@
 	if (arg->stop)
 		return;
 
-	for (h = 0; h < 256; h++) {
+	for (h = 0; h < FW_FILTER_HSIZE; h++) {
 		struct fw_filter *f;
 
 		for (f = head->ht[h]; f; f = f->next) {