Replace completions with semaphores

A long long time ago when dinosaurs roamed the earth and tech company stock valuations were high (2001), the primitive
of the completion was introduced to save us from a problem with semaphores. Those interested in the details can examine
http://www.ussg.iu.edu/hypermail/linux/kernel/0107.3/0674.html and related messages, but everyone else can take my word for it that, with the generic semaphores I hope will be merged in 2.6.26, semaphores no longer have the problem that caused us to switch to completions.

So does it make sense to retain the completion as a primitive in Linux? On the one hand, it clearly denotes how one uses it -- that it's initially 'locked' and becomes 'unlocked' later. On the other hand, it is Yet Another Thing to be maintained; I had to add wait_for_completion_killable(), probably there needs to be a wait_for_completion_killable_timeout() too.

I have a cheesy hack to remove them without causing too much disturbance. Obviously, I would never suggest this for inclusion -- #define completion semaphore should be enough to raise anyone's eyebrows -- but it's a starting point to decide whether or not to get rid of completions or retain them in some way while basing their implementation on semaphores, or leave them the hell alone.

I'm a little puzzled at the numbers I get for replacing completions with semaphores. The individual files change very little in size:

   text    data     bss     dec     hex filename
   1280       0       0    1280     500 kernel/semaphore-before.o
   1656       0       0    1656     678 kernel/semaphore.o
  36816    8270     376   45462    b196 kernel/sched-before.o
  35938    8270     392   44600    ae38 kernel/sched.o
 369958  678538 4287224 5335720  516aa8 kernel/built-in-before.o
 371154  678538 4287288 5336980  516f94 kernel/built-in.o

7388295 1401040 4712200 13501535 ce045f vmlinux-before
7380903 1401040 4712000 13493943 cde6b7 vmlinux

So despite a net gain of 500 bytes when comparing semaphore.o and sched.o, kernel/built-in.o actually increases in size and vmlinux is even bigger. The only thing I can think of is that this is a lockdep thing.

Anyway, here's the cheesy patch, just for entertainment value. I think the discussion needs to be more around semantics and maintainability than code size or just how silly this patch is.

index d2961b6..9e7e718 100644
@@ -1,58 +1,30 @@
 #ifndef __LINUX_COMPLETION_H
 #define __LINUX_COMPLETION_H
 
-/*
- * (C) Copyright 2001 Linus Torvalds
- *
- * Atomic wait-for-completion handler data structures.
- * See kernel/sched.c for details.
- */
-
-#include <linux/wait.h>
-
-struct completion {
-	unsigned int done;
-	wait_queue_head_t wait;
-};
-
-#define COMPLETION_INITIALIZER(work) \
-	{ 0, __WAIT_QUEUE_HEAD_INITIALIZER((work).wait) }
-
-#define COMPLETION_INITIALIZER_ONSTACK(work) \
-	({ init_completion(&work); work; })
-
-#define DECLARE_COMPLETION(work) \
-	struct completion work = COMPLETION_INITIALIZER(work)
-
-/*
- * Lockdep needs to run a non-constant initializer for on-stack
- * completions - so we use the _ONSTACK() variant for those that
- * are on the kernel stack:
- */
-#ifdef CONFIG_LOCKDEP
-# define DECLARE_COMPLETION_ONSTACK(work) \
-	struct completion work = COMPLETION_INITIALIZER_ONSTACK(work)
-#else
-# define DECLARE_COMPLETION_ONSTACK(work) DECLARE_COMPLETION(work)
-#endif
-
-static inline void init_completion(struct completion *x)
+#include <linux/semaphore.h>
+
+#define completion semaphore
+#define COMPLETION_INITIALIZER(work)		__SEMAPHORE_INITIALIZER(work, 0)
+#define COMPLETION_INITIALIZER_ONSTACK(work)	__SEMAPHORE_INITIALIZER(work, 0)
+#define DECLARE_COMPLETION(work)	__DECLARE_SEMAPHORE_GENERIC(work, 0) 
+#define DECLARE_COMPLETION_ONSTACK(work) DECLARE_COMPLETION(work)
+#define init_completion(work)	init_MUTEX_LOCKED(work)
+
+#define wait_for_completion(work)		down(work)
+#define wait_for_completion_interruptible(work)	down_interruptible(work)
+#define wait_for_completion_killable(work)	down_killable(work)
+#define wait_for_completion_timeout(work, timeout) \
+			down_timeout(work, timeout)
+#define wait_for_completion_interruptible_timeout(work, timeout) \
+			down_interruptible_timeout(work, timeout)
+
+static inline void complete(struct semaphore *work)
 {
-	x->done = 0;
-	init_waitqueue_head(&x->wait);
+	up(work);
 }
 
-extern void wait_for_completion(struct completion *);
-extern int wait_for_completion_interruptible(struct completion *x);
-extern int wait_for_completion_killable(struct completion *x);
-extern unsigned long wait_for_completion_timeout(struct completion *x,
-						   unsigned long timeout);
-extern unsigned long wait_for_completion_interruptible_timeout(
-			struct completion *x, unsigned long timeout);
-
-extern void complete(struct completion *);
-extern void complete_all(struct completion *);
+#define complete_all(work)			up_all(work)
 
