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

Discussions on more advanced topics such as monolithic vs micro-kernels, transactional memory models, and paging vs segmentation should go here. Use this forum to expand and improve the wiki!
Post Reply
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

The mainstream consensus is that lock-free operation must be provided by hardware atomic instructions (ETH Zurich: "These primitives typically have to be provided by hardware"). This design proposes a counterexample: a pure software protocol (Read → Write → Wait → Read-back → Clear) + bitmask contention + instruction-counted waiting that achieves lock-free parallel allocation on bare metal, without atomic instructions and without memory barriers. Please examine it from a falsification angle — wait-time calibration, disk contention path latency, rebuild cost, and application-managed contiguous layout are the four most attackable points.

1. ONE MODEL, MULTIPLE WORKING POSITIONS
The same model (configuration-driven + fixed-length entries + parallel ID contention) is reused by position:

- Storage version = QwQ-FS: partition table + file system (the FS itself doubles as the partition table; position zero holds the configuration, avoiding nested layering);
- Memory version = QwQ-mm: memory management (lock-free parallel, bitmask IDs);
- It can also run on a GPU (the parallel unit is basically 1 bit; a GPU processing one word at a time is a natural fit; no dependence on atomics, no dependence on memory model).
Not "three-in-one", not feature merging — the same model reused.

2. BOOT CHAIN CHOICES

- No UEFI: (1) position zero must hold the configuration, and the GPT partition table occupies exactly that position; (2) the FS itself doubles as a partition table + EFI = nested layering; (3) GPT structure not understood; (4) repeated build failures; (5) dislike of protocol/patent/interface restrictions.
- No BIOS: (1) in real mode, position 0 holds the interrupt vector table, so the configuration has nowhere to go; (2) interface restrictions.
- ROM wanted but unusable: (1) vendor-locked; (2) only 16-bit width supported, while the configuration must be written at the CPU's widest width; (3) too small; (4) no accurate memory information obtainable.
- BIOS chosen only as last resort: (1) it can provide the E820 memory map; (2) no specific partition table required; (3) ROM/EFI unusable.

3. DISK LAYOUT
Reserved 1 GiB (BIOS + memory init) | Config area (18 entries) | Fragment table (fixed-length entries) | File table (fixed-length entries) | Content area (app data, contiguous)

- Content area start = file table start + file table size (computed, not separately configured);
- Fragment table entry: fixed-length size → fixed-length start → fixed-length contention ID at the tail;
- File table entry: fixed-length path (actually a file name; no hierarchy) → fixed-length size → fixed-length start → fixed-length contention ID at the tail;
- CPU-native little-endian direct read/write; no truncation markers (the early 0x1A marker misfired across encodings and was removed);
- Index-multiplication addressing (offset = entry width × index); widths written in the config header, zero parsing.

4. CONFIGURATION AREA — 18 ENTRIES (source: manual / computed / hardware-calibrated)

#1 Config width — Manual
#2 Total config space — Manual
#3 Fragment & file table size/start field width (merged, widest wins) — Manual
#4 Fragment table start — Computed = end of config area (#2)
#5 Fragment table entry count — Manual
#6 Fragment table entry width — Manual
#7 Fragment table entry start offset — Computed = size width (#3)
#8 Fragment table entry ID offset — Computed = size + start (2×#3)
#9 File table start — Computed = fragment table start + fragment table size (#4 + #5×#6)
#10 File table entry count — Manual
#11 File table entry width — Manual
#12 File table path width — Manual
#13 File table entry size offset — Computed = path width (#12)
#14 File table entry start offset — Computed = path + size (#12 + #3)
#15 File table entry ID offset — Computed = path + size + start (#12 + 2×#3)
#16 Parallel ID width — Manual
#17 Parallel wait time (instruction count N for step 3) — Hardware-calibrated or manual
#18 Ordinary file start (recorded as entry number) — Executor-side; not a bare-metal requirement

- #18 semantics: executors/applications only pass entry numbers, byte addresses are forbidden; the address is computed internally as "entry × entry width", eliminating illegal addresses and alignment bugs at the source;
- Config corruption → refuse to mount, go straight to rebuild;
- Extensions (log/hash/append toggling) are an executor-side module system; the config area has no extension switches — extensions are done by executors, not by config.

5. CONCURRENCY PROTOCOL: READ → WRITE → WAIT → READ-BACK → CLEAR

- The ID is a fixed-length contention slot at the tail of each fragment/file table entry, located in storage (disk), not in a shared memory variable; there is no resident copy in memory — only step 4 reads it back into a temporary copy;
- Contention slot starts at 0000; each executor owns one bit (a=1000, b=0100); write only your own bit (write 1 bit), overwriting writes are forbidden — non-overwrite write is a principle;
- Protocol = Read → Write → Wait → Read-back → Clear; all zero = win; not all zero = clear your bit and move to a new slot (or keep contending on the same slot);
- Why the ID sits at the entry tail: fixed-offset direct read/write, ID separated from content, size/start fields unaffected.

Code: Select all

