Module Name: src
Committed By: martin
Date: Wed Apr 18 14:06:24 UTC 2018
Modified Files:
src/sys/netipsec [netbsd-8]: key.c keydb.h
Log Message:
Pull up following revision(s) (requested by yamaguchi in ticket #776):
sys/netipsec/key.c: revision 1.251-1.253
sys/netipsec/keydb.h: revision 1.22
Introduced a hash table to sahlist
An saidx of sah included in the list is unique so that
the search can use a hash list whose hash is calculated by
the saidx to find an sah quickly.
The hash list of the sahlits is used in FreeBSD, too.
reviewed by ozaki-r@n.o, thanks.
Added a lookup table to find an sav quickly
key_sad.sahlists doesn't work well for inbound packets because
its key includes source address. For the reason, the
look-up-table for the inbound packets is newly added.
The table has all sav whose state is MATURE or DYING and uses a
key calculated by destination address, protocol, and spi instead
of saidx.
reviewd ozaki-r@n.o, thanks.
Fix panic of SADB when the state of sav is changed in timeout
pointed out by ozaki-r@n.o, thanks
To generate a diff of this commit:
cvs rdiff -u -r1.163.2.8 -r1.163.2.9 src/sys/netipsec/key.c
cvs rdiff -u -r1.15.2.2 -r1.15.2.3 src/sys/netipsec/keydb.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/netipsec/key.c
diff -u src/sys/netipsec/key.c:1.163.2.8 src/sys/netipsec/key.c:1.163.2.9
--- src/sys/netipsec/key.c:1.163.2.8 Mon Apr 16 14:31:44 2018
+++ src/sys/netipsec/key.c Wed Apr 18 14:06:24 2018
@@ -1,4 +1,4 @@
-/* $NetBSD: key.c,v 1.163.2.8 2018/04/16 14:31:44 martin Exp $ */
+/* $NetBSD: key.c,v 1.163.2.9 2018/04/18 14:06:24 martin Exp $ */
/* $FreeBSD: src/sys/netipsec/key.c,v 1.3.2.3 2004/02/14 22:23:23 bms Exp $ */
/* $KAME: key.c,v 1.191 2001/06/27 10:46:49 sakane Exp $ */
@@ -32,7 +32,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: key.c,v 1.163.2.8 2018/04/16 14:31:44 martin Exp $");
+__KERNEL_RCSID(0, "$NetBSD: key.c,v 1.163.2.9 2018/04/18 14:06:24 martin Exp $");
/*
* This code is referred to RFC 2367
@@ -72,6 +72,7 @@ __KERNEL_RCSID(0, "$NetBSD: key.c,v 1.16
#include <sys/condvar.h>
#include <sys/localcount.h>
#include <sys/pserialize.h>
+#include <sys/hash.h>
#include <net/if.h>
#include <net/route.h>
@@ -122,6 +123,14 @@ __KERNEL_RCSID(0, "$NetBSD: key.c,v 1.16
#define PORT_LOOSE 1
#define PORT_STRICT 2
+#ifndef SAHHASH_NHASH
+#define SAHHASH_NHASH 128
+#endif
+
+#ifndef SAVLUT_NHASH
+#define SAVLUT_NHASH 128
+#endif
+
percpu_t *pfkeystat_percpu;
/*
@@ -204,20 +213,23 @@ static u_int32_t acq_seq = 0;
/*
* Locking notes on SAD:
* - Data structures
- * - SAs are managed by the list called key_sad.sahlist and sav lists of sah
- * entries
+ * - SAs are managed by the list called key_sad.sahlists and sav lists of
+ * sah entries
* - An sav is supposed to be an SA from a viewpoint of users
* - A sah has sav lists for each SA state
- * - Multiple sahs with the same saidx can exist
+ * - Multiple saves with the same saidx can exist
* - Only one entry has MATURE state and others should be DEAD
* - DEAD entries are just ignored from searching
- * - Modifications to the key_sad.sahlist and sah.savlist must be done with
- * holding key_sad.lock which is a adaptive mutex
- * - Read accesses to the key_sad.sahlist and sah.savlist must be in
- * pserialize(9) read sections
+ * - All sav whose state is MATURE or DYING are registered to the lookup
+ * table called key_sad.savlut in addition to the savlists.
+ * - The table is used to search an sav without use of saidx.
+ * - Modifications to the key_sad.sahlists, sah.savlist and key_sad.savlut
+ * must be done with holding key_sad.lock which is a adaptive mutex
+ * - Read accesses to the key_sad.sahlists, sah.savlist and key_sad.savlut
+ * must be in pserialize(9) read sections
* - sah's lifetime is managed by localcount(9)
* - Getting an sah entry
- * - We get an sah from the key_sad.sahlist
+ * - We get an sah from the key_sad.sahlists
* - Must iterate the list and increment the reference count of a found sah
* (by key_sah_ref) in a pserialize read section
* - A gotten sah must be released after use by key_sah_unref
@@ -261,7 +273,10 @@ static struct {
static struct {
kmutex_t lock;
kcondvar_t cv_lc;
- struct pslist_head sahlist;
+ struct pslist_head *sahlists;
+ u_long sahlistmask;
+ struct pslist_head *savlut;
+ u_long savlutmask;
pserialize_t psz;
kcondvar_t cv_psz;
@@ -341,13 +356,23 @@ static struct {
#define SAHLIST_WRITER_REMOVE(sah) \
PSLIST_WRITER_REMOVE((sah), pslist_entry)
#define SAHLIST_READER_FOREACH(sah) \
- PSLIST_READER_FOREACH((sah), &key_sad.sahlist, struct secashead,\
- pslist_entry)
+ for(int _i_sah = 0; _i_sah <= key_sad.sahlistmask; _i_sah++) \
+ PSLIST_READER_FOREACH((sah), &key_sad.sahlists[_i_sah], \
+ struct secashead, pslist_entry)
+#define SAHLIST_READER_FOREACH_SAIDX(sah, saidx) \
+ PSLIST_READER_FOREACH((sah), \
+ &key_sad.sahlists[key_saidxhash((saidx), \
+ key_sad.sahlistmask)], \
+ struct secashead, pslist_entry)
#define SAHLIST_WRITER_FOREACH(sah) \
- PSLIST_WRITER_FOREACH((sah), &key_sad.sahlist, struct secashead,\
- pslist_entry)
+ for(int _i_sah = 0; _i_sah <= key_sad.sahlistmask; _i_sah++) \
+ PSLIST_WRITER_FOREACH((sah), &key_sad.sahlists[_i_sah], \
+ struct secashead, pslist_entry)
#define SAHLIST_WRITER_INSERT_HEAD(sah) \
- PSLIST_WRITER_INSERT_HEAD(&key_sad.sahlist, (sah), pslist_entry)
+ PSLIST_WRITER_INSERT_HEAD( \
+ &key_sad.sahlists[key_saidxhash(&(sah)->saidx, \
+ key_sad.sahlistmask)], \
+ (sah), pslist_entry)
/* Macros for key_sad.sahlist#savlist */
#define SAVLIST_ENTRY_INIT(sav) \
@@ -395,6 +420,23 @@ static struct {
#define SAVLIST_READER_NEXT(sav) \
PSLIST_READER_NEXT((sav), struct secasvar, pslist_entry)
+/* Macros for key_sad.savlut */
+#define SAVLUT_ENTRY_INIT(sav) \
+ PSLIST_ENTRY_INIT((sav), pslist_entry_savlut)
+#define SAVLUT_READER_FOREACH(sav, dst, proto, hash_key) \
+ PSLIST_READER_FOREACH((sav), \
+ &key_sad.savlut[key_savluthash(dst, proto, hash_key, \
+ key_sad.savlutmask)], \
+ struct secasvar, pslist_entry_savlut)
+#define SAVLUT_WRITER_INSERT_HEAD(sav) \
+ key_savlut_writer_insert_head((sav))
+#define SAVLUT_WRITER_REMOVE(sav) \
+ do { \
+ if (!(sav)->savlut_added) \
+ break; \
+ PSLIST_WRITER_REMOVE((sav), pslist_entry_savlut); \
+ (sav)->savlut_added = false; \
+ } while(0)
/* search order for SAs */
/*
@@ -794,6 +836,14 @@ static struct callout key_timehandler_ch
static struct workqueue *key_timehandler_wq;
static struct work key_timehandler_wk;
+static inline void
+ key_savlut_writer_insert_head(struct secasvar *sav);
+static inline uint32_t
+ key_saidxhash(const struct secasindex *, u_long);
+static inline uint32_t
+ key_savluthash(const struct sockaddr *,
+ uint32_t, uint32_t, u_long);
+
/*
* Utilities for percpu counters for sadb_lifetime_allocations and
* sadb_lifetime_bytes.
@@ -1203,9 +1253,7 @@ key_lookup_sa(
u_int16_t dport,
const char* where, int tag)
{
- struct secashead *sah;
struct secasvar *sav;
- u_int state;
int chkport;
int s;
@@ -1213,6 +1261,7 @@ key_lookup_sa(
int must_check_alg = 0;
u_int16_t cpi = 0;
u_int8_t algo = 0;
+ uint32_t hash_key = spi;
if ((sport != 0) && (dport != 0))
chkport = PORT_STRICT;
@@ -1235,6 +1284,7 @@ key_lookup_sa(
cpi = (u_int16_t) tmp;
if (cpi < IPCOMP_CPI_NEGOTIATE_MIN) {
algo = (u_int8_t) cpi;
+ hash_key = algo;
must_check_spi = 0;
must_check_alg = 1;
}
@@ -1251,57 +1301,51 @@ key_lookup_sa(
* encrypted so we can't check internal IP header.
*/
s = pserialize_read_enter();
- SAHLIST_READER_FOREACH(sah) {
- /* search valid state */
- SASTATE_USABLE_FOREACH(state) {
- SAVLIST_READER_FOREACH(sav, sah, state) {
- KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
- "try match spi %#x, %#x\n",
- ntohl(spi), ntohl(sav->spi));
- /* sanity check */
- KEY_CHKSASTATE(sav->state, state);
- /* do not return entries w/ unusable state */
- if (!SADB_SASTATE_USABLE_P(sav)) {
- KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
- "bad state %d\n", sav->state);
- continue;
- }
- if (proto != sav->sah->saidx.proto) {
- KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
- "proto fail %d != %d\n",
- proto, sav->sah->saidx.proto);
- continue;
- }
- if (must_check_spi && spi != sav->spi) {
- KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
- "spi fail %#x != %#x\n",
- ntohl(spi), ntohl(sav->spi));
- continue;
- }
- /* XXX only on the ipcomp case */
- if (must_check_alg && algo != sav->alg_comp) {
- KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
- "algo fail %d != %d\n",
- algo, sav->alg_comp);
- continue;
- }
+ SAVLUT_READER_FOREACH(sav, &dst->sa, proto, hash_key) {
+ KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
+ "try match spi %#x, %#x\n",
+ ntohl(spi), ntohl(sav->spi));
+
+ /* do not return entries w/ unusable state */
+ if (!SADB_SASTATE_USABLE_P(sav)) {
+ KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
+ "bad state %d\n", sav->state);
+ continue;
+ }
+ if (proto != sav->sah->saidx.proto) {
+ KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
+ "proto fail %d != %d\n",
+ proto, sav->sah->saidx.proto);
+ continue;
+ }
+ if (must_check_spi && spi != sav->spi) {
+ KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
+ "spi fail %#x != %#x\n",
+ ntohl(spi), ntohl(sav->spi));
+ continue;
+ }
+ /* XXX only on the ipcomp case */
+ if (must_check_alg && algo != sav->alg_comp) {
+ KEYDEBUG_PRINTF(KEYDEBUG_MATCH,
+ "algo fail %d != %d\n",
+ algo, sav->alg_comp);
+ continue;
+ }
#if 0 /* don't check src */
/* Fix port in src->sa */
- /* check src address */
- if (!key_sockaddr_match(&src->sa, &sav->sah->saidx.src.sa, PORT_NONE))
- continue;
+ /* check src address */
+ if (!key_sockaddr_match(&src->sa, &sav->sah->saidx.src.sa, PORT_NONE))
+ continue;
#endif
- /* fix port of dst address XXX*/
- key_porttosaddr(__UNCONST(dst), dport);
- /* check dst address */
- if (!key_sockaddr_match(&dst->sa, &sav->sah->saidx.dst.sa, chkport))
- continue;
- key_sa_ref(sav, where, tag);
- goto done;
- }
- }
+ /* fix port of dst address XXX*/
+ key_porttosaddr(__UNCONST(dst), dport);
+ /* check dst address */
+ if (!key_sockaddr_match(&dst->sa, &sav->sah->saidx.dst.sa, chkport))
+ continue;
+ key_sa_ref(sav, where, tag);
+ goto done;
}
sav = NULL;
done:
@@ -1393,6 +1437,7 @@ key_init_sav(struct secasvar *sav)
localcount_init(&sav->localcount);
SAVLIST_ENTRY_INIT(sav);
+ SAVLUT_ENTRY_INIT(sav);
}
u_int
@@ -1531,6 +1576,7 @@ key_unlink_sav(struct secasvar *sav)
KASSERT(mutex_owned(&key_sad.lock));
SAVLIST_WRITER_REMOVE(sav);
+ SAVLUT_WRITER_REMOVE(sav);
KDASSERT(mutex_ownable(softnet_lock));
key_sad_pserialize_perform();
@@ -1566,6 +1612,7 @@ key_destroy_sav_with_ref(struct secasvar
mutex_enter(&key_sad.lock);
sav->state = SADB_SASTATE_DEAD;
SAVLIST_WRITER_REMOVE(sav);
+ SAVLUT_WRITER_REMOVE(sav);
mutex_exit(&key_sad.lock);
/* We cannot unref with holding key_sad.lock */
@@ -3367,7 +3414,7 @@ key_getsah(const struct secasindex *said
{
struct secashead *sah;
- SAHLIST_READER_FOREACH(sah) {
+ SAHLIST_READER_FOREACH_SAIDX(sah, saidx) {
if (sah->state == SADB_SASTATE_DEAD)
continue;
if (key_saidx_match(&sah->saidx, saidx, flag))
@@ -5700,6 +5747,7 @@ key_api_update(struct socket *so, struct
newsav->state = SADB_SASTATE_MATURE;
mutex_enter(&key_sad.lock);
SAVLIST_WRITER_INSERT_TAIL(sah, SADB_SASTATE_MATURE, newsav);
+ SAVLUT_WRITER_INSERT_HEAD(newsav);
mutex_exit(&key_sad.lock);
key_validate_savlist(sah, SADB_SASTATE_MATURE);
@@ -5897,6 +5945,7 @@ key_api_add(struct socket *so, struct mb
newsav->state = SADB_SASTATE_MATURE;
mutex_enter(&key_sad.lock);
SAVLIST_WRITER_INSERT_TAIL(sah, SADB_SASTATE_MATURE, newsav);
+ SAVLUT_WRITER_INSERT_HEAD(newsav);
mutex_exit(&key_sad.lock);
key_validate_savlist(sah, SADB_SASTATE_MATURE);
@@ -8091,7 +8140,10 @@ key_do_init(void)
PSLIST_INIT(&key_spd.socksplist);
- PSLIST_INIT(&key_sad.sahlist);
+ key_sad.sahlists = hashinit(SAHHASH_NHASH, HASH_PSLIST, true,
+ &key_sad.sahlistmask);
+ key_sad.savlut = hashinit(SAVLUT_NHASH, HASH_PSLIST, true,
+ &key_sad.savlutmask);
for (i = 0; i <= SADB_SATYPE_MAX; i++) {
LIST_INIT(&key_misc.reglist[i]);
@@ -8335,6 +8387,9 @@ key_sa_chgstate(struct secasvar *sav, u_
if (_sav == NULL) {
SAVLIST_WRITER_INSERT_TAIL(sav->sah, state, sav);
}
+
+ SAVLUT_WRITER_INSERT_HEAD(sav);
+
key_validate_savlist(sav->sah, state);
}
@@ -8537,6 +8592,99 @@ key_update_used(void)
}
}
+static inline void
+key_savlut_writer_insert_head(struct secasvar *sav)
+{
+ uint32_t hash_key;
+ uint32_t hash;
+
+ KASSERT(mutex_owned(&key_sad.lock));
+ KASSERT(!sav->savlut_added);
+
+ if (sav->sah->saidx.proto == IPPROTO_IPCOMP)
+ hash_key = sav->alg_comp;
+ else
+ hash_key = sav->spi;
+
+ hash = key_savluthash(&sav->sah->saidx.dst.sa,
+ sav->sah->saidx.proto, hash_key, key_sad.savlutmask);
+
+ PSLIST_WRITER_INSERT_HEAD(&key_sad.savlut[hash], sav,
+ pslist_entry_savlut);
+ sav->savlut_added = true;
+}
+
+/*
+ * Calculate hash using protocol, source address,
+ * and destination address included in saidx.
+ */
+static inline uint32_t
+key_saidxhash(const struct secasindex *saidx, u_long mask)
+{
+ uint32_t hash32;
+ const struct sockaddr_in *sin;
+ const struct sockaddr_in6 *sin6;
+
+ hash32 = saidx->proto;
+
+ switch (saidx->src.sa.sa_family) {
+ case AF_INET:
+ sin = &saidx->src.sin;
+ hash32 = hash32_buf(&sin->sin_addr,
+ sizeof(sin->sin_addr), hash32);
+ sin = &saidx->dst.sin;
+ hash32 = hash32_buf(&sin->sin_addr,
+ sizeof(sin->sin_addr), hash32 << 1);
+ break;
+ case AF_INET6:
+ sin6 = &saidx->src.sin6;
+ hash32 = hash32_buf(&sin6->sin6_addr,
+ sizeof(sin6->sin6_addr), hash32);
+ sin6 = &saidx->dst.sin6;
+ hash32 = hash32_buf(&sin6->sin6_addr,
+ sizeof(sin6->sin6_addr), hash32 << 1);
+ break;
+ default:
+ hash32 = 0;
+ break;
+ }
+
+ return hash32 & mask;
+}
+
+/*
+ * Calculate hash using destination address, protocol,
+ * and spi. Those parameter depend on the search of
+ * key_lookup_sa().
+ */
+static uint32_t
+key_savluthash(const struct sockaddr *dst, uint32_t proto,
+ uint32_t spi, u_long mask)
+{
+ uint32_t hash32;
+ const struct sockaddr_in *sin;
+ const struct sockaddr_in6 *sin6;
+
+ hash32 = hash32_buf(&proto, sizeof(proto), spi);
+
+ switch(dst->sa_family) {
+ case AF_INET:
+ sin = satocsin(dst);
+ hash32 = hash32_buf(&sin->sin_addr,
+ sizeof(sin->sin_addr), hash32);
+ break;
+ case AF_INET6:
+ sin6 = satocsin6(dst);
+ hash32 = hash32_buf(&sin6->sin6_addr,
+ sizeof(sin6->sin6_addr), hash32);
+ break;
+ default:
+ hash32 = 0;
+ }
+
+ return hash32 & mask;
+}
+
static int
sysctl_net_key_dumpsa(SYSCTLFN_ARGS)
{
Index: src/sys/netipsec/keydb.h
diff -u src/sys/netipsec/keydb.h:1.15.2.2 src/sys/netipsec/keydb.h:1.15.2.3
--- src/sys/netipsec/keydb.h:1.15.2.2 Wed Mar 7 13:46:41 2018
+++ src/sys/netipsec/keydb.h Wed Apr 18 14:06:24 2018
@@ -1,4 +1,4 @@
-/* $NetBSD: keydb.h,v 1.15.2.2 2018/03/07 13:46:41 martin Exp $ */
+/* $NetBSD: keydb.h,v 1.15.2.3 2018/04/18 14:06:24 martin Exp $ */
/* $FreeBSD: src/sys/netipsec/keydb.h,v 1.1.4.1 2003/01/24 05:11:36 sam Exp $ */
/* $KAME: keydb.h,v 1.14 2000/08/02 17:58:26 sakane Exp $ */
@@ -95,7 +95,9 @@ struct comp_algo;
/* Security Association */
struct secasvar {
struct pslist_entry pslist_entry;
+ struct pslist_entry pslist_entry_savlut;
struct localcount localcount; /* reference count */
+ bool savlut_added; /* Status of registration of the LUT */
u_int8_t state; /* Status of this Association */
