Merge pull request #17 from SuperconductZB/guangzheliu/someotherfix

FINAL FIX

.gitmodules

@@ -0,0 +1,3 @@
+[submodule "googletest"]
+	path = googletest
+	url = https://github.com/google/googletest.git

CMakeLists.txt

@@ -6,6 +6,7 @@ set(CMAKE_CXX_STANDARD 14)
 include_directories(
   # fischl include files
   ${CMAKE_CURRENT_SOURCE_DIR}/include
+  # ${CMAKE_CURRENT_SOURCE_DIR}/googletest/googletest/include
 )
 
 add_executable(fischl
@@ -15,12 +16,25 @@ add_executable(fischl
   lib/rawdisk.cpp
   lib/fs/datablock_manager.cpp
   lib/fs/fs_data_types.cpp
-  lib/fs/fs_resize.cpp
-  lib/fs/fs_read_write.cpp
+  lib/fs/fs_file_io.cpp
   lib/fs/fs.cpp
   lib/fs/inode_manager.cpp
+  lib/files.cpp
+  lib/direntry.cpp
 
 )
 
 enable_testing()
 add_subdirectory(test)
+add_subdirectory(googletest)
+
+# Add the -Wall flag
+target_compile_options(fischl PRIVATE -Wall)
+
+# Use pkg-config to get flags for fuse3
+find_package(PkgConfig REQUIRED)
+pkg_search_module(FUSE3 REQUIRED fuse3)
+
+# Add the flags from pkg-config for fuse3
+target_include_directories(fischl PRIVATE ${FUSE3_INCLUDE_DIRS})
+target_link_libraries(fischl PRIVATE ${FUSE3_LIBRARIES})

README.md

@@ -19,6 +19,29 @@ cmake ..
 make # cmake --build . is same
 ```
 
+## mount and test
+normal usage:
+```bash
+./fischl diskpath n -s mountpoint
+```
+diskpath must be provided following ./fischl
+l/n must be provided following diskpath indicating whether to load the exisiting file system or create a new one.
+for loading:
+```bash
+./fischl diskpath l -s mountpoint
+```
+-s is also required because our fs doesn't support multi-threading.
+
+if the diskpath need to be accessed by root:
+```bash
+sudo ./fischl diskpath n -o allow_other -s mountpoint
+```
+
+for debugging:
+```bash
+sudo ./fischl diskpath n -o allow_other -d -s mountpoint
+```
+
 ## run test
 ### add your own test file on test/CMakeList.txt
 ```

googletest

@@ -0,0 +1 @@
+Subproject commit b10fad38c4026a29ea6561ab15fc4818170d1c10

include/direntry.h

@@ -0,0 +1,66 @@
+typedef struct fileNode {
+    char *name = NULL;
+    int inode_number;
+    int permissions;
+    char *Symbolink;
+    struct treeNode *subdirectory;
+    struct fileNode *next;
+} FileNode;
+
+typedef struct {
+    int size;
+    FileNode **table;
+} HashTable;
+
+typedef struct treeNode {
+    char *dirName;
+    HashTable *contents;
+    struct treeNode *parent;
+    FileNode *self_info; //self fileNode infromation
+} TreeNode;
+
+
+typedef struct RenameInfo {
+    FileNode *oldFileNode;       // The file node being renamed.
+    FileNode *oldParentNode;     // The parent directory of the file node being renamed.
+    FileNode *newParentNode;     // The target parent directory where the file node will be moved.
+    char *newName;               // The new name of the file node after the rename.
+    FileNode *newFileNode;       // The new file node, if one already exists at the target location.
+    bool exchangeExist;          // Flag to indicate if the rename should replace an existing file node.
+} RenameInfo;
+
+/*for root*/
+TreeNode *fischl_init_entry(int new_inode_number, const char *fileName, INode_Data *new_inode);
+/*the to be added file in add_entry should be parent-child relationship with treenode, otherwise will wrong */
+/*see Add_FindFiletest in dir_API.cpp*/
+FileNode* fischl_add_entry_for_cache(TreeNode *parent, int new_inode_number, const char *fileName, INode_Data *new_inode);
+int fischl_add_entry(TreeNode *parent, int new_inode_number, const char *fileName, INode_Data *new_inode);
+int fischl_rm_entry(TreeNode *parent, const char *fileName);
+/*if want to use dir mode use the subdirectory treeNode pointer */
+//e.g. FileNode *Dirnode = fischl_find_entry(); can see file inside with Dirnode->subdirectory
+//e.g. go to the current Dirnode parent directory, use TreeNode *get_Dir_parent = Dirnode->subdirectory->parent;
+FileNode *fischl_find_entry(Fs *fs, TreeNode *root, const char *path);
+
+void freeTree(TreeNode *node);
+/*for debug use*/
+TreeNode *createDirectory(const char *dirName, TreeNode *parent, int hashSize);
+TreeNode *find_parentPath(TreeNode *root, const char *path);
+
+struct DirectoryEntry {
+    u_int64_t inode_number;
+    char file_name[256];
+    void serialize(char* buffer) {
+        u_int64_t t = inode_number;
+        for (int j = 0; j < 8; j++){
+            buffer[j] = t & (((u_int64_t)1<<(8))-1);
+            t >>= 8;
+        }
+        strcpy(buffer+8, file_name);
+    }
+    void deserialize(char* buffer) {
+        inode_number = 0;
+        for (int j = 0; j < 8; j++)
+            inode_number = inode_number | (((u_int64_t)(unsigned char)buffer[j])<<(8*j));
+        strcpy(file_name, buffer+8);
+    }
+};

include/files.h

@@ -0,0 +1,51 @@
+#include <sys/types.h>
+#include <fs.hpp>
+#include <fuse.h>
+#include "direntry.h"
+
+class FilesOperation {
+    RawDisk& disk;
+    Fs *fs;
+    void create_dot_dotdot(INode_Data*, u_int64_t);
+
+public:   
+    TreeNode *root_node;
+    FilesOperation(RawDisk&, Fs*);
+    //int read_datablock(const INode_Data& inode, u_int64_t index, char* buffer);
+    //int write_datablock(INode_Data& inode, u_int64_t index, char* buffer);
+    void initialize_rootinode();
+    void initialize(bool load);
+    void printbuffer(const char*,int);
+    void printDirectory(u_int64_t);
+    bool permission_check(int, INode_Data*);
+    bool permission_check_by_inode_num(int, u_int64_t);
+    INode_Data* create_new_inode(u_int64_t parent_inode_number, const char* name, mode_t mode);
+    int insert_inode_to(u_int64_t parent_inode_number, const char* name, INode_Data *new_inode, bool check_replace);
+    void unlink_inode(u_int64_t inode_number);
+    u_int64_t disk_namei(const char* path);
+    u_int64_t namei(const char* path);
+    int fischl_mkdir(const char*, mode_t);
+    int fischl_mknod(const char*, mode_t, dev_t);//for special file
+    int fischl_access(const char* path, int mask);
+    int fischl_create(const char *, mode_t, struct fuse_file_info *);//for regular file
+    int fischl_getattr(const char *path, struct stat *stbuf, struct fuse_file_info *fi);
+    int fischl_readdir(const char *, void *, fuse_fill_dir_t, off_t, struct fuse_file_info *, enum fuse_readdir_flags);
+    int fischl_releasedir(const char* path, struct fuse_file_info *fi);
+    int fischl_unlink (const char *);
+    int fischl_opendir(const char* path, struct fuse_file_info* fi);
+    int fischl_rmdir(const char *);
+    int fischl_readlink(const char* path, char* buf, size_t size);
+    int fischl_symlink(const char* from, const char* to);
+    int fischl_link(const char* from, const char* to);
+    int fischl_rename(const char *path, const char *, unsigned int flags);
+    int fischl_truncate(const char *path, off_t, struct fuse_file_info *fi);
+    int fischl_chmod(const char *path, mode_t, struct fuse_file_info *fi);
+    int fischl_chown(const char *path, uid_t uid, gid_t gid, struct fuse_file_info *fi);
+    int fischl_open (const char *, struct fuse_file_info *);//open file
+    int fischl_release (const char *, struct fuse_file_info *);//close file
+    int fischl_write(const char *, const char *, size_t, off_t, struct fuse_file_info *);
+    int fischl_read(const char *, char *, size_t, off_t, struct fuse_file_info *);
+    int fischl_utimens(const char *path, const struct timespec tv[2], struct fuse_file_info *fi);
+    int fischl_statfs(const char* path, struct statvfs* stbuf);
+    FileNode *fischl_load_entry(TreeNode *root, const char *path);
+};

include/fischl.h

@@ -1,7 +1,3 @@
-class fischl{
 
-    // declare
-    public:
-         int init();
 
-};
+int fischl(int argc, char *argv[]);

include/fs.hpp

@@ -15,20 +15,12 @@ public:
   Fs(RawDisk *disk);
   ~Fs();
 
-  int allocate_datablock(INode_Data *inode_data, u_int64_t *datablock_num);
-  int deallocate_datablock(INode_Data *inode_data, u_int64_t *datablock_num);
-
   ssize_t read(INode_Data *inode_data, char buf[], size_t count, size_t offset);
-  ssize_t write(INode_Data *inode_data, char buf[], size_t count,
+  ssize_t write(INode_Data *inode_data, const char buf[], size_t count,
                 size_t offset);
-
-  int sweep_inode_datablocks(INode_Data *inode_data,
-                             u_int64_t start_block_index, bool allocate,
-                             DatablockOperation *op);
-
-  int sweep_datablocks(u_int64_t *block_num, int indirect_num,
-                       u_int64_t start_block_index, bool allocate,
-                       DatablockOperation *op);
+  int truncate(INode_Data *inode_data, off_t length);
+  ssize_t lseek_next_data(INode_Data *inode_data, size_t offset);
+  ssize_t lseek_next_hole(INode_Data *inode_data, size_t offset);
 
   int format();
 
@@ -44,8 +36,13 @@ public:
   int save_free_list_head(u_int64_t new_free_list_head);
   int save_inode_list_head(u_int64_t new_inode_list_head);
 
-  int allocate_indirect(u_int64_t *storage, int n, u_int64_t *datablock_num);
-  int deallocate_indirect(u_int64_t *storage, int n, u_int64_t *datablock_num);
+  int sweep_inode_datablocks(INode_Data *inode_data,
+                             u_int64_t start_block_index, bool allocate,
+                             DatablockOperation *op);
+
+  int sweep_datablocks(u_int64_t *block_num, int indirect_num,
+                       u_int64_t start_block_index, bool allocate,
+                       DatablockOperation *op);
 };
 
 #endif

include/fs/fs_data_types.hpp

@@ -25,12 +25,14 @@ public:
   u_int64_t inode_num;
 
 #define NUMBER_OF_METADATA_BYTES                                               \
-  (4 * sizeof(u_int64_t) + (2 * sizeof(u_int32_t)))
+  (6 * sizeof(u_int64_t) + (2 * sizeof(u_int32_t)))
   struct INode_MetaData {
     u_int64_t uid;
     u_int64_t gid;
     u_int64_t permissions;
     u_int64_t size; // not yet implemented
+    u_int64_t access_time;
+    u_int64_t modification_time;
     u_int32_t reference_count;
     u_int32_t flags;
   } metadata;
@@ -39,11 +41,15 @@ public:
 
 #define NUMBER_OF_DIRECT_BLOCKS                                                \
   (((INODE_SIZE - NUMBER_OF_METADATA_BYTES) / sizeof(u_int64_t)) - 3)
+#define FILE_SIZE_MAX                                                          \
+  (IO_BLOCK_SIZE * (NUMBER_OF_DIRECT_BLOCKS + INDIRECT_BLOCKS +                \
+                    (INDIRECT_BLOCKS * INDIRECT_BLOCKS) +                      \
+                    (INDIRECT_BLOCKS * INDIRECT_BLOCKS * INDIRECT_BLOCKS)))
 
   u_int64_t single_indirect_block, double_indirect_block, triple_indirect_block;
   u_int64_t direct_blocks[NUMBER_OF_DIRECT_BLOCKS];
 
-  INode_Data(u_int64_t inode_num = 0xFFFFFFFFFFFFFFFF);
+  INode_Data(u_int64_t inode_num = (u_int64_t)(0xFFFFFFFFFFFFFFFF));
   void serialize(char buf[]);
   void deserialize(char buf[]);
 };

include/fs_constants.hpp

@@ -2,6 +2,7 @@
 #define FS_CONSTANTS_HPP
 
 #include <algorithm>
+#include <errno.h>
 #include <fcntl.h>
 #include <inttypes.h>
 #include <linux/fs.h>
@@ -11,13 +12,15 @@
 #include <sys/ioctl.h>
 #include <unistd.h>
 
-#define IO_BLOCK_SIZE 4096
 
-#define NUM_INODE_BLOCKS 1023
-#define NUM_BLOCKS 2048
+#define IO_BLOCK_SIZE 4096
+#define INDIRECT_BLOCKS 512
+
+#define NUM_INODE_BLOCKS 262143
 
 #define INODE_SIZE 512
 
-#define DATABLOCKS_PER_BITMAP_BLOCK 255
+// TODO: explore the optimal value for this
+#define DATABLOCKS_PER_BITMAP_BLOCK 2047
 
 #endif

lib/direntry.cpp