if read_storage(ID slot) == 0000:                    # 1 Read: write only if all zero (pre-write boolean free check)
set own bit in storage(ID slot) to 1             # 2 Write: only 1 bit, overwriting forbidden (read/write not atomic)
execute N instructions                           # 3 Wait: instruction count (#17), let the write settle
temp = read_storage(ID slot)                     # 4 Read-back: copy into a temporary memory variable
set own bit in temp to 0                         #    only the copy is cleared; this is NOT clearing storage
if all bits of temp are 0:                       #    rest all zero = contention won
do your work (between step 4 and step 5)
set own bit in storage(ID slot) to 0         # 5 Clear: only your own 1 bit; never clear a whole byte
else:                                            #    not all zero = contention lost
set own bit in storage(ID slot) to 0         # 5 Clear: clear your residue; retry on a new slot
- Read/write is not atomic, but correctness does not rely on atomicity: it rests on discoverability (read-back after write decides the winner) + wait coverage, not on "uninterruptible" (atomic);
- Double-success argument: with a sufficient wait, A's write is necessarily seen by B → when B reads back, A's bit is set → B loses; double success is impossible;
- Bitmask vs. overwrite write: trampling is discoverable vs. undiscoverable; torn window is one bit vs. multiple bytes;
- Difference from CAS: CAS = compare + conditional atomic write + retry on failure; QwQ has no "compare", no expected value, and the write content is unconditional (write only your own bit = 1), but the write has a precondition (write only if all zero) — correctness is ultimately decided by the post-write read-back.

