Re: [PATCH 1/2] sched: lockless wake-queues

Re: [PATCH 1/2] sched: lockless wake-queues

[George Spelvin]

+struct wake_q_head {
+	struct wake_q_node *first;
+	struct wake_q_node *last;
+};
+
+#define WAKE_Q_TAIL ((struct wake_q_node *) 0x01)
+
+#define WAKE_Q(name)					\
+	struct wake_q_head name = { WAKE_Q_TAIL, WAKE_Q_TAIL }

Is there some reason you don't use the simpler singly-linked list
construction with the tail being a pointer to a pointer:

struct wake_q_head {
       struct wake_q_node *first, **lastp;
};

#define WAKE_Q(name)                                   \
       struct wake_q_head name = { WAKE_Q_TAIL, &name.first }


That removes a conditional from wake_q_add:

+/*
+ * Queue a task for later wake-up by wake_up_q().  If the task is already
+ * queued by someone else, leave it to them to deliver the wakeup.
+ *
+ * This property makes it impossible to guarantee the order of wakeups,
+ * but for efficiency we try to deliver wakeups in the order tasks
+ * are added.  If we didn't mind reversing the order, a LIFO stack
+ * would be simpler.
+ */
+void wake_q_add(struct wake_q_head *head, struct task_struct *task)
+{
+	struct wake_q_node *node = &task->wake_q;
+
+	/*
+	 * Atomically grab the task, if ->wake_q is !nil already it means
+	 * its already queued (either by us or someone else) and will get the
+	 * wakeup due to that.
+	 *
+	 * This cmpxchg() implies a full barrier, which pairs with the write
+	 * barrier implied by the wakeup in wake_up_list().
+	 */
+	if (cmpxchg(&node->next, NULL, WAKE_Q_TAIL))
+		return;
+
+	get_task_struct(task);
+
+	/*
+	 * The head is context local, there can be no concurrency.
+	 */
+	*head->lastp = node;
+	head->lastp = &node->next;
+}

It may also be worth commenting the fact that wake_up_q() leaves the
struct wake_q_head in a corrupt state, so don't try to do it again.

Re: [PATCH 1/2] sched: lockless wake-queues

[Davidlohr Bueso]

On Mon, 2015-04-20 at 14:24 -0400, George Spelvin wrote:
> +struct wake_q_head {
> +	struct wake_q_node *first;
> +	struct wake_q_node *last;
> +};
> +
> +#define WAKE_Q_TAIL ((struct wake_q_node *) 0x01)
> +
> +#define WAKE_Q(name)					\
> +	struct wake_q_head name = { WAKE_Q_TAIL, WAKE_Q_TAIL }
> 
> Is there some reason you don't use the simpler singly-linked list
> construction with the tail being a pointer to a pointer:

Sure, that would also work.

> 
> struct wake_q_head {
>        struct wake_q_node *first, **lastp;
> };
> 
> #define WAKE_Q(name)                                   \
>        struct wake_q_head name = { WAKE_Q_TAIL, &name.first }
> 
> 
> That removes a conditional from wake_q_add:
> 
> +/*
> + * Queue a task for later wake-up by wake_up_q().  If the task is already
> + * queued by someone else, leave it to them to deliver the wakeup.

This is already commented in the cmpxchg.

> + *
> + * This property makes it impossible to guarantee the order of wakeups,
> + * but for efficiency we try to deliver wakeups in the order tasks
> + * are added.  

Ok.

> If we didn't mind reversing the order, a LIFO stack
> + * would be simpler.

While true, I don't think it belongs here.

> + */
> +void wake_q_add(struct wake_q_head *head, struct task_struct *task)
> +{
> +	struct wake_q_node *node = &task->wake_q;
> +
> +	/*
> +	 * Atomically grab the task, if ->wake_q is !nil already it means
> +	 * its already queued (either by us or someone else) and will get the
> +	 * wakeup due to that.
> +	 *
> +	 * This cmpxchg() implies a full barrier, which pairs with the write
> +	 * barrier implied by the wakeup in wake_up_list().
> +	 */
> +	if (cmpxchg(&node->next, NULL, WAKE_Q_TAIL))
> +		return;
> +
> +	get_task_struct(task);
> +
> +	/*
> +	 * The head is context local, there can be no concurrency.
> +	 */
> +	*head->lastp = node;
> +	head->lastp = &node->next;
> +}
> 
> It may also be worth commenting the fact that wake_up_q() leaves the
> struct wake_q_head in a corrupt state, so don't try to do it again.

