sched: lockless wake-queues
+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.
Quoted 10 lines · George Spelvin
(quoted diff) +9
-0+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 }
Quoted 2 lines
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.
Quoted 9 lines
struct wake_q_head { struct wake_q_node *first, **lastp; };#define WAKE_Q(name) \ struct wake_q_head name = { WAKE_Q_TAIL, &name.first }
Quoted 5 lines
That removes a conditional from
wake_q_add:+/*
+ * Queue a task for later wake-up bywake_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.
Quoted 4 lines
+ *
+ * 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.
Quoted 2 lines
If we didn't mind reversing the order, a LIFO stack
+ * would be simpler.
While true, I don't think it belongs here.
Quoted 25 lines
+ */
(quoted diff) +23
-0+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; +}
Quoted 2 lines
It may also be worth commenting the fact that
wake_up_q()leaves the structwake_q_headin 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
Quoted 4 lines
Quoted 2 lines
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.
Quoted 4 lines
Quoted 3 lines
+/*
+ * Queue a task for later wake-up bywake_up_q(). If the task is already
+ * queued by someone else, leave it to them to deliver the wakeup.
Quoted 8 lines
This is already commented in the cmpxchg.
Quoted 4 lines
+ *
+ * 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.
Quoted 5 lines
Quoted 2 lines
It may also be worth commenting the fact that
wake_up_q()leaves the structwake_q_headin 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.
*/