fuse_backend_rs/overlayfs/
inode_store.rs

1// Copyright (C) 2023 Ant Group. All rights reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4use std::io::{Error, ErrorKind, Result};
5use std::{
6    collections::HashMap,
7    sync::{atomic::Ordering, Arc},
8};
9
10use super::{Inode, OverlayInode, VFS_MAX_INO};
11
12use radix_trie::Trie;
13
14pub struct InodeStore {
15    // Active inodes.
16    inodes: HashMap<Inode, Arc<OverlayInode>>,
17    // Deleted inodes which were unlinked but have non zero lookup count.
18    deleted: HashMap<Inode, Arc<OverlayInode>>,
19    // Path to inode mapping, used to reserve inode number for same path.
20    path_mapping: Trie<String, Inode>,
21    next_inode: u64,
22}
23
24impl InodeStore {
25    pub(crate) fn new() -> Self {
26        Self {
27            inodes: HashMap::new(),
28            deleted: HashMap::new(),
29            path_mapping: Trie::new(),
30            next_inode: 1,
31        }
32    }
33
34    pub(crate) fn alloc_unique_inode(&mut self) -> Result<Inode> {
35        // Iter VFS_MAX_INO times to find a free inode number.
36        let mut ino = self.next_inode;
37        for _ in 0..VFS_MAX_INO {
38            if ino > VFS_MAX_INO {
39                ino = 1;
40            }
41            if !self.inodes.contains_key(&ino) && !self.deleted.contains_key(&ino) {
42                self.next_inode = ino + 1;
43                return Ok(ino);
44            }
45            ino += 1;
46        }
47        error!("reached maximum inode number: {}", VFS_MAX_INO);
48        Err(Error::new(
49            ErrorKind::Other,
50            format!("maximum inode number {} reached", VFS_MAX_INO),
51        ))
52    }
53
54    pub(crate) fn alloc_inode(&mut self, path: &String) -> Result<Inode> {
55        match self.path_mapping.get(path) {
56            // If the path is already in the mapping, return the reserved inode number.
57            Some(v) => Ok(*v),
58            // Or allocate a new inode number.
59            None => self.alloc_unique_inode(),
60        }
61    }
62
63    pub(crate) fn insert_inode(&mut self, inode: Inode, node: Arc<OverlayInode>) {
64        self.path_mapping.insert(node.path.clone(), inode);
65        self.inodes.insert(inode, node);
66    }
67
68    pub(crate) fn get_inode(&self, inode: Inode) -> Option<Arc<OverlayInode>> {
69        self.inodes.get(&inode).cloned()
70    }
71
72    pub(crate) fn get_deleted_inode(&self, inode: Inode) -> Option<Arc<OverlayInode>> {
73        self.deleted.get(&inode).cloned()
74    }
75
76    // Return the inode only if it's permanently deleted from both self.inodes and self.deleted_inodes.
77    pub(crate) fn remove_inode(
78        &mut self,
79        inode: Inode,
80        path_removed: Option<String>,
81    ) -> Option<Arc<OverlayInode>> {
82        let removed = match self.inodes.remove(&inode) {
83            Some(v) => {
84                // Refcount is not 0, we have to delay the removal.
85                if v.lookups.load(Ordering::Relaxed) > 0 {
86                    self.deleted.insert(inode, v.clone());
87                    return None;
88                }
89                Some(v)
90            }
91            None => {
92                // If the inode is not in hash, it must be in deleted_inodes.
93                match self.deleted.get(&inode) {
94                    Some(v) => {
95                        // Refcount is 0, the inode can be removed now.
96                        if v.lookups.load(Ordering::Relaxed) == 0 {
97                            self.deleted.remove(&inode)
98                        } else {
99                            // Refcount is not 0, the inode will be removed later.
100                            None
101                        }
102                    }
103                    None => None,
104                }
105            }
106        };
107
108        if let Some(path) = path_removed {
109            self.path_mapping.remove(&path);
110        }
111        removed
112    }
113
114    // As a debug function, print all inode numbers in hash table.
115    // This function consumes quite lots of memory, so it's disabled by default.
116    #[allow(dead_code)]
117    pub(crate) fn debug_print_all_inodes(&self) {
118        // Convert the HashMap to Vector<(inode, pathname)>
119        let mut all_inodes = self
120            .inodes
121            .iter()
122            .map(|(inode, ovi)| (inode, ovi.path.clone(), ovi.lookups.load(Ordering::Relaxed)))
123            .collect::<Vec<_>>();
124        all_inodes.sort_by(|a, b| a.0.cmp(b.0));
125        trace!("all active inodes: {:?}", all_inodes);
126
127        let mut to_delete = self
128            .deleted
129            .iter()
130            .map(|(inode, ovi)| (inode, ovi.path.clone(), ovi.lookups.load(Ordering::Relaxed)))
131            .collect::<Vec<_>>();
132        to_delete.sort_by(|a, b| a.0.cmp(b.0));
133        trace!("all deleted inodes: {:?}", to_delete);
134    }
135}
136
137#[cfg(test)]
138mod test {
139    use super::*;
140
141    #[test]
142    fn test_alloc_unique() {
143        let mut store = InodeStore::new();
144        let empty_node = Arc::new(OverlayInode::new());
145        store.insert_inode(1, empty_node.clone());
146        store.insert_inode(2, empty_node.clone());
147        store.insert_inode(VFS_MAX_INO - 1, empty_node.clone());
148
149        let inode = store.alloc_unique_inode().unwrap();
150        assert_eq!(inode, 3);
151        assert_eq!(store.next_inode, 4);
152
153        store.next_inode = VFS_MAX_INO - 1;
154        let inode = store.alloc_unique_inode().unwrap();
155        assert_eq!(inode, VFS_MAX_INO);
156
157        let inode = store.alloc_unique_inode().unwrap();
158        assert_eq!(inode, 3);
159    }
160
161    #[test]
162    fn test_alloc_existing_path() {
163        let mut store = InodeStore::new();
164        let mut node_a = OverlayInode::new();
165        node_a.path = "/a".to_string();
166        store.insert_inode(1, Arc::new(node_a));
167        let mut node_b = OverlayInode::new();
168        node_b.path = "/b".to_string();
169        store.insert_inode(2, Arc::new(node_b));
170        let mut node_c = OverlayInode::new();
171        node_c.path = "/c".to_string();
172        store.insert_inode(VFS_MAX_INO - 1, Arc::new(node_c));
173
174        let inode = store.alloc_inode(&"/a".to_string()).unwrap();
175        assert_eq!(inode, 1);
176
177        let inode = store.alloc_inode(&"/b".to_string()).unwrap();
178        assert_eq!(inode, 2);
179
180        let inode = store.alloc_inode(&"/c".to_string()).unwrap();
181        assert_eq!(inode, VFS_MAX_INO - 1);
182
183        let inode = store.alloc_inode(&"/notexist".to_string()).unwrap();
184        assert_eq!(inode, 3);
185    }
186
187    #[test]
188    fn test_remove_inode() {
189        let mut store = InodeStore::new();
190        let mut node_a = OverlayInode::new();
191        node_a.lookups.fetch_add(1, Ordering::Relaxed);
192        node_a.path = "/a".to_string();
193        store.insert_inode(1, Arc::new(node_a));
194
195        let mut node_b = OverlayInode::new();
196        node_b.path = "/b".to_string();
197        store.insert_inode(2, Arc::new(node_b));
198
199        let mut node_c = OverlayInode::new();
200        node_c.lookups.fetch_add(1, Ordering::Relaxed);
201        node_c.path = "/c".to_string();
202        store.insert_inode(VFS_MAX_INO - 1, Arc::new(node_c));
203
204        let inode = store.alloc_inode(&"/new".to_string()).unwrap();
205        assert_eq!(inode, 3);
206
207        // Not existing.
208        let inode = store.remove_inode(4, None);
209        assert!(inode.is_none());
210
211        // Existing but with non-zero refcount.
212        let inode = store.remove_inode(1, None);
213        assert!(inode.is_none());
214        assert!(store.get_deleted_inode(1).is_some());
215        assert!(store.path_mapping.get(&"/a".to_string()).is_some());
216
217        // Remove again with file path.
218        let inode = store.remove_inode(1, Some("/a".to_string()));
219        assert!(inode.is_none());
220        assert!(store.get_deleted_inode(1).is_some());
221        assert!(store.path_mapping.get(&"/a".to_string()).is_none());
222
223        // Node b has refcount 0, removing will be permanent.
224        let inode = store.remove_inode(2, Some("/b".to_string()));
225        assert!(inode.is_some());
226        assert!(store.get_deleted_inode(2).is_none());
227        assert!(store.path_mapping.get(&"/b".to_string()).is_none());
228
229        // Allocate new inode, it should reuse inode 2 since inode 1 is still in deleted list.
230        store.next_inode = 1;
231        let inode = store.alloc_inode(&"/b".to_string()).unwrap();
232        assert_eq!(inode, 2);
233
234        // Allocate inode with path "/c" will reuse its inode number.
235        let inode = store.alloc_inode(&"/c".to_string()).unwrap();
236        assert_eq!(inode, VFS_MAX_INO - 1);
237    }
238}
fuse_backend_rs/overlayfs/inode_store.rs

fuse_backend_rs/overlayfs/
inode_store.rs
