Add a trigger API for efficient non-blocking waiting

The trigger API is simple:

To initialize a trigger, you can either do it statically with:

include/linux/trigger.h new file +63 -0

+ */
+static inline void trigger_init(trigger_t *t)
+{
+	__raw_trigger_init(t);
+}
+
+/**
+ * trigger_reset - reset a trigger
+ * @t - trigger to be reset
+ *
+ * This resets the trigger state, allowing a trigger_wait to block.
+ * Note that preemption must be disabled between trigger_reset() and
+ * trigger_finish().
+ *
+ * The use of these functions is:
+ *	trigger_reset(&t);
+ *	while(!condition)
+ *		trigger_wait(&t);
+ *	trigger_finish(&t);
+ *
+ * and where the condition is set:
+ *	condition = true;
+ *	trigger_kick(&t);
+ */
+static inline void trigger_reset(trigger_t *t)
+{
+	__raw_trigger_reset(t);
+}
+
+/**
+ * trigger_wait - wait for a trigger to be kicked
+ * @t - trigger to be waited on
+ *
+ * This blocks until the trigger has been kicked.  If the trigger has
+ * already been kicked, it will return immediately.  It may also
+ * return without the trigger having been kicked at all; the caller
+ * must test the condition before calling trigger_wait() again.
+ *
+ * trigger_wait() acts as a read barrier.
+ *
+ * On return, the trigger will have always be reset.
+ */
+static inline void trigger_wait(trigger_t *t)
+{
+	__raw_trigger_wait(t);
+}
+
+/**
+ * trigger_kick - kick a trigger
+ * @t - trigger to kick
+ *
+ * This causes anyone waiting in trigger_wait to continue.  It may be
+ * called in any context.
+ *
+ * trigger_kick() acts as a write barrier.
+ */
+static inline void trigger_kick(trigger_t *t)
+{
+	__raw_trigger_kick(t);
+}
+
+/**
+ * trigger_finish - clean up trigger

There are various places in the kernel which wish to wait for a condition to come true while in a non-blocking context. Existing examples of this are stop_machine() and smp_call_function_mask(). (No doubt there are other instances of this pattern in the tree.)

Thus far, the only way to achieve this is by spinning with a cpu_relax() loop. This is fine if the condition becomes true very quickly, but it is not ideal:

- There's little opportunity to put the CPUs into a low-power state. cpu_relax() may do this to some extent, but if the wait is relatively long, then we can probably do better.

- In a virtual environment, spinning virtual CPUs just waste CPU resources, and may steal CPU time from vCPUs which need it to make progress. The trigger API allows the vCPUs to give up their CPU entirely. The s390 people observed a problem with stop_machine taking a very long time (seconds) when there are more vcpus than available cpus.

Quoted 9 lines · On Sat, 16 Aug 2008 09:34:13 -0700 Jeremy Fitzhardinge <[email protected]> wrote:

There are various places in the kernel which wish to wait for a condition to come true while in a non-blocking context. Existing examples of this are stop_machine() and smp_call_function_mask(). (No doubt there are other instances of this pattern in the tree.)

Thus far, the only way to achieve this is by spinning with a cpu_relax() loop. This is fine if the condition becomes true very quickly, but it is not ideal:

Quoted 4 lines

- There's little opportunity to put the CPUs into a low-power state. cpu_relax() may do this to some extent, but if the wait is relatively long, then we can probably do better.

If this change saves a significant amount of power then we should fix the offending callsites.

Quoted 7 lines

- In a virtual environment, spinning virtual CPUs just waste CPU resources, and may steal CPU time from vCPUs which need it to make progress. The trigger API allows the vCPUs to give up their CPU entirely. The s390 people observed a problem with stop_machine taking a very long time (seconds) when there are more vcpus than available cpus.

If this change saves a significant amount of virtual-cpu-time then we should fix the offending callsites.

Quoted 17 lines · Andrew Morton

Quoted 13 lines · On Sat, 16 Aug 2008 09:34:13 -0700 Jeremy Fitzhardinge <[email protected]> wrote:

There are various places in the kernel which wish to wait for a condition to come true while in a non-blocking context. Existing examples of this are stop_machine() and smp_call_function_mask(). (No doubt there are other instances of this pattern in the tree.)

Thus far, the only way to achieve this is by spinning with a cpu_relax() loop. This is fine if the condition becomes true very quickly, but it is not ideal:

- There's little opportunity to put the CPUs into a low-power state. cpu_relax() may do this to some extent, but if the wait is relatively long, then we can probably do better.

Quoted 3 lines

If this change saves a significant amount of power then we should fix the offending callsites.

Fix them how? In general we're talking about contexts where we can't block, and where the wait time is limited by some property of the platform, such as IPI time or interrupt latency (though doing a cross-cpu call of a long-running function would be something we could fix).

Quoted 11 lines

Quoted 7 lines

- In a virtual environment, spinning virtual CPUs just waste CPU resources, and may steal CPU time from vCPUs which need it to make progress. The trigger API allows the vCPUs to give up their CPU entirely. The s390 people observed a problem with stop_machine taking a very long time (seconds) when there are more vcpus than available cpus.

If this change saves a significant amount of virtual-cpu-time then we should fix the offending callsites.

This case isn't particularly about saving vcpu time, but making timely progress. stop_machine() gets all the cpus into a spinloop, where they spin waiting for an event to tell them to go to their next state-machine state. By definition this can't be a blocking operation (since the whole point is that they're high priority threads that prevent anything else from running). But in the virtual case, the fact that they're all spinning means that the underlying hypervisor has no idea who's just spinning, and who's trying to do some work needed to make overall progress, so the whole thing gets bogged down.

Now perhaps we could solve stop_machine by modifying the scheduler in some way, where you can block the run queue so that you sit in the idle loop even though there's runnable processes waiting. But even then, stop_machine requires that interrupts be disabled, which means the we're pretty much limited to spinning.

So my proposal is to add a non-scheduler-blocking operation which is semantically equivalent to spinning, but gives the underlying platform more information about what's going on.

Arjan suggested that since this is more or less equivalent to a completion, we should just implement "spinpletions" - a spinning completion. This should be more familiar to kernel programmers, and should be just as useful as triggers.

I've run out of time to work on this now, but Rusty has hinted he'll pick up the baton...

(I'd also like to hear from other architecture folks, particularly s390, to make sure this is going to be useful to them too.)

J

Quoted 20 lines · On Wed, 20 Aug 2008 11:42:27 -0700 Jeremy Fitzhardinge <[email protected]> wrote:

Quoted 18 lines · Andrew Morton

Quoted 14 lines · On Sat, 16 Aug 2008 09:34:13 -0700 Jeremy Fitzhardinge <[email protected]> wrote:

There are various places in the kernel which wish to wait for a condition to come true while in a non-blocking context. Existing examples of this are stop_machine() and smp_call_function_mask(). (No doubt there are other instances of this pattern in the tree.)

Thus far, the only way to achieve this is by spinning with a cpu_relax() loop. This is fine if the condition becomes true very quickly, but it is not ideal:

- There's little opportunity to put the CPUs into a low-power state. cpu_relax() may do this to some extent, but if the wait is relatively long, then we can probably do better.

Quoted 9 lines

Quoted 4 lines

If this change saves a significant amount of power then we should fix the offending callsites.

Fix them how? In general we're talking about contexts where we can't block, and where the wait time is limited by some property of the platform, such as IPI time or interrupt latency (though doing a cross-cpu call of a long-running function would be something we could fix).

ah, OK, I'd failed to note that you had identified two specific culprits.

Are either of these operations executed frequently enough for there to be significant energy savings here?

Quoted 12 lines

Quoted 8 lines

Quoted 8 lines

- In a virtual environment, spinning virtual CPUs just waste CPU resources, and may steal CPU time from vCPUs which need it to make progress. The trigger API allows the vCPUs to give up their CPU entirely. The s390 people observed a problem with stop_machine taking a very long time (seconds) when there are more vcpus than available cpus.

Quoted 4 lines

If this change saves a significant amount of virtual-cpu-time then we should fix the offending callsites.

Quoted 10 lines

This case isn't particularly about saving vcpu time, but making timely progress. stop_machine() gets all the cpus into a spinloop, where they spin waiting for an event to tell them to go to their next state-machine state. By definition this can't be a blocking operation (since the whole point is that they're high priority threads that prevent anything else from running). But in the virtual case, the fact that they're all spinning means that the underlying hypervisor has no idea who's just spinning, and who's trying to do some work needed to make overall progress, so the whole thing gets bogged down.

hm. I'm surprised that stop_machine() is executed frequently enough for you to care. What's causing it?

Quoted 6 lines

Now perhaps we could solve stop_machine by modifying the scheduler in some way, where you can block the run queue so that you sit in the idle loop even though there's runnable processes waiting. But even then, stop_machine requires that interrupts be disabled, which means the we're pretty much limited to spinning.

If stop_machine() is the _only_ problematic callsite and we reasonably expect that no new ones will pop up then sure, a stop_machine()-specific fix might be appropriate.

Otherwise, sure, we'd need to loko at something more general.

If stop_machine() is the _only_ problematic callsite and we reasonably expect that no new ones will pop up then sure, a stop_machine()-specific fix might be appropriate.

Otherwise, sure, we'd need to loko at something more general.

- In a virtual environment, spinning virtual CPUs just waste CPU resources, and may steal CPU time from vCPUs which need it to make progress. The trigger API allows the vCPUs to give up their CPU entirely. The s390 people observed a problem with stop_machine taking a very long time (seconds) when there are more vcpus than available cpus.

The trigger API is simple:

To initialize a trigger, you can either do it statically with:

   DEFINE_TRIGGER(trigger);

or dynamically with

   trigger_init(&trigger);

Then to use it, the wait side does:

   trigger_reset(&trigger);

   while(!condition)
	trigger_wait(&trigger);

   trigger_finish(&trigger);

and when the condition is set true:

   condition = true;
   trigger_kick(&trigger);