I've pushed out a new version of the semaphore tree.  I'll send the new
patches as a reply to this mail.

git://git.kernel.org/pub/scm/linux/kernel/git/willy/misc.git semaphore-20080314

Changes:
 - Dropped all the asm/semaphore.h changes.  They're just causing
   conflicts for linux-next, and while Stephen assures me that fixing
   them up is trivial and he doesn't mind, I'd rather not burn him out
   prematurely.  I still intend to push them, but they don't need to be
   part of linux-next, IMO.
 - Split the addition of down_killable() out of the main patch.  It's
   logically separate (adding a new interface), and it was sheer
   laziness to not split it out in the first place.
 - New functionality!  down_timeout().  Just look at the mess in
   acpi/osl.c where it tries to emulate it.  It's very little extra code
   to add it to kernel/semaphore.c, so I thought it was a good idea.
 - Simplify the implementation.  Dave Howells said the current algorithm
   makes his head hurt, and in retrospect, perhaps I was just trying to
   be too clever.
 - Fix the lockdep bug (thanks to Peter Zijlstra)
 - Remove an unsightly and unnecessary unlikely() (thanks to Harvey Harrison)
 - Fix the down() while interrupts disabled bug (thanks to Ingo Molnar)
   (I may have posted this one before.  Not sure.)

I've tested the end result of this with Dave Howells' synchro-test module
and not found any problems.

If you prefer, you can also find the patches at
http://git.kernel.org/?p=linux/kernel/git/willy/misc.git;a=shortlog;h=semaphore-200803...

-- 
Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."
--

From: Harvey Harrison <harvey.harrison@gmail.com>
Subject: [PATCH] semaphore: add stubs for kerneldoc to semphore functions

The difference between down/down_trylock/down_interruptable/down_killable
should be expanded to note the difference/use case, a simple stub is added here.

Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com>
---
This applies on top of the last patch I sent, feel free to just use it as
a base for a fuller version.

 kernel/semaphore.c |   37 ++++++++++++++++++++++++++++++++++---
 1 files changed, 34 insertions(+), 3 deletions(-)

diff --git a/kernel/semaphore.c b/kernel/semaphore.c
index bae1017..f48ac5e 100644
--- a/kernel/semaphore.c
+++ b/kernel/semaphore.c
@@ -98,6 +98,12 @@ static noinline void __sched __up(struct semaphore *sem)
 	wake_up_process(waiter->task);
 }
 
+/**
+ * down - acquire the semaphore
+ * @sem: the semaphore to be acquired
+ *
+ * This can be called from interrupt context, unlike mutexes.
+ */
 void down(struct semaphore *sem)
 {
 	unsigned long flags;
@@ -111,6 +117,12 @@ void down(struct semaphore *sem)
 }
 EXPORT_SYMBOL(down);
 
+/**
+ * down_killable - try to acquire the semaphore
+ * @sem: the semaphore to be acquired
+ *
+ * This can be called from interrupt context, unlike mutexes.
+ */
 int down_interruptible(struct semaphore *sem)
 {
 	unsigned long flags;
@@ -127,6 +139,12 @@ int down_interruptible(struct semaphore *sem)
 }
 EXPORT_SYMBOL(down_interruptible);
 
