Improved performance of hash algorithm while (hopefully) not reducing

the quality of the hash distribution. This does not fix a problem dealing
with poor distribution when using lots of IP aliases and listening
on the same port on every one of them...some other day perhaps; fixing
that requires significant code changes.
The use of xor was inspired by David S. Miller <davem@jenolan.rutgers.edu>

7 files changed, 22 insertions, 19 deletions

diff --git a/sys/netinet/in_pcb.c b/sys/netinet/in_pcb.c
index c60cc377..ff2bc30 100644
--- a/sys/netinet/in_pcb.c
+++ b/sys/netinet/in_pcb.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)in_pcb.c	8.4 (Berkeley) 5/24/95
- *	$Id$
+ *	$Id: in_pcb.c,v 1.27 1997/02/22 09:41:29 peter Exp $
  */
 
 #include <sys/param.h>
@@ -686,7 +686,7 @@ in_pcblookuphash(pcbinfo, faddr, fport_arg, laddr, lport_arg, wildcard)
 	/*
 	 * First look for an exact match.
 	 */
-	head = &pcbinfo->hashbase[(faddr.s_addr + lport + fport) % pcbinfo->hashsize];
+	head = &pcbinfo->hashbase[INP_PCBHASH(faddr.s_addr, lport, fport, pcbinfo->hashmask)];
 	for (inp = head->lh_first; inp != NULL; inp = inp->inp_hash.le_next) {
 		if (inp->inp_faddr.s_addr == faddr.s_addr &&
 		    inp->inp_fport == fport && inp->inp_lport == lport &&
@@ -696,7 +696,7 @@ in_pcblookuphash(pcbinfo, faddr, fport_arg, laddr, lport_arg, wildcard)
 	if (wildcard) {
 		struct inpcb *local_wild = NULL;
 
-		head = &pcbinfo->hashbase[(INADDR_ANY + lport) % pcbinfo->hashsize];
+		head = &pcbinfo->hashbase[INP_PCBHASH(INADDR_ANY, lport, 0, pcbinfo->hashmask)];
 		for (inp = head->lh_first; inp != NULL; inp = inp->inp_hash.le_next) {
 			if (inp->inp_faddr.s_addr == INADDR_ANY &&
 			    inp->inp_fport == 0 && inp->inp_lport == lport) {
@@ -738,8 +738,8 @@ in_pcbinshash(inp)
 {
 	struct inpcbhead *head;
 
-	head = &inp->inp_pcbinfo->hashbase[(inp->inp_faddr.s_addr +
-		inp->inp_lport + inp->inp_fport) % inp->inp_pcbinfo->hashsize];
+	head = &inp->inp_pcbinfo->hashbase[INP_PCBHASH(inp->inp_faddr.s_addr,
+		 inp->inp_lport, inp->inp_fport, inp->inp_pcbinfo->hashmask)];
 
 	LIST_INSERT_HEAD(head, inp, inp_hash);
 }
@@ -754,8 +754,8 @@ in_pcbrehash(inp)
 	s = splnet();
 	LIST_REMOVE(inp, inp_hash);
 
-	head = &inp->inp_pcbinfo->hashbase[(inp->inp_faddr.s_addr +
-		inp->inp_lport + inp->inp_fport) % inp->inp_pcbinfo->hashsize];
+	head = &inp->inp_pcbinfo->hashbase[INP_PCBHASH(inp->inp_faddr.s_addr,
+		inp->inp_lport, inp->inp_fport, inp->inp_pcbinfo->hashmask)];
 
 	LIST_INSERT_HEAD(head, inp, inp_hash);
 	splx(s);
diff --git a/sys/netinet/in_pcb.h b/sys/netinet/in_pcb.h
index 1b416f1..6adad91 100644
--- a/sys/netinet/in_pcb.h
+++ b/sys/netinet/in_pcb.h
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)in_pcb.h	8.1 (Berkeley) 6/10/93
- * $Id$
+ * $Id: in_pcb.h,v 1.18 1997/02/22 09:41:29 peter Exp $
  */
 
 #ifndef _NETINET_IN_PCB_H_
@@ -68,12 +68,15 @@ struct inpcb {
 struct inpcbinfo {
 	struct inpcbhead *listhead;
 	struct inpcbhead *hashbase;
-	unsigned long hashsize;
+	unsigned long hashmask;
 	unsigned short lastport;
 	unsigned short lastlow;
 	unsigned short lasthi;
 };
 
+#define INP_PCBHASH(faddr, lport, fport, mask) \
+	(((faddr) ^ ((faddr) >> 16) ^ (lport) ^ (fport)) & (mask))
+
 /* flags in inp_flags: */
 #define	INP_RECVOPTS		0x01	/* receive incoming IP options */
 #define	INP_RECVRETOPTS		0x02	/* receive IP options for reply */
diff --git a/sys/netinet/ip_divert.c b/sys/netinet/ip_divert.c
index 6c0e9c9..8cfd0ff 100644
--- a/sys/netinet/ip_divert.c
+++ b/sys/netinet/ip_divert.c
@@ -30,7 +30,7 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *	$Id$
+ *	$Id: ip_divert.c,v 1.6 1997/02/22 09:41:31 peter Exp $
  */
 
 #include <sys/param.h>
@@ -109,7 +109,7 @@ div_init(void)
 	 * to allocate a one entry hash list than it is to check all
 	 * over the place for hashbase == NULL.
 	 */
-	divcbinfo.hashbase = phashinit(1, M_PCB, &divcbinfo.hashsize);
+	divcbinfo.hashbase = hashinit(1, M_PCB, &divcbinfo.hashmask);
 }
 
 /*
diff --git a/sys/netinet/raw_ip.c b/sys/netinet/raw_ip.c
index e290c5e..7f50216 100644
--- a/sys/netinet/raw_ip.c
+++ b/sys/netinet/raw_ip.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)raw_ip.c	8.7 (Berkeley) 5/15/95
- *	$Id: raw_ip.c,v 1.41 1997/02/13 19:46:45 wollman Exp $
+ *	$Id: raw_ip.c,v 1.42 1997/02/18 20:46:29 wollman Exp $
  */
 
 #include <sys/param.h>
@@ -93,7 +93,7 @@ rip_init()
 	 * to allocate a one entry hash list than it is to check all
 	 * over the place for hashbase == NULL.
 	 */
-	ripcbinfo.hashbase = phashinit(1, M_PCB, &ripcbinfo.hashsize);
+	ripcbinfo.hashbase = hashinit(1, M_PCB, &ripcbinfo.hashmask);
 }
 
 static struct	sockaddr_in ripsrc = { sizeof(ripsrc), AF_INET };
diff --git a/sys/netinet/tcp_subr.c b/sys/netinet/tcp_subr.c
index 9f07fbc..f7b4469 100644
--- a/sys/netinet/tcp_subr.c
+++ b/sys/netinet/tcp_subr.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)tcp_subr.c	8.2 (Berkeley) 5/24/95
- *	$Id$
+ *	$Id: tcp_subr.c,v 1.34 1997/02/22 09:41:41 peter Exp $
  */
 
 #include <sys/param.h>
@@ -107,7 +107,7 @@ tcp_init()
 	tcp_cleartaocache();
 	LIST_INIT(&tcb);
 	tcbinfo.listhead = &tcb;
-	tcbinfo.hashbase = phashinit(TCBHASHSIZE, M_PCB, &tcbinfo.hashsize);
+	tcbinfo.hashbase = hashinit(TCBHASHSIZE, M_PCB, &tcbinfo.hashmask);
 	if (max_protohdr < sizeof(struct tcpiphdr))
 		max_protohdr = sizeof(struct tcpiphdr);
 	if (max_linkhdr + sizeof(struct tcpiphdr) > MHLEN)
diff --git a/sys/netinet/tcp_timewait.c b/sys/netinet/tcp_timewait.c
index 9f07fbc..f7b4469 100644
--- a/sys/netinet/tcp_timewait.c
+++ b/sys/netinet/tcp_timewait.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)tcp_subr.c	8.2 (Berkeley) 5/24/95
- *	$Id$
+ *	$Id: tcp_subr.c,v 1.34 1997/02/22 09:41:41 peter Exp $
  */
 
 #include <sys/param.h>
@@ -107,7 +107,7 @@ tcp_init()
 	tcp_cleartaocache();
 	LIST_INIT(&tcb);
 	tcbinfo.listhead = &tcb;
-	tcbinfo.hashbase = phashinit(TCBHASHSIZE, M_PCB, &tcbinfo.hashsize);
+	tcbinfo.hashbase = hashinit(TCBHASHSIZE, M_PCB, &tcbinfo.hashmask);
 	if (max_protohdr < sizeof(struct tcpiphdr))
 		max_protohdr = sizeof(struct tcpiphdr);
 	if (max_linkhdr + sizeof(struct tcpiphdr) > MHLEN)
diff --git a/sys/netinet/udp_usrreq.c b/sys/netinet/udp_usrreq.c
index 801d93a..56a84ac 100644
--- a/sys/netinet/udp_usrreq.c
+++ b/sys/netinet/udp_usrreq.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)udp_usrreq.c	8.6 (Berkeley) 5/23/95
- *	$Id: udp_usrreq.c,v 1.34 1997/02/18 20:46:36 wollman Exp $
+ *	$Id: udp_usrreq.c,v 1.35 1997/02/24 20:31:25 wollman Exp $
  */
 
 #include <sys/param.h>
@@ -99,7 +99,7 @@ udp_init()
 {
 	LIST_INIT(&udb);
 	udbinfo.listhead = &udb;
-	udbinfo.hashbase = phashinit(UDBHASHSIZE, M_PCB, &udbinfo.hashsize);
+	udbinfo.hashbase = hashinit(UDBHASHSIZE, M_PCB, &udbinfo.hashmask);
 }
 
 void