The SMP course measured what a lost update costs and told you to use lock. This concept is the exhaustive answer to the question that follows immediately and is almost never asked: which instructions can you put it on, and what happens if you leave it off? The answer is not “the ones that write memory”, and it is emphatically not “all the read-modify-writes”.
Forty-two arms, three instruments, two threads pinned to two cores with a barrier and the shared word reset before every single arm. And two results in the set are the course:
lock inc is exact. The draft for this course said it was not. It is, and the reason it is the only read-modify-write with that property is a single sentence in the instruction's description: INC does not disturb the CARRY flag, so it needs no special case in the silicon.or $0, and $0xffffffff, xor $0 and sub $0 with no prefix all lose updates. These are the arms that look like no-ops, and a no-op is the perfect camouflage: there is no visible effect of the lost update because there was no visible effect to begin with.The counter is the obvious instrument — two threads increment a shared word N times each, and a total of 2N means nothing was lost. Here is the whole table, and every row's target is a different number for a reason that is worth reading before the verdicts:
$ ./vecdump | sed -n '/^ CNT | instruction/,/bt \$0/p'
CNT | add $1, no LOCK | 83 00 01 | 120000 | 78548 | NOT ATOMIC
CNT | add $1, LOCK | f0 83 00 01 | 120000 | 120000 | ATOMIC
CNT | inc, no LOCK | ff 00 | 120000 | 63066 | NOT ATOMIC
CNT | inc, LOCK | f0 ff 00 | 120000 | 120000 | ATOMIC
CNT | dec, no LOCK | ff 08 | 4294847296 | 4294900952 | NOT ATOMIC
CNT | dec, LOCK | f0 ff 08 | 4294847296 | 4294847296 | ATOMIC
CNT | xadd $1, NO PREFIX | 0f c1 01 | 120000 | 77812 | NOT ATOMIC
CNT | xadd $1, LOCK | f0 0f c1 01 | 120000 | 120000 | ATOMIC
CNT | cmpxchg loop, NO PREFIX | 0f b1 01 | 120000 | 62692 | NOT ATOMIC
CNT | cmpxchg loop, LOCK | f0 0f b1 01 | 120000 | 120000 | ATOMIC
CNT | cmpxchg8b, NO PREFIX | 0f c7 01 | 120000 | 63790 | NOT ATOMIC
CNT | cmpxchg16b, NO PREFIX | 48 0f c7 01 | 120000 | 62430 | NOT ATOMIC
CNT | cmpxchg8b, LOCK | f0 0f c7 01 | 120000 | 120000 | ATOMIC
CNT | cmpxchg16b, LOCK | f0 48 0f c7 01 | 120000 | 120000 | ATOMIC
CNT | load+add+XCHG | mov;add;87 | 120000 | 80634 | NOT ATOMIC
CNT | load+add+LOCK XCHG | mov;add;f0 87 | 120000 | 83096 | NOT ATOMIC
Read the dec rows first, because they carry the concept's sharpest methodological point. The word starts at zero and each thread decrements 60000 times, so the exact total is 232 − 2N = 4294847296, not 2N. A table that expected 2N would report a perfectly atomic lock dec as non-atomic — and did, for one run, before the expectation was corrected. The expectation is the thing that has to be right before a measurement can be called a pass, and there are three of them here, not one: an arm that moves the value up ends at 2N, one that moves it down ends at 232−2N, and one that toggles a bit ends at 0 because the two threads toggle an even number of times between them. Getting any of the three wrong calls a working arm broken.
And the last two rows are the other half of the story, so do not skip them. mov;add;87 is a load, an add and a bare XCHG with a memory operand — and it loses updates. Adding lock to that XCHGdoes not help, and the reason is the shape of the program rather than the instruction: by the time the XCHG runs, the damage is in the mov and the add before it. XCHG is genuinely atomic with a memory operand, and that fact does not make a three-instruction sequence atomic. Atomicity is a property of the instruction, and a sequence of atomic instructions is not thereby an atomic sequence.
The counter cannot decide or $0, because the value never changes and a lost update leaves no trace. So the second instrument asks a different question: run an operation that does not move the value, and check whether a counter the operation should have incremented got incremented anyway. A sub $0 is a subtraction of zero, which changes nothing; the instrument counts how many times each thread's own paired counter advanced past the value it had written. If the word is not read and written atomically, one thread's write is lost between the other's read and write.
$ ./vecdump | sed -n '/^ PAIR | instruction/,/sbb \$0, LOCK/p'
PAIR | or $0, NO PREFIX | 83 08 00 | 60000 | 23643 | NOT ATOMIC
PAIR | or $0, LOCK | f0 83 08 00 | 60000 | 60000 | ATOMIC
PAIR | and $0xffffffff,NO PREFIX | 81 20 ff ff ff ff | 60000 | 30345 | NOT ATOMIC
PAIR | and $0xffffffff,LOCK | f0 81 20 ff ff ff ff | 60000 | 60000 | ATOMIC
PAIR | xor $0, NO PREFIX | 83 30 00 | 60000 | 28042 | NOT ATOMIC
PAIR | xor $0, LOCK | f0 83 30 00 | 60000 | 60000 | ATOMIC
PAIR | sub $0, NO PREFIX | 83 28 00 | 60000 | 21598 | NOT ATOMIC
PAIR | sub $0, LOCK | f0 83 28 00 | 60000 | 60000 | ATOMIC
PAIR | xor $0x80000000,NO PREFIX | 81 30 00 00 00 80 | 60000 | 26480 | NOT ATOMIC
PAIR | xor $0x80000000,LOCK | f0 81 30 00 00 00 80 | 60000 | 60000 | ATOMIC
PAIR | bt $0 + a mov | 0f ba 20 00; 89 | 60000 | 6172342 | NOT ATOMIC
PAIR | adc $0, NO PREFIX | 83 10 00 | 60000 | 85507 | NOT ATOMIC
PAIR | adc $0, LOCK | f0 83 10 00 | 60000 | 120000 | NOT ATOMIC
PAIR | sbb $0, NO PREFIX | 83 18 00 | 60000 | 4294924018 | NOT ATOMIC
PAIR | sbb $0, LOCK | f0 83 18 00 | 60000 | 0 | NOT ATOMIC
Every value-preserving arm without a prefix loses, and every one with a prefix is exact. That is fifteen rows and a partition, and it is the strongest result in the course because the verdict does not depend on the counts: the arms are 23643, 30345, 28042 and 21598 where exactness is 60000, and the locked versions of all four are 60000 exactly. A number moves between runs. These four all lost, and these five all did not does not.
The last four rows are the interesting failures, and they are failures of the expectation rather than of the instruction. adc $0 adds the carry flag, and a two-threaded loop on that flag produces 120000 with a lock and 120000 without — the flag happens to be stable, and the arm is testing the wrong thing. sbb $0 subtracts it, and the totals are 0 and 4294924018 because a sbb on a carry-heavy loop is not a counter at all. They are in the table because a table of atomic instructions should include the ones the instrument cannot decide, and hiding two of them would make the table look tidier and be worth less.
NOT and NEG report no old value and they are involutions, so neither instrument can read them. Apply twice and ask whether the word came back: the pair is the identity, so a lost update is the only thing that can break it.
$ ./vecdump | sed -n '/^ IDENT|/,/^$/p'
IDENT| instruction | bytes | final | verdict
IDENT| not, twice, no LOCK | f7 d0 | 0x5a5a5a5a | RESTORED
IDENT| not, twice, LOCK | f0 f7 d0 | 0x5a5a5a5a | RESTORED
IDENT| neg, twice, no LOCK | f7 d8 | 0x5a5a5a5a | RESTORED
IDENT| neg, twice, LOCK | f0 f7 d8 | 0x5a5a5a5a | RESTORED
All four say RESTORED, and that is not evidence that they are atomic. Two threads applying NOT an even number of times between them returns the word to where it started whether or not either was lost. The unprefixed arms being RESTORED is the expected reading, and an instrument that cannot tell an atomic operation from a non-atomic one has told you nothing. This is retraction 3, and it is the most useful thing in the file: a lost-update count is a test for atomicity only for operations that move a value in one direction, which is a much narrower statement than “is it atomic” and the reason this section has three instruments rather than one.
This is the part of the concept that changes how you read every other reference on the subject, and it is NOT MEASURED — it is quoted from the SDM and then used to read the measured table above.
$ ./vecdump | sed -n '/1B3\. THE LOCK LIST/,/without it\./p'
1B3. THE LOCK LIST, AND WHO IMPLIES IT. NOT MEASURED.
The SDM names EIGHTEEN instructions that accept a LOCK prefix:
ADD ADC AND BTC BTR BTS CMPXCHG CMPXCHG8B CMPXCHG16B
DEC INC NEG NOT OR SBB SUB XOR XADD XCHG
and says of XCHG, in so many words:
'If a memory operand is referenced, the processor's locking
protocol is automatically implemented for the duration of
the exchange operation, REGARDLESS OF THE PRESENCE OR
ABSENCE OF THE LOCK prefix.'
THE INSTRUCTION WITH NO LOCK IS 'BT'. BTC, BTR and BTS are on
the list; BT is not, because BT does not write. A read-modify-
write a reader builds out of BT and a store is therefore two
instructions and no encoding can make it atomic, which is a
fact about the INSTRUCTION SET rather than about a prefix.
So the lock inc result has a precise reading. The draft said “INC and DEC are not atomic even with the LOCK prefix,” and the SDM is the source of that error: it lists INC as accepting the prefix, and a reader who skims “accepts” as “is atomic” gets it wrong. Measured, both are exact. The reason is in the instruction's own description and is about a flag: INC and DEC do not disturb CARRY, which is precisely why they were given their own opcodes fe and ff separate from the general ADD/SUB forms — and that freedom from the carry flag is exactly what lets the locked versions be ordinary locked operations rather than a special case in the silicon.
And the bit-test row at the end of the counter table is the shape of a limit worth naming. BTS and BTR both read ATOMIC with and without a prefix — not because the unprefixed form is atomic, but because they are idempotent, so this instrument cannot tell. btc toggles and is the only one of the three the counter can decide. Getting a table like this right is less about the hardware than about choosing an operation whose failure has a visible consequence.
cd courses/x86simd/assets/samples && ./build_samples.sh, then read section 4. (Expect the seven locked arms to hit their targets exactly and the unprefixed twins to land somewhere below. Expect the dec rows to be 4294847296 and not 120000 — and if your run reports 120000 for the locked dec, you have found the bug that made retraction 18 necessary, and it is the single most useful thing a reader can reproduce here.)bt $0 and a store, and reason about whether any encoding makes it atomic. (Expect the answer to be no, and expect the reason to be a fact about the instruction set rather than about a prefix: BT does not write, so a read-modify-write built out of it is two instructions, and no prefix can make a sequence atomic. This is the one place in the course where the answer is a structural argument rather than a measurement, and it is worth noticing that the artifact says so.)xchg makes a sequence safe. Take the last two rows of the counter table and reverse them — put the XCHG first. (Expect it to be exact, because now the XCHG really is the only memory-touching instruction in the sequence and it really is atomic. Same instruction, same prefix, opposite verdict. The property was never about the instruction; it was about being the one that touches memory in a read-modify-write.)lock in front of an instruction that never needed it. (Expect to find some, and expect the reason they are harmless is that the prefix costs a few percent on an instruction that was already serialising for another reason. The interesting review question is not “is this lock necessary” but “what does this instruction guarantee, and does the code around it depend on the guarantee or on the hope that it was there”.)Backwards, the SMP course's atomic concept measured the cost of a race and told you that the fix is lock. This page is the reference that says whichlock, and it is worth reading the pair in that order: knowing the principle without the list produces code that is correct by luck, and knowing the list without the principle produces code that is fast and wrong. The SIMD course's compiler concept is where you will meet the same problem in a different shape — a compiler that reorders a non-atomic access is a bug, and the rule that prevents it is the same list.
Forwards, and the connection is mechanical rather than thematic. Every row in the table above is a single instruction made atomic, and the next concept is about what happens when one core's atomic operation is not enough — because atomicity says nothing about order. Two cores can each perform their operations perfectly and still disagree about the order they happened in. That gap is what MFENCE and its two siblings exist to close, and it is the reason the btc and adc rows that could not be decided here are worth keeping even unresolved.
Outward. The eighteen-instruction list is a beautiful piece of historical accident and it is the same list on every x86-64 part ever made, because it is baked into the encoding rather than the implementation. The assembly course's integer concept covers the flag semantics that make INC special here — INC and DEC not touching CARRY is a flag-design decision from 1978 that is still the reason two instructions behave differently from their obvious general forms. The transferable shape is: an instruction set accumulates special cases, and the special case is almost always about a flag nobody was thinking about when they wrote the loop that uses it.