code wiki / _hdl_build / nx_store_compact.nx
`nx_store_compact.nx` source

↩ module page · 398 lines · 19759 B
1// nx_store_compact.nx -- collapse a quadratic seg-store plane back to O(rows). RK013 sev9 / F829.
2//
3// THE DEFECT (measured 2026-07-20, root-caused from source, not theorised):
4//   sts_seed commits the WHOLE plane as a NEW segment on EVERY write (nx_store_seed_lib:45/65),
5//   sts_load does one ss_get PER ROW (:70), and ss_scan_seglist walks ALL segments chronologically
6//   for each key (nx_seg_store:1136). So a load costs O(rows x segments). Live numbers: debt- had
7//   464 segments / 42MB of .docs for ~200KB of actual rows (~210x amplification), ~124k segment-key
8//   scans per load, one nx_debt add took >15min then FAILED, nx_debt page was OOM-KILLED, and the
9//   store reached 15,024 files. The NAS went down under that load the same afternoon.
10//
11// THE INSIGHT THAT MAKES THE FIX SAFE AND CHEAP: because every segment is ALREADY a complete plane
12// snapshot, and ss_scan_seglist resolves each key to its LAST (newest) version, the NEWEST SEGMENT
13// ALONE IS A SEMANTICALLY COMPLETE PLANE -- including tombstones. So compaction does not merge, copy
14// or rewrite any record: it rewrites ONLY THE MANIFEST to reference the newest segment.
15//   - The superseded .docs/.idx files are LEFT ON DISK, untouched (rule 13 additive-only). Nothing is
16//     deleted; the manifest is the only mutation, and it is backed up first.
17//   - Therefore ROLLBACK IS ONE FILE COPY: restore <prefix>manifest.txt.bak-precompact.
18//
19// PROOF, NOT ASSERTION: apply loads the plane BEFORE, rewrites the manifest, loads AFTER, and compares
20// the two buffers BYTE-FOR-BYTE. Any difference -> the manifest is RESTORED and the organ REFUSES
21// (exit 3). A caller can never be left with a silently-lossy plane.
22//   nx_store_compact <prefix> check   -> segment count + newest segid (CHEAP: manifest only, no load)
23//   nx_store_compact <prefix> apply   -> the verified rewrite above (sts planes ONLY: every segment
24//                                        is a whole-plane snapshot there)
25//   nx_store_compact <prefix> fold    -> GENERIC merge compaction via the store's own ss_compact_cap
26//                                        (latest entry per key, tombstones kept, O(data) single pass).
27//                                        REQUIRED for reg planes (nx_registry: one record + index per
28//                                        segment -- newest segment is NOT a complete plane, so apply's
29//                                        manifest re-point would lose every other key). Verified by a
30//                                        pre-fold logical snapshot re-read AFTER through production
31//                                        ss_get; mismatch -> manifest restored, REFUSE (exit 3).
32// FAIL-CLOSED: missing/empty manifest, a load that fills the buffer (cannot verify a truncated view),
33// or a byte-mismatch all refuse without leaving the plane changed.
34// license_tier: ORIGINAL   No hw writes (Rule 26).   expect_exit: 0
35import "nx_store_seed_lib.nx"
36import "nx_seg_store.nx"
37import "nx_syscalls.nx"
38
39const SC_LOADCAP: i64 = 8388608
40const SC_KEYCAP: i64 = 1024
41const SC_MFCAP: i64 = 262144
42const SC_PATHCAP: i64 = 1024
43const SC_MSGCAP: i64 = 1024
44const SC_NL: i64 = 10
45const SC_DASH: i64 = 45
46const SC_ZERO: i64 = 48
47const SC_NINE: i64 = 57
48const SC_MODE: i64 = 420
49const SC_LOCK_EX: i64 = 2
50const SC_STDERR: i64 = 2
51const SC_EXIT_USAGE: i64 = 2
52const SC_EXIT_REFUSED: i64 = 3
53const SC_EXIT_IO: i64 = 1
54
55func sc_slen(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } return n }
56func sc_puts(s: *u8) -> i64 { sys_write(1, s, sc_slen(s)); return 0 }
57func sc_werr(s: *u8) -> i64 { sys_write(SC_STDERR, s, sc_slen(s)); return 0 }
58func sc_putn(v: i64) -> i64 { let b: *u8 = sys_mmap(32); let e: i64 = ss_catn(b, 0, v); sys_write(1, b, e); return 0 }
59func sc_eqs(a: *u8, b: *u8) -> i64 {
  var i: i64 = 0
  while a[i] != (0 as u8) { if a[i] != b[i] { return 0 } i = i + 1 }
  if b[i] != (0 as u8) { return 0 }
  return 1
64}
65func sc_path(prefix: *u8, tail: *u8, out: *u8) -> i64 {
  var o: i64 = ss_cat(out, 0, prefix)
  o = ss_cat(out, o, tail)
  out[o] = 0 as u8
  return o
70}
71func sc_read(path: *u8, b: *u8, cap: i64) -> i64 {
  let fd: i64 = sys_openat_rd(path)
  if fd < 0 { return 0 - 1 }
  var n: i64 = 0
  var go: i64 = 1
  while go == 1 {
      let r: i64 = sys_read(fd, (b as i64 + n) as *u8, cap - n)
      if r > 0 { n = n + r } else { go = 0 }
      if n >= cap { go = 0 }
  }
  sys_close(fd)
  return n
83}
84func sc_write(path: *u8, b: *u8, n: i64) -> i64 {
  let fd: i64 = sys_openat_wr(path, SC_MODE)
  if fd < 0 { return 0 - 1 }
  sys_write(fd, b, n)
  sys_fsync(fd)
  sys_close(fd)
  return 0
91}
92// count "seg-" lines and return the MAX segid via segmax[0]
93func sc_scan_manifest(b: *u8, n: i64, segmax: *i64) -> i64 {
  var cnt: i64 = 0
  var mx: i64 = 0 - 1
  var i: i64 = 0
  while i < n {
      var le: i64 = i
      var s: i64 = 1
      while s == 1 { if le >= n { s = 0 } else { if b[le] == (SC_NL as u8) { s = 0 } else { le = le + 1 } } }
      if le > i {
          // parse trailing digits after the last '-'
          var d: i64 = le
          var g: i64 = 1
          while g == 1 { g = 0; if d > i { let c: i64 = b[d-1] as i64; if c >= SC_ZERO { if c <= SC_NINE { d = d - 1; g = 1 } } } }
          if d < le { if d > i { if b[d-1] == (SC_DASH as u8) {
              var v: i64 = 0
              var k: i64 = d
              while k < le { v = v * 10 + ((b[k] as i64) - SC_ZERO); k = k + 1 }
              cnt = cnt + 1
              if v > mx { mx = v }
          } } }
      }
      i = le + 1
  }
  segmax[0] = mx
  return cnt
118}
119
120// ---- FOLD (generic merge compaction, any plane shape) ------------------------------------------------
121// Snapshot the plane's logical state by ONE chronological pass over every manifest segment's .docs
122// (each file read ONCE via ss_readall -- O(data), NOT O(keys x segments): a per-key ss_get walk over a
123// 1355-segment plane leaked >15GB of per-probe mappings and had to be killed, 2026-07-30). Last entry
124// per key wins, exactly ss_get's scan semantics. Tables: key ptr/len, kind (1=put 2=tombstone), val
125// ptr/len. Returns nk (keys), or -1 manifest read fail, -2 key-table overflow, -3 oversized key.
126func sc_snapshot(prefix: *u8, mfb: *u8, mfn: i64, tkp: *i64, tkl: *i64, tkind: *i64, tvp: *i64, tvl: *i64, maxk: i64) -> i64 {
  var nk: i64 = 0
  // DEDUP INDEX (2026-08-07): open-addressed hash -> key-slot+1 (0 = empty), power-of-two so the
  // probe masks instead of dividing, sized 2x maxk to hold the load factor <= 0.5. The hash is an
  // INDEX, never an identity -- every probe still byte-verifies with ss_kcmp, so a collision costs
  // one extra comparison and can never merge two distinct keys.
  // NOTE the comment at the head of this function: it records fixing the OTHER quadratic here (the
  // per-key ss_get walk that leaked >15GB on a 1355-segment plane, 2026-07-30). THIS one survived
  // that fix -- for EVERY record it walked the ENTIRE key table with NO early exit, because the
  // `if hit < 0` guard skipped only the comparison, never the iteration.
  // ★FIXING ONE QUADRATIC IN A FUNCTION DOES NOT MAKE THE FUNCTION LINEAR.
  var hcap: i64 = 16
  while hcap < maxk * 2 { hcap = hcap * 2 }
  let hidx: *i64 = sys_mmap(8 * hcap) as *i64
  var ls: i64 = 0
  var li: i64 = 0
  while li <= mfn {
      var eol: i64 = 0
      if li == mfn { eol = 1 } else { if mfb[li] == (SC_NL as u8) { eol = 1 } }
      if eol == 1 {
          if li > ls {
              let path: *u8 = sys_mmap(SC_PATHCAP)
              var o: i64 = ss_cat(path, 0, prefix)
              var c: i64 = 0
              while c < li - ls { path[o] = mfb[ls + c]; o = o + 1; c = c + 1 }
              o = ss_cat(path, o, ".docs" as *u8)
              path[o] = 0 as u8
              let szp: *i64 = sys_mmap(16) as *i64
              let b: *u8 = ss_readall(path, szp)
              if (b as i64) != 0 {
                  let sz: i64 = szp[0]
                  var i: i64 = 0
                  while i + 9 <= sz {
                      let kind: i64 = b[i] as i64
                      let kl: i64 = ss_r32(b, i + 1)
                      let koff: i64 = i + 5
                      let vl: i64 = ss_r32(b, koff + kl)
                      let voff: i64 = koff + kl + 4
                      if kl >= SC_KEYCAP { return 0 - 3 }
                      let kp: *u8 = ((b as i64) + koff) as *u8
                      var probe: i64 = ss_khash(kp, kl) & (hcap - 1)
                      var hit: i64 = 0 - 1
                      var probing: i64 = 1
                      while probing == 1 {
                          let e: i64 = hidx[probe]
                          if e == 0 { probing = 0 } else {
                              if ss_kcmp(tkp[e - 1] as *u8, tkl[e - 1], kp, kl) == 0 { hit = e - 1; probing = 0 }
                              else { probe = (probe + 1) & (hcap - 1) }
                          }
                      }
                      if hit < 0 {
                          if nk >= maxk { return 0 - 2 }
                          hit = nk
                          hidx[probe] = nk + 1
                          nk = nk + 1
                      }
                      tkp[hit] = (b as i64) + koff
                      tkl[hit] = kl
                      tkind[hit] = kind
                      tvp[hit] = (b as i64) + voff
                      tvl[hit] = vl
                      i = voff + vl
                  }
              }
          }
          ls = li + 1
      }
      li = li + 1
  }
  return nk
196}
197
198func main(argc: i64, argv: *i64) -> i64 {
  if argc < 3 { sc_werr("usage: nx_store_compact <prefix> check|apply|fold  (apply = sts manifest re-point; fold = generic merge via ss_compact_cap, REQUIRED for reg planes)\n" as *u8); sys_exit(SC_EXIT_USAGE); return SC_EXIT_USAGE }
  let prefix: *u8 = argv[1] as *u8
  let verb: *u8 = argv[2] as *u8
202
  let mfp: *u8 = sys_mmap(SC_PATHCAP)
  sc_path(prefix, "manifest.txt" as *u8, mfp)
  let mfb: *u8 = sys_mmap(SC_MFCAP)
  let mfn: i64 = sc_read(mfp, mfb, SC_MFCAP - 1)
  if mfn <= 0 { sc_werr("MANIFEST ABSENT/EMPTY (fail-closed): " as *u8); sc_werr(mfp); sc_werr("\n" as *u8); sys_exit(SC_EXIT_REFUSED); return SC_EXIT_REFUSED }
  let segmax: *i64 = sys_mmap(16) as *i64
  let segs: i64 = sc_scan_manifest(mfb, mfn, segmax)
  if segs <= 0 { sc_werr("MANIFEST has no seg- rows (fail-closed)\n" as *u8); sys_exit(SC_EXIT_REFUSED); return SC_EXIT_REFUSED }
211
  if sc_eqs("check" as *u8, verb) == 1 {
      sc_puts("COMPACT-CHECK prefix=" as *u8)
      sc_puts(prefix)
      sc_puts(" segments=" as *u8)
      sc_putn(segs)
      sc_puts(" newest_segid=" as *u8)
      sc_putn(segmax[0])
      sc_puts(" scan_cost_multiplier=" as *u8)
      sc_putn(segs)
      sc_puts("x (a load walks every segment per key)\n" as *u8)
      sys_exit(0)
      return 0
  }
225
  if sc_eqs("fold" as *u8, verb) == 1 {
      // ---- GENERIC MERGE COMPACTION: ss_compact_cap folds ALL segments into one (latest entry per
      // key, tombstones kept, retired names archived, atomic manifest swap; every failure path is
      // BEFORE the swap). Works for reg planes, whose newest segment is NOT a complete snapshot --
      // the sts-only "apply" manifest re-point would LOSE data there. Wrapped in proof: snapshot the
      // logical plane FIRST (one O(data) pass), then re-read every key AFTER through the production
      // ss_get path; any mismatch -> manifest RESTORED from backup, REFUSE.
      if segs == 1 { sc_puts("NO-OP already single-segment\n" as *u8); sys_exit(0); return 0 }
      let lkp2: *u8 = sys_mmap(SC_PATHCAP)
      sc_path(prefix, "plock" as *u8, lkp2)
      let lfd2: i64 = sys_openat_append(lkp2, SC_MODE)
      if lfd2 < 0 { sc_werr("REFUSED: cannot open plane lock (plock)\n" as *u8); sys_exit(SC_EXIT_REFUSED); return SC_EXIT_REFUSED }
      sys_flock(lfd2, SC_LOCK_EX)
      // BEFORE: logical snapshot, key-table sized data-driven (every entry >= 9 bytes)
      var tot: i64 = 0
      var ls2: i64 = 0
      var li2: i64 = 0
      while li2 <= mfn {
          var eol2: i64 = 0
          if li2 == mfn { eol2 = 1 } else { if mfb[li2] == (SC_NL as u8) { eol2 = 1 } }
          if eol2 == 1 { if li2 > ls2 { tot = tot + 1 } ls2 = li2 + 1 }
          li2 = li2 + 1
      }
      let maxk: i64 = SC_LOADCAP / 9 + 16
      let tkp: *i64 = sys_mmap(8 * maxk) as *i64
      let tkl: *i64 = sys_mmap(8 * maxk) as *i64
      let tkind: *i64 = sys_mmap(8 * maxk) as *i64
      let tvp: *i64 = sys_mmap(8 * maxk) as *i64
      let tvl: *i64 = sys_mmap(8 * maxk) as *i64
      let nk: i64 = sc_snapshot(prefix, mfb, mfn, tkp, tkl, tkind, tvp, tvl, maxk)
      if nk <= 0 { sc_werr("REFUSED: snapshot failed/empty (nothing to verify against)\n" as *u8); sys_exit(SC_EXIT_REFUSED); return SC_EXIT_REFUSED }
      // back the manifest up FIRST: rollback must be one file copy
      let bkp2: *u8 = sys_mmap(SC_PATHCAP)
      sc_path(prefix, "manifest.txt.bak-precompact" as *u8, bkp2)
      if sc_write(bkp2, mfb, mfn) < 0 { sc_werr("REFUSED: cannot write manifest backup\n" as *u8); sys_exit(SC_EXIT_IO); return SC_EXIT_IO }
      let segid: i64 = ss_next_segid(prefix)
      let rc: i64 = ss_compact_cap(prefix, segid, segs + 64)
      if rc < 0 {
          sc_werr("REFUSED: ss_compact_cap failed rc=" as *u8)
          let m0: *u8 = sys_mmap(SC_MSGCAP)
          var mo0: i64 = ss_catn(m0, 0, rc)
          mo0 = ss_cat(m0, mo0, " (live manifest untouched -- all failure paths precede the swap)\n" as *u8)
          sys_write(SC_STDERR, m0, mo0)
          sys_exit(SC_EXIT_REFUSED)
          return SC_EXIT_REFUSED
      }
      // AFTER: every snapshotted key re-read through the PRODUCTION ss_get path must agree
      var same: i64 = 1
      var badk: i64 = 0 - 1
      let kbuf: *u8 = sys_mmap(SC_KEYCAP)
      let po: *i64 = sys_mmap(16) as *i64
      let lo: *i64 = sys_mmap(16) as *i64
      var vk: i64 = 0
      var puts_n: i64 = 0
      var tombs_n: i64 = 0
      while vk < nk {
          let kpn: *u8 = tkp[vk] as *u8
          var kc: i64 = 0
          while kc < tkl[vk] { kbuf[kc] = kpn[kc]; kc = kc + 1 }
          kbuf[tkl[vk]] = 0 as u8
          let st: i64 = ss_get(prefix, kbuf, po, lo)
          if tkind[vk] == 1 {
              puts_n = puts_n + 1
              if st != 1 { same = 0; badk = vk } else {
                  if lo[0] != tvl[vk] { same = 0; badk = vk } else {
                      let va: *u8 = tvp[vk] as *u8
                      let vb: *u8 = po[0] as *u8
                      var q: i64 = 0
                      while q < tvl[vk] { if va[q] != vb[q] { same = 0; badk = vk; q = tvl[vk] } else { q = q + 1 } }
                  }
              }
          } else {
              tombs_n = tombs_n + 1
              if st != 0 { same = 0; badk = vk }
          }
          if same == 0 { vk = nk } else { vk = vk + 1 }
      }
      if same == 0 {
          sc_write(mfp, mfb, mfn)
          sc_werr("REFUSED: post-fold ss_get view DIFFERS at key #" as *u8)
          let m1: *u8 = sys_mmap(SC_MSGCAP)
          var mo1: i64 = ss_catn(m1, 0, badk)
          mo1 = ss_cat(m1, mo1, " -- manifest RESTORED, plane unchanged\n" as *u8)
          sys_write(SC_STDERR, m1, mo1)
          sys_exit(SC_EXIT_REFUSED)
          return SC_EXIT_REFUSED
      }
      sc_puts("FOLDED prefix=" as *u8)
      sc_puts(prefix)
      sc_puts(" segments=" as *u8)
      sc_putn(segs)
      sc_puts(" -> 1 (seg-" as *u8)
      sc_putn(segid)
      sc_puts(") keys=" as *u8)
      sc_putn(puts_n)
      sc_puts(" tombstones=" as *u8)
      sc_putn(tombs_n)
      sc_puts(" verified via production ss_get BYTE-IDENTICAL; retired segment FILES left on disk + archived (rule 13); rollback = restore " as *u8)
      sc_puts(bkp2)
      sc_puts("\n" as *u8)
      sys_exit(0)
      return 0
  }
329
  if sc_eqs("apply" as *u8, verb) == 1 {
      if segs == 1 { sc_puts("NO-OP already single-segment\n" as *u8); sys_exit(0); return 0 }
      // serialize against plane writers (nx_debt/nx_store_put use <prefix>plock)
      let lkp: *u8 = sys_mmap(SC_PATHCAP)
      sc_path(prefix, "plock" as *u8, lkp)
      let lfd: i64 = sys_openat_append(lkp, SC_MODE)
      // FAIL-CLOSED LOCK (2026-07-29 seq1254): proceeding UNLOCKED on a failed plock open lets a
      // compact race live writers -- a lost manifest RMW then drops their committed lines silently.
      if lfd < 0 { sc_werr("REFUSED: cannot open plane lock (plock) -- compacting UNLOCKED can race a live writer and drop its manifest line\n" as *u8); sys_exit(SC_EXIT_REFUSED); return SC_EXIT_REFUSED }
      sys_flock(lfd, SC_LOCK_EX)
340
      // BEFORE: the authoritative logical plane
      let bufA: *u8 = sys_mmap(SC_LOADCAP)
      let na: i64 = sts_load(prefix, bufA, SC_LOADCAP)
      if na <= 0 { sc_werr("REFUSED: plane loads empty (nothing to verify against)\n" as *u8); sys_exit(SC_EXIT_REFUSED); return SC_EXIT_REFUSED }
      if na >= SC_LOADCAP { sc_werr("REFUSED: plane fills the load buffer -- cannot verify a TRUNCATED view\n" as *u8); sys_exit(SC_EXIT_REFUSED); return SC_EXIT_REFUSED }
346
      // back the manifest up FIRST: rollback must be one file copy
      let bkp: *u8 = sys_mmap(SC_PATHCAP)
      sc_path(prefix, "manifest.txt.bak-precompact" as *u8, bkp)
      if sc_write(bkp, mfb, mfn) < 0 { sc_werr("REFUSED: cannot write manifest backup\n" as *u8); sys_exit(SC_EXIT_IO); return SC_EXIT_IO }
351
      // the ONLY mutation: a manifest naming just the newest segment
      let nmb: *u8 = sys_mmap(SC_PATHCAP)
      var o: i64 = ss_cat(nmb, 0, "seg-" as *u8)
      o = ss_catn(nmb, o, segmax[0])
      nmb[o] = SC_NL as u8
      o = o + 1
      if sc_write(mfp, nmb, o) < 0 { sc_werr("REFUSED: cannot write manifest\n" as *u8); sys_exit(SC_EXIT_IO); return SC_EXIT_IO }
359
      // AFTER: must be byte-identical or we put it all back
      let bufB: *u8 = sys_mmap(SC_LOADCAP)
      let nb: i64 = sts_load(prefix, bufB, SC_LOADCAP)
      var same: i64 = 1
      if nb != na { same = 0 } else {
          var i: i64 = 0
          while i < na { if bufA[i] != bufB[i] { same = 0; i = na } else { i = i + 1 } }
      }
      if same == 0 {
          sc_write(mfp, mfb, mfn)
          sc_werr("REFUSED: post-compaction load DIFFERS -- manifest RESTORED, plane unchanged. before_bytes=" as *u8)
          let m: *u8 = sys_mmap(SC_MSGCAP)
          var mo: i64 = ss_catn(m, 0, na)
          mo = ss_cat(m, mo, " after_bytes=" as *u8)
          mo = ss_catn(m, mo, nb)
          mo = ss_cat(m, mo, "\n" as *u8)
          sys_write(SC_STDERR, m, mo)
          sys_exit(SC_EXIT_REFUSED)
          return SC_EXIT_REFUSED
      }
      sc_puts("COMPACTED prefix=" as *u8)
      sc_puts(prefix)
      sc_puts(" segments=" as *u8)
      sc_putn(segs)
      sc_puts(" -> 1 (seg-" as *u8)
      sc_putn(segmax[0])
      sc_puts(") verified_bytes=" as *u8)
      sc_putn(na)
      sc_puts(" BYTE-IDENTICAL; superseded segment FILES left on disk untouched (rule 13); rollback = restore " as *u8)
      sc_puts(bkp)
      sc_puts("\n" as *u8)
      sys_exit(0)
      return 0
  }
394
  sc_werr("usage: nx_store_compact <prefix> check|apply|fold\n" as *u8)
  sys_exit(SC_EXIT_USAGE)
  return SC_EXIT_USAGE
398}
nx_store_compact.nx source

`nx_store_compact.nx` source
