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

↩ module page · 268 lines · 12961 B
1// nx_dup_source_check.nx v3 -- ANTI-CLOBBER cross-tree source-dup detector.
2//
3// 🚨v3 EXISTS BECAUSE v2 WAS AN OOM BOMB THAT TOOK THE NAS DOWN (2026-07-20). Root cause, stated plainly:
4// v2 widened the scan from 2 hardcoded dirs to ALL discovered source trees (78 pairs) -- a good change -- but
5// REUSED v1's `exists()` helper UNCHANGED, and that helper did `sys_mmap(4096)` PER CALL and never unmapped.
6// v1 called it ~15k times (ONE pair) = ~60MB = survivable. v2 called it ~250k times = ~1GB LEAKED PER RUN, on a
7// cron. Result: NAS userspace starved -- kernel still SYN-ACKs but sshd gives no banner, HTTPS returns status=0,
8// even DSM stops answering.
9//
10// ★THE LESSON, so it is never repeated: CHANGING A CALLER'S FAN-OUT RE-COSTS EVERY CALLEE. A 2->78 pair change
11// is a 17x amplifier on an O(files) helper. Reviewing only the code you WROTE is not enough -- you must re-cost
12// the code you INHERITED AND AMPLIFIED. And note what the v2 selftest could NOT do: it was GREEN 4/4 because
13// fixture dirs hold 2-3 files, so it tested the ALGORITHM at scale and never the RESOURCE at scale. A scale-law
14// tooth that asserts only correctness-on-big-input is HALF a tooth; the other half is a RESOURCE bound.
15//
16// v3 FIX: every path buffer is allocated ONCE PER PAIR (or once per walk) and passed down, never per file.
17// Allocation profile is now O(pairs + dirs), not O(files), and it is DECLARED in the output envelope so the
18// property is inspectable rather than assumed. Detection semantics and the emitted "  DUP basename: " line are
19// UNCHANGED (rule 19) -- nx_favela_census counts that exact substring out of knowledge/status/dup_source.log.
20// expect_exit:0 when clean.
21import "nx_syscalls.nx"
22import "nx_itoa_lib.nx"   // shared MSB-first emitter (zero-alloc)
23const K_MAGIC_131072: i64 = 131072
24const K_MAGIC_4096: i64 = 4096
25
26func 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 }
27// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
28// per call and never freed it. At PAGE granularity that is 4096B leaked PER CALL -- the
29// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff (2MB input, ~3.66M calls).
30// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
31func dp_wn(v: i64) -> i64 { nxi_out(v); return 0 }
32
33func 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
38}
39
40func 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
47}
48
49// ★v3: takes a CALLER-OWNED scratch buffer. No allocation here -- this is the hot path (once per .nx file).
50func 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
55}
56
57func 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
63}
64
65func 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 }
66
67// ★v3: exactly TWO allocations per pair (dirent buffer + path scratch), regardless of file count.
68// Output contract UNCHANGED from v1/v2 (rule 19).
69func 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
98}
99
100func 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 }
101
102// BFS-discover dirs holding >=1 .nx. Buffers hoisted; allocation is O(1) per walk, not per entry.
103func 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)
                                      str_copy((qbuf as i64 + qt*256) as *u8, child)
                                      qdep[qt] = cdep + 1
                                      qt = qt + 1
                                  } else { cap[0] = 1 }
                              }
                          }
                      } else {
                          if ends_nx(nm) == 1 { hasnx = 1 }
                      }
                      off = off + dirent_reclen(rec)
                  }
              }
          }
          sys_close(fd)
          if hasnx == 1 {
              if nd < maxd { str_copy((out as i64 + nd*256) as *u8, cur); nd = nd + 1 }
              else { cap[0] = 1 }
          }
      }
  }
  return nd
156}
157
158func 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
223}
224
225func 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
268}
nx_dup_source_check_v3.nx source

`nx_dup_source_check_v3.nx` source
