Skip to contentSkip to conversation

semaphores: add down_interruptible_timeout() and asm-generic/semaphore.h

PATCH In review [email protected] 5 participants 10 messages Feb 27, 2007 – Mar 3, 2007

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

cover semaphores: add down_interruptible_timeout() and asm-generic/semaphore.h

Introduce down_interruptible_timeout() using timers to make the waiter stop waiting by simulating a signal (see first patch for more details). As well introduce asm-generic/semaphore.h and make other architectures use it too.

--

Inaky

#1 lore raw

PATCH 1/2 semaphores: Add down_interruptible_timeout()

I was in a situation where I could really simplify many things by using down_interruptible() with a timeout. I went around looking for how could one be implemented and ran away from the asm code in arch/.

At the end I realized I could make a simple one by setting up a timer that would 'fake' a sigpending situation (setting the task's TIF_SIGPENDING bit) so that the __down_interruptible_failed() path would quit when the timer went off.

I gave it a quick try (must admit, not too tested) and it seems that the setting of TIF_SIGPENDING without really having a signal queued is not having easily visible ugly consequences.

If the timeout arrives right after a signal was delivered but before the thread returns from down_interruptible, then it will also look like a timeout (as the code in the if statement will kick in) -- to some extent, it is 'right' theoretically, as it didn't get the sem before the time expired. TIF_SIGPENDING is still set, so the signal is not lost (unless I miss something else about the signal delivery engine).

IF the timeout arrives after the signal and after down_interruptible returns, no side effects happen. There is a window where the timer could still execute before it is deleted and it would look like a timeout [which theoretically could be right too]. Maybe the result < 0 && data.result < 0 check should be done before del_timer(). Suggestions accepted.

Arjan van de Ven suggested I moved the declaration into asm-generic/semaphore.h to lay the egg for a saner sharing of semaphore code between arches. This patch also introduces that witn the down_interruptible_timeout() decl and the next adds the inclusion to all the arches' semaphore.h [note: haven't been able to compile test all of them, just i386].

---
 include/asm-generic/semaphore.h |   15 ++++++++++
 lib/semaphore-sleepers.c        |   60 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 75 insertions(+)
lib/semaphore-sleepers.c +60 -0
Index: linux.hg/lib/semaphore-sleepers.c
===================================================================
@@ -174,3 +174,63 @@
 	spin_unlock_irqrestore(&sem->wait.lock, flags);
 	return 1;
 }
+
+
+struct dit_data
+{
+	struct task_struct *task;
+	int result;
+};
+
+
+/**
+ * dit_kick_process - set a fake 'signal pending' and kick
+ *
+ * Helper for down_interruptible_timeout(). Sets the signal pending
+ * flag on the task that is waiting for a semaphore and kicks it. That
+ * tells the down_interruptible() code to quit waiting.
+ */
+static
+void dit_kick_process(unsigned long _data)
+{
+	struct dit_data *data = (void *) _data;
+	set_tsk_thread_flag(data->task, TIF_SIGPENDING);
+	data->result = -ETIMEDOUT;
+	kick_process(data->task);
+}
+
+
+/*
+ * Interruptible try to acquire a semaphore.
+ *
+ * If we obtained it, return zero.  If we were interrupted, returns
+ * -EINTR. If we timedout, we return -ETIMEDOUT;
+ *
+ * Note the ugly hack, using a helper timer and function to wake up
+ * the waiter. We need to distinguish, if we get an error, if it was
+ * because we were woken up (-ETIMEDOUT) or for other reason (-EINTR),
+ * hence the last if block.
+ *
+ * There is some fine print if a signal arrives at a time close to the
+ * timeout, being the most confusing case if the timeout arrives AFTER
+ * the signal but before del_timer() get's called. In that case
+ * down_interruptible_timeout() will return -ETIMEDOUT even when the
+ * signal arrived first. However, the signal pending condition is not
+ * cleared.
+ */
+int down_interruptible_timeout(struct semaphore *sem, unsigned long to)
+{
+	int result;
+	struct dit_data data = {
+		.task = get_current(), .result = 0
+	};
+	DEFINE_TIMER(dit_timer, dit_kick_process, to, (unsigned long) &data);
+	add_timer(&dit_timer);
+	result = down_interruptible(sem);
+	del_timer(&dit_timer);
+	if (result < 0 && data.result < 0)
+		result = data.result;
+	return result;
+}
+EXPORT_SYMBOL_GPL(down_interruptible_timeout);
+
include/asm-generic/semaphore.h new file +32 -0
Index: linux.hg/include/asm-generic/semaphore.h
===================================================================
@@ -0,0 +1,32 @@
+/*
+ * Generic code for semaphores
+ *
+ * Copyright (C) 2007 Inaky Perez-Gonzalez <[email protected]>
+ *   - down_interruptible_timeout()'s implementation
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
+ *
+ */
+#ifndef _GENERIC_SEMAPHORE_H
+#define _GENERIC_SEMAPHORE_H
+
+#ifdef __KERNEL__
+
+struct semaphore;
+extern void down_timeout_interruptible(struct semaphore *);
+
+#endif /* #ifdef __KERNEL__ */
+
+#endif /* #define _GENERIC_SEMAPHORE_H */