-#define INIT_COMPLETION(x)	((x).done = 0)
+#define INIT_COMPLETION(x)			init_MUTEX_LOCKED(x)
 
 #endif

index 2df44e7..e8634e5 100644
@@ -90,7 +90,7 @@ extern int console_printk[];
 #define minimum_console_loglevel (console_printk[2])
 #define default_console_loglevel (console_printk[3])
 
-struct completion;
+struct semaphore;
 struct pt_regs;
 struct user;
 

@@ -135,7 +135,7 @@ extern void oops_exit(void);
 extern int oops_may_print(void);
 NORET_TYPE void do_exit(long error_code)
 	ATTRIB_NORET;
-NORET_TYPE void complete_and_exit(struct completion *, long)
+NORET_TYPE void complete_and_exit(struct semaphore *, long)
 	ATTRIB_NORET;
 extern unsigned long simple_strtoul(const char *,char **,unsigned int);
 extern long simple_strtol(const char *,char **,unsigned int);

index 9b6c935..111c540 100644
@@ -8,7 +8,7 @@
 #include <asm/atomic.h>
 
 struct net;
-struct completion;
+struct semaphore;
 
 /*
  * The proc filesystem constants/structures

@@ -79,7 +79,7 @@ struct proc_dir_entry {
 	atomic_t count;		/* use count */
 	int pde_users;	/* number of callers into module in progress */
 	spinlock_t pde_unload_lock; /* proc_fops checks and pde_users bumps */
-	struct completion *pde_unload_completion;
+	struct semaphore *pde_unload_completion;
 };
 
 struct kcore_list {

index 9cae64b..470a4bc 100644
@@ -46,6 +46,9 @@ extern int __must_check down_interruptible(struct semaphore *sem);
 extern int __must_check down_killable(struct semaphore *sem);
 extern int __must_check down_trylock(struct semaphore *sem);
 extern int __must_check down_timeout(struct semaphore *sem, long jiffies);
+extern int __must_check down_interruptible_timeout(struct semaphore *sem,
+						   long jiffies);
 extern void up(struct semaphore *sem);
+extern void up_all(struct semaphore *sem);
 
 #endif /* __LINUX_SEMAPHORE_H */

index 571f01d..15d0ace 100644
@@ -30,7 +30,7 @@
 #include <linux/compiler.h>
 
 struct file;
-struct completion;
+struct semaphore;
 
 #define CTL_MAXNAME 10		/* how many path components do we allow in a
 				   call to sysctl?   In other words, what is

@@ -1063,7 +1063,7 @@ struct ctl_table_header
 	struct ctl_table *ctl_table;
 	struct list_head ctl_entry;
 	int used;
-	struct completion *unregistering;
+	struct semaphore *unregistering;
 	struct ctl_table *ctl_table_arg;
 	struct ctl_table_root *root;
 };

index 5c2942e..4e536c5 100644
@@ -36,6 +36,8 @@ 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 int __down_interruptible_timeout(struct semaphore *sem,
+							long jiffies);
 static noinline void __up(struct semaphore *sem);
 
 /**

@@ -167,6 +169,22 @@ int down_timeout(struct semaphore *sem, long jiffies)
 }
 EXPORT_SYMBOL(down_timeout);
 
+int down_interruptible_timeout(struct semaphore *sem, long jiffies)
+{
+	unsigned long flags;
+	int result = 0;
+
+	spin_lock_irqsave(&sem->lock, flags);
+	if (likely(sem->count > 0))
+		sem->count--;
+	else
+		result = __down_interruptible_timeout(sem, jiffies);
+	spin_unlock_irqrestore(&sem->lock, flags);
+
+	return result;
+}
+EXPORT_SYMBOL(down_interruptible_timeout);
+
 /**
  * up - release the semaphore
  * @sem: the semaphore to release

@@ -187,6 +205,18 @@ void up(struct semaphore *sem)
 }
 EXPORT_SYMBOL(up);
 
+void up_all(struct semaphore *sem)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&sem->lock, flags);
+	while (!list_empty(&sem->wait_list))
+		__up(sem);
+	sem->count = 1 << 30;
+	spin_unlock_irqrestore(&sem->lock, flags);
+}
+EXPORT_SYMBOL(up_all);
+
 /* Functions for the contended case */
 
 struct semaphore_waiter {

@@ -254,6 +284,12 @@ static noinline int __sched __down_timeout(struct semaphore *sem, long jiffies)
 	return __down_common(sem, TASK_UNINTERRUPTIBLE, jiffies);
 }
 
