Skip to main content

roundtrip/
roundtrip.rs

1//! A tree's whole way round, with a store on disk.
2//!
3//! Builds a tree from a folder, checks it, fetches it into a second store as
4//! a receiver would, reads stretches of its largest file without the rest,
5//! writes the tree out again, and holds the copy to the same root. It prints
6//! how long each step took.
7//!
8//! ```sh
9//! cargo run --release --example roundtrip -- <folder> <work-dir>
10//! ```
11//!
12//! `<work-dir>` must not exist. The stores and the copy are made in it.
13//!
14//! The store here keeps each thing as a file named by its hash. It is the
15//! smallest store that does not hold a tree in memory, and it shows what a
16//! store has to do: keep bytes under a hash, and give them back.
17
18use scionic_merkletree::{
19    build, fetch, folder_of, record_of, verify, write_to_disk, BuildOptions, Error, Hash, Kind,
20    Remote, Responder, Result, Store, Stored, Target,
21};
22use std::fs::{self, File};
23use std::io::{ErrorKind, Read};
24use std::path::{Path, PathBuf};
25use std::sync::atomic::{AtomicU64, Ordering};
26use std::sync::{Arc, Mutex};
27use std::time::Instant;
28
29struct DirStore {
30    dir: PathBuf,
31    /// Numbers the files that are being written, so that two writers of the
32    /// same thing do not write to the same file.
33    writing: AtomicU64,
34    /// Memory that things are read into, kept for the next read: fresh
35    /// memory for each chunk, as `get` takes, costs some systems more than
36    /// the reading does. One for each thread that reads at once.
37    read: Mutex<Vec<Vec<u8>>>,
38}
39
40fn failed(operation: &'static str, path: &Path, source: std::io::Error) -> Error {
41    Error::Io {
42        operation,
43        path: path.to_path_buf(),
44        source,
45    }
46}
47
48impl DirStore {
49    fn new(dir: PathBuf) -> Self {
50        Self {
51            dir,
52            writing: AtomicU64::new(0),
53            read: Mutex::new(Vec::new()),
54        }
55    }
56
57    fn path(&self, kind: Stored, hash: &Hash) -> PathBuf {
58        let kind = match kind {
59            Stored::Chunk => "chunks",
60            Stored::FileList => "files",
61            Stored::FolderList => "folders",
62            Stored::Record => "records",
63        };
64        let name = hash.to_hex();
65        self.dir.join(kind).join(&name[..2]).join(name)
66    }
67}
68
69impl Store for DirStore {
70    fn put(&self, kind: Stored, hash: &Hash, bytes: &[u8]) -> Result<()> {
71        let path = self.path(kind, hash);
72        if path.exists() {
73            return Ok(());
74        }
75        if let Some(parent) = path.parent() {
76            // Looked at first: trying to make a folder that is there already
77            // costs several times what seeing that it is there does.
78            if !parent.is_dir() {
79                fs::create_dir_all(parent).map_err(|error| failed("create", parent, error))?;
80            }
81        }
82        // Written under another name first, so that a file is never found
83        // under a hash before all of its bytes are there.
84        let number = self.writing.fetch_add(1, Ordering::Relaxed);
85        let unfinished = path.with_extension(format!("writing-{number}"));
86        fs::write(&unfinished, bytes).map_err(|error| failed("write", &unfinished, error))?;
87        match fs::rename(&unfinished, &path) {
88            Ok(()) => Ok(()),
89            // Another writer was first, with the same bytes.
90            Err(_) if path.exists() => {
91                let _ = fs::remove_file(&unfinished);
92                Ok(())
93            }
94            Err(error) => Err(failed("keep", &path, error)),
95        }
96    }
97
98    fn get(&self, kind: Stored, hash: &Hash) -> Result<Option<Arc<[u8]>>> {
99        let path = self.path(kind, hash);
100        let mut file = match File::open(&path) {
101            Ok(file) => file,
102            Err(error) if error.kind() == ErrorKind::NotFound => return Ok(None),
103            Err(error) => return Err(failed("open", &path, error)),
104        };
105        let length = file
106            .metadata()
107            .map_err(|error| failed("look at", &path, error))?
108            .len();
109        let length = usize::try_from(length).map_err(|_| {
110            let too_long = std::io::Error::other("it is longer than this machine can hold");
111            failed("read", &path, too_long)
112        })?;
113        // The bytes are read straight into the memory that is handed out. A
114        // `Vec` that is turned into an `Arc` is copied once more, and a chunk
115        // is megabytes long.
116        let mut bytes: Arc<[u8]> = std::iter::repeat_n(0, length).collect();
117        let room = Arc::get_mut(&mut bytes).expect("nothing else holds what was just made");
118        file.read_exact(room)
119            .map_err(|error| failed("read", &path, error))?;
120        Ok(Some(bytes))
121    }
122
123    /// The library reads a tree's chunks through here, and each is read into
124    /// memory that was read into before.
125    fn lend(
126        &self,
127        kind: Stored,
128        hash: &Hash,
129        with: &mut dyn FnMut(&[u8]) -> Result<()>,
130    ) -> Result<bool> {
131        let path = self.path(kind, hash);
132        let mut file = match File::open(&path) {
133            Ok(file) => file,
134            Err(error) if error.kind() == ErrorKind::NotFound => return Ok(false),
135            Err(error) => return Err(failed("open", &path, error)),
136        };
137        let mut bytes = match self.read.lock() {
138            Ok(mut kept) => kept.pop().unwrap_or_default(),
139            Err(_) => Vec::new(),
140        };
141        bytes.clear();
142        let lent = file
143            .read_to_end(&mut bytes)
144            .map_err(|error| failed("read", &path, error))
145            .and_then(|_| with(&bytes));
146        if let Ok(mut kept) = self.read.lock() {
147            kept.push(bytes);
148        }
149        lent.map(|()| true)
150    }
151
152    /// The library reads chunks that it sends, or reads several at once,
153    /// through here, straight into memory of its own. A file of another
154    /// length than that memory is not read.
155    fn read_into(&self, kind: Stored, hash: &Hash, into: &mut [u8]) -> Result<Option<u64>> {
156        let path = self.path(kind, hash);
157        let mut file = match File::open(&path) {
158            Ok(file) => file,
159            Err(error) if error.kind() == ErrorKind::NotFound => return Ok(None),
160            Err(error) => return Err(failed("open", &path, error)),
161        };
162        let length = file
163            .metadata()
164            .map_err(|error| failed("look at", &path, error))?
165            .len();
166        if length == into.len() as u64 {
167            file.read_exact(into)
168                .map_err(|error| failed("read", &path, error))?;
169        }
170        Ok(Some(length))
171    }
172
173    fn size(&self, kind: Stored, hash: &Hash) -> Result<Option<u64>> {
174        let path = self.path(kind, hash);
175        match fs::metadata(&path) {
176            Ok(metadata) => Ok(Some(metadata.len())),
177            Err(error) if error.kind() == ErrorKind::NotFound => Ok(None),
178            Err(error) => Err(failed("look at", &path, error)),
179        }
180    }
181
182    fn remove(&self, kind: Stored, hash: &Hash) -> Result<()> {
183        let path = self.path(kind, hash);
184        match fs::remove_file(&path) {
185            Err(error) if error.kind() != ErrorKind::NotFound => {
186                Err(failed("remove", &path, error))
187            }
188            _ => Ok(()),
189        }
190    }
191}
192
193/// The largest file of a tree, each folder looked into once.
194fn largest_file(store: &dyn Store, top: Target) -> Result<Option<Target>> {
195    let mut largest: Option<Target> = None;
196    let mut seen = std::collections::HashSet::new();
197    let mut pending = vec![top];
198    while let Some(target) = pending.pop() {
199        match target.kind {
200            Kind::File if largest.is_none_or(|file| file.size < target.size) => {
201                largest = Some(target);
202            }
203            Kind::File => {}
204            Kind::Folder if seen.insert(target.hash) => {
205                let list = folder_of(store, &target)?;
206                pending.extend(list.entries().iter().map(|entry| entry.target()));
207            }
208            Kind::Folder => {}
209        }
210    }
211    Ok(largest)
212}
213
214fn report(step: &str, started: Instant, bytes: u64) {
215    let seconds = started.elapsed().as_secs_f64();
216    let rate = bytes as f64 / (1 << 20) as f64 / seconds.max(1e-9);
217    println!("{step:<12} {seconds:>8.2} s  {rate:>8.0} MiB/s");
218}
219
220fn main() -> std::result::Result<(), Box<dyn std::error::Error>> {
221    let mut arguments = std::env::args_os().skip(1);
222    let (Some(folder), Some(work)) = (arguments.next(), arguments.next()) else {
223        eprintln!("usage: roundtrip <folder> <work-dir>");
224        std::process::exit(2);
225    };
226    let work = PathBuf::from(work);
227    fs::create_dir(&work)?;
228
229    let source = DirStore::new(work.join("source-store"));
230    let started = Instant::now();
231    let root = build(&source, &folder, &BuildOptions::new())?;
232    let record = record_of(&source, &root)?;
233    let (size, totals) = (record.top().size, record.totals());
234    report("built", started, size);
235    println!("root         {root}");
236    println!(
237        "the tree     {size} bytes; kept once: {} chunks of {} bytes, and {} bytes of lists",
238        totals.chunks, totals.chunk_bytes, totals.list_bytes
239    );
240
241    let started = Instant::now();
242    let summary = verify(&source, &root)?;
243    report("checked", started, totals.chunk_bytes);
244    println!(
245        "             {} different files in {} different folders",
246        summary.files, summary.folders
247    );
248
249    let fetched = DirStore::new(work.join("fetched-store"));
250    let started = Instant::now();
251    fetch(&fetched, &root, &mut Responder::new(&source))?;
252    report("fetched", started, totals.chunk_bytes);
253
254    if let Some(file) = largest_file(&source, record.top())? {
255        // A stretch of 4 KiB is read from 64 places spread over the file, each
256        // asked for on its own, and the time one takes on average is printed:
257        // a single read is shorter than some systems' clocks can tell apart.
258        let length = file.size.min(4096);
259        let places: u64 = 64;
260        let mut holder = Responder::new(&source);
261        let mut remote = Remote::open(&mut holder, &root)?;
262        let mut stretch = Vec::new();
263        let started = Instant::now();
264        for place in 0..places {
265            stretch.clear();
266            let offset = (file.size - length) * place / (places - 1);
267            remote.read(&file, offset, length, &mut stretch)?;
268        }
269        println!(
270            "a stretch    {:>8.4} s  {} bytes at a time, from {places} places in a file of {} bytes",
271            started.elapsed().as_secs_f64() / places as f64,
272            stretch.len(),
273            file.size
274        );
275    }
276
277    let written = work.join("written");
278    let started = Instant::now();
279    write_to_disk(&fetched, &root, &written)?;
280    report("written out", started, size);
281
282    let again = DirStore::new(work.join("again-store"));
283    let started = Instant::now();
284    let rebuilt = build(&again, &written, &BuildOptions::new())?;
285    report("built again", started, size);
286    if rebuilt != root {
287        return Err(format!("the copy has the root {rebuilt}, and not {root}").into());
288    }
289    println!("the copy has the same root");
290    Ok(())
291}