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

On Sat, 17 Dec 2005, Linus Torvalds wrote:

> On Sat, 17 Dec 2005, Nicolas Pitre wrote:
> >
> > Well, if you really want to be honest, you have to consider that the
> > ldrex/strex instructions are available only on ARM architecture level 6
> > and above, or in other words with only about 1% of all ARM deployments
> > out there. The other 99% of actual ARM processors in the field only
> > have the atomic swap (swp) instruction which is insufficient for
> > implementing a counting semaphore (we therefore have to disable
> > interrupts, do the semaphore update and enable interrupts again which is
> > much slower than a swp-based mutex).
>
> Ehh.. Have you seen any SMP arm machines with the old ones?

No. I never saw any SMP on ARM yet. About only RMK did.

> As far as I can tell from the Linux arm assembly (which I admittedly don't
> read very well at all), the non-ARMv6 semaphore code just disables
> interrupts and does the semaphore without any atomic instructions at all.

Exact, and that's because on pre-ARMv6 you have UP only, and the only
atomic instruction on pre-ARMv6 is the swp instruction which doesn't cut
it for semaphores.

> Which is fine for UP (in fact, I'm not even convinced you need to disable
> interrupts, since any interrupts - even if they do a "trylock+up" - should
> always leave the counter in the same state it was before).

I don't think I follow you here. The down() implementation goes like
this:

1) disable interrupts
2) load semaphore count into register
3) decrement register value (remember if it goes negative)
4) store register value to semaphore count location
5) enable interrupts
6) if the count went negative go to sleep

The up() goes like this:

1) disable interrupts
2) load semaphore count into register
3) increment register value (remember if it remains < 1)
4) store register value to semaphore count location
5) enable interrupts
6) if the sem count is still < 1 then wake up someone

Now if you don't disable interrupts then nothing prevents an interrupt
handler, or another thread if kernel preemption is allowed, to come
along right between (2) and (4) to call up() or down() which will
make the sem count inconsistent as soon as the interrupted down() or
up() is resumed.

> So afaik, Linux simply doesn't support pre-ARMv6 in SMP configurations,
> and never has (and I'd assume never will).

Indeed.

> Or am I missing something?

I understand this thread is about simple mutex (locked/unlocked) vs full
counting semaphores. And I'm presuming that we still care about best
performances with pre-ARMv6 support, maybe even more than ARMv6 and
above given the current deployment figures using Linux.

In that case, a simple mutex_lock implementation on pre-ARMv6 would look
like this:

__lock:
mov r1, #1 @ 1 = lock flag
swp r2, r1, [r0] @ lock the mutex, get current state
cmp r2, #0 @ was it unlocked?
beq __continue @ if so we're done
mov r1, #2 @ 2 = contended lock
swp r2, r1, [r0] @ upgrade the lock to contended
cmp r2, #0 @ was it unlocked in the mean time?
beq __continue @ if so we just acquired the lock
bl __sleep @ go to sleep
b __lock
__continue:

Here you can even have the 4 first instructions inline for the fast
uncontended case and the rest out of line, making it much smaller than
the counting semaphore implementation with the same inline property.

And for completeness, here's the mutex_unlock:

__unlock:
mov r1, #0 @ 0 = unlocked
swp r2, r1, [r0] @ unlock mutex, get current state
cmp r2, #2 @ was it contended?
bleq __wake @ if so call wake_up

And the mutex_trylock is trivial as well.

That's it. 4 inline instructions for locking, 4 inline instructions for
unlocking, no disabling/enabling of interrupts needed any more.


Nicolas
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: [PATCH 1/12]: MUTEX: Implement mutexes
    ... > ldrex/strex instructions are available only on ARM architecture level 6 ... do the semaphore update and enable interrupts again which is ... basically never used in SMP configs, but just with two independent CPU's ... interrupts and does the semaphore without any atomic instructions at all. ...
    (Linux-Kernel)
  • Re: [RFC] unify semaphore implementations
    ... > semaphore implementation across all architectures (not posted as ... I set about testing this implementation against the ARM ... Instructions: 23, 23 in the common execution path. ... kernel series on ARM for the same functionality, ...
    (Linux-Kernel)
  • Re: semtake function in ISR
    ... ISR, but upon closer inspection, it is being called from task-level. ... including whether interrupts are enabled or disabled. ... TaskA gets the semaphore and continues chugging along, ... If you are a newbie to VxWorks, here are the reasons why semTake ...
    (comp.os.vxworks)
  • Re: Hi
    ... For history of older ARM architectures, the Wikipedia got a nice table ... ARM7 is based on arch v4, with ARM instructions only. ... ARM1136 come with a new architecture, which include new instructions, ... But Cortex-M3 doesn't not support ARM ...
    (comp.sys.arm)
  • Re: [BUG] long freezes on thinkpad t60
    ... task_rq_lock- that is done with interrupts disabled. ... i think the only thing that eventually got Miklos' laptop out of the ... the second column is the number of times the profiling interrupt has hit ... Note the many zero entries - this means that for instructions that are ...
    (Linux-Kernel)