6. WHY THE WAIT USES INSTRUCTION COUNTING (#17)

- What the wait is for: the visibility window of a non-atomic write — waiting for "the read/write to settle within the region";
- Accounting for cache/bus/clock/concurrency jitter, err on the long side; a long wait can be filled with useful instructions — waiting is a fillable time window, not spinning;
- No timers, no TSC, no memory barriers: no bus touch, no shared-memory touch, blocks no one, works across frequencies;
- Instruction count = time measurement = a property common to all hardware (any machine that can execute instructions must spend time) — independent of hardware, memory model, and era;
- The only shared-resource touch in the whole path is "simultaneous read-to-judge-zero" → structurally fully parallel, no serial segment; wait cost is independent of thread count and does not scale with core count.

7. COMPARISON WITH THE MAINSTREAM

- Synchronization means — Mainstream: Atomic instructions (hardware tax: atomic units + cache coherence + bus locks) | QwQ: Ordinary read/write + instruction counting
- Mutual exclusion / allocation — Mainstream: Mutual exclusion = serial (take number + scan + queue) | QwQ: Contention allocation = parallel + probabilistic retry (O(1) zero-check)
- Correctness basis — Mainstream: Uninterruptible (atomic) | QwQ: Discoverable (read-back after write) + time
- Torn read — Mainstream: read → decrement → write-back has tearing/lost updates | QwQ: No "read-old → compute-new → write-back" pattern; immune
- Mainstream "lock-free must be hardware-atomic" has three reasons: (1) cache visibility — cores have private caches; a write by one core may be invisible to another, needing barriers/atomics; (2) read-modify-write must be atomic (software cannot do it); (3) hardware provides the primitives (ETH Zurich). All three are bypassed: (1) visibility via "wait + read-back" (instruction counting gives the write time to settle, read-back confirms); (2) read-modify-write is split into read/write/read-back, correctness rests on read-back; (3) correctness changes from "uninterruptible" to "discoverable" — discoverability is achievable in software;
- Single-bit contention vs. complex-structure lock-free: mainstream lock-free data structures (queues/stacks/hash tables) must update complex shared state, so atomics are required; QwQ's scene is "single-bit contention" (who owns it or not; the state is one bit) — the state is minimal, so splitting + confirmation is enough;
- Hardware tax: general CPUs pay the CAS hardware tax; in bare-metal scenarios the tax must be built from zero, and QwQ pays none of it.

8. PROPERTIES

- Natively asynchronous: correct even when executors run at different frequencies; atomics bet on "speed/synchronization", QwQ bets on "time + confirmation";
- Default compatibility with unbounded threads is a design axiom: hence storage placement, software protocol, move-on-failure (no waiting), zero resident memory, bitmask isolation;
- Depends on nothing but computation: ordinary read/write/execution time exists on any machine that can compute — works across past/present/future timelines, across file-system categories, only requiring config changes;
- Configuration-driven: the protocol never changes (Read → Write → Wait → Read-back → Clear); all timeline differences are absorbed by configuration;
- Structure pays, operators choose: the protocol pays "locating ability" (constant), operators pay "strategy" (free); ease-of-use is outsourced to applications, trees are outsourced to upper layers, strategy is outsourced to operators;
- Parallelism is the steady state, not the exception: multi-executor parallelism is the default way of running, not an acceleration option; wait/zero-check/relocate are part of every normal path, so they must be O(1), lock-free, constant-cost.

9. SEARCH MODULES (96 = 88 FILE SEARCHES + 8 FRAGMENT SEARCHES)
Not independent algorithms — they are combinations of orthogonal dimensions: target table × match condition × scan direction × start point × return shape.
Dimensions:

- Target table: File table / Fragment table
- Match condition: Exact / Prefix / Range / Extreme (max/min/Top-N) / Statistics
- Scan direction: Sequential / Reverse / From-position / Start-bidirectional (0→n-1→1→n-2→…, clamping inward) / Start-bidirectional-segmented (clamp in segments from both ends, segment length configurable) / From-position-bidirectional (expand one entry at a time from center to both sides) / Segmented-bidirectional (from a given center: right N → left N → alternate segments, segment length N configurable)
- Return shape: Brief single / Brief multi / Detailed single / Detailed multi (with path + size + start)

FILE SEARCH 88:
(1) Extreme queries (8) — scan from head/tail maintaining Top-N; usage: defragmentation, largest/smallest fragment, batch reclaim.
largest_file_query_from_start / largest_n_files_query_from_start / smallest_file_query_from_start / smallest_n_files_query_from_start / largest_file_query_from_tail / largest_n_files_query_from_tail / smallest_file_query_from_tail / smallest_n_files_query_from_tail

(2) Sequential/Reverse (4) — forward/reverse scan, exact match; usage: exact entry location for read/write/delete.
sequential_file_table_search / sequential_fragment_table_search / reverse_file_table_search / reverse_fragment_table_search

(3) Prefix match (26) — prefix × sequential/reverse/from-position/range/start-bidirectional × brief/detailed × single/multi; usage: batch operations on same-prefix files.
prefix_sequential_file_table_search / prefix_reverse_file_table_search / prefix_from_position_sequential_file_table_search / prefix_from_position_reverse_file_table_search / prefix_start_bidirectional_file_table_search / prefix_detailed_start_bidirectional_file_table_search / prefix_single_return_from_position_bidirectional_file_table_search / prefix_range_sequential_file_table_search / prefix_range_multi_return_file_table_search / prefix_range_detailed_single_return_file_table_search / prefix_range_detailed_multi_return_file_table_search / prefix_multi_return_sequential_file_table_search / prefix_multi_return_reverse_file_table_search / prefix_multi_return_from_position_sequential_file_table_search / prefix_multi_return_from_position_reverse_file_table_search / prefix_multi_return_from_position_bidirectional_file_table_search / prefix_detailed_single_return_sequential_file_table_search / prefix_detailed_single_return_reverse_file_table_search / prefix_detailed_single_return_from_position_sequential_file_table_search / prefix_detailed_single_return_from_position_reverse_file_table_search / prefix_detailed_single_return_from_position_bidirectional_file_table_search / prefix_detailed_multi_return_sequential_file_table_search / prefix_detailed_multi_return_reverse_file_table_search / prefix_detailed_multi_return_from_position_sequential_file_table_search / prefix_detailed_multi_return_from_position_reverse_file_table_search / prefix_detailed_multi_return_from_position_bidirectional_file_table_search

(4) Range match (8) — scan within size/position range × sequential/detailed/multi/statistics/extreme; usage: range-partitioned parallelism, range statistics.
range_sequential_file_table_search / range_multi_return_file_table_search / range_detailed_single_return_file_table_search / range_detailed_multi_return_file_table_search / range_file_count_statistics / range_largest_file_query / range_smallest_n_files_query / range_smallest_file_size_query

(5) From-position (4) — scan backward/forward from a given entry position; usage: nearest lookup.
from_position_sequential_file_table_search / from_position_reverse_file_table_search / from_position_sequential_fragment_table_search / from_position_reverse_fragment_table_search

(6) Start-bidirectional (2) — alternate from head and tail (0→n-1→1→n-2→…); usage: huge tables where the target's end is unknown.
start_bidirectional_file_table_search / start_bidirectional_fragment_table_search

(7) From-position-bidirectional single (2) — expand one entry at a time from a given center to both sides (single return); usage: nearest-first. (Multi-return bidirectional in group 10.)
single_return_from_position_bidirectional_file_table_search / single_return_from_position_bidirectional_fragment_table_search

(8) Detailed single return (10) — "detailed single" × sequential/reverse/from-position/bidirectional; usage: single-entry location needing full path+size+start.
detailed_single_return_sequential_file_table_search / detailed_single_return_reverse_file_table_search / detailed_single_return_sequential_fragment_table_search / detailed_single_return_reverse_fragment_table_search / detailed_single_return_from_position_sequential_file_table_search / detailed_single_return_from_position_reverse_file_table_search / detailed_single_return_from_position_sequential_fragment_table_search / detailed_single_return_from_position_reverse_fragment_table_search / detailed_single_return_from_position_bidirectional_file_table_search / detailed_single_return_from_position_bidirectional_fragment_table_search

(9) Detailed multi return (10) — "detailed multi" × sequential/reverse/from-position/bidirectional; usage: batch needing full info.
detailed_multi_return_sequential_file_table_search / detailed_multi_return_reverse_file_table_search / detailed_multi_return_sequential_fragment_table_search / detailed_multi_return_reverse_fragment_table_search / detailed_multi_return_from_position_sequential_file_table_search / detailed_multi_return_from_position_reverse_file_table_search / detailed_multi_return_from_position_sequential_fragment_table_search / detailed_multi_return_from_position_reverse_fragment_table_search / detailed_multi_return_from_position_bidirectional_file_table_search / detailed_multi_return_from_position_bidirectional_fragment_table_search

(10) Multi-return general (11) — "brief multi" × sequential/reverse/from-position (incl. bidirectional); usage: batch listing, reclaim candidates.
multi_return_sequential_file_table_search / multi_return_reverse_file_table_search / multi_return_sequential_fragment_table_search / multi_return_reverse_fragment_table_search / multi_return_from_position_sequential_file_table_search / multi_return_from_position_reverse_file_table_search / multi_return_from_position_sequential_fragment_table_search / multi_return_from_position_reverse_fragment_table_search / multi_return_from_position_bidirectional_file_table_search / multi_return_from_position_bidirectional_fragment_table_search / multi_return_detailed_sequential_file_table_search

(11) Bidirectional-detailed / start (3) — start-bidirectional × detailed + single-return start-bidirectional; usage: huge-table two-end convergence.
detailed_start_bidirectional_file_table_search / detailed_start_bidirectional_fragment_table_search / single_return_start_bidirectional_file_table_search

Total: 8+4+26+8+4+2+2+10+10+11+3 = 88.

FRAGMENT SEARCH 8:

- find_empty_fragment_entry_in_range — find the first free fragment entry within a given range — allocate a location when creating a file
- largest_free_block_query — full-table scan for the largest free block — creating large files, merging reclaim
- largest_n_free_blocks_query — maintain Top-N for the N largest free blocks — batch creation, layout planning
- largest_free_block_count_query — count free blocks — capacity assessment, pre-defragmentation check
- largest_free_block_query_in_range — largest free block within a range — sharded parallel allocation
- smallest_free_block_query_in_range — smallest free block within a range — nearest small-file allocation
- largest_n_free_blocks_query_in_range — Top-N free blocks within a range — in-range batch allocation
- fragment_count_statistics_in_range — count fragments within a range — defragmentation decisions
New design (not in the repo, design supplement): segmented-bidirectional (from a given center: right N → left N → alternate segments, segment length N configurable), start-bidirectional-segmented (clamp inward in N-entry alternating segments until they meet) — convergence optimizations for nearest and huge-table scenarios.

10. EXECUTORS

- Entry: at boot, count CPUs → allocate threads → map one-to-one to CPUs → run that many executors;
- Duties: the only component that can read the config (direct read/write per config); the only channel isolating system files from applications; sound output and network packet distribution (executor takes the current packet → app decides ownership) are the executor's job;
- Grouping idea: multiple executors work in parallel groups, each group owns a block (e.g. a group opens a new fixed table when it has stored a certain number of files);
- Acceleration: every instruction is known (the result path is known before execution; nothing to guess); instruction-group packing reduces jump overhead; a novice executor basically only uses if; fixed-length direct read/write, zero config parsing, relative-position search — all bare-metal acceleration;
- Hot I/O path: O(1) multiplicative addressing, application-managed contiguous layout, no search on the hot path; background/offline path: search = low-frequency maintenance.

11. WHY APPLICATIONS CANNOT DIRECTLY ACCESS THE CONFIG AREA / FILE TABLE / FRAGMENT TABLE / CONTENTION ID SLOTS
12. Metadata is the root of global correctness: if applications write tables directly, concurrent writes to the same entry by multiple apps → mutual overwrite, tearing → the whole FS corrupts;
13. Contention bits are a coordination mechanism between executors: apps do not understand the protocol; writing contention bits incorrectly (clearing someone else's bit) → contention correctness collapses;
14. A wrong config change destroys everything: any one wrong entry (table offsets, entry widths, wait time N) immediately misaligns or breaks the system;
15. Address & alignment safety: apps pass only entry numbers and never touch byte addresses; illegal addresses and misalignment bugs are eliminated at the source (#18 semantics);
16. System-file / application isolation: the executor is the only channel; apps cannot touch system files or other apps' data areas;
17. Protocol transparent to apps: concurrency/wait/retry/clear are all encapsulated inside executors; no matter how an app writes, it cannot break concurrency;
18. Rebuild reliability: crash recovery relies on rebuild — only when metadata is written uniformly by executors can rebuild distinguish real state from garbage data.
19. SCHEDULING MODEL
Mechanism:

- CPU ↔ executor: many-to-many — one CPU can host one or more executors;
- Once a task is assigned, it runs to completion on the executor's own core — no interruption, no migration, no preemption;
- Rotation happens at the "task-acceptance eligibility" layer, not the "task timeslice" layer: after an executor runs a certain instruction count, it hands the right-to-run to the next executor;
- The next executor first checks whether its remaining performance is sufficient — if not, it keeps asking the next one until it finds one that can take the task;
- Once assigned: that executor writes its performance into the memory config (state persistence);
- Scheduling is done uniformly by executors; applications participate zero.

Worked example:

Code: Select all

2 cores C0, C1; C0 hosts E1, E2; C1 hosts E3; rotation E1→E2→E3→E1→…; tasks A, B, C queued

1. E1 runs N instructions → hands the right to E2; E2 sees itself idle → takes task A → pinned on C0 (no migration); writes its performance to config
2. E2 runs N instructions → hands to E3; E3 sees itself idle → takes task B → pinned on C1
3. E3 runs N → hands back to E1; E1 is running A → insufficient → asks E2 (also running) → asks E3 (running B) → no one idle → C waits
4. E1 finishes A and frees up → next round its remaining performance suffices → takes task C → pinned on C0
Performance characteristics: scheduling overhead is O(1) constant (count instructions + handover + check + write config; lock-free); zero context switches, perfect cache affinity; no preemption → head-of-line blocking under adversarial and uncontrollable load (does not hold in controllable-input scenarios); overhead does not scale with core/thread count — traditional runqueue/balancer/atomic tax grows with scale, QwQ's is constant.
5. APPLICATION STATE IN THE SYSTEM (WHY IT IS DESIGNED THIS WAY)
Boot chain: power on → QwQ-FS memory version (QwQ-mm) runs → executors run → desktop → applications start.
When an application starts:
6. The system tells the app its entry storage position — the app only needs to know where it starts, not the global layout;
7. The app does relative-position search from its entry — using any of the search modules to locate its own data from the entry point;
8. The executor uses built-in entry swapping to arrange the app's files into an ideal position (contiguous state): data laid out contiguously, hot I/O path is O(1) multiplicative addressing.
Why this design:
9. Global layout is transparent to apps: apps only know "entry + relative search"; layout knowledge is outsourced to executors;
10. Relative search keeps huge metadata usable: location is constant-cost (input number → multiplicative addressing), no matter how large the table; the 96 search methods cover different scenarios;
11. Contiguous state is the premise of the hot path: contiguous data → hot I/O O(1), few jumps on read; search is low-frequency maintenance and does not run on the hot path — "search has overhead" does not hold in the steady state;
12. Another outsourcing chain: the kernel only provides "locating primitives + entry swapping"; ease-of-use is composed by application layers themselves — the kernel stays minimally complete.
13. TRADE-OFFS AND EXTENSIONS
General principle: extensions are done by executors, not by config; outsource whenever possible; the kernel stays minimally complete. Every extension first asks "why is it needed" — most traditional features have cheaper alternatives in this model.
14. log — not built-in; has a built-in equivalent. The contention bit (occupancy marker) is itself a resident intent record in storage; on power loss an ID that had no time to be cleared is exactly the crash scene; combined with the "reserve first → write content → clear later" order + rebuild, every power-loss intermediate state is discoverable and recoverable — the problem log solves (undiscoverable half-overwrite) is eliminated by ordering. File creation flow: (1) contention-bit acquisition → fragment/file table entries marked occupied; (2) then write the file name; (3) only after the content address is written into the file table is the fragment table cleared — the old fragment is released last; data is never half-overwritten. Writing a dedicated log is over-engineering (write amplification in exchange for replay; rebuild is cheaper).
15. backup/snapshot — not built-in. The backup mechanism itself is high-difficulty; QwQ-FS doubles as a partition table, so mounting another file system on top of it gives backup/snapshot; not built-in → smaller system → fewer bugs.
16. quotas — not implemented. Whoever needs quotas runs a virtual file system inside an application on QwQ-FS (one nested layer), and the virtual layer manages quotas — same for multi-user (each user runs their own virtual machine for isolation).
17. hard links / symbolic links — not implemented. The access model is position addressing (entry + relative-position search), not name references; finding a file is direct relative-position search; links add a detour with zero benefit — useless here.
18. compression / encryption — not provided. The design starting point is extreme performance; no space was reserved; in an environment with abundant space but weak CPUs, trading CPU for space/security is a bad deal — it runs against the performance-extreme direction; when encryption is needed, mount another file system on QwQ-FS (virtual layer) and let that FS handle it.
19. permissions / timestamps / SHA — extension implementation (off by default). Permissions are basically unused on a single-user system (multi-user runs isolated VMs); when needed, plan a fixed-width prefix area inside the file name (path field) for permission/SHA/timestamp — the path field is fixed-length, the prefix occupies fixed width, fixed-length entries are not broken; executors validate permissions before file operations.
20. append — extension implementation (chained fragments). The default tail-record append has trampling + non-reclaim-on-delete costs, so it is not built-in; when needed, use chained fragments — the file table entry points to the first fragment, each fragment header has a fixed area (width = configured start+size width) recording the next fragment's address+size; appending does not touch existing data.
21. tree directories — not a kernel extension. Implement /a/b/c.txt in an upper layer over the core; the kernel needs no change — ease-of-use is outsourced wholesale to the application layer.

Traditional features comparison:

- create/delete/read/modify/rename — native (modular)
- free-space management — native (fragment table + 8 queries)
- defragmentation — native
- metadata — native (fragment table + file table)
- bad-block detection — native
- search — native (96 kinds)
- partition table — native (FS doubles as it)
- concurrency safety — native (contention-bit protocol, lock-free)
- log/recovery — built-in equivalent (contention bit + ordering + rebuild)
- permissions/timestamps/SHA — extension (file-name prefix area)
- directories — upper layer over the core
- append/snapshot/backup/quota/encryption — extension or mount another FS
- hard/symbolic links — position addressing makes them useless
- compression — performance-extreme; not done

15. CONCLUSION
Parallelism is the steady state, not the exception — the mainstream protects parallelism as an exception; QwQ designs parallelism as the norm, so its cost structure is pressed to constant in the steady state. The hardware direction of scheduling and concurrency (custom CPU) is already in the design; details in a later post.

SIMILAR PROCESSORS (DESIGN REFERENCES)

- Graphcore IPU (Colossus): 1472 cores × 6 threads per core = 7000+ independent instruction streams, non-lockstep (each thread is a truly independent program; no grouped lockstep execution, no merged memory access) — structurally isomorphic to the custom CPU's "many independent lines"; difference: it has hardware thread scheduling + a BSP synchronization barrier (synchronize → exchange → compute again), whereas QwQ has no synchronization and no locks; the company raised over $700M and was once valued at $2.8B, yet never became mainstream — spent a lot of money without a suitable protocol.
- Intel Xeon Phi (Knights Landing): 72 x86 cores + 512-bit SIMD, a form between CPU and GPU; difference: the cores are still traditional x86 cores (register files + atomic instructions + cache coherence), not "minimal units, no registers"; retired — Intel's money-burning many-core project, whose programming protocol never became mainstream.
- GreenArrays GA144: 144 independent nodes, stack-based (no register file), no clock synchronization, no shared memory, each node's program ≤256 instructions — in hardware form the closest to "minimal units, no registers, no locks"; difference: node program space is tiny and the scale is only 144 lines, without the "many lines" big parallelism, and it does not come with a GPU-like form.

[Note] Entry/field widths are multiples of the CPU width (8/16/32/64 bits): machine-oriented direct read/write without mask-and-split — lower code complexity; native-width single read/write — higher performance. The storage version additionally needs alignment with the storage granularity (entry 1 KiB, 4 entries aligned to a 4 KiB block).
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

Addendum (supplementary design rules):
Every entry in the config region is exactly the maximum native word width of the CPU, not a multiple.
This keeps one config entry inside a single hardware access unit to prevent torn writes. This design does NOT depend on hardware atomic instructions.
Values exceeding this width are stored in consecutive separate entries, instead of expanding one single entry.
Other regular entries follow the rule above: widths as multiples of CPU word width and aligned to storage granularity.

Additionally, each contention mask slot also uses the CPU maximum native word width.
If concurrent threads outnumber the bits in one slot, we use multi-round contention, rather than widening a single mask slot.

All table entries are self-contained, with no embedded cross-block pointers or forward references.
Cross-table references use standalone entry IDs only. Modifications to one entry will not trigger chained updates to other metadata.

This filesystem does not use WAL or transaction log.
Any modification is localized to a single slot, with no cross-location chained updates. Corrupted states are limited to individual slots and recovered by scanning & reconstruction; there is no risk of index fracture.
nullplan
Member
Member
Posts: 2055
Joined: Wed Aug 30, 2017 8:24 am

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

Post by nullplan »

I'm sorry, but what is this? Seems you are describing a file system. File systems are kept on storage devices, and storage devices are only accessed using block commands. The blocks used to be 1/2 kB in size and these days are often 4KB in size. There is no way to only write a single bit. All operating systems that don't want to go crazy implement a page cache per storage device, serializing all reads and writes on that layer so that not multiple copies of the same block exist in memory. That would be bad!

Even if you were talking about in-memory structures, you are describing the impossible.
mochangyan wrote: ↑Sun Nov 01, 2026 7:13 am overwriting writes are forbidden — non-overwrite write is a principle;
There is no such thing as a non-overwrite write. The smallest store a modern CPU has is a cache line. A CPU will always fetch a cache line, modify it, and eventually write it back. And even within a cache line, a CPU's smallest store size is a byte.

What you are ultimately proposing is a system in which all threads write their ID into a shared memory variable, and then they sleep and read the variable again to see if the write took. This system has the problem that no thread can be certain that no other thread is currently between "saw free lock" and "wrote thread ID". That's only possible if you can give a maximum time between those two points, but in the presence of interrupts, it's impossible to tell. You are also assuming that there's a maximum number of instructions until a write has progressed to the cache, but that is also not a necessity, nor is the existence of a cache coherency protocol. The effects of memory ordering are also entirely omitted from view.

Also, if you write any of this in C (or a language ultimately based on C, such as Rust), then accessing the same storage location from at least two threads, at least one of which is writing, and not all of which are atomic, is a data race. Data races are undefined behavior (as in, your code can fault there).

In conclusion:
mochangyan wrote: ↑Sun Nov 01, 2026 7:13 am Parallelism is the steady state, not the exception — the mainstream protects parallelism as an exception;
Absolutely not. The mainstream requires that you properly think about how you organize your data structure if you want parallelism that isn't a big conga line of threads blocked at all the same locks all the time. But this is very different from your idea that side-stepping atomic operations is going to do a thing.
Carpe diem!
Octocontrabass
Member
Member
Posts: 6286
Joined: Mon Mar 25, 2013 7:01 pm

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

Post by Octocontrabass »

mochangyan wrote: ↑Sun Nov 01, 2026 7:13 amPlease examine it from a falsification angle
The smallest unit of data an x86 CPU can address is one byte. If you want to set one bit in a byte, you must write to the entire byte, replacing the previous values of all eight bits in that byte. If you want to preserve the previous values of the other bits in that byte while other CPUs might also be updating those bits, you must use an atomic read-modify-write operation.

There you go, I have falsified all of your claims.
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

Thank you for your feedback, let me clarify the layout, full contention example and my original pseudocode for reference.

Each file table entry is a fixed-size record: filename field, size, start offset, and a valid ID at the end. This ID only marks whether this file entry is valid.

The ID contention region for allocation is a separate independent array, outside the file table.
It is made of many whole-word slots, NOT one shared bitmask word with multiple bits for different threads.
Threads scan to pick one idle slot first, then run the below protocol on that single selected slot.
Once claimed successfully, this slot is exclusive to that thread, other threads will skip it.

This contention slot is only for allocation arbitration. It is NOT the ID field inside the file table entry.
After acquiring the contention slot, the thread can then write its formal file table entry into the file table area.

Full contention example with state changes:
Initial contention slot state: [0, 0, 0, 0]
Step 1: Thread A scans the array. Slot 0 is 0. Thread A selects slot 0 and runs the protocol on slot 0.
Current contention state: [1, 0, 0, 0]
Step 2: Thread B scans the array. Slot 0 is already occupied, skip it. Slot 1 is 0. Thread B selects slot1 and runs protocol on slot1.
Current contention state: [1, 1, 0, 0]
Step 3: Thread C scans the array. Slot0=1, slot1=1, skip both. Slot2 is 0. Thread C selects slot2 and runs protocol on slot2.
Current contention state: [1, 1, 1, 0]
Step 4: All three threads A/B/C now own their separate exclusive contention slots. They proceed to write their own independent file table entries.
No two threads will run this protocol on the same contention slot.

My original pseudocode for the single-slot contention protocol:
if read_storage(ID slot) == 0000: # 1 Read: write only if all zero (pre-write boolean free check)
set own bit in storage(ID slot) to 1 # 2 Write: only 1 bit, overwriting forbidden (read/write not atomic)
execute N instructions # 3 Wait: instruction count (#17), let the write settle
temp = read_storage(ID slot) # 4 Read-back: copy into a temporary memory variable
set own bit in temp to 0 # only the copy is cleared; this is NOT clearing storage
if all bits of temp are 0: # rest all zero = contention won
do your work (between step 4 and step 5)
set own bit in storage(ID slot) to 0 # 5 Clear: only your own 1 bit; never clear a whole byte
else: # not all zero = contention lost
set own bit in storage(ID slot) to 0

This protocol assumes a specific CPU that supports direct single-bit writes. It is not designed for generic x86 hardware.

This is a specialized arbitration protocol, so it is not suitable for every CPU. The core design goal of QwQ-FS is to minimize the use of complex instructions, reduce total instruction count and cut runtime overhead as much as possible for better steady-state performance.

It is worth noting that 1-bit storage access is not inherently impossible. The 8-bit minimum granularity is mostly a human convention rather than a fundamental hardware limit.
Some GPU-like architectures already use 1-bit access in their design. GPUs also support native `i1` (1-bit integer) types, though these are typically used for predicates and masking rather than general random single-bit memory writes.
I choose the 1-bit primitive for forward extensibility and future porting potential. QwQ-FS is designed to be portable and may later migrate to GPU-like processors.
The protocol avoids heavy, high-cost instructions by design. One of the goals is to offload this work onto GPU-like cores when the main CPU is saturated, if this feature is required.

People with hardware background can understand this line of reasoning, but they will not assume that arbitrary 1-bit memory access is a standard, universal feature.
If the boundaries are stated clearly in advance, it is easier for them to recognize this as a deliberate design trade-off rather than a lack of hardware knowledge.

About 1-bit write:
Direct single-bit write instructions are not universal.
This "1-bit write" capability only exists on some specific target CPUs, it is NOT available on general x86.
If this contention protocol is ported to standard x86, we have to use 8 bits (one byte) as one contention ID, because x86's minimum accessible granularity is a byte.
For regular x86 systems, any bit modification requires read-modify-write on the whole byte or word.

About the 17-instruction delay:
This fixed N=17 instruction pause is not for busy-waiting another thread.
It compensates for write propagation latency on simple memory buses or uncached bare-metal environments.
Without this delay, a subsequent read-back might read stale old value before the write has fully reached the storage medium.
The count 17 is a tuned constant for the target simple bus timing, not a magic general-purpose value.

Parallel work operates on isolated slots, so there is no concurrent modification to the same shared word. That is why atomic RMW is not required here.

Also, "non-overwrite write" is our protocol rule: once a file table entry is marked valid (its ID is written), we never overwrite it in-place. New data goes to free unused entries.

Examples of supported CPUs and GPUs:
- AVR (ATmega series): SBI / CBI instructions to set or clear individual bits in registers
- 8-bit PIC microcontrollers: native bit manipulation instructions for individual bits
- ARM Cortex‑M3 / M4 with Bit-Band: bit-band alias mapping allows independent bit addressing and writes
- Custom RISC-V cores with custom bit-manipulation extensions
- Some GPU architectures: support i1 predicate types, suitable for offloading marking logic even if general random bit write is not exposed for memory

These architectures can natively match the single-bit write semantics in this pseudocode. x86 and baseline standard RISC-V do not belong to this category.
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

These two points are preconditions and conventions for running this protocol, not flaws inside the protocol itself.
The protocol only defines the contention and collision-check logic. It assumes the runtime environment follows these rules: each executor has a unique ID mapped to an exclusive bit, and the hardware supports independent single-bit writes without altering other bits within the slot.
The protocol logic itself holds valid as long as those conventions are respected. It is not designed to run on hardware that requires read-modify-write operations to update individual bits.
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

One extra note: each executor can run only one store operation at a time. It cannot issue many consecutive store instructions in this contention sequence.
Octocontrabass
Member
Member
Posts: 6286
Joined: Mon Mar 25, 2013 7:01 pm

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

Post by Octocontrabass »

mochangyan wrote: ↑Sun Nov 01, 2026 9:58 pmThis protocol assumes a specific CPU that supports direct single-bit writes. It is not designed for generic x86 hardware.
If your protocol requires a specific non-x86 CPU, why did you spend an entire section of your first post explaining how to use your protocol on generic x86 hardware?

If your protocol requires a specific non-x86 CPU, why didn't you mention that anywhere in your first post?
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

Good question. I have two separate implementations.
The native ideal version relies on hardware direct single-bit write for the contention slot.
The x86 variant I described earlier is an emulated fallback implementation, which simulates this behaviour on x86 with extra rules, and it has different constraints.
I should have made this distinction clearer in my original post.
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

Also, regarding the halt/interrupt question above:
Clarification: When the halt instruction runs, the executor stops fetching new instructions. It waits for ongoing memory and store operations to complete. Custom halt-wait instructions are allowed for custom executor implementations, before the executor halts.
Even an abrupt forced halt will not cause corruption. The slot for store ID competition is marked as occupied. If it was marked occupied, previous operations can be resumed. If it was unoccupied, we only need to clean up the competition slot, empty size, location entries and path entries. Since one executor maps to one ID, we can locate matching ID records to resume interrupted work or perform cleanup.
mochangyan
Posts: 8
Joined: Sat Oct 31, 2026 3:27 am
Libera.chat IRC: muchangyan

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

Post by mochangyan »

QwQ-FS Addendum: Application Data Management

1. Data classification inside an application (4 types)

- Application entry — just an entry; the location anchor
- Static data — code + static resources (textures/audio); rarely grows
- Dynamic data — dynamic resources + code; may grow slightly (add entries)
- Application user data — user data (game saves / edited images); dynamic growth, plain storage

2. Placement strategies (6)

1. Local-table arrangement — read the local table at startup, then arrange (entry swapping)
2. Network-table swapping — fetch the table from the network at startup, then do entry swapping
3. Runtime-ordered layout — built-in relative position; re-arranged at runtime (details in section 8 )
4. Virtual disk — use a virtual disk to manage placement
5. Outsource to another application — hand data management to another app
6. Zero strategy — no arrangement at all (kept)

3. Hosting forms

- Real storage + app-managed — the app manages its own data and user data, appending at the tail — recommended
- Specific data to FS — some data goes through the FS channel; the boundary is decided by the app — optional
- Virtual disk — the FS doubles as a partition table, so a virtual disk is just raw storage it can parse itself — feasible, not recommended
- Per-app virtual disk / shared virtual disk — one disk per app, or one disk shared by several apps; decided by the apps — feasible, not recommended

4. Where the table lives

- FM-like apps — a local private table (FS does not parse its content)
- Other apps (games) — no local table; fetched from the network or none

5. Cross-application delivery

Getting a location: asking the system is recommended (O(1), one step); an app may also search for it itself, but that costs more (search is low-frequency, off the hot path).

1. The app obtains the other app's entry location (via the system, or by its own search)
2. Choose one way to write: hand it directly to the other app / place it in a free slot right after the other app's entry / read the other app's private table and add a new entry
3. Ownership ends up in the receiver's table

6. The file manager is an application

Difference between FM and a normal app:

- Data — normal app: resources + saves; FM: user files (FM's application user data)
- Table — normal app: none locally; FM: a local private table (FS does not parse it)
- Placement strategy — normal app: any (network table, runtime-ordered layout, etc.); FM: only local-table arrangement; cannot use runtime-ordered layout
- Role — normal app: manages its own data; FM: manages "files" — the shelter of user files
- Receiving — normal app: generally receives nothing; FM: receives deliveries from other apps (e.g., edited images)

Whether FM is built into the system is decided by the system maker; either way, it stands on an equal footing with other apps — no privilege.

7. Conclusion

Whose data it is, that app manages it; tables live locally only in the apps that need them (FM); growth is always appended at the tail; locations are recommended to be obtained via the system (self-search is allowed, at a higher cost); the medium may be real storage or a virtual disk (the FS parses it itself).

8. Runtime-ordered layout (example)

Runtime-ordered layout = the app keeps a built-in designated position for each entry (relative to its entry point), and re-arranges at runtime — each time it arranges only the single entry that is about to be used (usually only one file is input at a time).

Internal steps:

1. Code inputs an entry's relative position (its designated position relative to the entry point)
2. Bidirectional segmented search from the entry point (search outward in segments from the center)
3. After the search, judge: is this entry at its designated position?
4. If not: move it to the current position and swap the entries
5. Done — only this one is handled; once used, it is in place; other entries stay untouched and are arranged individually when they are needed next

Key property: it runs correctly even without arrangement — correctness does not depend on layout; it is an optimization that re-arranges at runtime (built-in relative position, gradual placement during execution). Recommended to be built into the executor: it is common code, reusable, saves space; apps just call it — convenient.
Octocontrabass
Member
Member
Posts: 6286
Joined: Mon Mar 25, 2013 7:01 pm

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

Post by Octocontrabass »

mochangyan wrote: ↑Sun Nov 01, 2026 10:54 pmThe native ideal version relies on hardware direct single-bit write for the contention slot.
It also relies on an atomic read instruction to read all bits of that bit field at the same time. So, even on your hypothetical CPU, your claim of "no atomic instructions" is false.
Post Reply