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.

[Octocontrabass]

The "atomicity" of a single load/store exists on every CPU, x86 included

Loads and stores are not always atomic on x86. For a load or store to be atomic, it must meet specific requirements including size, alignment, and cache configuration.

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

But only on your special "simple bus" CPU that can modify individual bits of memory. On any normal CPU, you still need atomic RMW instructions to manipulate individual bits.

I only use ordinary independent load and store. What I avoid is the all-in-one RMW atomic instruction like CAS.

An ordinary store can't be smaller than a whole byte. You rely on stores to individual bits, which is anything but ordinary.

I designed this protocol entirely from scratch, without referencing any existing contention algorithms or established terminology,

You should research existing algorithms so you can understand what's wrong with your algorithm.

[mochangyan]

Let me clarify the slot layout:
The logical unit for one ID is 1 bit — chosen for minimal space usage, best performance, and portability. CPUs do not natively compute in 8-bit units — internally they operate on individual bits, in parallel or serially. Storing one bit of state in an 8-bit unit wastes storage capacity.

The 1-bit unit is also chosen with future possibilities in mind: the design does not lock itself into any fixed word width or architecture. If CPU throughput becomes the bottleneck, the design can extend to GPU-like massively parallel architectures. Since the logical model is already bit-level, porting to bit-parallel hardware is frictionless — no repacking, no model rewrite.

On x86, one ID is stored as one 8-bit byte slot, only to match x86's byte-level memory access granularity. Packing bits would require read-modify-write and be slower; one ID per byte trades 7 unused bits for avoiding RMW entirely.
0b11111111 = one slot for one executor's ID entry.
0b11111111 11111111 = two consecutive slots for two executors' ID entries.
With N executors, each file table entry reserves 8 × N bits (N bytes) at its tail as the contention ID region — one 8-bit byte slot per executor.

This 8-bit storage width is only for x86 compatibility, it does NOT mean the numeric ID value is limited to 8 bits.
When contending, I perform a plain store to overwrite the entire 8-bit slot. There is no partial-bit modification, so no read-modify-write sequence is required.

These contention slots are embedded at the tail of each individual file table entry, after the fixed-length path, size and data offset fields. Every file table record carries its own group of contention slots for synchronizing access to that specific file.

The wait step is already part of the protocol semantics, so added latency is not a problem — the protocol never assumes read-back happens immediately. What matters is controllable, not low, latency. GPU compute-heavy paths (bulk contention verification, checksums, deduplication, metadata scans) are data-parallel and GPU-friendly. Notably, GPUs have no CPU-style atomic RMW instructions — inter-thread coordination relies on shared memory and software detection — so this protocol's no-atomic-instruction philosophy is a natural fit there. Fine-grained per-entry contention stays where latency matters; bulk verification can be offloaded. If the whole contention flow runs inside a GPU block using shared memory, warp/block synchronization is lockstep-deterministic.

[Octocontrabass]

On x86, one ID is stored as one 8-bit byte slot, only to match x86's byte-level memory access granularity. [...] With N executors, each file table entry reserves 8 × N bits (N bytes) at its tail as the contention ID region — one 8-bit byte slot per executor.

On x86, stores to different addresses from different CPUs are not guaranteed to be observed in the same order from every CPU. Two CPUs may read the mutex region, see that all slots are clear, set their respective bytes, read the region again, and both see that they are the only CPU to set a byte in that region.

[mochangyan]

You are right about real x86's memory model — stores to different addresses from different CPUs have no global propagation order, and without a fence two cores can each read back only their own byte and both pass verification. But this protocol does not run on that model.

The design uses executors instead of assuming a specific CPU. When a specific target CPU exists, the design would use that CPU's native mechanisms directly. Since there is no fixed target CPU here, the executor layer is the only way to guarantee compatible execution across unknown hardware — it is not an extra layer by choice, but a necessity. Executors abstract the cores: one executor corresponds to one core. An executor defines a unified, simplified memory semantics: one executor can have at most one load and one store in flight — never two memory ops, never two store ops. There is no out-of-order execution and no store buffer in this model. The bus propagates writes immediately in a single global order.

Any CPU that implements these executor rules can run this protocol. The protocol therefore does not depend on any particular CPU's memory model — which is exactly why the x86 cache-coherence objection does not apply: the executor layer has already normalized that behavior away. After the wait step, read-back necessarily observes every contender's write. The double-winner interleaving you describe cannot occur under these rules — it requires the very mechanisms this model explicitly removes.

[Octocontrabass]

Since there is no fixed target CPU here, the executor layer is the only way to guarantee compatible execution across unknown hardware

No it isn't. All major programming languages provide their own CPU-independent solutions to memory ordering problems. For example, C++ has well-defined memory ordering semantics.

An executor defines a unified, simplified memory semantics: one executor can have at most one load and one store in flight — never two memory ops, never two store ops. There is no out-of-order execution and no store buffer in this model. The bus propagates writes immediately in a single global order.

Your executors must be very slow, since they require expensive memory barriers around every read and write operation. (Meanwhile, C++ allows you to specify exactly how memory ordering is important to your program, so the compiler can avoid unnecessary memory barriers.)