+static noinline int __sched __down_interruptible_timeout(struct semaphore *sem,
+								long jiffies)
+{
+	return __down_common(sem, TASK_INTERRUPTIBLE, jiffies);
+}
+
 static noinline void __sched __up(struct semaphore *sem)
 {
 	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,

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."

semaphores.. The problem with semaphores is the lack of a strict API, and loose usage. I've seen a lot of "creative" locking in the kernel, and if we allow that we're just asking for continued maintainability problems in the code that uses semaphores. At times I've spent hours trying to figure out what a semaphore is doing, or suppose to be doing. If we enforce strict usage of semaphores, then we'll basically reproduce mutex usage, and we have a generic mutex already..

Daniel

Hi Daniel,

Seconded!

Ask any software engineer, to describe what a semaphore is and how it behaves. You'll get the full spectrum of possible semaphore implementation options. Ask any advanced software engineer and he'll ask "What kind of semaphore?".

So let them die ASAP!

Same here. Or figuring out what kind of semphore behavior the developer expected.

Or have different API for using the same semaphores in different creative ways. It might be hard to implement lockdep for that :-)

No, I'm happy that Linux has so many more advanced concurrency concepts, that the pre-dinosaur locking mechanism (semaphore) is usually the last on your list.

Best Regards

Ingo Oeser

My take on it is the opposite: kill off semaphores and leave the completions around.

OK, so all three of you have got the wrong end of the stick.

My point is that the struct semaphore and the struct completion are essentially the same data structure, operated on in essentially the same way and having essentially the same purpose.

It would look bloody odd to write (code taken from megasas_mgmt_ioctl_fw() in drivers/scsi/megaraid/megaraid_sas.c):

        if (wait_for_completion_interruptible(&instance->ioctl_completion)) {
                error = -ERESTARTSYS;
                goto out_kfree_ioc;
        }
        error = megasas_mgmt_fw_ioctl(instance, user_ioc, ioc);
        complete(&instance->ioctl_sem);

What I'm trying to get a feeling for is whether people find it similarly odd to use semaphores where we currently use completions. We *used* to, but I don't find that a compelling reason.

Arnd contacted me off-list and made the very sensible suggestion of:

struct completion {
	struct semaphore sem;
}

That lets us eliminate the duplicate code since all the completion functions become very thin wrappers around semaphore operations.

I'll note that the semaphore code I hae queued for 2.6.26 is slightly more efficient than the current implementation of completions because completions use the generic waitqueue code and thus do an indirect function call per wakeup. Of course, there's no reason completions couldn't use the same technique as my semaphore code ... but then they would be identical to semaphores ;-)

So I'm going to redo my patch using Arnd's idea because it allows us to eliminate code without changing the API at all. We can continue the discussion about eliminating one or the other API, but my opinion is that eliminating either is a mistake. The choice of API indicates how the author thinks about the code, which is crucial for those reading the code.

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."

The above doesn't look all that odd to me. It may be that you've seen semaphores in that position in the past and just expect to see them.

I would just re-write completions keeping the name and API in tact, make them better and just leave semaphores alone..

Daniel

Which is exactly the point, semaphores are rarely the right tool for the job (I'm currently only aware of XFS that actually uses them as actual semaphores, and the driver model that uses it to get around lockdep - still need to come up with a good solution for that).

Even worse, semaphores actively harm the development of linux-rt and arguably linux kernel development as a whole by not being part of lockdep - so making a mistake will not be noticed until its too late.

Completions OTOH are not the typical exclusion primitive, they are more a synchronisation primitive - not unlike wait4(). Typically not things concerned about priority inversion.

I guess you haven't grepped the tree recently then. We have 11 places which call sema_init with a number other than 0 or 1 as the second argument:

./fs/xfs/linux-2.6/sema.h:#define initnsema(sp, val, name) sema_init(sp, val)
./drivers/net/mlx4/cmd.c: sema_init(&priv->cmd.event_sem, priv->cmd.max_cmds);
./drivers/char/viotape.c: sema_init(&reqSem, VIOTAPE_MAXREQ);
./drivers/infiniband/hw/mthca/mthca_cmd.c: sema_init(&dev->cmd.event_sem, dev->cmd.max_cmds);
./drivers/acpi/osl.c: sema_init(sem, initial_units);
./drivers/scsi/megaraid/megaraid_sas.c: sema_init(&instance->ioctl_sem, MEGASAS_INT_CMDS); ./drivers/scsi/megaraid/megaraid_mm.c: sema_init(&adapter->kioc_semaphore, lld_adp->max_kioc); ./drivers/video/omap/hwa742.c: sema_init(&hwa742.req_sema, i - IRQ_REQ_POOL_SIZE);
./drivers/video/omap/blizzard.c: sema_init(&blizzard.req_sema, i - IRQ_REQ_POOL_SIZE);
./drivers/usb/misc/usblcd.c: sema_init(&dev->limit_sem, USB_LCD_CONCURRENT_WRITES);
./drivers/usb/usb-skeleton.c: sema_init(&dev->limit_sem, WRITES_IN_FLIGHT);

It's nice to know that nobody is using __DECLARE_SEMAPHORE_GENERIC or __SEMAPHORE_INITIALIZER at this time. I'll delete those from my semaphore tree soon.

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."

Luckily those are mostly drivers, but yeah - I haven't actually grepped the tree I just know the few sem users I've ran into myself.

Still doesn't make it a good idea to have semaphores.

Just make sure you don't forget the history of completions... As Linus said long ago (http://lwn.net/2001/0802/a/lt-completions.php3):

In case anybody cares, the race was that Linux semaphores only protect the accesses _inside_ the semaphore, while the accesses by the semaphores themselves can "race" in the internal implementation. That helps make an efficient implementation, but it means that the race was:

            cpu #1                       cpu #2
  
            DECLARE_MUTEX_LOCKED(sem);
            ..
            down(&sem);                   up(&sem);
            return;
                                          wake_up(&sem.wait) /*BOOM*/

Yes, that text appears in the URL I provided in the mail that started this thread ;-)

