Font: Spacing: Letters: Width:

Ordering: TSO, the Three Fences, and What Each One Orders

25 minadvancedModule 2: Atomics and Ordering, and the Instructions That Imply LOCKContinues from x86-atomics

Why this matters

The previous concept made every instruction in the atomic set individually atomic. That is necessary and nowhere near sufficient, and the gap between the two is the entire subject of this page: two cores can each perform their operations perfectly and still disagree about the order in which they happened. Atomicity is a property of an instruction. Ordering is a property of a sequence, and the x86-64 instruction set gives you three instructions — and one of the three is nearly useless on a modern part.

This is also the concept where the course's one architecture-shaped answer lives. The SMP course taught total store order as a model and named the store buffer as the mechanism. The x86-64 reference for that is short — three opcodes, six bytes of encoding, and a documented rule that says stores retire in order and loads may pass them — and the reference is worth having precisely because the model is architecture-neutral and the answer is not.

The three fences, which are three bytes and one opcode

“What does SFENCE actually encode?” has an answer, and it is short enough to print in full. NOT MEASURED here — disassembled, not quoted, because the point of the table is that the encoding is small enough to be completely understood:

$ ./vecdump | sed -n '/5B\. THE FENCES/,/are 11 and 000/p'
  FENCE | the three bytes | the ModRM reg field, bits 5:3
  ------+-----------------+--------------------------
  MFENCE| 0f ae f0        | 111 = 7   order loads AND stores
  LFENCE| 0f ae e8        | 101 = 5   order loads only
  SFENCE| 0f ae f8        | 111 = 7   order stores only
         all three are the SAME opcode, 0F AE, and the
         mod and rm fields are 11 and 000 in all three.

Read the reg column twice. MFENCE and SFENCE both have reg=7. They are told apart by the map — the 0F escape byte they share — and by the CPU’s internal decode of the escape. So there are not three opcodes and there are not three reg values either: 0F AE is one opcode with a three-bit selector, and a decoder that switches on ModRM.reg alone gets MFENCE and SFENCE right only by accident. That sentence is the practical one, and it is why the last concept of this course exists.

And then the detail everybody gets wrong, which is retraction 22:

THE DRAFT SAID "a single bit position." IT IS TWO, AND THE DIFFERENCE IS WHY THE THREE BITS ARE NOT CONTIGUOUS. MFENCE 0xF0 reg = 111 = 7 SFENCE 0xF8 reg = 111 = 7 bit 3 0 in MFENCE, 1 in SFENCE <- differs bit 2 0 in both bit 1 0 in both Two bit positions differ, not one. A "single bit" story about this table cannot be made to fit, and the reason it cannot is that bits 2 and 1 are CLEAR IN BOTH, which is exactly the pattern a single-bit claim cannot produce.

So what does each one order? SFENCE orders stores against each other, LFENCE orders loads against each other, and MFENCE orders both. Every memory barrier on x86-64 is one of these three, and on a modern part most of them compile to nothing at all — because the memory model guarantees that they were unnecessary in the first place.

And here is the property that surprises people, quoted from the artifact because it is a fact about the instruction rather than a recommendation:

A LOCKED INSTRUCTION IS A BETTER FENCE THAN SFENCE AND IT IS ONE INSTRUCTION SHORTER. The LOCKED store already drains the buffer, because the store cannot retire until it has. That is why a spinlock built on CMPXCHG needs no SFENCE, and it is a property of the INSTRUCTION rather than a recommendation.

That is the practical heart of the whole page. A hand-rolled spinlock that does lock cmpxchg and then an sfence is paying for a fence the cmpxchg already provided, and the reason it is easy to get wrong is that the sfence is what looks like the correctness argument.

The ping-pong: seven arms, and the result that is not the expected one

Two threads pinned to two cores, a barrier, and one store plus one peer load per iteration. Seven arms, interleaved, min-of-N, and the word reset before every one:

$ ./vecdump | sed -n '/^  ORD  |/,/the two floors differ/p'
  ORD  | store to my line, then load the peer's  (no flag)    52.399 ticks/iter
  ORD  | ...with an SFENCE between them                    62.036 ticks/iter
  ORD  | ...with an MFENCE between them                   143.045 ticks/iter
  ORD  | ...with a LOCKED store instead of a plain one     125.864 ticks/iter
  ORD  | store and load, both words in ONE cache line      78.245 ticks/iter
  ORD  | THE FLOOR: the store alone, no peer load          62.151 ticks/iter
  ORD  | the other floor: the peer load alone              39.245 ticks/iter

