QwQ-FS: A complete file system with no atomic instructions — software bitmask ID contention on bare metal

[mochangyan]

The "atomicity" of a single load/store exists on every CPU, x86 included — I have never denied that. What I deny is the need for dedicated atomic instructions (CAS, lock-prefixed ops, atomic RMW) to arbitrate contention. The arbitration is done by the protocol itself (discoverability), not by an atomic instruction. "Simple bus" removes out-of-order and write-propagation issues so read-back is trustworthy; it is not a source of "atomic instructions". And using atomic instructions here would only waste performance: the protocol has no need for them — discoverability already does the arbitration — and atomic ops (bus locks, waiting on other CPUs) are pure overhead in this model. On a simple bus they add nothing and cost latency and parallelism.

[Octocontrabass]

What I deny is the need for dedicated atomic instructions (CAS, lock-prefixed ops, atomic RMW) to arbitrate contention.

If you make every instruction atomic, you don't need dedicated atomic instructions. Your claim of "no atomic instructions" is still false.

On a simple bus they add nothing and cost latency and parallelism.

On a simple bus, all instructions cost latency and parallelism because all instructions are atomic.

[mochangyan]

The "atomicity" of a single load/store exists on every CPU, x86 included — I have never denied that. What I deny is the need for dedicated atomic instructions (CAS, lock-prefixed ops, atomic RMW) to arbitrate contention. The arbitration is done by the protocol itself (discoverability), not by an atomic instruction. "Simple bus" is a clean baseline environment; it removes out-of-order and write-propagation issues to make read-back easy to verify. It is not a source of "atomic instructions". And using atomic instructions here would only waste performance: the protocol has no need for them — discoverability already does the arbitration — and atomic ops (bus locks, waiting on other CPUs) are pure overhead in this model. On a simple bus they add nothing and cost latency and parallelism.

The sequence read → write → wait → read-back is multiple separate instructions. There is no single hardware instruction that wraps this whole sequence as atomic. I only use ordinary independent load and store. What I avoid is the all-in-one RMW atomic instruction like CAS.

Even if this whole sequence (read → write → wait → read-back) were implemented as a single custom hardware instruction, it would still not be equivalent to a conventional atomic RMW like CAS. CAS suppresses conflicts in hardware and guarantees exactly one winner. This protocol permits conflicts to happen. After verification, it only returns that this slot is occupied, and all contending participants fail and retry. The arbitration model is fundamentally different.

I do not mention the later work and ID-clearing steps up front for simplicity. The acquisition sequence: read → write ID → wait → read-back, is the critical part that distinguishes this protocol from conventional atomic RMW. Adding the later workflow early would obscure the core difference and make it harder to follow.

The full complete flow is: read → write ID → wait → read-back (verify). If verification passes, perform the target file operation, then clear the ID after the operation finishes.

The mismatch between our statements comes from my informal, self-coined wording. I designed this protocol entirely from scratch, without referencing any existing contention algorithms or established terminology, so the words I use may not align with the definitions this community normally adopts.

This protocol also works correctly even on CPUs with out-of-order execution, as long as software preserves the ordering of these four critical steps: read, write ID, wait, read-back. The out-of-order rearrangement of unrelated instructions by the CPU will not break the protocol.