The semaphore rewrite I did does not have this problem (it's less efficient than the hand-optimised assembler, but much more maintainable). You're supposed to be using mutexes if you want efficiency anyway.

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."

but semaphores will be _removed_, _completely_. Rewriting them in generic C code is just the first step towards that - it consolidates all the myriads of semaphore implementations that Linux has spread out.

your proposed change to change completions to semaphores is totally backwards and prolongs an API we want to get rid of. Did you miss this aspect of the mutex rewrite, of the semaphore-to-mutex, semaphore-to-completions and semaphore-to-rwsem conversions?

Ingo

I think you're dreaming. We have 11 places in the tree that currently demand to use a counting semaphore (with 'n' plausibly greater than 1). If we remove the facility, these places are going to invent their own weird locking schemes.

Yes -- because it wasn't raised at the time for semaphore-to-completions. It was raised for semaphore-to-mutex, of course. And I agree that we /want/ to be rid of counting semaphores, but I don't see a way to do it. I do believe tht we should be converting all the semaphore users to mutexes that we can (eg scx200_wdt.c), and converting semaphore users to completions where that makes sense (eg libusual.c). But there's still the other dozen places to support.

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."

no, i'm hoping for a simpler and thus more maintainable kernel.

which ones exactly are these places that demand the use of a counting semaphore? I cannot think of a single place where it's the best choice, let alone one where it's the only choice.

And if there's just 5 isolated places in the kernel that would need a different locking primitive then i say that it's probably not worth it. Locking is at the center of every data structure and the clarity and simplicity of basic data structure operations is paramount IMHO.

Semaphores are i think a relic from the days when people thought that parallelism can be best achieved via complexity and rafinery of locking primitives - regardless of how usable and debuggable those APIs end up to be. Today we can go extremely parallel with very simple and robust primitives.

i'm not worried about weird locking anymore - lockdep tends to expose them rather nicely and the lack of lockdep coverage for open-coded locking schemes tends to be a barrier as well. The past 2 years have shown that people want lockdep coverage for just about everything where it can be applied: workqueues, special locks, etc. (there's even questions about whether it could be extended to cover user-space locks.)

Ingo

Two of the places that use semaphores are drivers/infiniband/hw/mthca and drivers/net/mlx4 -- in both cases, the device firmware allows up to "N" outstanding firmware commands to be in flight, and the driver uses a semaphore to handle issuing firmware commands. That is, down() when we want to issue a command, and up() when the firmware responds that the command is complete.

What would you suggest as a better way to code this? This is an honest question -- there probably is a more elegant way to handle this situation and I really would like to learn about it.

Also, the argument that removing semaphores makes the kernel as a whole better does make sense to me; I wouldn't be opposed to basically open-coding semaphores in terms of wait_event() in the driver or something like that, but I wouldn't say that such an implementation is locally more readable or maintainable if we look only at the driver code.

- R.

Yeah, I would open code it. But this is indeed a sane usage of the counting semaphore because there is no priority inversion.

Maybe we need a "counter" primitive instead?

(the implementation can be pretty much the current semaphore one of course)

If you want to reach me at my work email, use [email protected]
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

I'm only too happy to rename semaphore.c to atomic_counter.c and do appropriate renames. Or maybe 'kcounter' would be more in vogue for a name ;-) I'd like a name that implies sleeping, but I'm not able to think of one right now.

Then semaphores and completions each become wrappers around counters and everybody's happy. Right?

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."

But when you open code that, how is it different from just having semaphores?

-Andi

Because we can then eventually get rid of semaphores, so those people cannot mistakenly use them. Its just too easy to create prio inversion with them around.

I'm not for open coding anything .. This "writes in flight" type code happens often enough we should have something that covers it.. completions come fairly close (since they're just like locked semaphores) only it's not easy to initialize them to allow multiple completes before the waiting starts..

Daniel

But then you end up with lots of likely subtly buggy open coded implementations. Also not good.

For me it sounds like you just want to rename semaphores to some other name that people don't use them for normal locking?

-Andi

Would it really be a good idea to give a synchronization concept that behaves exactly like a semaphore another name than "semaphore" ? The semaphore concept is well known and is taught in every computer science course.

