Login/Register
Is x86 CMPXCHG atomic, if so why does it need LOCK?
Asked Answered
Solved concurrencyx86atomiclock-freecompare-and-swap
N

3

43

The Intel documentation says

This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically.

My question is

  1. Can CMPXCHG operate with memory address? From the document it seems not but can anyone confirm that only works with actual VALUE in registers, not memory address?

  2. If CMPXCHG isn't atomic and a high level language level CAS has to be implemented through LOCK CMPXCHG (with LOCK prefix), what's the purpose of introducing such an instruction at all?

(I am asking from a high level language perspective. I.e., if the lock-free algorithm has to be translated into a LOCK CMPXCHG on the x86 platform, then it's still prefixed with LOCK. That means the lock-free algorithms are not better than ones with a carefully written synchronized lock / mutex (on x86 at least). This also seems to make the naked CMPXCHG instruction pointless, as I guess the major point for introducing it, was to support such lock-free operations.)

Nagoya answered 8/1, 2015 at 10:20 Comment(6)
Obviously you can use a memory address, that's the whole point. The first operand is of type r/m, so there you go. And how could you prefix the instruction with lock if it didn't itself exist? – Agustinaah
@Agustinaah I don't quite understand what doesn't exist. You prefix with LOCK if you want the instruction to be atomic. So the CMPXCHG, without LOCK prefix, is atomic or not? – Nagoya
No, but in your question 2 you seem to ask why "cmpxchg without lock" exists, which is sort of odd, since the combination can't exist without the parts - if that is not what you meant then can you clarify? – Agustinaah
@Agustinaah I am asking from a high level language perspective. I.e. if the lock-free algorithms has to be translated into LOCK CMPXCHG on x86 platform, then it's still prefixed with LOCK. That means the lock-free algos are not better than a carefully written synchronized lock / murex (on x86 at least). This seems to make the CMPXCHG instruction pointless, as I guess the major point for introducing it, is to support such lock-free operations. – Nagoya
@Alex Suo: You are mixing up high-level locks with the lowlevel CPU feature that happened to be named LOCK. The high-level locks that lock-free algorithms try to avoid will have to put threads into wait state until the lock is available which is a costly operation and an entirely different thing than the CPU LOCK prefix feature which might hold other threads for a single instruction only. – Emrick
@Emrick Thanks. Can you post this as an answer so I can accept it :) – Nagoya
E
35

You are mixing up high-level locks with the low-level CPU feature that happened to be named LOCK.

The high-level locks that lock-free algorithms try to avoid can guard arbitrary code fragments whose execution may take arbitrary time and thus, these locks will have to put threads into wait state until the lock is available which is a costly operation, e.g. implies maintaining a queue of waiting threads.

This is an entirely different thing than the CPU LOCK prefix feature which guards a single instruction only and thus might hold other threads for the duration of that single instruction only. Since this is implemented by the CPU itself, it doesn’t require additional software efforts.

Therefore the challenge of developing lock-free algorithms is not the removal of synchronization entirely, it boils down to reduce the critical section of the code to a single atomic operation which will be provided by the CPU itself.

Emrick answered 9/1, 2015 at 8:41 Comment(8)
Then is it correct to say that CMPXCHG still holds the lock which is different from program level lock (i.e. JVM lock) – Shaniqua
@Rohit Sachan: you could say that it holds the BUS lock, but since this holds for every memory access, the only difference is that it is held for two memory accesses made by a single instruction and, more important, it’s just confusing when talking about “lock free programming”. In other words, you should always care about whether the discussion is about hardware or software architecture… – Emrick
I think the OP is partly asking "what's the point of cmpxchg without lock?". See my answer: Intel designed it that way because it's useful on a uniprocessor system. – Truitt
@Peter Cordes: the OP’s actual question became apparent in this comment. I only posted an answer after the OP acknowledged that this confusion between high level locks and the instruction prefix is the actual issue. Your addition still might be valuable for future readers finding this question after searching for “lock prefix”. – Emrick
Ah I see. No wonder this question didn't get much attention. I only noticed it in the related list while tidying up some of my old answers, and didn't wade through all the comments. – Truitt
What a lucid and technical explanation of the backend philosophy! – Mesoderm
Thank you Holger, your answer really helps me a lot ! – Graphomotor
Very interesting answer. But it still eludes me why they made the lock on XCHG implicit. Afterall there are more uses for an unlocked XCHG [mem],reg, certainly because the 16/32-bit x86 design isn't exactly renowned for its large register file. – Rutherfordium
T
59

It seems like part what you're really asking is:

Why isn't the lock prefix implicit for cmpxchg with a memory operand, like it is for xchg (since 386)?

The simple answer (that others have given) is simply that Intel designed it this way. But this leads to the question:

Why did Intel do that? Is there a use-case for cmpxchg without lock?

On a single-CPU system, cmpxchg is atomic with respect to other threads, or any other code running on the same CPU core. (But not to "system" observers like a memory-mapped I/O device, or a device doing DMA reads of normal memory, so lock cmpxchg was relevant even on uniprocessor CPU designs).

Context switches can only happen on interrupts, and interrupts happen before or after an instruction, not in the middle. Any code running on the same CPU will see the cmpxchg as either fully executed or not at all.

