Re: [PATCH 11/12] Generic semaphore implementation

Re: [PATCH 11/12] Generic semaphore implementation

[Andrew Morton]

On Thu, 28 Feb 2008 17:39:54 -0700 Matthew Wilcox <matthew@wil.cx> wrote:

> On Thu, Feb 28, 2008 at 08:18:23AM +0100, Ingo Molnar wrote:
> > very nice work!
> > 
> > Acked-by: Ingo Molnar <mingo@elte.hu>
> 
> Thanks!
> 
> Stephen, I've put the semaphore patches into a git tree; can you add it
> to linux-next?
> 
> http://git.kernel.org/?p=linux/kernel/git/willy/misc.git;a=shortlog;h=semaphore
> 

err, we'd better tell the arch maintainers than we just deleted all their
sempahore code.

edited list:

 arch/alpha/kernel/semaphore.c                    |  224 --------------------
 arch/arm/kernel/semaphore.c                      |  221 --------------------
 arch/avr32/kernel/semaphore.c                    |  148 -------------
 arch/cris/kernel/semaphore.c                     |  129 -----------
 arch/frv/kernel/semaphore.c                      |  155 --------------
 arch/h8300/kernel/semaphore.c                    |  132 -----------
 arch/ia64/kernel/semaphore.c                     |  165 --------------
 arch/m32r/kernel/semaphore.c                     |  185 ----------------
 arch/m68k/kernel/semaphore.c                     |  132 -----------
 arch/m68k/lib/semaphore.S                        |   53 ----
 arch/m68knommu/kernel/semaphore.c                |  133 ------------
 arch/m68knommu/lib/semaphore.S                   |   66 -----
 arch/mips/kernel/semaphore.c                     |  168 ---------------
 arch/mn10300/kernel/semaphore.c                  |  149 -------------
 arch/parisc/kernel/semaphore.c                   |  102 ---------
 arch/powerpc/kernel/semaphore.c                  |  135 ------------
 arch/ppc/kernel/semaphore.c                      |  131 -----------
 arch/s390/kernel/semaphore.c                     |  108 ---------
 arch/sh/kernel/semaphore.c                       |  139 ------------
 arch/sparc/kernel/semaphore.c                    |  155 --------------
 arch/sparc64/kernel/semaphore.c                  |  254 -----------------------
 arch/v850/kernel/semaphore.c                     |  166 ---------------
 arch/xtensa/kernel/semaphore.c                   |  226 --------------------
 b/arch/x86/lib/semaphore_32.S                    |   83 -------
 b/include/asm-alpha/semaphore.h                  |  150 -------------
 b/include/asm-arm/semaphore.h                    |   99 --------
 b/include/asm-avr32/semaphore.h                  |  109 ---------
 b/include/asm-blackfin/semaphore.h               |  106 ---------
 b/include/asm-cris/semaphore.h                   |  134 ------------
 b/include/asm-frv/semaphore.h                    |  156 --------------
 b/include/asm-h8300/semaphore.h                  |  191 -----------------
 b/include/asm-ia64/semaphore.h                   |  100 ---------
 b/include/asm-m32r/semaphore.h                   |  145 -------------
 b/include/asm-m68k/semaphore.h                   |  164 --------------
 b/include/asm-m68knommu/semaphore.h              |  154 -------------
 b/include/asm-mips/semaphore.h                   |  109 ---------
 b/include/asm-mn10300/semaphore.h                |  170 ---------------
 b/include/asm-parisc/semaphore.h                 |  146 -------------
 b/include/asm-powerpc/semaphore.h                |   95 --------
 b/include/asm-s390/semaphore.h                   |  108 ---------
 b/include/asm-sh/semaphore.h                     |  116 ----------
 b/include/asm-sparc/semaphore.h                  |  193 -----------------
 b/include/asm-sparc64/semaphore.h                |   54 ----
 b/include/asm-v850/semaphore.h                   |   85 -------
 b/include/asm-xtensa/semaphore.h                 |  100 ---------
 b/include/linux/semaphore.h                      |   81 +++++++
 b/kernel/semaphore.c                             |  204 ++++++++++++++++++
 include/asm-arm/semaphore-helper.h               |   84 -------
 include/asm-blackfin/semaphore-helper.h          |   82 -------
 include/asm-cris/semaphore-helper.h              |   78 -------
 include/asm-h8300/semaphore-helper.h             |   85 -------
 include/asm-m68k/semaphore-helper.h              |  142 ------------
 include/asm-m68knommu/semaphore-helper.h         |   82 -------
 include/asm-parisc/semaphore-helper.h            |   89 --------
 include/asm-sh/semaphore-helper.h                |   89 --------
 include/asm-x86/semaphore_32.h                   |  175 ---------------
 include/asm-x86/semaphore_64.h                   |  180 ----------------
 lib/semaphore-sleepers.c                         |  176 ---------------

