vfs

vfs is a library that implements a Virtual File System in Rust from scratch, with all the methods necessary for using it. This vfs doesn't comply with any regulations, it is only my take on the subject. It is fully functional.

Table of Contents

• Features
• File System Manipulation
• Files Manipulation
• Directories Manipulation
• Implementation Details
  • Memory Handling
  • Structure Handling
  • Crash Handling

---

Features

• Incorruptible regardless of crashes
• Thorough tests for ensuring correctness and incorruptibleness
• Directory manipulation, including a hierarchy, iterating over the contents, deletion, creation
• File manipulation, including modifying the file (large files supported), seek, creation, deletion, truncate, writing, reading
• Metadata: name, type, address, creation date, last modified date
• Importing and exporting files to your OS
• Creating multiple vfs in the same scope, with saving/open/integrity check feature

File System Manipulation

VirtualFileSystem class encapsulates every method necessary for the vfs to work properly.

Create a new instance

pub fn new(filename : &str)  -> Self

It creates a file with the name filename, that will contain all the data of the vfs and returns a VirtualFileSystem instance.

Open a vfs file

pub fn open(filename : &str) -> Self 

Opens an already existing file system. It also checks if it is valid. If it is, it will return a VirtualFileSystem instance.

Integrity check

pub fn integrity_check(&mut self)

Performs an integrity check of the file system. The check is thorough, validating even file data.

Create a file

pub fn make_file(&mut self , path : &str)  -> Result < FileUsable , Box < dyn Error > > 

Create a file in the filesystem, on the specified path. If it couldn't be created, a specific error will be returned instead. Otherwise a FileUsable instance will be returned.

Example:

let mut file = vfs.make_file("/root/bin/file.txt")?;

Remove a file

pub fn rm_file(&mut self , path : &str)  -> Result < () , Box < dyn Error > > 

Deletes the file specified by path from the filesystem. If the file couldn't be deleted, a specific error will be returned instead.

Example:

vfs.rm_file("/root/bin/file.txt")?;

Print contents of a file

pub fn cat(&mut self , path : &str)  -> Result < () , Box < dyn Error > > 

Prints in the terminal the contents of the file. If an error occurs, the error will be returned instead.

Example:

vfs.cat("/root/bin/file.txt")?;

Open a file

pub fn open_file(&mut self , path : &str)  -> Result < FileUsable , Box < dyn Error > > 

Opens a file, for future modifications. If something goes wrong, an error will be returned. Otherwise a FileUsable instance will be returned.

Example:

let mut file = vfs.open_file("/root/bin/file.txt")?;

Create a directory

pub fn make_dir(&mut self , path : &str)  -> Result < DirEntry , Box < dyn Error > > 

Creates a directory in the filesystem, specified by path. If an error occurs, the error will be returned. Otherwise, a DirEntry instance will be returned.

Example:

let mut dir = vfs.make_dir("/root/bin/user")?;

Remove a directory

pub fn rm_dir(&mut self , path : &str)  -> Result < () , Box < dyn Error > >

Deletes the directory specified by path. If an error occurs, the error will be returned. The directory must be empty.

Example:

vfs.rm_dir("/root/bin/user")?;

List a directory

pub fn ls(&mut self , path : &str)  -> Result < () , Box < dyn Error > >

Lists the contents of the directory specified by path, similar to how a simple ls in UNIX OS works. If an error occurs, the error will be returned.

Example:

vfs.ls("/root/bin")?;

Open a directory

pub fn open_dir(&mut self , path : &str)  -> Result < DirEntry , Box < dyn Error > > 

Opens a directory for future modifications. If an error occurs, the error will be returned. Otherwise a DirEntry instance will be returned.

Example:

let mut dir = vfs.make_dir("/root/bin/user")?;

Reading a directory

pub fn read_dir(&mut self , path : &str) -> DirIter 

Reads a directory, offering a method for getting the instances that represent the entries individually. If an error occurs, the execution will stop. Otherwise a DirIter instance will be returned. DirIter is an iterator for a directory, that will return an Entry enum, that encapsulates the entries.

Example:

for entry in vfs.read_dir("/root")
{
    data.clear();

    if let Entry::File(mut file) = entry 
    {
        file.read_to_string(&mut data).expect("");
        print!("{}" , data);
    }
    else if let Entry::Dir(mut dir) = entry 
    {
        print!("{}" , dir.pwd()?);
    }
}

