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.117 / U:1.008 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site