And the layout, which is printed because the first version of this experiment was wrong about it and the wrongness was invisible in the numbers:

$ ./vecdump | sed -n '/THE LAYOUT/,/different lines/p'
  THE LAYOUT, printed because R24 was a layout bug:
    the two 'mine' lines are  64 bytes apart (TWO lines)
    the two 'both' lines are  64 bytes apart (TWO lines)
    'mine' and 'both' are in different lines: yes

Three findings, and none of them is the textbook one.

Adding an SFENCE does not turn the ping-pong into the textbook picture of a line changing hands on every iteration. What SFENCE does is make the arm more expensive, and what the LOCKED store does is make it more expensive, and both of those are the store buffer draining — which is the mechanism the SMP course named. So the extension confirms the explanation and does not rescue the shape.
Why the shape never appears: a store does not invalidate the other core’s copy when it executes. It goes into this core’s store buffer and the peer’s copy stays VALID until the store retires. Two threads in a tight loop with no synchronisation therefore do not take turns: each runs ahead, each load often finds the peer’s line still valid and SHARED, and the transfers that do happen are spread out rather than serialised. That is total store order, visible as an absence of a cost.
The same-line arm is several times the two-line version, and that is a bigger effect than any fence here. Whichever way you are going to make this fast, moving the two words apart is worth more than choosing a fence — and that is false sharing, the cheapest performance bug in concurrent code to write and the most expensive to find.

MECHANISM: INFERRED. There is no counter here that can count coherence traffic: perf_event_paranoid is 4 and every mechanism named above is inferred from a duration. A duration bounds a count without measuring it, and the instrument that would settle it is perf_event_open with a permissive paranoid setting and a PMU passthrough from the host.

Which is also why a race is hard to find

The result of all that is worth more than the number: the fast path and the slow path look the same on average. A program with a race usually runs at full speed and gives the wrong answer once in a million times, which is exactly the profile of a heisenbug. The single-line row is the one that does show a cost, and it shows it because two words in one line is a different data structure rather than a different fence.

The direction flag is bit 10, and there is a story about why it is hard to remember

This course was written from a brief that said the direction flag is EFLAGS bit 21. It is not. Here is the register, read out with PUSHFQ in the artifact, with every bit named rather than the one remembered:

$ ./vecdump | sed -n '/^  EFLAGS/,/bit 21/p'
  EFLAGS as read by PUSHFQ      0x0000000000000202
    bit  0 CF                 0
    bit  2 PF                 1
    bit  6 ZF                 0
    bit  9 IF                 1
    bit 10 DF, THE DIRECTION  0
    bit 11 OF                 0
    bit 16 RF                 0
    bit 18 AC                 0
    bit 21 ID, NOT DIRECTION  0

Bit 10 is DF. Bit 21 is the ID flag, and the ID flag has a completely different job: before CPUID existed, software identified a processor by setting a bit it was not supposed to be able to set and pushing the flags. The 8086 and 8088 had no such bit; the Pentium does. The two flags have nothing in common, and the bit number is the whole of the confusion.

There is a small tell here that is worth more than the fact. The direction flag is set and cleared by two instructions that do nothing else: STD sets it and CLD clears it. There is no complement — no CLDD, no instruction to flip it — which is a gap in the instruction set closed with PUSHF, an XOR and POPF. And the reason the ID flag exists at all is that it needed to be settable without a dedicated instruction, which is exactly the kind of bit that gets confused with one that has its own STD. A flag that is set by a dedicated instruction and a flag that is set by arithmetic look the same in a manual and behave nothing alike in a shell.

Now what it costs. rep movsb moves a string in the direction DF names, and the two directions are not symmetric:

$ ./vecdump | sed -n '/bytes |   DF=0/,/^  ---/p'
  bytes |   DF=0  |   DF=1  | ratio  | ticks/byte up | ticks/byte dn
  ------+----------+----------+--------+--------------+--------------
     16 |       23 |      184 |   8.00 |       1.4375 |      11.5000
    256 |       23 |      253 |  11.00 |       0.0898 |       0.9883
   1024 |       46 |      782 |  17.00 |       0.0449 |       0.7637
   4096 |       92 |     2875 |  31.25 |       0.0225 |       0.7019