Bart.

Are the ramifications wrt priority inversion taught? Is it made clear that its hard to validate because there is no clear resource owner?

Afaik, non of these subjects are touched upon in the CS-101 courses and that is exactly the problem. So you can say they are not well know, they are just widely misunderstood.

And yes, if there are more hand a very few such users it doesn't make sense to keep them open coded.

Regarding semaphores and priority inversion: I have never recommended the use of semaphores over mutexes, all I recommended is to keep the name "semaphore" for something that behaves like a semaphore. There might be better ways to discourage the use of the semaphore API, e.g. letting the compiler print a warning every time a semaphore function is called unless one or another #define has been enabled.

Regarding priority inheritance: does the above mean that you consider priority inheritance as an optimal solution for realizing real-time behavior in the kernel ? Are you aware of the fundamental problems associated with priority inheritance ? These issues are well explained in Victor Yodaiken's paper "Against priority inheritance". See also
http://www.linuxdevices.com/files/misc/yodaiken-july02.pdf .

Bart.

That sounds horrible; I really prefer targeted replacements like completions that make it clear what they're supposed to be used for.

Priority inheritance isn't ideal, but comming from a general purpose kernel that wasn't build from scratch to accomodate hard realtime its basically the only option.

Also things like lockdep are a real help to a lot of developers - loads of locking bugs never make it into the kernel because of it.

I agree that lockdep is a real help for kernel developers. But please keep in mind that locking order checking has its limitations. While locking order checking can detect certain very important classes of deadlocks, it can't detect all classes of possible deadlocks. Consider e.g. the example mentioned by Roland Dreier, where semaphores are used to count the number of elements in a queue. Deadlocks triggered by waiting for a certain semaphore value can't be detected by lockdep-style algorithms. And renaming semaphores into something else won't help.

Bart.

I agree. I'd rather _keep_ the completions, and get rid of the semaphores, so I think the whole fundamental patch here under discussion is broken.

We should do:
- continue replacing semaphores that are used purely for mutual exclusion with mutexes.
- probably add support for completions to do counting
- and then eventually just do the _reverse_ of what the current patch does, namely replace the existing counting semaphore usage with completions.

Hmm?

Linus

But that's just a semaphore, isn't it?

-Andi

Exactly. But the point here is:

- nobody should use semaphores anyway (use mutexes)
- making *more* code use semaphores is wrong
- completions have a different _mental_ model

IOW, this is not about implementation issues. It's about how you think about the operations.

We should _not_ implement completions as semaphores, simply because we want to get *rid* of semaphores some day.

So rather than this long and involved patch series that first makes semaphores generic, and then makes them be used as completions, I'd much rather just skip this whole pointless exercise entirely.

Why have "generic semaphores" at all, if we want to get rid of them?

Linus

i very much agree with the "get rid of semaphores" argument - the reason why i initially supported the "move to generic semaphores" step was because i saw it basically as the precursor to full removal: it is the removal of semaphores from all architectures - with a small generic compatibility wrapper to handle the remaining few uses of semaphores.

i got thoroughly surprised by the "increase the scope of semaphores" angle to the patchset though, and in hindsight i'd rather see neither of those generalizations and see semaphores die a slow but sure natural death than to see their prolongation :-/

perhaps the 'remove all semaphores from all architectures' privilege should be a final step kept for the lucky guy who manages to get rid of the last remaining semaphore use in the kernel? :)

Ingo

Hm. I thought you initially supported it because it deleted so much code. I don't want to go and add down_killable() to each architecture again, and you were pretty enthusiastic about adding down_killable().

I'm fully in favour of reducing the number of semaphore users, and eventually eliminating them. Arjan and I discussed a way to do that just now ... I'll write some code, see how it looks.

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."

... sorry, but i always thought of semaphores to be removed completely.

... the killable sleeps should and are already propagated everywhere - i never thought of them as a semaphore-only feature.

killable sleeps are probably the next best thing to true interruptability.

btw., has anyone thought about killable sync/fsync syscalls - would that surprise too many programs?

cool!

Ingo

killable stat and readdir would be even more important I would say.

When sync/fsync takes too long it's typically just a kernel bug of some sort (like that long running MM starvation issue that stalls writes on some kinds of background activity) that should be really just fixed.

But handling down network servers which hit stat/readdir etc. is a real situation not explained by a bug.

For example a standard situation that hits me regularly is that I save something in firefox on a different server and then later turn that machine off. Then next time I try to save something in firefox it first blocks forever in stat()ing that down directory.

-Andi

I think that's fixed now. Can you check with 2.6.25-rc1 or later? If it's unkillable, can you let me know the wchan for that process?

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."

For normal locks. But if you have N number of outstanding events you need to wait for the semaphore is the right primitive.

And it seems there is a not high but non trivial number of places in the kernel who have a legitimate need for this.

Ok so you just want to rename it.

