Bug 170098

Comment 1 Adrian Chadd 2012-07-23 23:59:09 UTC

Class Changed
From-To: doc-bug->sw-bug

This is partially a docs and partially a kern problem. 

Comment 2 Adrian Chadd 2012-07-23 23:59:09 UTC

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

This is partially a docs and partially a kern problem.

This has been fixed by the attached 2 patches, which are applied
to -HEAD in order.

Thanks muchly to PseudoCylon for his work, this has taken a while
but the difficult solutions are that way.

thanks

-kim

Comment 4 Adrian Chadd 2012-08-15 17:50:53 UTC

Hi,

I'm just testing out the patch(es) now. The basic spirit of them
works, but there are some improvements to be made.

* The node generation count doesn't have to be checked. We know the
node table is locked; the reason the node generation is there is
because in the older way of doing it, the node table lock is released
each trip through the loop.
* 'goto restart' on each successful addition to the node table turns
an O(n) operation into an O(n^2) operation. That's just plain going to
suck.
* It's always good practice to alloc and free memory in the same
function or module and doing it consistently. The patch allocates it
in iterate_nodes() but frees it in iterate_nt() if there's an error.
That kind of inconsistent handling could cause problems.
* There's no need to decrement the node scan generation on error. It's
fine the way it is.
* .. which means if you don't decrement the scangen in each node, you
can release the node table / node iteration table locks earlier,
avoiding any LOR with ieee80211_node_free().

I have a replacement patch which I'm currently testing out. I'll push
it into -HEAD today.

Thanks again to Kim and PseudoCylon for finding and fixing the problem!



Adrian

Comment 5 dfilter service 2012-08-15 21:01:39 UTC

Author: adrian
Date: Wed Aug 15 20:01:28 2012
New Revision: 239312
URL: http://svn.freebsd.org/changeset/base/239312

Log:
  Don't call the node iteration function inside the node table / node
  iterate lock.
  
  This causes LORs and deadlocks as some code paths will have the com lock
  held when calling ieee80211_iterate_nodes().
  
  Here, the comlock isn't held during the node table and node iteration
  locks; and the callback isn't called with any (extra) lock held.
  
  PR:		kern/170098
  Submitted by:	moonlightakkiy@yahoo.ca
  MFC after:	4 weeks

Modified:
  head/sys/net80211/ieee80211_node.c
  head/sys/net80211/ieee80211_node.h

Modified: head/sys/net80211/ieee80211_node.c
==============================================================================
--- head/sys/net80211/ieee80211_node.c	Wed Aug 15 19:59:13 2012	(r239311)
+++ head/sys/net80211/ieee80211_node.c	Wed Aug 15 20:01:28 2012	(r239312)
@@ -2156,30 +2156,124 @@ ieee80211_node_timeout(void *arg)
 		ieee80211_node_timeout, ic);
 }
 
