blackout_target/
static_tree.rs

Help
1// Copyright 2019 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! Generate a random directory tree that can be commited to disk all at once. The general formula
6//! goes like this -
7//!
8//! ```
9//! use {rand::{Rng, SeedableRng, rngs::StdRng}, static_tree::{EntryDistribution, DirectoryEntry}};
10//! let mut rng = StdRng::seed_from_u64(seed);
11//! let dist = EntryDistribution::new(depth);
12//! let tree: DirectoryEntry = rng.sample(&dist);
13//! tree.write_tree_at(root).expect("failed to write tree");
14//! ```
15
16use anyhow::Error;
17use fidl_fuchsia_io as fio;
18use rand::{distributions, Rng};
19
20/// A random distribution specialized to generation of random directory trees. This distribution
21/// decreases the likelyhood of a directory being generated linearly relative to the depth of the
22/// subset of the tree being generated, until it's 0% at the maximum depth.
23#[derive(Clone, Copy, Debug, Eq, PartialEq)]
24pub struct EntryDistribution {
25    depth: u32,
26    max_depth: u32,
27}
28
29impl EntryDistribution {
30    /// Create a new `EntryDistribution` with a maximum depth of `max_depth`. This distribution is
31    /// used for generating [`DirectoryEntry`]s and [`Entry`]s.
32    pub fn new(max_depth: u32) -> EntryDistribution {
33        EntryDistribution { depth: 1, max_depth }
34    }
35
36    /// get the entry distribution for the next level down on the directory tree.
37    fn next_level(&self) -> EntryDistribution {
38        debug_assert!(
39            self.depth <= self.max_depth,
40            "directory tree exceeded max depth ({} vs max of {}). programming error.",
41            self.depth,
42            self.max_depth
43        );
44        EntryDistribution { depth: self.depth + 1, max_depth: self.max_depth }
45    }
46
47    /// creates a bernoulli distribution where the likelyhood is progressively decreased at further
48    /// depths until it's 0% at max_depth.
49    fn directory_distribution(&self) -> distributions::Bernoulli {
50        distributions::Bernoulli::from_ratio(self.max_depth - self.depth, self.max_depth).unwrap()
51    }
52}
53
54/// A file entry in the generated tree. Contains a randomly generated u64 for a name and randomly
55/// generated byte contents. The file size is random, in a range of 1 byte to 2^16 bytes (~65kb).
56#[derive(Debug, Clone, Eq, PartialEq)]
57pub struct FileEntry {
58    name: u64,
59    contents: Vec<u8>,
60}
61
62impl distributions::Distribution<FileEntry> for distributions::Standard {
63    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> FileEntry {
64        let size = rng.gen_range(1..1 << 16);
65        // unfortunately, we can't use sample_iter to generate the content here. the trait
66        // definition for distribution requires the Rng type parameter to have ?Sized (or "maybe
67        // sized"), but the sample_iter function requires the provided Rng be Sized, either through
68        // the explicit Self: Sized on the Rng sample_iter function, or the implicit Sized present
69        // on type parameters for the equivalent Distribution function.
70        let mut contents = vec![0; size];
71        rng.fill(contents.as_mut_slice());
72        FileEntry { name: rng.gen(), contents }
73    }
74}
75
76impl FileEntry {
77    async fn write_file_at(self, root: &fio::DirectoryProxy) -> Result<(), Error> {
78        let file = fuchsia_fs::directory::open_file(
79            root,
80            &self.name.to_string(),
81            fio::Flags::FLAG_MAYBE_CREATE | fio::PERM_WRITABLE,
82        )
83        .await?;
84        fuchsia_fs::file::write(&file, &self.contents).await?;
85        Ok(())
86    }
87}
88
89/// A directory entry in the generated tree. Contains a randomly generated u64 for a name and a
90/// vector of randomly generated directory entries, with a number of entries somewhere in the range
91/// of [0, 6). The sample function generates the entire subtree depth-first before returning, and is
92/// mutually recursive with the [`Entry`] sample function.
93#[derive(Clone, Debug, Eq, PartialEq)]
94pub struct DirectoryEntry {
95    name: u64,
96    entries: Vec<Entry>,
97}
98
99impl distributions::Distribution<DirectoryEntry> for EntryDistribution {
100    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> DirectoryEntry {
101        // each directory has a random number of entries in the range [0, 6)
102        let num_entries = rng.gen_range(0..6);
103        let mut entries = vec![];
104        let entry_dist = self.next_level();
105        for _ in 0..num_entries {
106            entries.push(rng.sample(&entry_dist));
107        }
108        DirectoryEntry { name: rng.gen(), entries }
109    }
110}
111
112impl DirectoryEntry {
113    /// get the path the directory entry will be written to relative to a given root.
114    pub fn get_name(&self) -> String {
115        self.name.to_string()
116    }
117
118    /// Take the entire randomly generated tree and commit it to disk.
119    pub fn write_tree_at<'a>(
120        self,
121        root: &'a fio::DirectoryProxy,
122    ) -> futures::future::BoxFuture<'a, Result<(), Error>> {
123        Box::pin(async {
124            let this = fuchsia_fs::directory::create_directory(
125                root,
126                &self.get_name(),
127                fio::PERM_READABLE | fio::PERM_WRITABLE,
128            )
129            .await?;
130            for entry in self.entries {
131                match entry {
132                    Entry::File(file_entry) => file_entry.write_file_at(&this).await?,
133                    Entry::Directory(dir_entry) => dir_entry.write_tree_at(&this).await?,
134                }
135            }
136            Ok(())
137        })
138    }
139}
140
141/// An entry of either File or Directory. The chance of it being a directory is relative to the depth
142/// recorded in EntryDistribution. The associated entry is also then generated.
143#[derive(Clone, Debug, Eq, PartialEq)]
144pub enum Entry {
145    /// This entry is a file.
146    File(FileEntry),
147    /// This entry is a directory
148    Directory(DirectoryEntry),
149}
150
151impl distributions::Distribution<Entry> for EntryDistribution {
152    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Entry {
153        if rng.sample(self.directory_distribution()) {
154            Entry::Directory(rng.sample(self))
155        } else {
156            Entry::File(rng.sample(distributions::Standard))
157        }
158    }
159}
160
161#[cfg(test)]
162mod tests {
163    use super::{DirectoryEntry, Entry, EntryDistribution, FileEntry};
164    use fs_management::Minfs;
165    use fuchsia_async as fasync;
166    use ramdevice_client::RamdiskClient;
167    use rand::rngs::mock::StepRng;
168    use rand::Rng as _;
169
170    // this fixture will have to get updated any time the generation logic changes. depending on the
171    // nature of the change, the comparison logic may have to be changed as well.
172    fn get_fixture(initial: u64, increment: u64, depth: u32) -> DirectoryEntry {
173        // confirm that the rng and depth used to generate this tree are the same.
174        assert_eq!(initial, 0xdeadbeef, "initial value changed - update fixture");
175        assert_eq!(increment, 1, "increment value changed - update fixture");
176        assert_eq!(depth, 2, "depth value changed - update fixture");
177        DirectoryEntry {
178            name: 3735928580,
179            entries: vec![
180                Entry::File(FileEntry { name: 3735928563, contents: vec![242] }),
181                Entry::File(FileEntry { name: 3735928567, contents: vec![246] }),
182                Entry::File(FileEntry { name: 3735928571, contents: vec![250] }),
183                Entry::File(FileEntry { name: 3735928575, contents: vec![254] }),
184                Entry::File(FileEntry { name: 3735928579, contents: vec![2] }),
185            ],
186        }
187    }
188
189    #[test]
190    fn gen_tree() {
191        let initial = 0xdeadbeef;
192        let increment = 1;
193        let depth = 2;
194        // make sure we are generating a tree at all.
195        let mut rng = StepRng::new(initial, increment);
196        let dist = EntryDistribution::new(depth);
197        let tree: DirectoryEntry = rng.sample(dist);
198        // this skips the contents for the files, because they are huge, so we do our own manual
199        // comparison.
200        let fixture = get_fixture(initial, increment, depth);
201        assert_eq!(fixture, tree);
202        for i in 0..fixture.entries.len() {
203            match &fixture.entries[i] {
204                Entry::File(fixture_file_entry) => match &tree.entries[i] {
205                    Entry::File(tree_file_entry) => {
206                        assert_eq!(fixture_file_entry.name, tree_file_entry.name)
207                    }
208                    _ => panic!("expected a file in generated tree"),
209                },
210                _ => panic!("expected a file in fixture tree"),
211            }
212        }
213    }
214
215    #[test]
216    fn same_rng_same_tree() {
217        // this confirms an assumption about the properties of tree generation that we rely on for
218        // consistency checking.
219        let dist = EntryDistribution::new(5);
220
221        let tree1: DirectoryEntry = StepRng::new(1337, 1).sample(dist);
222        let tree2: DirectoryEntry = StepRng::new(1337, 1).sample(dist);
223
224        assert_eq!(tree1, tree2);
225    }
226
227    #[fasync::run_singlethreaded(test)]
228    async fn write_tree() {
229        let root = "/test-root";
230        let initial = 0xdeadbeef;
231        let increment = 1;
232        let depth = 2;
233
234        let mut rng = StepRng::new(initial, increment);
235        let dist = EntryDistribution::new(depth);
236        let tree: DirectoryEntry = rng.sample(dist);
237
238        let mut ramdisk =
239            RamdiskClient::create(512, 1 << 16).await.expect("failed to make ramdisk");
240        let controller = ramdisk.take_controller().expect("invalid controller");
241        let mut minfs = Minfs::new(controller);
242
243        minfs.format().await.expect("failed to format minfs");
244        let mut minfs = minfs.serve().await.expect("failed to mount minfs");
245        minfs.bind_to_path(root).expect("failed to bind path");
246
247        tree.write_tree_at(minfs.root()).await.expect("failed to write tree");
248
249        let fixture = get_fixture(initial, increment, depth);
250        let path = std::path::PathBuf::from(format!("{}/{}", root, fixture.name));
251        assert!(path.is_dir(), "{}", path.display());
252        for (i, entry) in std::fs::read_dir(&path).expect("failed to read directory").enumerate() {
253            let entry = entry.expect("failed to read entry");
254            let file_type = entry.file_type().expect("failed to get file type");
255            assert!(file_type.is_file());
256            let file_name =
257                entry.file_name().into_string().expect("failed to convert file name to string");
258            let expected_name = match &fixture.entries[i] {
259                Entry::File(f) => f.name,
260                Entry::Directory(_) => panic!("expected a file in the fixture tree"),
261            };
262            assert_eq!(file_name, expected_name.to_string());
263        }
264
265        minfs.shutdown().await.expect("failed to unmount minfs");
266        ramdisk.destroy().await.expect("failed to destroy ramdisk");
267    }
268}
blackout_target/static_tree.rs

blackout_target/
static_tree.rs