Files Manipulation

FileUsable class is responsible for handling an instance of a file. It contains: a cursor for seeking purposes, filename and file size. The cursor is mantained after each operation accordingly, simulating the behaviour of the UNIX OS style. Be careful of data synchronization of 2 instances that refer to the same file. It could lead to undefined behaviuour. It is not recommended.

• Append data

  pub fn append(&mut self , data : &[u8]) -> Result < u64 , Box < dyn Error > > 

  Appends bytes of data at the end of the file. If an error occurs, the error is returned. Otherwise, the new cursor position is returned.

  Example:

  file.append(b"file bytes")?;

• Import from OS

  pub fn load_from(&mut self , filename : &str) -> Result < () , Box < dyn Error > > 

  Imports a file from the OS into the filesystem and rewrites the current file data, matching the file from the OS. If an error occurs, the error is returned.

  Example:

  file.load_from("/home/users/user/file.txt")?;

• Export from OS

  pub fn export_to(&mut self , filename : &str) -> Result < () , Box < dyn Error > >

  Saves the file to the OS. If an error occurs, the error is returned.

  Example:

  file.export_to("file_exported.txt")?; 

• Print data

  pub fn print(&mut self) -> Result < () , Box < dyn Error > >

  Prints into terminal the contents of the file. If an error occurs, the error is returned.

  Example:

  file.print()?; 

• Transform content in String

  pub fn read_to_string(&mut self , data : &mut String) -> Result < () , Box < dyn Error > >

  Writes the contents of the file into data String. If an error occurs, the error is returned.

  Example:

  let mut data = String::new();
  file.read_to_string(&mut data)?;
  print!("{data}");

• Truncate

  pub fn truncate(&mut self , size : u64) -> Result < () , Box < dyn Error > > 

  Truncates the file to the specified size. If the size is bigger than the file's size, than the remaining will be filed with 0s. Otherwise the file will be cut till the specified size is met. If an error occurs, the error will be returned instead. The cursor will be moved poiting to the last byte.

  Example:

  file.truncate(3)?; // -> truncates the file to 3 bytes ; and the cursor points to the 4-th byte.

• Seek

  pub fn seek(&mut self , pos : u64) -> Result < () , Box < dyn Error > > 

  Moves the cursor to the specified position. The position has to be in the interval [0 ; self.size], otherwise an error will rise. If an error occurs, the error will be returned.

  Example:

  file.seek(4)?; // -> moves the cursor to the 5th byte, preparing for the modifications

• Read

  pub fn read(&mut self , bytes : &mut [u8]) -> Result < () , Box < dyn Error > > 

  Reads |bytes| bytes sequentially from the current cursor position (and moves the cursor) and places the data read into the bytes array. If the bytes size exceeds the length of the remaining bytes from the current cursor position till the end of the file, it won't fill the remaining bytes.

  Example:

  let mut arr : [u8 ; 10] = [u8 ; 0];
  file.seek(3)?;
  file.read(&mut arr)?; // -> reads 10 characters from the 4th character  ; the cursor is moved to the 14th character

• Write

  pub fn write(&mut self , bytes : &[u8]) -> Result < () , Box < dyn Error > > 

  Writes all the bytes in bytes array, from the current cursor position. If the cursor exceeds the filesize, then the file gets expanded. If an error occurs, the error will be returned.

  Example:

  file.seek(3)?;
  let arr : [u8 ; 5] = [97 , 98 , 99 , 100 , 101]; // -> abcde
  file.write(&arr)?; // -> writes abcd on the 4th, 5th , 6th , 7th , 8th bytes from the file ; cursor gets moved to the 9th byte

• Get path of the file

  pub fn pwd(&mut self) -> Result < String , Box < dyn Error > > 

  Returns a string with the real path in the vfs. If an error occurs, the error is returned instead.

  Example:

  let mut file = vfs.make_file("/root/file.txt")?;
  let path = file.pwd()?;
  print!("{path}"); // -> prints /root/file.txt

Directories Manipulation

