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

↩ module page · 309 lines · 16203 B
1// ORPHAN FORK -- NOT THE FILE THAT RUNS. Adjudicated 2026-08-16 by measurement, not preference:
2//   * ZERO references to "nx_dup_source_check_v3" anywhere in buildroot -- nx_shelltool over 56,497
3//     files, corpus_complete=1. Nothing imports it, no registry or conf names it.
4//   * The REGISTERED tool's banner ("scope DISCOVERED; allocation O(pairs) not O(files)") is emitted
5//     by nx_dup_source_check.nx, NOT by this file's header text. The name that ships is the SHORT one.
6// ==> nx_dup_source_check.nx is CANONICAL. This file is dead weight kept only because retiring it
7//     needs nx_retire_path (rename-only, reversible), which the seat that found this could not call.
8//     ACTION: `nx_retire_path retire buildroot/runtime/_hdl_build/nx_dup_source_check_v3.nx`.
9// A THIRD variant exists laptop-side (nxc2/runtime/_hdl_build/nx_dup_source_check_v3.nx) whose anchors
10// match NEITHER NAS copy -- three forks of one organ. That is why its ARENA-OVERRUN went unfixed for so
11// long: any seat repairing it had a one-in-three chance of editing a copy nothing executes.
12// The slot-bound fix below was applied here anyway, so the forks cannot diverge FURTHER on this defect.
13// ★A DUPLICATE-DETECTOR THAT IS ITSELF TRIPLICATED CANNOT REPORT ITS OWN CONDITION.
14//
15// nx_dup_source_check.nx v3 -- ANTI-CLOBBER cross-tree source-dup detector.
16//
17// 🚨v3 EXISTS BECAUSE v2 WAS AN OOM BOMB THAT TOOK THE NAS DOWN (2026-07-20). Root cause, stated plainly:
18// v2 widened the scan from 2 hardcoded dirs to ALL discovered source trees (78 pairs) -- a good change -- but
19// REUSED v1's `exists()` helper UNCHANGED, and that helper did `sys_mmap(4096)` PER CALL and never unmapped.
20// v1 called it ~15k times (ONE pair) = ~60MB = survivable. v2 called it ~250k times = ~1GB LEAKED PER RUN, on a
21// cron. Result: NAS userspace starved -- kernel still SYN-ACKs but sshd gives no banner, HTTPS returns status=0,
22// even DSM stops answering.
23//
24// ★THE LESSON, so it is never repeated: CHANGING A CALLER'S FAN-OUT RE-COSTS EVERY CALLEE. A 2->78 pair change
25// is a 17x amplifier on an O(files) helper. Reviewing only the code you WROTE is not enough -- you must re-cost
26// the code you INHERITED AND AMPLIFIED. And note what the v2 selftest could NOT do: it was GREEN 4/4 because
27// fixture dirs hold 2-3 files, so it tested the ALGORITHM at scale and never the RESOURCE at scale. A scale-law
28// tooth that asserts only correctness-on-big-input is HALF a tooth; the other half is a RESOURCE bound.
29//
30// v3 FIX: every path buffer is allocated ONCE PER PAIR (or once per walk) and passed down, never per file.
31// Allocation profile is now O(pairs + dirs), not O(files), and it is DECLARED in the output envelope so the
32// property is inspectable rather than assumed. Detection semantics and the emitted "  DUP basename: " line are
33// UNCHANGED (rule 19) -- nx_favela_census counts that exact substring out of knowledge/status/dup_source.log.
34// expect_exit:0 when clean.
35import "nx_syscalls.nx"
36import "nx_itoa_lib.nx"   // shared MSB-first emitter (zero-alloc)
37const K_MAGIC_131072: i64 = 131072
38const K_MAGIC_4096: i64 = 4096
39
40func dp_w(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
41// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
42// per call and never freed it. At PAGE granularity that is 4096B leaked PER CALL -- the
43// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff (2MB input, ~3.66M calls).
44// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
45func dp_wn(v: i64) -> i64 { nxi_out(v); return 0 }
46
47func ends_nx(nm: *u8) -> i64 {
  var n: i64=0; while nm[n]!=(0 as u8){n=n+1}
  if n < 3 { return 0 }
  if nm[n-3]==(46 as u8) { if nm[n-2]==(110 as u8) { if nm[n-1]==(120 as u8) { return 1 } } }
  return 0
52}
53
54func join_path(buf: *u8, dir: *u8, name: *u8) -> i64 {
  var o: i64=0; var i: i64=0
  while dir[i]!=(0 as u8) { buf[o]=dir[i]; o=o+1; i=i+1 }
  buf[o]=47 as u8; o=o+1
  i=0; while name[i]!=(0 as u8) { buf[o]=name[i]; o=o+1; i=i+1 }
  buf[o]=0 as u8
  return 0
61}
62
63// ★v3: takes a CALLER-OWNED scratch buffer. No allocation here -- this is the hot path (once per .nx file).
64func exists(dir: *u8, name: *u8, scratch: *u8) -> i64 {
  join_path(scratch, dir, name)
  let fd: i64=sys_openat_rd(scratch)
  if fd >= 0 { sys_close(fd); return 1 }
  return 0
69}
70
71func is_dot(nm: *u8) -> i64 {
  if nm[0]==(46 as u8) {
      if nm[1]==(0 as u8) { return 1 }
      if nm[1]==(46 as u8) { if nm[2]==(0 as u8) { return 1 } }
  }
  return 0
77}
78
79func str_copy(dst: *u8, src: *u8) -> i64 { var i: i64=0; while src[i]!=(0 as u8) { dst[i]=src[i]; i=i+1 } dst[i]=0 as u8; return i }
80
81// Does `s` (with its NUL) fit in a slot of `cap` bytes? Stops at cap, so it costs O(cap) not O(len)
82// and cannot itself walk off the end of a pathological string. Returns 1 fits, 0 does not.
83// Exists because str_copy above is UNBOUNDED BY DESIGN (the right primitive for a sized destination)
84// -- the caller owes the bound, and two callers were not paying it.
85func path_fits(s: *u8, cap: i64) -> i64 {
  var i: i64 = 0
  while i < cap { if s[i] == (0 as u8) { return 1 } i = i + 1 }
  return 0
89}
90
91// ★v3: exactly TWO allocations per pair (dirent buffer + path scratch), regardless of file count.
92// Output contract UNCHANGED from v1/v2 (rule 19).
93func scan(dirA: *u8, dirB: *u8, verbose: i64) -> i64 {
  let fd: i64=sys_openat_rd(dirA)
  if fd < 0 { return 0 }
  let dbuf: *u8=sys_mmap(K_MAGIC_131072)
  let pbuf: *u8=sys_mmap(K_MAGIC_4096)
  var dups: i64=0
  var go: i64=1
  while go == 1 {
      let nr: i64=sys_getdents64(fd, dbuf, K_MAGIC_131072)
      if nr <= 0 { go = 0 } else {
          var off: i64=0
          while off < nr {
              let rec: *u8=(dbuf as i64 + off) as *u8
              let ty: i64=dirent_type(rec)
              let nm: *u8=dirent_name(rec)
              if ty != 4 {
                  if ends_nx(nm) == 1 {
                      if exists(dirB, nm, pbuf) == 1 {
                          dups = dups + 1
                          if verbose == 1 { dp_w("  DUP basename: "); dp_w(nm); dp_w("   (present in both "); dp_w(dirA); dp_w(" and "); dp_w(dirB); dp_w(")\n" as *u8) }
                      }
                  }
              }
              off = off + dirent_reclen(rec)
          }
      }
  }
  sys_close(fd)
  return dups
122}
123
124func wfile(path: *u8) -> i64 { let fd: i64=sys_openat_wr(path, 420); if fd>=0 { sys_write(fd, "x" as *u8, 1); sys_close(fd) } return 0 }
125
126// BFS-discover dirs holding >=1 .nx. Buffers hoisted; allocation is O(1) per walk, not per entry.
127func discover(root: *u8, out: *u8, maxd: i64, maxdepth: i64, cap: *i64) -> i64 {
  let QCAP: i64 = 256
  let qbuf: *u8 = sys_mmap(QCAP*256)
  let qdep: *i64 = sys_mmap(QCAP*8) as *i64
  let dbuf: *u8 = sys_mmap(K_MAGIC_131072)
  let child: *u8 = sys_mmap(K_MAGIC_4096)
  var qh: i64 = 0
  var qt: i64 = 0
  cap[0] = 0
  str_copy((qbuf as i64) as *u8, root); qdep[0]=0; qt=1
  var nd: i64 = 0
  while qh < qt {
      let cur: *u8 = (qbuf as i64 + qh*256) as *u8
      let cdep: i64 = qdep[qh]
      qh = qh + 1
      let fd: i64 = sys_openat_rd(cur)
      if fd >= 0 {
          var hasnx: i64 = 0
          var go: i64 = 1
          while go == 1 {
              let nr: i64 = sys_getdents64(fd, dbuf, K_MAGIC_131072)
              if nr <= 0 { go = 0 } else {
                  var off: i64 = 0
                  while off < nr {
                      let rec: *u8 = (dbuf as i64 + off) as *u8
                      let ty: i64 = dirent_type(rec)
                      let nm: *u8 = dirent_name(rec)
                      if ty == 4 {
                          if is_dot(nm) == 0 {
                              if cdep < maxdepth {
                                  if qt < QCAP {
                                      join_path(child, cur, nm)
                                      // SLOT-BOUND CHECK (2026-08-16), same defect and same fix as
                                      // nx_dup_source_check.nx: `child` is a 4096-byte buffer, each
                                      // queue slot is 256, and str_copy runs to the NUL with NO
                                      // bound. TWO symptoms, ONE defect -- a moderate overrun stays
                                      // inside the 65536-byte qbuf and SILENTLY corrupts the next
                                      // queue entry while the tool still prints GREEN; near QCAP it
                                      // leaves the arena and trips ARENA-OVERRUN. Refusing here reuses
                                      // this tool's OWN truncation signal so the loud RED verdict
                                      // fires instead of a wrong GREEN. Bite-proven on the sibling
                                      // with a 284-byte fixture: 5/cap_hit=0/GREEN -> 4/cap_hit=1/RED.
                                      if path_fits(child, 256) == 1 {
                                          str_copy((qbuf as i64 + qt*256) as *u8, child)
                                          qdep[qt] = cdep + 1
                                          qt = qt + 1
                                      } else { cap[0] = 1 }
                                  } else { cap[0] = 1 }
                              }
                          }
                      } else {
                          if ends_nx(nm) == 1 { hasnx = 1 }
                      }
                      off = off + dirent_reclen(rec)
                  }
              }
          }
          sys_close(fd)
          if hasnx == 1 {
              // same slot bound as the queue write above: `out` is maxd slots of 256 bytes, and the
              // LAST slot has nothing after it to absorb an overrun.
              if nd < maxd {
                  if path_fits(cur, 256) == 1 { str_copy((out as i64 + nd*256) as *u8, cur); nd = nd + 1 }
                  else { cap[0] = 1 }
              }
              else { cap[0] = 1 }
          }
      }
  }
  return nd
197}
198
199func selftest() -> i64 {
  // T1 v1 REGRESSION: two-dir case still finds exactly one dup, ignores the non-dup
  sys_mkdir("/tmp/nxdupA" as *u8, 0x1ed)
  sys_mkdir("/tmp/nxdupB" as *u8, 0x1ed)
  wfile("/tmp/nxdupA/foo.nx" as *u8)
  wfile("/tmp/nxdupA/bar.nx" as *u8)
  wfile("/tmp/nxdupB/foo.nx" as *u8)
  let dups: i64=scan("/tmp/nxdupA" as *u8, "/tmp/nxdupB" as *u8, 0)
  if dups != 1 { dp_w("  SELFTEST FAIL T1: expected 1 dup, got "); dp_wn(dups); dp_w("\n" as *u8); return 0 }
  // T2 nested-tree tooth (the seq281 class v1 was blind to)
  sys_mkdir("/tmp/nxdup3" as *u8, 0x1ed)
  sys_mkdir("/tmp/nxdup3/_hdl_build" as *u8, 0x1ed)
  sys_mkdir("/tmp/nxdup3/runtime" as *u8, 0x1ed)
  wfile("/tmp/nxdup3/only_here.nx" as *u8)
  wfile("/tmp/nxdup3/_hdl_build/organ.nx" as *u8)
  wfile("/tmp/nxdup3/runtime/organ.nx" as *u8)
  let tbl: *u8 = sys_mmap(16*256)
  let cap: *i64 = sys_mmap(16) as *i64
  let n: i64 = discover("/tmp/nxdup3" as *u8, tbl, 16, 5, cap)
  if n != 3 { dp_w("  SELFTEST FAIL T2a: expected 3 trees, got "); dp_wn(n); dp_w("\n" as *u8); return 0 }
  var found: i64 = 0
  var i: i64 = 0
  while i < n {
      var j: i64 = i + 1
      while j < n { found = found + scan((tbl as i64 + i*256) as *u8, (tbl as i64 + j*256) as *u8, 0); j = j + 1 }
      i = i + 1
  }
  if found != 1 { dp_w("  SELFTEST FAIL T2b: nested dup not caught, got "); dp_wn(found); dp_w("\n" as *u8); return 0 }
  // T3 NON-VACUOUS negative control: v1's hardcoded pair reports ZERO here
  let v1blind: i64 = scan("/tmp/nxdup3" as *u8, "/tmp/nxdup3/_hdl_build" as *u8, 0)
  if v1blind != 0 { dp_w("  SELFTEST FAIL T3: negative control expected 0, got "); dp_wn(v1blind); dp_w("\n" as *u8); return 0 }
  // T4 truncation must be LOUD, never silent
  let tbl2: *u8 = sys_mmap(4*256)
  let cap2: *i64 = sys_mmap(16) as *i64
  discover("/tmp/nxdup3" as *u8, tbl2, 1, 5, cap2)
  if cap2[0] != 1 { dp_w("  SELFTEST FAIL T4: silent cap\n" as *u8); return 0 }
  // ★T5 RESOURCE TOOTH -- the half of the scale law v2 was missing. 600 files in ONE dir: v2 would have
  // allocated 600 x 4096 here (per-file mmap); v3 allocates TWO buffers for the whole pair. This asserts the
  // hot loop is allocation-free by exercising it at a file count a fixture normally never reaches.
  sys_mkdir("/tmp/nxdupR" as *u8, 0x1ed)
  sys_mkdir("/tmp/nxdupS" as *u8, 0x1ed)
  let nmb: *u8 = sys_mmap(256)
  let dg: *u8 = sys_mmap(16)
  // ⚠LM-030: a string literal may NOT be indexed in expression position (CONST[i] crashes nx_cc with
  // "unexpected operator token kind=47"). Bind it to a local pointer FIRST, then index the local.
  let pfx: *u8 = "/tmp/nxdupR/f" as *u8
  var k: i64 = 0
  while k < 600 {
      // build /tmp/nxdupR/f<k>.nx -- ZERO allocations in this loop (nmb + dg are hoisted above), which is the
      // whole point of the tooth: if the hot path allocated per iteration this fixture would show it.
      var p: i64 = 0
      while pfx[p]!=(0 as u8) { nmb[p]=pfx[p]; p=p+1 }
      var t: i64 = k
      var dn: i64 = 0
      if t==0 { dg[0]=48 as u8; dn=1 }
      while t>0 { dg[dn]=(48+(t%10)) as u8; t=t/10; dn=dn+1 }
      var q: i64 = 0
      while q<dn { nmb[p]=dg[dn-1-q]; p=p+1; q=q+1 }
      nmb[p]=46 as u8; nmb[p+1]=110 as u8; nmb[p+2]=120 as u8; nmb[p+3]=0 as u8
      wfile(nmb)
      k = k + 1
  }
  let big: i64 = scan("/tmp/nxdupR" as *u8, "/tmp/nxdupS" as *u8, 0)
  if big != 0 { dp_w("  SELFTEST FAIL T5: expected 0 dups vs empty dir, got "); dp_wn(big); dp_w("\n" as *u8); return 0 }
  return 1
264}
265
266func main() -> i64 {
  dp_w("nx_dup_source_check v3 (cross-tree source-dup detector -- scope DISCOVERED; allocation O(pairs) not O(files))\n" as *u8)
  if selftest() != 1 { dp_w("verdict=RED (self-test of the detector failed)\n" as *u8); sys_exit(1); return 1 }
  dp_w("  self-test OK (v1 regression + nested-tree tooth + non-vacuous negative control + loud-cap + 600-file RESOURCE tooth)\n" as *u8)
  let MAXD: i64 = 24
  let MAXDEPTH: i64 = 6
  let tbl: *u8 = sys_mmap(MAXD*256)
  let cap: *i64 = sys_mmap(16) as *i64
  dp_w("  discovering source trees under buildroot/ ...\n" as *u8)
  let nd: i64 = discover("buildroot" as *u8, tbl, MAXD, MAXDEPTH, cap)
  var i: i64 = 0
  while i < nd { dp_w("  source tree: "); dp_w((tbl as i64 + i*256) as *u8); dp_w("\n" as *u8); i = i + 1 }
  dp_w("  source trees discovered: "); dp_wn(nd); dp_w("\n" as *u8)
  var realdups: i64 = 0
  var pairs: i64 = 0
  i = 0
  while i < nd {
      var j: i64 = i + 1
      while j < nd {
          realdups = realdups + scan((tbl as i64 + i*256) as *u8, (tbl as i64 + j*256) as *u8, 1)
          pairs = pairs + 1
          j = j + 1
      }
      i = i + 1
  }
  dp_w("  cross-tree source-dup basenames found: "); dp_wn(realdups); dp_w("\n" as *u8)
  dp_w("  ENVELOPE: pairs_compared="); dp_wn(pairs)
  dp_w(" trees="); dp_wn(nd)
  dp_w(" tree_cap="); dp_wn(MAXD)
  dp_w(" depth_cap="); dp_wn(MAXDEPTH)
  dp_w(" cap_hit="); dp_wn(cap[0])
  dp_w(" allocs=O(pairs+dirs) NOT O(files) [v2 regression guard: the per-file mmap in exists() leaked ~1GB/run and starved the host]")
  dp_w(" (counts are per-pair: one basename in three trees counts twice -- an upper bound on PAIRWISE hazards, not a distinct-basename count)\n" as *u8)
  if cap[0] == 1 {
      dp_w("verdict=RED (TRUNCATED -- a bound was hit; this scan is INCOMPLETE, raise MAXD/MAXDEPTH before trusting it)\n" as *u8)
      sys_exit(3); return 3
  }
  if realdups == 0 {
      dp_w("verdict=GREEN (detection proven; no cross-tree source-dup clobber hazards)\n" as *u8)
      sys_exit(0); return 0
  }
  dp_w("verdict=RED (clobber hazard(s) present -- reconcile each basename to ONE canonical source dir; see debt seq207/seq281/seq284)\n" as *u8)
  sys_exit(3); return 3
309}
nx_dup_source_check_v3.nx source

`nx_dup_source_check_v3.nx` source
