Linux-libre 4.2-gnu

1 files changed, 180 insertions, 129 deletions

diff --git a/ipc/kdbus/node.c b/ipc/kdbus/node.c
index 89f58bc85..986aca39c 100644
--- a/ipc/kdbus/node.c
+++ b/ipc/kdbus/node.c
@@ -111,33 +111,27 @@
  *
  * All nodes can be deactivated via kdbus_node_deactivate() at any time. You can
  * call this multiple times, even in parallel or on nodes that were never
- * linked, and it will just work. The only restriction is, you must not hold an
- * active reference when calling kdbus_node_deactivate().
- * By deactivating a node, it is immediately marked inactive. Then, we wait for
- * all active references to be released (called 'draining' the node). This
- * shouldn't take very long as we don't perform long-lasting operations while
- * holding an active reference. Note that once the node is marked inactive, no
- * new active references can be acquired.
- * Once all active references are dropped, the node is considered 'drained'. Now
- * kdbus_node_deactivate() is called on each child of the node before we
- * continue deactivating our node. That is, once all children are entirely
- * deactivated, we call ->release_cb() of our node. ->release_cb() can release
- * any resources on that node which are bound to the "active" state of a node.
- * When done, we unlink the node from its parent rb-tree, mark it as
- * 'released' and return.
- * If kdbus_node_deactivate() is called multiple times (even in parallel), all
- * but one caller will just wait until the node is fully deactivated. That is,
- * one random caller of kdbus_node_deactivate() is selected to call
- * ->release_cb() and cleanup the node. Only once all this is done, all other
- * callers will return from kdbus_node_deactivate(). That is, it doesn't matter
- * whether you're the selected caller or not, it will only return after
- * everything is fully done.
+ * linked, and it will just work. Furthermore, all children will be deactivated
+ * recursively as well. If a node is deactivated, there might still be active
+ * references that were acquired before calling kdbus_node_deactivate(). The
+ * owner of an object must call kdbus_node_drain() (which is a superset of
+ * kdbus_node_deactivate()) before dropping their reference. This will
+ * deactivate the node and also synchronously wait for all active references to
+ * be dropped. Hence, once kdbus_node_drain() returns, the node is fully
+ * released and no active references exist, anymore.
+ * kdbus_node_drain() can be called at any times, multiple times, and in
+ * parallel on multiple threads. All calls are synchronized internally and will
+ * return only once the node is fully drained. The only restriction is, you
+ * must not hold an active reference when calling kdbus_node_drain() (unlike
+ * deactivation, which allows the caller to hold an active reference).
  *
  * When a node is activated, we acquire a normal object reference to the node.
