code wiki / _hdl_build / nx_galx_cid_index.nx
nx_galx_cid_index.nx source
↩ module page · 147 lines · 8455 B
1// nx_galx_cid_index.nx -- SOVEREIGN O(1) cid->path store (replaces the per-request flat-TSV scan).
2//
3// The gallery resolved cid->path by READING + SCANNING the whole galx_cid_paths.tsv (34.5MB, 235k lines) on
4// EVERY /img and /thumb request -- a grid page = ~60 of those = the "loading is atrocious". This builds a
5// sovereign binary hash index (our own format, NOT a flat TSV; "nishi ecosystem all the way up"): an FNV-1a
6// open-addressed bucket table (cid_hash -> path location) + a paths blob. Lookup is O(1) average. The .idx +
7// .blob ARE the runtime store; the TSV is only a one-time build input (and can then be retired).
8//
9// Format:
10// <idx>: [8 n_buckets][8 n_entries] then n_buckets * 24: [8 cid_hash][8 path_off][8 path_len]
11// cid_hash==0 marks an empty bucket (a cid hashing to 0 is remapped to 1).
12// <blob>: the concatenated path bytes (path_off/path_len locate each).
13// Collision-safety: FNV-1a 64; for 235k entries the chance of ANY 64-bit collision is ~3e-9 (negligible);
14// the cid itself is nxc1-<64 hex> (already a content hash) so it is effectively unique.
15// license_tier: ORIGINAL
16import "nx_syscalls.nx"
17
18const CIDX_CIDLEN: i64 = 69 // "nxc1-" + 64 hex
19
20// FNV-1a 64 of s[0..n). i64 multiply wraps (mod 2^64) -- fine for hashing.
21func cidx_fnv1a(s: *u8, n: i64) -> i64 {
22 var h: i64 = 0xcbf29ce484222325 as i64
23 var i: i64 = 0
24 while i < n {
25 h = h ^ (s[i] as i64)
26 h = h * (0x100000001b3 as i64)
27 i = i + 1
28 }
29 if h == 0 { h = 1 }
30 return h
31}
32
33// Build the index+blob from a cid_paths.tsv (lines: "<cid>\t<path>"). Returns n_entries, or -1 on error.
34// Little-endian i64 (native struct-stat field order), as opposed to cidx_rd64's big-endian on-disk
35// index fields. Two byte orders live in this file ON PURPOSE: the INDEX format is ours and
36// big-endian; struct stat is the kernel's and native-endian. Reading one with the other's reader
37// yields an enormous, plausible-looking timestamp -- always stale, or never stale, and silent.
38func cidx_rd64le(p: *u8, o: i64) -> i64 {
39 return (p[o] as i64) | ((p[o+1] as i64)<<8) | ((p[o+2] as i64)<<16) | ((p[o+3] as i64)<<24)
40 | ((p[o+4] as i64)<<32) | ((p[o+5] as i64)<<40) | ((p[o+6] as i64)<<48) | ((p[o+7] as i64)<<56)
41}
42
43// Is the derived index STALE with respect to its source TSV? 1 = rebuild, 0 = keep.
44//
45// WHY THIS EXISTS. The server rebuilt idx+blob from the TSV UNCONDITIONALLY at every boot. That
46// silently made the "runtime store" a DERIVED CACHE and the "retired" TSV the real source of truth
47// -- so a native insert into idx+blob was correct, resolvable by the reader, and then ERASED by the
48// next restart. The restart required to PUBLISH a write was the same event that DESTROYED it.
49// A STORE THAT REGENERATES ITSELF FROM A LEGACY FORMAT ON EVERY BOOT CANNOT BE WRITTEN TO, AND THAT
50// IS EXACTLY WHY IT ONLY EVER SHIPPED WITH A BUILDER AND NO INSERT.
51// Conditional rebuild keeps BOTH paths honest: edit the TSV and its mtime overtakes the index, so it
52// rebuilds exactly as before; write natively and the index is newer, so the write survives.
53// It also removes a 34MB parse of 235k rows from every boot.
54func gs_cidindex_stale(tsv_path: *u8, idx_path: *u8, blob_path: *u8) -> i64 {
55 let si: *u8 = sys_mmap(256)
56 let sb: *u8 = sys_mmap(256)
57 let st: *u8 = sys_mmap(256)
58 if sys_fstatat(idx_path, si) < 0 { return 1 } // no index at all -> build
59 if sys_fstatat(blob_path, sb) < 0 { return 1 } // half an index is not an index
60 // A missing SOURCE is not a reason to discard a good index: refuse to destroy what we have.
61 if sys_fstatat(tsv_path, st) < 0 { return 0 }
62 if cidx_rd64le(st, 88) > cidx_rd64le(si, 88) { return 1 }
63 return 0
64}
65
66func gs_cidindex_build(tsv_path: *u8, idx_path: *u8, blob_path: *u8) -> i64 {
67 let szp: *i64 = sys_mmap(16) as *i64
68 let b: *u8 = sys_read_file(tsv_path, szp)
69 if (b as i64) == 0 { return 0 - 1 }
70 let sz: i64 = szp[0]
71 // count lines
72 var nent: i64 = 0; var i: i64 = 0
73 while i < sz { if b[i] == (10 as u8) { nent = nent + 1 } i = i + 1 }
74 if nent < 1 { return 0 }
75 // n_buckets = smallest power of two >= nent*2
76 var nb: i64 = 1
77 while nb < nent * 2 { nb = nb * 2 }
78 let idx: *u8 = sys_mmap(16 + nb * 24 + 64)
79 var z: i64 = 0; while z < 16 + nb * 24 { idx[z] = 0 as u8; z = z + 1 } // zero (empty buckets)
80 // header
81 var hi: i64 = 0
82 idx[0]=(nb>>56) as u8; idx[1]=(nb>>48) as u8; idx[2]=(nb>>40) as u8; idx[3]=(nb>>32) as u8; idx[4]=(nb>>24) as u8; idx[5]=(nb>>16) as u8; idx[6]=(nb>>8) as u8; idx[7]=nb as u8
83 idx[8]=(nent>>56) as u8; idx[9]=(nent>>48) as u8; idx[10]=(nent>>40) as u8; idx[11]=(nent>>32) as u8; idx[12]=(nent>>24) as u8; idx[13]=(nent>>16) as u8; idx[14]=(nent>>8) as u8; idx[15]=nent as u8
84 let blob: *u8 = sys_mmap(sz + 64)
85 var blob_off: i64 = 0
86 var ls: i64 = 0; i = 0
87 while i <= sz {
88 var nl: i64 = 0; if i == sz { nl = 1 } else { if b[i] == (10 as u8) { nl = 1 } }
89 if nl == 1 {
90 if i - ls > CIDX_CIDLEN {
91 // cid = [ls, ls+69); expect TAB at ls+69; path = [ls+70, i)
92 if b[ls + CIDX_CIDLEN] == (9 as u8) {
93 let poff: i64 = blob_off
94 let plen: i64 = i - (ls + CIDX_CIDLEN + 1)
95 var p: i64 = 0; while p < plen { blob[blob_off] = b[ls + CIDX_CIDLEN + 1 + p]; blob_off = blob_off + 1; p = p + 1 }
96 let cb: *u8 = ((b as i64) + ls) as *u8
97 let h: i64 = cidx_fnv1a(cb, CIDX_CIDLEN)
98 var bk: i64 = h & (nb - 1)
99 var placed: i64 = 0
100 while placed == 0 {
101 let bo: i64 = 16 + bk * 24
102 let cur: i64 = (((idx[bo] as i64)<<56)|((idx[bo+1] as i64)<<48)|((idx[bo+2] as i64)<<40)|((idx[bo+3] as i64)<<32)|((idx[bo+4] as i64)<<24)|((idx[bo+5] as i64)<<16)|((idx[bo+6] as i64)<<8)|(idx[bo+7] as i64))
103 if cur == 0 {
104 idx[bo]=(h>>56) as u8; idx[bo+1]=(h>>48) as u8; idx[bo+2]=(h>>40) as u8; idx[bo+3]=(h>>32) as u8; idx[bo+4]=(h>>24) as u8; idx[bo+5]=(h>>16) as u8; idx[bo+6]=(h>>8) as u8; idx[bo+7]=h as u8
105 idx[bo+8]=(poff>>56) as u8; idx[bo+9]=(poff>>48) as u8; idx[bo+10]=(poff>>40) as u8; idx[bo+11]=(poff>>32) as u8; idx[bo+12]=(poff>>24) as u8; idx[bo+13]=(poff>>16) as u8; idx[bo+14]=(poff>>8) as u8; idx[bo+15]=poff as u8
106 idx[bo+16]=(plen>>56) as u8; idx[bo+17]=(plen>>48) as u8; idx[bo+18]=(plen>>40) as u8; idx[bo+19]=(plen>>32) as u8; idx[bo+20]=(plen>>24) as u8; idx[bo+21]=(plen>>16) as u8; idx[bo+22]=(plen>>8) as u8; idx[bo+23]=plen as u8
107 placed = 1
108 } else { bk = (bk + 1) & (nb - 1) }
109 }
110 }
111 }
112 ls = i + 1
113 }
114 i = i + 1
115 }
116 let fa: i64 = sys_openat_wr(idx_path, 0x1a4); if fa < 0 { return 0 - 1 }
117 sys_write(fa, idx, 16 + nb * 24); sys_close(fa)
118 let fb: i64 = sys_openat_wr(blob_path, 0x1a4); if fb < 0 { return 0 - 1 }
119 sys_write(fb, blob, blob_off); sys_close(fb)
120 return nent
121}
122
123// Read an i64 (big-endian) at idx[o].
124func cidx_rd64(p: *u8, o: i64) -> i64 { return ((p[o] as i64)<<56)|((p[o+1] as i64)<<48)|((p[o+2] as i64)<<40)|((p[o+3] as i64)<<32)|((p[o+4] as i64)<<24)|((p[o+5] as i64)<<16)|((p[o+6] as i64)<<8)|(p[o+7] as i64) }
125
126// O(1) lookup: cid (69 chars) -> out_path (NUL-terminated). idx/blob are the mmap'd files; nb = n_buckets.
127// Returns 1 if found, 0 if not.
128func gs_cidindex_lookup(idx: *u8, blob: *u8, nb: i64, cid: *u8, out_path: *u8) -> i64 {
129 let h: i64 = cidx_fnv1a(cid, CIDX_CIDLEN)
130 var bk: i64 = h & (nb - 1)
131 var guard: i64 = 0
132 while guard < nb {
133 let bo: i64 = 16 + bk * 24
134 let ch: i64 = cidx_rd64(idx, bo)
135 if ch == 0 { return 0 }
136 if ch == h {
137 let poff: i64 = cidx_rd64(idx, bo + 8)
138 let plen: i64 = cidx_rd64(idx, bo + 16)
139 var p: i64 = 0; while p < plen { out_path[p] = blob[poff + p]; p = p + 1 }
140 out_path[plen] = 0 as u8
141 return 1
142 }
143 bk = (bk + 1) & (nb - 1)
144 guard = guard + 1
145 }
146 return 0
147}