One of the reasons IPsec still requires the KERNEL_LOCK() in the
forwarding path is that it uses the radix tree for the SPD lookup.
Since the radix code is used by other subsystems (NFS export list,
PIPEX, PF) we want it to be able to run on parallel, at least when
callers aren't manipulating the same tree.
That's what the diff below does by getting rid of the globals used
in rn_addmask(). For that we now use a buffer on the stack of the
caller instead of the global ``addmask_key''.
While here I documented other globals, moved local prototypes to the
C file and added a SALEN() macro for readability purpose.
ok?
Index: net/radix.c
===================================================================
RCS file: /cvs/src/sys/net/radix.c,v
retrieving revision 1.56
diff -u -p -r1.56 radix.c
--- net/radix.c 24 Jan 2017 10:08:30 -0000 1.56
+++ net/radix.c 6 Jun 2017 13:23:19 -0000
@@ -48,24 +48,32 @@
#include <net/radix.h>
-static unsigned int max_keylen;
-struct radix_node_head *mask_rnhead;
-static char *addmask_key;
-static char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1};
-static char *rn_zeros, *rn_ones;
+#define SALEN(sa) (*(u_char *)sa)
+
+/*
+ * Read-only variables, allocated & filled during rn_init().
+ */
+static char *rn_zeros; /* array of 0s */
+static char *rn_ones; /* array of 1s */
+static unsigned int max_keylen; /* size of the above arrays */
+#define KEYLEN_LIMIT 64 /* maximum allowed keylen */
-struct pool rtmask_pool; /* pool for radix_mask structures */
-#define rn_masktop (mask_rnhead->rnh_treetop)
+struct radix_node_head *mask_rnhead; /* head of shared mask tree */
+struct pool rtmask_pool; /* pool for radix_mask structures */
+static int rn_refines(void *, void *);
+static int rn_inithead0(struct radix_node_head *, int);
static inline int rn_satisfies_leaf(char *, struct radix_node *, int);
static inline int rn_lexobetter(void *, void *);
static inline struct radix_mask *rn_new_radix_mask(struct radix_node *,
struct radix_mask *);
+struct radix_node *rn_addmask(void *, int, int);
struct radix_node *rn_insert(void *, struct radix_node_head *, int *,
struct radix_node [2]);
struct radix_node *rn_newpair(void *, int, struct radix_node[2]);
+void rn_link_dupedkey(struct radix_node *, struct radix_node *, int);
static inline struct radix_node *rn_search(void *, struct radix_node *);
struct radix_node *rn_search_m(void *, struct radix_node *, void *);
@@ -143,7 +151,7 @@ rn_search_m(void *v_arg, struct radix_no
return x;
}
-int
+static int
rn_refines(void *m_arg, void *n_arg)
{
caddr_t m = m_arg;
@@ -414,8 +422,9 @@ rn_addmask(void *n_arg, int search, int
int b = 0, mlen, j;
int maskduplicated, m0, isnormal;
static int last_zeroed = 0;
+ char addmask_key[KEYLEN_LIMIT];
- if ((mlen = *(u_char *)netmask) > max_keylen)
+ if ((mlen = SALEN(netmask)) > max_keylen)
mlen = max_keylen;
if (skip == 0)
skip = 1;
@@ -439,7 +448,7 @@ rn_addmask(void *n_arg, int search, int
if (m0 < last_zeroed)
memset(addmask_key + m0, 0, last_zeroed - m0);
*addmask_key = last_zeroed = mlen;
- tm = rn_search(addmask_key, rn_masktop);
+ tm = rn_search(addmask_key, mask_rnhead->rnh_treetop);
if (memcmp(addmask_key, tm->rn_key, mlen) != 0)
tm = NULL;
if (tm || search)
@@ -452,7 +461,7 @@ rn_addmask(void *n_arg, int search, int
memcpy(cp, addmask_key, mlen);
tm = rn_insert(cp, mask_rnhead, &maskduplicated, tm);
if (maskduplicated) {
- log(LOG_ERR, "rn_addmask: mask impossibly already in tree\n");
+ log(LOG_ERR, "%s: mask impossibly already in tree\n", __func__);
free(saved_tm, M_RTABLE, 0);
return (tm);
}
@@ -464,6 +473,9 @@ rn_addmask(void *n_arg, int search, int
for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;)
cp++;
if (cp != cplim) {
+ static const char normal_chars[] = {
+ 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1
+ };
for (j = 0x80; (j & *cp) != 0; j >>= 1)
b++;
if (*cp != normal_chars[b] || cp != (cplim - 1))
@@ -488,9 +500,9 @@ rn_lexobetter(void *m_arg, void *n_arg)
* first. The netmasks were normalized before calling this function and
* don't have unneeded trailing zeros.
*/
- if (*mp > *np)
+ if (SALEN(mp) > SALEN(np))
return 1;
- if (*mp < *np)
+ if (SALEN(mp) < SALEN(np))
return 0;
/*
* Must return the first difference between the masks
@@ -756,6 +768,8 @@ rn_addroute(void *v_arg, void *n_arg, st
struct radix_node *tt, *saved_tt, *tm = NULL;
int keyduplicated;
+ KERNEL_ASSERT_LOCKED();
+
/*
* In dealing with non-contiguous masks, there may be
* many different routes which have the same mask.
@@ -905,7 +919,9 @@ rn_delete(void *v_arg, void *n_arg, stru
int off = top->rn_off;
int vlen;
- vlen = *(u_char *)v;
+ KERNEL_ASSERT_LOCKED();
+
+ vlen = SALEN(v);
/*
* Implement a lookup similar to rn_lookup but we need to save
@@ -1050,6 +1066,8 @@ rn_walktree(struct radix_node_head *h, i
int error;
struct radix_node *base, *next;
struct radix_node *rn = h->rnh_treetop;
+
+ KERNEL_ASSERT_LOCKED();
/*
* This gets complicated because we may delete the node
* while applying the function f to it, so we need to calculate
@@ -1116,7 +1134,7 @@ rn_inithead(void **head, int off)
return (1);
}
-int
+static int
rn_inithead0(struct radix_node_head *rnh, int offset)
{
struct radix_node *t, *tt, *ttt;
@@ -1138,13 +1156,15 @@ rn_inithead0(struct radix_node_head *rnh
/*
* rn_init() can be called multiple time with a different key length
- * as long as not radix tree head has been allocated.
+ * as long as no radix tree head has been allocated.
*/
void
rn_init(unsigned int keylen)
{
char *cp, *cplim;
+ KASSERT(keylen <= KEYLEN_LIMIT);
+
if (max_keylen == 0) {
pool_init(&rtmask_pool, sizeof(struct radix_mask), 0,
IPL_SOFTNET, 0, "rtmask", NULL);
@@ -1155,14 +1175,14 @@ rn_init(unsigned int keylen)
KASSERT(mask_rnhead == NULL);
- free(rn_zeros, M_RTABLE, 3 * max_keylen);
- rn_zeros = mallocarray(3, keylen, M_RTABLE, M_NOWAIT | M_ZERO);
+ free(rn_zeros, M_RTABLE, 2 * max_keylen);
+ rn_zeros = mallocarray(2, keylen, M_RTABLE, M_NOWAIT | M_ZERO);
if (rn_zeros == NULL)
panic("cannot initialize a radix tree without memory");
max_keylen = keylen;
- rn_ones = cp = rn_zeros + max_keylen;
- addmask_key = cplim = rn_ones + max_keylen;
+ cp = rn_ones = rn_zeros + max_keylen;
+ cplim = rn_ones + max_keylen;
while (cp < cplim)
*cp++ = -1;
}
Index: net/radix.h
===================================================================
RCS file: /cvs/src/sys/net/radix.h,v
retrieving revision 1.29
diff -u -p -r1.29 radix.h
--- net/radix.h 14 Nov 2016 08:56:12 -0000 1.29
+++ net/radix.h 6 Jun 2017 13:21:56 -0000
@@ -98,14 +98,10 @@ struct radix_node_head {
void rn_init(unsigned int);
int rn_inithead(void **, int);
-int rn_inithead0(struct radix_node_head *, int);
-int rn_refines(void *, void *);
-void rn_link_dupedkey(struct radix_node *, struct radix_node *, int);
int rn_walktree(struct radix_node_head *,
int (*)(struct radix_node *, void *, u_int), void *);
-struct radix_node *rn_addmask(void *, int, int);
struct radix_node *rn_addroute(void *, void *, struct radix_node_head *,
struct radix_node [2], u_int8_t);
struct radix_node *rn_delete(void *, void *, struct radix_node_head *,
