[RFC PATCH urcu 00/01] Introduce-rcu_barrier_finalize()

[RFC PATCH urcu 00/01] Introduce-rcu_barrier_finalize()

[Jérémie Galarneau]

Following a prior discussion on this mailing list [1], I am proposing
the introduction of rcu_barrier_finalize() in liburcu.

*** Use Case ***

As pointed out in the e-mail thread, some applications are nesting
liburcu data structures or, as part of their design, composing objects
which use liburcu data structures (e.g. lttng-tools daemons).

When such objects or data structures are destroyed, it is likely that
their 'call_rcu' callbacks will, in turn, enqueue new 'call_rcu' work
items.

This leads to a "chaining" phenomenon where 'call_rcu' callbacks are
added to the 'call_rcu' queue by callbacks being processed.

The implication of this chaining is that the rcu_barrier() mechanism
cannot be relied on to empty the 'call_rcu' queue. More specifically,
an application calling rcu_barrier() on exit may spuriously leak
memory since any unprocessed reclamation callback euqueued after the
barrier will result in a leak.

Of course, one could argue that it would be possible to refactor
applications to separate object tear down from memory
reclamation. However, the guarantee that an object is unreachable when
its 'call_rcu' callback is invoked (during a grace period) becomes
very useful to safely tear down its internal state (and release other
resources) in cases where an explicit reference counting mechanism
isn't being used.

*** Implementation limitations ***

The proposed implementation of rcu_barrier_finalize() is
straightforward, basically invoking rcu_barrier() until all queues are
observed to be empty. The call_rcu_mutex is released between each
iteration to ensure the application can fork() without deadlocking.
This ensures that all queues are empty on return, which in my use
case, is a crude way of ensuring all work enqueued by the work
enqueued prior to the rcu_barrier() has been processed.

This design may cause rcu_barrier_finalize() to never return if the
application can chain an unbounded amount of callbacks.

It could be improved by ensuring that all queues have been observed to
be empty at least once (and skipping them during the next iterations),
therefore guaranteeing that all chained work has been executed, but
foregoing the guarantee that all queues are empty on return (makes no
difference in my use case).

An alternative guarantee that could be offered would consist in
ensuring that all callbacks _and_ whichever callbacks they may
enqueue, are processed, but nothing more. I don't have a use-case for
this, but it may come in handy to someone (please speak up!). However,
since the implementation I have in mind does somewhat increase the
overall complexity of the solution, I am not sure it is worth
it. (Thoughts ?)

[1] https://lists.lttng.org/pipermail/lttng-dev/2015-December/025356.html

Jérémie Galarneau (1):
  Introduce rcu_barrier_finalize()

 doc/rcu-api.md       | 23 ++++++++++++++++++++---
 urcu-call-rcu-impl.h | 36 ++++++++++++++++++++++++++++++++++++
 urcu-call-rcu.h      |  1 +
 3 files changed, 57 insertions(+), 3 deletions(-)

-- 
2.6.4


_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

[RFC PATCH urcu 01/01] Introduce rcu_barrier_finalize()

[Jérémie Galarneau]

This new entry point is meant to allow applications to guarantee
that all work already pushed to the "call_rcu" queues has completed
before, for instance, tearing themselves down.

Signed-off-by: Jérémie Galarneau <jeremie.galarneau@efficios.com>
---
 doc/rcu-api.md       | 23 ++++++++++++++++++++---
 urcu-call-rcu-impl.h | 36 ++++++++++++++++++++++++++++++++++++
 urcu-call-rcu.h      |  1 +
 3 files changed, 57 insertions(+), 3 deletions(-)

diff --git a/doc/rcu-api.md b/doc/rcu-api.md
index ea316d1..798dd6f 100644
--- a/doc/rcu-api.md
+++ b/doc/rcu-api.md
@@ -99,9 +99,26 @@ void rcu_barrier(void);
 Wait for all `call_rcu()` work initiated prior to `rcu_barrier()` by
 _any_ thread on the system to have completed before `rcu_barrier()`
 returns. `rcu_barrier()` should never be called from a `call_rcu()`