yummy summary:

 254 files changed, 386 insertions(+), 7827 deletions(-)

The only major conflict is with avr32 which seems to have just done a major
revamp of that architecture's semaphore implementation.  Oh well.

There are a couple of small #include rejects here and there, nothing at all
major.


Yes, let's get this into linux-next if poss please.  If mainline later
breaks for some architecture, well, we did our best..

Re: [PATCH 11/12] Generic semaphore implementation

[Andrew Morton]

On Thu, 28 Feb 2008 01:34:00 -0500 Matthew Wilcox <matthew@wil.cx> wrote:

> Semaphores are no longer performance-critical, so a generic C
> implementation is better for maintainability, debuggability and
> extensibility.
> 

This make all architectures use the lib/semaphore-sleepers.c
implementation.  The major difference is that down() and up() will now
unconditionally do a spin_lock_irq[save]() on the not-contended fastpath,
whereas the hand-optimised arch-specific implementations would avoid that.

Yes, hopefully not many sempahores are used on fastpaths any more, and a
suitable fix for any which _are_ so used is usually convert-to-mutex.

And spin_lock_irqsave() probably isn't hugely slower than an atomic-dec
anyway.



A few nits, most or all of which pertain to the old code:

> --- /dev/null
> +++ b/kernel/semaphore.c
> @@ -0,0 +1,204 @@
> +/*
> + * Copyright (c) 2008 Intel Corporation
> + * Author: Matthew Wilcox <willy@linux.intel.com>
> + *
> + * Distributed under the terms of the GNU GPL, version 2
> + */
> +
> +#include <linux/compiler.h>
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <linux/sched.h>
> +#include <linux/semaphore.h>
> +#include <linux/spinlock.h>
> +
> +/*
> + * Some notes on the implementation:
> + *
> + * 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 order to avoid a third task
> + * coming in and stealing the second task's wakeup, we leave the ->count
> + * negative.  If we have a more complex situation, the ->count may become
> + * zero or negative (eg a semaphore with count = 2, three tasks attempt to
> + * acquire it, one sleeps, two finish and call up(), the second task to call
> + * up() notices that the list is empty and just increments count).
> + */
> +
> +static void noinline __down(struct semaphore *sem);
> +static int noinline __down_interruptible(struct semaphore *sem);
> +static int noinline __down_killable(struct semaphore *sem);
> +static void noinline __up(struct semaphore *sem);