Right, we could re-init the list once the loop is complete, yes. But it
shouldn't matter due to how we use wake-queues.

Thanks,
Davidlohr

Re: [PATCH 1/2] sched: lockless wake-queues

[George Spelvin]

>> Is there some reason you don't use the simpler singly-linked list
>> construction with the tail being a pointer to a pointer:

> Sure, that would also work.

It's just a convenient simplification, already used in struct hlist_node.

>> +/*
>> + * Queue a task for later wake-up by wake_up_q().  If the task is already
>> + * queued by someone else, leave it to them to deliver the wakeup.
>
> This is already commented in the cmpxchg.
>
>> + *
>> + * This property makes it impossible to guarantee the order of wakeups,
>> + * but for efficiency we try to deliver wakeups in the order tasks
>> + * are added.  
>
> Ok.

This is just me thinking "out loud" about the semantics.

>> It may also be worth commenting the fact that wake_up_q() leaves the
>> struct wake_q_head in a corrupt state, so don't try to do it again.

> Right, we could re-init the list once the loop is complete, yes. But it
> shouldn't matter due to how we use wake-queues.

Oh, indeed, there's no point.  Unless it's worth a debugging option,
but as you say the usage patterns are such that I don't expect it's
needed.

It just seemed worth commenting explicitly.


If I were going to comment it, here's what I'd write.  Feel free
to copy any or none of this:

/*
 * Wake-queues are lists of tasks about to be woken up.
 * Deferring the wakeup is useful when the waker is waking up multiple
 * tasks while holding a lock which the woken tasks will need, so they'd
 * go straight into a wait queue anyway.
 *
 * So instead, the the waker can wake_q_add(&q, task) under the lock,
 * and then wake_up_q(&q) afterward.
 *
 * The list head is allocated on the waker's stack, and the queue nodes
 * are preallocated as part of the task struct.
 *
 * A reference to each task (get_task_struct()) is held during the wait,
 * so the list will remain valid through wake_up_q().
 *
 * One per task suffices, because there's never a need for a task to be
 * in two wake queues simultaneously; it is forbidden to abandon a task
 * in a wake queue (a call to wake_up_q() _must_ follow), so if a task is
 * already in a wake queue, the wakeup will happen soon and the second
 * waker can just skip it.
 *
 * As with all Linux wakeup primitives, there is no guarantee about the
 * order, but this code tries to wake tasks in wake_q_add order.
 *
 * The WAKE_Q macro declares and initializes the list head.
 * wake_up_q() does NOT reinitialize the list; it's expected to be
 * called near the end of a function, where the fact that the queue is
 * not used again will be easy to see by inspection.
 */

Re: [PATCH 1/2] sched: lockless wake-queues

[Peter Zijlstra]

On Sun, Apr 19, 2015 at 12:17:39PM -0700, Davidlohr Bueso wrote:
> +void wake_q_add(struct wake_q_head *head, struct task_struct *task)
> +{
> +	struct wake_q_node *node = &task->wake_q;
> +
> +	/*
> +	 * Atomically grab the task, if ->wake_q is !nil already it means
> +	 * its already queued (either by us or someone else) and will get the
> +	 * wakeup due to that.
> +	 *
> +	 * This cmpxchg() implies a full barrier, which pairs with the write
> +	 * barrier implied by the wakeup in wake_up_list().
> +	 */
> +	if (cmpxchg(&node->next, NULL, WAKE_Q_TAIL))
> +		return;
> +
> +	get_task_struct(task);
> +
> +	/*
> +	 * The head is context local, there can be no concurrency.
> +	 */
> +	if (head->first == WAKE_Q_TAIL)
> +		head->first = node;
> +	else
> +		head->last->next = node;
> +
> +	head->last = node;
> +}

Do we want a sched_feat() that makes the above to an immediate wake-up
instead of the fancy thing? -- just for debuging/performance
measurements like things?

[PATCH 1/2] sched: lockless wake-queues

[Davidlohr Bueso]

From: Peter Zijlstra <peterz@infradead.org>

This is useful for locking primitives that can effect multiple
wakeups per operation and want to avoid lock internal lock contention
by delaying the wakeups until we've released the lock internal locks.

