lkml.org 
[lkml]   [2010]   [Apr]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Date
    SubjectRe: [RFC] sched: implement the exclusive wait queue as a LIFO queue
    On Wed, Apr 28, 2010 at 2:22 PM, Changli Gao <xiaosuo@gmail.com> wrote:
    >
    > I am sorry. the later task_list should be task_list_ex. The updated
    > patch is attached. And I will replace task_list list with hlist for
    > saving space.
    >

    This version replaces list with hlist.


    --
    Regards,
    Changli Gao(xiaosuo@gmail.com)
    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/list.h b/include/linux/list.h
    index 8392884..3622d90 100644
    --- a/include/linux/list.h
    +++ b/include/linux/list.h
    @@ -573,6 +573,11 @@ static inline int hlist_unhashed(const struct hlist_node *h)
    return !h->pprev;
    }

    +static inline int hlist_unhashed_careful(const struct hlist_node *h)
    +{
    + return !h->pprev && !h->next;
    +}
    +
    static inline int hlist_empty(const struct hlist_head *h)
    {
    return !h->first;
    diff --git a/include/linux/wait.h b/include/linux/wait.h
    index a48e16b..5f42123 100644
    --- a/include/linux/wait.h
    +++ b/include/linux/wait.h
    @@ -30,11 +30,9 @@ 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;
    + struct hlist_node task_list;
    };

    struct wait_bit_key {
    @@ -49,7 +47,8 @@ struct wait_bit_queue {

    struct __wait_queue_head {
    spinlock_t lock;
    - struct list_head task_list;
    + struct hlist_head task_list;
    + struct hlist_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 = HLIST_HEAD_INIT, \
    + .task_list_ex = HLIST_HEAD_INIT }

    #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 !hlist_empty(&q->task_list) || !hlist_empty(&q->task_list_ex);
    }

    extern void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait);
    @@ -121,22 +119,22 @@ extern void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait);

    static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
    {
    - list_add(&new->task_list, &head->task_list);
    + hlist_add_head(&new->task_list, &head->task_list);
    }

    /*
    * 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);
    + hlist_add_head(&new->task_list, &head->task_list_ex);
    }

    static inline void __remove_wait_queue(wait_queue_head_t *head,
    wait_queue_t *old)
    {
    - list_del(&old->task_list);
    + hlist_del(&old->task_list);
    }

    void __wake_up(wait_queue_head_t *q, unsigned int mode, int nr, void *key);
    @@ -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);
    }

    /*
    @@ -449,7 +446,7 @@ int wake_bit_function(wait_queue_t *wait, unsigned mode, int sync, void *key);
    wait_queue_t name = { \
    .private = current, \
    .func = function, \
    - .task_list = LIST_HEAD_INIT((name).task_list), \
    + .task_list = { NULL, NULL }, \
    }

    #define DEFINE_WAIT(name) DEFINE_WAIT_FUNC(name, autoremove_wake_function)
    @@ -460,8 +457,7 @@ int wake_bit_function(wait_queue_t *wait, unsigned mode, int sync, void *key);
    .wait = { \
    .private = current, \
    .func = wake_bit_function, \
    - .task_list = \
    - LIST_HEAD_INIT((name).wait.task_list), \
    + .task_list = { NULL, NULL }, \
    }, \
    }

    @@ -469,7 +465,7 @@ int wake_bit_function(wait_queue_t *wait, unsigned mode, int sync, void *key);
    do { \
    (wait)->private = current; \
    (wait)->func = autoremove_wake_function; \
    - INIT_LIST_HEAD(&(wait)->task_list); \
    + INIT_HLIST_NODE(&(wait)->task_list); \
    } while (0)

    /**
    diff --git a/kernel/sched.c b/kernel/sched.c
    index be5ab70..813fd44 100644
    --- a/kernel/sched.c
    +++ b/kernel/sched.c
    @@ -3901,13 +3901,14 @@ EXPORT_SYMBOL(default_wake_function);
    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;
    + wait_queue_t *curr;
    + struct hlist_node *pos, *n;

    - list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
    - unsigned flags = curr->flags;
    + hlist_for_each_entry_safe(curr, pos, n, &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)
    + hlist_for_each_entry_safe(curr, pos, n, &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..b4278f0 100644
    --- a/kernel/wait.c
    +++ b/kernel/wait.c
    @@ -14,7 +14,8 @@ 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_HLIST_HEAD(&q->task_list);
    + INIT_HLIST_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,9 +68,8 @@ 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))
    + if (hlist_unhashed(&wait->task_list))
    __add_wait_queue(q, wait);
    set_current_state(state);
    spin_unlock_irqrestore(&q->lock, flags);
    @@ -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);
    + if (hlist_unhashed(&wait->task_list))
    + __add_wait_queue_ex(q, wait);
    set_current_state(state);
    spin_unlock_irqrestore(&q->lock, flags);
    }
    @@ -119,9 +116,9 @@ void finish_wait(wait_queue_head_t *q, wait_queue_t *wait)
    * have _one_ other CPU that looks at or modifies
    * the list).
    */
    - if (!list_empty_careful(&wait->task_list)) {
    + if (!hlist_unhashed_careful(&wait->task_list)) {
    spin_lock_irqsave(&q->lock, flags);
    - list_del_init(&wait->task_list);
    + hlist_del_init(&wait->task_list);
    spin_unlock_irqrestore(&q->lock, flags);
    }
    }
    @@ -152,8 +149,8 @@ void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait,

    __set_current_state(TASK_RUNNING);
    spin_lock_irqsave(&q->lock, flags);
    - if (!list_empty(&wait->task_list))
    - list_del_init(&wait->task_list);
    + if (!hlist_unhashed(&wait->task_list))
    + hlist_del_init(&wait->task_list);
    else if (waitqueue_active(q))
    __wake_up_locked_key(q, mode, key);
    spin_unlock_irqrestore(&q->lock, flags);
    @@ -165,7 +162,7 @@ int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *
    int ret = default_wake_function(wait, mode, sync, key);

    if (ret)
    - list_del_init(&wait->task_list);
    + hlist_del_init(&wait->task_list);
    return ret;
    }
    EXPORT_SYMBOL(autoremove_wake_function);
    \
     
     \ /
      Last update: 2010-04-28 10:09    [W:0.046 / U:121.148 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site