wasmtime_vfs_ledger/
lib.rs

1use std::collections::BTreeSet;
2use std::ops::{Deref, Range};
3use std::sync::{Arc, Mutex};
4
5/// A potentially infinite stream of unique `u64` ids.
6///
7/// You can call `.next()` to allocate a new identifier. This will return
8/// `None` if the stream is exhausted. However, unused identifiers can be
9/// returned to the stream with `.free()` and will be reused.
10struct Reusable {
11    // A set of all free, discontiguous identifiers.
12    free: BTreeSet<u64>,
13
14    // A set of all free, contiguous identifiers.
15    next: Range<u64>,
16}
17
18impl Default for Reusable {
19    fn default() -> Self {
20        Reusable {
21            free: BTreeSet::new(),
22            next: 0..u64::MAX,
23        }
24    }
25}
26
27impl Iterator for Reusable {
28    type Item = u64;
29
30    fn next(&mut self) -> Option<Self::Item> {
31        // Try to reuse an identifier from the discontiguous set.
32        // Fall back to allocating from the contiguous range.
33        self.free.pop_first().or_else(|| self.next.next())
34    }
35}
36
37impl Reusable {
38    fn free(&mut self, id: u64) {
39        // Detect double-free conditions.
40        debug_assert!(id < self.next.start);
41        debug_assert!(!self.free.contains(&id));
42
43        // Insert the freed id into the discontiguous set.
44        self.free.insert(id);
45
46        // Attempt to move the discontiguous set into the contiguous range.
47        while self.next.start > 0 {
48            let prev = self.next.start - 1;
49            if !self.free.remove(&prev) {
50                break;
51            }
52
53            self.next.start = prev;
54        }
55    }
56}
57
58/// A ledger of filesystem devices.
59pub struct Ledger(Mutex<Reusable>);
60
61impl Ledger {
62    /// Create a new ledger.
63    pub fn new() -> Arc<Ledger> {
64        Arc::new(Ledger(Default::default()))
65    }
66
67    /// Allocate a new device.
68    pub fn create_device(self: Arc<Self>) -> Arc<DeviceId> {
69        let id = self.0.lock().unwrap().next().expect("out of devices");
70        Arc::new(DeviceId {
71            id,
72            inodes: Default::default(),
73            devices: self,
74        })
75    }
76}
77
78/// A filesystem device identifier.
79pub struct DeviceId {
80    devices: Arc<Ledger>,
81    inodes: Mutex<Reusable>,
82    id: u64,
83}
84
85impl Drop for DeviceId {
86    fn drop(&mut self) {
87        self.devices.0.lock().unwrap().free(self.id);
88    }
89}
90
91impl Deref for DeviceId {
92    type Target = u64;
93
94    fn deref(&self) -> &Self::Target {
95        &self.id
96    }
97}
98
99impl Eq for DeviceId {}
100impl PartialEq for DeviceId {
101    fn eq(&self, other: &Self) -> bool {
102        self.id == other.id
103    }
104}
105
106impl DeviceId {
107    /// Get a reference to the ledger.
108    pub fn ledger(&self) -> Arc<Ledger> {
109        self.devices.clone()
110    }
111
112    /// Allocate a new inode.
113    pub fn create_inode(self: Arc<Self>) -> Arc<InodeId> {
114        let id = self.inodes.lock().unwrap().next().expect("out of inodes");
115        Arc::new(InodeId { id, device: self })
116    }
117}
118
119/// A filesystem inode identifier.
120pub struct InodeId {
121    device: Arc<DeviceId>,
122    id: u64,
123}
124
125impl Drop for InodeId {
126    fn drop(&mut self) {
127        self.device.inodes.lock().unwrap().free(self.id);
128    }
129}
130
131impl Deref for InodeId {
132    type Target = u64;
133
134    fn deref(&self) -> &Self::Target {
135        &self.id
136    }
137}
138
139impl Eq for InodeId {}
140impl PartialEq for InodeId {
141    fn eq(&self, other: &Self) -> bool {
142        self.device == other.device && self.id == other.id
143    }
144}
145
146impl InodeId {
147    /// Get a reference to the device.
148    pub fn device(&self) -> Arc<DeviceId> {
149        self.device.clone()
150    }
151}
152
153#[cfg(test)]
154mod test {
155    use crate::Ledger;
156
157    #[test]
158    fn reuse() {
159        // Test the first inode number.
160        let inode00 = Ledger::new().create_device().create_inode();
161        assert_eq!(**inode00.device(), 0);
162        assert_eq!(**inode00, 0);
163
164        // Test the second inode number.
165        let inode01 = inode00.device().create_inode();
166        assert_eq!(**inode01.device(), 0);
167        assert_eq!(**inode01, 1);
168
169        // Test the first inode on a new device.
170        let inode10 = inode00.device().ledger().create_device().create_inode();
171        assert_eq!(**inode10.device(), 1);
172        assert_eq!(**inode10, 0);
173
174        // Test the third inode number.
175        let inode02 = inode00.device().create_inode();
176        assert_eq!(**inode02.device(), 0);
177        assert_eq!(**inode02, 2);
178
179        // Test the second inode on a new device.
180        let inode11 = inode10.device().create_inode();
181        assert_eq!(**inode11.device(), 1);
182        assert_eq!(**inode11, 1);
183
184        // Test the third inode on a new device.
185        let inode12 = inode11.device().create_inode();
186        assert_eq!(**inode12.device(), 1);
187        assert_eq!(**inode12, 2);
188
189        drop(inode01);
190        drop(inode12);
191
192        // Test inode reuse.
193        let inode01 = inode00.device().create_inode();
194        assert_eq!(**inode01.device(), 0);
195        assert_eq!(**inode01, 1);
196
197        // Test inode reuse on a new device.
198        let inode12 = inode10.device().create_inode();
199        assert_eq!(**inode12.device(), 1);
200        assert_eq!(**inode12, 2);
201
202        drop(inode00);
203        drop(inode01);
204        drop(inode02);
205
206        // Test device reuse.
207        let inode00 = inode10.device().ledger().create_device().create_inode();
208        assert_eq!(**inode00.device(), 0);
209        assert_eq!(**inode00, 0);
210    }
211}
wasmtime_vfs_ledger/lib.rs

wasmtime_vfs_ledger/
lib.rs