- * This reference is dropped after deactivation is fully done (and only iff the
+ * This reference is dropped after deactivation is fully done (and only if the
  * node really was activated). This allows callers to link+activate a child node
- * and then drop all refs. The node will be deactivated together with the
- * parent, and then be freed when this reference is dropped.
+ * and then drop all refs. This has the effect that nobody owns a reference to
+ * the node, except for the parent node. Hence, if the parent is deactivated
+ * (and thus all children are deactivated, too), this will automatically
+ * release the child node.
  *
  * Currently, nodes provide a bunch of resources that external code can use
  * directly. This includes:
@@ -198,11 +192,10 @@
  *                   is even unique if linked but not activated, yet. This might
  *                   change in the future, though. Code should not rely on this.
  *
- *     * node->lock:     lock to protect node->children, node->rb, node->parent
+ *     * node->lock:   lock to protect node->children, node->rb, node->parent
  *     * node->parent: Reference to parent node. This is set during LINK time
- *                     and is dropped during destruction. You must not access
- *                     it unless you hold an active reference to the node or if
- *                     you know the node is dead.
+ *                     and is dropped during destruction. You can freely access
+ *                     this field, but it may be NULL (root node).
  *     * node->children: rb-tree of all linked children of this node. You must
  *                       not access this directly, but use one of the iterator
  *                       or lookup helpers.
@@ -265,6 +258,18 @@ static unsigned int kdbus_node_name_hash(const char *name)
  * @name:	name to compare the node with
  * @node:	node to compare the name with
  *
+ * This compares a query string against a kdbus node. If the kdbus node has the
+ * given name, this returns 0. Otherwise, this returns >0 / <0 depending
+ * whether the query string is greater / less than the node.
+ *
+ * Note: If @node is drained but has the name @name, this returns 1. The
+ *       reason for this is that we treat drained nodes as "renamed". The
+ *       slot of such nodes is no longer occupied and new nodes can claim it.
+ *       Obviously, this has the side-effect that you cannot match drained
+ *       nodes, as they will never return 0 on name-matches. But this is
+ *       intentional, as there is no reason why anyone would ever want to match
+ *       on drained nodes.
+ *
  * Return: 0 if @name and @hash exactly match the information in @node, or
  * an integer less than or greater than zero if @name is found, respectively,
  * to be less than or be greater than the string stored in @node.
@@ -272,10 +277,16 @@ static unsigned int kdbus_node_name_hash(const char *name)
 static int kdbus_node_name_compare(unsigned int hash, const char *name,
 				   const struct kdbus_node *node)
 {
+	int ret;
+
 	if (hash != node->hash)
 		return hash - node->hash;
 
-	return strcmp(name, node->name);
+	ret = strcmp(name, node->name);
+	if (ret != 0)
+		return ret;
+
+	return atomic_read(&node->active) == KDBUS_NODE_DRAINED;
 }
 
 /**
@@ -312,7 +323,7 @@ void kdbus_node_init(struct kdbus_node *node, unsigned int type)
  * ID could be allocated. You must not activate a node if linking failed! It is
  * safe to deactivate it, though.
  *
- * Once you linked a node, you must call kdbus_node_deactivate() before you drop
+ * Once you linked a node, you must call kdbus_node_drain() before you drop
  * the last reference (even if you never activate the node).
  *
  * Return: 0 on success. negative error otherwise.
@@ -419,7 +430,7 @@ struct kdbus_node *kdbus_node_ref(struct kdbus_node *node)
  *
  * Note that this calls into ->free_cb() and thus _might_ sleep. The ->free_cb()
  * callbacks must not acquire any outer locks, though. So you can safely drop
- * references while holding locks.
+ * references while holding locks (apart from node->parent->lock).
  *
  * If @node is NULL, this is a no-op.
  *
@@ -431,7 +442,16 @@ struct kdbus_node *kdbus_node_unref(struct kdbus_node *node)
 		struct kdbus_node safe = *node;
 
 		WARN_ON(atomic_read(&node->active) != KDBUS_NODE_DRAINED);
-		WARN_ON(!RB_EMPTY_NODE(&node->rb));
+
+		if (node->parent) {
+			mutex_lock(&node->parent->lock);
+			if (!RB_EMPTY_NODE(&node->rb)) {
+				rb_erase(&node->rb,
+					 &node->parent->children);
+				RB_CLEAR_NODE(&node->rb);
+			}
+			mutex_unlock(&node->parent->lock);
+		}
 
 		if (node->free_cb)
 			node->free_cb(node);
@@ -439,12 +459,6 @@ struct kdbus_node *kdbus_node_unref(struct kdbus_node *node)
 			ida_simple_remove(&kdbus_node_ida, safe.id);
 
 		kfree(safe.name);
-
-		/*
-		 * kdbusfs relies on the parent to be available even after the
-		 * node was deactivated and unlinked. Therefore, we pin it
-		 * until a node is destroyed.
-		 */
 		kdbus_node_unref(safe.parent);
 	}
 
@@ -534,78 +548,149 @@ bool kdbus_node_activate(struct kdbus_node *node)
 }
 
 /**
- * kdbus_node_deactivate() - deactivate a node
- * @node:	The node to deactivate.
+ * kdbus_node_recurse_unlock() - advance iterator on a tree
+ * @start:	node at which the iteration started
+ * @node:	previously visited node
  *
- * This function recursively deactivates this node and all its children. It
- * returns only once all children and the node itself were recursively disabled
- * (even if you call this function multiple times in parallel).
+ * This helper advances an iterator by one, when traversing a node tree. It is
+ * supposed to be used like this:
  *
- * It is safe to call this function on _any_ node that was initialized _any_
- * number of times.
+ *     struct kdbus_node *n;
  *
- * This call may sleep, as it waits for all active references to be dropped.
+ *     n = start;
+ *     while (n) {
+ *             mutex_lock(&n->lock);
+ *             ... visit @n ...
+ *             n = kdbus_node_recurse_unlock(start, n);
+ *     }
+ *
+ * This helpers takes as input the start-node of the iteration and the current
+ * position. It returns a pointer to the next node to visit. The caller must
+ * hold a reference to @start during the whole iteration. Furthermore, @node
+ * must be locked when entering this helper. On return, the lock is released.
+ *
+ * The order of visit is pre-order traversal.
+ *
+ * If @node is deactivated before recursing its children, then it is guaranteed
+ * that all children will be visited. If @node is still active, new nodes might
+ * be inserted during traversal, and thus might be missed.
+ *
+ * Also note that the node-locks are released while traversing children. You
+ * must not rely on the locks to be held during the whole traversal. Each node
+ * that is visited is pinned by this helper, so the caller can rely on owning a
+ * reference. It is dropped, once all of the children of the node have been
+ * visited (recursively).
+ *
+ * You *must not* bail out of a traversal early, otherwise you'll leak
+ * ref-counts to all nodes in the current depth-path.
+ *
+ * Return: Reference to next node, or NULL.
  */