Alternatively it can be used to avoid issuing multiple wakeups, and
thus save a few cycles, in packet processing. Queue all target tasks
and wakeup once you've processed all packets. That way you avoid
waking the target task multiple times if there were multiple packets
for the same task.

Properties of a wake_q are:
- Lockless, as queue head must reside on the stack.
- Being a queue, maintains wakeup order passed by the callers. This can
  be important for otherwise, in scenarios where highly contended locks
  could affect any reliance on lock fairness. It also respects user
  order of wakeups.
- A queued task cannot be added again until it is woken up.

This patch adds the needed infrastructure into the scheduler code
and uses the new wake_q to delay the futex wakeups until after
we've released the corresponding user locks.

Signed-off-by: Peter Zijlstra <peterz@infradead.org>
[tweaks, adjustments, comments, etc.]
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 include/linux/sched.h | 30 ++++++++++++++++++++++++++++++
 kernel/sched/core.c   | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 79 insertions(+)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 8222ae4..3b20fe5 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -947,6 +947,34 @@ static inline int cpu_numa_flags(void)
 }
 #endif
 
+/*
+ * Wake-queues are lists of tasks with a pending wakeup, whose
+ * callers have already marked the task as woken internally,
+ * and can thus carry on. A common use case is being able to
+ * do the wakeups once the corresponding lock as been released.
+ *
+ * We hold reference to each task in the list across the wakeup,
+ * thus guaranteeing that the memory is still valid by the time
+ * the actual wakeups are performed in wake_up_q().
+ */
+struct wake_q_node {
+	struct wake_q_node *next;
+};
+
+struct wake_q_head {
+	struct wake_q_node *first;
+	struct wake_q_node *last;
+};
+
+#define WAKE_Q_TAIL ((struct wake_q_node *) 0x01)
+
+#define WAKE_Q(name)					\
+	struct wake_q_head name = { WAKE_Q_TAIL, WAKE_Q_TAIL }
+
+extern void wake_q_add(struct wake_q_head *head,
+			  struct task_struct *task);
+extern void wake_up_q(struct wake_q_head *head);
+
 struct sched_domain_attr {
 	int relax_domain_level;
 };
@@ -1519,6 +1547,8 @@ struct task_struct {
 	/* Protection of the PI data structures: */
 	raw_spinlock_t pi_lock;
 
+	struct wake_q_node wake_q;
+
 #ifdef CONFIG_RT_MUTEXES
 	/* PI waiters blocked on a rt_mutex held by this task */
 	struct rb_root pi_waiters;
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index f9123a8..ebe6890 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -541,6 +541,55 @@ static bool set_nr_if_polling(struct task_struct *p)
 #endif
 #endif
 
+void wake_q_add(struct wake_q_head *head, struct task_struct *task)
+{
+	struct wake_q_node *node = &task->wake_q;
+
+	/*
+	 * Atomically grab the task, if ->wake_q is !nil already it means
+	 * its already queued (either by us or someone else) and will get the
+	 * wakeup due to that.
+	 *
+	 * This cmpxchg() implies a full barrier, which pairs with the write
+	 * barrier implied by the wakeup in wake_up_list().
+	 */
+	if (cmpxchg(&node->next, NULL, WAKE_Q_TAIL))
+		return;
+
+	get_task_struct(task);
+
+	/*
+	 * The head is context local, there can be no concurrency.
+	 */
+	if (head->first == WAKE_Q_TAIL)
+		head->first = node;
+	else
+		head->last->next = node;
+
+	head->last = node;
+}
+
+void wake_up_q(struct wake_q_head *head)
+{
+	struct wake_q_node *node = head->first;
+
+	while (node != WAKE_Q_TAIL) {
+		struct task_struct *task;
+
+		task = container_of(node, struct task_struct, wake_q);
+		BUG_ON(!task);
+		node = node->next;
+		task->wake_q.next = NULL; /* task can safely be re-inserted now */
+
+		/*
+		 * wake_up_process() implies a wmb() to pair with the queueing
+		 * in wake_q_add() so as not to miss wakeups.
+		 */
+		wake_up_process(task);
+		put_task_struct(task);
+	}
+}
+
 /*
  * resched_curr - mark rq's current task 'to be rescheduled now'.
  *
-- 
2.1.4