lkml.org 
[lkml]   [2005]   [Dec]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-12-18 05:10    [W:0.050 / U:14.596 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site