-thread. This function can be used, for instance, to ensure that
-all memory reclaim involving a shared object has completed
-before allowing `dlclose()` of this shared object to complete.
+thread.
+
+
+```c
+void rcu_barrier_finalize(void);
+```
+
+Wait for all `call_rcu()` work initiated by _any_ thread prior to
+`rcu_barrier_finalize()`, along with all `call_rcu()` work initiated
+(chained) by these `call_rcu()` to have completed before returning.
+
+`rcu_barrier_finalize()` should never be called from a `call_rcu()`
+thread. This function can be used, for instance, to ensure that all
+memory reclamation involving a shared object has completed before
+allowing `dlclose()` of this shared object to complete.
+
+`rcu_barrier_finalize()` should not be used if the application does
+not bound its chaining of `call_rcu()`. Otherwise,
+`rcu_barrier_finalize()` may never finish since the execution of
+`call_rcu()` callbacks may keep generating new work indefinitely.
 
 
 ```c
diff --git a/urcu-call-rcu-impl.h b/urcu-call-rcu-impl.h
index 65f63ee..e3a3b4e 100644
--- a/urcu-call-rcu-impl.h
+++ b/urcu-call-rcu-impl.h
@@ -901,6 +901,42 @@ online:
 }
 
 /*
+ * Wait for all in-flight call_rcu callbacks, and whichever call_rcu callbacks
+ * they might in turn add, to complete execution before returning.
+ *
+ * It may also complete more work than necessary since other threads could also
+ * be inserting new work items in the work queue.
+ */
+void rcu_barrier_finalize(void)
+{
+	for (;;) {
+		int work_left = 0;
+		struct call_rcu_data *crdp;
+		/*
+		 * Callbacks executed during rcu_barrier() might insert new work
+		 * in the call_rcu queues. Therefore, we have to loop until all
+		 * queues are observed to be empty.
+		 */
+		rcu_barrier();
+		/* Protect access to call_rcu_data_list */
+		call_rcu_lock(&call_rcu_mutex);
+		cds_list_for_each_entry(crdp, &call_rcu_data_list, list) {
+			if (!cds_wfcq_empty(&crdp->cbs_head, &crdp->cbs_tail)) {
+				work_left = 1;
+				break;
+			}
+		}
+		call_rcu_unlock(&call_rcu_mutex);
+		/*
+		 * Ensure that newly issued work items are also completed before
+		 * returning.
+		 */
+		if (!work_left)
+			return;
+	}
+}
+
+/*
  * Acquire the call_rcu_mutex in order to ensure that the child sees
  * all of the call_rcu() data structures in a consistent state. Ensure
  * that all call_rcu threads are in a quiescent state across fork.
diff --git a/urcu-call-rcu.h b/urcu-call-rcu.h
index 339ebac..7c04a4a 100644
--- a/urcu-call-rcu.h
+++ b/urcu-call-rcu.h
@@ -93,6 +93,7 @@ void call_rcu_after_fork_parent(void);
 void call_rcu_after_fork_child(void);
 
 void rcu_barrier(void);
+void rcu_barrier_finalize(void);
 
 #ifdef __cplusplus
 }
-- 
2.6.4


_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: [RFC PATCH urcu 00/01] Introduce-rcu_barrier_finalize()

[Paul E. McKenney]

On Fri, Jan 22, 2016 at 12:22:02PM -0500, Jérémie Galarneau wrote:
> Following a prior discussion on this mailing list [1], I am proposing
> the introduction of rcu_barrier_finalize() in liburcu.
> 
> *** Use Case ***
> 
> As pointed out in the e-mail thread, some applications are nesting
> liburcu data structures or, as part of their design, composing objects
> which use liburcu data structures (e.g. lttng-tools daemons).
> 
> When such objects or data structures are destroyed, it is likely that
> their 'call_rcu' callbacks will, in turn, enqueue new 'call_rcu' work
> items.
> 
> This leads to a "chaining" phenomenon where 'call_rcu' callbacks are
> added to the 'call_rcu' queue by callbacks being processed.
> 
> The implication of this chaining is that the rcu_barrier() mechanism
> cannot be relied on to empty the 'call_rcu' queue. More specifically,
> an application calling rcu_barrier() on exit may spuriously leak
> memory since any unprocessed reclamation callback euqueued after the
> barrier will result in a leak.
> 
> Of course, one could argue that it would be possible to refactor
> applications to separate object tear down from memory
> reclamation. However, the guarantee that an object is unreachable when
> its 'call_rcu' callback is invoked (during a grace period) becomes
> very useful to safely tear down its internal state (and release other
> resources) in cases where an explicit reference counting mechanism
> isn't being used.

Just a design/architecture-level observation at the moment...

The point is that some callbacks register other callbacks, which
themselves might register other callbacks.  You want to wait until
the full chain of callbacks instigated by any previous call_rcu()
has completed.

This maps onto the RCU API.  When registering a callback that might
itself register a callback, you need to do something sort of like
rcu_read_lock(), but if this is down the chain, this new rcu_read_lock()
must block anyone blocked by the rcu_read_lock() at the head of the
chain.  When such a callback completes, you need to do something sort
of like rcu_read_unlock().  Then you wait using something kind of like
synchronize_rcu(), followed by rcu_barrier() to handle callbacks being
preempted just after they do the final rcu_read_unlock().

If each callback spawns at most one callback (which is the only case
that I am aware of in real life), you just do the rcu_read_lock()-like
thing before posting the first callback in the chain.  You wait to do
the rcu_read_unlock()-like thing until the final callback executes.
If callbacks can spawn multiple callbacks, then some adjustments are
needed.  This might be a reference counter, or it might be an
SRCU-like design where the first srcu_read_lock() returns an index
that is passed to subsequent srcu_read_lock() and srcu_read_lock()
calls on that chain.

Why is this important?  Because it allows you to draw on design
techniques from multiple RCU implementations to avoid your starvation
case.  This approach can also substitute a wait-wakeup approach for
your polling loop.

Or am I missing your point?

							Thanx, Paul

> *** Implementation limitations ***
> 
> The proposed implementation of rcu_barrier_finalize() is
> straightforward, basically invoking rcu_barrier() until all queues are
> observed to be empty. The call_rcu_mutex is released between each
> iteration to ensure the application can fork() without deadlocking.
> This ensures that all queues are empty on return, which in my use
> case, is a crude way of ensuring all work enqueued by the work
> enqueued prior to the rcu_barrier() has been processed.
> 
> This design may cause rcu_barrier_finalize() to never return if the
> application can chain an unbounded amount of callbacks.
> 
> It could be improved by ensuring that all queues have been observed to
> be empty at least once (and skipping them during the next iterations),
> therefore guaranteeing that all chained work has been executed, but
> foregoing the guarantee that all queues are empty on return (makes no
> difference in my use case).
> 
> An alternative guarantee that could be offered would consist in
> ensuring that all callbacks _and_ whichever callbacks they may
> enqueue, are processed, but nothing more. I don't have a use-case for
> this, but it may come in handy to someone (please speak up!). However,
> since the implementation I have in mind does somewhat increase the
> overall complexity of the solution, I am not sure it is worth
> it. (Thoughts ?)
> 
> [1] https://lists.lttng.org/pipermail/lttng-dev/2015-December/025356.html
> 
> Jérémie Galarneau (1):
>   Introduce rcu_barrier_finalize()
> 
>  doc/rcu-api.md       | 23 ++++++++++++++++++++---
>  urcu-call-rcu-impl.h | 36 ++++++++++++++++++++++++++++++++++++
>  urcu-call-rcu.h      |  1 +
>  3 files changed, 57 insertions(+), 3 deletions(-)
> 
> -- 
> 2.6.4
>