We conventionally do `static inline void' rather than `static void inline',
so I guess we should do `static noinline void' too.

> +int down_interruptible(struct semaphore *sem)
> +{
> +	int result = 0;
> +	might_sleep();
> +	spin_lock_irq(&sem->lock);
> +	if (unlikely(sem->count-- <= 0))
> +		result = __down_interruptible(sem);
> +	spin_unlock_irq(&sem->lock);
> +	return result;
> +}
> +EXPORT_SYMBOL(down_interruptible);

Some functions leave no blank line between end-of-locals and start-of-code...

> +int down_killable(struct semaphore *sem)
> +{
> +	int result = 0;
> +	might_sleep();
> +	spin_lock_irq(&sem->lock);
> +	if (unlikely(sem->count-- <= 0))
> +		result = __down_killable(sem);
> +	spin_unlock_irq(&sem->lock);
> +	return result;
> +}
> +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
> + * been acquired successfully and 1 if it is contended.
> + *
> + * NOTE: This return value is inverted from both spin_trylock and
> + * mutex_trylock!  Be careful about this when converting code.
> + *
> + * Unlike mutex_trylock, this function can be used from interrupt context,
> + * and the semaphore can be released by any task or interrupt.
> + */
> +int down_trylock(struct semaphore *sem)
> +{
> +	unsigned long flags;
> +	int count;
> +
> +	spin_lock_irqsave(&sem->lock, flags);
> +	count = sem->count - 1;
> +	if (likely(count >= 0))
> +		sem->count = count;
> +	spin_unlock_irqrestore(&sem->lock, flags);
> +	return (count < 0);
> +}
> +EXPORT_SYMBOL(down_trylock);

whereas some others do leave a blank line.

I think the 51% consensus is that the latter form is preferred.

> +void up(struct semaphore *sem)
> +{
> +	unsigned long flags;
> +
> +	spin_lock_irqsave(&sem->lock, flags);
> +	if (likely(sem->count >= 0))
> +		sem->count++;
> +	else
> +		__up(sem);
> +	spin_unlock_irqrestore(&sem->lock, flags);
> +}
> +EXPORT_SYMBOL(up);
> +
> +/* Functions for the contended case */
> +
> +struct semaphore_waiter {
> +	struct list_head list;
> +	struct task_struct *task;
> +	int up;
> +};
> +
> +/*
> + * Wake up a process waiting on a semaphore.  We need to call this from both
> + * __up and __down_common as it's possible to race a task into the semaphore
> + * if it comes in at just the right time between two tasks calling up() and
> + * a third task waking up.  This function assumes the wait_list is already
> + * checked for being non-empty.
> + */
> +static void noinline __sched __up_down_common(struct semaphore *sem)
> +{
> +	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
> +						struct semaphore_waiter, list);
> +	list_del(&waiter->list);
> +	waiter->up = 1;

hm.  Do we need a barrier here?

> +	wake_up_process(waiter->task);
> +}
> +
> +/*
> + * Because this function is inlined, the 'state' parameter will be constant,
> + * and thus optimised away by the compiler.
> + */
> +static inline int __sched __down_common(struct semaphore *sem, long state)
> +{
> +	int result = 0;
> +	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 (unlikely((state == TASK_INTERRUPTIBLE &&
> +					signal_pending(task)) ||
> +			     (state == TASK_KILLABLE &&
> +					fatal_signal_pending(task))))
> +			goto interrupted;
> +		__set_task_state(task, state);
> +		spin_unlock_irq(&sem->lock);
> +		schedule();
> +		spin_lock_irq(&sem->lock);
> +		if (waiter.up)
> +			goto woken;
> +	}
> +
> + interrupted:
> +	list_del(&waiter.list);
> +	result = -EINTR;
> + woken:
> +	/*
> +	 * Account for the process which woke us up.  For the case where
> +	 * we're interrupted, we need to increment the count on our own
> +	 * behalf.  I don't believe we can hit the case where the
> +	 * sem->count hits zero, *and* there's a second task sleeping,
> +	 * but it doesn't hurt, that's not a commonly exercised path and
> +	 * it's not a performance path either.
> +	 */
> +	if (unlikely((++sem->count >= 0) && !list_empty(&sem->wait_list)))
> +		__up_down_common(sem);
> +	return result;
> +}

That is one huuuuuuuge inline.  Are we sure it's justified?

> +static void noinline __sched __down(struct semaphore *sem)
> +{
> +	__down_common(sem, TASK_UNINTERRUPTIBLE);
> +}
> +
> +static int noinline __sched __down_interruptible(struct semaphore *sem)
> +{
> +	return __down_common(sem, TASK_INTERRUPTIBLE);
> +}
> +
> +static int noinline __sched __down_killable(struct semaphore *sem)
> +{
> +	return __down_common(sem, TASK_KILLABLE);
> +}
> +
> +static void noinline __sched __up(struct semaphore *sem)
> +{
> +	if (unlikely(list_empty(&sem->wait_list)))
> +		sem->count++;
> +	else
> +		__up_down_common(sem);
> +}
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 11/12] Generic semaphore implementation

[Andrew Morton]

On Fri, 29 Feb 2008 13:00:19 +1100 Stephen Rothwell <sfr@canb.auug.org.au> wrote:

> On Thu, 28 Feb 2008 17:39:54 -0700 Matthew Wilcox <matthew@wil.cx> wrote:
> >
> > Stephen, I've put the semaphore patches into a git tree; can you add it
> > to linux-next?
> > 
> > http://git.kernel.org/?p=linux/kernel/git/willy/misc.git;a=shortlog;h=semaphore
> 
> I have put this in for toady's build (but using the git URL).  This tree
> is in the "too many conflicts and its out until fixed" category ...

A shame.

Most of the conflicts will be due to all the

-#include <asm/semaphore.h>
+#include <linux/semaphore.h>

but they're all optional anyway, because include/asm-*/semaphore.h is

#include <linux/semaphore.h>

so either a) you just ignore all those conflicts or b) we ask Willy to
remove all that stuff and we can trickle it in via subsystems later.

Re: [PATCH 11/12] Generic semaphore implementation

[Matthew Wilcox]

On Thu, Feb 28, 2008 at 05:43:49PM -0800, Andrew Morton wrote:
> err, we'd better tell the arch maintainers than we just deleted all their
> sempahore code.
     ^^  I'm so glad it's not just me who makes that typo.  I actually
grepped for it before sending the patches out.

I did already send it to linux-arch back in January or so.  But a
reminder won't hurt.

> yummy summary:
> 
>  254 files changed, 386 insertions(+), 7827 deletions(-)

Yeah, that's quite attractive ;-)

> Yes, let's get this into linux-next if poss please.  If mainline later
> breaks for some architecture, well, we did our best..

It _should_ only be build breakage.  I guess we'll see.

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

Re: [PATCH 11/12] Generic semaphore implementation

[Matthew Wilcox]

On Thu, Feb 28, 2008 at 06:10:54PM -0800, Andrew Morton wrote:
> Most of the conflicts will be due to all the
> 
> -#include <asm/semaphore.h>
> +#include <linux/semaphore.h>
> 
> but they're all optional anyway, because include/asm-*/semaphore.h is
> 
> #include <linux/semaphore.h>
> 
> so either a) you just ignore all those conflicts or b) we ask Willy to
> remove all that stuff and we can trickle it in via subsystems later.

Yeah, we can trickle that in later.  Fine by me.

I think rather more conflict is likely with the 105 files where I just
removed the asm/semaphore.h include.  I'd like it if we could get Linus
to merge those at this stage.  Since it passes an x86 allmodconfig
build, I'd like to think the breakage would be minimal.

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

Re: [PATCH 11/12] Generic semaphore implementation

[Matthew Wilcox]

On Thu, Feb 28, 2008 at 05:57:29PM -0800, Andrew Morton wrote:
> This make all architectures use the lib/semaphore-sleepers.c
> implementation.

It's slightly different -- I didn't use any existing semaphore
implementation for inspiration (though I did write the parisc one,
so I couldn't help but be influenced).  I was much more influenced
by mutex.c.  After I'd posted it the first time, dhowells pointed out
it was essentially the same as FRV's implementation.

> The major difference is that down() and up() will now
> unconditionally do a spin_lock_irq[save]() on the not-contended fastpath,
> whereas the hand-optimised arch-specific implementations would avoid that.
> 
> Yes, hopefully not many sempahores are used on fastpaths any more, and a
> suitable fix for any which _are_ so used is usually convert-to-mutex.
> 
> And spin_lock_irqsave() probably isn't hugely slower than an atomic-dec
> anyway.

As always, the major cost is getting the cacheline exclusive on this
CPU.  I'd be surprised if you can measure the difference.

> A few nits, most or all of which pertain to the old code:

Thanks for the review.

> > +static void noinline __down(struct semaphore *sem);
> > +static int noinline __down_interruptible(struct semaphore *sem);
> > +static int noinline __down_killable(struct semaphore *sem);
> > +static void noinline __up(struct semaphore *sem);
> 
> We conventionally do `static inline void' rather than `static void inline',
> so I guess we should do `static noinline void' too.

I can change that.  I'll modify the git tree, unless anyone has any
complaints.  We should fix mutex.c at the same time:

static void noinline __sched
__mutex_lock_slowpath(atomic_t *lock_count);

> > +int down_interruptible(struct semaphore *sem)
> > +{
> > +	int result = 0;
> > +	might_sleep();
> > +	spin_lock_irq(&sem->lock);
> > +	if (unlikely(sem->count-- <= 0))
> > +		result = __down_interruptible(sem);
> > +	spin_unlock_irq(&sem->lock);
> > +	return result;
> > +}
> > +EXPORT_SYMBOL(down_interruptible);
> 
> Some functions leave no blank line between end-of-locals and start-of-code...

It's not something I feel strongly about ;-)

> whereas some others do leave a blank line.
> 
> I think the 51% consensus is that the latter form is preferred.

Fine.

> > +static void noinline __sched __up_down_common(struct semaphore *sem)
> > +{
> > +	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
> > +						struct semaphore_waiter, list);
> > +	list_del(&waiter->list);
> > +	waiter->up = 1;
> 
> hm.  Do we need a barrier here?

__up_down_common is always called while holding the spinlock.  The
spinlock is acquired by the waiter before it checks the flag.  If
there's a race here, I question the value of spinlocks at all.

> > +	wake_up_process(waiter->task);


> > + * Because this function is inlined, the 'state' parameter will be constant,
> > + * and thus optimised away by the compiler.
> > + */

> That is one huuuuuuuge inline.  Are we sure it's justified?

It's a mirror of __mutex_lock_common ... I don't believe it's justified
in one case and not the other.

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

Re: [PATCH 11/12] Generic semaphore implementation

[Stephen Rothwell]

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

On Thu, 28 Feb 2008 18:10:54 -0800 Andrew Morton <akpm@linux-foundation.org> wrote:
>
> > I have put this in for toady's build (but using the git URL).  This tree
> > is in the "too many conflicts and its out until fixed" category ...
> 
> A shame.
> 
> Most of the conflicts will be due to all the
> 
> -#include <asm/semaphore.h>
> +#include <linux/semaphore.h>
> 
> but they're all optional anyway, because include/asm-*/semaphore.h is
> 
> #include <linux/semaphore.h>
> 
> so either a) you just ignore all those conflicts or b) we ask Willy to
> remove all that stuff and we can trickle it in via subsystems later.

My conflict tolerance is already rising.  i.e. I will fix up such trivial
to fix conflicts.  I am more concerned with complexity of conflicts than
mere number (so "too many conflicts" should be read as "too many
conflicts that I can't figure out in a shortish period of time").

If it gets too bad, it falls into Linus' "the person who changes the APIs
bears the pain" basket. :-)

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 11/12] Generic semaphore implementation

[Haavard Skinnemoen]

On Thu, 28 Feb 2008 17:43:49 -0800
Andrew Morton <akpm@linux-foundation.org> wrote:

> The only major conflict is with avr32 which seems to have just done a major
> revamp of that architecture's semaphore implementation.  Oh well.

Not anymore. It was a pure spaces-to-tabs conversion, so I dropped it.

Haavard

Re: [PATCH 11/12] Generic semaphore implementation

[Ingo Molnar]

* Andrew Morton <akpm@linux-foundation.org> wrote:

> yummy summary:
> 
>  254 files changed, 386 insertions(+), 7827 deletions(-)
> 
> The only major conflict is with avr32 which seems to have just done a 
> major revamp of that architecture's semaphore implementation.  Oh 
> well.
> 
> There are a couple of small #include rejects here and there, nothing 
> at all major.
> 
> Yes, let's get this into linux-next if poss please.  If mainline later 
> breaks for some architecture, well, we did our best..

a better approach would be to send the core bits to Linus right now - as 
long as it's Kconfig isolated and inactive code - hence it is eligible 
as a cleanup.

That means arch maintainers could start applying the patches at their 
own pace, starting right now, in their own work-flow and test-flow. 
(obviously, the first such patches would hit mainline starting in the 
next merge window)

And all the linux-next integration trouble down the line is avoided, and 
each architecture can do a concentrated effort of: 'get rid of semaphore 
code'.

Please!

	Ingo