Re: [RFC] sched: implement the exclusive wait queue as a LIFO queue

[Xiaotian Feng]

On Wed, Apr 28, 2010 at 1:03 PM, Changli Gao <xiaosuo@xxxxxxxxx> wrote:
> implement the exclusive wait queue as a LIFO queue
>
> If the exclusive wait queue is also a LIFO queue as the normal wait queue, the
> process who goes to sleep recently, will be woke up first. As its memory is
> more likely in cache, we will get better performance. And when there are many
> processes waiting on a exclusive wait queue, some of them may not be woke up,
> if the others can handle the workload, and it will reduce the load of
> the scheduler.
>

Starve some processes for performance?

> Note: before applying this patch, you need my previous patch patched first.
> https://patchwork.kernel.org/patch/95600/
>
> Signed-off-by: Changli Gao <xiaosuo@xxxxxxxxx>
> ----
> Âfs/eventpoll.c    |  Â3 +--
> Âinclude/linux/wait.h | Â 17 +++++++----------
> Âkernel/sched.c    |  Â8 ++++----
> Âkernel/wait.c    Â|  Â9 +++------
> Â4 files changed, 15 insertions(+), 22 deletions(-)
> diff --git a/fs/eventpoll.c b/fs/eventpoll.c
> index bd056a5..e9b3ebe 100644
> --- a/fs/eventpoll.c
> +++ b/fs/eventpoll.c
> @@ -1140,8 +1140,7 @@ retry:
> Â Â Â Â Â Â Â Â * ep_poll_callback() when events will become available.
> Â Â Â Â Â Â Â Â */
> Â Â Â Â Â Â Â Âinit_waitqueue_entry(&wait, current);
> - Â Â Â Â Â Â Â wait.flags |= WQ_FLAG_EXCLUSIVE;
> - Â Â Â Â Â Â Â __add_wait_queue(&ep->wq, &wait);
> + Â Â Â Â Â Â Â __add_wait_queue_ex(&ep->wq, &wait);
>
> Â Â Â Â Â Â Â Âfor (;;) {
> Â Â Â Â Â Â Â Â Â Â Â Â/*
> diff --git a/include/linux/wait.h b/include/linux/wait.h
> index a48e16b..95c127d 100644
> --- a/include/linux/wait.h
> +++ b/include/linux/wait.h
> @@ -30,8 +30,6 @@ typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int flags, v
> Âint default_wake_function(wait_queue_t *wait, unsigned mode, int flags, void *key);
>
> Âstruct __wait_queue {
> - Â Â Â unsigned int flags;
> -#define WQ_FLAG_EXCLUSIVE Â Â Â0x01
> Â Â Â Âvoid *private;
> Â Â Â Âwait_queue_func_t func;
> Â Â Â Âstruct list_head task_list;
> @@ -50,6 +48,7 @@ struct wait_bit_queue {
> Âstruct __wait_queue_head {
> Â Â Â Âspinlock_t lock;
> Â Â Â Âstruct list_head task_list;
> + Â Â Â struct list_head task_list_ex;
> Â};
> Âtypedef struct __wait_queue_head wait_queue_head_t;
>
> @@ -69,7 +68,8 @@ struct task_struct;
>
> Â#define __WAIT_QUEUE_HEAD_INITIALIZER(name) { Â Â Â Â Â Â Â Â Â Â Â Â Â\
>    Â.lock      = __SPIN_LOCK_UNLOCKED(name.lock),       Â\
> -    .task_list   Â= { &(name).task_list, &(name).task_list } }
> +    .task_list   Â= { &(name).task_list, &(name).task_list },   \
> +    .task_list_ex  = { &(name).task_list_ex, &(name).task_list_ex } }
>
> Â#define DECLARE_WAIT_QUEUE_HEAD(name) \
> Â Â Â Âwait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)
> @@ -97,7 +97,6 @@ extern void __init_waitqueue_head(wait_queue_head_t *q, struct lock_class_key *)
>
> Âstatic inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
> Â{
> - Â Â Â q->flags = 0;
> Â Â Â Âq->private = p;
> Â Â Â Âq->func = default_wake_function;
> Â}
> @@ -105,14 +104,13 @@ static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
> Âstatic inline void init_waitqueue_func_entry(wait_queue_t *q,
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âwait_queue_func_t func)
> Â{
> - Â Â Â q->flags = 0;
> Â Â Â Âq->private = NULL;
> Â Â Â Âq->func = func;
> Â}
>
> Âstatic inline int waitqueue_active(wait_queue_head_t *q)
> Â{
> - Â Â Â return !list_empty(&q->task_list);
> + Â Â Â return !list_empty(&q->task_list) || !list_empty(&q->task_list);
> Â}
>
> Âextern void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait);
> @@ -127,10 +125,10 @@ static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
> Â/*
> Â* Used for wake-one threads:
> Â*/
> -static inline void __add_wait_queue_tail(wait_queue_head_t *head,
> +static inline void __add_wait_queue_ex(wait_queue_head_t *head,
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âwait_queue_t *new)
> Â{
> - Â Â Â list_add_tail(&new->task_list, &head->task_list);
> + Â Â Â list_add(&new->task_list, &head->task_list_ex);
> Â}
>
> Âstatic inline void __remove_wait_queue(wait_queue_head_t *head,
> @@ -409,8 +407,7 @@ do { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> Âstatic inline void add_wait_queue_exclusive_locked(wait_queue_head_t *q,
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â wait_queue_t * wait)
> Â{
> - Â Â Â wait->flags |= WQ_FLAG_EXCLUSIVE;
> - Â Â Â __add_wait_queue_tail(q, Âwait);
> + Â Â Â __add_wait_queue_ex(q, Âwait);
> Â}
>
> Â/*
> diff --git a/kernel/sched.c b/kernel/sched.c
> index be5ab70..59b1534 100644
> --- a/kernel/sched.c
> +++ b/kernel/sched.c
> @@ -3903,11 +3903,11 @@ static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
> Â{
> Â Â Â Âwait_queue_t *curr, *next;
>
> - Â Â Â list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
> - Â Â Â Â Â Â Â unsigned flags = curr->flags;
> + Â Â Â list_for_each_entry_safe(curr, next, &q->task_list, task_list)
> + Â Â Â Â Â Â Â curr->func(curr, mode, wake_flags, key);
>
> - Â Â Â Â Â Â Â if (curr->func(curr, mode, wake_flags, key) &&
> - Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
> + Â Â Â list_for_each_entry_safe(curr, next, &q->task_list_ex, task_list) {
> + Â Â Â Â Â Â Â if (curr->func(curr, mode, wake_flags, key) && !--nr_exclusive)
> Â Â Â Â Â Â Â Â Â Â Â Âbreak;
> Â Â Â Â}
> Â}
> diff --git a/kernel/wait.c b/kernel/wait.c
> index c4bd3d8..a0559df 100644
> --- a/kernel/wait.c
> +++ b/kernel/wait.c
> @@ -15,6 +15,7 @@ void __init_waitqueue_head(wait_queue_head_t *q, struct lock_class_key *key)
> Â Â Â Âspin_lock_init(&q->lock);
> Â Â Â Âlockdep_set_class(&q->lock, key);
> Â Â Â ÂINIT_LIST_HEAD(&q->task_list);
> + Â Â Â INIT_LIST_HEAD(&q->task_list_ex);
> Â}
>
> ÂEXPORT_SYMBOL(__init_waitqueue_head);
> @@ -23,7 +24,6 @@ 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);
> @@ -34,9 +34,8 @@ 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);
> + Â Â Â __add_wait_queue_ex(q, wait);
> Â Â Â Âspin_unlock_irqrestore(&q->lock, flags);
> Â}
> ÂEXPORT_SYMBOL(add_wait_queue_exclusive);
> @@ -69,7 +68,6 @@ prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
> Â{
> Â Â Â Âunsigned long flags;
>
> - Â Â Â wait->flags &= ~WQ_FLAG_EXCLUSIVE;
> Â Â Â Âspin_lock_irqsave(&q->lock, flags);
> Â Â Â Âif (list_empty(&wait->task_list))
> Â Â Â Â Â Â Â Â__add_wait_queue(q, wait);
> @@ -83,10 +81,9 @@ prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state)
> Â{
> Â Â Â Âunsigned long flags;
>
> - Â Â Â wait->flags |= WQ_FLAG_EXCLUSIVE;
> Â Â Â Âspin_lock_irqsave(&q->lock, flags);
> Â Â Â Âif (list_empty(&wait->task_list))
> - Â Â Â Â Â Â Â __add_wait_queue_tail(q, wait);
> + Â Â Â Â Â Â Â __add_wait_queue_ex(q, wait);
> Â Â Â Âset_current_state(state);
> Â Â Â Âspin_unlock_irqrestore(&q->lock, flags);
> Â}
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at Âhttp://vger.kernel.org/majordomo-info.html
> Please read the FAQ at Âhttp://www.tux.org/lkml/
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/