--

Inaky

#2 lore raw

PATCH 2/2 semaphores: all arches use include/asm-generic/semaphore.h

In reply to [email protected]

As suggested by Arjan van de Ven, introduced a generic semaphore.h for all that arches (previous patch in series). Make all arches include that generic file.

Warning: not compile tested in all arches

---
 include/asm-alpha/semaphore.h     |    1 +
 include/asm-arm/semaphore.h       |    1 +
 include/asm-arm26/semaphore.h     |    1 +
 include/asm-avr32/semaphore.h     |    1 +
 include/asm-cris/semaphore.h      |    1 +
 include/asm-frv/semaphore.h       |    1 +
 include/asm-h8300/semaphore.h     |    1 +
 include/asm-i386/semaphore.h      |    1 +
 include/asm-ia64/semaphore.h      |    1 +
 include/asm-m32r/semaphore.h      |    1 +
 include/asm-m68k/semaphore.h      |    1 +
 include/asm-m68knommu/semaphore.h |    1 +
 include/asm-mips/semaphore.h      |    1 +
 include/asm-parisc/semaphore.h    |    1 +
 include/asm-powerpc/semaphore.h   |    1 +
 include/asm-s390/semaphore.h      |    1 +
 include/asm-sh/semaphore.h        |    1 +
 include/asm-sh64/semaphore.h      |    1 +
 include/asm-sparc/semaphore.h     |    1 +
 include/asm-sparc64/semaphore.h   |    1 +
 include/asm-v850/semaphore.h      |    1 +
 include/asm-x86_64/semaphore.h    |    1 +
 include/asm-xtensa/semaphore.h    |    1 +
 23 files changed, 23 insertions(+)
include/asm-alpha/semaphore.h +1 -0
Index: linux.hg/include/asm-alpha/semaphore.h
===================================================================
@@ -11,6 +11,7 @@
 #include <asm/current.h>
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 #include <linux/compiler.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
include/asm-arm/semaphore.h +1 -0
Index: linux.hg/include/asm-arm/semaphore.h
===================================================================
@@ -11,6 +11,7 @@
 
 #include <asm/atomic.h>
 #include <asm/locks.h>