Fine for me. I always found up() and down() unintuitive anyways (but it's admittedly better than "P" and "V" which some other systems use)

Because we still "counted completions" for some things and that's the same code?

Rather i suspect the real problem is not the name, but just not sure it gets abused. That is largely more a review problem and as far as I can figure out basically all the usual reviewers take care of that anyways. But renaming it also probably wouldn't hurt.

[IMHO I always thought we should have a maintained single "list of things for reviewers to watch out for" list somewhere]

-Andi

Right. Except if you were to just use completions instead (which could be trivially extended to do that).

MUCH more trivial than this complex series.

(You may think that the "Replace completions with semaphores" patch is not very complicated, but it *is* - it depends very intimately on the big patch-series that basically turns semaphores into what completions are now!)

In other words, what makes me not like this is hat we first turn semaphores into the generic code (which is largely what completions were:
just a special case of the generic semaphores!) and then turns completions into these things. That just doesn't make any sense to me!

Linus

complex? big? The big bits are dealing with renaming asm/semaphore.h to linux/semaphore.h, and I've dropped those out now. There's a couple of up-front patches which add inclusions of asm/semaphore.h to files which were missing it. Then I add the new semaphore implementation, delete the old ones, and add the down_timeout() and down_killable() functions.

Blame me for not realising that completions were semaphores under a different name.

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."

The origin of completions is literally the semaphore code - just simplified to use spinlocks and be usable as just a mutex. We used to use semaphores, and because of the subtle race with lockless semaphores I wrote that stupid completion code as a "generic semaphore with a very specific usage schenario" and called them "completions".

The completions _could_ have been extended/used as mutex semaphores, but the difference was really the mental model for them. That then limited the implementation of them: the functions working on completions are defined on purpose to be limited - it doesn't really have "up()" and "down()"
functions: "complete()" is really a up(), but "wait_for_completion()" is more like a "wait_until_I_could_do_a_trydown()" function.

Would it make sense to use completions for countable events too? Yeah. In fact, we have some things that really would like to do counting, both in the sense of "wait for <n> events to all complete" _and_ in the sense of "allow up to <n> events to be outstanding". Both of which could be done as a counting function (just make "complete" increment the counter, and then make "wait for <n> events" initialize it to negative, while "allow <n> outstanding events" would be a positive counter, and make "wait_for_completion()" basically be a "decrement and wait until it is zero".

IOW, completions() really follow the same patterns as semaphores, and it *does* make sense to just have one single code-base. But if we want to make semaphores go away, I think that it would be better to implement semaphores in terms of "extended completions" rather than the other way around. That way, we could one day really get rid of semaphores entirely.

Linus

Hmm, why not introduce a provide_slots(),
wait_for_slot() and free_slot() API?

provide_slots() := initialize a resource with N available slots wait_for_slot() := wait for a slot in countable resource to be free free_slot() := make a slot available

That would:
- fit the use case nicely
- could be optimized for countable resources
with upper limits
- allow to measure slot utilization
- ...
- is not called semaphore :-)

And isn't this the same problem (called scheduling) as:
- keeping N cpus busy
- keeping N (disk) spindles busy
- keeping N nic transmit queues busy
- ...

???

But maybe I oversimplify here :-)

Best Regards

Ingo Oeser

The kcounter API I'm working on has something in common with this. But it adds the more important feature:

- Is debuggable

I've also researched the current users of semaphores and completions and the API has to be extended a few different ways to take account of some reasonable usage patterns.

The basic idea is that you get back a cookie from the kcounter_claim() which you have to hand to the kcounter_release() function so it knows which one you released. It's similar to mutex debugging except that mutexes can use the thread_info pointer as an implicit cookie. Completions and semaphores have usage patterns where the resource is released from interrupt context.

I'm not finished yet, but this is the current API:

extern void kcounter_init(struct kcounter *kc, unsigned int count);

extern long __must_check kcounter_claim(struct kcounter *kc); extern long __must_check kcounter_claim_interruptible(struct kcounter *kc); extern long __must_check kcounter_claim_timeout(struct kcounter *kc,

                                                long jiffies);
extern long __must_check kcounter_claim_interruptible_timeout(
                                struct kcounter *kc, long jiffies);

extern long __must_check kcounter_try_claim(struct kcounter *kc); extern int __must_check kcounter_has_resources(struct kcounter *kc); extern void kcounter_release(struct kcounter *kc, long resource);

#ifdef CONFIG_DEBUG_KCOUNTER
extern void kcounter_add_resource(struct kcounter *kc); extern int __must_check kcounter_remove_resource(struct kcounter *kc); #else
#define kcounter_add_resource(kc) kcounter_release(kc, 0)
#define kcounter_remove_resource(kc) kcounter_claim(kc)
#endif
extern void kcounter_add_all_resources(struct kcounter *kc);

The kcounter_add_resource()/kcounter_remove_resource() API is for where we're actually adding new slots rather than releasing an already-acquired slot. Without debugging they're the same thing, but conceptually, they're a different thing.

