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

[Changli Gao <xiaosuo@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 333 bytes --]

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)

[-- Attachment #2: wq-ex-lifo.diff --]
[-- Type: text/plain, Size: 8628 bytes --]

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);