Three things in that table, and the middle one is the finding.

The downward direction is slower at every size — 8.00×, 11.00×, 17.00×, 31.25× — and both arms printed nothing from the checksum comparison on every row, which is the check that they copied the same bytes. A rep movsb with DF=1 is a correct copy. It is just a much slower one.
The ratio GROWS with size, and that is the whole result. A fixed per-call overhead would give a constant ratio, so a growing one means a per-byte cost that the downward direction pays and the upward one does not — which is a hardware counter. The artifact marks the mechanism INFERRED and prints “why the downward string direction is slower” in its limits block, because the number and the reason are separable and only the number is measured.
The forward per-byte cost also falls, from 1.4375 at 16 bytes to 0.0225 at 4096. That is the loop-overhead term amortising away, and it is printed in the same table precisely so the reader can see that the ratio is not measuring overhead: both arms have the same overhead and the ratio still grows.

Apply it

Reproduce the fence bytes.cd courses/x86simd/assets/samples && ./build_samples.sh, then read section 5B. (Expect 0f ae f0, 0f ae e8, 0f ae f8 and reg fields 7, 5, 7. Then write the decoder that switches on reg alone and watch it confuse MFENCE with SFENCE — which is the one practical thing on this page you can get wrong in a real disassembler.)
Remove the sfence from a spinlock. Take a lock cmpxchg spinlock and delete the sfence after the successful exchange. (Expect it to remain correct, because the locked instruction already drained the buffer, and expect the reasoning to be the thing that changed: the fence was never the correctness argument, the locked RMW was. Then find the version that is wrong — a spinlock built on bt plus a store — and notice that its bug is a different bug, in a different category, that no fence could fix either.)
Build the L'L-style decoder bug for the fence set.(Expect the failure to be a decoder that produces legal bytes for a different instruction, with no length surprise and no trap. This is the same class as the AVX-512 62 prefix problem in the previous concept, and recognising the class twice is the point: an encoding is a namespace, and a decoder that ignores a field dependency is a namespace violation with a very quiet symptom.)
Find the bit 21 in a real program. Search a codebase for 21 near the word “flag”. (Expect to find a PUSHF/modify/POPF sequence that is not about the direction flag, and expect it to be an ID-detection routine that nobody has run since 1994. The sequence is still the documented way to identify a processor that has CPUID, which means a piece of 1994 identification code is still load-bearing in code that thinks it is from 2020.)
Measure the direction flag’s cost in your own string code.(Expect a memmove-based copy to be roughly the speed of the DF=0 arm, and expect hand-written rep movsb to be close to it too. Then write a copy that runs with DF=1 and watch it approach the 31.25× row at large sizes — and then find out why the libc never does this, which is that rep movsb is not actually the fastest string primitive on a modern part for small sizes and is only competitive above a threshold that is not 16 bytes.)

Connect

Backwards, the previous concept made every instruction atomic and this one says what atomicity does not buy. The SMP course's ordering concept is where TSO is taught as a model, and the seven-arm table above is that model coming back as a number — and coming back disagreeing with the shape the model predicts, which is the most valuable thing in the section. Its atomic concept owns the store buffer story; this page is the x86-64 evidence for it.

Forwards. The last concept is the artifact, and it is a change of subject that is not really a change: it encodes and decodes thirty vector instructions, and the fence table above is the reason a second reader matters. A decoder that switches on ModRM.reg alone gets two of the three fences right by accident, and a round trip through a decoder built from the same wrong table would report thirty perfect rows and be wrong about every one of them.

Outward. The store buffer is the reason TSO exists as a model rather than as a prohibition, and it is the reason the language-level answer is a mutex and not a fence: a C11 atomic_load with acquire ordering compiles to nothing on x86-64, because the hardware already does it. The ordering concept owns that translation and this page is the hardware half of it. And on an ARM machine the same source line becomes a dmb — so the fence you do or do not emit is a fact about where the code runs, which is the single most useful thing to carry out of the whole section.

Keyboard Shortcuts