It's not nearly as complex. Each of those uses domain-specific knowledge to optimise the solution.

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."

Am Mittwoch, 16. April 2008 18:16:52 schrieb Matthew Wilcox:

So in addition to the kcounter we need to save a token in a data structure? In fact, there must be a data structure that can house that token. So you can no longer live with a pointer just to a device descriptor, but every individual use of a resource must have an associated data structure?

Regards
Oliver

That's right. Do you have an example where this would be inconvenient? I couldn't find one. For example, with USB, you could place one in the struct urb.

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."

Am Mittwoch, 16. April 2008 18:34:14 schrieb Matthew Wilcox:

That's a data structure we really want to shrink. And furthermore, the needs of the use cases should shape the locking primitives, not the reverse.

Regards
Oliver

The cookies aren't checked by the kcounter implementation if CONFIG_DEBUG_KCOUNTER isn't set. So you can avoid storing them if it's *really* that important to shrink your data structures.

You'll still have to check the return value from the various kcounter_claim* APIs for errors, of course.

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."

I guess if anyone cared we could have something analogous to DECLARE_PCI_UNMAP_ADDR() et al that compiles to nothing if CONFIG_DEBUG_KCOUNTER isn't set. But I'm not sure it's worth it. Certainly for the mthca/mlx4 cases of semaphore use there's no problem holding onto a cookie.

- R.

yup. For kcounters there is a clear owner for each "slot". [This is the part that makes it debugable again)

Now for non-debug builds, the space taken for the token can be.. zero depending on how we define the types for it.

If you want to reach me at my work email, use [email protected]
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Hm. That might be worth changing the API for. Right now, I'm overloading the return value of kcounter_claim with an errno and a cookie. Maybe we should go for:

extern int __must_check kcounter_claim(struct kcounter *kc, kcounter_cookie_t *resource);

with the return value being 0 or errno and on success, kcounter_claim writes a cookie to 'resource'?

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."

or we return a cookie, and define some sort of "cookie_is_error()" thing

If you want to reach me at my work email, use [email protected]
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

I was considering that, but then we can't rely on __must_check to warn whether people are actually checking the errno or just storing the cookie somewhere.

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."

OK, here's the first version that even compiles. It's not completed -- a few functions need to be written, and I certainly haven't tried to convert anything to use it. Also, documentation would be good. But it's useful for people to take pot-shots at the API and suggest other things that are worth debugging checks.

One thing I want to add is a 'check if we can free this kcounter'. ie are there any outstanding resources claimed. And I'm not checking for a double-release of a resource yet (trivial to add, but I need to grab lunch).

commit 4496d41a540897039138a7d67dbef51f96dd0b09

Author: Matthew Wilcox <[email protected]>
Date:   Wed Apr 16 14:04:28 2008 -0400

kcounters

new file mode 100644
index 0000000..35f83ed
@@ -0,0 +1,58 @@
+#ifndef __LINUX_KCOUNTER_H
+#define __LINUX_KCOUNTER_H
+/*
+ * include/linux/kcounter.h
+ *
+ * Copyright (c) 2008 Intel Corporation
+ * Author: Matthew Wilcox <[email protected]>
+ *
+ * Distributed under the terms of the GNU GPL, version 2
+ *
+ * kcounters model a situation where you have a certain number of resources
+ * and tasks must sleep to acquire a resource if there are none available.
+ * New resources may be added or existing ones removed.
+ */
+
+#include <linux/list.h>
+#include <linux/spinlock.h>
+
+#ifdef CONFIG_DEBUG_KCOUNTER
+typedef struct { struct kcounter_owner *owner; } kcounter_cookie_t;
+#else
+typedef struct { } kcounter_cookie_t;
+#endif
+
+struct kcounter {
+	spinlock_t		lock;
+	unsigned int		count;
+	struct list_head	wait_list;
+#ifdef CONFIG_DEBUG_KCOUNTER
+	unsigned int		size;
+	struct kcounter_owner	*owners;
+#endif
+};
+
+extern void kcounter_init(struct kcounter *kc, unsigned int count);
+
+extern int __must_check kcounter_claim(struct kcounter *, kcounter_cookie_t *);
+extern int __must_check kcounter_claim_interruptible(struct kcounter *,
+				kcounter_cookie_t *);
+extern int __must_check kcounter_claim_timeout(struct kcounter *,
+				kcounter_cookie_t *, long jiffies);
+extern int __must_check kcounter_claim_interruptible_timeout(struct kcounter *,
+				kcounter_cookie_t *, long jiffies);
+extern int __must_check kcounter_try_claim(struct kcounter *kc,
+				kcounter_cookie_t *);
+extern int __must_check kcounter_has_free_resources(struct kcounter *kc);
+extern void kcounter_release(struct kcounter *, kcounter_cookie_t *);
+
+#ifdef CONFIG_DEBUG_KCOUNTER
+extern void kcounter_add_resource(struct kcounter *kc);
+extern int __must_check kcounter_remove_resource(struct kcounter *kc);
+#else
+#define kcounter_add_resource(kc)	kcounter_release(kc, NULL)
+#define kcounter_remove_resource(kc)	kcounter_claim(kc, NULL)
+#endif
+extern void kcounter_add_all_resources(struct kcounter *kc);
+
+#endif

