Implementing your own mutex with cmpxchgLast edited on Jun 28, 2012

The cmpxchg instruction takes the form of "cmpxchg destination source" where the destination is a memory location and the source is a register. Before using this instruction, you need to load a value in the EAX register. The instruction will first compare the value in EAX to the value in memory pointed by the destination operand. If both values are equal, the value of the source operand will be loaded in memory where the destination operand points to. Note that this compare and store operation is done atomically. If, on the other hand, the destination and EAX do not match, then the destination will be loaded into eax. At first, it might not be clear why this instruction would be usefull. But consider this:

l2: mov eax,[mutex]
    cmp eax,1
    je l2
    mov eax,1
l3: mov [mutex],eax

This is an unsafe way of creating a mutex. You loop until its value is zero and then set a 1 in it. But what if another thread or another CPU changed the value between l2 and l3?

If you need to store the value of a lock in memory (let's say at location 0x12345678) then before attempting to lock a section of code, you would read the lock to see if it is free. So you would read location 0x12345678 and test if this value is zero. If it isn't, then keep on reading memory until it reads as zero (because some other thread cleared it). After that, you would need to store a "1" in this location to take ownership of the lock. But what if another thread takes ownership between the time you read the value and the time you wrote it? The CMPXCHG instruction will write a "1" in there only if a "0" was in memory first. EAX would be equal to "0" because we would first spin until the memory value is "0". So after that, we tell the CPU: "EAX is zero now, so compare value at 0x12345678 with EAX (thus 0) and change it to 1 if it is equal. Otherwise, if the value at 0x12345678 is not equal to 0 anymore, then load this value into EAX and I will go back to spinning until I get a zero". Simple enough? Here is a sample code that illustrates this.

    mov edx,1
l2: mov eax,[mutex]
    cmp eax,1
    je l2                   ; spin until we see that eax == 0
    lock cmpxchg [mutex],edx; At this point, eax=0 for sure. Now if memory location still equal to
                            ; eax, then store edx in there.
                            ; otherwise, eax will be loaded with changed value of mutex (should be 1)
                            ; if not equal to zero, it means it was modified. If it was modified,
    jnz l2                  ; it means cmpxchg has loaded the value of the mutex in it.
                            ; and if the value of mutex was loaded, it means it wasn't equal to zero
                            ; by the definition of the CMPXCHG instruction.
                            ; zf will have been set in that case, so we can just make a conditional jump

Now, notice how we used "lock" before using cmpxchg? This is because we want the CPU to lock the bus before doing the operation so that no other CPU will interfere with that memory location.