This is part of a larger tutorial: The Adventures of OS: Making a RISC-V Operating System using Rust.

We wrote the code in our Minix 3 file system to read an inode and then read the direct, indirect, doubly-indirect, and triply-indirect pointers that point to the data relevant to the given inode. However, we were required to do a stat in order to see what inode we needed to get. Obviously, this isn’t how file systems actually work. Instead, we want to search for a given inode by its name.

Recall that in Minix 3, we have a directory entry structure, which in Rust looks as follows.

#[repr(C)]
pub struct DirEntry {
	pub inode: u32,
	pub name:  [u8; 60]
}

The code above shows that we have a 4-byte inode and a 60-byte name. This is how we link a name to an inode. In fact, we can have multiple names link to the same inode–these would be called hard links. This is also why we don’t have a delete filesystem function. Instead, it is called unlink. When we unlink, we break a name to inode linkage. Whenever there are no more links left, the file is considered deleted.

Where do we find these DirEntry structures? That’s fairly simple. Recall that whenever we read a file, we go to the 10 “zone” pointers. For a regular file, when we go to the ends of each pointer, we find the actual data that belongs to the file. However, if the file in question is a directory, which we would know by looking at the inode’s mode, then these pointers point to a bunch of DirEntry structures.

For a block size of 1,024 bytes, we have \(1,024 / 64 = 16\) total DirEntries per block. Recall that we have a 4-byte inode and a 60-byte name, which is why each structure takes 64 bytes.

Another issue we run into is searching the directory entries. This is a very expensive task since we only get 16 entries per block. Therefore, we need to cache the inodes. In other words, we need to put something in memory to make look-ups quicker. Fortunately, this is fairly straightforward to do.

Our game plan is to look for all directory entries in the file system and store them in a some format where lookups are quick. We don’t really care about insertion or deletion times, but we will be doing a ton of lookups. So, let’s add some code to cache inodes. We will start whenever we initialize a file system. We are given the block device that backs the file system. This way here, we can use our virtio block driver to read and write to it.

static mut MFS_INODE_CACHE: [Option<BTreeMap<String, Inode>>; 8] =
	[None, None, None, None, None, None, None, None];

We don’t quite have a virtual filesystem yet, so we’re doing much like a DOS based allocation system. So, essentially we are blockdevice:, such as 8: (remember in DOS, we had C:?). Then, whenever we get into that block device, we have our underlying file system. Currently, we cannot just mount one file system into the directory structure of another. However, with a VFS, we would have a single map that stores the entire file system. Instead of mapping strings to Inodes, we would need to map strings to some sort of structure that told us what block device to go to and then the Inode or some identifying value.

Notice that I’m using the BTreeMap here. This is built-in to Rust’s alloc::collections library, which then hooks to the global allocator we wrote a loooooooong time ago.

We will be storing the entries by path–this is our key. Then, we will store the Inode of that entry as the value. This should give us all the information we need.

So, now we need a game plan to actually cache the inodes. First, we need to know the directory structure. Recall that in Minix 3, we only know the name of the given file in the DirEntry structure. We don’t know the full path, so that’s something we will need to keep up with ourselves. So, here’s our init() function in Rust.

pub fn init(bdev: usize) {
	if unsafe { MFS_INODE_CACHE[bdev - 1].is_none() } {
		let mut btm = BTreeMap::new();
		let cwd = String::from("/");
		// Let's look at the root (inode #1)
		Self::cache_at(&mut btm, &cwd, 1, bdev);
		unsafe {
			MFS_INODE_CACHE[bdev - 1] = Some(btm);
		}
	}
	else {
		println!(
		         "KERNEL: Initialized an already initialized \
		          filesystem {}",
		         bdev
		);
	}
}

As you can see above, we allocate a string (String::from(“/”)), which is the root directory. Then, we look at each directory entry in the root. If we hit yet another directory, we recursively do the same thing until there are no more directories. So, our cache will store both directories and regular files–their paths and inodes, not the actual data.

As a side note, Rust requires that we add unsafe {} because this is a mutable static variable, meaning that it is global and can be changed, hence, it is not thread-safe unless we added locking.

