kernel/lib.rs
1#![forbid(unsafe_op_in_unsafe_fn)]
2
3pub mod btree;
4pub mod budget;
5pub mod limits;
6pub mod bulk;
7pub mod io;
8pub mod keys;
9pub mod graph;
10pub mod meta;
11pub mod page;
12pub mod pool;
13pub mod recover;
14pub mod vecquant;
15pub mod text;
16pub mod score;
17pub mod readers;
18pub mod spatial;
19pub mod geomath;
20pub mod nav;
21pub mod store;
22#[cfg(test)]
23mod test_support;
24/// Counting allocator for unit tests only.
25///
26/// `tests/codec_allocations.rs` in the root crate proves a claim about
27/// allocation by counting it rather than by reasoning about it; the kernel had
28/// no such allocator, so the same thread-local pattern is repeated here. It is
29/// `cfg(test)`: nothing that ships is wrapped, and when `TRACK` is off the
30/// wrapper is one thread-local read.
31#[cfg(test)]
32pub(crate) mod test_alloc {
33 use std::alloc::{GlobalAlloc, Layout, System};
34 use std::cell::Cell;
35 thread_local! {
36 static TRACK: Cell<bool> = const { Cell::new(false) };
37 static COUNT: Cell<usize> = const { Cell::new(0) };
38 static BYTES: Cell<usize> = const { Cell::new(0) };
39 }
40 pub struct Counting;
41 // SAFETY: every method forwards to `System` unchanged; the counters are
42 // thread-local side effects that never touch the returned pointer.
43 unsafe impl GlobalAlloc for Counting {
44 unsafe fn alloc(&self, l: Layout) -> *mut u8 {
45 note(l.size());
46 unsafe { System.alloc(l) }
47 }
48 unsafe fn dealloc(&self, p: *mut u8, l: Layout) { unsafe { System.dealloc(p, l) } }
49 unsafe fn realloc(&self, p: *mut u8, l: Layout, n: usize) -> *mut u8 {
50 note(n);
51 unsafe { System.realloc(p, l, n) }
52 }
53 unsafe fn alloc_zeroed(&self, l: Layout) -> *mut u8 {
54 note(l.size());
55 unsafe { System.alloc_zeroed(l) }
56 }
57 }
58 fn note(size: usize) {
59 TRACK.try_with(|t| {
60 if t.get() {
61 COUNT.with(|c| c.set(c.get() + 1));
62 BYTES.with(|b| b.set(b.get() + size));
63 }
64 }).ok();
65 }
66 #[global_allocator]
67 static ALLOC: Counting = Counting;
68
69 /// Run `f` with allocation counting on. Returns (value, allocations, bytes).
70 pub fn measured<T>(f: impl FnOnce() -> T) -> (T, usize, usize) {
71 COUNT.with(|c| c.set(0));
72 BYTES.with(|b| b.set(0));
73 TRACK.with(|t| t.set(true));
74 let v = f();
75 TRACK.with(|t| t.set(false));
76 (v, COUNT.with(Cell::get), BYTES.with(Cell::get))
77 }
78}
79pub mod wal;
80#[doc(hidden)]
81pub mod write_stats;
82/// Structural verification. `verify_published_tree` is public so a live
83/// database's shape can be proven after a graft; the rest stays internal.
84pub mod verify;
85#[cfg(feature = "write-trace")]
86pub mod write_trace;
87
88#[derive(Debug)]
89pub enum Error {
90 Io(std::io::Error),
91 /// A page failed verification. Carries the page number that was asked for.
92 Corrupt { page_no: u32, why: &'static str },
93 /// A structural limit was hit, e.g. a record too large for a page.
94 TooLarge,
95 /// A mutation was attempted on a snapshot reader (2f). Readers serve
96 /// the state of one published generation; every write path refuses.
97 ReadOnly,
98 /// Another live writer already owns the data file. The lock is advisory
99 /// and attached to that writer's file descriptor, so dropping the handle
100 /// or process exit releases it; snapshot readers do not take this lock.
101 WriterLocked,
102 /// The write-ahead log holds something at `offset` that cannot be
103 /// accepted AND cannot be treated as the log simply ending there --
104 /// `Wal::scan` classified it `Stop::Damaged` (see that type). `open`
105 /// refuses rather than truncating past it, because the bytes behind it
106 /// may be committed frames and a reader that is unsure has no business
107 /// deleting them (Law 3).
108 ///
109 /// NOT terminal, and that is half the design rather than a detail (Law
110 /// 5): a refusal with no way to clear it is as unrecoverable as a
111 /// deletion. `recover()` is the way through -- it copies and hashes the
112 /// whole log as `wal.corrupt.N`, resynchronises later committed regions
113 /// into a verified live log, and the store opens. A previous round shipped this
114 /// refusal without that path and turned 29 of 400 single-bit flips into
115 /// stores that would never open again.
116 ///
117 /// Deliberately not `Corrupt`: a WAL frame has no page number, and
118 /// reusing `page_no` for a byte offset would mislabel what failed.
119 CorruptWal { offset: u64, why: &'static str },
120 /// A `Store` whose logged write or checkpoint failed partway through
121 /// refuses every further write. A tree error may escape after a leaf was
122 /// compacted or split but before its replacement or parent was installed;
123 /// `flush_all` clears each frame's dirty bit
124 /// BEFORE its barrier is issued, so a barrier that fails does not mean
125 /// the writes never happened -- those bytes can already be sitting in
126 /// the OS page cache, forgotten by our own bookkeeping, and reach the
127 /// disk anyway via later, unrelated writeback with no further fsync from
128 /// us. The store therefore cannot say whether its last checkpoint took
129 /// effect, and the pages it believes clean may not be durable.
130 ///
131 /// What makes continuing actively dangerous rather than merely
132 /// uncertain is `checkpoint`'s last step: `Wal::rotate` DELETES the log.
133 /// A second checkpoint would flush nothing (those frames are marked
134 /// clean), issue a barrier that may well return `Ok` this time -- a
135 /// failed `fsync` is reported once and the kernel then forgets it -- and
136 /// go on to discard the one remaining copy of records whose pages never
137 /// reached the medium. That is Law 3 exactly: something that can be
138 /// wrong about what exists, deleting. So every writer refuses:
139 /// `put`, `delete`, `commit`, `checkpoint` and `bulk_load` alike.
140 ///
141 /// NOT a dead end (Law 5). The flag is per-instance and never persisted:
142 /// dropping the `Store` and calling `Store::open` again clears it, and
143 /// that reopen is not a way of ignoring the problem -- it re-reads
144 /// `Meta` from disk and replays the log, which is what re-establishes
145 /// what is actually durable. `recover()` is available for the case where
146 /// the reopen itself finds damage.
147 StorePoisoned,
148 /// A memory reservation could not be granted.
149 OutOfBudget,
150 /// A configured resource ceiling refused work. A partially changed writer
151 /// must be dropped and reopened; committed metadata and readers survive.
152 ResourceLimit(&'static str),
153 /// A bulk load's input contained two entries with the same key. Not
154 /// `Corrupt` -- page 0 is the superblock, and naming it for a condition
155 /// that has nothing to do with a page reads as structural damage in a
156 /// log when it is really just an input the caller must deduplicate.
157 DuplicateKey,
158 /// A packed range can only be grafted where the live tree has no key.
159 /// Overwriting through this path would bypass ordinary update semantics.
160 RangeNotEmpty,
161 /// The file is not a sekejap disk format v2 file: an intact page claims
162 /// the disk-format version in `found` at bytes 18-19 and this build
163 /// reads 2 and nothing else (`page::FORMAT_VERSION`,
164 /// docs/core/FORMAT_V2.md).
165 ///
166 /// Raised before any byte of the source is changed, and never converted:
167 /// there is no v1, no e1 file and no silent conversion, so the only
168 /// honest answer is to name the number the file carries and stop. Zero
169 /// is what an e4 pre-release file carries.
170 UnsupportedFormat { found: u16 },
171}
172
173impl From<std::io::Error> for Error {
174 fn from(e: std::io::Error) -> Self { Error::Io(e) }
175}
176
177/// Every variant says what failed AND where the way out is, because these
178/// strings are what a wrapper user sees: a refusal with no route forward
179/// reads as a dead end (Law 5), and the `Display` text is often the only
180/// part of that law a caller ever meets.
181impl std::fmt::Display for Error {
182 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
183 match self {
184 Error::Io(e) => write!(f, "io error: {e}"),
185 Error::Corrupt { page_no, why } =>
186 write!(f, "page {page_no} failed verification ({why}); recover() copies the \
187 damage aside and reopens what is readable"),
188 Error::TooLarge => write!(f, "record too large for a page"),
189 Error::ReadOnly => write!(f, "this handle is a snapshot reader; snapshot readers \
190 serve one published generation and never write"),
191 Error::WriterLocked => write!(f, "database already has an active writer; the \
192 exclusive writer lock is held (close that writer or \
193 wait for its process to exit; read-only snapshots \
194 remain available)"),
195 Error::CorruptWal { offset, why } =>
196 write!(f, "write-ahead log unusable at offset {offset} ({why}); recover() \
197 preserves the whole log as wal.corrupt.N and opens the readable \
198 prefix"),
199 Error::StorePoisoned =>
200 write!(f, "a logged write or checkpoint failed partway, so this handle cannot say what is \
201 durable and refuses every further write; drop it and open again \
202 to re-read the meta and replay the log"),
203 Error::OutOfBudget => write!(f, "memory reservation refused: cache budget exhausted"),
204 Error::ResourceLimit(why) => write!(f, "resource limit: {why}; reduce the transaction, release old snapshots, or export to a larger store"),
205 Error::DuplicateKey => write!(f, "bulk load input contained a duplicate key"),
206 Error::RangeNotEmpty => write!(f, "packed range overlaps keys already present in the live tree"),
207 // The refusal sentence, written ONCE. Everything above this
208 // layer quotes it rather than composing its own.
209 Error::UnsupportedFormat { found } =>
210 write!(f, "sekejap disk format {found}; this build reads v2"),
211 }
212 }
213}
214
215impl std::error::Error for Error {
216 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
217 match self { Error::Io(e) => Some(e), _ => None }
218 }
219}
220
221pub type Result<T> = std::result::Result<T, Error>;
222
223/// The sekejap disk format this build reads and writes: 2. Defined in
224/// [`page`] beside the header field it is stamped into, and re-exported here
225/// so a caller names `kernel::FORMAT_VERSION` rather than a page-module path.
226pub use page::FORMAT_VERSION;
227
228/// The gate's edge formula, shared so e3 and the SQLite harness traverse the
229/// IDENTICAL logical graph: per src, 2 near edges (locality) + 2 far (cross).
230pub fn bench_edges(src: u64, n: u64) -> [(u64, u64); 4] {
231 let far1 = 1 + (src.wrapping_mul(2_654_435_761)) % n;
232 let far2 = 1 + (src.wrapping_mul(0x9E37_79B9_7F4A_7C15) >> 1) % n;
233 // A distinct type per slot makes (src,ty,dst) unique by construction --
234 // far1 can equal far2 and the keys still cannot collide.
235 [
236 (1, 1 + src % n), // src+1 wrap
237 (2, 1 + (src + 7) % n),
238 (3, far1),
239 (4, far2),
240 ]
241}