Re: [PATCH 1/19] MUTEX: Introduce simple mutex implementation

[Nikita Danilov]

Nick Piggin writes:
 > David Howells wrote:
 > > Nick Piggin <nickpiggin@xxxxxxxxxxxx> wrote:
 > > 
 > > 
 > >>> (2) Those that have CMPXCHG or equivalent: 68020, i486+, x86_64, ia64,
 > >>>sparc.
 > >>> (3) Those that have LL/SC or equivalent: mips (some), alpha, powerpc, arm6.
 > >>>
 > >>
 > >>cmpxchg is basically exactly equivalent to a store-conditional, so 2 and 3
 > >>are the same level.
 > > 
 > > 
 > > No, they're not. LL/SC is more flexible than CMPXCHG because under some
 > > circumstances, you can get away without doing the SC, and because sometimes
 > > you can do one LL/SC in lieu of two CMPXCHG's because LL/SC allows you to
 > > retrieve the value, consider it and then modify it if you want to. With
 > > CMPXCHG you have to anticipate, and so you're more likely to get it wrong.
 > > 
 > 
 > I don't think that is more flexible, just different. For example with
 > cmpxchg you may not have to do the explicit load if you anticipate an
 > unlocked mutex as the fastpath.
 > 
 > My point is that they are of semantically equal strength.

In the context of implementing mutex they most likely are. But not
generally: LL/SC fails when _any_ write was made into monitored
location, whereas CAS fails only when value stored in that location
changes. As a result, CAS has to deal with "ABA problem" when value
(e.g., first element in a queue) is changed from A to B (head of the
queue is removed) and then back to A (old head is inserted back).

Nikita.
-
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/