Skip to main content

scionic_merkletree/
sync.rs

1//! Syncing by file hash and chunk number.
2//!
3//! * A [`Responder`] answers a receiver's requests from a store.
4//! * [`fetch`] takes a whole tree from a peer into a store, from the top
5//!   down, and skips whatever the store holds already.
6//! * A [`Remote`] reads parts of a tree straight from a peer: one name in a
7//!   folder, a branch of entries, or a stretch of a file's bytes. It needs no
8//!   store, and takes nothing but the parts it is asked for.
9//! * [`export`] and [`import`] carry a whole tree as one stream of frames.
10//! * [`serve`] answers requests on a connection, and a [`StreamPeer`] asks
11//!   them there.
12//!
13//! Nothing is compared between the two sides. The receiver walks down from
14//! the root it trusts, and every answer is checked as it arrives against a
15//! hash that is already checked. An answer that is forged, that belongs
16//! somewhere else, or that was not asked for is refused. With each request
17//! goes the longest frame that can answer it, so a peer cannot make a
18//! receiver set aside more memory than the tree it trusts calls for.
19
20use crate::fastcdc::FASTCDC_MIN_SIZE;
21use crate::format::{
22    check_name, ChunkRef, Chunking, Entry, FileList, FolderBranch, Kind, OpenFile, OpenFolder,
23    Record, Target, LIST_ITEM_BYTES, MAX_CARRIED_NODES, MAX_ENTRY_BYTES, MAX_FOLDER_DEPTH,
24    MAX_NAME_BYTES, MAX_RECORD_BYTES,
25};
26use crate::hash::{Hash, Root};
27use crate::intake::{Arrived, ChunkFrames, Intake, Summary, TakingIn};
28use crate::read::{file_of, folder_of, record_of};
29use crate::store::{check_chunk, damaged, lent, ChunksAhead, Store, Stored};
30use crate::wire::{
31    file_branch_frame, file_list_frame, folder_branch_frame, folder_list_frame, have_frame,
32    read_next, refused_frame, write_end, write_frame, write_framed, Frame, HaveMap, Next, Refusal,
33    Request, BUNDLE_MAGIC, FRAME_CHUNK, FRAME_FILE_LIST, FRAME_FOLDER_LIST, FRAME_REFUSED,
34    MAX_REQUEST_BYTES,
35};
36use crate::{Error, Result};
37use std::collections::HashSet;
38use std::io::{Read, Write};
39use std::sync::{Arc, Mutex, TryLockError};
40
41/// The most requests [`fetch`] sends before it looks at what is still wanted.
42const REQUESTS_PER_ROUND: usize = 64;
43/// The most items of a list that one answer shows.
44const MAX_BRANCH_ITEMS: u64 = 16_384;
45/// The most chunks that one answer sends.
46const MAX_CHUNKS_PER_ANSWER: u64 = 256;
47
48fn invalid(detail: &str) -> Error {
49    Error::InvalidData {
50        detail: detail.to_owned(),
51    }
52}
53
54fn peer_error(detail: &str) -> Error {
55    Error::Peer {
56        detail: detail.to_owned(),
57    }
58}
59
60const OTHER_KIND: Error = Error::NotWanted {
61    what: "an answer of another kind than was asked for",
62};
63const TOO_MUCH: Error = Error::NotWanted {
64    what: "more than was asked for",
65};
66
67/// The bytes of a branch's frame that are there whatever it shows: its first
68/// byte, the list's count, the branch's start, how many items it shows, and how
69/// many nodes it carries.
70const BRANCH_FIXED_BYTES: usize = 23;
71
72/// How many bytes of requests a [`StreamPeer`] sends ahead of their answers.
73/// It is small on purpose. The other end answers one request before it reads
74/// the next, so requests that are sent ahead wait in the connection, and a
75/// connection that could not hold them would leave both ends waiting for
76/// each other. Every connection holds this much.
77pub const REQUESTS_AHEAD_BYTES: usize = 2048;
78
79/// Refuses a frame that is longer than its asker takes.
80fn within(limit: usize, frame: &[u8]) -> Result<()> {
81    if frame.len() > limit {
82        return Err(Error::LimitExceeded {
83            what: "a frame",
84            limit: limit as u64,
85            requested: frame.len() as u64,
86        });
87    }
88    Ok(())
89}
90
91/// The longest frame that shows `entries` entries of a folder.
92fn folder_branch_limit(entries: u64) -> usize {
93    let carried = MAX_CARRIED_NODES * (42 + MAX_NAME_BYTES);
94    usize::try_from(entries)
95        .unwrap_or(usize::MAX)
96        .saturating_mul(MAX_ENTRY_BYTES)
97        .saturating_add(BRANCH_FIXED_BYTES + carried)
98}
99
100/// The longest frame that shows `items` items of a file's list.
101fn file_branch_limit(items: u64) -> usize {
102    usize::try_from(items)
103        .unwrap_or(usize::MAX)
104        .saturating_mul(LIST_ITEM_BYTES)
105        .saturating_add(BRANCH_FIXED_BYTES + MAX_CARRIED_NODES * 40)
106}
107
108/// The most chunks that `length` bytes of a file can lie in. All of them but
109/// the first and the last lie in the stretch whole, and no chunk but a
110/// file's last is shorter than the tree's way of chunking allows.
111fn most_chunks_in(chunking: Chunking, length: u64) -> u64 {
112    let shortest = match chunking {
113        Chunking::FastCdcV1 => FASTCDC_MIN_SIZE as u64 + 1,
114        Chunking::Fixed(chunk) => u64::from(chunk.get()),
115    };
116    length / shortest + 2
117}
118
119/// Something that answers requests: a connection to another machine, or a
120/// [`Responder`] in this one.
121pub trait Peer {
122    /// Sends one request, and hands each frame of the answer to `on_frame`
123    /// in the order the frames come. An error from `on_frame` ends the
124    /// answer, and is what `ask` returns.
125    ///
126    /// `limit` is the longest frame the asker takes in answer. A frame that
127    /// is longer is an error, and a peer on a connection refuses it by its
128    /// length, before any of it is read.
129    fn ask(
130        &mut self,
131        request: &[u8],
132        limit: usize,
133        on_frame: &mut dyn FnMut(&[u8]) -> Result<()>,
134    ) -> Result<()>;
135
136    /// Sends several requests, each with its limit, and hands each frame to
137    /// `on_frame` with the place of the request that it answers. Answers
138    /// come in the order of the requests.
139    ///
140    /// This asks one at a time. A peer on a connection sends requests ahead
141    /// of their answers, and saves the waiting between them.
142    fn ask_all(
143        &mut self,
144        requests: &[(Vec<u8>, usize)],
145        on_frame: &mut dyn FnMut(usize, &[u8]) -> Result<()>,
146    ) -> Result<()> {
147        for (place, (request, limit)) in requests.iter().enumerate() {
148            self.ask(request, *limit, &mut |frame| on_frame(place, frame))?;
149        }
150        Ok(())
151    }
152}
153
154/// How many items of lists a responder keeps between requests, for each of
155/// the three kinds it keeps, unless it is told otherwise. This many items of
156/// files' lists stand for about half a terabyte of files.
157const RECENT_ITEMS: u64 = 1 << 18;
158
159/// The most lists of one kind that a responder keeps, however short.
160const RECENT_LISTS: usize = 64;
161
162/// The lists that were used last. Reading a list from the store and hashing
163/// it takes a pass over the whole of it, so a list that was asked about is
164/// kept for the next request. Lists are weighed by their items, and the ones
165/// used longest ago go first.
166struct Recent<T> {
167    kept: Vec<(Hash, Arc<T>, u64)>,
168}
169
170impl<T> Recent<T> {
171    fn new() -> Self {
172        Self { kept: Vec::new() }
173    }
174
175    fn get(&mut self, hash: &Hash) -> Option<Arc<T>> {
176        let at = self.kept.iter().position(|(kept, _, _)| kept == hash)?;
177        let found = self.kept.remove(at);
178        let value = Arc::clone(&found.1);
179        self.kept.push(found);
180        Some(value)
181    }
182
183    /// Keeps `value`, and lets go of older ones while there are more than
184    /// `most` items or too many lists. The newest one always stays.
185    fn keep(&mut self, hash: Hash, value: Arc<T>, items: u64, most: u64) {
186        self.kept.retain(|(kept, _, _)| *kept != hash);
187        self.kept.push((hash, value, items.max(1)));
188        let mut total: u64 = self.kept.iter().map(|(_, _, items)| *items).sum();
189        while self.kept.len() > 1 && (total > most || self.kept.len() > RECENT_LISTS) {
190            total -= self.kept.remove(0).2;
191        }
192    }
193}
194
195/// Answers requests from a store.
196///
197/// It answers for whatever the store holds, by hash. It gives what it has and
198/// says so when it has nothing: a receiver never has to trust it, because a
199/// receiver checks every answer.
200///
201/// One responder serves many threads at once.
202pub struct Responder<'s> {
203    store: &'s dyn Store,
204    /// The files whose lists were read last.
205    lists: Mutex<Recent<FileList>>,
206    /// The files and the folders whose trees were built last. Showing a
207    /// part of a long list needs its tree.
208    files: Mutex<Recent<OpenFile>>,
209    folders: Mutex<Recent<OpenFolder>>,
210    /// The frame that the last chunk was sent in, filled again for the next.
211    frame: Mutex<Vec<u8>>,
212    /// Reads the chunks of an answer ahead of sending them, into frames
213    /// that are filled again for the next answer.
214    ahead: Mutex<ChunksAhead>,
215    threads: usize,
216    recent: u64,
217    have: bool,
218}
219
220fn lock<T>(mutex: &Mutex<T>) -> std::sync::MutexGuard<'_, T> {
221    mutex
222        .lock()
223        .unwrap_or_else(|poisoned| poisoned.into_inner())
224}
225
226/// Fills `frame` with the frame of a chunk, from its start.
227fn refill(frame: &mut Vec<u8>, chunk: &[u8]) {
228    frame.clear();
229    frame.push(FRAME_CHUNK);
230    frame.extend_from_slice(chunk);
231}
232
233impl<'s> Responder<'s> {
234    pub fn new(store: &'s dyn Store) -> Self {
235        Self {
236            store,
237            lists: Mutex::new(Recent::new()),
238            files: Mutex::new(Recent::new()),
239            folders: Mutex::new(Recent::new()),
240            frame: Mutex::new(Vec::new()),
241            ahead: Mutex::new(ChunksAhead::new()),
242            threads: 0,
243            recent: RECENT_ITEMS,
244            have: true,
245        }
246    }
247
248    /// How many items of lists are kept between requests, for each of the
249    /// three kinds: files' lists, files' trees and folders' trees. A list
250    /// that is not kept is read from the store and hashed again when it is
251    /// next asked about, which takes a pass over the whole of it. An item
252    /// kept costs some tens of bytes for a file and some hundreds for a
253    /// folder. The list that was used last is kept whatever its length.
254    pub fn recent(mut self, items: u64) -> Self {
255        self.recent = items;
256        self
257    }
258
259    /// Whether a peer is told which chunks of a file are held here. Telling
260    /// takes a look into the store for every chunk of the file, so a
261    /// responder that serves strangers may leave it off. It then answers
262    /// such a request as it does for a file it does not hold.
263    pub fn have(mut self, on: bool) -> Self {
264        self.have = on;
265        self
266    }
267
268    /// How many threads read the chunks of one answer from the store, ahead
269    /// of sending them: 1 is the thread that answers alone, and zero, the
270    /// default, is one for each core. Several are worth it when reading a
271    /// chunk takes longer than sending it, as from a disk to a fast
272    /// receiver. With several, a responder keeps up to 64 MiB of memory
273    /// between answers, to read the chunks of the next one into. A responder
274    /// that serves many peers at once may give each answer one thread, which
275    /// keeps memory for one chunk.
276    pub fn threads(mut self, threads: usize) -> Self {
277        self.threads = threads;
278        self.ahead = Mutex::new(ChunksAhead::with_threads(threads));
279        self
280    }
281
282    fn file_list(&self, file: &Hash) -> Result<Option<Arc<FileList>>> {
283        if let Some(list) = lock(&self.lists).get(file) {
284            return Ok(Some(list));
285        }
286        if let Some(open) = lock(&self.files).get(file) {
287            return Ok(Some(open.shared_list()));
288        }
289        let Some(bytes) = self.store.get(Stored::FileList, file)? else {
290            return Ok(None);
291        };
292        let list = FileList::decode(&bytes)
293            .ok()
294            .filter(|list| list.hash() == file)
295            .ok_or_else(|| damaged("a stored file's list", file))?;
296        let list = Arc::new(list);
297        lock(&self.lists).keep(*file, Arc::clone(&list), list.count(), self.recent);
298        Ok(Some(list))
299    }
300
301    fn open_file(&self, file: &Hash) -> Result<Option<Arc<OpenFile>>> {
302        if let Some(open) = lock(&self.files).get(file) {
303            return Ok(Some(open));
304        }
305        // Looked up on a line of its own: the lock is let go before the
306        // list is hashed, so that other threads are not kept waiting.
307        let listed = lock(&self.lists).get(file);
308        let open = match listed {
309            Some(list) => OpenFile::shared(list)?,
310            None => {
311                let Some(bytes) = self.store.get(Stored::FileList, file)? else {
312                    return Ok(None);
313                };
314                // Read and hashed once, for the list and for its tree.
315                OpenFile::decode(&bytes)
316                    .ok()
317                    .filter(|open| open.list().hash() == file)
318                    .ok_or_else(|| damaged("a stored file's list", file))?
319            }
320        };
321        let open = Arc::new(open);
322        let items = open.list().count();
323        lock(&self.files).keep(*file, Arc::clone(&open), items, self.recent);
324        Ok(Some(open))
325    }
326
327    fn open_folder(&self, folder: &Hash) -> Result<Option<Arc<OpenFolder>>> {
328        if let Some(open) = lock(&self.folders).get(folder) {
329            return Ok(Some(open));
330        }
331        let Some(bytes) = self.store.get(Stored::FolderList, folder)? else {
332            return Ok(None);
333        };
334        let open = OpenFolder::decode(&bytes)
335            .ok()
336            .filter(|open| open.list().hash() == folder)
337            .ok_or_else(|| damaged("a stored folder's list", folder))?;
338        let open = Arc::new(open);
339        let items = open.list().count();
340        lock(&self.folders).keep(*folder, Arc::clone(&open), items, self.recent);
341        Ok(Some(open))
342    }
343
344    /// Hands `with` a frame to send chunks in. It is the responder's own,
345    /// filled again for each chunk and from one request to the next: memory
346    /// that is used again costs much less than fresh memory for every chunk,
347    /// which a system has to find and clear first. A thread that finds it in
348    /// use, by another thread or by an answer that this one is still giving,
349    /// is given a frame of its own, and nobody waits for it.
350    fn with_frame(&self, with: impl FnOnce(&mut Vec<u8>) -> Result<()>) -> Result<()> {
351        match self.frame.try_lock() {
352            Ok(mut kept) => with(&mut kept),
353            // The frame is filled from its start each time, so nothing that a
354            // thread left in it when it panicked is ever sent.
355            Err(TryLockError::Poisoned(poisoned)) => with(&mut poisoned.into_inner()),
356            Err(TryLockError::WouldBlock) => with(&mut Vec::new()),
357        }
358    }
359
360    /// Hands `with` what reads the chunks of an answer ahead of sending
361    /// them. As with [`Responder::with_frame`], a thread that finds it in use
362    /// is given one of its own.
363    fn with_ahead(&self, with: impl FnOnce(&mut ChunksAhead) -> Result<()>) -> Result<()> {
364        match self.ahead.try_lock() {
365            Ok(mut kept) => with(&mut kept),
366            // Each frame is filled from its start each time.
367            Err(TryLockError::Poisoned(poisoned)) => with(&mut poisoned.into_inner()),
368            Err(TryLockError::WouldBlock) => with(&mut ChunksAhead::with_threads(self.threads)),
369        }
370    }
371
372    /// Answers one request. Each frame of the answer is handed to
373    /// `on_frame`. A request that is malformed is an error. A request for
374    /// something the store does not hold is answered with a refusal.
375    pub fn answer(
376        &self,
377        request: &[u8],
378        on_frame: &mut dyn FnMut(&[u8]) -> Result<()>,
379    ) -> Result<()> {
380        let not_held = refused_frame(Refusal::NotHeld);
381        let out_of_range = refused_frame(Refusal::OutOfRange);
382        match Request::decode(request)? {
383            Request::Record(root) => match self.store.get(Stored::Record, root.as_hash())? {
384                Some(bytes) => on_frame(&bytes),
385                None => on_frame(&not_held),
386            },
387            Request::Folder(folder) => match self.store.get(Stored::FolderList, &folder)? {
388                Some(bytes) => on_frame(&folder_list_frame(&bytes)),
389                None => on_frame(&not_held),
390            },
391            Request::File(file) => match self.store.get(Stored::FileList, &file)? {
392                Some(bytes) => on_frame(&file_list_frame(&bytes)),
393                None => on_frame(&not_held),
394            },
395            Request::Chunk(chunk) => self.with_frame(|frame| {
396                let held = lent(self.store, Stored::Chunk, &chunk, &mut |bytes| {
397                    refill(frame, bytes);
398                    Ok(())
399                })?;
400                on_frame(if held {
401                    frame.as_slice()
402                } else {
403                    not_held.as_slice()
404                })
405            }),
406            Request::FolderBranch {
407                folder,
408                start,
409                count,
410            } => {
411                let Some(open) = self.open_folder(&folder)? else {
412                    return on_frame(&not_held);
413                };
414                let total = open.list().count();
415                if total == 0 {
416                    return on_frame(&folder_branch_frame(&FolderBranch::empty()));
417                }
418                if start >= total {
419                    return on_frame(&out_of_range);
420                }
421                let end = total.min(start + u64::from(count).min(MAX_BRANCH_ITEMS));
422                on_frame(&folder_branch_frame(&open.open(start, end)?))
423            }
424            Request::FolderName { folder, name } => match self.open_folder(&folder)? {
425                Some(open) => on_frame(&folder_branch_frame(&open.open_name(&name)?)),
426                None => on_frame(&not_held),
427            },
428            Request::FileBranch { file, start, count } => {
429                let Some(open) = self.open_file(&file)? else {
430                    return on_frame(&not_held);
431                };
432                let total = open.list().count();
433                if start >= total {
434                    return on_frame(&out_of_range);
435                }
436                let end = total.min(start + u64::from(count).min(MAX_BRANCH_ITEMS));
437                on_frame(&file_branch_frame(&open.open(start, end)?))
438            }
439            Request::FileBytes {
440                file,
441                offset,
442                length,
443            } => {
444                let Some(open) = self.open_file(&file)? else {
445                    return on_frame(&not_held);
446                };
447                let size = open.list().size();
448                if offset >= size {
449                    return on_frame(&out_of_range);
450                }
451                let (first, after) = open.chunks_for(offset, length.min(size - offset))?;
452                let after = after.min(first + MAX_BRANCH_ITEMS);
453                on_frame(&file_branch_frame(&open.open(first, after)?))
454            }
455            Request::Chunks { file, start, count } => {
456                let Some(list) = self.file_list(&file)? else {
457                    return on_frame(&not_held);
458                };
459                if start >= list.count() {
460                    return on_frame(&out_of_range);
461                }
462                let count = u64::from(count).min(MAX_CHUNKS_PER_ANSWER) as usize;
463                let items = &list.items()[start as usize..];
464                let items = &items[..count.min(items.len())];
465                // The chunks are read ahead, several at once, and sent in
466                // their order. A frame is lent to `on_frame` for the call
467                // only: the next chunk is read into it. A chunk that the
468                // store holds with another length than the list gives cannot
469                // be it, and is refused as one that is not held.
470                self.with_ahead(|ahead| {
471                    ahead.frames(self.store, items, &mut |frame| {
472                        on_frame(frame.unwrap_or(not_held.as_slice()))
473                    })
474                })
475            }
476            Request::Have(file) => {
477                if !self.have {
478                    return on_frame(&not_held);
479                }
480                let Some(list) = self.file_list(&file)? else {
481                    return on_frame(&not_held);
482                };
483                let mut map = HaveMap::new(list.count())?;
484                for (number, item) in (0_u64..).zip(list.items()) {
485                    if self.store.has(Stored::Chunk, &item.hash)? {
486                        map.set(number)?;
487                    }
488                }
489                on_frame(&have_frame(&map))
490            }
491        }
492    }
493}
494
495impl Peer for Responder<'_> {
496    fn ask(
497        &mut self,
498        request: &[u8],
499        limit: usize,
500        on_frame: &mut dyn FnMut(&[u8]) -> Result<()>,
501    ) -> Result<()> {
502        self.answer(request, &mut |frame| {
503            within(limit, frame)?;
504            on_frame(frame)
505        })
506    }
507}
508
509/// Asks for one frame. A refusal, no frame and more than one frame are
510/// errors.
511fn ask_one(peer: &mut dyn Peer, request: &Request, limit: usize) -> Result<Vec<u8>> {
512    let mut answer: Option<Vec<u8>> = None;
513    peer.ask(&request.encode(), limit, &mut |frame| {
514        if answer.is_some() {
515            return Err(TOO_MUCH);
516        }
517        answer = Some(frame.to_vec());
518        Ok(())
519    })?;
520    let frame = answer.ok_or_else(|| peer_error("gave no answer"))?;
521    if frame.first() == Some(&FRAME_REFUSED) {
522        return Err(match Frame::decode(&frame)? {
523            Frame::Refused(Refusal::OutOfRange) => {
524                peer_error("says that what was asked for lies outside the list or the file")
525            }
526            _ => peer_error("does not hold what was asked for"),
527        });
528    }
529    Ok(frame)
530}
531
532/// Takes the whole tree with this root from a peer into a store.
533///
534/// It goes from the top down: the record, then each folder's entries and
535/// each file's list, then the chunks, by their file and their numbers in it.
536/// Whatever the store holds already is skipped by its hash, be it a chunk,
537/// a file or a whole folder, and wherever it came from. Every answer has to
538/// be exactly what was asked for, and is checked before it is kept.
539///
540/// A fetch that fails can be started again: it goes on from what the store
541/// holds.
542pub fn fetch(store: &dyn Store, root: &Root, peer: &mut dyn Peer) -> Result<Summary> {
543    let mut intake = Intake::new(store, *root)?;
544    // Chunks that come one after another are held, and taken in together
545    // by several threads while the next ones come.
546    let mut frames = [ChunkFrames::new(), ChunkFrames::new()];
547    loop {
548        let requests = intake.requests(REQUESTS_PER_ROUND);
549        if requests.is_empty() {
550            break;
551        }
552        // What each answer has to be is settled before anything is sent.
553        // Nothing that comes in one round changes it: a round asks for each
554        // thing once.
555        let expected: Vec<Vec<Arrived>> = requests
556            .iter()
557            .map(|request| intake.expected(request))
558            .collect();
559        let asks: Vec<(Vec<u8>, usize)> = requests
560            .iter()
561            .map(|request| (request.encode(), intake.answer_limit(request)))
562            .collect();
563        let mut taken = vec![0_usize; requests.len()];
564        let mut refused = vec![false; requests.len()];
565        std::thread::scope(|scope| {
566            let mut taking = TakingIn::new(scope, &mut intake, &mut frames);
567            let asked = peer.ask_all(&asks, &mut |place, frame| {
568                let (Some(expected), Some(taken), Some(refused)) = (
569                    expected.get(place),
570                    taken.get_mut(place),
571                    refused.get_mut(place),
572                ) else {
573                    return Err(peer_error("answered a request that was not sent"));
574                };
575                if *refused {
576                    return Err(peer_error("sent more after it refused"));
577                }
578                if frame.first() == Some(&FRAME_REFUSED) {
579                    Frame::decode(frame)?;
580                    *refused = true;
581                    return Ok(());
582                }
583                let Some(expected) = expected.get(*taken) else {
584                    return Err(TOO_MUCH);
585                };
586                if matches!(expected, Arrived::Chunk(_)) && frame.first() == Some(&FRAME_CHUNK) {
587                    taking.hold_copy(frame, Some(*expected))?;
588                } else {
589                    // What came before is taken in first.
590                    taking.intake()?.accept_expected(frame, *expected)?;
591                }
592                *taken += 1;
593                Ok(())
594            });
595            // What came before a failure is taken in first, and its own
596            // failure is the one given.
597            taking.finish().and(asked)
598        })?;
599        if taken.contains(&0) {
600            return Err(peer_error("does not hold what the tree needs"));
601        }
602    }
603    intake.finish()
604}
605
606/// A branch of a folder's entries, as a peer showed it and as it was checked.
607#[derive(Clone, Debug, Eq, PartialEq)]
608pub struct Entries {
609    /// How many entries the folder has in all.
610    pub total: u64,
611    /// The place of the first entry here.
612    pub start: u64,
613    pub entries: Vec<Entry>,
614}
615
616/// Reads parts of one tree straight from a peer, with nothing kept.
617///
618/// It starts from a root that the caller trusts. Each thing it hands back
619/// was shown by the peer and checked against that root: an entry by its
620/// place in its folder, and bytes by their place in their file.
621pub struct Remote<'p> {
622    peer: &'p mut dyn Peer,
623    root: Root,
624    record: Record,
625}
626
627impl<'p> Remote<'p> {
628    /// Asks the peer for the record of `root`, and checks it.
629    pub fn open(peer: &'p mut dyn Peer, root: &Root) -> Result<Self> {
630        let frame = ask_one(peer, &Request::Record(*root), MAX_RECORD_BYTES)?;
631        if Root::of_record(&frame) != *root {
632            return Err(Error::HashMismatch { what: "a record" });
633        }
634        let record = Record::decode(&frame)?;
635        Ok(Self {
636            peer,
637            root: *root,
638            record,
639        })
640    }
641
642    pub fn root(&self) -> &Root {
643        &self.root
644    }
645
646    pub fn record(&self) -> &Record {
647        &self.record
648    }
649
650    /// What is under `name` in `folder`, or nothing when the folder has no
651    /// such name. Either answer is proven by the one entry the peer shows.
652    pub fn entry(&mut self, folder: &Target, name: &str) -> Result<Option<Entry>> {
653        check_name(name)?;
654        folder.require(Kind::Folder)?;
655        let frame = ask_one(
656            self.peer,
657            &Request::FolderName {
658                folder: folder.hash,
659                name: name.to_owned(),
660            },
661            folder_branch_limit(1),
662        )?;
663        let Frame::FolderBranch(branch) = Frame::decode(&frame)? else {
664            return Err(OTHER_KIND);
665        };
666        Ok(branch.check_name(folder, name)?.cloned())
667    }
668
669    /// What is at `path` in the tree: names with `/` between them. One
670    /// question is asked for each name on the way.
671    pub fn lookup(&mut self, path: &str) -> Result<Option<Entry>> {
672        let mut current = self.record.top();
673        let mut found = None;
674        for (folders_passed, name) in path.split('/').enumerate() {
675            check_name(name)?;
676            if current.kind != Kind::Folder {
677                return Ok(None);
678            }
679            if folders_passed >= MAX_FOLDER_DEPTH {
680                return Err(Error::TooDeep {
681                    limit: MAX_FOLDER_DEPTH,
682                });
683            }
684            let Some(entry) = self.entry(&current, name)? else {
685                return Ok(None);
686            };
687            current = entry.target();
688            found = Some(entry);
689        }
690        Ok(found)
691    }
692
693    /// Up to `count` entries of a folder, from place `start`. Fewer come
694    /// back when the folder ends first, or when the peer gives fewer at a
695    /// time. An empty folder gives none.
696    pub fn entries(&mut self, folder: &Target, start: u64, count: u32) -> Result<Entries> {
697        folder.require(Kind::Folder)?;
698        let request = Request::FolderBranch {
699            folder: folder.hash,
700            start,
701            count,
702        };
703        let frame = ask_one(self.peer, &request, folder_branch_limit(u64::from(count)))?;
704        let Frame::FolderBranch(branch) = Frame::decode(&frame)? else {
705            return Err(OTHER_KIND);
706        };
707        branch.check(folder)?;
708        if branch.count() != 0
709            && (branch.start() != start || branch.entries().len() > count as usize)
710        {
711            return Err(Error::NotWanted {
712                what: "a branch that was not asked for",
713            });
714        }
715        Ok(Entries {
716            total: branch.count(),
717            start: branch.start(),
718            entries: branch.entries().to_vec(),
719        })
720    }
721
722    /// Writes `length` bytes of a file, from byte `offset`, to `out`.
723    ///
724    /// The peer shows the branch of the file's list that holds the stretch, and
725    /// that proves each chunk's number and the byte it starts at. Then the
726    /// chunks are asked for by their numbers, and each is checked against
727    /// the list before any of its bytes is written. Nothing else of the file
728    /// is taken.
729    pub fn read(
730        &mut self,
731        file: &Target,
732        offset: u64,
733        length: u64,
734        out: &mut dyn Write,
735    ) -> Result<()> {
736        file.require(Kind::File)?;
737        let end = offset
738            .checked_add(length)
739            .filter(|end| *end <= file.size)
740            .ok_or_else(|| invalid("a stretch of bytes is outside the file"))?;
741        let chunking = self.record.chunking();
742        let mut at = offset;
743        while at < end {
744            let request = Request::FileBytes {
745                file: file.hash,
746                offset: at,
747                length: end - at,
748            };
749            let branch_limit = file_branch_limit(most_chunks_in(chunking, end - at));
750            let frame = ask_one(self.peer, &request, branch_limit)?;
751            let Frame::FileBranch(branch) = Frame::decode(&frame)? else {
752                return Err(OTHER_KIND);
753            };
754            let branch_start = branch.check(file, Some(chunking))?;
755            let items = branch.items();
756            // The branch has to begin with the chunk that holds the first byte
757            // still due, and may not reach past the chunk that holds the last.
758            let before_last: u64 = items[..items.len() - 1]
759                .iter()
760                .map(|item| u64::from(item.length))
761                .sum();
762            let holds_first = branch_start <= at && at < branch_start + u64::from(items[0].length);
763            if !holds_first || branch_start + before_last >= end {
764                return Err(Error::NotWanted {
765                    what: "a branch that does not hold the bytes asked for",
766                });
767            }
768            let chunks = Request::Chunks {
769                file: file.hash,
770                start: branch.start(),
771                count: items.len() as u32,
772            };
773            // No chunk that is due is longer than the longest in the branch.
774            let longest = items
775                .iter()
776                .map(|item| item.length as usize)
777                .max()
778                .unwrap_or(0);
779            let mut taken = 0_usize;
780            let mut chunk_start = branch_start;
781            let mut refused = false;
782            self.peer.ask(&chunks.encode(), longest + 1, &mut |frame| {
783                if refused {
784                    return Err(peer_error("sent more after it refused"));
785                }
786                match Frame::decode(frame)? {
787                    Frame::Refused(_) => refused = true,
788                    Frame::Chunk(bytes) => {
789                        let item = items.get(taken).ok_or(TOO_MUCH)?;
790                        check_chunk(item, bytes, "a chunk")?;
791                        let chunk_end = chunk_start + u64::from(item.length);
792                        let from = (at - chunk_start) as usize;
793                        let to = (end.min(chunk_end) - chunk_start) as usize;
794                        out.write_all(&bytes[from..to])
795                            .map_err(|source| Error::Stream {
796                                operation: "write a file's bytes",
797                                source,
798                            })?;
799                        at = end.min(chunk_end);
800                        chunk_start = chunk_end;
801                        taken += 1;
802                    }
803                    _ => return Err(OTHER_KIND),
804                }
805                Ok(())
806            })?;
807            if taken == 0 {
808                return Err(peer_error("does not hold the chunks asked for"));
809            }
810        }
811        Ok(())
812    }
813
814    /// Which chunks of a file the peer says it holds, one bit a chunk. This
815    /// is what the peer says about itself: nothing proves it, and a chunk it
816    /// claims is still checked when it comes. Only the number of chunks is
817    /// held to what the file's size allows.
818    pub fn have(&mut self, file: &Target) -> Result<HaveMap> {
819        file.require(Kind::File)?;
820        let chunking = self.record.chunking();
821        let most = chunking.count_bounds(file.size).1;
822        let limit = usize::try_from(most.div_ceil(8))
823            .unwrap_or(usize::MAX)
824            .saturating_add(9);
825        let frame = ask_one(self.peer, &Request::Have(file.hash), limit)?;
826        let Frame::Have(map) = Frame::decode(&frame)? else {
827            return Err(OTHER_KIND);
828        };
829        chunking.check_count(file.size, map.count())?;
830        Ok(map)
831    }
832}
833
834/// Writes a whole tree to `out` as one stream: the bundle's first bytes,
835/// the record, and then every list and every chunk once, each after what
836/// names it. [`import`] reads it back.
837pub fn export(store: &dyn Store, root: &Root, out: &mut dyn Write) -> Result<()> {
838    let record = record_of(store, root)?;
839    out.write_all(&BUNDLE_MAGIC)
840        .map_err(|source| Error::Stream {
841            operation: "write a bundle",
842            source,
843        })?;
844    write_frame(out, &record.encode())?;
845    let mut lists: HashSet<(Kind, Hash)> = HashSet::new();
846    let mut chunks: HashSet<Hash> = HashSet::new();
847    let mut ahead = ChunksAhead::new();
848    let mut pending = vec![record.top()];
849    while let Some(target) = pending.pop() {
850        if !lists.insert((target.kind, target.hash)) {
851            continue;
852        }
853        match target.kind {
854            Kind::Folder => {
855                let list = folder_of(store, &target)?;
856                write_framed(out, FRAME_FOLDER_LIST, &list.encode())?;
857                pending.extend(list.entries().iter().rev().map(Entry::target));
858            }
859            Kind::File => {
860                let list = file_of(store, &target)?;
861                write_framed(out, FRAME_FILE_LIST, &list.encode())?;
862                let new: Vec<ChunkRef> = list
863                    .items()
864                    .iter()
865                    .filter(|item| chunks.insert(item.hash))
866                    .copied()
867                    .collect();
868                ahead.lend(store, &new, &mut |_, bytes| {
869                    write_framed(out, FRAME_CHUNK, bytes)
870                })?;
871            }
872        }
873    }
874    Ok(())
875}
876
877/// Reads a bundle that [`export`] wrote, and takes the tree with this root
878/// from it into a store. Every frame goes through the same checks as a
879/// frame from a peer, and the tree must be whole when the stream ends. A
880/// frame for something the store holds already is passed over. A frame that
881/// nothing in the tree names is an error.
882pub fn import(store: &dyn Store, root: &Root, input: &mut dyn Read) -> Result<Summary> {
883    let mut magic = [0_u8; 8];
884    input
885        .read_exact(&mut magic)
886        .map_err(|source| Error::Stream {
887            operation: "read a bundle",
888            source,
889        })?;
890    if magic != BUNDLE_MAGIC {
891        return Err(invalid("a stream does not start as a bundle does"));
892    }
893    let mut intake = Intake::new(store, *root)?;
894    // Chunks that come one after another are held, and taken in together
895    // by several threads while the next ones are read, once the record is
896    // in. Each frame is read after the chunk frames that are held, and one
897    // more buffer takes every other frame of the bundle.
898    let mut frames = [ChunkFrames::new(), ChunkFrames::new()];
899    let mut frame = Vec::new();
900    // What the intake takes changes only when it takes a frame that is not
901    // a chunk's, and those are taken here.
902    let mut limit = intake.frame_limit();
903    let mut recorded = intake.record().is_some();
904    std::thread::scope(|scope| {
905        let mut taking = TakingIn::new(scope, &mut intake, &mut frames);
906        let read = loop {
907            let next = match taking.read_next(input, limit) {
908                Ok(next) => next,
909                Err(error) => break Err(error),
910            };
911            match next {
912                Next::Frame if recorded && taking.next_is_chunk() => {
913                    if let Err(error) = taking.hold(None) {
914                        break Err(error);
915                    }
916                }
917                Next::Frame => {
918                    // What came before is taken in first.
919                    taking.take_next(&mut frame);
920                    let accepted = taking.intake().and_then(|intake| {
921                        intake.accept(&frame)?;
922                        limit = intake.frame_limit();
923                        recorded = intake.record().is_some();
924                        Ok(())
925                    });
926                    if let Err(error) = accepted {
927                        break Err(error);
928                    }
929                }
930                Next::End => break Err(invalid("a frame is empty")),
931                Next::Closed => break Ok(()),
932            }
933        };
934        // What came before a failure is taken in first, and its own failure
935        // is the one given.
936        taking.finish().and(read)
937    })?;
938    intake.finish()
939}
940
941/// Answers the requests that come in on a connection, until it ends.
942///
943/// A request comes as a frame does: its length in four bytes, and then its
944/// bytes. The answer goes out as its frames, each with its length before it,
945/// and then a length of zero. Requests are answered one at a time, in the
946/// order they come.
947///
948/// A request that is malformed or too long ends the serving with an error.
949/// What is not held is answered with a refusal, and the serving goes on.
950pub fn serve(store: &dyn Store, input: &mut dyn Read, output: &mut dyn Write) -> Result<()> {
951    let responder = Responder::new(store);
952    let mut request = Vec::new();
953    loop {
954        match read_next(input, MAX_REQUEST_BYTES, &mut request)? {
955            Next::Frame => {}
956            Next::End => return Err(invalid("a request is empty")),
957            Next::Closed => return Ok(()),
958        }
959        responder.answer(&request, &mut |frame| write_frame(output, frame))?;
960        write_end(output)?;
961        output.flush().map_err(|source| Error::Stream {
962            operation: "send an answer",
963            source,
964        })?;
965    }
966}
967
968/// A peer at the other end of a connection, where [`serve`] answers.
969///
970/// `input` is what the other end sends, and `output` is what it reads. An
971/// answer that is left half read, because a frame of it was refused, leaves
972/// the connection where nobody knows what comes next. Nothing more is asked
973/// on it then: open a new one.
974pub struct StreamPeer<R, W> {
975    input: R,
976    output: W,
977    broken: bool,
978    /// One buffer for every frame that is read, from answer to answer.
979    frame: Vec<u8>,
980}
981
982impl<R: Read, W: Write> StreamPeer<R, W> {
983    pub fn new(input: R, output: W) -> Self {
984        Self {
985            input,
986            output,
987            broken: false,
988            frame: Vec::new(),
989        }
990    }
991}
992
993impl<R: Read, W: Write> Peer for StreamPeer<R, W> {
994    fn ask(
995        &mut self,
996        request: &[u8],
997        limit: usize,
998        on_frame: &mut dyn FnMut(&[u8]) -> Result<()>,
999    ) -> Result<()> {
1000        self.ask_all(&[(request.to_vec(), limit)], &mut |_, frame| {
1001            on_frame(frame)
1002        })
1003    }
1004
1005    fn ask_all(
1006        &mut self,
1007        requests: &[(Vec<u8>, usize)],
1008        on_frame: &mut dyn FnMut(usize, &[u8]) -> Result<()>,
1009    ) -> Result<()> {
1010        if self.broken {
1011            return Err(peer_error(
1012                "is on a connection that an earlier answer left half read",
1013            ));
1014        }
1015        self.broken = true;
1016        let mut answered = 0;
1017        while answered < requests.len() {
1018            // Send ahead what the connection is sure to hold, and one
1019            // request at the least.
1020            let mut sent = answered;
1021            let mut ahead = 0;
1022            while let Some((request, _)) = requests.get(sent) {
1023                let bytes = request.len() + 4;
1024                if sent > answered && ahead + bytes > REQUESTS_AHEAD_BYTES {
1025                    break;
1026                }
1027                write_frame(&mut self.output, request)?;
1028                ahead += bytes;
1029                sent += 1;
1030            }
1031            self.output.flush().map_err(|source| Error::Stream {
1032                operation: "send a request",
1033                source,
1034            })?;
1035            for (place, (_, limit)) in requests.iter().enumerate().take(sent).skip(answered) {
1036                loop {
1037                    match read_next(&mut self.input, *limit, &mut self.frame)? {
1038                        Next::Frame => on_frame(place, &self.frame)?,
1039                        Next::End => break,
1040                        Next::Closed => {
1041                            return Err(peer_error("closed the connection inside an answer"));
1042                        }
1043                    }
1044                }
1045            }
1046            answered = sent;
1047        }
1048        self.broken = false;
1049        Ok(())
1050    }
1051}