ternaria_fs/
image.rs

1//! Building a TFS image on the host.
2//!
3//! The guest driver reads and writes an image; this builds one. A filesystem
4//! needs to exist before a driver can be tested against it, and formatting a
5//! disk from inside a machine that cannot yet read a disk is a bootstrap
6//! problem better solved on the host.
7//!
8//! # Why fields are stored in base 243
9//!
10//! A stored word is three trytes, and every tryte crossing to the image must be
11//! a byte: 0 to 255. That leaves a choice of radix for spreading a value across
12//! the three.
13//!
14//! The obvious choice is 256, which is what a binary filesystem would use. It
15//! is a poor one here. Reassembling a field would mean computing
16//! `t0 + 256*t1 + 65536*t2`, and 256 is not a power of three, so each of those
17//! is a genuine multiply on every metadata access.
18//!
19//! Base 243 is used instead. It is 3^5, so it is a power of three, and it is
20//! below 256, so every digit is still a valid byte. Reassembling a field
21//! becomes `t0 + (t1 << 5) + (t2 << 10)` in trit shifts, which the machine does
22//! with `shl` in one instruction each.
23//!
24//! The cost is range: a stored word reaches 243^3 - 1 rather than 256^3 - 1, a
25//! loss of about 15 per cent. The fields this format stores are block numbers,
26//! inode numbers and file sizes, all far below either limit.
27
28use crate::{
29    BLOCK_TRYTES, DIRECT_BLOCKS, DIRENT_TRYTES, INODE_TRYTES, INODES_PER_BLOCK, MAGIC,
30    MAX_FILE_TRYTES, NAME_TRYTES, ROOT_INODE, WORD_TRYTES, ino, kind, sb,
31};
32
33/// How a value is split across the trytes of a word.
34///
35/// 3^5, so a digit is a trit shift away rather than a multiply, and under 256,
36/// so a digit is still a byte. See the module documentation.
37pub const RADIX: i64 = 243;
38
39/// Trits per stored digit: `RADIX` is 3 to this power.
40pub const RADIX_TRITS: u32 = 5;
41
42/// Largest value a stored word can hold.
43pub const MAX_STORED: i64 = RADIX * RADIX * RADIX - 1;
44
45/// Something the builder could not do.
46#[derive(Clone, PartialEq, Eq, Debug)]
47pub enum BuildError {
48    /// The image has no free block left.
49    OutOfBlocks,
50    /// The image has no free inode left.
51    OutOfInodes,
52    /// A file was larger than the format's direct blocks can address.
53    FileTooLarge {
54        /// How many trytes were asked for.
55        wanted: usize,
56        /// The most the format can hold.
57        limit: usize,
58    },
59    /// A name did not fit a directory entry.
60    NameTooLong {
61        /// The offending name.
62        name: String,
63    },
64    /// A path component named something that is not a directory.
65    NotADirectory {
66        /// The offending component.
67        name: String,
68    },
69    /// A value did not fit the three trytes a stored word has.
70    ValueTooLarge {
71        /// The offending value.
72        value: i64,
73    },
74}
75
76impl std::fmt::Display for BuildError {
77    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
78        match self {
79            BuildError::OutOfBlocks => write!(f, "no free block"),
80            BuildError::OutOfInodes => write!(f, "no free inode"),
81            BuildError::FileTooLarge { wanted, limit } => {
82                write!(f, "file of {wanted} trytes exceeds the limit of {limit}")
83            }
84            BuildError::NameTooLong { name } => write!(f, "name {name:?} is too long"),
85            BuildError::NotADirectory { name } => write!(f, "{name:?} is not a directory"),
86            BuildError::ValueTooLarge { value } => {
87                write!(f, "value {value} does not fit a stored word")
88            }
89        }
90    }
91}
92
93impl std::error::Error for BuildError {}
94
95/// Builds a TFS image.
96pub struct Builder {
97    bytes: Vec<u8>,
98    total_blocks: usize,
99    map_start: usize,
100    map_blocks: usize,
101    inode_start: usize,
102    inode_blocks: usize,
103    data_start: usize,
104}
105
106impl Builder {
107    /// A freshly formatted image of `total_blocks` blocks.
108    ///
109    /// The layout is derived rather than fixed: the allocation map is sized to
110    /// cover the image at one tryte per block, and the inode table is sized to
111    /// one inode per four blocks, which is generous for a small disk and costs
112    /// little.
113    pub fn new(total_blocks: usize) -> Builder {
114        let map_blocks = total_blocks.div_ceil(BLOCK_TRYTES).max(1);
115        let inodes = (total_blocks / 4).max(INODES_PER_BLOCK);
116        let inode_blocks = inodes.div_ceil(INODES_PER_BLOCK);
117
118        let map_start = 1;
119        let inode_start = map_start + map_blocks;
120        let data_start = inode_start + inode_blocks;
121
122        let mut b = Builder {
123            bytes: vec![0u8; total_blocks * BLOCK_TRYTES],
124            total_blocks,
125            map_start,
126            map_blocks,
127            inode_start,
128            inode_blocks,
129            data_start,
130        };
131        b.write_superblock();
132        // Everything up to the first data block is metadata and is in use.
133        for block in 0..data_start {
134            b.set_block_used(block, true);
135        }
136        // The root directory exists in an empty filesystem.
137        b.set_inode_word(ROOT_INODE, ino::KIND, kind::DIRECTORY);
138        b.set_inode_word(ROOT_INODE, ino::SIZE, 0);
139        b
140    }
141
142    /// The finished image.
143    pub fn finish(self) -> Vec<u8> {
144        self.bytes
145    }
146
147    /// Reopens an existing image, reading its layout from the superblock.
148    ///
149    /// For a host inspecting what a guest wrote. The layout fields are read
150    /// back rather than recomputed, so an image built by something else is
151    /// still readable as long as its superblock is honest.
152    pub fn from_image(bytes: Vec<u8>) -> Builder {
153        let get = |tryte_offset: usize| -> i64 {
154            let mut acc = 0i64;
155            let mut weight = 1i64;
156            for k in 0..WORD_TRYTES {
157                acc += bytes[tryte_offset + k] as i64 * weight;
158                weight *= RADIX;
159            }
160            acc
161        };
162        Builder {
163            total_blocks: get(sb::TOTAL_BLOCKS * WORD_TRYTES) as usize,
164            map_start: get(sb::MAP_START * WORD_TRYTES) as usize,
165            map_blocks: get(sb::MAP_BLOCKS * WORD_TRYTES) as usize,
166            inode_start: get(sb::INODE_START * WORD_TRYTES) as usize,
167            inode_blocks: get(sb::INODE_BLOCKS * WORD_TRYTES) as usize,
168            data_start: get(sb::DATA_START * WORD_TRYTES) as usize,
169            bytes,
170        }
171    }
172
173    /// How many entries a directory holds.
174    pub fn dir_len(&self, inode: i64) -> i64 {
175        self.inode_word(inode, ino::SIZE)
176    }
177
178    /// A direct block pointer of an inode, for a host checking allocation.
179    pub fn inode_direct(&self, inode: i64, index: usize) -> i64 {
180        self.inode_word(inode, ino::DIRECT + index)
181    }
182
183    /// The kind of an inode, for a host checking what a guest created.
184    pub fn inode_kind(&self, inode: i64) -> i64 {
185        self.inode_word(inode, ino::KIND)
186    }
187
188    /// The contents of a file inode.
189    pub fn read_file(&self, inode: i64) -> Vec<u8> {
190        let size = self.inode_word(inode, ino::SIZE) as usize;
191        let mut out = Vec::with_capacity(size);
192        for index in 0..DIRECT_BLOCKS {
193            if out.len() >= size {
194                break;
195            }
196            let block = self.inode_word(inode, ino::DIRECT + index);
197            if block == 0 {
198                break;
199            }
200            let at = block as usize * BLOCK_TRYTES;
201            let take = (size - out.len()).min(BLOCK_TRYTES);
202            out.extend_from_slice(&self.bytes[at..at + take]);
203        }
204        out
205    }
206
207    /// The bytes so far, for inspection without consuming the builder.
208    pub fn bytes(&self) -> &[u8] {
209        &self.bytes
210    }
211
212    /// First block available for data.
213    pub fn data_start(&self) -> usize {
214        self.data_start
215    }
216
217    // ---------------------------------------------------------------- fields
218
219    fn put_word(&mut self, tryte_offset: usize, value: i64) {
220        // Callers inside this module pass block numbers and sizes, all small.
221        // A public entry point checks first; this is the unchecked worker.
222        let mut v = value;
223        for k in 0..WORD_TRYTES {
224            self.bytes[tryte_offset + k] = (v % RADIX) as u8;
225            v /= RADIX;
226        }
227    }
228
229    fn get_word(&self, tryte_offset: usize) -> i64 {
230        let mut acc = 0i64;
231        let mut weight = 1i64;
232        for k in 0..WORD_TRYTES {
233            acc += self.bytes[tryte_offset + k] as i64 * weight;
234            weight *= RADIX;
235        }
236        acc
237    }
238
239    fn checked_word(value: i64) -> Result<i64, BuildError> {
240        if (0..=MAX_STORED).contains(&value) {
241            Ok(value)
242        } else {
243            Err(BuildError::ValueTooLarge { value })
244        }
245    }
246
247    fn write_superblock(&mut self) {
248        let fields = [
249            (sb::MAGIC, MAGIC),
250            (sb::TOTAL_BLOCKS, self.total_blocks as i64),
251            (sb::MAP_START, self.map_start as i64),
252            (sb::MAP_BLOCKS, self.map_blocks as i64),
253            (sb::INODE_START, self.inode_start as i64),
254            (sb::INODE_BLOCKS, self.inode_blocks as i64),
255            (sb::DATA_START, self.data_start as i64),
256            (sb::ROOT, ROOT_INODE),
257        ];
258        for (word, value) in fields {
259            self.put_word(word * WORD_TRYTES, value);
260        }
261    }
262
263    // ------------------------------------------------------- allocation map
264
265    fn map_offset(&self, block: usize) -> usize {
266        self.map_start * BLOCK_TRYTES + block
267    }
268
269    fn set_block_used(&mut self, block: usize, used: bool) {
270        let at = self.map_offset(block);
271        self.bytes[at] = u8::from(used);
272    }
273
274    /// True if the allocation map marks `block` as in use.
275    pub fn is_block_used(&self, block: usize) -> bool {
276        self.bytes[self.map_offset(block)] != 0
277    }
278
279    fn alloc_block(&mut self) -> Result<usize, BuildError> {
280        for block in self.data_start..self.total_blocks {
281            if !self.is_block_used(block) {
282                self.set_block_used(block, true);
283                return Ok(block);
284            }
285        }
286        Err(BuildError::OutOfBlocks)
287    }
288
289    // ---------------------------------------------------------------- inodes
290
291    fn inode_offset(&self, inode: i64) -> usize {
292        self.inode_start * BLOCK_TRYTES + (inode as usize) * INODE_TRYTES
293    }
294
295    fn set_inode_word(&mut self, inode: i64, word: usize, value: i64) {
296        let at = self.inode_offset(inode) + word * WORD_TRYTES;
297        self.put_word(at, value);
298    }
299
300    fn inode_word(&self, inode: i64, word: usize) -> i64 {
301        self.get_word(self.inode_offset(inode) + word * WORD_TRYTES)
302    }
303
304    fn inode_capacity(&self) -> i64 {
305        (self.inode_blocks * INODES_PER_BLOCK) as i64
306    }
307
308    fn alloc_inode(&mut self, k: i64) -> Result<i64, BuildError> {
309        // Inode 0 means "none", so allocation starts at 1.
310        for inode in 1..self.inode_capacity() {
311            if self.inode_word(inode, ino::KIND) == kind::FREE {
312                self.set_inode_word(inode, ino::KIND, k);
313                self.set_inode_word(inode, ino::SIZE, 0);
314                return Ok(inode);
315            }
316        }
317        Err(BuildError::OutOfInodes)
318    }
319
320    // ------------------------------------------------------------ directories
321
322    /// Appends an entry to a directory inode.
323    fn link(&mut self, dir: i64, name: &str, target: i64) -> Result<(), BuildError> {
324        if name.len() > NAME_TRYTES {
325            return Err(BuildError::NameTooLong {
326                name: name.to_string(),
327            });
328        }
329        let used = self.inode_word(dir, ino::SIZE) as usize;
330        let block_index = used / crate::DIRENTS_PER_BLOCK;
331        if block_index >= DIRECT_BLOCKS {
332            return Err(BuildError::OutOfBlocks);
333        }
334
335        // Grow the directory by a block if this entry starts a new one.
336        let mut block = self.inode_word(dir, ino::DIRECT + block_index);
337        if block == 0 {
338            block = self.alloc_block()? as i64;
339            self.set_inode_word(dir, ino::DIRECT + block_index, block);
340        }
341
342        let slot = used % crate::DIRENTS_PER_BLOCK;
343        let at = block as usize * BLOCK_TRYTES + slot * DIRENT_TRYTES;
344        self.put_word(at, target);
345        for (k, byte) in name.bytes().enumerate() {
346            self.bytes[at + WORD_TRYTES + k] = byte;
347        }
348        self.set_inode_word(dir, ino::SIZE, used as i64 + 1);
349        Ok(())
350    }
351
352    /// Resolves a directory path, creating nothing.
353    fn resolve_dir(&self, path: &str) -> Result<i64, BuildError> {
354        let mut dir = ROOT_INODE;
355        for part in path.split('/').filter(|p| !p.is_empty()) {
356            dir = self
357                .lookup(dir, part)
358                .ok_or_else(|| BuildError::NotADirectory {
359                    name: part.to_string(),
360                })?;
361            if self.inode_word(dir, ino::KIND) != kind::DIRECTORY {
362                return Err(BuildError::NotADirectory {
363                    name: part.to_string(),
364                });
365            }
366        }
367        Ok(dir)
368    }
369
370    /// Finds `name` in directory `dir`.
371    pub fn lookup(&self, dir: i64, name: &str) -> Option<i64> {
372        let used = self.inode_word(dir, ino::SIZE) as usize;
373        for index in 0..used {
374            let block_index = index / crate::DIRENTS_PER_BLOCK;
375            let slot = index % crate::DIRENTS_PER_BLOCK;
376            let block = self.inode_word(dir, ino::DIRECT + block_index);
377            if block == 0 {
378                continue;
379            }
380            let at = block as usize * BLOCK_TRYTES + slot * DIRENT_TRYTES;
381            let target = self.get_word(at);
382            if target == 0 {
383                continue;
384            }
385            let raw = &self.bytes[at + WORD_TRYTES..at + DIRENT_TRYTES];
386            let end = raw.iter().position(|b| *b == 0).unwrap_or(raw.len());
387            if raw[..end] == *name.as_bytes() {
388                return Some(target);
389            }
390        }
391        None
392    }
393
394    // --------------------------------------------------------- public writing
395
396    /// Creates a directory at `path`, which must not already exist.
397    ///
398    /// Parent directories must exist. `path` is absolute with or without a
399    /// leading slash.
400    pub fn mkdir(&mut self, path: &str) -> Result<i64, BuildError> {
401        let (parent, name) = self.split_parent(path)?;
402        let inode = self.alloc_inode(kind::DIRECTORY)?;
403        self.link(parent, name, inode)?;
404        Ok(inode)
405    }
406
407    /// Creates a file at `path` holding `data`, one byte per tryte.
408    pub fn write_file(&mut self, path: &str, data: &[u8]) -> Result<i64, BuildError> {
409        if data.len() > MAX_FILE_TRYTES {
410            return Err(BuildError::FileTooLarge {
411                wanted: data.len(),
412                limit: MAX_FILE_TRYTES,
413            });
414        }
415        let (parent, name) = self.split_parent(path)?;
416        let inode = self.alloc_inode(kind::FILE)?;
417        Self::checked_word(data.len() as i64)?;
418        self.set_inode_word(inode, ino::SIZE, data.len() as i64);
419
420        for (index, chunk) in data.chunks(BLOCK_TRYTES).enumerate() {
421            let block = self.alloc_block()?;
422            self.set_inode_word(inode, ino::DIRECT + index, block as i64);
423            let at = block * BLOCK_TRYTES;
424            self.bytes[at..at + chunk.len()].copy_from_slice(chunk);
425        }
426        self.link(parent, name, inode)?;
427        Ok(inode)
428    }
429
430    /// Splits a path into its parent directory and its final component.
431    fn split_parent<'p>(&self, path: &'p str) -> Result<(i64, &'p str), BuildError> {
432        let trimmed = path.trim_end_matches('/');
433        let (dir_path, name) = match trimmed.rfind('/') {
434            Some(cut) => (&trimmed[..cut], &trimmed[cut + 1..]),
435            None => ("", trimmed),
436        };
437        Ok((self.resolve_dir(dir_path)?, name))
438    }
439}
ternaria_fs/image.rs

ternaria_fs/
image.rs
