Comment 1 Mark Linimon 2009-05-15 00:05:22 UTC

Responsible Changed
From-To: freebsd-bugs->freebsd-net

Over to maintainer(s).

Comment 2 dfilter service 2013-10-16 13:18:58 UTC

Author: melifaro
Date: Wed Oct 16 12:18:44 2013
New Revision: 256624
URL: http://svnweb.freebsd.org/changeset/base/256624

Log:
  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
  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)
  
  PR:		kern/182851, kern/169206, kern/135476, kern/134531
  Found by:	Slawa Olhovchenkov <slw@zxy.spb.ru>
  MFC after:	2 weeks
  Reviewed by:	glebius
  Sponsored by:	Yandex LLC

Modified:
  head/sys/net/radix.c
  head/sys/net/radix.h
  head/sys/net/route.c

Modified: head/sys/net/radix.c
==============================================================================
--- head/sys/net/radix.c	Wed Oct 16 12:15:33 2013	(r256623)
+++ head/sys/net/radix.c	Wed Oct 16 12:18:44 2013	(r256624)
@@ -66,27 +66,19 @@ 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;
-/*
- * 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.
- */
-static char *rn_zeros, *rn_ones, *addmask_key;
+static void rn_detachhead_internal(void **head);
+static int rn_inithead_internal(void **head, int off);
+
+#define	RADIX_MAX_KEY_LEN	32
 
-#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 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,
+};
 
-#define rn_masktop (mask_rnhead->rnh_treetop)
 
 static int	rn_lexobetter(void *m_arg, void *n_arg);
 static struct radix_mask *
@@ -230,7 +222,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(m_arg, head->rnh_masks, 1,
+		    head->rnh_treetop->rn_offset);
 		if (x == 0)
 			return (0);
 		netmask = x->rn_key;
@@ -489,53 +482,47 @@ on1:
 }
 
 struct radix_node *
-rn_addmask(n_arg, search, skip)
-	int search, skip;
-	void *n_arg;
+rn_addmask(void *n_arg, struct radix_node_head *maskhead, int search, int skip)
 {
 	caddr_t netmask = (caddr_t)n_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);
@@ -590,12 +577,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 +616,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(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 +796,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(netmask, head->rnh_masks, 1, head_off);
+		if (x == NULL)
 			return (0);
 		netmask = x->rn_key;
 		while (tt->rn_mask != netmask)
@@ -841,7 +830,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 +921,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 +1117,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 +1150,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 +1163,41 @@ 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);
 }
 
-void
-rn_init(int maxk)
+int
+rn_detachhead(void **head)
 {
-	char *cp, *cplim;
+	struct radix_node_head *rnh;
 
-	max_keylen = maxk;
-	if (max_keylen == 0) {
-		log(LOG_ERR,
-		    "rn_init: radix functions require max_keylen be set\n");
-		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)
-		panic("rn_init 2");
+	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);
 }
+

Modified: head/sys/net/radix.h
==============================================================================
--- head/sys/net/radix.h	Wed Oct 16 12:15:33 2013	(r256623)
+++ head/sys/net/radix.h	Wed Oct 16 12:18:44 2013	(r256624)
@@ -124,6 +124,7 @@ struct radix_node_head {
 	void	(*rnh_close)	/* do something when the last ref drops */
 		(struct radix_node *rn, struct radix_node_head *head);
 	struct	radix_node rnh_nodes[3];	/* empty tree for common case */
+	struct	radix_node_head *rnh_masks;	/* Storage for our masks */
 #ifdef _KERNEL
 	struct	rwlock rnh_lock;		/* locks entire radix tree */
 #endif
@@ -152,12 +153,11 @@ struct radix_node_head {
 #define	RADIX_NODE_HEAD_WLOCK_ASSERT(rnh) rw_assert(&(rnh)->rnh_lock, RA_WLOCKED)
 #endif /* _KERNEL */
 
-void	 rn_init(int);
 int	 rn_inithead(void **, int);
 int	 rn_detachhead(void **);
 int	 rn_refines(void *, void *);
 struct radix_node
-	 *rn_addmask(void *, int, int),
+	 *rn_addmask(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 *),

Modified: head/sys/net/route.c
==============================================================================
--- head/sys/net/route.c	Wed Oct 16 12:15:33 2013	(r256623)
+++ head/sys/net/route.c	Wed Oct 16 12:18:44 2013	(r256624)
@@ -183,20 +183,12 @@ rt_tables_get_rnh(int table, int fam)
 static void
 route_init(void)
 {
-	struct domain *dom;
-	int max_keylen = 0;
 
 	/* whack the tunable ints into  line. */
 	if (rt_numfibs > RT_MAXFIBS)
 		rt_numfibs = RT_MAXFIBS;
 	if (rt_numfibs == 0)
 		rt_numfibs = 1;
-
-	for (dom = domains; dom; dom = dom->dom_next)
-		if (dom->dom_maxrtkey > max_keylen)
-			max_keylen = dom->dom_maxrtkey;
-
-	rn_init(max_keylen);	/* init all zeroes, all ones, mask table */
 }
 SYSINIT(route_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, route_init, 0);
 
_______________________________________________
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-unsubscribe@freebsd.org"

Comment 3 dfilter service 2013-10-29 12:53:33 UTC

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 <slw@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-unsubscribe@freebsd.org"

Comment 4 dfilter service 2013-10-30 16:08:42 UTC

Author: melifaro
Date: Wed Oct 30 16:08:27 2013
New Revision: 257389
URL: http://svnweb.freebsd.org/changeset/base/257389

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 <slw@zxy.spb.ru>
  Reviewed by:	glebius (previous versions)
  Sponsored by:	Yandex LLC

Modified:
  stable/9/sys/net/radix.c
  stable/9/sys/net/radix.h
Directory Properties:
  stable/9/sys/   (props changed)
  stable/9/sys/net/   (props changed)

Modified: stable/9/sys/net/radix.c
==============================================================================
--- stable/9/sys/net/radix.c	Wed Oct 30 15:46:50 2013	(r257388)
+++ stable/9/sys/net/radix.c	Wed Oct 30 16:08:27 2013	(r257389)
@@ -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/9/sys/net/radix.h
==============================================================================
--- stable/9/sys/net/radix.h	Wed Oct 30 15:46:50 2013	(r257388)
+++ stable/9/sys/net/radix.h	Wed Oct 30 16:08:27 2013	(r257389)
@@ -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-unsubscribe@freebsd.org"

Comment 5 Eitan Adler 2017-12-31 08:00:58 UTC

For bugs matching the following criteria:

Status: In Progress Changed: (is less than) 2014-06-01

Reset to default assignee and clear in-progress tags.

Mail being skipped

Comment 6 Oleksandr Tymoshenko 2019-01-19 19:46:19 UTC

There was a commit referencing this bug, but it's still not closed and has been inactive for some time. Closing as "fixed". Please re-open it if the issue hasn't been completely resolved.