[src/trunk]: src/sys/netkey 2^n hash table is better in the kernel. advise b...

[itojun <itojun%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/5aa36b10b201
branches:  trunk
changeset: 551935:5aa36b10b201
user:      itojun <itojun%NetBSD.org@localhost>
date:      Sun Sep 14 07:30:32 2003 +0000

description:
2^n hash table is better in the kernel.  advise by perry@netbsd

diffstat:

 sys/netkey/key.c |  19 ++++++++++---------
 1 files changed, 10 insertions(+), 9 deletions(-)

diffs (82 lines):

diff -r 2dc4e9cd6730 -r 5aa36b10b201 sys/netkey/key.c
--- a/sys/netkey/key.c  Sun Sep 14 07:14:28 2003 +0000
+++ b/sys/netkey/key.c  Sun Sep 14 07:30:32 2003 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: key.c,v 1.98 2003/09/14 03:11:31 itojun Exp $  */
+/*     $NetBSD: key.c,v 1.99 2003/09/14 07:30:32 itojun Exp $  */
 /*     $KAME: key.c,v 1.310 2003/09/08 02:23:44 itojun Exp $   */
 
 /*
@@ -35,7 +35,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: key.c,v 1.98 2003/09/14 03:11:31 itojun Exp $");
+__KERNEL_RCSID(0, "$NetBSD: key.c,v 1.99 2003/09/14 07:30:32 itojun Exp $");
 
 #include "opt_inet.h"
 #include "opt_ipsec.h"
@@ -147,7 +147,8 @@
 static LIST_HEAD(_regtree, secreg) regtree[SADB_SATYPE_MAX + 1];
                                                        /* registed list */
 
-#define SPIHASHSIZE    131     /* prime */
+#define SPIHASHSIZE    128
+#define        SPIHASH(x)      (((x) ^ ((x) >> 16)) % SPIHASHSIZE)
 static LIST_HEAD(_spihash, secasvar) spihash[SPIHASHSIZE];
 
 #ifndef IPSEC_NONBLOCK_ACQUIRE
@@ -751,7 +752,7 @@
        /* search valid state */
        match = NULL;
        matchidx = _ARRAYLEN(saorder_state_valid);
-       LIST_FOREACH(sav, &spihash[spi % SPIHASHSIZE], spihash) {
+       LIST_FOREACH(sav, &spihash[SPIHASH(spi)], spihash) {
                if (sav->spi != spi)
                        continue;
                if (proto != sav->sah->saidx.proto)
@@ -2837,7 +2838,7 @@
        }
 
        /* check all SAD */
-       LIST_FOREACH(sav, &spihash[spi % SPIHASHSIZE], spihash) {
+       LIST_FOREACH(sav, &spihash[SPIHASH(spi)], spihash) {
                if (sav->spi != spi)
                        continue;
                for (stateidx = 0;
@@ -2864,7 +2865,7 @@
        sav->spi = spi;
        if (sav->spihash.le_prev || sav->spihash.le_next)
                LIST_REMOVE(sav, spihash);
-       LIST_INSERT_HEAD(&spihash[spi % SPIHASHSIZE], sav, spihash);
+       LIST_INSERT_HEAD(&spihash[SPIHASH(spi)], sav, spihash);
        splx(s);
 }
 
@@ -2884,7 +2885,7 @@
 
        match = NULL;
        matchidx = _ARRAYLEN(saorder_state_alive);
-       LIST_FOREACH(sav, &spihash[spi % SPIHASHSIZE], spihash) {
+       LIST_FOREACH(sav, &spihash[SPIHASH(spi)], spihash) {
                if (sav->spi != spi)
                        continue;
                if (sav->sah != sah)
@@ -6962,7 +6963,7 @@
        int cnt;
 
        cnt = 0;
-       LIST_FOREACH(sav, &spihash[spi % SPIHASHSIZE], spihash) {
+       LIST_FOREACH(sav, &spihash[SPIHASH(spi)], spihash) {
                if (sav->spi != spi)
                        continue;
                cnt++;
@@ -6972,7 +6973,7 @@
                return (NULL);
 
        m = NULL;
-       LIST_FOREACH(sav, &spihash[spi % SPIHASHSIZE], spihash) {
+       LIST_FOREACH(sav, &spihash[SPIHASH(spi)], spihash) {
                if (sav->spi != spi)
                        continue;
                satype = key_proto2satype(sav->sah->saidx.proto);