-void kdbus_node_deactivate(struct kdbus_node *node)
+static struct kdbus_node *kdbus_node_recurse_unlock(struct kdbus_node *start,
+						    struct kdbus_node *node)
 {
-	struct kdbus_node *pos, *child;
+	struct kdbus_node *t, *prev = NULL;
 	struct rb_node *rb;
-	int v_pre, v_post;
 
-	pos = node;
+	lockdep_assert_held(&node->lock);
 
-	/*
-	 * To avoid recursion, we perform back-tracking while deactivating
-	 * nodes. For each node we enter, we first mark the active-counter as
-	 * deactivated by adding BIAS. If the node as children, we set the first
-	 * child as current position and start over. If the node has no
-	 * children, we drain the node by waiting for all active refs to be
-	 * dropped and then releasing the node.
-	 *
-	 * After the node is released, we set its parent as current position
-	 * and start over. If the current position was the initial node, we're
-	 * done.
-	 *
-	 * Note that this function can be called in parallel by multiple
-	 * callers. We make sure that each node is only released once, and any
-	 * racing caller will wait until the other thread fully released that
-	 * node.
-	 */
+	rb = rb_first(&node->children);
+	if (!rb) {
+		do {
+			mutex_unlock(&node->lock);
+			kdbus_node_unref(prev);
+
+			if (node == start)
+				return NULL;
+
+			prev = node;
+			node = node->parent;
+
+			mutex_lock(&node->lock);
+			rb = rb_next(&prev->rb);
+		} while (!rb);
+	}
+
+	t = kdbus_node_ref(kdbus_node_from_rb(rb));
+	mutex_unlock(&node->lock);
+	kdbus_node_unref(prev);
+	return t;
+}
+
+/**
+ * kdbus_node_deactivate() - deactivate a node
+ * @node:	node to deactivate
+ *
+ * This recursively deactivates the passed node and all its children. The nodes
+ * are marked as deactivated, but they're not drained. Hence, even after this
+ * call returns, there might still be someone holding an active reference to
+ * any of the nodes. However, no new active references can be acquired after
+ * this returns.
+ *
+ * It is safe to call this multiple times (even in parallel). Each call is
+ * guaranteed to only return after _all_ nodes have been deactivated.
+ */
+void kdbus_node_deactivate(struct kdbus_node *node)
+{
+	struct kdbus_node *pos;
+	int v;
+
+	pos = node;
+	while (pos) {
+		mutex_lock(&pos->lock);
 
-	for (;;) {
 		/*
-		 * Add BIAS to node->active to mark it as inactive. If it was
+		 * Add BIAS to pos->active to mark it as inactive. If it was
 		 * never active before, immediately mark it as RELEASE_INACTIVE
-		 * so we remember this state.
-		 * We cannot remember v_pre as we might iterate into the
-		 * children, overwriting v_pre, before we can release our node.
+		 * so that this case can be detected later on.
+		 * If the node was already deactivated, make sure to still
+		 * recurse into the children. Otherwise, we might return before
+		 * a racing thread finished deactivating all children. But we
+		 * want to guarantee that the whole tree is deactivated once
+		 * this returns.
 		 */
-		mutex_lock(&pos->lock);
-		v_pre = atomic_read(&pos->active);
-		if (v_pre >= 0)
+		v = atomic_read(&pos->active);
+		if (v >= 0)
 			atomic_add_return(KDBUS_NODE_BIAS, &pos->active);
-		else if (v_pre == KDBUS_NODE_NEW)
+		else if (v == KDBUS_NODE_NEW)
 			atomic_set(&pos->active, KDBUS_NODE_RELEASE_DIRECT);
-		mutex_unlock(&pos->lock);
 
+		pos = kdbus_node_recurse_unlock(node, pos);
+	}
+}
+
+/**
+ * kdbus_node_drain() - drain a node
+ * @node:	node to drain
+ *
+ * This function recursively deactivates this node and all its children and
+ * then waits for all active references to be dropped. This function is a
+ * superset of kdbus_node_deactivate(), as it additionally drains all nodes. It
+ * returns only once all children and the node itself were recursively drained
+ * (even if you call this function multiple times in parallel).
+ *
+ * It is safe to call this function on _any_ node that was initialized _any_
+ * number of times.
+ *
+ * This call may sleep, as it waits for all active references to be dropped.
+ */
+void kdbus_node_drain(struct kdbus_node *node)
+{
+	struct kdbus_node *pos;
+	int v;
+
+	kdbus_node_deactivate(node);
+
+	pos = node;
+	while (pos) {
 		/* wait until all active references were dropped */
 		wait_event(pos->waitq,
 			   atomic_read(&pos->active) <= KDBUS_NODE_BIAS);
 
-		mutex_lock(&pos->lock);
-		/* recurse into first child if any */
-		rb = rb_first(&pos->children);
-		if (rb) {
-			child = kdbus_node_ref(kdbus_node_from_rb(rb));
-			mutex_unlock(&pos->lock);
-			pos = child;
-			continue;
-		}
-
 		/* mark object as RELEASE */
-		v_post = atomic_read(&pos->active);
-		if (v_post == KDBUS_NODE_BIAS ||
-		    v_post == KDBUS_NODE_RELEASE_DIRECT)
+		mutex_lock(&pos->lock);
+		v = atomic_read(&pos->active);
+		if (v == KDBUS_NODE_BIAS || v == KDBUS_NODE_RELEASE_DIRECT)
 			atomic_set(&pos->active, KDBUS_NODE_RELEASE);
 		mutex_unlock(&pos->lock);
 
@@ -614,20 +699,9 @@ void kdbus_node_deactivate(struct kdbus_node *node)
 		 * perform the actual release. Otherwise, we wait until the
 		 * release is done and the node is marked as DRAINED.
 		 */
-		if (v_post == KDBUS_NODE_BIAS ||
-		    v_post == KDBUS_NODE_RELEASE_DIRECT) {
+		if (v == KDBUS_NODE_BIAS || v == KDBUS_NODE_RELEASE_DIRECT) {
 			if (pos->release_cb)
-				pos->release_cb(pos, v_post == KDBUS_NODE_BIAS);
-
-			if (pos->parent) {
-				mutex_lock(&pos->parent->lock);
-				if (!RB_EMPTY_NODE(&pos->rb)) {
-					rb_erase(&pos->rb,
-						 &pos->parent->children);
-					RB_CLEAR_NODE(&pos->rb);
-				}
-				mutex_unlock(&pos->parent->lock);
-			}
+				pos->release_cb(pos, v == KDBUS_NODE_BIAS);
 
 			/* mark as DRAINED */
 			atomic_set(&pos->active, KDBUS_NODE_DRAINED);
@@ -646,7 +720,7 @@ void kdbus_node_deactivate(struct kdbus_node *node)
 			 * immediately went to NODE_RELEASE_DIRECT. In that case
 			 * we must not drop the reference.
 			 */
-			if (v_post == KDBUS_NODE_BIAS)
+			if (v == KDBUS_NODE_BIAS)
 				kdbus_node_unref(pos);
 		} else {
 			/* wait until object is DRAINED */
@@ -654,19 +728,8 @@ void kdbus_node_deactivate(struct kdbus_node *node)
 			    atomic_read(&pos->active) == KDBUS_NODE_DRAINED);
 		}
 
-		/*
-		 * We're done with the current node. Continue on its parent
-		 * again, which will try deactivating its next child, or itself
-		 * if no child is left.
-		 * If we've reached our initial node again, we are done and
-		 * can safely return.
-		 */
-		if (pos == node)
-			break;
-
-		child = pos;
-		pos = pos->parent;
-		kdbus_node_unref(child);
+		mutex_lock(&pos->lock);
+		pos = kdbus_node_recurse_unlock(node, pos);
 	}
 }
 
@@ -859,18 +922,6 @@ struct kdbus_node *kdbus_node_next_child(struct kdbus_node *node,
 		pos = kdbus_node_from_rb(rb);
 		if (kdbus_node_acquire(pos))
 			goto exit;
-	} else if (RB_EMPTY_NODE(&prev->rb)) {
-		/*
-		 * The current iterator is no longer linked to the rb-tree. Use
-		 * its hash value and name to find the next _higher_ node and
-		 * acquire it. If we got it, return it as next element.
-		 * Otherwise, the loop below will find the next active node.
-		 */
-		pos = node_find_closest_unlocked(node, prev->hash, prev->name);
-		if (!pos)
-			goto exit;
-		if (kdbus_node_acquire(pos))
-			goto exit;
 	} else {
 		/*
 		 * The current iterator is still linked to the parent. Set it