index 0796c1a..926293d 100644
@@ -265,6 +265,13 @@ config DEBUG_MUTEXES
 	 This feature allows mutex semantics violations to be detected and
 	 reported.
 
+config DEBUG_KCOUNTER
+	bool "Kcounter debugging: basic checks"
+	depends on DEBUG_KERNEL
+	help
+	  Enabling this option allows the kernel to detect some basic
+	  misuses of the kcounter feature.
+
 config DEBUG_SEMAPHORE
 	bool "Semaphore debugging"
 	depends on DEBUG_KERNEL

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."

And it'll be far harder to even find the priority inversion problems in the open coded alternatives.

I know the semaphore-to-mutex rewrites were essential a.o. to make further merging of the real-time tree into the mainstream Linux kernel possible. But the semaphore concept is more powerful than the mutex
concept: semaphores can be used to let one thread wait for a state change reported by another thread. Should all state-change-waiting be implemented via wait_event*() functions ?

One of the strengths of the Linux kernel is that the barrier for new developers is low: in theory anyone familiar with the C programming language can start writing kernel drivers. Most people still learn kernel development via the third edition of the "Linux Device Drivers" book, and with some luck or some help, they come across an overview of the 2.6 kernel API changes (http://lwn.net/Articles/2.6-kernel-api/).
The LWN book is getting outdated after all the 2.6 kernel API changes, and the page with 2.6 kernel API changes was last updated six months ago. Where can a kernel developer find up to date information about kernel programming ?

Bart.

The failure to update the API changes page is just me not managing to get around to it. I'll do my best to take care of that in the next few days. Apologies for that.

Updating LDD (which isn't really "the LWN book" though it's hosted here) will take a little longer. I'd like to find a way to produce an LDD4 with quality at least as good as LDD3, but which doesn't fill the world with immediately-obsolete bricks of dead trees. Still working on it...

jon

Books should only be used to obtain the general picture, any details will be instantly-obsolete, esp at the pace Linux changes.

Most of the concepts from LDD3 are still valid, many of the details are dead wrong.

Can't we make LDD4 a high level book, explcitly mentioning how people should go about obtaining details? Like go ask on #kernelnewbies and the sorts.

The thing I always tell #kernelnewbies people is to look at a related driver (of course that kite doesn't always fly). Another good way to learn stuff is to just read the implementation.

A 'trick' that is often useful is to look in git to see how something was changed, provided you knew how to do it some time in the past.

What I remember from the first time I wrote a network driver is that reading the chapter in LDD3 about network drivers was the fastest way to get started. Learning how to write a network driver by reverse engineering existing drivers would have required much more time. My opinion is that mentioning all relevant details in a book makes sense.

Bart.

Thanks for bringing this back to attention -- I wasn't aware of the message you cited.

My opinion about the above race is that this race has nothing to do with the semaphore concept, but that the race is caused by the way in which the semaphore object is used. Using any object after it has been destroyed is asking for trouble.

Bart.

I think you need to re-read more carefully.

The users of the semaphore were doing nothing wrong. They were not using the object after it was destroyed.

The i386 implementation of the semaphore was calling wake_up() after setting the counter to allow cpu #0 to proceed. That was faster for the common case, but had this problem. completions were careful not to do that, and the semaphore implementation I wrote doesn't do that either.

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."

exactly. I first misread the subject line because i parsed it as "replace semaphores with completions" and i thought "cool", then did i realize that the patch does it the other way around. Converting completions to semaphores just makes no sense.

Besides all your arguments later in this thread about how problematic locking primitives semaphores are because they are so vague (which are all correct), there's also another aspect: completions are faster a bit in theory, because they know that they will schedule most of the time - while semaphores assume that they will _not_ schedule. (And that's exactly because the intent of the developer when using a completion is crystal clear.)

Ingo

In practice though, the current implementation is slower. Of course, that's fixable, and I strongly suspect that the current users of completions simply don't care about speed -- the normal use of completions is in startup and shutdown paths where a millisecond extra isn't going to be noticable.

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."

any URL to benchmarks?

completions and semaphores act in the sub-microsecond range, not in the milliseconds range.

Ingo

No -- just reading the code.

I've clearly misled both you and Jens, for which I apologise. My point was "even if they were a millisecond slower, nobody would notice", rather than "I've measured it and they're a millisecond slower" or even "from eyeballing it, I estimate they're about a millisecond slower".

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."

I'd be surprised if it was in that range, milisecond range would definetely mean that something was completely bused in that area :-). IOW, I'd be surprised if you can measure much of a difference, even in microbencmarks.

And performance does matter somewhat, it's not ONLY used in startup/shutdown scenarios. The block layer uses it for sync requests, for instance.

Jens Axboe