-void
-ieee80211_iterate_nodes(struct ieee80211_node_table *nt,
-	ieee80211_iter_func *f, void *arg)
+/*
+ * Iterate over the node table and return an array of ref'ed nodes.
+ *
+ * This is separated out from calling the actual node function so that
+ * no LORs will occur.
+ *
+ * If there are too many nodes (ie, the number of nodes doesn't fit
+ * within 'max_aid' entries) then the node references will be freed
+ * and an error will be returned.
+ *
+ * The responsibility of allocating and freeing "ni_arr" is up to
+ * the caller.
+ */
+int
+ieee80211_iterate_nt(struct ieee80211_node_table *nt,
+    struct ieee80211_node **ni_arr, uint16_t max_aid)
 {
-	struct ieee80211_node *ni;
 	u_int gen;
+	int i, j, ret;
+	struct ieee80211_node *ni;
 
 	IEEE80211_NODE_ITERATE_LOCK(nt);
-	gen = ++nt->nt_scangen;
-restart:
 	IEEE80211_NODE_LOCK(nt);
+
+	gen = ++nt->nt_scangen;
+	i = ret = 0;
+
+	/*
+	 * We simply assume here that since the node
+	 * scan generation doesn't change (as
+	 * we are holding both the node table and
+	 * node table iteration locks), we can simply
+	 * assign it to the node here.
+	 */
 	TAILQ_FOREACH(ni, &nt->nt_node, ni_list) {
-		if (ni->ni_scangen != gen) {
-			ni->ni_scangen = gen;
-			(void) ieee80211_ref_node(ni);
-			IEEE80211_NODE_UNLOCK(nt);
-			(*f)(arg, ni);
-			ieee80211_free_node(ni);
-			goto restart;
+		if (i >= max_aid) {
+			ret = E2BIG;
+			if_printf(nt->nt_ic->ic_ifp,
+			    "Node array overflow: max=%u", max_aid);
+			break;
 		}
+		ni_arr[i] = ieee80211_ref_node(ni);
+		ni_arr[i]->ni_scangen = gen;
+		i++;
 	}
-	IEEE80211_NODE_UNLOCK(nt);
 
+	/*
+	 * It's safe to unlock here.
+	 *
+	 * If we're successful, the list is returned.
+	 * If we're unsuccessful, the list is ignored
+	 * and we remove our references.
+	 *
+	 * This avoids any potential LOR with
+	 * ieee80211_free_node().
+	 */
+	IEEE80211_NODE_UNLOCK(nt);
 	IEEE80211_NODE_ITERATE_UNLOCK(nt);
+
+	/*
+	 * If ret is non-zero, we hit some kind of error.
+	 * Rather than walking some nodes, we'll walk none
+	 * of them.
+	 */
+	if (ret) {
+		for (j = 0; j < i; j++) {
+			/* ieee80211_free_node() locks by itself */
+			ieee80211_free_node(ni_arr[j]);
+		}
+	}
+
+	return (ret);
+}
+
+/*
+ * Just a wrapper, so we don't have to change every ieee80211_iterate_nodes()
+ * reference in the source.
+ *
+ * Note that this fetches 'max_aid' from the first VAP, rather than finding
+ * the largest max_aid from all VAPs.
+ */
+void
+ieee80211_iterate_nodes(struct ieee80211_node_table *nt,
+	ieee80211_iter_func *f, void *arg)
+{
+	struct ieee80211_node **ni_arr;
+	unsigned long size;
+	int i;
+	uint16_t max_aid;
+
+	max_aid = TAILQ_FIRST(&nt->nt_ic->ic_vaps)->iv_max_aid;
+	size = max_aid * sizeof(struct ieee80211_node *);
+	ni_arr = (struct ieee80211_node **) malloc(size, M_80211_NODE,
+	    M_NOWAIT | M_ZERO);
+	if (ni_arr == NULL)
+		return;
+
+	/*
+	 * If this fails, the node table won't have any
+	 * valid entries - ieee80211_iterate_nt() frees
+	 * the references to them.  So don't try walking
+	 * the table; just skip to the end and free the
+	 * temporary memory.
+	 */
+	if (!ieee80211_iterate_nt(nt, ni_arr, max_aid))
+		goto done;
+
+	for (i = 0; i < max_aid; i++) {
+		if (ni_arr[i] == NULL)	/* end of the list */
+			break;
+
+		(*f)(arg, ni_arr[i]);
+		/* ieee80211_free_node() locks by itself */
+		ieee80211_free_node(ni_arr[i]);
+	}
+
+done:
+	free(ni_arr, M_80211_NODE);
 }
 
 void

Modified: head/sys/net80211/ieee80211_node.h
==============================================================================
--- head/sys/net80211/ieee80211_node.h	Wed Aug 15 19:59:13 2012	(r239311)
+++ head/sys/net80211/ieee80211_node.h	Wed Aug 15 20:01:28 2012	(r239312)
@@ -438,6 +438,8 @@ int	ieee80211_node_delucastkey(struct ie
 void	ieee80211_node_timeout(void *arg);
 
 typedef void ieee80211_iter_func(void *, struct ieee80211_node *);
+int	ieee80211_iterate_nt(struct ieee80211_node_table *,
+		struct ieee80211_node **, uint16_t);
 void	ieee80211_iterate_nodes(struct ieee80211_node_table *,
 		ieee80211_iter_func *, void *);
 
_______________________________________________
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 6 dfilter service 2012-08-16 01:53:40 UTC

Author: adrian
Date: Thu Aug 16 00:53:23 2012
New Revision: 239319
URL: http://svn.freebsd.org/changeset/base/239319

Log:
  Fix an incorrect comparison.
  
  PR:		kern/170098

Modified:
  head/sys/net80211/ieee80211_node.c

Modified: head/sys/net80211/ieee80211_node.c
==============================================================================
--- head/sys/net80211/ieee80211_node.c	Thu Aug 16 00:51:50 2012	(r239318)
+++ head/sys/net80211/ieee80211_node.c	Thu Aug 16 00:53:23 2012	(r239319)
@@ -2242,7 +2242,7 @@ ieee80211_iterate_nodes(struct ieee80211
 	ieee80211_iter_func *f, void *arg)
 {
 	struct ieee80211_node **ni_arr;
-	unsigned long size;
+	size_t size;
 	int i;
 	uint16_t max_aid;
 
@@ -2260,13 +2260,12 @@ ieee80211_iterate_nodes(struct ieee80211
 	 * the table; just skip to the end and free the
 	 * temporary memory.
 	 */
-	if (!ieee80211_iterate_nt(nt, ni_arr, max_aid))
+	if (ieee80211_iterate_nt(nt, ni_arr, max_aid) != 0)
 		goto done;
 
 	for (i = 0; i < max_aid; i++) {
 		if (ni_arr[i] == NULL)	/* end of the list */
 			break;
-
 		(*f)(arg, ni_arr[i]);
 		/* ieee80211_free_node() locks by itself */
 		ieee80211_free_node(ni_arr[i]);
_______________________________________________
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 7 Eitan Adler 2018-05-28 19:45:40 UTC

batch change:

For bugs that match the following
-  Status Is In progress 
AND
- Untouched since 2018-01-01.
AND
- Affects Base System OR Documentation

DO:

Reset to open status.


Note:
I did a quick pass but if you are getting this email it might be worthwhile to double check to see if this bug ought to be closed.

Comment 8 Oleksandr Tymoshenko 2019-01-20 01:27:07 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.