• List contents of the directory

  pub fn ls(&mut self) -> DirIter

  Returns an iterator for iteraing the directory. If an error occurs, the execution will be stopped.

  Example:

  let mut dir = vfs.open_dir("/root")?;
  
  for entry in dir.ls()?
  {
      data.clear();
  
      if let Entry::File(mut file) = entry 
      {
          file.read_to_string(&mut data).expect("");
          print!("{}" , data);
      }
      else if let Entry::Dir(mut dir) = entry 
      {
          print!("{}" , dir.pwd()?);
      }
  }

• Recursive listing of the directory

  pub fn ls_all(&mut self) -> Result < () , Box < dyn Error > > 

  Lists in the terminal the contents of the directory recursively, like ls -r in UNIX OS

  Example:

  dir.ls_all()?;

• Get path of the directory

  pub fn pwd(&mut self) -> Result < String , Box < dyn Error > >

  Returns a string with the real path in the vfs. If an error occurs, the error is returned instead.

  Example:

  let mut dir = vfs.make_dir("/root/dir")?;
  let path = file.pwd()?;
  print!("{path}"); // -> prints /root/dir

Getting metadata of files/directories can be achieved by printing the instance. The metadata supported are: name, type, address, creation date, last modified date. Example:

print!("{file}"); 

Check out main.rs and tests.rs for a thorough example of using the library.

---

Implementation Details

There are 2 components: memory handling and structures handling. The hardest one of course is the former. Besides these 2 components, the vfs has to solve the corruption problem, so that in case of a crash a small portion gets lost or nothing gets lost. Also every atomic operation should have logarithmic complexity so that everything runs smoothly and efficient.

Memory Handling

Note: this implementation considers writing 8 byte integers as atomic.

Every byte in memory file is numbered from 0 and it is a 64 bit address.

The vfs uses pagination so it avoids external fragmentation. The size of a page can be changed, but it should be a power of two for better optimizations. The structure of a page is the following: PAGE_TYPE (4 bytes) , USED_COUNT (4 bytes) , PARENT (8 bytes) , DATA (remaining bytes).

The memory has to do the following: dispatch a new instance to be written to, delete an instance from memory.

There are 5 types of structures: directory structure, trie structure, file structure, pointer structure and data structure. The only difference between these ones is that each has a different use, so to avoid internal fragmentation and instant access, each type gets his own page. So the structures are placed sequentially in each page, guaranteeing searching for an entry in O(1) access (because the size of a structure is finite and fixed for entire page, to find the kth instance, the formula is page_pointer + DATA_OFFSET + (k - 1) * structure_size)

There are 5 different types of pages:

• Type 1: In this page the only instances present are of directory type

  Directory instances contains data for achieving the hierarchy and all the necessary things for names and other new entries.

  It contains:

  • parent_directory -> pointer to the start structure of the parent directory
  • root_entry -> pointer to the start structure of the trie
  • creation_date -> 8 byte integer that represents the number of seconds from 1970 when the directory was created
  • last_modified_date -> 8 byte integer that preresents the number of seconds from 1970 when the directory was modified the last time
  • name -> pointer to the trie node that points to this structure

• Type 2: In this page the only instances present are of trie type

  • chl -> array of pointers, where ith pointer represents the choice of appending on the path ith ascii character.
  • file_ptr -> pointer to a file/directory structure
  • sum -> 4 byte integer that sums up all instances in the current subtree
  • parent -> pointer to the parent trie node. If you are already in the root, the parent will point to the directory that you belong to.
  • ch -> 1 byte integer, representing the character on the edge between current node and the parent (the last choice so to speak)

• Type 3: In this page the only instances present are of file type

  • parent_directory -> pointer to the start structure of the parent directory that contains the file
  • file_data -> pointer to the file data
  • creation_date -> 8 byte integer that represents the number of seconds from 1970 when the file was created
  • last_modified_date -> 8 byte integer that preresents the number of seconds from 1970 when the file was modified the last time
  • name -> pointer to the trie node that points to this structure

• Type 4: In this page the only instances present are of pointer type

  Every instance is a 8 byte integer, representing a pointer to somewhere in the memory (it is 0 if it is not in use)

• Type 5: In this page only file data is present Page is filled with data of the file.

As you can see, directories and files are nearly the same, the only difference being the semantics. It is cleaner having 2 separate structures in case of expansion. It is very easy to escalate anything and implement new features.

The usage of this structure will be stated in the usage section

