Re: cmpxchg / atomic_cmpset_int emulation for userland (i386) ?

Luigi Rizzo wrote:
> On Thu, Apr 02, 2009 at 11:48:33AM +0300, Kostik Belousov wrote:
>> On Thu, Apr 02, 2009 at 09:06:05AM +0200, Luigi Rizzo wrote:
>>> Hi,
>>> I have some list manipulation algorithm that I would like to use
>>> that relies rather centrally on atomic_cmpset_int().
>>>
>>> This is an atomic instruction on 486+, but not available on 386
>>> and maybe other platforms. i386/atomic.h has a replacement
>>> but it uses "pushfl; cli; ... popfl;" so it cannot run in userland.
>>>
>>> I was wondering if there is a good emulation for that instruction
>>> on the i386 that is suitable for userland (other architectures
>>> we support have a CPU instruction that does it, or in the case of ARM,
>>> a usable emulation for userland).
>> FreeBSD cannot boot on anything < 486, i.e. cmpxchgl and xaddl may be
>> considered always supported by the CPU.
> 
> It was a slightly more generic question -- this stuff is for userland
> so while we can assume it works on modern FreeBSD versions, I would
> like to see what constraints it has on older versions of FreeBSD.
> Of course I can emulate the critical section with a pthread lock,
> but that would be the worst case option.

On i386's you can use XCHG instruction to implement locks and test&set 
in userland. Check this:

http://lists.canonical.org/pipermail/kragen-tol/1999-August/000457.html
http://www.acm.uiuc.edu/sigops/roll_your_own/i386/atomic.html

<quote>
The simplest is the XCHG instruction, which can be used to atomically
exchange two registers or a register and a memory location.  This makes
it possible to implement multiple exclusion; reserve a particular
location in RAM as a mutex, and initially set it to 1.  To acquire the
mutex, set a register to 0, and XCHG it with the location in RAM.  If
what you get back is a 1, then you have successfully acquired the
mutex; otherwise, someone else has it.  You can return the mutex simply
by setting the location to a nonzero value.

Intel's doc says, "When a memory operand is used with the XCHG
instruction, the processor's LOCK signal is automatically asserted.
This instruction is thus useful for implementing semaphores or similar
data structures for process synchronization."
</quote>


-Maxim