Re: [PATCH 1/12]: MUTEX: Implement mutexes

[Nicolas Pitre <nico@cam.org>]

On Sun, 18 Dec 2005, Linus Torvalds wrote:

> 
> 
> On Sun, 18 Dec 2005, Russell King wrote:
> >
> > On Sat, Dec 17, 2005 at 10:30:41PM -0800, Linus Torvalds wrote:
> > > An interrupt can never change the value without changing it back, except 
> > > for the old-fashioned use of "up()" as a completion (which I don't think 
> > > we do any more - we used to do it for IO completion a looong time ago).
> > 
> > I doubt you can guarantee that statement, or has the kernel source
> > been audited for this recently?
> 
> Well, _if_ it's a noticeable performance win, we should just do it. We 
> already know that people don't call "down()" in interrupts (it just 
> wouldn't work), we can instrument "up()" too.

And how would that prevent the kernel preemption issue?

> > Balancing the elimination of 4 instructions per semaphore operation,
> > totalling about 4 to 6 cycles, vs stability I'd go for stability
> > unless we can prove the above assertion via (eg) sparse.
> 
> I agree, if arm interrupt disables are fast. For example, on x86 (where 
> this isn't needed, because you can have an "interrupt-safe" decrement by 
> just having it as a single instruction, even if it isn't SMP-safe), 
> disabling and re-enabling interrupts is just one instruction each, but the 
> combination is usually something like 50+ cycles. So if this was an issue 
> on x86, we'd definitely care.
> 
> But if you don't think it's a big issue on ARM, it just doesn't matter.

Let's see.  The core of the uncontended down() on ARM looks like this:

	mrs     r0, cpsr
	orr     r1, r0, #128
	msr     cpsr_c, r1
	ldr     r1, [%0]
	subs     r1, r1, #1
	str     r1, [%0]
	msr     cpsr_c, r0
	blt	__contention

On a 624MHz ARMv5 processor I can execute this sequence approximately 
266100 times in 10 ms, which means approx 23 cycles.  The uncontended 
up() is the same except the sub is replaced by an add.

Removing the interrupt masking/unmasking reduces the above sequence to 4 
instructions using 6 cycles.  However it becomes completely unsafe wrt 
usage of up() from interrupt handlers, and it is completely preemption 
unsafe.

Now if we consider simple mutexes, the core of it becomes this on ARM:

	mov	r0, #1
	swp	r1, r0, [%0]
	cmp	r1, #0
	bne	__contention

The above takes 8 cycles.  It uses 4 instructions, and it could even be 
reduced to 3 when gcc's cse optimization can find a register that 
already contains the value 1 (then using only 7 cycles).  It is 
interrupt safe.  It is preemption safe.  It is small.

So if you think ARM is important, and if you consider the above a good 
enough improvement (I do), then that should talk in favor of simple 
mutexes for the kernel.  And it will have the nice side effect of making 
it easier on some other more obscur architectures.


Nicolas