@@ -0,0 +1,278 @@
+#include <stdio.h>
+#include <string>
+#include <assert.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include "fs.hpp"
+#include "direntry.h"
+/*********************************Hash operation********************************************
+
+********************************************************************************************/
+// Hash operation
+unsigned int hash(HashTable *h, char *key) {
+    unsigned int hashval = 0;
+    for (; *key != '\0'; key++) hashval = *key + (hashval << 5) - hashval;
+    return hashval % h->size;
+}
+
+HashTable *createHashTable(int size) {
+    HashTable *newTable = (HashTable *)malloc(sizeof(HashTable));
+    newTable->size = size;
+    newTable->table = (FileNode **)malloc(sizeof(FileNode *) * size);
+    for (int i = 0; i < size; i++) newTable->table[i] = NULL;
+    return newTable;
+}
+
+FileNode *insertHash(HashTable *h, char *key, TreeNode *subdirectory) {
+    unsigned int hashval = hash(h, key);
+    FileNode *newNode = (FileNode *)malloc(sizeof(FileNode));
+    newNode->name = strdup(key);
+    newNode->subdirectory = subdirectory;
+    newNode->next = h->table[hashval];
+    h->table[hashval] = newNode;
+    return newNode;
+}
+
+FileNode *lookupHash(HashTable *h, char *key) {
+    unsigned int hashval = hash(h, key);
+    FileNode *node = h->table[hashval];
+    while (node != NULL) {
+        if (strcmp(node->name, key) == 0) return node;
+        node = node->next;
+    }
+    return NULL; // Not found
+}
+
+bool removeHash(HashTable *h, char *key) {
+    unsigned int hashval = hash(h, key);
+    FileNode *node = h->table[hashval];
+    if (node == NULL) return false;
+    if (strcmp(node->name, key) == 0) {
+        h->table[hashval] = node->next;
+        return true;
+    }
+    FileNode *prev = NULL;
+    bool foundit = false;
+    while (node != NULL) {
+        if (strcmp(node->name, key) == 0) break;
+        prev = node;
+        node = node->next;
+    }
+    if (node == NULL) {
+        return false;
+    } else {
+        prev->next = node->next;
+        return true;
+    }
+}
+
+TreeNode *createDirectory(const char *dirName, TreeNode *parent, int hashSize) {
+    TreeNode *newDir = (TreeNode *)malloc(sizeof(TreeNode));
+    newDir->dirName = strdup(dirName);
+    newDir->contents = createHashTable(hashSize);
+    newDir->parent = parent;
+    if (parent) {
+        newDir->self_info = insertHash(parent->contents, newDir->dirName, newDir);
+    }
+    return newDir;
+}
+
+TreeNode *find_parentPath(TreeNode *root, const char *path) {
+    char *pathCopy = strdup(path);
+    char *segment = strtok(pathCopy, "/");
+    TreeNode *current = root;
+    FileNode *file = NULL;
+
+    while (segment != NULL && current != NULL) {
+        file = lookupHash(current->contents, segment);
+        if (file != NULL && file->subdirectory == NULL) {
+            free(pathCopy); 
+            //printf("status current directory %s\n",current->dirName);
+            return current; //File found
+        }
+        current = file ? file->subdirectory : NULL;
+        segment = strtok(NULL, "/");
+    }
+
+    free(pathCopy);
+    return current; // NULL if not found
+}
+
+void freeHashTable(HashTable *table) {
+    if (table == NULL) return;
+
+    free(table->table);
+    free(table);
+}
+
+void freeTree(TreeNode *node) {
+    //printf("***********************FREE TREE %s**************************\n",node->dirName);
+    //printf("***********************FREE TREE **************************\n");
+    if (node == NULL) return;
+
+    if (node->contents != NULL) {
+        for (int i = 0; i < node->contents->size; ++i) {
+            FileNode *current = node->contents->table[i];
+            while (current != NULL) {
+                FileNode *temp = current;
+                current = current->next;
+
+                if (temp->subdirectory != NULL) {
+                    freeTree(temp->subdirectory);
+                }
+                // Free the FileNode if it's not a directory
+                // printf("free who %s\n",temp->name);
+                free(temp->name);
+                free(temp);
+            }
+        }
+        //printf("free %s's hash table\n",node->dirName);
+        freeHashTable(node->contents);
+        //node->contents = NULL;
+    }
+    //printf("free directory %s\n",node->dirName);
+    free(node->dirName);
+    node->dirName = NULL;
+    free(node);
+    node = NULL;
+    //printf("***********************END**************************\n");
+}
+
+/*********************************Direntry operation******************************************
+
+********************************************************************************************/
+//for fake root (mount point)
+TreeNode *fischl_init_entry(int new_inode_number, const char *fileName, INode_Data *new_inode) {
+    TreeNode *newDir = (TreeNode *)malloc(sizeof(TreeNode));
+    newDir->dirName = strdup(fileName);
+    newDir->contents = createHashTable(20);//hashSize define 20
+    newDir->parent = newDir;
+    FileNode *newFile = (FileNode *)malloc(sizeof(FileNode));
+    newFile->name = strdup(fileName);
+    newFile->inode_number = new_inode_number;
+    newFile->permissions = new_inode->metadata.permissions;
+    newFile->subdirectory = newDir;
+    newDir->self_info = newFile;
+    return newDir;
+}
+
+FileNode* fischl_add_entry_for_cache(TreeNode *parent, int new_inode_number, const char *fileName, INode_Data *new_inode){
+    char *Name = strdup(fileName);
+    TreeNode *newDir = NULL;
+    /*If directory, malloc TreeNode, and then create filenode that belongs to Parent hash table content*/
+    if ((new_inode->metadata.permissions & S_IFMT) == S_IFDIR) {
+        newDir = (TreeNode *)malloc(sizeof(TreeNode));
+        newDir->dirName = Name;
+        newDir->contents = createHashTable(20);//hasSize define 20
+        newDir->parent = parent;
+    }
+    FileNode *newFile = insertHash(parent->contents, Name, newDir); //newDir == NULL indicates it's a file
+    //assign INode *new_inode metadata to data member in FileNode structure
+    newFile->permissions = new_inode->metadata.permissions;
+    newFile->inode_number = new_inode_number;
+    //Diretory have its own file information, that is . here
+    if(newDir != NULL)
+        newDir->self_info = newFile;
+    return newFile;
+}
+
+int fischl_add_entry(TreeNode *parent, int new_inode_number, const char *fileName, INode_Data *new_inode){
+    char *Name = strdup(fileName);
+    TreeNode *newDir = NULL;
+    /*If directory, malloc TreeNode, and then create filenode that belongs to Parent hash table content*/
+    if ((new_inode->metadata.permissions & S_IFMT) == S_IFDIR) {
+        newDir = (TreeNode *)malloc(sizeof(TreeNode));
+        newDir->dirName = Name;
+        newDir->contents = createHashTable(20);//hasSize define 20
+        newDir->parent = parent;
+    }
+    FileNode *newFile = insertHash(parent->contents, Name, newDir); //newDir == NULL indicates it's a file
+    //assign INode *new_inode metadata to data member in FileNode structure
+    newFile->permissions = new_inode->metadata.permissions;
+    newFile->inode_number = new_inode_number;
+    //Diretory have its own file information, that is . here
+    if(newDir != NULL)
+        newDir->self_info = newFile;
+    //free(Name); cannot free name
+    return 0;
+}
+
+int fischl_rm_entry(TreeNode *parent, const char *fileName) {
+    char *fileName_dup = strdup(fileName);
+    if (parent->contents == NULL) return -1;
+    FileNode *file = NULL;
+    file = lookupHash(parent->contents, fileName_dup);
+    if (file == NULL) return -1;
+    if (file->subdirectory != NULL) freeTree(file->subdirectory);
+    removeHash(parent->contents, fileName_dup);
+    free(file->name);
+    free(file);
+    delete fileName_dup;
+}
+
+
+FileNode *fischl_find_entry(Fs *fs, TreeNode *root, const char *path){
+    //support . and .. function
+    char *pathCopy = strdup(path);
+    char *segment = strtok(pathCopy, "/");
+    TreeNode *current = root;
+    FileNode *file = NULL;
+
+    printf("FINDING %s %s %llu\n", path, segment, current->self_info->inode_number);
+
+    while (segment != NULL && current != NULL) {
+        if (strcmp(segment, "..") == 0) {
+            // Move up to the parent directory
+            current = current->parent;
+            if (current == NULL) {
+                // If there's no parent, we've reached the top of the tree, but root itself is same
+                file = NULL;
+                break;
+            } else {
+                file = current->self_info;
+            }
+        } else if (strcmp(segment, ".") == 0) {
+            // Stay in the current directory (no action needed)
+        } 
+        else{
+            file = lookupHash(current->contents, segment);
+            if (file == NULL) {
+                // find on disk whether this exists
+                INode_Data inode;
+                inode.inode_num = current->self_info->inode_number;
+                fs->inode_manager->load_inode(&inode);
+                char buffer[IO_BLOCK_SIZE] = {0};
+                for (u_int64_t idx=0; idx<inode.metadata.size/IO_BLOCK_SIZE; idx++) {
+                    fs->read(&inode, buffer, IO_BLOCK_SIZE, idx*IO_BLOCK_SIZE);
+                    DirectoryEntry ent;
+                    for(int i=0;i<=IO_BLOCK_SIZE-264;i+=264){
+                        ent.deserialize(buffer+i);
+                        //printf("WARNING:%d %llu %llu %s %s\n",__LINE__,inode.inode_num, ent.inode_number, ent.file_name, segment);
+                        if (ent.inode_number && strcmp(ent.file_name, segment)==0) {
+                            file = fischl_add_entry_for_cache(current, ent.inode_number, ent.file_name, &inode);
+                            //printf("DONE !! %llu\n", file->inode_number);
+                            break;
+                        }
+                    }
+                }
+            }
+            if (file != NULL && file->subdirectory == NULL) {
+                free(pathCopy);
+                printf("FOUND !! %llu\n", file->inode_number);
+                return file; //File found
+                //return current; return filenode
+            }
+            current = file ? file->subdirectory : NULL;
+        }
+        segment = strtok(NULL, "/");
+    }
+
+    free(pathCopy);
+
+    if (current != NULL && file == NULL) {
+        // If we've stopped at a directory and not a file, return the directory's self info
+        return current->self_info;
+    }
+
+    return file; // NULL if not found
+}

lib/fischl.cpp

@@ -1,8 +1,314 @@
-#include "fischl.h"
+#define FUSE_USE_VERSION 31
 
-#include <cstdio>
+#include <fuse.h>
+#include <stdio.h>
+#include <string>
+#include <errno.h>
+#include <fcntl.h>
+#include <stddef.h>
+#include <assert.h>
+#include "fs.hpp"
+#include "files.h"
 
