nx_kv_store.nx source
↩ module page · 349 lines · 11842 B
1// nx_kv_store.nx -- Provides an append-only key-value store with linear-scan index for session and config persistence.
2const NXKV_MAGIC_1099511628211: i64 = 1099511628211
3// nx_kv_store.nx -- append-only key-value store with linear-scan index.
4//
5// Foundation for sessions / content / config persistence. v0 is
6// in-memory only with append-only record format; future v1 wraps a
7// file fd for durable persistence.
8//
9// Per cardinal user-owns-every-bit:
10// - Caller provides the backing buffer (data_buf, data_cap)
11// - Caller provides the index buffer (index_buf, index_cap)
12// - Substrate never auto-allocates; never grows past caller's cap
13// - OOM_DATA / OOM_INDEX verdicts when caps exceeded
14//
15// Per cardinal feedback-additive-only-data:
16// - Updates write a NEW record; old records are LATENT history
17// - Reads use the most-recent matching key
18// - No delete (future: delete writes a tombstone)
19// - Replay rebuilds the index by walking the data buffer
20//
21// Record format (big-endian for portability):
22// [4 bytes: key_len]
23// [key_len bytes: key]
24// [4 bytes: value_len]
25// [value_len bytes: value]
26//
27// Index entry: 16 bytes
28// [8 bytes: key_hash (FNV-1a 64)]
29// [8 bytes: record_offset (i64 offset into data_buf)]
30//
31// Linear-scan lookup is O(n_entries) per get. For typical session
32// workloads (100-1000 active sessions) this is < 16 KB of index
33// scan per op -- trivial. Future v2 swaps in a hash table index
34// (composes nx_map once nx_map is refactored syscall-free).
35//
36// nx_capability_claims:
37// needs: [sealed_enum, byte_ops, fnv1a_hash]
38// provides: [append_only_kv_store, opaque_session_value_store,
39// additive_history_preservation]
40// safety: [no_unchecked_deref, no_floating_point, no_syscall,
41// bounded_iteration, cap_enforced, additive_only]
42// verdict: [sealed_enum_6_state]
43// license: ORIGINAL
44// kind: racing_crew_specialist
45// layer: L3 (algorithm: KV state machine)
46
47// ---- Sealed enum: verdict ----------------------------------------
48
49const NXKV_OK: i64 = 0
50const NXKV_NOT_FOUND: i64 = 1
51const NXKV_OOM_DATA: i64 = 2
52const NXKV_OOM_INDEX: i64 = 3
53const NXKV_BAD_RECORD: i64 = 4
54const NXKV_BAD_ARG: i64 = 5
55const NXKV_VERDICT_N: i64 = 6
56
57func nxkv_verdict_is_valid(v: i64) -> i64 {
58 if v < 0 { return 0 }
59 if v >= NXKV_VERDICT_N { return 0 }
60 return 1
61}
62
63func nxkv_verdict_name(v: i64) -> *u8 {
64 if v == NXKV_OK { return "OK" as *u8 }
65 if v == NXKV_NOT_FOUND { return "NOT_FOUND" as *u8 }
66 if v == NXKV_OOM_DATA { return "OOM_DATA" as *u8 }
67 if v == NXKV_OOM_INDEX { return "OOM_INDEX" as *u8 }
68 if v == NXKV_BAD_RECORD { return "BAD_RECORD" as *u8 }
69 if v == NXKV_BAD_ARG { return "BAD_ARG" as *u8 }
70 return "INVALID" as *u8
71}
72
73// ---- KvStore struct ----------------------------------------------
74
75struct NxKvStore {
76 // Data buffer: append-only records (caller-owned).
77 data_buf: *u8,
78 data_cap: i64,
79 data_off: i64, // next-byte-to-write
80
81 // Index buffer: 16-byte entries (hash + record_offset), caller-owned.
82 index_buf: *u8,
83 index_cap: i64,
84 n_entries: i64,
85}
86
87const NX_KV_STORE_BYTES: i64 = 48 // 6 i64 fields
88
89// ---- Init --------------------------------------------------------
90//
91// Caller passes empty (or pre-populated for replay) buffers.
92
93func nx_kv_store_init(
94 kv: *NxKvStore,
95 data_buf: *u8, data_cap: i64,
96 index_buf: *u8, index_cap: i64) -> i64 {
97 if kv == (0 as *NxKvStore) { return NXKV_BAD_ARG }
98 if data_buf == (0 as *u8) { return NXKV_BAD_ARG }
99 if index_buf == (0 as *u8) { return NXKV_BAD_ARG }
100 if data_cap <= 0 { return NXKV_BAD_ARG }
101 if index_cap < 16 { return NXKV_BAD_ARG }
102 kv.data_buf = data_buf
103 kv.data_cap = data_cap
104 kv.data_off = 0
105 kv.index_buf = index_buf
106 kv.index_cap = index_cap
107 kv.n_entries = 0
108 return NXKV_OK
109}
110
111// ---- FNV-1a 64-bit hash for keys --------------------------------
112
113func nxkv_fnv1a_64(bytes: *u8, n: i64) -> i64 {
114 var h: i64 = 0xcbf29ce484222325
115 let prime: i64 = NXKV_MAGIC_1099511628211
116 var i: i64 = 0
117 while i < n {
118 h = h ^ (bytes[i] as i64)
119 h = h * prime
120 i = i + 1
121 }
122 return h
123}
124
125// ---- Big-endian u32 read/write helpers ---------------------------
126
127func nxkv_put_u32_be(buf: *u8, off: i64, v: i64) -> i64 {
128 buf[off] = ((v >> 24) & 0xff) as u8
129 buf[off + 1] = ((v >> 16) & 0xff) as u8
130 buf[off + 2] = ((v >> 8) & 0xff) as u8
131 buf[off + 3] = (v & 0xff) as u8
132 return off + 4
133}
134
135func nxkv_get_u32_be(buf: *u8, off: i64) -> i64 {
136 let b0: i64 = buf[off] as i64
137 let b1: i64 = buf[off + 1] as i64
138 let b2: i64 = buf[off + 2] as i64
139 let b3: i64 = buf[off + 3] as i64
140 return (b0 << 24) | (b1 << 16) | (b2 << 8) | b3
141}
142
143// Big-endian i64 helpers (for index entries' record_offset)
144func nxkv_put_i64_be(buf: *u8, off: i64, v: i64) -> i64 {
145 var s: i64 = 56
146 var p: i64 = off
147 while s >= 0 {
148 buf[p] = ((v >> s) & 0xff) as u8
149 p = p + 1
150 s = s - 8
151 }
152 return p
153}
154
155func nxkv_get_i64_be(buf: *u8, off: i64) -> i64 {
156 var v: i64 = 0
157 var i: i64 = 0
158 while i < 8 {
159 v = (v << 8) | ((buf[off + i] as i64) & 0xff)
160 i = i + 1
161 }
162 return v
163}
164
165// ---- Index entry read/write -------------------------------------
166//
167// Entry layout: [8 bytes hash][8 bytes offset] = 16 bytes.
168
169func nxkv_index_entry_offset(kv: *NxKvStore, i: i64) -> i64 {
170 return i * 16
171}
172
173func nxkv_index_get_hash(kv: *NxKvStore, i: i64) -> i64 {
174 return nxkv_get_i64_be(kv.index_buf, nxkv_index_entry_offset(kv, i))
175}
176
177func nxkv_index_get_record_off(kv: *NxKvStore, i: i64) -> i64 {
178 return nxkv_get_i64_be(kv.index_buf, nxkv_index_entry_offset(kv, i) + 8)
179}
180
181func nxkv_index_set_entry(kv: *NxKvStore, i: i64,
182 hash: i64, record_off: i64) -> i64 {
183 let off: i64 = nxkv_index_entry_offset(kv, i)
184 nxkv_put_i64_be(kv.index_buf, off, hash)
185 nxkv_put_i64_be(kv.index_buf, off + 8, record_off)
186 return 0
187}
188
189// ---- Key match (verify hash + byte-compare key) -----------------
190//
191// Linear scan: for each index entry with matching hash, fetch the
192// record's key from data_buf + compare bytes. Returns the record
193// offset on match or -1.
194
195func nxkv_find_record_off(kv: *NxKvStore,
196 key: *u8, key_n: i64,
197 key_hash: i64) -> i64 {
198 var i: i64 = kv.n_entries - 1
199 // Scan backward so the MOST RECENT write wins on duplicate keys.
200 while i >= 0 {
201 if nxkv_index_get_hash(kv, i) == key_hash {
202 let rec_off: i64 = nxkv_index_get_record_off(kv, i)
203 // Verify key bytes match.
204 let rec_key_len: i64 = nxkv_get_u32_be(kv.data_buf, rec_off)
205 if rec_key_len == key_n {
206 var eq: i64 = 1
207 var j: i64 = 0
208 while j < key_n {
209 if kv.data_buf[rec_off + 4 + j] != key[j] {
210 eq = 0
211 j = key_n
212 }
213 j = j + 1
214 }
215 if eq == 1 { return rec_off }
216 }
217 }
218 i = i - 1
219 }
220 return -1
221}
222
223// ---- put ---------------------------------------------------------
224//
225// Appends a new record. Per additive-only-data: even if the key
226// exists, a new record is appended; the most-recent write wins on
227// future reads.
228
229func nx_kv_store_put(
230 kv: *NxKvStore,
231 key: *u8, key_n: i64,
232 value: *u8, value_n: i64) -> i64 {
233 if kv == (0 as *NxKvStore) { return NXKV_BAD_ARG }
234 if key == (0 as *u8) { return NXKV_BAD_ARG }
235 if value == (0 as *u8) && value_n > 0 { return NXKV_BAD_ARG }
236 if key_n <= 0 { return NXKV_BAD_ARG }
237 if value_n < 0 { return NXKV_BAD_ARG }
238
239 let need: i64 = 4 + key_n + 4 + value_n
240 if kv.data_off + need > kv.data_cap { return NXKV_OOM_DATA }
241 let next_idx: i64 = kv.n_entries
242 if (next_idx + 1) * 16 > kv.index_cap { return NXKV_OOM_INDEX }
243
244 let rec_off: i64 = kv.data_off
245 var p: i64 = rec_off
246 p = nxkv_put_u32_be(kv.data_buf, p, key_n)
247 var ki: i64 = 0
248 while ki < key_n {
249 kv.data_buf[p + ki] = key[ki]
250 ki = ki + 1
251 }
252 p = p + key_n
253 p = nxkv_put_u32_be(kv.data_buf, p, value_n)
254 var vi: i64 = 0
255 while vi < value_n {
256 kv.data_buf[p + vi] = value[vi]
257 vi = vi + 1
258 }
259 p = p + value_n
260 kv.data_off = p
261
262 let key_hash: i64 = nxkv_fnv1a_64(key, key_n)
263 nxkv_index_set_entry(kv, next_idx, key_hash, rec_off)
264 kv.n_entries = next_idx + 1
265 return NXKV_OK
266}
267
268// ---- get ---------------------------------------------------------
269//
270// Returns NXKV_OK + sets *out_value_off (within data_buf) and
271// *out_value_len. Returns NXKV_NOT_FOUND if no record matches.
272
273func nx_kv_store_get(
274 kv: *NxKvStore,
275 key: *u8, key_n: i64,
276 out_value_off: *i64, out_value_len: *i64) -> i64 {
277 if kv == (0 as *NxKvStore) { return NXKV_BAD_ARG }
278 if key == (0 as *u8) { return NXKV_BAD_ARG }
279 if out_value_off == (0 as *i64) { return NXKV_BAD_ARG }
280 if out_value_len == (0 as *i64) { return NXKV_BAD_ARG }
281 if key_n <= 0 { return NXKV_BAD_ARG }
282
283 let key_hash: i64 = nxkv_fnv1a_64(key, key_n)
284 let rec_off: i64 = nxkv_find_record_off(kv, key, key_n, key_hash)
285 if rec_off < 0 { return NXKV_NOT_FOUND }
286 let key_len: i64 = nxkv_get_u32_be(kv.data_buf, rec_off)
287 let value_len: i64 = nxkv_get_u32_be(kv.data_buf, rec_off + 4 + key_len)
288 *out_value_off = rec_off + 4 + key_len + 4
289 *out_value_len = value_len
290 return NXKV_OK
291}
292
293// ---- contains ----------------------------------------------------
294
295func nx_kv_store_contains(
296 kv: *NxKvStore, key: *u8, key_n: i64) -> i64 {
297 if kv == (0 as *NxKvStore) { return 0 }
298 if key == (0 as *u8) { return 0 }
299 if key_n <= 0 { return 0 }
300 let key_hash: i64 = nxkv_fnv1a_64(key, key_n)
301 let rec_off: i64 = nxkv_find_record_off(kv, key, key_n, key_hash)
302 if rec_off < 0 { return 0 }
303 return 1
304}
305
306// ---- len / observers ---------------------------------------------
307
308func nx_kv_store_len(kv: *NxKvStore) -> i64 {
309 if kv == (0 as *NxKvStore) { return -1 }
310 return kv.n_entries
311}
312
313func nx_kv_store_bytes_used(kv: *NxKvStore) -> i64 {
314 if kv == (0 as *NxKvStore) { return -1 }
315 return kv.data_off
316}
317
318// ---- replay ------------------------------------------------------
319//
320// Reconstruct the index from an existing data buffer. Caller has
321// populated data_buf[0..pre_loaded_n] (e.g., from a file read).
322// Substrate walks the records + rebuilds the index.
323
324func nx_kv_store_replay(kv: *NxKvStore, pre_loaded_n: i64) -> i64 {
325 if kv == (0 as *NxKvStore) { return NXKV_BAD_ARG }
326 if pre_loaded_n < 0 { return NXKV_BAD_ARG }
327 if pre_loaded_n > kv.data_cap { return NXKV_BAD_ARG }
328
329 var p: i64 = 0
330 var n_idx: i64 = 0
331 while p < pre_loaded_n {
332 if p + 4 > pre_loaded_n { return NXKV_BAD_RECORD }
333 let key_len: i64 = nxkv_get_u32_be(kv.data_buf, p)
334 if key_len <= 0 { return NXKV_BAD_RECORD }
335 if p + 4 + key_len + 4 > pre_loaded_n { return NXKV_BAD_RECORD }
336 let value_len: i64 = nxkv_get_u32_be(kv.data_buf, p + 4 + key_len)
337 if value_len < 0 { return NXKV_BAD_RECORD }
338 if p + 4 + key_len + 4 + value_len > pre_loaded_n { return NXKV_BAD_RECORD }
339 if (n_idx + 1) * 16 > kv.index_cap { return NXKV_OOM_INDEX }
340 let key_ptr: *u8 = ((kv.data_buf as i64) + p + 4) as *u8
341 let key_hash: i64 = nxkv_fnv1a_64(key_ptr, key_len)
342 nxkv_index_set_entry(kv, n_idx, key_hash, p)
343 n_idx = n_idx + 1
344 p = p + 4 + key_len + 4 + value_len
345 }
346 kv.data_off = pre_loaded_n
347 kv.n_entries = n_idx
348 return NXKV_OK
349}