Author: melifaro
Date: Tue Oct 29 12:53:23 2013
New Revision: 257330
URL: http://svnweb.freebsd.org/changeset/base/257330
Log:
MFC r256624:
Fix long-standing issue with incorrect radix mask calculation.
Usual symptoms are messages like
rn_delete: inconsistent annotation
rn_addmask: mask impossibly already in tree
routing daemon constantly deleting IPv6 default route
or inability to flush/delete particular prefix in ipfw table.
Changes:
* Assume 32 bytes as maximum radix key length
* Remove rn_init()
* Statically allocate rn_ones/rn_zeroes
* Make separate mask tree for each "normal" tree instead of system
global one
* Remove "optimization" on masks reusage and key zeroying
* Change rn_addmask() arguments to accept tree pointer (no users in base)
MFC changes:
* keep rn_init()
* create global mask tree, protected with mutex, for old rn_addmask
users (currently 0 in base)
* Add new rn_addmask_r() function (rn_addmask in head) with additional
argument to accept tree pointer
PR: kern/182851, kern/169206, kern/135476, kern/134531
Found by: Slawa Olhovchenkov <s...@zxy.spb.ru>
Reviewed by: glebius (previous versions)
Sponsored by: Yandex LLC
Approved by: re (glebius)
Modified:
stable/10/sys/net/radix.c
stable/10/sys/net/radix.h
Modified: stable/10/sys/net/radix.c
==============================================================================
--- stable/10/sys/net/radix.c Tue Oct 29 12:34:11 2013 (r257329)
+++ stable/10/sys/net/radix.c Tue Oct 29 12:53:23 2013 (r257330)
@@ -66,27 +66,27 @@ static struct radix_node
*rn_search(void *, struct radix_node *),
*rn_search_m(void *, struct radix_node *, void *);
-static int max_keylen;
-static struct radix_mask *rn_mkfreelist;
-static struct radix_node_head *mask_rnhead;
+static void rn_detachhead_internal(void **head);
+static int rn_inithead_internal(void **head, int off);
+
+#define RADIX_MAX_KEY_LEN 32
+
+static char rn_zeros[RADIX_MAX_KEY_LEN];
+static char rn_ones[RADIX_MAX_KEY_LEN] = {
+ -1, -1, -1, -1, -1, -1, -1, -1,
+ -1, -1, -1, -1, -1, -1, -1, -1,
+ -1, -1, -1, -1, -1, -1, -1, -1,
+ -1, -1, -1, -1, -1, -1, -1, -1,
+};
+
/*
- * Work area -- the following point to 3 buffers of size max_keylen,
- * allocated in this order in a block of memory malloc'ed by rn_init.
- * rn_zeros, rn_ones are set in rn_init and used in readonly afterwards.
- * addmask_key is used in rn_addmask in rw mode and not thread-safe.
+ * XXX: Compat stuff for old rn_addmask() users
*/
-static char *rn_zeros, *rn_ones, *addmask_key;
-
-#define MKGet(m) { \
- if (rn_mkfreelist) { \
- m = rn_mkfreelist; \
- rn_mkfreelist = (m)->rm_mklist; \
- } else \
- R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); }
-
-#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
+static struct radix_node_head *mask_rnhead_compat;
+#ifdef _KERNEL
+static struct mtx mask_mtx;
+#endif
-#define rn_masktop (mask_rnhead->rnh_treetop)
static int rn_lexobetter(void *m_arg, void *n_arg);
static struct radix_mask *
@@ -230,7 +230,8 @@ rn_lookup(v_arg, m_arg, head)
caddr_t netmask = 0;
if (m_arg) {
- x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
+ x = rn_addmask_r(m_arg, head->rnh_masks, 1,
+ head->rnh_treetop->rn_offset);
if (x == 0)
return (0);
netmask = x->rn_key;
@@ -489,53 +490,47 @@ on1:
}
struct radix_node *
-rn_addmask(n_arg, search, skip)
- int search, skip;
- void *n_arg;
+rn_addmask_r(void *arg, struct radix_node_head *maskhead, int search, int skip)
{
- caddr_t netmask = (caddr_t)n_arg;
+ caddr_t netmask = (caddr_t)arg;
register struct radix_node *x;
register caddr_t cp, cplim;
register int b = 0, mlen, j;
- int maskduplicated, m0, isnormal;
+ int maskduplicated, isnormal;
struct radix_node *saved_x;
- static int last_zeroed = 0;
+ char addmask_key[RADIX_MAX_KEY_LEN];
- if ((mlen = LEN(netmask)) > max_keylen)
- mlen = max_keylen;
+ if ((mlen = LEN(netmask)) > RADIX_MAX_KEY_LEN)
+ mlen = RADIX_MAX_KEY_LEN;
if (skip == 0)
skip = 1;
if (mlen <= skip)
- return (mask_rnhead->rnh_nodes);
+ return (maskhead->rnh_nodes);
+
+ bzero(addmask_key, RADIX_MAX_KEY_LEN);
if (skip > 1)
bcopy(rn_ones + 1, addmask_key + 1, skip - 1);
- if ((m0 = mlen) > skip)
- bcopy(netmask + skip, addmask_key + skip, mlen - skip);
+ bcopy(netmask + skip, addmask_key + skip, mlen - skip);
/*
* Trim trailing zeroes.
*/
for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;)
cp--;
mlen = cp - addmask_key;
- if (mlen <= skip) {
- if (m0 >= last_zeroed)
- last_zeroed = mlen;
- return (mask_rnhead->rnh_nodes);
- }
- if (m0 < last_zeroed)
- bzero(addmask_key + m0, last_zeroed - m0);
- *addmask_key = last_zeroed = mlen;
- x = rn_search(addmask_key, rn_masktop);
+ if (mlen <= skip)
+ return (maskhead->rnh_nodes);
+ *addmask_key = mlen;
+ x = rn_search(addmask_key, maskhead->rnh_treetop);
if (bcmp(addmask_key, x->rn_key, mlen) != 0)
x = 0;
if (x || search)
return (x);
- R_Zalloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x));
+ R_Zalloc(x, struct radix_node *, RADIX_MAX_KEY_LEN + 2 * sizeof (*x));
if ((saved_x = x) == 0)
return (0);
netmask = cp = (caddr_t)(x + 2);
bcopy(addmask_key, cp, mlen);
- x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
+ x = rn_insert(cp, maskhead, &maskduplicated, x);
if (maskduplicated) {
log(LOG_ERR, "rn_addmask: mask impossibly already in tree");
Free(saved_x);
@@ -568,6 +563,23 @@ rn_addmask(n_arg, search, skip)
return (x);
}
+struct radix_node *
+rn_addmask(void *n_arg, int search, int skip)
+{
+ struct radix_node *tt;
+
+#ifdef _KERNEL
+ mtx_lock(&mask_mtx);
+#endif
+ tt = rn_addmask_r(&mask_rnhead_compat, n_arg, search, skip);
+
+#ifdef _KERNEL
+ mtx_unlock(&mask_mtx);
+#endif
+
+ return (tt);
+}
+
static int /* XXX: arbitrary ordering for non-contiguous masks */
rn_lexobetter(m_arg, n_arg)
void *m_arg, *n_arg;
@@ -590,12 +602,12 @@ rn_new_radix_mask(tt, next)
{
register struct radix_mask *m;
- MKGet(m);
+ R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask));
if (m == 0) {
- log(LOG_ERR, "Mask for route not entered\n");
+ log(LOG_ERR, "Failed to allocate route mask\n");
return (0);
}
- bzero(m, sizeof *m);
+ bzero(m, sizeof(*m));
m->rm_bit = tt->rn_bit;
m->rm_flags = tt->rn_flags;
if (tt->rn_flags & RNF_NORMAL)
@@ -629,7 +641,8 @@ rn_addroute(v_arg, n_arg, head, treenode
* nodes and possibly save time in calculating indices.
*/
if (netmask) {
- if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0)
+ x = rn_addmask_r(netmask, head->rnh_masks, 0, top->rn_offset);
+ if (x == NULL)
return (0);
b_leaf = x->rn_bit;
b = -1 - x->rn_bit;
@@ -808,7 +821,8 @@ rn_delete(v_arg, netmask_arg, head)
* Delete our route from mask lists.
*/
if (netmask) {
- if ((x = rn_addmask(netmask, 1, head_off)) == 0)
+ x = rn_addmask_r(netmask, head->rnh_masks, 1, head_off);
+ if (x == NULL)
return (0);
netmask = x->rn_key;
while (tt->rn_mask != netmask)
@@ -841,7 +855,7 @@ rn_delete(v_arg, netmask_arg, head)
for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
if (m == saved_m) {
*mp = m->rm_mklist;
- MKFree(m);
+ Free(m);
break;
}
if (m == 0) {
@@ -932,7 +946,7 @@ on1:
struct radix_mask *mm = m->rm_mklist;
x->rn_mklist = 0;
if (--(m->rm_refs) < 0)
- MKFree(m);
+ Free(m);
m = mm;
}
if (m)
@@ -1128,10 +1142,8 @@ rn_walktree(h, f, w)
* bits starting at 'off'.
* Return 1 on success, 0 on error.
*/
-int
-rn_inithead(head, off)
- void **head;
- int off;
+static int
+rn_inithead_internal(void **head, int off)
{
register struct radix_node_head *rnh;
register struct radix_node *t, *tt, *ttt;
@@ -1163,8 +1175,8 @@ rn_inithead(head, off)
return (1);
}
-int
-rn_detachhead(void **head)
+static void
+rn_detachhead_internal(void **head)
{
struct radix_node_head *rnh;
@@ -1176,28 +1188,60 @@ rn_detachhead(void **head)
Free(rnh);
*head = NULL;
+}
+
+int
+rn_inithead(void **head, int off)
+{
+ struct radix_node_head *rnh;
+
+ if (*head != NULL)
+ return (1);
+
+ if (rn_inithead_internal(head, off) == 0)
+ return (0);
+
+ rnh = (struct radix_node_head *)(*head);
+
+ if (rn_inithead_internal((void **)&rnh->rnh_masks, 0) == 0) {
+ rn_detachhead_internal(head);
+ return (0);
+ }
+
+ return (1);
+}
+
+int
+rn_detachhead(void **head)
+{
+ struct radix_node_head *rnh;
+
+ KASSERT((head != NULL && *head != NULL),
+ ("%s: head already freed", __func__));
+
+ rnh = *head;
+
+ rn_detachhead_internal((void **)&rnh->rnh_masks);
+ rn_detachhead_internal(head);
return (1);
}
void
rn_init(int maxk)
{
- char *cp, *cplim;
-
- max_keylen = maxk;
- if (max_keylen == 0) {
+ if ((maxk <= 0) || (maxk > RADIX_MAX_KEY_LEN)) {
log(LOG_ERR,
- "rn_init: radix functions require max_keylen be set\n");
+ "rn_init: max_keylen must be within 1..%d\n",
+ RADIX_MAX_KEY_LEN);
return;
}
- R_Malloc(rn_zeros, char *, 3 * max_keylen);
- if (rn_zeros == NULL)
- panic("rn_init");
- bzero(rn_zeros, 3 * max_keylen);
- rn_ones = cp = rn_zeros + max_keylen;
- addmask_key = cplim = rn_ones + max_keylen;
- while (cp < cplim)
- *cp++ = -1;
- if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0)
+
+ /*
+ * XXX: Compat for old rn_addmask() users
+ */
+ if (rn_inithead((void **)(void *)&mask_rnhead_compat, 0) == 0)
panic("rn_init 2");
+#ifdef _KERNEL
+ mtx_init(&mask_mtx, "radix_mask", NULL, MTX_DEF);
+#endif
}
Modified: stable/10/sys/net/radix.h
==============================================================================
--- stable/10/sys/net/radix.h Tue Oct 29 12:34:11 2013 (r257329)
+++ stable/10/sys/net/radix.h Tue Oct 29 12:53:23 2013 (r257330)
@@ -136,6 +136,7 @@ struct radix_node_head {
#ifdef _KERNEL
struct rwlock rnh_lock; /* locks entire radix tree */
#endif
+ struct radix_node_head *rnh_masks; /* Storage for our masks */
};
#ifndef _KERNEL
@@ -167,6 +168,7 @@ int rn_detachhead(void **);
int rn_refines(void *, void *);
struct radix_node
*rn_addmask(void *, int, int),
+ *rn_addmask_r(void *, struct radix_node_head *, int, int),
*rn_addroute (void *, void *, struct radix_node_head *,
struct radix_node [2]),
*rn_delete(void *, void *, struct radix_node_head *),
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