For example, the Linux kernel is normally compiled with SMP support, so it uses lock cmpxchg for atomic CAS. But when booted on a single-processor system, it will patch the lock prefix to a ds prefix everywhere that code was inlined, since plain cmpxchg without the lock runs much faster than lock cmpxchg. (The ds prefix has no effect except to take up the space; Linux uses a flat memory model so even in 32-bit code using (%ebp) or (%esp) addressing modes, it's still the same as a plain cmpxchg.) For more info, see this LWN article about Linux's "SMP alternatives" system. It can even patch back to lock prefixes before hot-plugging a second CPU.

Read more about atomicity of single instructions on uniprocessor systems in this answer, and in @supercat's answer + comments on Can num++ be atomic for int num. See my answer there for lots of details about how atomicity really works / is implemented for read-modify-write instructions like lock cmpxchg.

(This same reasoning also applies to cmpxchg8b / cmpxchg16b, and xadd, which are usually only used for synchonization / atomic ops, not to make single-threaded code run faster. Of course memory-destination instructions like add [mem], reg have obvious uses for non-shared data.)

Related:

Truitt answered 30/5, 2017 at 22:53 Comment(8)
" But when booted on a single-processor system, will patch the lock prefix to a nop everywhere that code was inlined, since nop cmpxchg runs much faster than lock cmpxchg." I'd assume you mean compiles in a single-processor system? As I am not aware of OS can patch such compiled instructions at run-time. – Nagoya
@AlexSuo: No, Linux's SMP alternatives system really does patch the kernel image on UP systems. (And BTW, if it was purely a compile-time thing, it would depend on whether you were building for a UP system, not on a UP system. I think if you leave out CONFIG_SMP, some locking / synchronization stuff can be left out entirely instead of being patched into NOPs at boot time. But these days probably not that much, especially with the standard CONFIG_PREEMPT that allows kernel code to be pre-empted.) – Truitt
@AlexSuo, IMHO this answer should be chosen as the accepted one. – Febrific
@raiks: I thought the same thing; Holger pointed out that the OP's real confusion was different from what they asked in the question itself, so that explains why Holger wrote that answer and the OP accepted it, even though the interesting part of the question (IMO) is what I answered. – Truitt
SMP probably means "Symmetrical multiprocessing" – Mullane
@Jeshan: That's (almost) correct, SMP stands for "Symmetric multiprocessing". I assumed everyone knew what the term stood for. Configuring Linux with CONFIG_SMP=y is a compile-time choice to include code necessary to take advantage of multiple CPU cores. Without it, there won't be any lock prefixes to patch away in the first place. – Truitt
The LOCK prefix is changed to a DS: segment override prefix, not a separate NOP instruction. This 2008 patch made the change, motivated by a correctness issue (but it's also more efficient): git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/… – Gallon
@amonakov: Thanks, that makes sense. I was thinking nop seemed like probably not the best way possible, but I didn't think of using a prefix and hadn't checked the actual code. – Truitt
E
35

You are mixing up high-level locks with the low-level CPU feature that happened to be named LOCK.

The high-level locks that lock-free algorithms try to avoid can guard arbitrary code fragments whose execution may take arbitrary time and thus, these locks will have to put threads into wait state until the lock is available which is a costly operation, e.g. implies maintaining a queue of waiting threads.

This is an entirely different thing than the CPU LOCK prefix feature which guards a single instruction only and thus might hold other threads for the duration of that single instruction only. Since this is implemented by the CPU itself, it doesn’t require additional software efforts.

Therefore the challenge of developing lock-free algorithms is not the removal of synchronization entirely, it boils down to reduce the critical section of the code to a single atomic operation which will be provided by the CPU itself.

Emrick answered 9/1, 2015 at 8:41 Comment(8)
Then is it correct to say that CMPXCHG still holds the lock which is different from program level lock (i.e. JVM lock) – Shaniqua
@Rohit Sachan: you could say that it holds the BUS lock, but since this holds for every memory access, the only difference is that it is held for two memory accesses made by a single instruction and, more important, it’s just confusing when talking about “lock free programming”. In other words, you should always care about whether the discussion is about hardware or software architecture… – Emrick
I think the OP is partly asking "what's the point of cmpxchg without lock?". See my answer: Intel designed it that way because it's useful on a uniprocessor system. – Truitt
@Peter Cordes: the OP’s actual question became apparent in this comment. I only posted an answer after the OP acknowledged that this confusion between high level locks and the instruction prefix is the actual issue. Your addition still might be valuable for future readers finding this question after searching for “lock prefix”. – Emrick
Ah I see. No wonder this question didn't get much attention. I only noticed it in the related list while tidying up some of my old answers, and didn't wade through all the comments. – Truitt
What a lucid and technical explanation of the backend philosophy! – Mesoderm
Thank you Holger, your answer really helps me a lot ! – Graphomotor
Very interesting answer. But it still eludes me why they made the lock on XCHG implicit. Afterall there are more uses for an unlocked XCHG [mem],reg, certainly because the 16/32-bit x86 design isn't exactly renowned for its large register file. – Rutherfordium
S
4

The LOCK prefix is to lock the memory access for the current command, so that other commands that are in the CPU pipeline can not access the memory at the same time. Using the LOCK prefix, the execution of the command won't be interrupted by another command in the CPU pipeline due to memory access of other commands that are executed at the same time. The INTEL manual says:

The LOCK prefix can be prepended only to the following in structions and only to those forms of the instructions where the destination operand is a memory operand: ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, and XCHG. If the LOCK prefix is used with one of these instructions and the source operand is a memory operand, an undefined opcode exception (#UD) may be generated.

Spraggins answered 8/1, 2015 at 16:13 Comment(3)
Which pipeline? – Fritzsche
Did you mean "can't access memory at this time?" – Truitt
Equally importantly, lock prevents accesses from other cores (and even DMA etc.) from appearing to happen between the load and store of an atomic RMW. Merely preventing other operations from this core from interleaving wouldn't be sufficient. – Truitt

© 2022 - 2024 — McMap. All rights reserved.