+/**
+ * down_killable - try to acquire the semaphore
+ * @sem: the semaphore to be acquired
+ *
+ * This can be called from interrupt context, unlike mutexes.
+ */
 int down_killable(struct semaphore *sem)
 {
 	unsigned long flags;
@@ -147,7 +165,7 @@ EXPORT_SYMBOL(down_killable);
  * down_trylock - try to acquire the semaphore, without waiting
  * @sem: the semaphore to be acquired
  *
- * Try to acquire the semaphore atomically.  Returns 0 if the mutex has
+ * Try to acquire the semaphore atomically.  Returns 0 if ...
[ message continues ]

Hi Harvey,


Mismatching function names.

	Hannes
--

From: Harvey Harrison <harvey.harrison@gmail.com>
Subject: [PATCH] semaphore: eliminate forward declarations

Move the internal helper functions before their use and remove
the forward declarations.

Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com>
---
This is a pretty trivial thing...other than this looks good to me.

 kernel/semaphore.c |  156 +++++++++++++++++++++++++---------------------------
 1 files changed, 75 insertions(+), 81 deletions(-)

diff --git a/kernel/semaphore.c b/kernel/semaphore.c
index bef977b..bae1017 100644
--- a/kernel/semaphore.c
+++ b/kernel/semaphore.c
@@ -22,11 +22,81 @@
  * semaphore.  If it's zero, there may be tasks waiting on the list.
  */
 
-static noinline void __down(struct semaphore *sem);
-static noinline int __down_interruptible(struct semaphore *sem);
-static noinline int __down_killable(struct semaphore *sem);
-static noinline int __down_timeout(struct semaphore *sem, long jiffies);
-static noinline void __up(struct semaphore *sem);
+/* Functions for the contended case */
+
+struct semaphore_waiter {
+	struct list_head list;
+	struct task_struct *task;
+	int up;
+};
+
+/*
+ * Because this function is inlined, the 'state' parameter will be
+ * constant, and thus optimised away by the compiler.  Likewise the
+ * 'timeout' parameter for the cases without timeouts.
+ */
+static inline int __sched __down_common(struct semaphore *sem, long state,
+								long timeout)
+{
+	struct task_struct *task = current;
+	struct semaphore_waiter waiter;
+
+	list_add_tail(&waiter.list, &sem->wait_list);
+	waiter.task = task;
+	waiter.up = 0;
+
+	for (;;) {
+		if (state == TASK_INTERRUPTIBLE && signal_pending(task))
+			goto interrupted;
+		if (state == TASK_KILLABLE && fatal_signal_pending(task))
+			goto interrupted;
+		if (timeout <= 0)
+			goto timed_out;
+		__set_task_state(task, state);
+		spin_unlock_irq(&sem->lock);
+		timeout = schedule_timeout(timeout);
+		spin_loc...
[ message continues ]

quota.h currently relies on asm/semaphore.h (through some chain; it
doesn't actually include semaphore.h itself) to include wait.h.  As
well as being bad practice to rely on an implicit include, subsequent
patches will break this.  While I'm in this file, add atomic.h and
list.h, and sort the list of includes.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 include/linux/quota.h |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/include/linux/quota.h b/include/linux/quota.h
index 6e0393a..eb560d0 100644
--- a/include/linux/quota.h
+++ b/include/linux/quota.h
@@ -160,14 +160,18 @@ enum {
 
 
 #ifdef __KERNEL__
-#include <linux/spinlock.h>
-#include <linux/rwsem.h>
+#include <linux/list.h>
 #include <linux/mutex.h>
+#include <linux/rwsem.h>
+#include <linux/spinlock.h>
+#include <linux/wait.h>
 
 #include <linux/dqblk_xfs.h>
 #include <linux/dqblk_v1.h>
 #include <linux/dqblk_v2.h>
 
+#include <asm/atomic.h>
+
 extern spinlock_t dq_data_lock;
 
 /* Maximal numbers of writes for quota operation (insert/delete/update)
-- 
1.5.4.3

--

kernel_lock.c uses DECLARE_MUTEX, up() and down() without explicitly
including asm/semaphore.h.  This is fragile and leaves it vulnerable
to breakage during header reorganisations.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 lib/kernel_lock.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/lib/kernel_lock.c b/lib/kernel_lock.c
index 812dbf0..fbc11a3 100644
--- a/lib/kernel_lock.c
+++ b/lib/kernel_lock.c
@@ -8,6 +8,7 @@
 #include <linux/smp_lock.h>
 #include <linux/module.h>
 #include <linux/kallsyms.h>
+#include <asm/semaphore.h>
 
 /*
  * The 'big kernel semaphore'
-- 
1.5.4.3

--

Semaphores are no longer performance-critical, so a generic C
implementation is better for maintainability, debuggability and
extensibility.  Thanks to Peter Zijlstra for fixing the lockdep
warning.  Thanks to Harvey Harrison for pointing out that the
unlikely() was unnecessary.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Acked-by: Ingo Molnar <mingo@elte.hu>
---
 arch/alpha/kernel/Makefile               |    2 +-
 arch/alpha/kernel/alpha_ksyms.c          |    9 -
 arch/alpha/kernel/semaphore.c            |  224 --------------------------
 arch/arm/kernel/Makefile                 |    2 +-
 arch/arm/kernel/semaphore.c              |  221 --------------------------
 arch/avr32/kernel/Makefile               |    2 +-
 arch/avr32/kernel/semaphore.c            |  148 -----------------
 arch/blackfin/Kconfig                    |    4 -
 arch/blackfin/kernel/bfin_ksyms.c        |    5 -
 arch/cris/kernel/Makefile                |    3 +-
 arch/cris/kernel/crisksyms.c             |    7 -
 arch/cris/kernel/semaphore.c             |  129 ---------------
 arch/frv/kernel/Makefile                 |    2 +-
 arch/frv/kernel/frv_ksyms.c              |    1 -
 arch/frv/kernel/semaphore.c              |  155 ------------------
 arch/h8300/kernel/Makefile               |    2 +-
 arch/h8300/kernel/h8300_ksyms.c          |    1 -
 arch/h8300/kernel/semaphore.c            |  132 ----------------
 arch/ia64/kernel/Makefile                |    2 +-
 arch/ia64/kernel/ia64_ksyms.c            |    6 -
 arch/ia64/kernel/semaphore.c             |  165 -------------------
 arch/m32r/kernel/Makefile                |    2 +-
 arch/m32r/kernel/m32r_ksyms.c            |    5 -
 arch/m32r/kernel/semaphore.c             |  185 ----------------------
 arch/m68k/kernel/Makefile                |    2 +-
 arch/m68k/kernel/m68k_ksyms.c            |    6 -
 arch/m68k/kernel/semaphore.c             |  132 ----------------
 arch/m68k/lib/Makefile                   |    2 +-
 arch/m68k/lib/sem...
[ message continues ]

down_killable() is the functional counterpart of mutex_lock_killable.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 include/linux/semaphore.h |    6 ++++++
 kernel/semaphore.c        |   22 ++++++++++++++++++++++
 2 files changed, 28 insertions(+), 0 deletions(-)

diff --git a/include/linux/semaphore.h b/include/linux/semaphore.h
index b3c691b..88f2a28 100644
--- a/include/linux/semaphore.h
+++ b/include/linux/semaphore.h
@@ -62,6 +62,12 @@ extern void down(struct semaphore *sem);
 extern int __must_check down_interruptible(struct semaphore *sem);
 
 /*
+ * As down_interruptible(), except the sleep may only be interrupted by
+ * signals which are fatal to this process.
+ */
+extern int __must_check down_killable(struct semaphore *sem);
+
+/*
  * As down(), except this function will not sleep.  It will return 0 if it
  * acquired the semaphore and 1 if the semaphore was contended.  This
  * function may be called from any context, including interrupt and softirq.
diff --git a/kernel/semaphore.c b/kernel/semaphore.c
index d5a7270..2da2aed 100644
--- a/kernel/semaphore.c
+++ b/kernel/semaphore.c
@@ -34,6 +34,7 @@
 
 static noinline void __down(struct semaphore *sem);
 static noinline int __down_interruptible(struct semaphore *sem);
+static noinline int __down_killable(struct semaphore *sem);
 static noinline void __up(struct semaphore *sem);
 
 void down(struct semaphore *sem)
@@ -61,6 +62,20 @@ int down_interruptible(struct semaphore *sem)
 }
 EXPORT_SYMBOL(down_interruptible);
 
+int down_killable(struct semaphore *sem)
+{
+	unsigned long flags;
+	int result = 0;
+
+	spin_lock_irqsave(&sem->lock, flags);
+	if (unlikely(sem->count-- <= 0))
+		result = __down_killable(sem);
+	spin_unlock_irqrestore(&sem->lock, flags);
+
+	return result;
+}
+EXPORT_SYMBOL(down_killable);
+
 /**
  * down_trylock - try to acquire the semaphore, without waiting
  * @sem: the semaphore to be acquired
@@ -143,6 +158,8 @@ static inline int __s...
[ message continues ]

ACPI currently emulates a timeout for semaphores with calls to
down_trylock and sleep.  This produces horrible behaviour in terms of
fairness and excessive wakeups.  Now that we have a unified semaphore
implementation, adding a real down_trylock is almost trivial.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 drivers/acpi/osl.c        |   89 +++++++++++----------------------------------
 include/linux/semaphore.h |    6 +++
 kernel/semaphore.c        |   42 ++++++++++++++++++----
 3 files changed, 62 insertions(+), 75 deletions(-)

diff --git a/drivers/acpi/osl.c b/drivers/acpi/osl.c
index 065819b..2adfb6d 100644
--- a/drivers/acpi/osl.c
+++ b/drivers/acpi/osl.c
@@ -4,6 +4,8 @@
  *  Copyright (C) 2000       Andrew Henroid
  *  Copyright (C) 2001, 2002 Andy Grover <andrew.grover@intel.com>
  *  Copyright (C) 2001, 2002 Paul Diefenbaugh <paul.s.diefenbaugh@intel.com>
+ *  Copyright (c) 2008 Intel Corporation
+ *   Author: Matthew Wilcox <willy@linux.intel.com>
  *
  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  *
@@ -37,15 +39,18 @@
 #include <linux/workqueue.h>
 #include <linux/nmi.h>
 #include <linux/acpi.h>
-#include <acpi/acpi.h>
-#include <asm/io.h>
-#include <acpi/acpi_bus.h>
-#include <acpi/processor.h>
-#include <asm/uaccess.h>
-
 #include <linux/efi.h>
 #include <linux/ioport.h>
 #include <linux/list.h>
+#include <linux/jiffies.h>
+#include <linux/semaphore.h>
+
+#include <asm/io.h>
+#include <asm/uaccess.h>
+
+#include <acpi/acpi.h>
+#include <acpi/acpi_bus.h>
+#include <acpi/processor.h>
 
 #define _COMPONENT		ACPI_OS_SERVICES
 ACPI_MODULE_NAME("osl");
@@ -848,7 +853,6 @@ acpi_os_create_semaphore(u32 max_units, u32 initial_units, acpi_handle * handle)
 {
 	struct semaphore *sem = NULL;
 
-
 	sem = acpi_os_allocate(sizeof(struct semaphore));
 	if (!sem)
 		return AE_NO_MEMO...
[ message continues ]

By removing the negative values of 'count' and relying on the wait_list to
indicate whether we have any waiters, we can simplify the implementation
by removing the protection against an unlikely race condition.  Thanks to
David Howells for his suggestions.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 include/linux/semaphore.h |    9 ++---
 kernel/semaphore.c        |   78 ++++++++++++++-------------------------------
 2 files changed, 27 insertions(+), 60 deletions(-)

diff --git a/include/linux/semaphore.h b/include/linux/semaphore.h
index a107aeb..a7125da 100644
--- a/include/linux/semaphore.h
+++ b/include/linux/semaphore.h
@@ -15,15 +15,12 @@
 
 /*
  * The spinlock controls access to the other members of the semaphore.
- * 'count' is decremented by every task which calls down*() and incremented
- * by every call to up().  Thus, if it is positive, it indicates how many
- * more tasks may acquire the lock.  If it is negative, it indicates how
- * many tasks are waiting for the lock.  Tasks waiting for the lock are
- * kept on the wait_list.
+ * 'count' represents how many more tasks can acquire this semaphore.
+ * Tasks waiting for the lock are kept on the wait_list.
  */
 struct semaphore {
 	spinlock_t		lock;
-	int			count;
+	unsigned int		count;
 	struct list_head	wait_list;
 };
 
diff --git a/kernel/semaphore.c b/kernel/semaphore.c
index 5a12a85..bef977b 100644
--- a/kernel/semaphore.c
+++ b/kernel/semaphore.c
@@ -18,18 +18,8 @@
  * down_trylock() and up() can be called from interrupt context.
  * So we have to disable interrupts when taking the lock.
  *
- * The ->count variable, if positive, defines how many more tasks can
- * acquire the semaphore.  If negative, it represents how many tasks are
- * waiting on the semaphore (*).  If zero, no tasks are waiting, and no more
- * tasks can acquire the semaphore.
- *
- * (*) Except for the window between one task calling up() and the task
- * sleeping in a __down_common() waking up.  In or...
[ message continues ]