The most important part of this memory management is allocating new entries and deleting them (like new/malloc and delete from C/C++). Let's focus on this for now:

To implement a fast and reliable dispatch of memory, you need to care of 2 things: searching and deletion. My solution runs in O(log_PAGE_SIZE(Number of Entries))

For this to take place, I have implemented the following mechanism: multi-level pointer tree structure, with leaves on the same level. The leaves are pages of data that are non-pointer type. The in-nodes are pages of pointers type. Now, knowing this, we have to do this dynamically, so to add new entries however the usage. This is achieved by dynamically extending the tree: the old root of the tree, becomes a child of a new root and a sibling of old root is created.

Searching for a new sequence of bytes that can hold a new structure instance:

We consider and mantain the following property: used_count field in a pointer type page counts the number of subtrees that are fully completed. Keep in mind that means a partially completed subtree or a null pointer is counted the same (nothing). This invariant is simple to implement and mantain, being a simple data structure. So searching now is a recursive process: iterate over all pointers in the page. If the pointer is null, then you complete the tree by appending an empty tree and try again the process. If you encounter a non-null pointer, you verify if the page that points to is not full. If it is not then you retry the process from that page, otherwise you continue the iteration. Complexity: O(log_PAGE_SIZE(Number of Entries)) (simple traversal in the tree from current node to the root)

Deletion:

You clear the corresponding bytes that makes up the structure instance and decrement the used_count of the corresponding page, updating the pointer type pages on the path from current page to the root. Complexity: O(log_PAGE_SIZE(Number of Entries)) (simple traversal in the tree from current node to the root)

As you might guess, for a 2MB page size, you will encounter maximum 3 levels before you run out of physical memory. So the complexity is approximately 6MB of data processed. Pretty good, regardless of the size invariant of the structure.

For future reference, this is structure handling mechanism. This is the root of the vfs. (*)

Now, knowing this, the first page of the vfs contains: (the first fields are the same as any other page and the page type of this page is pointer type)

• directory_root_pointer -> pointer to the root of the tree concerning directory instances (on leaves) (see *)
• trie_root_pointer -> pointer to the root of the tree concerning trie instances (on leaves) (see *)
• fileentry_root_pointer -> pointer to the root of the tree concerning file instances (on leaves) (see *)
• data_root_pointer -> pointer to the root of the tree concerning file data pages (on leaves) (see *)
• root_directory_pointer -> pointer to the root directory instance
• virtual_page_size -> 8 byte integer representing the size of a virtual page in bytes
• swap1_pointer -> (see crash handling section)
• swap2_pointer -> (see crash handling section)
• last_address_pointer -> (see crash handling section)
• operation_pointer -> (see crash handling section)

Structure Handling

Now, having memory established and we have structure handling mechanism in place, we can actually use it and code the actual vfs and make it work with some simple algorithms.

The directory itself is just a directory instance. The entries in the directory are present as pointers in end nodes in a trie. The path from the root to the end-node comprises the name of the entry. So the root_entry from a directory instance is the root of the trie concerning that directory. Traversing this trie will get you all the entries (file_ptr field in a trie node gets you to the instance itself if it is not null). The name field in a file/directory structure is a pointer to the trie end-node that points to the file/directory. So to reconstitute the name, you have to traverse the trie nodes till the root, collect all the characters on the edges and then reverse what you get.

Visual representation

Add an entry in a directory: parse the name of the entry and the trie simultaneously. If there is no edge with the current character on it, you allocate a new trie node instance, with the character on the edge and go on it. At the end, you update the file_ptr with the corresponding pointer. You will also update the sum variable accordingly.

Complexity: O(|name| * T) , T - memory access constant time

Deletion of an entry in a directory: parse the name of the entry and the trie simultaneously. Deleting now means: 1. decreasing the sum field 2. if the sum is 0 you should delete the node (2. is not implemented unfortunately, due to some complications and not having time)

Complexity: O(|name| * T), T - memory access constant time

