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: 2
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: 2
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!
Post Reply