Skip to main content

enxame_engine/
lib.rs

1//! Sans-io BitTorrent session engine — the download state machine.
2//!
3//! The engine is **transport-free** (sans-io): it consumes typed
4//! [`Event`]s (a peer connected, a peer message arrived, a block was
5//! written to disk, a timer ticked) and emits typed [`Action`]s (send
6//! this message, write this block, this piece verified). The daemon
7//! (`enxamed`) provides the actual sockets and disk; tests drive the
8//! same `on_event` with synthetic events. This is the pleme-io
9//! interpreter idiom — a pure `(state, event) -> (state, actions)` core,
10//! the same shape as mado's overlay FSM and the sui-spec interpreters.
11//!
12//! Scope (M3): the **leech** path — connect, exchange bitfields, become
13//! interested, pipeline block requests rarest-first, assemble + SHA-1
14//! verify pieces, announce completion. Seeding/choke-algorithm and the
15//! endgame refinement layer onto this core (`theory/ENXAME.md` M4).
16
17#![forbid(unsafe_code)]
18
19use std::collections::{BTreeMap, HashMap};
20
21use enxame_bitfield::Bitfield;
22use enxame_metainfo::InfoDict;
23use enxame_peer::{Block, PeerMessage};
24use sha1::{Digest, Sha1};
25
26/// 16 KiB — the canonical block size BitTorrent peers request in.
27pub const BLOCK_LEN: u32 = 16 * 1024;
28/// How many block requests to keep in flight per peer (the pipeline).
29pub const PIPELINE_DEPTH: usize = 8;
30
31/// A peer handle the engine assigns; the daemon maps it to a socket.
32pub type PeerKey = u32;
33
34/// Something happened that the engine must react to.
35#[derive(Debug, Clone)]
36pub enum Event {
37    /// A peer connection completed its handshake and is ready.
38    PeerReady(PeerKey),
39    /// A decoded peer-wire message arrived from a peer.
40    Message(PeerKey, PeerMessage),
41    /// A peer's connection dropped.
42    PeerGone(PeerKey),
43    /// A block we requested was read off the wire and is ready to place
44    /// (the daemon may also persist it; the engine tracks completion).
45    BlockArrived { index: u32, begin: u32, data: Vec<u8> },
46}
47
48/// Something the daemon must do on the engine's behalf.
49#[derive(Debug, Clone, PartialEq, Eq)]
50pub enum Action {
51    /// Send a wire message to a peer.
52    Send(PeerKey, PeerMessage),
53    /// A piece passed SHA-1 verification — persist + announce `Have`.
54    PieceVerified(u32),
55    /// A piece failed verification — its blocks were dropped, re-pick.
56    PieceCorrupt(u32),
57    /// Every piece is verified — the torrent is complete.
58    Complete,
59    /// Drop a misbehaving peer.
60    Disconnect(PeerKey),
61}
62
63/// Per-peer protocol state (the four BEP-3 booleans + their bitfield +
64/// our in-flight requests to them).
65#[derive(Debug, Clone)]
66struct Peer {
67    am_choking: bool,
68    am_interested: bool,
69    peer_choking: bool,
70    #[allow(dead_code)] // tracked for the future choke algorithm
71    peer_interested: bool,
72    has: Bitfield,
73    /// Blocks we've requested from this peer and not yet received.
74    in_flight: Vec<Block>,
75}
76
77impl Peer {
78    fn new(num_pieces: usize) -> Self {
79        Self {
80            am_choking: true,
81            am_interested: false,
82            peer_choking: true,
83            peer_interested: false,
84            has: Bitfield::new(num_pieces),
85            in_flight: Vec::new(),
86        }
87    }
88}
89
90/// In-progress assembly of one piece: the blocks received so far.
91#[derive(Debug, Clone)]
92struct PieceAssembly {
93    /// `begin` → block bytes, kept sorted so we can concatenate.
94    blocks: BTreeMap<u32, Vec<u8>>,
95    received: u32,
96    total: u32,
97}
98
99/// The download session for one torrent.
100pub struct Session {
101    info: InfoDict,
102    /// Pieces we have verified.
103    have: Bitfield,
104    /// Pieces currently being assembled.
105    assembling: HashMap<u32, PieceAssembly>,
106    /// Per-piece availability across connected peers (rarest-first).
107    availability: Vec<u32>,
108    peers: HashMap<PeerKey, Peer>,
109    num_pieces: usize,
110}
111
112impl Session {
113    /// Start a session for a torrent we hold no pieces of yet.
114    #[must_use]
115    pub fn new(info: InfoDict) -> Self {
116        let num_pieces = info.piece_count();
117        Self {
118            have: Bitfield::new(num_pieces),
119            assembling: HashMap::new(),
120            availability: vec![0; num_pieces],
121            peers: HashMap::new(),
122            num_pieces,
123            info,
124        }
125    }
126
127    /// Pieces verified so far.
128    #[must_use]
129    pub fn have_count(&self) -> usize {
130        self.have.count()
131    }
132
133    /// Total pieces.
134    #[must_use]
135    pub fn piece_count(&self) -> usize {
136        self.num_pieces
137    }
138
139    /// Whether the whole torrent is downloaded + verified.
140    #[must_use]
141    pub fn is_complete(&self) -> bool {
142        self.have.is_complete()
143    }
144
145    /// The byte length of piece `index` (the last piece is short).
146    fn piece_len(&self, index: u32) -> u32 {
147        let total = self.info.total_length();
148        let plen = self.info.piece_length;
149        let start = u64::from(index) * plen;
150        u32::try_from((total - start).min(plen)).unwrap_or(u32::MAX)
151    }
152
153    /// Drive the state machine with one event; return the actions to
154    /// perform. Pure: the only effects are the returned [`Action`]s.
155    pub fn on_event(&mut self, event: Event) -> Vec<Action> {
156        match event {
157            Event::PeerReady(key) => {
158                self.peers.entry(key).or_insert_with(|| Peer::new(self.num_pieces));
159                // Greet with our bitfield (BEP-3: optional but standard).
160                vec![Action::Send(key, PeerMessage::Bitfield(self.have.as_bytes().to_vec()))]
161            }
162            Event::PeerGone(key) => {
163                if let Some(peer) = self.peers.remove(&key) {
164                    for i in peer.has.iter_set() {
165                        self.availability[i] = self.availability[i].saturating_sub(1);
166                    }
167                }
168                Vec::new()
169            }
170            Event::Message(key, msg) => self.on_message(key, &msg),
171            Event::BlockArrived { index, begin, data } => self.place_block(index, begin, data),
172        }
173    }
174
175    fn on_message(&mut self, key: PeerKey, msg: &PeerMessage) -> Vec<Action> {
176        let mut actions = Vec::new();
177        match msg {
178            PeerMessage::Choke => {
179                if let Some(p) = self.peers.get_mut(&key) {
180                    p.peer_choking = true;
181                    p.in_flight.clear(); // choked: assume our requests are dropped
182                }
183            }
184            PeerMessage::Unchoke => {
185                if let Some(p) = self.peers.get_mut(&key) {
186                    p.peer_choking = false;
187                }
188                actions.extend(self.fill_pipeline(key));
189            }
190            PeerMessage::Interested => {
191                if let Some(p) = self.peers.get_mut(&key) {
192                    p.peer_interested = true;
193                }
194            }
195            PeerMessage::NotInterested => {
196                if let Some(p) = self.peers.get_mut(&key) {
197                    p.peer_interested = false;
198                }
199            }
200            PeerMessage::Have(idx) => {
201                if let Some(p) = self.peers.get_mut(&key) {
202                    let i = *idx as usize;
203                    if i < self.num_pieces && !p.has.has(i) {
204                        p.has.set(i);
205                        self.availability[i] += 1;
206                    }
207                }
208                actions.extend(self.update_interest(key));
209            }
210            PeerMessage::Bitfield(bytes) => {
211                if let Ok(bf) = Bitfield::from_bytes(bytes, self.num_pieces) {
212                    if let Some(p) = self.peers.get_mut(&key) {
213                        for i in p.has.iter_set() {
214                            self.availability[i] = self.availability[i].saturating_sub(1);
215                        }
216                        for i in bf.iter_set() {
217                            self.availability[i] += 1;
218                        }
219                        p.has = bf;
220                    }
221                    actions.extend(self.update_interest(key));
222                } else {
223                    actions.push(Action::Disconnect(key));
224                }
225            }
226            PeerMessage::Piece { index, begin, data } => {
227                // Clear the satisfied in-flight request.
228                if let Some(p) = self.peers.get_mut(&key) {
229                    p.in_flight.retain(|b| !(b.index == *index && b.begin == *begin));
230                }
231                actions.extend(self.place_block(*index, *begin, data.clone()));
232                actions.extend(self.fill_pipeline(key));
233            }
234            // Inbound Request/Cancel/Port/Extended/KeepAlive/Unknown: the
235            // leech core ignores (seeding + DHT + ext layer on top later).
236            _ => {}
237        }
238        actions
239    }
240
241    /// Send `Interested` if the peer has a piece we lack and we aren't
242    /// already interested; trigger pipeline fill if already unchoked.
243    fn update_interest(&mut self, key: PeerKey) -> Vec<Action> {
244        let mut actions = Vec::new();
245        let wants = self
246            .peers
247            .get(&key)
248            .is_some_and(|p| p.has.difference(&self.have).next().is_some());
249        if let Some(p) = self.peers.get_mut(&key) {
250            if wants && !p.am_interested {
251                p.am_interested = true;
252                actions.push(Action::Send(key, PeerMessage::Interested));
253            }
254            if !p.peer_choking {
255                actions.extend(self.fill_pipeline(key));
256            }
257        }
258        actions
259    }
260
261    /// Request blocks from `key` until its pipeline is full, rarest-first
262    /// over the pieces it has that we still need.
263    fn fill_pipeline(&mut self, key: PeerKey) -> Vec<Action> {
264        let mut actions = Vec::new();
265        // Snapshot what's requestable from this peer.
266        let (peer_choking, slots, candidate_pieces) = {
267            let Some(p) = self.peers.get(&key) else { return actions };
268            let slots = PIPELINE_DEPTH.saturating_sub(p.in_flight.len());
269            let mut pieces: Vec<u32> = (0..self.num_pieces)
270                .filter(|&i| !self.have.has(i) && p.has.has(i))
271                .map(|i| i as u32)
272                .collect();
273            // Rarest first.
274            pieces.sort_by_key(|&i| self.availability[i as usize]);
275            (p.peer_choking, slots, pieces)
276        };
277        if peer_choking || slots == 0 {
278            return actions;
279        }
280        let mut requested = 0;
281        for index in candidate_pieces {
282            if requested >= slots {
283                break;
284            }
285            for block in self.needed_blocks(index) {
286                if requested >= slots {
287                    break;
288                }
289                let already = self
290                    .peers
291                    .get(&key)
292                    .is_some_and(|p| p.in_flight.iter().any(|b| *b == block));
293                if already {
294                    continue;
295                }
296                if let Some(p) = self.peers.get_mut(&key) {
297                    p.in_flight.push(block);
298                }
299                actions.push(Action::Send(key, PeerMessage::Request(block)));
300                requested += 1;
301            }
302        }
303        actions
304    }
305
306    /// The blocks of `index` we still need (not yet assembled).
307    fn needed_blocks(&self, index: u32) -> Vec<Block> {
308        let plen = self.piece_len(index);
309        let have_offsets: &BTreeMap<u32, Vec<u8>> = self
310            .assembling
311            .get(&index)
312            .map_or(&EMPTY_BLOCKS, |a| &a.blocks);
313        let mut blocks = Vec::new();
314        let mut begin = 0u32;
315        while begin < plen {
316            let length = BLOCK_LEN.min(plen - begin);
317            if !have_offsets.contains_key(&begin) {
318                blocks.push(Block { index, begin, length });
319            }
320            begin += length;
321        }
322        blocks
323    }
324
325    /// Place a received block; if the piece is now whole, verify it.
326    fn place_block(&mut self, index: u32, begin: u32, data: Vec<u8>) -> Vec<Action> {
327        if index as usize >= self.num_pieces || self.have.has(index as usize) {
328            return Vec::new(); // already have it / out of range
329        }
330        let plen = self.piece_len(index);
331        let entry = self.assembling.entry(index).or_insert_with(|| PieceAssembly {
332            blocks: BTreeMap::new(),
333            received: 0,
334            total: plen,
335        });
336        if entry.blocks.insert(begin, data).is_none() {
337            entry.received += BLOCK_LEN.min(plen - begin);
338        }
339        if entry.received >= entry.total {
340            return self.verify_piece(index);
341        }
342        Vec::new()
343    }
344
345    fn verify_piece(&mut self, index: u32) -> Vec<Action> {
346        let Some(assembly) = self.assembling.remove(&index) else {
347            return Vec::new();
348        };
349        let mut buf = Vec::with_capacity(assembly.total as usize);
350        for (_, block) in assembly.blocks {
351            buf.extend_from_slice(&block);
352        }
353        let digest: [u8; 20] = Sha1::digest(&buf).into();
354        let expected = self.info.pieces.get(index as usize).copied().unwrap_or([0; 20]);
355        if digest == expected {
356            self.have.set(index as usize);
357            let mut actions = vec![Action::PieceVerified(index)];
358            // Announce `Have` to all peers.
359            for &key in self.peers.keys() {
360                actions.push(Action::Send(key, PeerMessage::Have(index)));
361            }
362            if self.have.is_complete() {
363                actions.push(Action::Complete);
364            }
365            actions
366        } else {
367            vec![Action::PieceCorrupt(index)]
368        }
369    }
370}
371
372// A shared empty map so `needed_blocks` can borrow when no assembly yet.
373use std::sync::LazyLock;
374static EMPTY_BLOCKS: LazyLock<BTreeMap<u32, Vec<u8>>> = LazyLock::new(BTreeMap::new);
375
376#[cfg(test)]
377mod tests {
378    use super::*;
379    use enxame_metainfo::Layout;
380
381    /// Build a 2-piece torrent over `data`, piece_length 8.
382    fn info_for(data: &[u8], piece_length: u64) -> InfoDict {
383        let pieces: Vec<[u8; 20]> = data
384            .chunks(piece_length as usize)
385            .map(|c| Sha1::digest(c).into())
386            .collect();
387        InfoDict {
388            name: "t".into(),
389            piece_length,
390            pieces,
391            layout: Layout::SingleFile { length: data.len() as u64 },
392            private: false,
393        }
394    }
395
396    #[test]
397    fn greets_a_ready_peer_with_a_bitfield() {
398        let mut s = Session::new(info_for(b"hello world!", 8));
399        let actions = s.on_event(Event::PeerReady(1));
400        assert!(matches!(actions.as_slice(), [Action::Send(1, PeerMessage::Bitfield(_))]));
401    }
402
403    #[test]
404    fn becomes_interested_and_requests_rarest_first() {
405        let mut s = Session::new(info_for(b"hello world!", 8)); // 2 pieces (8 + 4)
406        s.on_event(Event::PeerReady(1));
407        // Peer advertises it has both pieces.
408        let mut bf = Bitfield::new(2);
409        bf.set(0);
410        bf.set(1);
411        let acts = s.on_event(Event::Message(1, PeerMessage::Bitfield(bf.as_bytes().to_vec())));
412        assert!(acts.contains(&Action::Send(1, PeerMessage::Interested)));
413        // Unchoke us → we request blocks.
414        let acts = s.on_event(Event::Message(1, PeerMessage::Unchoke));
415        let requests: Vec<_> = acts.iter().filter(|a| matches!(a, Action::Send(_, PeerMessage::Request(_)))).collect();
416        assert!(!requests.is_empty(), "expected block requests after unchoke");
417    }
418
419    #[test]
420    fn assembles_and_verifies_a_piece_end_to_end() {
421        let data = b"hello world!"; // 12 bytes, piece_length 8 → piece0=8, piece1=4
422        let mut s = Session::new(info_for(data, 8));
423        s.on_event(Event::PeerReady(1));
424        let mut bf = Bitfield::new(2);
425        bf.set(0);
426        s.on_event(Event::Message(1, PeerMessage::Bitfield(bf.as_bytes().to_vec())));
427        s.on_event(Event::Message(1, PeerMessage::Unchoke));
428        // Deliver piece 0's single block (8 bytes ≤ BLOCK_LEN).
429        let acts = s.on_event(Event::Message(
430            1,
431            PeerMessage::Piece { index: 0, begin: 0, data: data[..8].to_vec() },
432        ));
433        assert!(acts.contains(&Action::PieceVerified(0)));
434        assert_eq!(s.have_count(), 1);
435        assert!(!s.is_complete());
436    }
437
438    #[test]
439    fn rejects_a_corrupt_piece() {
440        let data = b"hello world!";
441        let mut s = Session::new(info_for(data, 8));
442        s.on_event(Event::PeerReady(1));
443        let acts = s.on_event(Event::Message(
444            1,
445            PeerMessage::Piece { index: 0, begin: 0, data: vec![0xff; 8] }, // wrong bytes
446        ));
447        assert!(acts.contains(&Action::PieceCorrupt(0)));
448        assert_eq!(s.have_count(), 0);
449    }
450
451    #[test]
452    fn completes_when_all_pieces_verify() {
453        let data = b"abcdefgh"; // one 8-byte piece
454        let mut s = Session::new(info_for(data, 8));
455        s.on_event(Event::PeerReady(1));
456        let acts = s.on_event(Event::Message(
457            1,
458            PeerMessage::Piece { index: 0, begin: 0, data: data.to_vec() },
459        ));
460        assert!(acts.contains(&Action::Complete));
461        assert!(s.is_complete());
462    }
463}