File instances contain a pointer (file_data_ptr) that leads to a structure handling mechanism. Seeking and truncating are in fact, searching for the kth byte in this mechanism. Keep in mind that the leaves are on the same level in the mechanism and data is placed sequentially in the leaves. This implies that all pointers of a page have the same number of data cells in the subtree. So now searching for the kth byte is similar to finding the kth entry in a AVL tree: traverse the current page of pointers and if the data cells in the subtree are still less than kth byte, you subtract the number of data cells in the substree and move on to the next pointer. Otherwise, you go deeper in the tree. Repeat the process till you find the leaf (being a data type page) and your kth byte is the kth byte in this page (excluding the header of the page).

Complexity: O(log_PAGE_SIZE(File size))

This complexities work, because pagination is in fact multi-layer SQRT decomposition. So you answer a query in a level to advance to the next one in O(B), where B = Bucket size (page size).

Pretty easy right?

Crash Handling Section

This is the most interesting one and I planned it ahead. There are 3 types of crash situations:

1. creating a new instance in the memory -> last_address_pointer
2. updating an existing instance in the memory -> swap1_pointer , swap2_pointer
3. a system operation (what we've talked in the previous section) -> operation_pointer

when a crash happens, the next time you run the program you will use open method. The first thing that will happen, it will repair the damage by reversing things using the above mentioned pointers that are on the first page of the system.

Case 1

creating a new instance means searching for a place in memory for the instance and then writing data in it. The first operation is read-only, so the latter one is the only problem. After finding the place in memory, you write the pointer in the last_address_pointer field in the first page. And only then you start writing data. After finishing writing, you will write null pointer instead. The take here is that if a crash happens upon creating an instance, you didn't have time to use it, so it is safe to delete it as if it didn't happen in the first place. This is what I do, I will erase the entry from the page and update used_count variable accordingly on the path to the root.

Case 2

This is a bit more complicated then Case 1. To make it atomic, you use the fact that writing a pointer is atomic. So we have to achieve creating a new instance with the desired updated fields and after it make a single pointer write to switch the old instance with the new one. The first thing you do, you search for a new place in memory. After that you load in swap1_pointer the current pointer of the structre and in swap2_pointer you load the found pointer. Write the updated structure and then write null pointers in swap2 and swap1 (in this order). In case a crash happens, the next run the system will be opened and then the repair will take place. If both swap1 and swap2 are non-null, it means that the moving process wasn't completed so you redo all the links using the structure pointed by swap1. Update the parent through the parent pointer, etc... . See repair_last_operation method in vfs.rs.

If only swap1 is present, then there are 2 cases: 1. it finished moving, but the swap1 pointer wasn't updated in time because of the crash 2. swap2 wasn't even written in memory (because of the crash) -> conclusion: you do nothing

To make sure that everything is fine, you run a recount on the pages that pointed by the pointers.

Case 3

a system operation means creating a new entry. As we have discussed, creating an entry requires 3 phases:

1. Creating the entry (file or directory instance)
2. If it is a file (appending data mechanism) ; if it is directory (appending trie mechanism for new entries)
3. Inserting it in the directory

If phase 1 was completed, then you load the pointer into operation_pointer. Now if a crash happens, you can detect in which phase the system was before the crash. If the pointer is null, that means nothing needs to be done, everything is clean and good. Otherwise, you look for phase 2: if root_entry / file_data pointers are null this means that phase 2 wasn't completed. if phase 2 wasn't completed:

1. file: this means that the data handling mechanism was not appended. After creating the first page for data, you write the pointer to the file structure and update the parent field of the page (in this order). This means that the parent of the page was not updated. This is not a memory leak, because memory recycler of pages comes in. When opening a system, you first recycle the pages that have a null parent. This is done linearly in O(Nr. of virtual pages) (there are maximum 10^7 pages, till you run out of physical memory, so it is fine). After this, you delete the structure.
2. directory: Being in this phase means that the trie wasn't created. Keep in mind that this is an empty trie => a single trie node. Even if it was created the pointer wasn't written in the directory structure. So nothing happens, because it will fall under the other crash cases. After that you delete the structure.

Even if phase 2 was completed, you will still deallocate root_entry/file_data, because you don't know anymore what to do with this file/directory and in the end you will delete the structure.

Checking for phase 3: name pointer in both structures. If it is null, it means that it wasn't inserted anywhere If it is null you don't have to do anything and just delete the structure. Otherwise you update the trie accordingly by deleting the instance from the name trie node that points to. (Simple deletion as we discussed above).

In the end you delete the structure.

This is it. If you have any questions you can DM me.