blackout_target/
static_tree.rs

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

blackout_target/
static_tree.rs