+#include <asm-generic/semaphore.h>
 
 struct semaphore {
 	atomic_t count;
include/asm-arm26/semaphore.h +1 -0
Index: linux.hg/include/asm-arm26/semaphore.h
===================================================================
@@ -11,6 +11,7 @@
 
 #include <asm/atomic.h>
 #include <asm/locks.h>
+#include <asm-generic/semaphore.h>
 
 struct semaphore {
 	atomic_t count;
include/asm-avr32/semaphore.h +1 -0
Index: linux.hg/include/asm-avr32/semaphore.h
===================================================================
@@ -17,6 +17,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 
include/asm-cris/semaphore.h +1 -0
Index: linux.hg/include/asm-cris/semaphore.h
===================================================================
@@ -13,6 +13,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 /*
  * CRIS semaphores, implemented in C-only so far. 
include/asm-frv/semaphore.h +1 -0
Index: linux.hg/include/asm-frv/semaphore.h
===================================================================
@@ -19,6 +19,7 @@
 #include <linux/wait.h>
 #include <linux/spinlock.h>
 #include <linux/rwsem.h>
+#include <asm-generic/semaphore.h>
 
 #define SEMAPHORE_DEBUG		0
 
include/asm-h8300/semaphore.h +1 -0
Index: linux.hg/include/asm-h8300/semaphore.h
===================================================================
@@ -12,6 +12,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 /*
  * Interrupt-safe semaphores..
include/asm-i386/semaphore.h +1 -0
Index: linux.hg/include/asm-i386/semaphore.h
===================================================================
@@ -38,6 +38,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 
include/asm-ia64/semaphore.h +1 -0
Index: linux.hg/include/asm-ia64/semaphore.h
===================================================================
@@ -10,6 +10,7 @@
 #include <linux/rwsem.h>
 
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 struct semaphore {
 	atomic_t count;
include/asm-m32r/semaphore.h +1 -0
Index: linux.hg/include/asm-m32r/semaphore.h
===================================================================
@@ -17,6 +17,7 @@
 #include <asm/assembler.h>
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 struct semaphore {
 	atomic_t count;
include/asm-m68k/semaphore.h +1 -0
Index: linux.hg/include/asm-m68k/semaphore.h
===================================================================
@@ -13,6 +13,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 /*
  * Interrupt-safe semaphores..
include/asm-m68knommu/semaphore.h +1 -0
Index: linux.hg/include/asm-m68knommu/semaphore.h
===================================================================
@@ -12,6 +12,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 /*
  * Interrupt-safe semaphores..
include/asm-mips/semaphore.h +1 -0
Index: linux.hg/include/asm-mips/semaphore.h
===================================================================
@@ -26,6 +26,7 @@
 
 #include <asm/atomic.h>
 #include <asm/system.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 
include/asm-parisc/semaphore.h +1 -0
Index: linux.hg/include/asm-parisc/semaphore.h
===================================================================
@@ -29,6 +29,7 @@
 #include <linux/rwsem.h>
 
 #include <asm/system.h>
+#include <asm-generic/semaphore.h>
 
 /*
  * The `count' is initialised to the number of people who are allowed to
include/asm-powerpc/semaphore.h +1 -0
Index: linux.hg/include/asm-powerpc/semaphore.h
===================================================================
@@ -12,6 +12,7 @@
 
 #include <asm/atomic.h>
 #include <asm/system.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 
include/asm-s390/semaphore.h +1 -0
Index: linux.hg/include/asm-s390/semaphore.h
===================================================================
@@ -13,6 +13,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 
include/asm-sh/semaphore.h +1 -0
Index: linux.hg/include/asm-sh/semaphore.h
===================================================================
@@ -19,6 +19,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 struct semaphore {
 	atomic_t count;
include/asm-sh64/semaphore.h +1 -0
Index: linux.hg/include/asm-sh64/semaphore.h
===================================================================
@@ -26,6 +26,7 @@
 
 #include <asm/system.h>
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 struct semaphore {
 	atomic_t count;
include/asm-sparc/semaphore.h +1 -0
Index: linux.hg/include/asm-sparc/semaphore.h
===================================================================
@@ -6,6 +6,7 @@
 #ifdef __KERNEL__
 
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 
include/asm-sparc64/semaphore.h +1 -0
Index: linux.hg/include/asm-sparc64/semaphore.h
===================================================================
@@ -10,6 +10,7 @@
 
 #include <asm/atomic.h>
 #include <asm/system.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 
include/asm-v850/semaphore.h +1 -0
Index: linux.hg/include/asm-v850/semaphore.h
===================================================================
@@ -7,6 +7,7 @@
 #include <linux/rwsem.h>
 
 #include <asm/atomic.h>
+#include <asm-generic/semaphore.h>
 
 struct semaphore {
 	atomic_t count;
include/asm-x86_64/semaphore.h +1 -0
Index: linux.hg/include/asm-x86_64/semaphore.h
===================================================================
@@ -39,6 +39,7 @@
 #include <asm/system.h>
 #include <asm/atomic.h>
 #include <asm/rwlock.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 #include <linux/stringify.h>
include/asm-xtensa/semaphore.h +1 -0
Index: linux.hg/include/asm-xtensa/semaphore.h
===================================================================
@@ -13,6 +13,7 @@
 
 #include <asm/atomic.h>
 #include <asm/system.h>
+#include <asm-generic/semaphore.h>
 #include <linux/wait.h>
 #include <linux/rwsem.h>
 

--

Inaky

#3 lore raw
In reply to [email protected]
Quoted 4 lines · On Mon, Feb 26, 2007 at 04:13:38PM -0800, [email protected] wrote:

Introduce down_interruptible_timeout() using timers to make the waiter stop waiting by simulating a signal (see first patch for more details). As well introduce asm-generic/semaphore.h and make other architectures use it too.

What do you want this for? Do you really need a full counting semaphore or do you actually want a mutex?

#4 lore raw
Quoted 8 lines · Christoph Hellwig
Quoted 4 lines · On Mon, Feb 26, 2007 at 04:13:38PM -0800, [email protected] wrote:

Introduce down_interruptible_timeout() using timers to make the waiter stop waiting by simulating a signal (see first patch for more details). As well introduce asm-generic/semaphore.h and make other architectures use it too.

What do you want this for? Do you really need a full counting semaphore or do you actually want a mutex?

Yeah, I need semaphore. This is a hw register that says when the hw is ready to accept a new command. Code that wants to send commands has to down the semaphore and then send it. When hw is ready to get a new command, it sends and IRQ and the IRQ up()s the semaphore.

Now, we don't want to hang on that down() forever if the hw spaces out. If we get a timeout, we can try recovery actions (like resetting it, for sake of being polite).

I use this in the WHCI Ultra Wide Band radio controller code (coming soon to a hw store near you).

Cristoph, I still wonder how the hell you do it to spot every message that comes into lkml -- I bet you have a cluster of employees using your name doing it... :)

-- Inaky

#5 lore raw
Quoted 4 lines

Yeah, I need semaphore. This is a hw register that says when the hw is ready to accept a new command. Code that wants to send commands has to down the semaphore and then send it. When hw is ready to get a new command, it sends and IRQ and the IRQ up()s the semaphore.

So you need a mutex not a semaphore

Quoted 4 lines

Now, we don't want to hang on that down() forever if the hw spaces out. If we get a timeout, we can try recovery actions (like resetting it, for sake of being polite).

Makes sense but you can also do that with mutexes, and its mutex_interruptible_timeout() you need I suspect ?

Alan

#6 lore raw
Quoted 6 lines · Alan
Quoted 4 lines

Yeah, I need semaphore. This is a hw register that says when the hw is ready to accept a new command. Code that wants to send commands has to down the semaphore and then send it. When hw is ready to get a new command, it sends and IRQ and the IRQ up()s the semaphore.

So you need a mutex not a semaphore

Theoretically I could use a mutex. Practically it would trigger ugly complications. Only the owner can unlock a mutex (for example), so I could not unlock from an IRQ handler -- not to mention that the semantic rules outlined in Documentation/mutex-design.txt explicitly forbid IRQ usage.

And then, this is what semaphores where designed for, as gates :) for once that I get to use a semaphore properly...

#7 lore raw

Hi Inaky,

Quoted 8 lines · Inaky Perez-Gonzalez
Quoted 6 lines · Alan
Quoted 4 lines

Yeah, I need semaphore. This is a hw register that says when the hw is ready to accept a new command. Code that wants to send commands has to down the semaphore and then send it. When hw is ready to get a new command, it sends and IRQ and the IRQ up()s the semaphore.

So you need a mutex not a semaphore

Quoted 8 lines

Theoretically I could use a mutex. Practically it would trigger ugly complications. Only the owner can unlock a mutex (for example), so I could not unlock from an IRQ handler -- not to mention that the semantic rules outlined in Documentation/mutex-design.txt explicitly forbid IRQ usage.

And then, this is what semaphores where designed for, as gates :) for once that I get to use a semaphore properly...

But they are not required for that :-)

I would suggest to use an irq-safe spinlock for the hardware access
and a status indicator (ready for command), if this is really just a command register. If the status indicator is updated (in IRQ) and read under spinlock, that is safe.

If that command sending is speed critical, please try a FIFO and batch that stuff.

Timeout based locking mechanisms are flawed, because they introduce the hard to find timing sensitive bugs.

Please try sth. different (e.g. like suggested above).

Semaphores aren't good "busy/ready flags", as you might have already noticed.

Many Thanks and Best Regards

Ingo Oeser, the down{_interruptible,}_timeout() implementation of Linux :-)

#8 lore raw
Quoted 20 lines · Ingo Oeser

Hi Inaky,

Quoted 8 lines · Inaky Perez-Gonzalez
Quoted 6 lines · Alan
Quoted 4 lines

Yeah, I need semaphore. This is a hw register that says when the hw is ready to accept a new command. Code that wants to send commands has to down the semaphore and then send it. When hw is ready to get a new command, it sends and IRQ and the IRQ up()s the semaphore.

So you need a mutex not a semaphore

Quoted 8 lines

Theoretically I could use a mutex. Practically it would trigger ugly complications. Only the owner can unlock a mutex (for example), so I could not unlock from an IRQ handler -- not to mention that the semantic rules outlined in Documentation/mutex-design.txt explicitly forbid IRQ usage.

And then, this is what semaphores where designed for, as gates :) for once that I get to use a semaphore properly...

Quoted 6 lines

But they are not required for that :-)

I would suggest to use an irq-safe spinlock for the hardware access and a status indicator (ready for command), if this is really just a command register. If the status indicator is updated (in IRQ) and read under spinlock, that is safe.

I have that already. The registers are shared for the two flows of information, sending commands to the device and receiving notifications from them, so any access to the registers is protected by a IRQ spinlock.

Now, it would be kind of pointless to do a busy poll for the command-ready indicator if I have an IRQ that notifies me of it, ergo there the need for a semaphore. I could use a waitqueue, as akpm suggested, but I still need something else that says 'its only me who has the command sending privilege now', and I'd still need to push a timeout something to detect broken hw.

So:
1 - to send a command I need to wait for !register.execute_command 2 - to access 'register', I need to have an spinlock
3 - when register.executing_command drops to zero, I get an IRQ 4 - other code flows access register

If I didn't have to wait for register.execute_command(), we have the usual construct:

execute_command(hw) {
...
spin_lock_irqsave(hw->lock, flags);
prep_command_buffer;
writel(execute_command, register)
spin_unlock_irqrestore(hw->lock, flags);
...
}

checking for 'register.execute_command == 0' inside the spinlock protected area, bailing out if busy and waiting for a while before retrying is another (fugly) option that I am not willing to implement.

Another option is using a wait_event() mechanism that is woken up from the IRQ that says register.execute_command is zero, but that's basically a semaphore.

A FIFO or queue is the most complex of the mechanisms, because now I have to create all this support infrastructure to store the queued commands.

A semaphore simplifies everything -- I guess I have brain corruption, because I can't understand your objections.

execute_command(hw) {
...
down(hw->cmd_semaphore);
/* now it's only this thread who can send a command */ spin_lock_irqsave(hw->lock, flags); prep_command_buffer;
writel(execute_command, register) spin_unlock_irqrestore(hw->lock, flags);
...
}

irq_handler(hw) {
...
spin_lock_irqsave(hw->lock, flags);
if (readl(irq_register & execute_command_cleared))

	up(hw->cmd_sem);

...
// touch command register here for other stuff
...
spin_unlock_irqrestore(hw->lock, flags);
...
}

It's not a mutex or spinlock, is a gating or sequencing mechanism that allows just one guy at a time.

Quoted 2 lines

Timeout based locking mechanisms are flawed, because they introduce the hard to find timing sensitive bugs.

The only reason why the timeout is added is to detect when the hw is dead so we can recover. This shouldn't create timing bugs because if it times out [in this case], the hw is broken and we are going to reset it.

Quoted 2 lines

Semaphores aren't good "busy/ready flags", as you might have already noticed.

That's why I am not using them as a flag.

-- Inaky

maintainer
#9 lore raw
In reply to Inaky Perez-Gonzalez
Quoted 11 lines · On Mon, 26 Feb 2007 16:54:17 -0800 Inaky Perez-Gonzalez…
Quoted 8 lines · Christoph Hellwig
Quoted 4 lines · On Mon, Feb 26, 2007 at 04:13:38PM -0800, [email protected] wrote:

Introduce down_interruptible_timeout() using timers to make the waiter stop waiting by simulating a signal (see first patch for more details). As well introduce asm-generic/semaphore.h and make other architectures use it too.

What do you want this for? Do you really need a full counting semaphore or do you actually want a mutex?

Quoted 9 lines

Yeah, I need semaphore. This is a hw register that says when the hw is ready to accept a new command. Code that wants to send commands has to down the semaphore and then send it. When hw is ready to get a new command, it sends and IRQ and the IRQ up()s the semaphore.

Now, we don't want to hang on that down() forever if the hw spaces out. If we get a timeout, we can try recovery actions (like resetting it, for sake of being polite).

This is a very common pattern - for example, shoving characters down a uart or a parport. Nobody else has needed to invent new locking infrastructure to do such things and I'd prefer not to do so now.

Can you not do things more conventionally within that driver? Use waitqueues for sleeping with timeout, use a spinlock for serialisation against the device registers. There are squillions of examples in drivers/*, surely.