sigilOS needed a storage engine. Not SQLite — that's C, and sigilOS has no C. Not a key-value store bolted on from outside — that would require trusting a runtime that isn't cc0. So we built one: SigDB, a page-managed B-tree with MVCC and write-ahead logging, written in Sigil, that never exposes raw database state to EL0 processes.
The design constraints
Every design decision in SigDB follows from two constraints:
- Crash safety — the database must survive a power cut without corruption. A storage engine that can silently lose data on any unexpected restart is not STABLE, and STABLE is one of the Four Pillars.
- Capability isolation — an EL0 process must never hold a raw pointer to database memory. On sigilOS, this is not optional: the capability model applies to storage the same way it applies to files, network sockets, and framebuffers.
Page management
SigDB works in 4KB pages, with a 32-page bitmap free-list stored in the database header (freemap). sigdb_page_alloc() scans the bitmap for the first free bit and returns the page number; sigdb_page_free() clears the bit. No external allocator is needed — the free-list is part of the database file itself.
The B-tree leaf node stores sorted Int-keyed entries with K_MAX=101 entries per node. Lookup is a linear scan (the node is small enough that binary search isn't worth the complexity in cc0); insert maintains sorted order by shifting existing entries right.
MVCC — multi-version concurrency control
Each entry in a SigDB leaf node holds two versions: cur (the current value) and prev (the previous value). Each version carries an epoch number. The visibility rule at read time is:
- If
cur_epoch ≤ snap→ the current value is visible - If
prev_epoch > 0andprev_epoch ≤ snap→ the previous value is visible
A transaction begins by calling sigdb_txn_begin(), which returns a snapshot epoch. That epoch pins the view of the database at that moment. A concurrent writer can commit a new version of any key without disturbing the reader's snapshot — the reader always sees what was true at its snapshot epoch, never partial writes from a concurrent transaction.
This is not a full serializable MVCC implementation — it's a two-version design intentionally sized for sigilOS's workloads (config stores, tag indexes, session state). Two versions is enough to give read-committed isolation without the storage overhead of a full version chain.
WAL — write-ahead logging
Before any mutation, SigDB appends a WAL record describing what's about to change. The record is 16 bytes: page_no + entry_idx + field_type + old_value. A full update writes 4 records — one each for cur_val, cur_epoch, prev_val, prev_epoch. A new-key insert writes 1 record for nkeys.
On commit, the WAL is reset (cleared). On crash before commit, sigdb_wal_undo() walks the WAL in reverse and restores each field to its pre-mutation value. The database is back to its pre-transaction state. This is crash-safe by construction: the WAL is always written before the data page, and the data page is never touched if the WAL write fails.
Cap<DBTxn> — the broker layer
The broker layer in sigdb/cap_txn.sg is what makes SigDB consistent with the sigilOS capability model. The public API for EL0 processes is:
| Function | What EL0 sees | What the broker holds |
|---|---|---|
sigdb_cap_open(base, mode) | Opaque slot handle (0–3) | db_base, mode, snapshot_epoch |
sigdb_cap_txn_begin(slot) | — | epoch snapshot |
sigdb_cap_get(slot, key) | Value | B-tree lookup against snapshot |
sigdb_cap_put(slot, key, val) | Status | WAL + B-tree mutation (mode==RW only) |
sigdb_cap_del(slot, key) | Status | WAL + physical compaction (mode==RW only) |
sigdb_cap_txn_commit(slot) | — | WAL reset |
sigdb_cap_txn_rollback(slot) | — | WAL undo + epoch restore |
The slot handle is an integer. It encodes nothing about db_base, mode, or epoch — the broker owns those. An EL0 process with mode RO=1 that calls sigdb_cap_put gets a rejection before any page is touched. A process in one session slot cannot access another's database — there is no way to forge a slot handle that points to a different database, because the broker never exposes the mapping.
Test coverage
The storage engine test (sigdb/store_test.sg) verifies six properties, reported as a single serial string:
| Character | Property |
|---|---|
F | Format + open (header magic, freemap init) |
I | Insert (key insertion, sorted order) |
L | Lookup (key retrieval by exact match) |
W | WAL integrity (pre-mutation records written) |
M | MVCC isolation (concurrent snapshot visibility) |
A | Alloc/free round-trip (page bitmap coherence) |
The broker test (cap_txn_test.sg) verifies: open RW, put, commit, get, open RO, SECURE put-rejection on RO handle, rollback restores the pre-put value. String: OPCGRSKV. Both tests pass on arm_emit and cc0. MANIFEST: 289 entries at broker merge, 305 by NFS3.
What it enables
SigDB is the backend required by the SQL planner (planned for 1.3). More immediately, it's available now as a native structured store for any system component that needs durable key-value storage with isolation — session state, tag metadata, application preferences — without importing a C library or trusting an external process. Every write is cap-scoped. Every transaction is either committed or fully rolled back. The Pi 3 floor works: no runtime dependency, no GC, cc0-compiled.