-int fischl::init(){
-    printf("Hello Fischl!");
-    return 3;
+/*
+ * Command line options
+ *
+ * We can't set default values for the char* fields here because
+ * fuse_opt_parse would attempt to free() them when the user specifies
+ * different values on the command line.
+ */
+static struct options {
+    RawDisk *H; // Use FakeRawDisk here if memory sanitizer complains
+    Fs *fs;
+    FilesOperation *fsop;
+	int show_help;
+    bool load;
+} options;
+
+#define OPTION(t, p)                           \
+    { t, offsetof(struct options, p), 1 }
+static const struct fuse_opt option_spec[] = {
+	OPTION("-h", show_help),
+	OPTION("--help", show_help),
+	FUSE_OPT_END
+};
+
+void* fischl_init(struct fuse_conn_info *conn, struct fuse_config *cfg) {
+    cfg->use_ino = 1;
+    conn->want &= ~FUSE_CAP_ATOMIC_O_TRUNC;
+    options.fsop->initialize(options.load);
+}
+
+int fischl_create(const char *path, mode_t mode, struct fuse_file_info *fi) {
+	return options.fsop->fischl_create(path, mode, fi);
+}
+
+
+void fischl_destroy(void* private_data) {
+
+}
+
+static int fischl_getattr(const char *path, struct stat *stbuf, struct fuse_file_info *fi) {
+     return options.fsop->fischl_getattr(path, stbuf, fi);
+}
+
+static int fischl_access(const char* path, int mask) {
+    return options.fsop->fischl_access(path, mask);
+} 
+
+static int fischl_readlink(const char* path, char* buf, size_t size) {
+    return options.fsop->fischl_readlink(path, buf, size);
+}
+
+static int fischl_opendir(const char* path, struct fuse_file_info* fi) {
+    return options.fsop->fischl_opendir(path, fi);
+}
+
+static int fischl_readdir(const char *path, void *buf, fuse_fill_dir_t filler, off_t ft, struct fuse_file_info *fi, enum fuse_readdir_flags flg) {
+    return options.fsop->fischl_readdir(path, buf, filler, ft, fi, flg);
+}
+
+static int fischl_mknod(const char* path, mode_t mode, dev_t rdev) {
+    return options.fsop->fischl_mknod(path, mode, rdev);
+}
+
+static int fischl_mkdir(const char *path, mode_t mode) {
+    return options.fsop->fischl_mkdir(path, mode);
+}
+
+static int fischl_unlink(const char* path) {
+	return options.fsop->fischl_unlink(path);
+}
+
+static int fischl_rmdir(const char* path) {
+    return options.fsop->fischl_rmdir(path);
+}
+
+static int fischl_symlink(const char* from, const char* to) {
+    return options.fsop->fischl_symlink(from, to);
+}
+
+static int fischl_rename(const char *path, const char *new_name, unsigned int flags) {
+    return options.fsop->fischl_rename(path, new_name, flags);
+}
+
+static int fischl_link(const char* from, const char* to) {
+    return options.fsop->fischl_link(from, to);
+}
+
+static int fischl_chmod(const char *path, mode_t mode, struct fuse_file_info *fi) {
+    return options.fsop->fischl_chmod(path, mode, fi);
+}
+
+static int fischl_chown(const char *path, uid_t uid, gid_t gid, struct fuse_file_info *fi) {
+    return options.fsop->fischl_chown(path, uid, gid, fi);
+}
+
+static int fischl_truncate(const char *path, off_t offset, struct fuse_file_info *fi) {
+    return options.fsop->fischl_truncate(path, offset, fi);
+}
+
+static int fischl_utimens(const char *path, const struct timespec tv[2], struct fuse_file_info *fi) {
+    return options.fsop->fischl_utimens(path, tv, fi);
+}
+
+static int fischl_open(const char *path, struct fuse_file_info *fi) {
+    return options.fsop->fischl_open(path, fi);
+}
+
+static int fischl_read(const char* path, char *buf, size_t size, off_t offset, struct fuse_file_info* fi) {
+	return options.fsop->fischl_read(path, buf, size, offset, fi);
+}
+
+static int fischl_write(const char *path, const char *buf, size_t size, off_t offset, struct fuse_file_info *fi) {
+    return options.fsop->fischl_write(path, buf, size, offset, fi);
+}
+
+static int fischl_statfs(const char* path, struct statvfs* stbuf) {
+    return options.fsop->fischl_statfs(path, stbuf);
+}
+
+static int fischl_release(const char* path, struct fuse_file_info *fi) {
+	return options.fsop->fischl_release(path, fi);
+}
+
+static int fischl_releasedir(const char* path, struct fuse_file_info *fi) {
+    return options.fsop->fischl_releasedir(path, fi);
+}
+
+
+static const struct fuse_operations fischl_oper = {
+	
+    
+    .getattr     = fischl_getattr,
+    .readlink    = fischl_readlink,
+    .mknod       = fischl_mknod,
+    .mkdir       = fischl_mkdir,
+    .unlink      = fischl_unlink,
+    .rmdir       = fischl_rmdir,
+    .symlink     = fischl_symlink,
+    .rename      = fischl_rename,
+    .link        = fischl_link,
+    .chmod       = fischl_chmod,
+    .chown       = fischl_chown,
+    .truncate    = fischl_truncate,
+    .open        = fischl_open,
+    .read        = fischl_read,
+    .write       = fischl_write,
+    .statfs      = fischl_statfs,
+    .release     = fischl_release,
+    /*
+#ifdef HAVE_SETXATTR
+    .setxattr    = fischl_setxattr,
+    .getxattr    = fischl_getxattr,
+    .listxattr   = fischl_listxattr,
+    .removexattr = fischl_removexattr,
+#endif
+*/
+    .opendir     = fischl_opendir,
+    .readdir     = fischl_readdir,
+    .releasedir  = fischl_releasedir,
+    .init        = fischl_init,
+    .destroy     = fischl_destroy,
+    .access      = fischl_access,
+    .create      = fischl_create,
+    .utimens     = fischl_utimens,
+    //.bmap        = fischl_bmap,
+    //.ioctl       = fischl_ioctl,
+    //.poll        = fischl_poll,
+};
+
+static void show_help(const char *progname)
+{
+	printf("usage: %s [options] <mountpoint>\n\n", progname);
+	printf("File-system specific options:\n"
+	       "    --name=<s>          Name of the \"fischl\" file\n"
+	       "                        (default: \"fischl\")\n"
+	       "    --contents=<s>      Contents \"fischl\" file\n"
+	       "                        (default \"fischl, World!\\n\")\n"
+	       "\n");
+}
+
+
+int fischl(int argc, char *argv[])
+{
+	int ret;
+    if(argc < 3){
+        printf("WRONG ARGUMENTS\n");
+        return 0;
+    }
+    std::swap(argv[0], argv[1]);
+    std::swap(argv[1], argv[2]);
+
+	struct fuse_args args = FUSE_ARGS_INIT(argc-2, argv+2);
+    srand(time(NULL)); // Seed the random number generator
+    //const char* d = (argc < 2) ? "/dev/vdc" : argv[1];
+
+    //setupTestDirectory(&options.root);
+    if(strcmp(argv[0], "fake")==0){
+        options.H = new FakeRawDisk(27648);
+    }
+    else{
+        options.H = new RealRawDisk(argv[0]);
+        char zero_es[IO_BLOCK_SIZE] = {0};
+        /*printf("zeroed\n");
+        for (int i = 0; i < 200000; i++){
+            options.H->write_block(i, zero_es);
+        }*/
+    }
+    if(strcmp(argv[1], "l")==0){
+        options.load = true;
+    }
+    else if(strcmp(argv[1], "n")==0){
+        options.load = false;
+    }
+    else{
+        printf("WRONG l/n ARGUMENTS\n");
+        return 0;
+    }
+    options.fs = new Fs(options.H);
+    if(!options.load){
+        printf("FORMAT %d\n", options.fs->format());
+    }
+    options.fsop = new FilesOperation(*options.H, options.fs);
+
+      /*INode_Data inode_data;
+  options.fs->inode_manager->new_inode(1, 2, 3, &inode_data);
+
+  int buf_size = 100000;
+  int seg_size = 10;
+  char buf[buf_size];
+
+  int res;
+  int num = 1;
+
+  for (u_int64_t i = 0; i < 30 * 1024 * 1024;) {
+    for (int j = 0; j < buf_size;) {
+      j += sprintf(&buf[j], "%010d\n", ++num);
+    }
+    res = options.fs->write(&inode_data, buf, buf_size, i);
+    if (res < buf_size)
+      printf("ERR: %d %d\n", res, i);
+    i += res;
+  }
+
+  num = 1;
+
+  printf("done write\n");
+  char buf2[buf_size];
+
+  for (u_int64_t i = 0; i < 30 * 1024 * 1024;) {
+    for (int j = 0; j < buf_size;) {
+      j += sprintf(&buf[j], "%010d\n", ++num);
+    }
+    res = options.fs->read(&inode_data, buf2, buf_size, i);
+    if (res < buf_size)
+      printf("ERR2: %d %d\n", res, i);
+    i += res;
+    for (int j = 0; j < res; ++j) {
+      if (buf[j] != buf2[j])
+        printf("err err err: %d %d", buf[j], i);
+    }
+  }
+
+  printf("done read\n");
+
+  num = 1;
+
+  for (u_int64_t i = 0; i < 30 * 1024 * 1024;) {
+    for (int j = 0; j < buf_size;) {
+      j += sprintf(&buf[j], "%010d\n", ++num);
+    }
+    res = options.fs->read(&inode_data, buf2, buf_size, i);
+    if (res < buf_size)
+      printf("ERR2: %d %d\n", res, i);
+    i += res;
+    for (int j = 0; j < res; ++j) {
+      if (buf[j] != buf2[j])
+        printf("err err err: %d %d", buf[j], i);
+    }
+  }
+
+  printf("done read2\n");*/
+
+
+
+	/* Parse options */
+	if (fuse_opt_parse(&args, &options, option_spec, NULL) == -1)
+		return 1;
+
+	/* When --help is specified, first print our own file-system
+	   specific help text, then signal fuse_main to show
+	   additional help (by adding `--help` to the options again)
+	   without usage: line (by setting argv[0] to the empty
+	   string) */
+	if (options.show_help) {
+		show_help(argv[0]);
+		assert(fuse_opt_add_arg(&args, "--help") == 0);
+		args.argv[0][0] = '\0';
+	}
+
+	ret = fuse_main(args.argc, args.argv, &fischl_oper, NULL);
+	fuse_opt_free_args(&args);
+	return ret;
 }

lib/fs/datablock_manager.cpp

@@ -52,16 +52,24 @@ int DataBlock_Manager_Bitmap::new_datablock(u_int64_t *block_num) {
   char zero_buf[IO_BLOCK_SIZE] = {0};
 
   if (bitmap_block_num < block_segment_start ||
-      bitmap_block_num >= block_segment_end)
+      bitmap_block_num >= block_segment_end) {
+    perror("Error with new_datablock freelist head\n");
     return -1;
+  }
 
   if ((err = fs->disk->read_block(bitmap_block_num, bitmap.buf)) < 0)
     return err;
 
+  // if (bitmap.get_next_node() == fs->superblock.free_list_head)
+  //   printf("WARNING: ON LAST BITMAP "
+  //          "BLOCK!\n");
+
   u_int64_t relative_block_num = bitmap.claim_relative_block();
 
-  if (relative_block_num == 0)
+  if (relative_block_num == 0) {
+    errno = ENOSPC;
     return -1;
+  }
 
   u_int64_t block_num_ = relative_block_num + bitmap_block_num;
 
@@ -122,6 +130,7 @@ int DataBlock_Manager_Bitmap::format() {
   char buf[IO_BLOCK_SIZE] = {0};
   int err;
   u_int64_t i = block_segment_start;
+  write_u64(i, buf);
   for (; i <= block_segment_end - (2 * bitmap_region_size);
        i += bitmap_region_size) {
     write_u64(i + bitmap_region_size, buf);

lib/fs/fs.cpp

@@ -1,10 +1,13 @@
 #include "fs.hpp"
+#include <assert.h>
 
 Fs::Fs(RawDisk *disk) : disk(disk) {
+  assert((disk->diskSize / IO_BLOCK_SIZE) >
+         2 + NUM_INODE_BLOCKS + DATABLOCKS_PER_BITMAP_BLOCK);
   superblock = SuperBlock_Data();
   inode_manager = new INode_Manager_Freelist(this, 1, 1 + NUM_INODE_BLOCKS);
-  datablock_manager =
-      new DataBlock_Manager_Bitmap(this, 1 + NUM_INODE_BLOCKS, NUM_BLOCKS);
+  datablock_manager = new DataBlock_Manager_Bitmap(
+      this, 1 + NUM_INODE_BLOCKS, disk->diskSize / IO_BLOCK_SIZE);
 };
 
 Fs::~Fs() {

lib/fs/fs_data_types.cpp

@@ -1,4 +1,5 @@
 #include "fs.hpp"
+#include <time.h>
 
 template <typename T> T write_int(T num, char buf[]) {
   size_t i = 0;
@@ -50,11 +51,15 @@ void SuperBlock_Data::deserialize(char buf[]) {
 }
 
 INode_Data::INode_Data(u_int64_t inode_num) : inode_num(inode_num) {
+  struct timespec ts;
+  clock_gettime(CLOCK_REALTIME, &ts);
   metadata.uid = -1;
   metadata.gid = -1;
   metadata.permissions = -1;
   metadata.size = 0;
-  metadata.reference_count = 0;
+  metadata.access_time = (u_int64_t)ts.tv_sec * 1000000000ULL + ts.tv_nsec;
+  metadata.modification_time = (u_int64_t)ts.tv_sec * 1000000000ULL + ts.tv_nsec;
+  metadata.reference_count = 1;
 
   single_indirect_block = double_indirect_block = triple_indirect_block = 0;
 
@@ -68,6 +73,8 @@ size_t INode_Data::serialize_metadata(char buf[]) {
   i += write_u64(metadata.gid, &buf[i]);
   i += write_u64(metadata.permissions, &buf[i]);
   i += write_u64(metadata.size, &buf[i]);
+  i += write_u64(metadata.access_time, &buf[i]);
+  i += write_u64(metadata.modification_time, &buf[i]);
   i += write_u32(metadata.reference_count, &buf[i]);
   i += write_u32(metadata.flags, &buf[i]);
   return i;
@@ -79,6 +86,8 @@ size_t INode_Data::deserialize_metadata(char buf[]) {
   i += read_u64(&metadata.gid, &buf[i]);
   i += read_u64(&metadata.permissions, &buf[i]);
   i += read_u64(&metadata.size, &buf[i]);
+  i += read_u64(&metadata.access_time, &buf[i]);
+  i += read_u64(&metadata.modification_time, &buf[i]);
   i += read_u32(&metadata.reference_count, &buf[i]);
   i += read_u32(&metadata.flags, &buf[i]);
   return i;

lib/fs/fs_file_io.cpp

@@ -0,0 +1,418 @@
+#include "fs.hpp"
+
+class DatablockOperation {
+public:
+  DatablockOperation(int (*_skip)(DatablockOperation *, u_int64_t) = nullptr)
+      : skip(_skip) {}
+  size_t count;
+  size_t offset;
+  size_t bytes_completed;
+  Fs *fs;
+  virtual int operation(u_int64_t block_num, bool *delete_block) = 0;
+  int (*skip)(DatablockOperation *, u_int64_t);
+};
+
+int default_skip_func(DatablockOperation *this_op, u_int64_t num_blocks) {
+  this_op->bytes_completed += (num_blocks * IO_BLOCK_SIZE) - this_op->offset;
+  this_op->offset = 0;
+
+  if (this_op->bytes_completed >= this_op->count)
+    return 0;
+  return 1;
+}
+
+int truncate_skip_func(DatablockOperation *this_op, u_int64_t num_blocks) {
+  this_op->offset = 0;
+  return 1;
+}
+
+int Fs::sweep_inode_datablocks(INode_Data *inode_data,
+                               u_int64_t start_block_index, bool allocate,
+                               DatablockOperation *op) {
+  int result;
+
+  // printf("SWEEP %llu %llu %llu\n", inode_data->inode_num,
+  // inode_data->single_indirect_block, inode_data->double_indirect_block);
+
+  u_int64_t start_index = start_block_index;
+  for (size_t i = start_index; i < NUMBER_OF_DIRECT_BLOCKS; ++i) {
+    if ((result = sweep_datablocks(&(inode_data->direct_blocks[i]), 0, 0,
+                                   allocate, op)) <= 0)
+      return result;
+    start_index = NUMBER_OF_DIRECT_BLOCKS;
+  }
+
+  start_index -= NUMBER_OF_DIRECT_BLOCKS;
+
+  if (start_index < INDIRECT_BLOCKS) {
+    if ((result = sweep_datablocks(&(inode_data->single_indirect_block), 1,
+                                   start_index, allocate, op)) <= 0)
+      return result;
+    start_index = INDIRECT_BLOCKS;
+  }
+
+  start_index -= INDIRECT_BLOCKS;
+
+  if (start_index < INDIRECT_BLOCKS * INDIRECT_BLOCKS) {
+    if ((result = sweep_datablocks(&(inode_data->double_indirect_block), 2,
+                                   start_index, allocate, op)) <= 0)
+      return result;
+    start_index = INDIRECT_BLOCKS * INDIRECT_BLOCKS;
+  }
+
+  start_index -= INDIRECT_BLOCKS * INDIRECT_BLOCKS;
+
+  if (start_index <
+      (u_int64_t)INDIRECT_BLOCKS * INDIRECT_BLOCKS * INDIRECT_BLOCKS) {
+    if ((result = sweep_datablocks(&(inode_data->triple_indirect_block), 3,
+                                   start_index, allocate, op)) <= 0)
+      return result;
+  }
+
+  return 1;
+}
+
+// This can simply be made non recursive by copy pasting - it is just
+// written this way as a proof of concept
+int Fs::sweep_datablocks(u_int64_t *block_num, int indirect_num,
+                         u_int64_t start_block_index, bool allocate,
+                         DatablockOperation *op) {
+  char buf[IO_BLOCK_SIZE];
+  int err;
+  int result = -1;
+
+  u_int64_t num_blocks_indirect;
+  u_int64_t num_blocks = 1;
+  for (int i = 0; i < indirect_num; ++i) {
+    num_blocks_indirect = num_blocks;
+    num_blocks *= INDIRECT_BLOCKS;
+  }
+
+  if ((*block_num) == 0) {
+    if (allocate) {
+      if ((err = datablock_manager->new_datablock(block_num)) < 0)
+        return err;
+    } else if (op->skip != nullptr) {
+      return (*(op->skip))(op, num_blocks);
+    }
+  }
+
+  // if((*block_num)>30000000000000LL)printf("DIES 1 %llu %d %llu\n",
+  // *block_num, indirect_num, start_block_index);
+
+  if (indirect_num == 0) {
+    bool delete_block = false;
+    if ((result = op->operation(*block_num, &delete_block)) < 0)
+      return result;
+    if (delete_block) {
+      if ((err = datablock_manager->free_datablock(*block_num)) < 0)
+        return err;
+      (*block_num) = 0;
+    }
+    return result;
+  }
+
+  if ((*block_num) == 0) {
+    memset(buf, 0, sizeof(buf));
+  } else {
+
+    if ((err = disk->read_block(*block_num, buf)) < 0)
+      return err;
+  }
+
+  u_int64_t this_layer_start_index = start_block_index / num_blocks_indirect;
+  u_int64_t next_layer_start_index =
+      start_block_index - (num_blocks_indirect * this_layer_start_index);
+
+  u_int64_t temp;
+  u_int64_t next_block_num;
+  bool modified = false;
+
+  for (size_t i = this_layer_start_index * sizeof(u_int64_t); i < IO_BLOCK_SIZE;
+       i += sizeof(u_int64_t)) {
+    read_u64(&temp, &buf[i]);
+    next_block_num = temp;
+
+    if ((result = sweep_datablocks(&next_block_num, indirect_num - 1,
+                                   next_layer_start_index, allocate, op)) < 0)
+      return result;
+    if (next_block_num != temp) {
+      write_u64(next_block_num, &buf[i]);
+      modified = true;
+    }
+    if (result == 0)
+      break;
+    next_layer_start_index = 0;
+  }
+
+  if (modified) {
+    bool delete_block = true;
+    for (size_t i = 0; i < IO_BLOCK_SIZE; ++i)
+      if (buf[i] != 0) {
+        delete_block = false;
+        break;
+      }
+    if (delete_block) {
+      if ((err = datablock_manager->free_datablock(*block_num)) < 0)
+        return err;
+      (*block_num) = 0;
+    } else {
+      if ((err = disk->write_block(*block_num, buf)) < 0)
+        return err;
+    }
+  }
+
+  return result;
+}
+
+class ReadDatablockOperation : public DatablockOperation {
+public:
+  char *buf;
+  ReadDatablockOperation() : DatablockOperation() {}
+  int operation(u_int64_t block_num, bool *delete_block) override {
+    char datablock_buf[IO_BLOCK_SIZE];
+    int err;
+
+    size_t read_size =
+        std::min(IO_BLOCK_SIZE - offset, count - bytes_completed);
+
+    if (block_num != 0) {
+      if ((block_num) > 3000000000000LL)
+        printf("DIES 2\n");
+      if ((err = fs->disk->read_block(block_num, datablock_buf)) < 0)
+        return err;
+
+      memcpy(&buf[bytes_completed], &datablock_buf[offset], read_size);
+    } else {
+      memset(&buf[bytes_completed], 0, read_size);
+    }
+
+    offset = 0;
+    bytes_completed += read_size;
+
+    if (bytes_completed >= count)
+      return 0;
+    return 1;
+  }
+};
+
+class WriteDatablockOperation : public DatablockOperation {
+public:
+  const char *buf;
+  WriteDatablockOperation() : DatablockOperation() {}
+  int operation(u_int64_t block_num, bool *delete_block) override {
+    char datablock_buf[IO_BLOCK_SIZE];
+    int err;
+
+    size_t write_size =
+        std::min(IO_BLOCK_SIZE - offset, count - bytes_completed);
+
+    if (write_size < IO_BLOCK_SIZE) {
+      if ((block_num) > 3000000000000LL)
+        printf("DIES 3\n");
+      if ((err = fs->disk->read_block(block_num, datablock_buf)) < 0)
+        return err;
+    }
+
+    memcpy(&datablock_buf[offset], &buf[bytes_completed], write_size);
+
+    if ((err = fs->disk->write_block(block_num, datablock_buf)) < 0)
+      return err;
+
+    offset = 0;
+    bytes_completed += write_size;
+
+    if (bytes_completed >= count)
+      return 0;
+    return 1;
+  }
+};
+
+class TruncateDatablockOperation : public DatablockOperation {
+public:
+  TruncateDatablockOperation() : DatablockOperation(truncate_skip_func) {}
+  int operation(u_int64_t block_num, bool *delete_block) override {
+    char datablock_buf[IO_BLOCK_SIZE];
+    int err;
+
+    if (offset == 0) {
+      (*delete_block) = true;
+      return 1;
+    }
+    if ((block_num) > 3000000000000LL)
+      printf("DIES 4\n");
+    if ((err = fs->disk->read_block(block_num, datablock_buf)) < 0)
+      return err;
+
+    memset(&datablock_buf[offset], 0, IO_BLOCK_SIZE - offset);
+
+    if ((err = fs->disk->write_block(block_num, datablock_buf)) < 0)
+      return err;
+
+    offset = 0;
+
+    return 1;
+  }
+};
+
+class LseekNextDataDatablockOperation : public DatablockOperation {
+public:
+  LseekNextDataDatablockOperation() : DatablockOperation(default_skip_func) {}
+  int operation(u_int64_t block_num, bool *delete_block) override { return 0; }
+};
+
+class LseekNextHoleDatablockOperation : public DatablockOperation {
+public:
+  LseekNextHoleDatablockOperation() : DatablockOperation() {}
+  int operation(u_int64_t block_num, bool *delete_block) override {
+    if (block_num == 0)
+      return 0;
+
+    bytes_completed += (IO_BLOCK_SIZE)-offset;
+    offset = 0;
+
+    if (bytes_completed >= count)
+      return 0;
+    return 1;
+  }
+};
+
+ssize_t Fs::read(INode_Data *inode_data, char buf[], size_t count,
+                 size_t offset) {
+  int err;
+
+  if (offset >= inode_data->metadata.size)
+    return 0;
+
+  u_int64_t start_block_index = offset / IO_BLOCK_SIZE;
+  size_t internal_offset = offset - (start_block_index * IO_BLOCK_SIZE);
+
+  ReadDatablockOperation op = ReadDatablockOperation();
+  op.offset = internal_offset;
+  op.buf = buf;
+  op.count = std::min(count, inode_data->metadata.size - offset);
+  op.bytes_completed = 0;
+  op.fs = this;
+
+  // printf("IN READ %llu %llu %llu\n", inode_data->inode_num,
+  // inode_data->single_indirect_block, inode_data->double_indirect_block);
+  if ((err = sweep_inode_datablocks(inode_data, start_block_index, false,
+                                    &op)) < 0)
+    return err;
+
+  return op.bytes_completed;
+}
+
+ssize_t Fs::write(INode_Data *inode_data, const char buf[], size_t count,
+                  size_t offset) {
+  int err;
+
+  if (count + offset > FILE_SIZE_MAX) {
+    errno = EFBIG;
+    return -1;
+  }
+
+  u_int64_t start_block_index = offset / IO_BLOCK_SIZE;
+  size_t internal_offset = offset - (start_block_index * IO_BLOCK_SIZE);
+
+  WriteDatablockOperation op = WriteDatablockOperation();
+  op.offset = internal_offset;
+  op.buf = buf;
+  op.count = count;
+  op.bytes_completed = 0;
+  op.fs = this;
+
+  if ((err = sweep_inode_datablocks(inode_data, start_block_index, true, &op)) <
+      0)
+    return err;
+
+  inode_data->metadata.size =
+      std::max(offset + op.bytes_completed, inode_data->metadata.size);
+
+  return op.bytes_completed;
+}
+
+int Fs::truncate(INode_Data *inode_data, off_t length) {
+  int err;
+
+  if (length > FILE_SIZE_MAX) {
+    errno = EFBIG;
+    return -1;
+  }
+
+  if (length < 0) {
+    errno = EINVAL;
+    return -1;
+  }
+
+  u_int64_t start_block_index = length / IO_BLOCK_SIZE;
+  size_t internal_offset = length - (start_block_index * IO_BLOCK_SIZE);
+
+  TruncateDatablockOperation op = TruncateDatablockOperation();
+  op.offset = internal_offset;
+  op.fs = this;
+
+  if ((err = sweep_inode_datablocks(inode_data, start_block_index, false,
+                                    &op)) < 0)
+    return err;
+
+  inode_data->metadata.size = length;
+
+  return 0;
+}
+
+ssize_t Fs::lseek_next_data(INode_Data *inode_data, size_t offset) {
+  int err;
+
+  if (offset >= inode_data->metadata.size) {
+    errno = ENXIO;
+    return -1;
+  }
+
+  u_int64_t start_block_index = offset / IO_BLOCK_SIZE;
+  size_t internal_offset = offset - (start_block_index * IO_BLOCK_SIZE);
+
+  LseekNextDataDatablockOperation op = LseekNextDataDatablockOperation();
+  op.offset = internal_offset;
+  op.count = inode_data->metadata.size;
+  op.bytes_completed = offset;
+  op.fs = this;
+
+  if ((err = sweep_inode_datablocks(inode_data, start_block_index, false,
+                                    &op)) < 0)
+    return err;
+
+  if (op.bytes_completed >= inode_data->metadata.size) {
+    errno = ENXIO;
+    return -1;
+  }
+
+  return op.bytes_completed;
+}
+
+ssize_t Fs::lseek_next_hole(INode_Data *inode_data, size_t offset) {
+  int err;
+
+  if (offset >= inode_data->metadata.size) {
+    errno = ENXIO;
+    return -1;
+  }
+
+  u_int64_t start_block_index = offset / IO_BLOCK_SIZE;
+  size_t internal_offset = offset - (start_block_index * IO_BLOCK_SIZE);
+
+  LseekNextHoleDatablockOperation op = LseekNextHoleDatablockOperation();
+  op.offset = internal_offset;
+  op.count = inode_data->metadata.size;
+  op.bytes_completed = offset;
+  op.fs = this;
+
+  if ((err = sweep_inode_datablocks(inode_data, start_block_index, false,
+                                    &op)) < 0)
+    return err;
+
+  if (op.bytes_completed >= inode_data->metadata.size)
+    return inode_data->metadata.size;
+
+  return op.bytes_completed;
+}

lib/fs/fs_read_write.cpp

@@ -1,212 +0,0 @@
-#include "fs.hpp"
-
-class DatablockOperation {
-public:
-  char *buf;
-  size_t count;
-  size_t offset;
-  size_t bytes_completed;
-  RawDisk *disk;
-  virtual int operation(u_int64_t block_num) = 0;
-};
-
-int Fs::sweep_inode_datablocks(INode_Data *inode_data,
-                               u_int64_t start_block_index, bool allocate,
-                               DatablockOperation *op) {
-  int result;
-
-  u_int64_t start_index = start_block_index;
-  for (size_t i = start_index; i < NUMBER_OF_DIRECT_BLOCKS; ++i) {
-    if ((result = sweep_datablocks(&(inode_data->direct_blocks[i]), 0, 0,
-                                   allocate, op)) <= 0)
-      return result;
-    start_index = NUMBER_OF_DIRECT_BLOCKS;
-  }
-
-  start_index -= NUMBER_OF_DIRECT_BLOCKS;
-
-  if (start_index < IO_BLOCK_SIZE) {
-    if ((result = sweep_datablocks(&(inode_data->single_indirect_block), 1,
-                                   start_index, allocate, op)) <= 0)
-      return result;
-    start_index = IO_BLOCK_SIZE;
-  }
-
-  start_index -= IO_BLOCK_SIZE;
-
-  if (start_index < IO_BLOCK_SIZE * IO_BLOCK_SIZE) {
-    if ((result = sweep_datablocks(&(inode_data->double_indirect_block), 2,
-                                   start_index, allocate, op)) <= 0)
-      return result;
-    start_index = IO_BLOCK_SIZE * IO_BLOCK_SIZE;
-  }
-
-  start_index -= IO_BLOCK_SIZE * IO_BLOCK_SIZE;
-
-  if (start_index < (u_int64_t)IO_BLOCK_SIZE * IO_BLOCK_SIZE * IO_BLOCK_SIZE) {
-    if ((result = sweep_datablocks(&(inode_data->triple_indirect_block), 3,
-                                   start_index, allocate, op)) <= 0)
-      return result;
-  }
-
-  return -1;
-}
-
-// This can simply be made non recursive by copy pasting - it is just
-// written this way as a proof of concept
-int Fs::sweep_datablocks(u_int64_t *block_num, int indirect_num,
-                         u_int64_t start_block_index, bool allocate,
-                         DatablockOperation *op) {
-  char buf[IO_BLOCK_SIZE];
-  int err;
-  int result = -1;
-
-  if (allocate && (*block_num) == 0)
-    if ((err = datablock_manager->new_datablock(block_num)) < 0)
-      return err;
-
-  if (indirect_num == 0)
-    return op->operation(*block_num);
-
-  if ((*block_num) == 0) {
-    memset(buf, 0, sizeof(buf));
-  } else {
-    if ((err = disk->read_block(*block_num, buf)) < 0)
-      return err;
-  }
-
-  u_int64_t indirect_block_size = 1;
-  for (int i = 1; i < indirect_num; ++i)
-    indirect_block_size *= IO_BLOCK_SIZE;
-
-  u_int64_t this_layer_start_index = start_block_index / indirect_block_size;
-  u_int64_t next_layer_start_index =
-      start_block_index - (indirect_block_size * this_layer_start_index);
-
-  u_int64_t temp;
-  u_int64_t next_block_num;
-  bool modified = false;
-
-  for (size_t i = this_layer_start_index * sizeof(u_int64_t); i < IO_BLOCK_SIZE;
-       i += sizeof(u_int64_t)) {
-    read_u64(&temp, &buf[i]);
-    next_block_num = temp;
-    if ((result = sweep_datablocks(&next_block_num, indirect_num - 1,
-                                   next_layer_start_index, allocate, op)) < 0)
-      return result;
-    if (next_block_num != temp) {
-      write_u64(next_block_num, &buf[i]);
-      modified = true;
-    }
-    if (result == 0)
-      break;
-  }
-
-  if (modified)
-    if ((err = disk->write_block(*block_num, buf)) < 0)
-      return err;
-
-  return result;
-}
-
-class ReadDatablockOperation : public DatablockOperation {
-public:
-  int operation(u_int64_t block_num) override {
-    char datablock_buf[IO_BLOCK_SIZE];
-    int err;
-
-    // printf("PRINT: (%d) %d %d %d\n", block_num, count, offset,
-    // bytes_completed);
-
-    size_t read_size =
-        std::min(IO_BLOCK_SIZE - offset, count - bytes_completed);
-
-    if (block_num != 0) {
-      if ((err = disk->read_block(block_num, datablock_buf)) < 0)
-        return err;
-
-      memcpy(&buf[bytes_completed], &datablock_buf[offset], read_size);
-    } else {
-      memset(&buf[bytes_completed], 0, read_size);
-    }
-
-    offset = 0;
-    bytes_completed += read_size;
-
-    if (bytes_completed >= count)
-      return 0;
-    return 1;
-  }
-};
-
-class WriteDatablockOperation : public DatablockOperation {
-public:
-  int operation(u_int64_t block_num) override {
-    char datablock_buf[IO_BLOCK_SIZE];
-    int err;
-
-    size_t write_size =
-        std::min(IO_BLOCK_SIZE - offset, count - bytes_completed);
-
-    if (write_size < IO_BLOCK_SIZE)
-      if ((err = disk->read_block(block_num, datablock_buf)) < 0)
-        return err;
-
-    memcpy(&datablock_buf[offset], &buf[bytes_completed], write_size);
-
-    if ((err = disk->write_block(block_num, datablock_buf)) < 0)
-      return err;
-
-    offset = 0;
-    bytes_completed += write_size;
-
-    if (bytes_completed >= count)
-      return 0;
-    return 1;
-  }
-};
-
-ssize_t Fs::read(INode_Data *inode_data, char buf[], size_t count,
-                 size_t offset) {
-  int err;
-
-  u_int64_t start_block_index = offset / IO_BLOCK_SIZE;
-  size_t internal_offset = offset - (start_block_index * IO_BLOCK_SIZE);
-
-  ReadDatablockOperation op = ReadDatablockOperation();
-  op.offset = internal_offset;
-  op.buf = buf;
-  op.count = std::min(count, inode_data->metadata.size - offset);
-  op.bytes_completed = 0;
-  op.disk = disk;
-
-  if ((err = sweep_inode_datablocks(inode_data, start_block_index, false,
-                                    &op)) < 0)
-    return err;
-
-  return op.bytes_completed;
-}
-
-ssize_t Fs::write(INode_Data *inode_data, char buf[], size_t count,
-                  size_t offset) {
-  int err;
-
-  u_int64_t start_block_index = offset / IO_BLOCK_SIZE;
-  size_t internal_offset = offset - (start_block_index * IO_BLOCK_SIZE);
-
-  WriteDatablockOperation op = WriteDatablockOperation();
-  op.offset = internal_offset;
-  op.buf = buf;
-  op.count = count;
-  op.bytes_completed = 0;
-  op.disk = disk;
-
-  if ((err = sweep_inode_datablocks(inode_data, start_block_index, true, &op)) <
-      0)
-    return err;
-
-  inode_data->metadata.size =
-      std::max(offset + op.bytes_completed, inode_data->metadata.size);
-
-  return op.bytes_completed;
-}

lib/fs/fs_resize.cpp

@@ -1,141 +0,0 @@
-#include "fs.hpp"
-
-int Fs::allocate_datablock(INode_Data *inode_data, u_int64_t *datablock_num) {
-  int result;
-
-  for (size_t i = 0; i < NUMBER_OF_DIRECT_BLOCKS; ++i) {
-    result =
-        allocate_indirect(&(inode_data->direct_blocks[i]), 0, datablock_num);
-    if (result <= 0)
-      return result;
-  }
-
-  result =
-      allocate_indirect(&(inode_data->single_indirect_block), 1, datablock_num);
-  if (result <= 0)
-    return result;
-
-  result =
-      allocate_indirect(&(inode_data->double_indirect_block), 2, datablock_num);
-  if (result <= 0)
-    return result;
-
-  result =
-      allocate_indirect(&(inode_data->triple_indirect_block), 3, datablock_num);
-  if (result <= 0)
-    return result;
-
-  return -1;
-}
-
-// This can simply be made non recursive by copy pasting - it is just written
-// this way as a proof of concept
-int Fs::allocate_indirect(u_int64_t *storage, int n, u_int64_t *datablock_num) {
-  char buf[IO_BLOCK_SIZE];
-  int result;
-
-  if ((*storage) == 0) {
-    if ((result = datablock_manager->new_datablock(storage)) < 0)
-      return result;
-    if (n == 0) {
-      (*datablock_num) = (*storage);
-      return 0;
-    }
-  }
-
-  if (n == 0)
-    return 1;
-
-  u_int64_t temp;
-
-  if ((result = disk->read_block(*storage, buf)) < 0)
-    return result;
-
-  for (size_t i = 0; i < IO_BLOCK_SIZE; i += sizeof(u_int64_t)) {
-    read_u64(&temp, &buf[i]);
-    result = allocate_indirect(&temp, n - 1, datablock_num);
-    if (result < 0)
-      return result;
-    if (result == 0) {
-      write_u64(temp, &buf[i]);
-      if ((result = disk->write_block(*storage, buf)) < 0)
-        return result;
-      return 0;
-    }
-  }
-
-  return 1;
-}
-
-int Fs::deallocate_datablock(INode_Data *inode_data, u_int64_t *datablock_num) {
-  int result;
-
-  result = deallocate_indirect(&(inode_data->triple_indirect_block), 3,
-                               datablock_num);
-  if (result <= 0)
-    return result;
-
-  result = deallocate_indirect(&(inode_data->double_indirect_block), 2,
-                               datablock_num);
-  if (result <= 0)
-    return result;
-
-  result = deallocate_indirect(&(inode_data->single_indirect_block), 1,
-                               datablock_num);
-  if (result <= 0)
-    return result;
-
-  for (size_t i = NUMBER_OF_DIRECT_BLOCKS - 1; i >= 0; --i) {
-    result =
-        deallocate_indirect(&(inode_data->direct_blocks[i]), 0, datablock_num);
-    if (result <= 0)
-      return result;
-  }
-
-  return -1;
-}
-
-int Fs::deallocate_indirect(u_int64_t *storage, int n,
-                            u_int64_t *datablock_num) {
-  char buf[IO_BLOCK_SIZE];
-  int result;
-
-  if (*storage == 0)
-    return 1;
-
-  if (n == 0) {
-    u_int64_t temp_datablock_num = (*storage);
-    if ((result = datablock_manager->free_datablock(*storage)) < 0)
-      return result;
-    (*datablock_num) = temp_datablock_num;
-    (*storage) = 0;
-    return 0;
-  }
-
-  u_int64_t temp;
-
-  if ((result = disk->read_block(*storage, buf)) < 0)
-    return result;
-
-  for (size_t i = IO_BLOCK_SIZE - sizeof(u_int64_t); i >= 0;
-       i -= sizeof(u_int64_t)) {
-    read_u64(&temp, &buf[i]);
-    result = deallocate_indirect(&temp, n - 1, datablock_num);
-    if (result < 0)
-      return result;
-    if (result == 0) {
-      if (i == 0 && temp == 0) {
-        if ((result = datablock_manager->free_datablock(*storage)) < 0)
-          return result;
-        (*storage) = 0;
-      } else {
-        write_u64(temp, &buf[i]);
-        if ((result = disk->write_block(*storage, buf)) < 0)
-          return result;
-      }
-      return 0;
-    }
-  }
-
-  return 1;
-}

lib/main.cpp

@@ -2,7 +2,7 @@
 #include "fs.hpp"
 #include <stdio.h>
 
-int main() {
+int main(int argc, char *argv[]) {
   //   printf("hello word!");
   //   fischl *F = new fischl;
   //   F->init();
@@ -34,6 +34,7 @@ int main() {
 
   // disk->print_block(1597);
 
+  /*
   int err;
 
   RawDisk *disk = new FakeRawDisk(2048);
@@ -80,7 +81,11 @@ int main() {
   printf("\n\nREAD: %d\n", err);
   for (int i = 0; i < N; ++i)
     printf("%d ", buf2[i]);
-  printf("\n");
+  printf("\n");*/
+
+  fischl(argc, argv);
+
+
 
   return 0;
 }

lib/rawdisk.cpp

@@ -10,12 +10,12 @@ void RawDisk::print_block(u_int64_t block_number) {
     return;
   }
 
-  printf("\nBlock %llu:\n", block_number);
+  printf("\nBlock %lu:\n", block_number);
   for (int i = 0; i < IO_BLOCK_SIZE; i += sizeof(u_int64_t)) {
     num = 0;
     for (int j = 0; j < 8; j++)
       num |= ((u_int64_t)(unsigned char)buf[i + j]) << (8 * j);
-    printf("%llu ", num);
+    printf("%lu ", num);
     if ((i / sizeof(u_int64_t)) % nums_per_line == nums_per_line - 1)
       printf("\n");
   }
@@ -43,12 +43,14 @@ RealRawDisk::RealRawDisk(const char *directory)
     exit(1);
   }
 
+  // diskSize = 27648 * IO_BLOCK_SIZE;
+
   // Calculate the size in bytes
   numSectors = diskSize / 512; // Assuming a sector size of 512 bytes
 
   printf("====Initializing RawDisk====\n");
-  printf("Number of sectors: %llu\n", numSectors);
-  printf("Disk size (in bytes): %llu\n", diskSize);
+  printf("Number of sectors: %lu\n", numSectors);
+  printf("Disk size (in bytes): %lu\n", diskSize);
 }
 
 RealRawDisk::~RealRawDisk() {
@@ -61,14 +63,20 @@ int RealRawDisk::read_block(u_int64_t block_number, char *buffer) {
   u_int64_t offset = block_number * IO_BLOCK_SIZE;
 
   if (lseek(fd, offset, SEEK_SET) == (u_int64_t)-1) {
+    printf("LSEEK ERROR %llu %llu\n", block_number, offset);
     perror("Error seeking to offset");
+    errno = EIO;
     return -1;
   }
 
   // TODO: this is incorrect
   ssize_t bytesRead = read(fd, buffer, IO_BLOCK_SIZE);
+  // printf("READ BLOCK: %llu\n", block_number);
+  // for (int i = 0; i < IO_BLOCK_SIZE; i++)printf("%x", buffer[i]&0xff);
+  // printf("\n");
   if (bytesRead < IO_BLOCK_SIZE) {
     perror("Error reading from device");
+    errno = EIO;
     return -1;
   }
 
@@ -80,6 +88,7 @@ int RealRawDisk::write_block(u_int64_t block_number, char *buffer) {
 
   if (lseek(fd, offset, SEEK_SET) == (u_int64_t)-1) {
     perror("Error seeking to offset");
+    errno = EIO;
     return -1;
   }
 
@@ -87,6 +96,7 @@ int RealRawDisk::write_block(u_int64_t block_number, char *buffer) {
   ssize_t bytesWritten = write(fd, buffer, IO_BLOCK_SIZE);
   if (bytesWritten < IO_BLOCK_SIZE) {
     perror("Error writing to device");
+    errno = EIO;
     return -1;
   }
 
@@ -101,7 +111,7 @@ FakeRawDisk::FakeRawDisk(u_int64_t num_blocks) {
     exit(1);
   }
   printf("====Initializing FAKE RawDisk====\n");
-  printf("FAKE Disk size (in bytes): %llu\n", diskSize);
+  printf("FAKE Disk size (in bytes): %lu\n", diskSize);
   perror("!!! USING FAKE RawDisk - THIS IS FOR TESTING ONLY !!!");
 }
 
@@ -112,6 +122,7 @@ int FakeRawDisk::read_block(u_int64_t block_number, char *buffer) {
 
   if (offset + IO_BLOCK_SIZE > diskSize) {
     perror("Error reading past fake disk size");
+    errno = EIO;
     return -1;
   }
 
@@ -125,6 +136,7 @@ int FakeRawDisk::write_block(u_int64_t block_number, char *buffer) {
 
   if (offset + IO_BLOCK_SIZE > diskSize) {
     perror("Error writing past fake disk size");
+    errno = EIO;
     return -1;
   }
 

test/CMakeLists.txt

@@ -1,34 +1,69 @@
-set(TARGET_LAYER0 test_layer0)
-set(TARGET_LAYER1_API test_layer1_API)
-# set(TARGET_LAYER1_TEST1 test_layer1_test1)
-set(DIR_PLACE /dev/vdb)
+# set(TARGET_LAYER0 test_layer0)
+# set(TARGET_LAYER1_API test_layer1_API)
+# set(TARGET_LAYER2_API test_layer2_API)
+# set(TARGET_DIR_API test_dir_API)
+# set(DIR_PLACE /dev/vdb)
+# # set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -g -fsanitize=address")
 
-# add test sources here ... 
-add_executable(${TARGET_LAYER0}
-    # add need lib and source code here
-    layer0.cpp
-
-    ../lib/rawdisk.cpp
-
-)
-add_executable(${TARGET_LAYER1_API}
-    # add need lib and source code here
-    layer1_API.cpp
-
-    ../lib/fischl.cpp
-    ../lib/rawdisk.cpp
-    ../lib/fs/datablock_manager.cpp
-    ../lib/fs/fs_data_types.cpp
-    ../lib/fs/fs_resize.cpp
-    ../lib/fs/fs.cpp
-    ../lib/fs/inode_manager.cpp
-)
-# add_executable(${TARGET_LAYER1_TEST1}
+# # add test sources here ... 
+# add_executable(${TARGET_LAYER0}
 #     # add need lib and source code here
-#     layer1_test1.cpp
+#     layer0.cpp
+
+#     ../lib/rawdisk.cpp
+
+# )
+# add_executable(${TARGET_LAYER1_API}
+#     # add need lib and source code here
+#     layer1_API.cpp
+#     ../lib/rawdisk.cpp
+#     ../lib/fs/datablock_manager.cpp
+#     ../lib/fs/fs_data_types.cpp
+#     ../lib/fs/fs_file_io.cpp
+#     ../lib/fs/fs.cpp
+#     ../lib/fs/inode_manager.cpp
+# )
+# add_executable(${TARGET_LAYER2_API}
+#     ../lib/direntry.cpp
+#     ../lib/rawdisk.cpp
+#     ../lib/fs/datablock_manager.cpp
+#     ../lib/fs/fs_data_types.cpp
+#     ../lib/fs/fs_file_io.cpp
+#     ../lib/fs/fs.cpp
+#     ../lib/fs/inode_manager.cpp
+#     ../lib/files.cpp
+#     layer2_API_dir.cpp
+# )
+# add_executable(${TARGET_DIR_API}
+#     ../lib/direntry.cpp
+#     ../lib/rawdisk.cpp
+#     ../lib/fs/datablock_manager.cpp
+#     ../lib/fs/fs_data_types.cpp
+#     ../lib/fs/fs_file_io.cpp
+#     ../lib/fs/fs.cpp
+#     ../lib/fs/inode_manager.cpp
+#     dir_API.cpp
 # )
 
-# add test to activate ctest -VV
-add_test(NAME ${TARGET_LAYER0} COMMAND sudo ./${TARGET_LAYER0} ${DIR_PLACE})
-add_test(NAME ${TARGET_LAYER1_API} COMMAND sudo ./${TARGET_LAYER1_API} ${DIR_PLACE})
-# add_test(NAME ${TARGET_LAYER1_TEST1} COMMAND sudo ./${TARGET_LAYER1_TEST1} ${DIR_PLACE})
+# # Link Google Test to your test executables
+# target_link_libraries(${TARGET_LAYER0} gtest gtest_main)
+# target_link_libraries(${TARGET_LAYER1_API} gtest gtest_main)
+# target_link_libraries(${TARGET_DIR_API} gtest gtest_main)
+
+# # add test to activate ctest -VV
+# add_test(NAME ${TARGET_LAYER0} COMMAND sudo ./${TARGET_LAYER0} ${DIR_PLACE})
+# add_test(NAME ${TARGET_LAYER1_API} COMMAND sudo ./${TARGET_LAYER1_API} ${DIR_PLACE})
+# add_test(NAME ${TARGET_LAYER2_API} COMMAND sudo ./${TARGET_LAYER2_API} ${DIR_PLACE})
+# add_test(NAME ${TARGET_DIR_API} COMMAND sudo ./${TARGET_DIR_API} ${DIR_PLACE})
+
+
+# # Add the -Wall flag
+# target_compile_options(${TARGET_LAYER2_API} PRIVATE -Wall)
+
+# # Use pkg-config to get flags for fuse3
+# find_package(PkgConfig REQUIRED)
+# pkg_search_module(FUSE3 REQUIRED fuse3)
+
+# # Add the flags from pkg-config for fuse3
+# target_include_directories(${TARGET_LAYER2_API} PRIVATE ${FUSE3_INCLUDE_DIRS})
+# target_link_libraries(${TARGET_LAYER2_API} PRIVATE ${FUSE3_LIBRARIES} gtest gtest_main)

test/dir_API.cpp

@@ -0,0 +1,352 @@
+/***********************************************************
+ Directory owns treeNode and FileNode structure, detect S_IFDIR to make treeNode or not (see add_entry Function)
+ File owns FileNode structure only, detect !S_IFDIR 
+
+*/
+#include <stdio.h>
+#include <string>
+#include <assert.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <gtest/gtest.h>
+#include <iostream>
+#include "fs.hpp"
+#include "direntry.h"
+/*
+typedef struct file_test{
+    const char* name;
+    file_test* next;//use linked-list to know the file at the same level directory
+}file_test;
+typedef struct dir_test{
+    const char* name;
+    file_test*  inFile;
+    dir_test*   subdir;
+    dir_test*   next;//use linked-list to know the other dir at the same parent dir.
+}dir_test;
+
+//global can be taken
+const char* d;
+TreeNode *root;
+std::string target_filepath;
+dir_test* mock_root = nullptr;
+
+int total_dir_num = 0;
+int total_file_num = 0;
+int total_free_dir = 0;
+int total_free_file = 0;
+
+
+const char* generateRandomName(size_t length) {
+    const std::string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+    std::string randomString;
+
+    for (size_t i = 0; i < length; ++i) {
+        randomString += chars[rand() % chars.size()];
+    }
+
+    // Allocate memory and copy the string
+    char* name = new char[randomString.length() + 1];
+    strcpy(name, randomString.c_str());
+    return name;
+}
+
+// Recursive function to create directory hierarchy
+dir_test* createDirHierarchy(int level, int maxLevel) {
+    if (level > maxLevel) {
+        return nullptr;
+    }
+
+    dir_test* head = nullptr;
+    dir_test* current = nullptr;
+
+    for (int i = 0; i < 3; ++i) {
+        dir_test* newDir = new dir_test;
+        newDir->name = generateRandomName(6); // Generate a random name for the directory
+        newDir->inFile = nullptr; // Initialize file list to nullptr
+        newDir->subdir = createDirHierarchy(level + 1, maxLevel); // Recursively create subdirectories
+        newDir->next = nullptr;
+
+        // Create file list for this directory
+        file_test* fileHead = nullptr;
+        file_test* fileCurrent = nullptr;
+        for (int j = 0; j < 3; ++j) {
+            file_test* newFile = new file_test;
+            newFile->name = generateRandomName(6); // Generate a random name for the file
+            newFile->next = nullptr;
+
+            if (!fileHead) {
+                fileHead = newFile;
+            } else {
+                fileCurrent->next = newFile;
+            }
+            fileCurrent = newFile;
+        }
+        newDir->inFile = fileHead;
+
+        // Add the new directory to the list
+        if (!head) {
+            head = newDir;
+        } else {
+            current->next = newDir;
+        }
+        current = newDir;
+    }
+
+    return head;
+}
+
+// Setup function for the test directory
+void setupTestDirectory(dir_test** root) {
+    // Allocate memory for root
+    *root = new dir_test;
+    (*root)->name = strdup("/"); // use / as begin
+    (*root)->inFile = nullptr; // Initialize file list to nullptr
+    (*root)->subdir = createDirHierarchy(0, 1);
+    (*root)->next = nullptr;
+    file_test* fileHead = nullptr;
+    file_test* fileCurrent = nullptr;
+    for (int j = 0; j < 3; ++j) {
+        file_test* newFile = new file_test;
+        newFile->name = generateRandomName(6); // Generate a random name for the file
+        newFile->next = nullptr;
+
+        if (!fileHead) {
+            fileHead = newFile;
+        } else {
+            fileCurrent->next = newFile;
+        }
+        fileCurrent = newFile;
+    }
+    (*root)->inFile = fileHead;
+}
+
+// Function to free a list of files
+void freeFileList(file_test* fileList) {
+    while (fileList != nullptr) {
+        file_test* temp = fileList;
+        fileList = fileList->next;
+        total_free_file++;//for debug
+        delete[] temp->name; // Free the name string
+        delete temp; // Free the current file
+    }
+}
+
+// Recursive function to free the directory hierarchy
+void freeDirHierarchy(dir_test* dir) {
+    while (dir != nullptr) {
+        dir_test* temp = dir;
+        dir = dir->next;
+        total_free_dir++;//for debug
+        freeFileList(temp->inFile);  // Free the list of files in the directory
+        freeDirHierarchy(temp->subdir); // Recursively free subdirectories
+        delete[] temp->name; // Free the name string
+        delete temp; // Free the current directory
+    }
+}
+
+// Function to print the list of files in a directory
+void printFileList(const file_test* fileList) {
+    const file_test* currentFile = fileList;
+    while (currentFile != nullptr) {
+        // std::cout << "  File: " << currentFile->name << std::endl;
+        total_file_num++;
+        currentFile = currentFile->next;
+    }
+}
+
+void traverseDirHierarchy(const dir_test* dir, int depth = 0) {
+    while (dir != nullptr) {
+        // std::cout << "Depth " << depth << ", Directory: " << dir->name << std::endl;
+        total_dir_num++;//for debug
+
+        // Print files in this directory
+        printFileList(dir->inFile);
+        // Recursively traverse subdirectories
+        traverseDirHierarchy(dir->subdir, depth + 1);
+
+        // Go to the next directory at the same level
+        dir = dir->next;
+    }
+}
+
+TEST(DirTest, root_test) {
+    //Init fake root directory
+    INode_Data inode_root;
+    u_int64_t file_permissions = 0;
+    inode_root.metadata.permissions = file_permissions | S_IFDIR;
+    root = fischl_init_entry(0, mock_root->name, &inode_root);//0 is inode number assigned by inode_allocate()
+}
+TEST(DirTest, AddFile_test) {
+    //assume file and dir itself(content,metadata) same,but different name and inode number
+    INode_Data inode_file;
+    INode_Data inode_dir;
+    u_int64_t file_permissions = 0;
+    file_permissions = 0;
+    inode_dir.metadata.permissions = file_permissions | S_IFDIR;
+    fischl_add_entry(root, 2, mock_root->inFile->name,&inode_file);
+    fischl_add_entry(root, 3, mock_root->subdir->name,&inode_dir);
+}
+TEST(DirTest, FindFile_test) {
+    //find file
+    target_filepath = std::string("/") + mock_root->inFile->name;
+    FileNode *get_file = fischl_find_entry(root,target_filepath.c_str());
+    EXPECT_TRUE(get_file != NULL);
+    EXPECT_STREQ(get_file->name, mock_root->inFile->name);
+    //find dir
+    target_filepath = std::string("/") + mock_root->subdir->name + "/";
+    FileNode *get_dir = fischl_find_entry(root,target_filepath.c_str());
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success 
+    EXPECT_STREQ(get_dir->name, mock_root->subdir->name);
+    ASSERT_TRUE(get_dir->subdirectory != NULL);//secure it is directory
+    //check . function
+    get_dir = fischl_find_entry(root,"./");
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success 
+    EXPECT_STREQ(get_dir->name, mock_root->name);
+    ASSERT_TRUE(get_dir->subdirectory != NULL);//secure it is directory
+    //check .. function
+    get_dir = fischl_find_entry(root,"..");
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success
+    EXPECT_STREQ(get_dir->name, mock_root->name);
+    ASSERT_TRUE(get_dir->subdirectory != NULL);//secure it is directory
+}
+TEST(DirTest, Add_FindFile_test) {
+    //add file and dir under subdirectory instead of root
+    INode_Data inode_file;
+    INode_Data inode_dir;
+    u_int64_t file_permissions = 0;
+    file_permissions = 0;
+    inode_dir.metadata.permissions = file_permissions | S_IFDIR;
+
+    // add with subdirectory
+    //Treenode dir(you cannot find here), you only can get Filenode dir based on fischl_find_entry Function
+    //So use Filenode->subdirectory will point to the treenode dir, then can add files
+    target_filepath = std::string("/") + mock_root->subdir->name + "/";
+    FileNode *get_dir = fischl_find_entry(root, target_filepath.c_str());
+    fischl_add_entry(get_dir->subdirectory, 4, mock_root->subdir->inFile->name, &inode_file);
+    
+    //verfication treeNode and Filenode relationship
+    target_filepath = std::string("/") + mock_root->subdir->name + "/" + mock_root->subdir->inFile->name;
+    TreeNode *get_dir_tree = find_parentPath(root,target_filepath.c_str());
+    ASSERT_TRUE(get_dir_tree == get_dir->subdirectory);//treeNode dir should be same as treeNode subdir in that Filenode
+ 
+    //two Ways to get File(include dir itself) information
+    FileNode *get_file = NULL;
+    //1. absolute path, the root(treeNode) will always exist when initialize
+    get_file = fischl_find_entry(root,target_filepath.c_str());
+    EXPECT_TRUE(get_file != NULL);
+    EXPECT_STREQ(get_file->name,mock_root->subdir->inFile->name);
+    //2. relative path, the get_dir(FileNode)->subdirectory(treeNode), use treeNode(dir) to find
+    target_filepath = std::string("/") + mock_root->subdir->inFile->name;
+    get_file = fischl_find_entry(get_dir->subdirectory,target_filepath.c_str());
+    EXPECT_TRUE(get_file != NULL);
+    EXPECT_STREQ(get_file->name, mock_root->subdir->inFile->name);
+    
+    //add one more file under fist subdir
+    fischl_add_entry(get_dir->subdirectory, 5, mock_root->subdir->inFile->next->name, &inode_file);
+    //add one more directory under fist subdir
+    fischl_add_entry(get_dir->subdirectory, 6, mock_root->subdir->subdir->name, &inode_dir);
+    //find
+    target_filepath = std::string("./") + mock_root->subdir->inFile->next->name;
+    get_file = fischl_find_entry(get_dir->subdirectory, target_filepath.c_str());
+    EXPECT_TRUE(get_file != NULL);
+    EXPECT_STREQ(get_file->name, mock_root->subdir->inFile->next->name);
+    //use .. from fist subdir to find file1
+    target_filepath = std::string("../") + mock_root->inFile->name;
+    get_file = fischl_find_entry(get_dir->subdirectory,target_filepath.c_str());
+    EXPECT_TRUE(get_file != NULL);
+    EXPECT_STREQ(get_file->name,mock_root->inFile->name);
+    //check fist subdir with .
+    get_dir = fischl_find_entry(get_dir->subdirectory,".");
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success
+    EXPECT_STREQ(get_dir->name, mock_root->subdir->name);
+    ASSERT_TRUE(get_dir->subdirectory != NULL);//secure it is directory
+    //check root via fist subdir
+    get_dir = fischl_find_entry(get_dir->subdirectory,"..");
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success
+    EXPECT_STREQ(get_dir->name, mock_root->name);
+    ASSERT_TRUE(get_dir->subdirectory != NULL);//secure it is directory
+    //use .. to access parent directory
+    target_filepath = std::string("/") + mock_root->subdir->name + "/" + mock_root->subdir->subdir->name + "/..";
+    get_dir = fischl_find_entry(root, target_filepath.c_str());
+    EXPECT_TRUE(get_dir != NULL);
+    EXPECT_STREQ(get_dir->name, mock_root->subdir->name);
+    target_filepath = std::string("/") + mock_root->subdir->name + "/" + mock_root->subdir->subdir->name + "/../..";
+    get_file = fischl_find_entry(root, target_filepath.c_str());
+    EXPECT_TRUE(get_file != NULL);
+    EXPECT_STREQ(get_file->name, mock_root->name);
+    EXPECT_TRUE(get_file->subdirectory != NULL);
+    EXPECT_TRUE(get_file->subdirectory->self_info == get_file);
+}
+
+// TEST(DirTest, Scale_test){
+//     INode_Data inode_file;
+//     INode_Data inode_dir;
+//     u_int64_t file_permissions = 0;
+//     file_permissions = 0;
+//     inode_dir.permissions = file_permissions | S_IFDIR;
+//     dir_test* temp = mock_root;
+//     // First loop: Add files and subdirectories under root
+//     file_test* currentFile = temp->inFile;
+//     dir_test* currentSubdir = temp->subdir;
+//
+//     for (int i = 1; i < 7; ++i) {
+//         if (currentFile) {
+//             //add can still add the same filename and dir name, but it will be linked behind the first added
+//             fischl_add_entry(root, i, currentFile->name, &inode_file);
+//             currentFile = currentFile->next;
+//         }
+//         if (currentSubdir) {
+//             fischl_add_entry(root, i + 1, currentSubdir->name, &inode_dir);
+//             currentSubdir = currentSubdir->next;
+//         }
+//     }
+
+//     // Second loop: Process each subdir under root
+//     temp = mock_root->subdir;
+//     while (temp) {
+//         target_filepath = "/" + std::string(temp->name) + "/";
+//         FileNode* get_dir = fischl_find_entry(root, target_filepath.c_str());
+
+//         ASSERT_TRUE(get_dir != NULL);
+//         EXPECT_STREQ(get_dir->name, temp->name);
+//         ASSERT_TRUE(get_dir->subdirectory != NULL);
+//         // Add files and subdirectories in each subdir
+//         file_test* currentFile = temp->inFile;
+//         dir_test* currentSubSubdir = temp->subdir;
+//         for (int j = 7; j < 13; ++j) {
+//             if (currentFile) {
+//                 fischl_add_entry(get_dir->subdirectory, j, currentFile->name, &inode_file);
+//                 currentFile = currentFile->next;
+//             }
+//             if (currentSubSubdir) {
+//                 fischl_add_entry(get_dir->subdirectory, j + 1, currentSubSubdir->name, &inode_dir);
+//                 currentSubSubdir = currentSubSubdir->next;
+//             }
+//         }
+
+//         temp = temp->next; // Move to next subdir
+//     }
+// }*/
+
+
+int main(int argc, char **argv) {
+    /*srand(time(NULL)); // Seed the random number generator
+    d = (argc < 2) ? "/dev/vdc" : argv[1];
+
+    setupTestDirectory(&mock_root);
+
+    ::testing::InitGoogleTest(&argc, argv);
+    int result = RUN_ALL_TESTS();
+
+    total_dir_num = 0;
+    total_file_num = 0;
+    traverseDirHierarchy(mock_root);//mock_root
+    printf("Traverse Total: Dir %d, File %d\n",total_dir_num, total_file_num);
+    
+    // Cleanup
+    freeDirHierarchy(mock_root);//mock_root
+    printf("Free Total: Dir %d, File %d\n",total_free_dir, total_free_file);
+    freeTree(root);
+    return result;*/
+    return 0;
+}

test/layer1_API.cpp

@@ -7,7 +7,7 @@
 int main(int argc, char *argv[]) {
   // const char* d = (argc < 2) ? "/dev/vdc" : argv[1];
 
-  RawDisk *H = new FakeRawDisk(2048);
+  RawDisk *H = new FakeRawDisk(21504);
   Fs *fs = new Fs(H);
 
   printf("test inode\n");
@@ -65,12 +65,16 @@ int main(int argc, char *argv[]) {
                   1); // the first 8 bytes of 4k I/O block will store
                       // the next address(after 2048*4k I/O block)
   // test the end of the datablock
-  H->read_block(NUM_BLOCKS - DATABLOCKS_PER_BITMAP_BLOCK - 1, buffer);
+
+  H->read_block(fs->disk->diskSize / IO_BLOCK_SIZE -
+                    DATABLOCKS_PER_BITMAP_BLOCK - 1,
+                buffer);
   t = 0;
   for (int j = 0; j < 8; j++)
     t |= ((u_int64_t)(unsigned char)buffer[j]) << (8 * j);
 
-  assert(t == NUM_BLOCKS - DATABLOCKS_PER_BITMAP_BLOCK - 1);
+  assert(t ==
+         fs->disk->diskSize / IO_BLOCK_SIZE - DATABLOCKS_PER_BITMAP_BLOCK - 1);
 
   /***************************test inode
    * de/allocation**********************************/
@@ -108,34 +112,35 @@ int main(int argc, char *argv[]) {
   // after free the datablock, the program will find the first smallest address
   // of datablock to give to the inode should test random resize each node, but
   // should use datablock_free data structure to record
-  u_int64_t rec_datablock_free[10][3] = {0}; // array version
-  u_int64_t temp_block_num = 0;
-  for (int i = 0; i < 10; i++) {
-    // printf("%dth data block starting addres: ", i);
-    for (int j = 0; j < 6; j++) {
-      fs->allocate_datablock(&inode_list[i], &temp_block_num);
-      // printf("%d," ,inode_inside[i].datablock_allocate(*H));
-    }
-    // printf("\n");
-  }
-  for (int i = 0; i < 10; i++) {
-    // printf("%dth data block free addres: ", i);
-    for (int j = 2; j >= 0; j--) {
-      fs->deallocate_datablock(&inode_list[i], &(rec_datablock_free[i][j]));
-      // printf("", rec_datablock_free[i][j]);
-    }
-    // printf("\n");
-  }
+  //   u_int64_t rec_datablock_free[10][3] = {0}; // array version
+  //   u_int64_t temp_block_num = 0;
+  //   for (int i = 0; i < 10; i++) {
+  //     // printf("%dth data block starting addres: ", i);
+  //     for (int j = 0; j < 6; j++) {
+  //       fs->allocate_datablock(&inode_list[i], &temp_block_num);
+  //       // printf("%d," ,inode_inside[i].datablock_allocate(*H));
+  //     }
+  //     // printf("\n");
+  //   }
+  //   for (int i = 0; i < 10; i++) {
+  //     // printf("%dth data block free addres: ", i);
+  //     for (int j = 2; j >= 0; j--) {
+  //       fs->deallocate_datablock(&inode_list[i],
+  //       &(rec_datablock_free[i][j]));
+  //       // printf("", rec_datablock_free[i][j]);
+  //     }
+  //     // printf("\n");
+  //   }
 
-  for (int i = 0; i < 10; i++) {
-    // printf("%dth data block allocate again addres: ", i);
-    for (int j = 0; j < 3; j++) {
-      fs->allocate_datablock(&inode_list[i], &temp_block_num);
-      assert(temp_block_num == rec_datablock_free[i][j]);
-      // printf("%d," ,inode_inside[i].datablock_allocate(*H));
-    }
-    // printf("\n");
-  }
+  //   for (int i = 0; i < 10; i++) {
+  //     // printf("%dth data block allocate again addres: ", i);
+  //     for (int j = 0; j < 3; j++) {
+  //       fs->allocate_datablock(&inode_list[i], &temp_block_num);
+  //       assert(temp_block_num == rec_datablock_free[i][j]);
+  //       // printf("%d," ,inode_inside[i].datablock_allocate(*H));
+  //     }
+  //     // printf("\n");
+  //   }
 
   // printf("}\n");
   delete H; // Delete the RawDisk object

test/layer2_API.cpp

@@ -0,0 +1,120 @@
+#include <stdio.h>
+#include <string>
+#include <assert.h>
+#include "files.h"
+
+int main(int argc, char *argv[]) {
+    const char* d = (argc < 2) ? "/dev/vdc" : argv[1];
+    
+    RawDisk *H = new RawDisk(d);
+
+    printf("test files\n");
+    FilesOperation fsop(*H);
+    fsop.initialize_rootinode();
+    
+    // create multiple files using mkdir or mknod
+    printf("=== Part 1: create files by path ===\n");
+    u_int64_t file1 = fsop.fischl_mknod("/test",0); // mode here is not used yet
+    printf("/test is inode %llu, it is a file\n", file1);
+    u_int64_t file2 = fsop.fischl_mkdir("/foo",0);
+    printf("/foo is inode %llu, it is a directory\n", file2);
+    fsop.printDirectory(1);
+    u_int64_t file3 = fsop.fischl_mkdir("/foo/bar",0);
+    printf("/foo/bar is inode %llu, it is a directory\n", file3);
+    fsop.printDirectory(file2);
+    u_int64_t file4 = fsop.fischl_mknod("/foo/bar/baz",0);
+    printf("/foo/bar/baz is inode %llu, it is a file\n", file4);
+    // the following three testcases will fail
+    u_int64_t f1 = fsop.fischl_mkdir("foo/bar",0);
+    u_int64_t f2 = fsop.fischl_mkdir("/doesnt_exist/bar",0);
+    u_int64_t f3 = fsop.fischl_mkdir("/test/bar",0);
+    u_int64_t f4 =  fsop.fischl_mkdir("/test",0);
+    u_int64_t f5 =  fsop.fischl_mkdir("/foo/bar",0);
+    u_int64_t f6 =  fsop.fischl_mkdir("/foo/bar/..",0);
+
+    // write to files (TODO: fischl_write)
+    // read and write to indirect datablocks are not supported yet
+    printf("=== Part 2: write to files ===\n");
+    char buffer[IO_BLOCK_SIZE] = {0};
+    INode inode;
+    inode.inode_construct(file1, *H);
+    buffer[0] = '1';
+    fsop.write_datablock(inode, 0, buffer);
+    inode.inode_save(*H);
+    inode.inode_construct(file4, *H);
+    buffer[0] = '4';
+    fsop.write_datablock(inode, 3, buffer);
+    buffer[0] = '5';
+    fsop.write_datablock(inode, 101, buffer);
+    inode.inode_save(*H);
+    // TODO: guard against overwriting directory datablocks
+
+    // retrieve inode-number by path
+    printf("=== Part 3: retrieve inode number using path (namei) ===\n");
+    u_int64_t file_test = fsop.namei("/test");
+    printf("inode number for \"/test\" is %llu\n", file_test);
+    assert(file_test == file1);
+    u_int64_t file_baz = fsop.namei("/foo/bar/baz");
+    printf("inode number for \"/foo/bar/baz\" is %llu\n", file_baz);
+    assert(file_baz == file4);
+    u_int64_t file_foo = fsop.namei("/foo/bar/..");
+    printf("inode number for \"/foo/bar/..\" is %llu\n", file_foo);
+    assert(file_foo == file2);
+    u_int64_t file_bar = fsop.namei("/foo/bar/.");
+    printf("inode number for \"/foo/bar/.\" is %llu\n", file_bar);
+    assert(file_bar == file3);
+
+    // read files (TODO: fischl_read)
+    printf("=== Part 4: read from files ===\n");
+    char read_buffer[IO_BLOCK_SIZE] = {0};
+    INode inode_read;
+    inode_read.inode_construct(file_test, *H);
+    fsop.read_datablock(inode_read, 0, read_buffer);
+    assert(read_buffer[0] == '1');
+    inode_read.inode_construct(file_baz, *H);
+    fsop.read_datablock(inode_read, 3, read_buffer);
+    assert(read_buffer[0] == '4');
+    fsop.read_datablock(inode_read, 101, read_buffer);
+    assert(read_buffer[0] == '5');
+
+    // pressure test create directory
+    printf("=== Part 5: pressure test create files ===\n");
+    u_int64_t file_pressure = fsop.fischl_mkdir("/pressure", 0);
+    u_int64_t inode_numbers[700];
+    std::string prefix = "/pressure/No_";
+    for(int i=0;i<700;i++){
+        inode_numbers[i] = fsop.fischl_mkdir((prefix+std::to_string(i)).c_str(), 0);
+    }
+    for(int i=0;i<700;i++){
+        u_int64_t inode_number = fsop.namei((prefix+std::to_string(i)).c_str());
+        assert(inode_number == inode_numbers[i]);
+    }
+
+    printf("=== Part 6: unlink test ===\n");
+    fsop.printDirectory(file_pressure);
+    for(int i=0;i<700;i+=2){
+        assert(!fsop.fischl_unlink((prefix+std::to_string(i)).c_str()));
+    }
+    for(int i=0;i<4;i+=2){
+        assert(fsop.namei((prefix+std::to_string(i)).c_str())==(u_int64_t)(-1));
+    }
+    for(int i=1;i<700;i+=2){
+        u_int64_t inode_number = fsop.namei((prefix+std::to_string(i)).c_str());
+        assert(inode_number == inode_numbers[i]);
+    }
+    fsop.printDirectory(file_pressure);
+    std::string newprefix = "/pressure/New";
+    for(int i=0;i<700;i+=2){
+        inode_numbers[i] = fsop.fischl_mkdir((newprefix+std::to_string(i)).c_str(), 0);
+    }
+    for(int i=0;i<700;i+=2){
+        u_int64_t inode_number = fsop.namei((newprefix+std::to_string(i)).c_str());
+        assert(inode_number == inode_numbers[i]);
+    }
+    fsop.printDirectory(file_pressure);
+
+    // long filename test
+    std::string longfilename = std::string(255,'A');
+    u_int64_t filelong = fsop.fischl_mknod((std::string("/")+longfilename).c_str(),0);
+    printf("/AAA...AAA is inode %llu, it is a file\n", filelong);
+}

test/layer2_API_dir.cpp

@@ -0,0 +1,377 @@
+#define FUSE_USE_VERSION 31
+
+#include <stdio.h>
+#include <string>
+#include <assert.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <gtest/gtest.h>
+#include <iostream>
+#include "fs.hpp"
+#include "files.h"
+
+
+typedef struct file_test{
+    const char* name;
+    file_test* next;//use linked-list to know the file at the same level directory
+}file_test;
+typedef struct dir_test{
+    const char* name;
+    file_test*  inFile;
+    dir_test*   subdir;
+    dir_test*   next;//use linked-list to know the other dir at the same parent dir.
+}dir_test;
+
+void setupTestDirectory(dir_test** root);
+void freeDirHierarchy(dir_test* dir);
+void traverseDirHierarchy(const dir_test* dir, int depth);
+
+//global can be taken
+std::string target_filepath;
+dir_test* mock_root = nullptr;
+RawDisk *H; // Use FakeRawDisk here if memory sanitizer complains
+Fs *fs;
+FilesOperation *fsop;
+std::string prefix = "/pressure/No_";
+
+int total_dir_num = 0;
+int total_file_num = 0;
+int total_free_dir = 0;
+int total_free_file = 0;
+
+FileNode* fischl_load_entry(TreeNode *root, const char *path){
+    return fischl_find_entry(fs, root, path);
+}
+
+TEST(FileOperationTest, MkdirnodTest) {
+
+    fsop->initialize_rootinode();
+    struct fuse_file_info fi;
+
+    mode_t mode;//set mode
+    mode = S_IRWXU | S_IRWXG | S_IRWXO;//future should test permission
+    //S_IRWXU(S_IRUSR | S_IWUSR | S_IXUSR) (owner), S_IRWXG(S_IRGRP | S_IWGRP | S_IXGRP) (group), S_IRWXO(S_IROTH | S_IWOTH | S_IXOTH)
+    EXPECT_EQ(fsop->fischl_create("/test", mode, &fi), 0);
+    EXPECT_EQ(fsop->fischl_mkdir("/foo", mode), 0);
+    EXPECT_EQ(fsop->fischl_mkdir("/foo/bar", mode),0);
+    fsop->printDirectory(1);
+    EXPECT_EQ(fsop->fischl_create("/foo/bar/baz", mode, &fi), 0);
+    fsop->printDirectory(4);
+    // the following three testcases will fail
+    printf("Failing cases\n");
+    EXPECT_TRUE(fsop->fischl_mkdir("foo/bar", mode) < 0);
+    EXPECT_TRUE(fsop->fischl_mkdir("/doesnt_exist/bar", mode) < 0);
+    EXPECT_TRUE(fsop->fischl_mkdir("/test/bar", mode) < 0);
+    EXPECT_TRUE(fsop->fischl_mkdir("/test", mode) < 0);
+    EXPECT_TRUE(fsop->fischl_mkdir("/foo/bar", mode) < 0);
+    EXPECT_TRUE(fsop->fischl_mkdir("/foo/bar/..", mode) < 0);
+}
+
+TEST(FileOperationTest, WriteTest) {
+    // write to files (TODO: fischl_write)
+    //get inode info from disk
+    char buffer[IO_BLOCK_SIZE] = {0};
+    INode_Data inode;
+    u_int64_t get_disk_inum;
+    struct fuse_file_info fi;
+    
+    //file test
+    printf("point 0\n");
+    get_disk_inum = fsop->disk_namei("/test");
+    printf("point 1\n");
+    fsop->fischl_open("/test", &fi);
+    EXPECT_EQ(fi.fh, get_disk_inum);
+    buffer[0] = '1';
+    fsop->fischl_write("/test", buffer, sizeof(buffer), 0, &fi);
+    printf("point 2\n");
+    //other file baz
+    get_disk_inum = fsop->disk_namei("/foo/bar/baz");
+    buffer[0] = '4';
+    fsop->fischl_open("/foo/bar/baz", &fi);
+    EXPECT_EQ(fi.fh, get_disk_inum);
+    fsop->fischl_write("/foo/bar/baz", buffer, sizeof(buffer), 3*IO_BLOCK_SIZE, &fi);
+    buffer[0] = '5';
+    fsop->fischl_write("/foo/bar/baz", buffer, sizeof(buffer), 101*IO_BLOCK_SIZE, &fi);
+}
+
+TEST(FileOperationTest, RamDiskTest) {
+    //use find_entry(specify certain files or directory)
+    FileNode* get_dir;
+    u_int64_t get_disk_inum;
+
+    get_dir = fischl_load_entry(fsop->root_node, "/test");//this is file
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success 
+    EXPECT_STREQ(get_dir->name, "test");
+    get_disk_inum = fsop->disk_namei("/test");
+    EXPECT_EQ(get_disk_inum, get_dir->inode_number);
+
+    get_dir = fischl_load_entry(fsop->root_node, "/foo/bar/baz");//this is file
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success 
+    EXPECT_STREQ(get_dir->name, "baz");
+    get_disk_inum = fsop->disk_namei("/foo/bar/baz");
+    EXPECT_EQ(get_disk_inum, get_dir->inode_number);
+
+    get_dir = fischl_load_entry(fsop->root_node, "/foo/bar/..");
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success 
+    EXPECT_STREQ(get_dir->name, "foo");
+    ASSERT_TRUE(get_dir->subdirectory != NULL);//secure it is directory
+    get_disk_inum = fsop->disk_namei("/foo/bar/..");
+    EXPECT_EQ(get_disk_inum, get_dir->inode_number);
+    fsop->printDirectory(get_disk_inum);
+
+    get_dir = fischl_load_entry(fsop->root_node, "/foo/bar/.");
+    EXPECT_TRUE(get_dir != NULL);//detect this should find success 
+    EXPECT_STREQ(get_dir->name, "bar");
+    ASSERT_TRUE(get_dir->subdirectory != NULL);//secure it is directory
+    get_disk_inum = fsop->disk_namei("/foo/bar/.");
+    EXPECT_EQ(get_disk_inum, get_dir->inode_number);
+    fsop->printDirectory(get_disk_inum);
+}
+
+
+TEST(FileOperationTest, ReadTest) {
+    // read files (TODO: fischl_read)
+    char read_buffer[IO_BLOCK_SIZE] = {0};
+    INode_Data inode;
+    u_int64_t get_file_inum;
+
+    //read test file
+    get_file_inum = fsop->namei("/test");
+    inode.inode_num = get_file_inum;
+    fs->inode_manager->load_inode(&inode);
+    //fsop->read_datablock(inode, 0, read_buffer);
+    //EXPECT_EQ(read_buffer[0], '1');
+
+    //read test file again with fischl_read API
+    struct fuse_file_info fi;
+    fsop->fischl_open("/test", &fi);
+    EXPECT_EQ(fi.fh, get_file_inum);
+    fsop->fischl_read("/test", read_buffer, sizeof(read_buffer), 0, &fi);
+    EXPECT_EQ(read_buffer[0], '1');
+
+    //read baz file
+    get_file_inum= fsop->namei("/foo/bar/baz");
+    // inode.inode_construct(get_file_inum, *H);
+    // fsop->read_datablock(inode, 3, read_buffer);
+    // EXPECT_EQ(read_buffer[0], '4');
+    // fsop->read_datablock(inode, 101, read_buffer);
+    // EXPECT_EQ(read_buffer[0], '5');
+
+    //read baz file again with fischl_read API
+    fsop->fischl_open("/foo/bar/baz", &fi);
+    EXPECT_EQ(fi.fh, get_file_inum);
+    fsop->fischl_read("/foo/bar/baz", read_buffer, sizeof(read_buffer), 3*IO_BLOCK_SIZE, &fi);
+    EXPECT_EQ(read_buffer[0], '4');
+    fsop->fischl_read("/foo/bar/baz", read_buffer, sizeof(read_buffer), 101*IO_BLOCK_SIZE, &fi);
+    EXPECT_EQ(read_buffer[0], '5');
+}
+
+TEST(FileOperationTest, PressureTest) {
+    mode_t mode;//set mode
+    mode = S_IRWXU | S_IRWXG | S_IRWXO;//future should test permission
+    EXPECT_EQ(fsop->fischl_mkdir("/pressure", mode), 0);
+    fsop->printDirectory(1);
+
+    for(int i=0;i<100;i++){
+        EXPECT_EQ(fsop->fischl_mkdir((prefix+std::to_string(i)).c_str(), mode), 0);
+    }
+    fsop->printDirectory(6);
+    for(int i=0;i<100;i++){
+        EXPECT_EQ(fsop->namei((prefix+std::to_string(i)).c_str()),fsop->disk_namei((prefix+std::to_string(i)).c_str()));
+    }
+}
+
+TEST(FileOperationTest, UnlinkTest) {
+    ssize_t file_pressure = fsop->namei("/pressure");
+    fsop->printDirectory(file_pressure);
+    for(int i=0;i<100;i+=2){
+        EXPECT_EQ(fsop->fischl_unlink((prefix+std::to_string(i)).c_str()), 0);
+    }
+    for(int i=0;i<4;i+=2){
+        EXPECT_EQ(fsop->namei((prefix+std::to_string(i)).c_str()), (u_int64_t)(-1));
+    }
+    printf("Finished Deallocating\n");
+    fsop->printDirectory(file_pressure);
+    std::string newprefix = "/pressure/New";
+    for(int i=0;i<100;i+=2){
+        EXPECT_EQ(fsop->fischl_mkdir((newprefix+std::to_string(i)).c_str(), 0), 0);
+    }
+    for(int i=0;i<100;i+=2){
+        u_int64_t inode_number = fsop->namei((newprefix+std::to_string(i)).c_str());
+        assert(inode_number>0);
+    }
+    printf("Finished Reallocating\n");
+    fsop->printDirectory(file_pressure);
+
+    // long filename test
+    std::string longfilename = std::string(255,'A');
+    EXPECT_EQ(fsop->fischl_mknod((std::string("/")+longfilename).c_str(),0,0),0);
+    u_int64_t filelong = fsop->namei((std::string("/")+longfilename).c_str());
+    printf("/AAA...AAA is inode %llu, it is a file\n", filelong);
+}
+
+
+int main(int argc, char **argv) {
+    srand(time(NULL)); // Seed the random number generator
+    const char* d = (argc < 2) ? "/dev/vdc" : argv[1];
+
+    setupTestDirectory(&mock_root);
+    H = new FakeRawDisk(21504);
+    fs = new Fs(H);
+    fs->format();
+    fsop = new FilesOperation(*H, fs);
+
+    ::testing::InitGoogleTest(&argc, argv);
+    int result = RUN_ALL_TESTS();
+
+    total_dir_num = 0;
+    total_file_num = 0;
+
+    traverseDirHierarchy(mock_root, 0);//mock_root
+    printf("Traverse Total: Dir %d, File %d\n",total_dir_num, total_file_num);
+    
+    // Cleanup
+    freeDirHierarchy(mock_root);//mock_root
+    printf("Free Total: Dir %d, File %d\n",total_free_dir, total_free_file);
+    
+    freeTree(fsop->root_node);
+    delete fsop; // First delete fsop which depends on H
+    delete H;
+
+    return result;
+}
+
+const char* generateRandomName(size_t length) {
+    const std::string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+    std::string randomString;
+
+    for (size_t i = 0; i < length; ++i) {
+        randomString += chars[rand() % chars.size()];
+    }
+
+    // Allocate memory and copy the string
+    char* name = new char[randomString.length() + 1];
+    strcpy(name, randomString.c_str());
+    return name;
+}
+
+// Recursive function to create directory hierarchy
+dir_test* createDirHierarchy(int level, int maxLevel) {
+    if (level > maxLevel) {
+        return nullptr;
+    }
+
+    dir_test* head = nullptr;
+    dir_test* current = nullptr;
+
+    for (int i = 0; i < 3; ++i) {
+        dir_test* newDir = new dir_test;
+        newDir->name = generateRandomName(6); // Generate a random name for the directory
+        newDir->inFile = nullptr; // Initialize file list to nullptr
+        newDir->subdir = createDirHierarchy(level + 1, maxLevel); // Recursively create subdirectories
+        newDir->next = nullptr;
+
+        // Create file list for this directory
+        file_test* fileHead = nullptr;
+        file_test* fileCurrent = nullptr;
+        for (int j = 0; j < 3; ++j) {
+            file_test* newFile = new file_test;
+            newFile->name = generateRandomName(6); // Generate a random name for the file
+            newFile->next = nullptr;
+
+            if (!fileHead) {
+                fileHead = newFile;
+            } else {
+                fileCurrent->next = newFile;
+            }
+            fileCurrent = newFile;
+        }
+        newDir->inFile = fileHead;
+
+        // Add the new directory to the list
+        if (!head) {
+            head = newDir;
+        } else {
+            current->next = newDir;
+        }
+        current = newDir;
+    }
+
+    return head;
+}
+
+// Setup function for the test directory
+void setupTestDirectory(dir_test** root) {
+    // Allocate memory for root
+    *root = new dir_test;
+    char* root_name = new char[2];
+    strcpy(root_name, "/");
+    (*root)->name = root_name; // use / as begin
+    (*root)->inFile = nullptr; // Initialize file list to nullptr
+    (*root)->subdir = createDirHierarchy(0, 1);
+    (*root)->next = nullptr;
+    file_test* fileHead = nullptr;
+    file_test* fileCurrent = nullptr;
+    for (int j = 0; j < 3; ++j) {
+        file_test* newFile = new file_test;
+        newFile->name = generateRandomName(6); // Generate a random name for the file
+        newFile->next = nullptr;
+
+        if (!fileHead) {
+            fileHead = newFile;
+        } else {
+            fileCurrent->next = newFile;
+        }
+        fileCurrent = newFile;
+    }
+    (*root)->inFile = fileHead;
+}
+
+// Function to free a list of files
+void freeFileList(file_test* fileList) {
+    while (fileList != nullptr) {
+        file_test* temp = fileList;
+        fileList = fileList->next;
+        total_free_file++;//for debug
+        delete[] temp->name; // Free the name string
+        delete temp; // Free the current file
+    }
+}
+
+// Recursive function to free the directory hierarchy
+void freeDirHierarchy(dir_test* dir) {
+    while (dir != nullptr) {
+        dir_test* temp = dir;
+        dir = dir->next;
+        total_free_dir++;//for debug
+        freeFileList(temp->inFile);  // Free the list of files in the directory
+        freeDirHierarchy(temp->subdir); // Recursively free subdirectories
+        delete[] temp->name; // Free the name string
+        delete temp; // Free the current directory
+    }
+}
+
+// Function to print the list of files in a directory
+void printFileList(const file_test* fileList) {
+    const file_test* currentFile = fileList;
+    while (currentFile != nullptr) {
+        // std::cout << "  File: " << currentFile->name << std::endl;
+        total_file_num++;
+        currentFile = currentFile->next;
+    }
+}
+
+void traverseDirHierarchy(const dir_test* dir, int depth = 0) {
+    while (dir != nullptr) {
+        // std::cout << "Depth " << depth << ", Directory: " << dir->name << std::endl;
+        total_dir_num++;//for debug
+
+        // Print files in this directory
+        printFileList(dir->inFile);
+        // Recursively traverse subdirectories
+        traverseDirHierarchy(dir->subdir, depth + 1);
+
+        // Go to the next directory at the same level
+        dir = dir->next;
+    }
+}