some questions/oddities regarding "exclusive" wait queues
currently digging through the code regarding wait queues and i ran across some oddities that i figure someone here can explain, so here goes. first, according to wait.h, there appears to be only one "flag" for a wait queue object: ===== struct __wait_queue { unsigned int flags; #define WQ_FLAG_EXCLUSIVE 0x01 void *private; wait_queue_func_t func; struct list_head task_list; }; ===== that's it -- WQ_FLAG_EXCLUSIVE appears to be the only possible flag setting for a "__wait_queue". am i missing any others? i certainly don't see any. next, as i read the code, it's possible to add both exclusive and non-exclusive wait queues to a wait queue head, and those operations are done in an interesting way in kernel/wait.c: ===== void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait) { unsigned long flags; wait->flags &= ~WQ_FLAG_EXCLUSIVE; spin_lock_irqsave(&q->lock, flags); __add_wait_queue(q, wait); spin_unlock_irqrestore(&q->lock, flags); } EXPORT_SYMBOL(add_wait_queue); void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait) { unsigned long flags; wait->flags |= WQ_FLAG_EXCLUSIVE; spin_lock_irqsave(&q->lock, flags); __add_wait_queue_tail(q, wait); spin_unlock_irqrestore(&q->lock, flags); } EXPORT_SYMBOL(add_wait_queue_exclusive); ===== note carefully the difference -- "exclusive" wait queues are added at the *tail* end of the list, which is important for what happens next, since this is how an entire wait queue is woken by the core wakeup function in kernel/sched/core.c: ===== /* * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve * number) then we wake all the non-exclusive tasks and one exclusive task. * * There are circumstances in which we can try to wake a task which has already * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns * zero in this (rare) case, and we handle it by continuing to scan the queue. */ static void __wake_up_common(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, int wake_flags, void *key) { wait_queue_t *curr, *next; list_for_each_entry_safe(curr, next, &q->task_list, task_list) { unsigned flags = curr->flags; if (curr->func(curr, mode, wake_flags, key) && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive) break; } } ===== first, the comment above that function seems wrong -- that routine will not simply wake "one exclusive task", it will wake "int nr_exclusive" exclusive tasks, will it not? (perhaps an earlier version woke only one, and the code was extended without adjusting the comment.) also, now it's clear why exclusive tasks are added at the *end* of the list -- all of the non-exclusive tasks must be processed first before counting off "nr_exclusive" tasks to be processed, does that seem correct? finally, if i understand all of the above correctly, there's one more curiosity back in wait.h -- a second form of the wait exclusive routine: ===== /* * Used for wake-one threads: */ static inline void __add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait) { wait->flags |= WQ_FLAG_EXCLUSIVE; __add_wait_queue(q, wait); } ===== note that that variation adds an exclusive wait queue, but *not* at the end, because it's apparently some sort of "wake-one thread", but i don't see a real distinction here. is it really necessary to recognize that distinction? a search of the entire kernel source tree shows only this: $ grep -rw "__add_wait_queue_exclusive" * fs/eventpoll.c: __add_wait_queue_exclusive(&ep->wq, &wait); include/linux/wait.h:static inline void __add_wait_queue_exclusive(wait_queue_head_t *q, $ that is, all of *one* usage in fs/eventpoll.c. does eventpoll.c genuinely need a unique interface for exclusive wait queues? anyway, feel free to tackle any of the above. more to come, i'm sure. rday -- ======================================================================== Robert P. J. Day Ottawa, Ontario, CANADA http://crashcourse.ca Twitter: http://twitter.com/rpjday LinkedIn: http://ca.linkedin.com/in/rpjday ========================================================================
On Fri, 21 Jun 2013 17:54:04 -0400, "Robert P. J. Day" said:
* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve * number) then we wake all the non-exclusive tasks and one exclusive task.
Right. Clear as mud. ;)
list_for_each_entry_safe(curr, next, &q->task_list, task_list) { unsigned flags = curr->flags;
if (curr->func(curr, mode, wake_flags, key) && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive) break; }
Oh, gotta love this tricky C. When do we actually hit the 'break;'? :)
first, the comment above that function seems wrong -- that routine will not simply wake "one exclusive task", it will wake "int nr_exclusive" exclusive tasks, will it not?
Hand-emulating with 'nr_exclusive == 3' indicates that in fact you're right. Does anybody actually call this with a value other than 1?
On Fri, 21 Jun 2013, Valdis.Kletnieks@vt.edu wrote:
On Fri, 21 Jun 2013 17:54:04 -0400, "Robert P. J. Day" said:
* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve * number) then we wake all the non-exclusive tasks and one exclusive task.
Right. Clear as mud. ;)
i already submitted a small patch to correct the above but i think maybe i should have been more extensive.
list_for_each_entry_safe(curr, next, &q->task_list, task_list) { unsigned flags = curr->flags;
if (curr->func(curr, mode, wake_flags, key) && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive) break; }
Oh, gotta love this tricky C. When do we actually hit the 'break;'? :)
as you did, i mentally worked through it and, as you did, seemed to clarify that it *will* process "nr_exclusive" so-called exclusive tasks before breaking. and that's based on what i wrote earlier -- that "exclusive" tasks are specifically added at the *end* of the wait queue list for this code to work properly.
first, the comment above that function seems wrong -- that routine will not simply wake "one exclusive task", it will wake "int nr_exclusive" exclusive tasks, will it not?
Hand-emulating with 'nr_exclusive == 3' indicates that in fact you're right. Does anybody actually call this with a value other than 1?
well, the value zero is common as that means everyone is processed but i realize you meant any non-zero value other than one. :-) and that's a good question. how many places in the source tree call __wake_up_common()? $ grep -rw __wake_up_common * kernel/sched/core.c:static void __wake_up_common(wait_queue_head_t *q, unsigned int mode, kernel/sched/core.c: __wake_up_common(q, mode, nr_exclusive, 0, key); kernel/sched/core.c: __wake_up_common(q, mode, nr, 0, NULL); kernel/sched/core.c: __wake_up_common(q, mode, 1, 0, key); kernel/sched/core.c: __wake_up_common(q, mode, nr_exclusive,wake_flags, key); kernel/sched/core.c: __wake_up_common(&x->wait, TASK_NORMAL, 1, 0, NULL); kernel/sched/core.c: __wake_up_common(&x->wait, TASK_NORMAL, 0, 0, NULL); $ so all the direct calls are in that one file, some of which are hard-coded to 0 or 1, but it just gets messy to try to figure out who calls *those* routines. and here's one example: ===== /** * __wake_up_sync_key - wake up threads blocked on a waitqueue. * @q: the waitqueue * @mode: which threads * @nr_exclusive: how many wake-one or wake-many threads to wake up * @key: opaque value to be passed to wakeup targets * * The sync wakeup differs that the waker knows that it will schedule * away soon, so while the target thread will be woken up, it will not * be migrated to another CPU - ie. the two threads are 'synchronized' * with each other. This can prevent needless bouncing between CPUs. * * On UP it can prevent extra preemption. * * It may be assumed that this function implies a write memory barrier before * changing the task state if and only if any tasks are woken up. */ void __wake_up_sync_key(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, void *key) { unsigned long flags; int wake_flags = WF_SYNC; if (unlikely(!q)) return; if (unlikely(!nr_exclusive)) wake_flags = 0; spin_lock_irqsave(&q->lock, flags); __wake_up_common(q, mode, nr_exclusive, wake_flags, key); spin_unlock_irqrestore(&q->lock, flags); } EXPORT_SYMBOL_GPL(__wake_up_sync_key); ===== so one would then track down all calls to __wake_up_sync_key to check the value of nr_exclusive ... etc, etc. and note a couple other things above. first, the comment talks about "wake-one" versus "wake-many" threads, a distinction i still don't understand. also note the "unlikeliness" of nr_exclusive being zero? and an initial check to make sure the wait_queue_head_t isn't NULL? i swear, this code could probably be cleaned up a bit. rday -- ======================================================================== Robert P. J. Day Ottawa, Ontario, CANADA http://crashcourse.ca Twitter: http://twitter.com/rpjday LinkedIn: http://ca.linkedin.com/in/rpjday ========================================================================
participants (2)
-
Robert P. J. Day -
Valdis.Kletnieks＠vt.edu