nydus_builder/core/
prefetch.rs

1// Copyright 2020 Ant Group. All rights reserved.
2// Copyright (C) 2023 Alibaba Cloud. All rights reserved.
3//
4// SPDX-License-Identifier: Apache-2.0
5
6use std::path::PathBuf;
7use std::str::FromStr;
8
9use anyhow::{anyhow, Context, Error, Result};
10use indexmap::IndexMap;
11use nydus_rafs::metadata::layout::v5::RafsV5PrefetchTable;
12use nydus_rafs::metadata::layout::v6::{calculate_nid, RafsV6PrefetchTable};
13
14use super::node::Node;
15use crate::core::tree::TreeNode;
16
17/// Filesystem data prefetch policy.
18#[derive(Clone, Copy, Debug, PartialEq)]
19pub enum PrefetchPolicy {
20    None,
21    /// Prefetch will be issued from Fs layer, which leverages inode/chunkinfo to prefetch data
22    /// from blob no matter where it resides(OSS/Localfs). Basically, it is willing to cache the
23    /// data into blobcache(if exists). It's more nimble. With this policy applied, image builder
24    /// currently puts prefetch files' data into a continuous region within blob which behaves very
25    /// similar to `Blob` policy.
26    Fs,
27    /// Prefetch will be issued directly from backend/blob layer
28    Blob,
29}
30
31impl Default for PrefetchPolicy {
32    fn default() -> Self {
33        Self::None
34    }
35}
36
37impl FromStr for PrefetchPolicy {
38    type Err = Error;
39    fn from_str(s: &str) -> Result<Self> {
40        match s {
41            "none" => Ok(Self::None),
42            "fs" => Ok(Self::Fs),
43            "blob" => Ok(Self::Blob),
44            _ => Err(anyhow!("invalid prefetch policy")),
45        }
46    }
47}
48
49/// Gather prefetch patterns from STDIN line by line.
50///
51/// Input format:
52///    printf "/relative/path/to/rootfs/1\n/relative/path/to/rootfs/2"
53///
54/// It does not guarantee that specified path exist in local filesystem because the specified path
55/// may exist in parent image/layers.
56fn get_patterns() -> Result<IndexMap<PathBuf, Option<TreeNode>>> {
57    let stdin = std::io::stdin();
58    let mut patterns = Vec::new();
59
60    loop {
61        let mut file = String::new();
62        let size = stdin
63            .read_line(&mut file)
64            .context("failed to read prefetch pattern")?;
65        if size == 0 {
66            return generate_patterns(patterns);
67        }
68        patterns.push(file);
69    }
70}
71
72fn generate_patterns(input: Vec<String>) -> Result<IndexMap<PathBuf, Option<TreeNode>>> {
73    let mut patterns = IndexMap::new();
74
75    for file in &input {
76        let file_trimmed: PathBuf = file.trim().into();
77        // Sanity check for the list format.
78        if !file_trimmed.is_absolute() {
79            warn!(
80                "Illegal file path {} specified, should be absolute path",
81                file
82            );
83            continue;
84        }
85
86        let mut current_path = file_trimmed.clone();
87        let mut skip = patterns.contains_key(&current_path);
88        while !skip && current_path.pop() {
89            if patterns.contains_key(&current_path) {
90                skip = true;
91                break;
92            }
93        }
94
95        if skip {
96            warn!(
97                "prefetch pattern {} is covered by previous pattern and thus omitted",
98                file
99            );
100        } else {
101            debug!(
102                "prefetch pattern: {}, trimmed file name {:?}",
103                file, file_trimmed
104            );
105            patterns.insert(file_trimmed, None);
106        }
107    }
108
109    Ok(patterns)
110}
111
112/// Manage filesystem data prefetch configuration and state for builder.
113#[derive(Default, Clone)]
114pub struct Prefetch {
115    pub policy: PrefetchPolicy,
116
117    pub disabled: bool,
118
119    // Patterns to generate prefetch inode array, which will be put into the prefetch array
120    // in the RAFS bootstrap. It may access directory or file inodes.
121    patterns: IndexMap<PathBuf, Option<TreeNode>>,
122
123    // File list to help optimizing layout of data blobs.
124    // Files from this list may be put at the head of data blob for better prefetch performance,
125    // The index of matched prefetch pattern is stored in `usize`,
126    // which will help to sort the prefetch files in the final layout.
127    // It only stores regular files.
128    files_prefetch: Vec<(TreeNode, usize)>,
129
130    // It stores all non-prefetch files that is not stored in `prefetch_files`,
131    // including regular files, dirs, symlinks, etc.,
132    // with the same order of BFS traversal of file tree.
133    files_non_prefetch: Vec<TreeNode>,
134}
135
136impl Prefetch {
137    /// Create a new instance of [Prefetch].
138    pub fn new(policy: PrefetchPolicy) -> Result<Self> {
139        let patterns = if policy != PrefetchPolicy::None {
140            get_patterns().context("failed to get prefetch patterns")?
141        } else {
142            IndexMap::new()
143        };
144
145        Ok(Self {
146            policy,
147            disabled: false,
148            patterns,
149            files_prefetch: Vec::with_capacity(10000),
150            files_non_prefetch: Vec::with_capacity(10000),
151        })
152    }
153
154    /// Insert node into the prefetch Vector if it matches prefetch rules,
155    /// while recording the index of matched prefetch pattern,
156    /// or insert it into non-prefetch Vector.
157    pub fn insert(&mut self, obj: &TreeNode, node: &Node) {
158        // Newly created root inode of this rafs has zero size
159        if self.policy == PrefetchPolicy::None
160            || self.disabled
161            || (node.inode.is_reg() && node.inode.size() == 0)
162        {
163            self.files_non_prefetch.push(obj.clone());
164            return;
165        }
166
167        let mut path = node.target().clone();
168        let mut exact_match = true;
169        loop {
170            if let Some((idx, _, v)) = self.patterns.get_full_mut(&path) {
171                if exact_match {
172                    *v = Some(obj.clone());
173                }
174                if node.is_reg() {
175                    self.files_prefetch.push((obj.clone(), idx));
176                } else {
177                    self.files_non_prefetch.push(obj.clone());
178                }
179                return;
180            }
181            // If no exact match, try to match parent dir until root.
182            if !path.pop() {
183                self.files_non_prefetch.push(obj.clone());
184                return;
185            }
186            exact_match = false;
187        }
188    }
189
190    /// Get node Vector of files in the prefetch list and non-prefetch list.
191    /// The order of prefetch files is the same as the order of prefetch patterns.
192    /// The order of non-prefetch files is the same as the order of BFS traversal of file tree.
193    pub fn get_file_nodes(&self) -> (Vec<TreeNode>, Vec<TreeNode>) {
194        let mut p_files = self.files_prefetch.clone();
195        p_files.sort_by_key(|k| k.1);
196
197        let p_files = p_files.into_iter().map(|(s, _)| s).collect();
198
199        (p_files, self.files_non_prefetch.clone())
200    }
201
202    /// Get the number of ``valid`` prefetch rules.
203    pub fn fs_prefetch_rule_count(&self) -> u32 {
204        if self.policy == PrefetchPolicy::Fs {
205            self.patterns.values().filter(|v| v.is_some()).count() as u32
206        } else {
207            0
208        }
209    }
210
211    /// Generate filesystem layer prefetch list for RAFS v5.
212    pub fn get_v5_prefetch_table(&mut self) -> Option<RafsV5PrefetchTable> {
213        if self.policy == PrefetchPolicy::Fs {
214            let mut prefetch_table = RafsV5PrefetchTable::new();
215            for i in self.patterns.values().filter_map(|v| v.clone()) {
216                let node = i.borrow_mut();
217                assert!(node.inode.ino() < u32::MAX as u64);
218                prefetch_table.add_entry(node.inode.ino() as u32);
219            }
220            Some(prefetch_table)
221        } else {
222            None
223        }
224    }
225
226    /// Generate filesystem layer prefetch list for RAFS v6.
227    pub fn get_v6_prefetch_table(&mut self, meta_addr: u64) -> Option<RafsV6PrefetchTable> {
228        if self.policy == PrefetchPolicy::Fs {
229            let mut prefetch_table = RafsV6PrefetchTable::new();
230            for i in self.patterns.values().filter_map(|v| v.clone()) {
231                let node = i.borrow_mut();
232                let ino = node.inode.ino();
233                debug_assert!(ino > 0);
234                let nid = calculate_nid(node.v6_offset, meta_addr);
235                // 32bit nid can represent 128GB bootstrap, it is large enough, no need
236                // to worry about casting here
237                assert!(nid < u32::MAX as u64);
238                trace!(
239                    "v6 prefetch table: map node index {} to offset {} nid {} path {:?} name {:?}",
240                    ino,
241                    node.v6_offset,
242                    nid,
243                    node.path(),
244                    node.name()
245                );
246                prefetch_table.add_entry(nid as u32);
247            }
248            Some(prefetch_table)
249        } else {
250            None
251        }
252    }
253
254    /// Disable filesystem data prefetch.
255    pub fn disable(&mut self) {
256        self.disabled = true;
257    }
258
259    /// Reset to initialization state.
260    pub fn clear(&mut self) {
261        self.disabled = false;
262        self.patterns.clear();
263        self.files_prefetch.clear();
264        self.files_non_prefetch.clear();
265    }
266}
267
268#[cfg(test)]
269mod tests {
270    use super::*;
271    use crate::core::node::NodeInfo;
272    use nydus_rafs::metadata::{inode::InodeWrapper, RafsVersion};
273    use std::cell::RefCell;
274
275    #[test]
276    fn test_generate_pattern() {
277        let input = vec![
278            "/a/b".to_string(),
279            "/a/b/c".to_string(),
280            "/a/b/d".to_string(),
281            "/a/b/d/e".to_string(),
282            "/f".to_string(),
283            "/h/i".to_string(),
284        ];
285        let patterns = generate_patterns(input).unwrap();
286        assert_eq!(patterns.len(), 3);
287        assert!(patterns.contains_key(&PathBuf::from("/a/b")));
288        assert!(patterns.contains_key(&PathBuf::from("/f")));
289        assert!(patterns.contains_key(&PathBuf::from("/h/i")));
290        assert!(!patterns.contains_key(&PathBuf::from("/")));
291        assert!(!patterns.contains_key(&PathBuf::from("/a")));
292        assert!(!patterns.contains_key(&PathBuf::from("/a/b/c")));
293        assert!(!patterns.contains_key(&PathBuf::from("/a/b/d")));
294        assert!(!patterns.contains_key(&PathBuf::from("/a/b/d/e")));
295        assert!(!patterns.contains_key(&PathBuf::from("/k")));
296    }
297
298    #[test]
299    fn test_prefetch_policy() {
300        let policy = PrefetchPolicy::from_str("fs").unwrap();
301        assert_eq!(policy, PrefetchPolicy::Fs);
302        let policy = PrefetchPolicy::from_str("blob").unwrap();
303        assert_eq!(policy, PrefetchPolicy::Blob);
304        let policy = PrefetchPolicy::from_str("none").unwrap();
305        assert_eq!(policy, PrefetchPolicy::None);
306        PrefetchPolicy::from_str("").unwrap_err();
307        PrefetchPolicy::from_str("invalid").unwrap_err();
308    }
309
310    #[test]
311    fn test_prefetch() {
312        let input = vec![
313            "/a/b".to_string(),
314            "/f".to_string(),
315            "/h/i".to_string(),
316            "/k".to_string(),
317        ];
318        let patterns = generate_patterns(input).unwrap();
319        let mut prefetch = Prefetch {
320            policy: PrefetchPolicy::Fs,
321            disabled: false,
322            patterns,
323            files_prefetch: Vec::with_capacity(10),
324            files_non_prefetch: Vec::with_capacity(10),
325        };
326        let mut inode = InodeWrapper::new(RafsVersion::V6);
327        inode.set_mode(0o755 | libc::S_IFREG as u32);
328        inode.set_size(1);
329
330        let info = NodeInfo::default();
331
332        let mut info1 = info.clone();
333        info1.target = PathBuf::from("/f");
334        let node1 = Node::new(inode.clone(), info1, 1);
335        let node1 = TreeNode::new(RefCell::from(node1));
336        prefetch.insert(&node1, &node1.borrow());
337
338        let inode2 = inode.clone();
339        let mut info2 = info.clone();
340        info2.target = PathBuf::from("/a/b");
341        let node2 = Node::new(inode2, info2, 1);
342        let node2 = TreeNode::new(RefCell::from(node2));
343        prefetch.insert(&node2, &node2.borrow());
344
345        let inode3 = inode.clone();
346        let mut info3 = info.clone();
347        info3.target = PathBuf::from("/h/i/j");
348        let node3 = Node::new(inode3, info3, 1);
349        let node3 = TreeNode::new(RefCell::from(node3));
350        prefetch.insert(&node3, &node3.borrow());
351
352        let inode4 = inode.clone();
353        let mut info4 = info.clone();
354        info4.target = PathBuf::from("/z");
355        let node4 = Node::new(inode4, info4, 1);
356        let node4 = TreeNode::new(RefCell::from(node4));
357        prefetch.insert(&node4, &node4.borrow());
358
359        let inode5 = inode.clone();
360        inode.set_mode(0o755 | libc::S_IFDIR as u32);
361        inode.set_size(0);
362        let mut info5 = info;
363        info5.target = PathBuf::from("/a/b/d");
364        let node5 = Node::new(inode5, info5, 1);
365        let node5 = TreeNode::new(RefCell::from(node5));
366        prefetch.insert(&node5, &node5.borrow());
367
368        // node1, node2
369        assert_eq!(prefetch.fs_prefetch_rule_count(), 2);
370
371        let (pre, non_pre) = prefetch.get_file_nodes();
372        assert_eq!(pre.len(), 4);
373        assert_eq!(non_pre.len(), 1);
374        let pre_str: Vec<String> = pre
375            .iter()
376            .map(|n| n.borrow().target().to_str().unwrap().to_owned())
377            .collect();
378        assert_eq!(pre_str, vec!["/a/b", "/a/b/d", "/f", "/h/i/j"]);
379        let non_pre_str: Vec<String> = non_pre
380            .iter()
381            .map(|n| n.borrow().target().to_str().unwrap().to_owned())
382            .collect();
383        assert_eq!(non_pre_str, vec!["/z"]);
384
385        prefetch.clear();
386        assert_eq!(prefetch.fs_prefetch_rule_count(), 0);
387        let (pre, non_pre) = prefetch.get_file_nodes();
388        assert_eq!(pre.len(), 0);
389        assert_eq!(non_pre.len(), 0);
390    }
391}
nydus_builder/core/prefetch.rs

nydus_builder/core/
prefetch.rs
