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 *,