So, let’s take a look at the function that actually does the work. This is the Self::cache_at function that you see above.

fn cache_at(btm: &mut BTreeMap<String, Inode>, cwd: &String, inode_num: u32, bdev: usize) {
   let ino = Self::get_inode(bdev, inode_num).unwrap();
   let mut buf = Buffer::new(((ino.size + BLOCK_SIZE - 1) & !BLOCK_SIZE) as usize);
   let dirents = buf.get() as *const DirEntry;
   let sz = Self::read(bdev, &ino, buf.get_mut(), BLOCK_SIZE, 0);
   let num_dirents = sz as usize / size_of::<DirEntry>();
   // We start at 2 because the first two entries are . and ..
   for i in 2..num_dirents {
      unsafe {
         let ref d = *dirents.add(i);
         let d_ino = Self::get_inode(bdev, d.inode).unwrap();
         let mut new_cwd = String::with_capacity(120);
         for i in cwd.bytes() {
            new_cwd.push(i as char);
         }
         // Add a directory separator between this inode and the next.
         // If we're the root (inode 1), we don't want to double up the
         // frontslash, so only do it for non-roots.
         if inode_num != 1 {
            new_cwd.push('/');
         }
         for i in 0..60 {
            if d.name[i] == 0 {
               break;
            }
            new_cwd.push(d.name[i] as char);
         }
         new_cwd.shrink_to_fit();
         if d_ino.mode & S_IFDIR != 0 {
            // This is a directory, cache these. This is a recursive call, which I don't really like.
            Self::cache_at(btm, &new_cwd, d.inode, bdev);
         }
         else {
            btm.insert(new_cwd, d_ino);
         }
      }
   }
}

What we do here is look at the inode that we’re initially given, which remember the root is number 1. We first read the given inode–the given inode should be a directory’s inode since we don’t call cache_at on regular files. Recall that each one of these inodes has blocks filled with the DirEntry structure (64 bytes).

If we find a directory, we recursively call cache_at with the new inode and new path. That will again search through all of the directory entries, and if there are any more directories, it will yet again recursively look through all of them. Otherwise, if we find a file, we just store the path, and we don’t recurse.

Pay no mind to me trying to figure out how to make Rust consider character arrays (u8 arrays more accurately) as strings. So, instead, I had to make a string and go character-by-character pushing each character from the array onto the string.

Using The Cache

Now that we’ve cached the inodes, it’s time to make it do something. Luckily, since BTreeMap is built-in to Rust, we can just use its .get() member function. If this function finds the key, it will return a Some(Inode). Otherwise, it will return None. We can use this to see if the file exists or not. So, let’s add some code to our open() filesystem function.

pub fn open(bdev: usize, path: &str) -> Result<Inode, FsError> {
   if let Some(cache) = unsafe { MFS_INODE_CACHE[bdev - 1].take() }
   {
      let ret;
      if let Some(inode) = cache.get(path) {
         ret = Ok(*inode);
      }
      else {
         ret = Err(FsError::FileNotFound);
      }
      unsafe {
         MFS_INODE_CACHE[bdev - 1].replace(cache);
      }
      ret
   }
   else {
      Err(FsError::FileNotFound)
   }
}

All we do here is grab exclusive access to the cache, look for the provided path, and then give back access to the cache. If we found the Inode, we copy it and return it wrapped in an Ok(). Otherwise, we wrap the cause of the error in an Err(). Notice I returned FileNotFound if we couldn’t get access to the cache. Perhaps this makes FNF ambiguous.

Now, to initialize our cache, we run init() in a process context. Then, we can grab the inode by using open(). Finally, if we want to read the data in it, we can use read(). Notice that the read() fs function has changed to accept an Inode reference. This helps keep things a little bit cleaner. This also gives us a flow: we cache inodes, we open a file to get its Inode structure, we read based on this Inode structure. For now, close doesn’t do anything because there is nothing really to close. For reads, we don’t care. For writes, the close would do something, such as make sure all writes have completed.

---

Video