On 09/06/17(Fri) 15:46, Alexander Bluhm wrote:
> On Fri, Jun 09, 2017 at 03:11:05PM +0200, Martin Pieuchot wrote:
> > > The static variable last_zeroed does not look MP safe. If I get
> > > this code correctly it is only an optimization to avoid multiple
> > > zeroing in addmask_key. This does not work anyway with addmask_key
> > > on the stack.
> >
> > You're right, I removed the 'static'.
>
> As last_zeroed is always 0 now, there is dead code left over.
> I think this variable should be killed.
I agree.
> > @@ -438,8 +447,8 @@ 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);
> > + SALEN(addmask_key) = mlen;
>
> This assumes that addmask_key has been zeroed in rn_init().
> I think now it must be
> memset(addmask_key + m0, 0, sizeof(addmask_key) - m0);
> Maybe the sizeof(addmask_key) could be optimized by using mlen
> or max_keylen instead.
I couldn't convince myself that rn_search() do not check bits
after 'mlen' so I added the memset() as you suggested.
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 9 Jun 2017 14:04:12 -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))
-struct pool rtmask_pool; /* pool for radix_mask structures */
+/*
+ * 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 */
-#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 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 *);
+int rn_refines(void *, void *);
+int rn_inithead0(struct radix_node_head *, int);
+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 *);
@@ -413,9 +421,9 @@ rn_addmask(void *n_arg, int search, int
caddr_t cp, cplim;
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;
@@ -432,14 +440,10 @@ rn_addmask(void *n_arg, int search, int
cp--;
mlen = cp - addmask_key;
if (mlen <= skip) {
- if (m0 >= last_zeroed)
- last_zeroed = mlen;
return (mask_rnhead->rnh_nodes);
}
- if (m0 < last_zeroed)
- memset(addmask_key + m0, 0, last_zeroed - m0);
- *addmask_key = last_zeroed = mlen;
- tm = rn_search(addmask_key, rn_masktop);
+ SALEN(addmask_key) = mlen;
+ 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 +456,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 +468,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 +495,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 +763,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 +914,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 +1061,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
@@ -1138,13 +1151,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 +1170,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 *,
