nx_endgame.nx source

1// nx_endgame.nx -- endgame last-piece racing for the fork-per-peer download model. 2// 3// module: nishi-core.torrent.endgame 4// depends: nx_avail_map.nx (am_open/am_load + the locked-RMW flock idiom; transitively nx_pm_rarest, 5// nx_pw_bitfield_has, nx_syscalls), nx_stream_picker.nx (nx_sp_in_endgame -- the canonical 6// endgame-entry threshold; importing it un-orphans the streaming smart layer). 7// capability: SWARM_INTELLIGENCE 8// 9// WHY: the dominant source of completion-time variance is the ONE slow peer holding the last piece. 10// Our forked children normally AVOID duplicating work (they skip pieces already done via the donefile), 11// which is correct for the bulk of a download. But in the TAIL -- when only a few obtainable pieces 12// remain and they are all already in-flight on some (possibly slow) peer -- a child with nothing fresh 13// should RACE one of those in-flight pieces from a second peer and let the faster connection win. This 14// organ is that decision plus the shared IN-FLIGHT refcount map the children coordinate through. 15// 16// HONEST BOUNDARY: a piece that NO connected peer has (availability 0) can never be raced -- you cannot 17// download data the swarm does not hold. eg_pick never returns such a piece; eg_obtainable_remaining 18// excludes them. That is exactly the "stuck at 99.x%, no seeder has the last piece" reality -- the fix 19// for THAT is webseed (BEP-19) / PEX (BEP-11), a later rung, not endgame. 20// 21// FILE FORMAT (download.inflight): npc bytes; byte p = saturating count (0..255) of children currently 22// downloading piece p. Locked read-modify-write (same flock floor as the availability map). 23 24import "nx_avail_map.nx" 25import "nx_stream_picker.nx" 26 27// open O_RDWR|O_CREAT, NO truncate (the shared worker idiom). 28func eg_open(path: *u8) -> i64 { return __syscall(SYS_OPENAT, AT_FDCWD, path as i64, 0x42, 0x1a4, 0, 0) } 29 30// zero the first npc bytes -- parent calls once/session before forking (in-flight is per-session). 31func eg_init(path: *u8, npc: i64) -> i64 { 32 let fd: i64 = eg_open(path); if fd < 0 { return 0 - 1 } 33 let z: *u8 = sys_mmap(npc + 16); sys_lseek(fd, 0, 0); sys_write(fd, z, npc); sys_close(fd); return 0 34} 35 36// child claims it is about to download piece p (LOCKED +1, saturating). 37func eg_mark(path: *u8, p: i64) -> i64 { 38 let fd: i64 = eg_open(path); if fd < 0 { return 0 - 1 } 39 sys_flock(fd, SYS_LOCK_EX) 40 let b: *u8 = sys_mmap(16); sys_lseek(fd, p, 0); let r: i64 = sys_read(fd, b, 1) 41 var c: i64 = 0; if r == 1 { c = b[0] as i64 } 42 if c < 255 { b[0] = (c + 1) as u8 } 43 sys_lseek(fd, p, 0); sys_write(fd, b, 1) 44 sys_flock(fd, SYS_LOCK_UN); sys_close(fd); return 0 45} 46 47// child finished or abandoned piece p (LOCKED -1, floor 0). 48func eg_clear(path: *u8, p: i64) -> i64 { 49 let fd: i64 = eg_open(path); if fd < 0 { return 0 - 1 } 50 sys_flock(fd, SYS_LOCK_EX) 51 let b: *u8 = sys_mmap(16); sys_lseek(fd, p, 0); let r: i64 = sys_read(fd, b, 1) 52 var c: i64 = 0; if r == 1 { c = b[0] as i64 } 53 if c > 0 { c = c - 1 } 54 b[0] = c as u8 55 sys_lseek(fd, p, 0); sys_write(fd, b, 1) 56 sys_flock(fd, SYS_LOCK_UN); sys_close(fd); return 0 57} 58 59// count NEEDED + OBTAINABLE pieces (done==0 AND avail>0) -- the outstanding count that drives endgame 60// entry. Unobtainable pieces (avail==0) can never complete, so they are NOT raceable outstanding work. 61func eg_obtainable_remaining(donebits: *u8, av: *i64, npc: i64) -> i64 { 62 var c: i64 = 0; var p: i64 = 0 63 while p < npc { if (donebits[p] as i64) == 0 { if av[p] > 0 { c = c + 1 } } p = p + 1 } 64 return c 65} 66 67// THE PICK. Two phases: 68// (1) NORMAL: rarest NEEDED piece this peer HAS that is NOT already in-flight (no duplicate work). 69// (2) ENDGAME: if (1) finds nothing fresh AND obtainable-remaining <= threshold, RACE -- the rarest 70// NEEDED piece this peer HAS even if in-flight (a 2nd peer races the slow holder; caller cancels 71// the loser on first PIECE). Reuses the canonical nx_pm_rarest (av>0 + done filter via eff) and 72// nx_sp_in_endgame (the threshold). Returns the piece index, or -1 (peer has nothing needed, or 73// not yet endgame and all its needed pieces are in-flight -> caller waits / frees the slot). 74// Caller passes scratch av/eff/inf (>= npc i64 each) to avoid per-pick churn. 75func eg_pick(availpath: *u8, inflightpath: *u8, donebits: *u8, peerbits: *u8, byte_len: i64, havebits: i64, npc: i64, threshold: i64, av: *i64, eff: *i64, inf: *i64) -> i64 { 76 am_load(availpath, av, npc) 77 am_load(inflightpath, inf, npc) 78 // A fast-ext have-all seeder sends NO bitfield (havebits==0) so it never contributed to the avail 79 // map -> its pieces could read avail 0 and be wrongly skipped (nx_pm_rarest needs avail>0). The 80 // seeder HAS every piece, so floor availability at 1 for the pick (local scratch only, not the file). 81 if havebits == 0 { var s: i64 = 0; while s < npc { if av[s] == 0 { av[s] = 1 } s = s + 1 } } 82 // phase 1: skip if done OR peer-lacks OR in-flight 83 var p: i64 = 0 84 while p < npc { 85 var skip: i64 = 0 86 if (donebits[p] as i64) == 1 { skip = 1 } 87 else { if havebits == 1 { if nx_pw_bitfield_has(peerbits, byte_len, p) == 0 { skip = 1 } } } 88 if skip == 0 { if inf[p] > 0 { skip = 1 } } 89 eff[p] = skip 90 p = p + 1 91 } 92 let fresh: i64 = nx_pm_rarest(av, eff, npc) 93 if fresh >= 0 { return fresh } 94 // phase 2: endgame race -- only when few obtainable pieces remain 95 let outstanding: i64 = eg_obtainable_remaining(donebits, av, npc) 96 if nx_sp_in_endgame(outstanding, threshold) == 0 { return 0 - 1 } 97 p = 0 98 while p < npc { 99 var skip2: i64 = 0 100 if (donebits[p] as i64) == 1 { skip2 = 1 } 101 else { if havebits == 1 { if nx_pw_bitfield_has(peerbits, byte_len, p) == 0 { skip2 = 1 } } } 102 eff[p] = skip2 103 p = p + 1 104 } 105 return nx_pm_rarest(av, eff, npc) // in-flight allowed (race); still avail>0 + peer-has + needed 106}