FilesystemTEMP

/*

  MyFS: a tiny file-system written for educational purposes

  MyFS is

  Copyright 2018-20 by

  University of Alaska Anchorage, College of Engineering.

  Contributors: Christoph Lauter
                ... and
                ...

  and based on

  FUSE: Filesystem in Userspace
  Copyright (C) 2001-2007  Miklos Szeredi <miklos@szeredi.hu>

  This program can be distributed under the terms of the GNU GPL.
  See the file COPYING.

  gcc -Wall myfs.c implementation.c `pkg-config fuse --cflags --libs` -o myfs

*/

#include <errno.h>
#include <fcntl.h>
#include <fuse.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/statvfs.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

#ifdef DEBUG
#   include <assert.h>
#endif


/* The filesystem you implement must support all the 13 operations
   stubbed out below. There need not be support for access rights,
   links, symbolic links. There needs to be support for access and
   modification times and information for statfs.

   The filesystem must run in memory, using the memory of size
   fssize pointed to by fsptr. The memory comes from mmap and
   is backed with a file if a backup-file is indicated. When
   the filesystem is unmounted, the memory is written back to
   that backup-file. When the filesystem is mounted again from
   the backup-file, the same memory appears at the newly mapped
   in virtual address. The filesystem datastructures hence must not
   store any pointer directly to the memory pointed to by fsptr; it
   must rather store offsets from the beginning of the memory region.

   When a filesystem is mounted for the first time, the whole memory
   region of size fssize pointed to by fsptr reads as zero-bytes. When
   a backup-file is used and the filesystem is mounted again, certain
   parts of the memory, which have previously been written, may read
   as non-zero bytes. The size of the memory region is at least 2048
   bytes.

   CAUTION:

   * You MUST NOT use any global variables in your program for reasons
   due to the way FUSE is designed.

   You can find ways to store a structure containing all "global" data
   at the start of the memory region representing the filesystem.

   * You MUST NOT store (the value of) pointers into the memory region
   that represents the filesystem. Pointers are virtual memory
   addresses and these addresses are ephemeral. Everything will seem
   okay UNTIL you remount the filesystem again.

   You may store offsets/indices (of type size_t) into the
   filesystem. These offsets/indices are like pointers: instead of
   storing the pointer, you store how far it is away from the start of
   the memory region. You may want to define a type for your offsets
   and to write two functions that can convert from pointers to
   offsets and vice versa.

   * You may use any function out of libc for your filesystem,
   including (but not limited to) malloc, calloc, free, strdup,
   strlen, strncpy, strchr, strrchr, memset, memcpy. However, your
   filesystem MUST NOT depend on memory outside of the filesystem
   memory region. Only this part of the virtual memory address space
   gets saved into the backup-file. As a matter of course, your FUSE
   process, which implements the filesystem, MUST NOT leak memory: be
   careful in particular not to leak tiny amounts of memory that
   accumulate over time. In a working setup, a FUSE process is
   supposed to run for a long time!

   It is possible to check for memory leaks by running the FUSE
   process inside valgrind:

   valgrind --leak-check=full ./myfs --backupfile=test.myfs ~/fuse-mnt/ -f

   However, the analysis of the leak indications displayed by valgrind
   is difficult as libfuse contains some small memory leaks (which do
   not accumulate over time). We cannot (easily) fix these memory
   leaks inside libfuse.

   * Avoid putting debug messages into the code. You may use fprintf
   for debugging purposes but they should all go away in the final
   version of the code. Using gdb is more professional, though.

   * You MUST NOT fail with exit(1) in case of an error. All the
   functions you have to implement have ways to indicate failure
   cases. Use these, mapping your internal errors intelligently onto
   the POSIX error conditions.

   * And of course: your code MUST NOT SEGFAULT!

   It is reasonable to proceed in the following order:

   (1)   Design and implement a mechanism that initializes a filesystem
         whenever the memory space is fresh. That mechanism can be
         implemented in the form of a filesystem handle into which the
         filesystem raw memory pointer and sizes are translated.
         Check that the filesystem does not get reinitialized at mount
         time if you initialized it once and unmounted it but that all
         pieces of information (in the handle) get read back correctly
         from the backup-file.

   (2)   Design and implement functions to find and allocate free memory
         regions inside the filesystem memory space. There need to be
         functions to free these regions again, too. Any "global" variable
         goes into the handle structure the mechanism designed at step (1)
         provides.

   (3)   Carefully design a data structure able to represent all the
         pieces of information that are needed for files and
         (sub-)directories.  You need to store the location of the
         root directory in a "global" variable that, again, goes into the
         handle designed at step (1).

   (4)   Write __myfs_getattr_implem and debug it thoroughly, as best as
         you can with a filesystem that is reduced to one
         function. Writing this function will make you write helper
         functions to traverse paths, following the appropriate
         subdirectories inside the file system. Strive for modularity for
         these filesystem traversal functions.

   (5)   Design and implement __myfs_readdir_implem. You cannot test it
         besides by listing your root directory with ls -la and looking
         at the date of last access/modification of the directory (.).
         Be sure to understand the signature of that function and use
         caution not to provoke segfaults nor to leak memory.

   (6)   Design and implement __myfs_mknod_implem. You can now touch files
         with

         touch foo

         and check that they start to exist (with the appropriate
         access/modification times) with ls -la.

   (7)   Design and implement __myfs_mkdir_implem. Test as above.

   (8)   Design and implement __myfs_truncate_implem. You can now
         create files filled with zeros:

         truncate -s 1024 foo

   (9)   Design and implement __myfs_statfs_implem. Test by running
         df before and after the truncation of a file to various lengths.
         The free "disk" space must change accordingly.

   (10)  Design, implement and test __myfs_utimens_implem. You can now
         touch files at different dates (in the past, in the future).

   (11)  Design and implement __myfs_open_implem. The function can
         only be tested once __myfs_read_implem and __myfs_write_implem are
         implemented.

   (12)  Design, implement and test __myfs_read_implem and
         __myfs_write_implem. You can now write to files and read the data
         back:

         echo "Hello world" > foo
         echo "Hallo ihr da" >> foo
         cat foo

         Be sure to test the case when you unmount and remount the
         filesystem: the files must still be there, contain the same
         information and have the same access and/or modification
         times.

   (13)  Design, implement and test __myfs_unlink_implem. You can now
         remove files.

   (14)  Design, implement and test __myfs_unlink_implem. You can now
         remove directories.

   (15)  Design, implement and test __myfs_rename_implem. This function
         is extremely complicated to implement. Be sure to cover all
         cases that are documented in man 2 rename. The case when the
         new path exists already is really hard to implement. Be sure to
         never leave the filessystem in a bad state! Test thoroughly
         using mv on (filled and empty) directories and files onto
         inexistant and already existing directories and files.

   (16)  Design, implement and test any function that your instructor
         might have left out from this list. There are 13 functions
         __myfs_XXX_implem you have to write.

   (17)  Go over all functions again, testing them one-by-one, trying
         to exercise all special conditions (error conditions): set
         breakpoints in gdb and use a sequence of bash commands inside
         your mounted filesystem to trigger these special cases. Be
         sure to cover all funny cases that arise when the filesystem
         is full but files are supposed to get written to or truncated
         to longer length. There must not be any segfault; the user
         space program using your filesystem just has to report an
         error. Also be sure to unmount and remount your filesystem,
         in order to be sure that it contents do not change by
         unmounting and remounting. Try to mount two of your
         filesystems at different places and copy and move (rename!)
         (heavy) files (your favorite movie or song, an image of a cat
         etc.) from one mount-point to the other. None of the two FUSE
         processes must provoke errors. Find ways to test the case
         when files have holes as the process that wrote them seeked
         beyond the end of the file several times. Your filesystem must
         support these operations at least by making the holes explicit
         zeros (use dd to test this aspect).

   (18)  Run some heavy testing: copy your favorite movie into your
         filesystem and try to watch it out of the filesystem.

*/

/* Helper types */
typedef size_t offset_t;
typedef uint32_t inodenum_t; // 2 billion files seems enough?
typedef nlink_t link_t;     // For hardlinks and entries in directory.

#ifndef MAGIC_NUM
#   define MAGIC_NUM (0xf54c1a55 /*fs for class*/)
#endif
#ifndef CHAR_LIMIT_INCLUDE_NULL
#   define CHAR_LIMIT_INCLUDE_NULL (256)
#endif
#ifndef BLOCKSIZE
#   define BLOCKSIZE (4096)
#endif
#ifndef MINIMUM_INODE_COUNT
#   define MINIMUM_INODE_COUNT                                                  \
        ((BLOCKSIZE - START_SIZE)                                                  \
         / sizeof(struct inode_t) /* For small filesystems */)
#endif
#ifndef SIZE_PER_INODE
#   define SIZE_PER_INODE (16384 /* For small filesystems */)
#endif
#ifndef INODE_INLINE_COUNT
#   define INODE_INLINE_COUNT                                                   \
        (8 /* Number of block_t to include inline before ptr_block */)
#endif

// TODO: move most of these types to different ones

struct start_t {
    uint32_t magic;
    uint32_t version;  //!< Version, in case we change it.
    offset_t size;     //!< Space in the filesystem
    inodenum_t inodes; //!< Number of inodes
    offset_t
      firstfree; //!< Offset from beginning of the linked list of free space

    unsigned clean_umount : 1; //!< Did we unmount cleanly?
};

struct block_t {
    offset_t location; //!< Offset from start to an array of struct direntry_t
    offset_t num;      //!< Number of adjacent blocks that have been combined
    union {
        struct {
            offset_t byteindex; //!< Index of first entry in block, byte
            link_t bytecount;   //!< Number of bytes in this block.
        };
        struct {
            link_t dirindex; //!< Index of first entry in block, directory entries
            link_t dircount; //!< Number of directory entries in this block.
        };
    };

    unsigned sparse : 1;
};

#define PTR_PER_PTRBLOCK                                                       \
    ((BLOCKSIZE - sizeof(offset_t)) / sizeof(struct block_t))
struct ptrblock_t {
    struct block_t blocks[PTR_PER_PTRBLOCK];
    offset_t next;
};

struct direntry_t {
    char name[CHAR_LIMIT_INCLUDE_NULL];
    inodenum_t num; //!< inode number of file
};

struct inode_t {
    union {
        offset_t size;  //!< How big is the file in bytes
        link_t entries; //!< Number of entries in this directory
    };
    link_t links; //!< Number of hard links to this file

    struct timespec atime;
    struct timespec mtime;

    uid_t uid;
    gid_t gid;
    mode_t mode; //!< May be tested for is directory with S_ISDIR().

    struct block_t block[INODE_INLINE_COUNT];
    offset_t ptr_block;

    unsigned isfree : 1; //!< 1 indicates inode is unused
};

struct freespace_t {
    offset_t
      prev; //!< How far from the previous. Not absolute. If 0, none preceed.
    offset_t next; //!< How far to the next. Not absolute. If 0, none follow.

    offset_t freeblocks; //!< Number of blocks free
};

// Why? Prevents unaligned load/store errors if say struct start_t is
// aligned to a 2-byte boundary and we try to load a 4-byte item after.
#define START_SIZE                                                             \
    ((sizeof(struct start_t) > sizeof(struct inode_t)) ? sizeof(struct start_t)  \
                                                       : sizeof(struct inode_t))
#define INODE_T_ZERO(start) ((struct inode_t *)((void *)start + START_SIZE))
#define MAX_ENTRIES_IN_DIRENTRY(direntry)                                      \
    ((direntry).num * BLOCKSIZE / sizeof(struct direntry_t))

/* End of helper types */

/* Helper functions */

//! Gets num free blocks, starting from the end, and marks it used.
//! If there is not num blocks available, then will allocate as many
//! as possible.
//! Sets only block->sparse = 0, block->num, block->location
//! Returns 0 on success, -1 on failure
int getblock(struct block_t *block, offset_t request, struct start_t *start,
             int *errnoptr) {
    if (start->firstfree == 0) {
        *errnoptr = ENOSPC;
        return -1;
    }
    struct freespace_t *ptr = (void *)start + start->firstfree;
    struct freespace_t *largest = ptr;

    //Continues until a big enough one is found, or there's no more in the list
    while (1) {
        if (ptr->freeblocks >= request) {
            largest = ptr;
            break;
        }
        else if (ptr->freeblocks > largest->freeblocks) {
            largest = ptr;
        }
        if (ptr->next == 0) {
            break;
        }
        ptr = (void *)ptr + ptr->next;
    }

    ptr = largest; // Whoops, used the wrong one. And ptr is easier to type.
    // Wow, this is a really bad mess of if statements.
    // Needs to set the previous and next correctly,
    // handling what happens at the beginning/end.
    if (ptr->freeblocks == 0) {
        *errnoptr = ENOSPC;
        return -1;
    }

    block->sparse = 0;
    block->location = (void *)ptr - (void *)start;

    //If we need to create a next ptr
    if (ptr->freeblocks > request) {
        block->num = request;

        offset_t nextblockoffset = (BLOCKSIZE * request);
        ((struct freespace_t *)((void *)ptr + nextblockoffset))->next =
          (ptr->next == 0) ? 0 : (ptr->next - nextblockoffset);
        ((struct freespace_t *)((void *)ptr + nextblockoffset))->freeblocks =
            ptr->freeblocks - request;
        ptr->next = nextblockoffset;
        //All other attributes of the next are set in cases following
    }
    // We found a huge block
    else {
        block->num = ptr->freeblocks;
        // Need to create next ptr
    }

    //Four cases: prev exists/doesn't and next exists/doesn't
    if (ptr->prev == 0) {
        if (ptr->next == 0) {
            start->firstfree = 0;
            //Nothing following to set
        }
        else {
            start->firstfree = ((void *)ptr - (void *)start + ptr->next);
            ((struct freespace_t *)((void *)ptr - ptr->next))->next = 0;
        }
    }
    else {
        if (ptr->next == 0) {
            ((struct freespace_t *)((void *)ptr - ptr->prev))->next = 0;
            // Nothing following to set
        }
        else {
            ((struct freespace_t *)((void *)ptr + ptr->next))->prev += ptr->prev;
            ((struct freespace_t *)((void *)ptr - ptr->prev))->next += ptr->next;
        }
    }
    return 0;
}

//! Gets a free inode, starting from 0, and marks it used.
//! Returns 0 on success, -1 on failure
int getinode(inodenum_t *inode, struct start_t *start, int *errnoptr) {
    // find first free inode
    struct inode_t *inodeptr = INODE_T_ZERO(start);
    for (inodenum_t i = 0; i < start->inodes; i++, inodeptr++) {
        if (inodeptr->isfree == 1) {
            // TODO decide what gets set in getinode
            inodeptr->isfree = 0;
            for (size_t i = 0; i < INODE_INLINE_COUNT; i++) {
                inodeptr->block[i] = (struct block_t){.location = 0, .num = 0};
            }
            inodeptr->ptr_block = 0;
            inodeptr->size = 0;
            inodeptr->links = 0;
            *inode = i;
            return 0;
        }
    }
    *errnoptr = ENOSPC;
    return -1;
}

//! Marks count number of blocks as free from end of block, maximum of
//! block->num. Pass 0 for count to free whole block.
//! Caller should set block->num and related appropriately after.
void freeblock(struct block_t *block, offset_t count, struct start_t *start) {
    if (count == 0 || count > block->num) {
        count = block->num;
    }

    offset_t pos = start->firstfree;
    //! Location to be added as freespace_t position
    offset_t freelocation = block->location + (block->num - count) * BLOCKSIZE;

    //Case where we have an earlier block than the already free blocks
    if (pos < freelocation) {
        start->firstfree = freelocation;
        ((struct freespace_t *)(start->firstfree))->freeblocks = block->num;
        ((struct freespace_t *)(start->firstfree))->prev = 0;
        ((struct freespace_t *)(start->firstfree))->next = pos;
        if (pos != 0) {
            ((struct freespace_t *)((void *)start + pos))->prev = freelocation;
        }
        return;
    }

    offset_t next = ((struct freespace_t *)((void *)start + pos))->next;
    while (!(next == 0 || next > freelocation)) {
        // While there is next pointers and we haven't gone past the correct point
        pos = next;
        next = ((struct freespace_t *)((void *)start + pos))->next;
    }
    // Pos will be the one *BEFORE* freelocation

    //Combine blocks if possible
    if (freelocation + count * BLOCKSIZE == next) {
        // Combine with next
        //! newnext = block after next
        offset_t newnext = ((struct freespace_t *)((void *)start + next))->next;
        ((struct freespace_t *)((void *)start + pos))->next = freelocation;
        ((struct freespace_t *)((void *)start + freelocation))->prev = pos;
        ((struct freespace_t *)((void *)start + freelocation))->freeblocks =
          ((struct freespace_t *)((void *)start + next))->freeblocks + count;
        ((struct freespace_t *)((void *)start + freelocation))->next = newnext;
        if (newnext != 0) {
            //Set next->next->prev to freelocation
            ((struct freespace_t *)((void *)start + newnext))->prev = freelocation;
        }
        next = newnext;
    }
    else {
        //Create normal block
        ((struct freespace_t *)((void *)start + pos))->next = freelocation;
        ((struct freespace_t *)((void *)start + freelocation))->prev = pos;
        ((struct freespace_t *)((void *)start + freelocation))->next = next;
        ((struct freespace_t *)((void *)start + freelocation))->freeblocks = count;
        if (next != 0) {
            ((struct freespace_t *)((void *)start + next))->prev = freelocation;
        }
    }

    // Is pos and freelocation combinable?
    if (pos + ((struct freespace_t *)((void *)start + pos))->freeblocks
        == freelocation) {
        //They are, merge them.
        ((struct freespace_t *)((void *)start + pos))->freeblocks +=
          ((struct freespace_t *)((void *)start + freelocation))->freeblocks;
        ((struct freespace_t *)((void *)start + pos))->next = next;
        if (next != 0) {
            ((struct freespace_t *)((void *)start + next))->prev = pos;
        }
    }
}

//! Gets a new block, and blanks it for use as a ptrblock.
//! Creates one block inside it, of requested size using getblock.
//! Will fail if call to getblock fails.
//! Caller must set all members of ptrblock[0] appropriately, except for
//! those set when calling getblock().
//! Returns 0 on success, -1 on failure
int getptrblock(offset_t *ptrblock, offset_t request, struct start_t *start,
                int *errnoptr) {
    struct block_t new;
    if (getblock(&new, 1, start, errnoptr) == -1) {
        // Haven't started moving anything, so just fail.
        return -1;
    }
    struct ptrblock_t *newptrblock;
    newptrblock = (struct ptrblock_t *)((void *)start + new.location);
    if (getblock(newptrblock->blocks, 1, start, errnoptr) == -1) {
        // Need to free allocated block
        freeblock(&new, 1, start);
        return -1;
    }

    //Blank the remaining ones in the ptrblock
    for (size_t i = 1; i < PTR_PER_PTRBLOCK; i++) {
        newptrblock->blocks[i] = (struct block_t){};
    }
    newptrblock->next = 0;

    *ptrblock = new.location;
    return 0;
}

//! Marks an inode as free and all its data blocks.
void freeinode(inodenum_t inode, struct start_t *start) {
    // TODO free all data blocks
    (INODE_T_ZERO(start))[inode].isfree = 1;
    //TODO replace with a linked list of free inodes?
}

//! Should only be used by function entry_helper.
//! If found, places position in block in *found,
//! if not found place proceding position.
//! Returns -1 if not present, 0 if found, 1 if may be in proceeding
static inline int entry_searchblocks(const char *name,
                                     const struct direntry_t *block,
                                     const link_t entries, link_t *found) {
    if (entries == 0) {
        *found = 0;
        return -1;
    }
    int present = strcmp(block[entries - 1].name, name);
    // Will be < 0 if not in this block.
    if (present < 0) {
        return 1;
    }
    else if (present == 0) {
        //Well, wasn't that easy?
        *found = entries - 1;
        return 0;
    }

    //So, we know it's got to be in this block, at least.
    //Binary search!
    link_t start = 0;         //!< Points to start
    link_t end = entries - 1; //!< Points to after end
    link_t mid;
    while (start < end) {
        mid = (start + end) / 2;
        present = strcmp(block[mid].name, name);

        if (present < 0) {
            start = mid + 1;
        }
        else if (present > 0) {
            end = mid;
        }
        else /* present == 0 */ {
            *found = mid;
            return 0;
        }
    }
    // Nope, wasn't found! But start points to the proceeding
    *found = start;
    return -1;
}

//! A helper function, returns in entrynum the index of the requested
//! entry or the proceeding if not present.
//! entrynum might refer to entries + 1, if all the entries preceeded the name.
//! WARNING: Will not check if inode is even a directory!
//! Returns 0 if found, -1 if not found.
int entry_helper(const char *name, const inodenum_t directory,
                 offset_t *entrynum, const struct start_t *start) {
    struct inode_t *inode = INODE_T_ZERO(start) + directory;
    link_t remaining = inode->entries;

    offset_t blocknumber = 0; //!< Which block_t are we in?
    for (offset_t i = 0; i < INODE_INLINE_COUNT; blocknumber = ++i) {
        struct direntry_t *ptr = ((void *)start + inode->block[i].location);

        link_t found;
        if (remaining <= inode->block[i].dircount) {
            // If it's not in this block, there's no more blocks to search
            int ret = entry_searchblocks(name, ptr, remaining, &found);
            if (ret == 1) {
                *entrynum = inode->block[i].dirindex + remaining;
            }
            else {
                *entrynum = inode->block[i].dirindex + found;
            }
            return ret ? -1 : 0;
        }
        int ret = entry_searchblocks(name, ptr, inode->block[i].dircount, &found);
        if (ret == -1) {
            *entrynum = inode->block[i].dirindex + found;
            return -1;
        }
        if (ret == 0) {
            *entrynum = inode->block[i].dirindex + found;
            return 0;
        }
        remaining -= inode->block[i].dircount;
    }

    // Loop through pointer blocks
    struct ptrblock_t *ptrblock = (void *)start + inode->ptr_block;
    while (1) {
        for (offset_t i = 0; i < INODE_INLINE_COUNT; i++, blocknumber++) {
            struct direntry_t *ptr = ((void *)start + ptrblock->blocks[i].location);
            link_t maxentries = MAX_ENTRIES_IN_DIRENTRY(ptrblock->blocks[i]);
            link_t found;
            if (remaining <= maxentries) {
                // If it's not in this block, there's no more blocks to search
                int ret = entry_searchblocks(name, ptr, remaining, &found);
                if (ret == 1) {
                    *entrynum = inode->block[i].dirindex + remaining;
                }
                else {
                    *entrynum = inode->block[i].dirindex + found;
                }
                return ret ? -1 : 0;
            }
            int ret = entry_searchblocks(name, ptr, maxentries, &found);
            if (ret == -1) {
                *entrynum = inode->block[i].dirindex + found;
                return -1;
            }
            if (ret == 0) {
                *entrynum = inode->block[i].dirindex + found;
                return 0;
            }
            remaining -= maxentries;
        }

        //If we made it this far, there's another pointer block.
        ptrblock = (void *)start + ptrblock->next;
    }
}


//! Finds the end, and shuffles everything foward by one.
//! Should only be called from function addentry.
//! There is no ptrblock after these ones if ptrblock_off is 0, but
//! *ptrblock_off may be changed if a new ptrblock needed to be created.
//! stationaryentries should be the number of entries that need to remain.
//! blockcount is the number of blocks in array blocks[].
//! *insert should refer to the block to be inserted after stationaryentries.
//! Returns 0 on success, -1 on failure
static int entry_shuffleforward(const offset_t stationaryentries,
                                struct direntry_t *insert,
                                struct block_t *blocks,
                                const offset_t blockcount,
                                offset_t *ptrblock_off, struct start_t *start,
                                int *errnoptr) {
    offset_t to = 0; //!< When shuffling, this many blocks. For if some are empty.
    offset_t entries = 0; //!< Number of entries in blocks[] combined
    // Count the number of entries in blocks
    for (offset_t i = 0; i < blockcount; i++) {
        to++; //If one of these is completely empty, it gets filled in later.
        entries += blocks[i].dircount;
        // #ifdef DEBUG
        // assert((blocks[i].num == 0 && blocks[i].sparse == 0));
        // #endif
        if (blocks[i].dircount < MAX_ENTRIES_IN_DIRENTRY(blocks[i])
            || (blocks[i].num == 0)) {
            //There's no more.
            break;
        }
    }

    offset_t remaining; //!< Remaining to not shuffle
    //Overflow detection
    remaining =
      (entries < stationaryentries) ? entries : (entries - stationaryentries);

    //! If the last block with things in it is full
    int lastisfull =
      (blocks[to - 1].dircount == MAX_ENTRIES_IN_DIRENTRY(blocks[to - 1]));
    // Do we need to recurse?
    if (*ptrblock_off != 0
        || (to == blockcount && lastisfull && blocks[to - 1].dircount != 0)) {
        //Do we need to allocate a new block?
        struct ptrblock_t *next; //!< Next ptrblock
        if (*ptrblock_off == 0) {
            if (getptrblock(ptrblock_off, 1, start, errnoptr) == -1) {
                return -1;
            }
            //Since allocating succeeded, set new things all correctly
            next = (void *)start + *ptrblock_off;
            next->blocks[0].dirindex =
              blocks[to - 1].dirindex + blocks[to - 1].dircount;
        }
        else {
            next = (void *)start + *ptrblock_off;
        }

        // Do we need to insert the last block or *insert?
        // Could only ever fail at allocating a block, before any kind of
        // shuffling occured, so don't need to worry about undoing what we did.
        // and if we just allocated a block, we know we don't need to allocate
        // a new one
        if (remaining != 0) {
            struct direntry_t *toinsert;
            struct direntry_t *lastblock; //!< Last one in array blocks[]
            lastblock = (void *)start + blocks[blockcount - 1].location;
            toinsert = lastblock + blocks[blockcount - 1].dircount - 1;
            if (entry_shuffleforward(remaining, toinsert, next->blocks,
                                     PTR_PER_PTRBLOCK, &(next->next), start, errnoptr)
                == -1) {
                return -1;
            }
        }
        else {
            return entry_shuffleforward(remaining, insert, next->blocks,
                                        PTR_PER_PTRBLOCK, &(next->next), start,
                                        errnoptr);
            // Don't need to shuffle this one if there's nothing remaining to shuffle.
            // So, return.
        }
    }
    // Do we need to add another block?
    else if (lastisfull && blocks[to - 1].location == 0) {
        // Add a new one at to
        if (getblock(&(blocks[to - 1]), 1, start, errnoptr) == -1) {
            return -1;
        }
        blocks[to - 1].dircount = 1;
        blocks[to - 1].dirindex = blocks[to - 2].dirindex + blocks[to - 2].dircount;


        struct direntry_t *to_set = ((void *)start + blocks[to - 1].location);
        *to_set =
          ((struct direntry_t *)((void *)start
                                 + blocks[to - 1]
                                     .location))[blocks[to - 1].dircount - 1];
        //Don't need to copy out the direntry, it will be done later.
    }
    // The last one was not full
    else {
        blocks[to - 1].dircount += 1;
    }
    // Do the shuffle
    // Sounds like the code is dancing
    struct direntry_t *replace = NULL; //!< When shifting out, move it here.
    offset_t i = to;

    // If remaining == 0 before something is assigned, then use *insert instead.
    // Decrement remaining after something is assigned.
    while (i) {
        i--; //Runs for i = 0 too
        struct direntry_t *direntries = (void *)start + blocks[i].location;
        link_t j = blocks[i].dircount - 1;
        if (replace != NULL) {
            if (remaining-- == 0) {
                *replace = *insert;
                return 0;
            }
            *replace = direntries[j];
        }
        while (j) {
            if (remaining-- == 0) {
                direntries[j] = *insert;
                return 0;
            }
            direntries[j] = direntries[j - 1];
            j--;
        }
        replace = direntries;
    }

    //The only way we could get here is if we need to replace the very first
    *replace = *insert;

    return 0;
}

//! Shuffles all entries in a directory back by one, effectively removing
//! the item at index stationaryentries.
//! Should only be called from function dropentry.
//! There is no ptrblock after these ones if ptrblock_off is 0, but
//! *ptrblock_off may be changed if there was no need for it anymore.
//! blockcount is the number of blocks in array blocks[].
//! *shuffleinto should be NULL by default, unless you want to save the item?
//! at index stationaryentries.
static void
entry_shufflebackward(offset_t stationaryentries, struct block_t *blocks,
                      const offset_t blockcount, offset_t *ptrblock_off,
                      struct direntry_t *shuffleinto, struct start_t *start) {
    __label__ doshuffle;
    offset_t i = 0, j;
    struct direntry_t *entries;
    for (; i < blockcount; i++) {
        for (j = 0; j < blocks[i].dircount; j++) {
            if (stationaryentries == 0) {
                entries = (void *)start + blocks[i].location;
                goto doshuffle;
            }
            else {
                stationaryentries--;
            }
        }
    }

    // Do the same thing, but shuffling things.
    for (; i < blockcount; i++) {
        entries = (void *)start + blocks[i].location;
        for (j = 0; j < blocks[i].dircount; j++) {
        doshuffle:
            if (shuffleinto != NULL) {
                *shuffleinto =
                  ((struct direntry_t *)((void *)start + blocks[i].location))[j];
                shuffleinto = NULL;
            }
            else {
                *shuffleinto =
                  ((struct direntry_t *)((void *)start + blocks[i].location))[j];
            }
        }
        shuffleinto = &entries[j - 1];
    }

    // Do we need to keep going?
    if (*ptrblock_off != 0) {
        struct ptrblock_t *ptrblock = (void *)start + *ptrblock_off;
        entry_shufflebackward(stationaryentries, ptrblock->blocks, PTR_PER_PTRBLOCK,
                              &(ptrblock->next), shuffleinto, start);
    }
#ifdef DEBUG
    //Make sure this succeeded
    assert(stationaryentries == 0);
#endif
    return;
}

//! Adds a new entry to a directory, associating a file name with an inode.
//! Will fail if name already exists.
//! WARNING: Will not check if inode is even a directory!
//! Caller must set inode.links appropriately.
//! Returns 0 on success, -1 on failure.
int addentry(const char *name, inodenum_t parent, inodenum_t child,
             struct start_t *start, int *errnoptr) {
    offset_t entrynum; //!< index of where we need to add the entry
    int helper = entry_helper(name, parent, &entrynum, start);
    if (helper == 0) {
        *errnoptr = EEXIST;
        return -1;
    }
    struct direntry_t insert = {.num = child};
    strcpy(insert.name, name);

    struct inode_t *parentinode = INODE_T_ZERO(start) + parent;
    if (entry_shuffleforward(entrynum, &insert, parentinode->block,
                             INODE_INLINE_COUNT, &(parentinode->ptr_block), start,
                             errnoptr)
        == -1) {
        return -1;
    }
    parentinode->entries++;
    return 0;
}

//! Gets or sets the inode associated with a name in a given directory.
//! *entry is not set on failure.
//! WARNING: Will not check if inode is even a directory!
//! Fails only if name doesn't exist.
//! Returns 0 on success, -1 on failure.
int getsetentry(const char *name, inodenum_t directory, inodenum_t *entry,
                int set, struct start_t *start, int *errnoptr) {
    __label__ getinodeout;
    offset_t entrynum;
    int helper = entry_helper(name, directory, &entrynum, start);
    if (helper == -1) {
        *errnoptr = ENOENT;
        return -1;
    }

    // Go find the block entrynum is in
    struct inode_t *inode = INODE_T_ZERO(start) + directory;
    struct block_t *block = inode->block;
    for (offset_t i = 0; i < INODE_INLINE_COUNT; i++) {
        if (inode->block[i].dircount + inode->block[i].dirindex > entrynum) {
            //Found it
            block = inode->block + i;
            goto getinodeout;
        }
    }
    struct ptrblock_t *ptrblock = (void *)start + inode->ptr_block;
    while (1) {
        for (offset_t i = 0; i < INODE_INLINE_COUNT; i++) {
            if (inode->block[i].dircount + inode->block[i].dirindex > entrynum) {
                //Found it
                block = ptrblock->blocks + i;
                goto getinodeout;
            }
        }
        //If we made it this far, there's another pointer block.
#ifdef DEBUG
        assert(ptrblock->next != 0);
#endif
        ptrblock = (void *)start + ptrblock->next;
    }

getinodeout:;
    struct direntry_t *direntry0 = ((void *)start + block->location);
    if (set) {
        (direntry0 + (entrynum - block->dirindex))->num = *entry;
    }
    else {
        *entry = (direntry0 + (entrynum - block->dirindex))->num;
    }
    return 0;
}

//! Gets the inode associated with a name in a given directory.
//! *entry is not set on failure.
//! WARNING: Will not check if inode is even a directory!
//! Fails only if name doesn't exist.
//! Returns 0 on success, -1 on failure.
int getentry(const char *name, inodenum_t directory, inodenum_t *entry,
             struct start_t *start, int *errnoptr) {
    return getsetentry(name, directory, entry, 0, start, errnoptr);
}
//! Sets the inode associated with a name in a given directory.
//! *entry is not set on failure.
//! WARNING: Will not check if inode is even a directory!
//! Fails only if name doesn't exist.
//! Returns 0 on success, -1 on failure.
int setentry(const char *name, inodenum_t directory, inodenum_t *entry,
             struct start_t *start, int *errnoptr) {
    return getsetentry(name, directory, entry, 1, start, errnoptr);
}

//! Removes the given name from a directory, if it exists.
//! WARNING: Will not check if name is '.' or '..' or if the inode is even a
//! directory!
//! Caller must set inode.links appropriately.
//! Fails only if name doesn't exist.
//! Returns 0 on success, -1 on failure.
int dropentry(const char *name, inodenum_t directory, struct start_t *start,
              int *errnoptr) {
    offset_t entrynum; //!< index of where we need to remove the entry
    int helper = entry_helper(name, directory, &entrynum, start);
    if (helper == -1) {
        *errnoptr = ENOENT;
        return -1;
    }

    struct inode_t *parentinode = INODE_T_ZERO(start) + directory;
    entry_shufflebackward(entrynum, parentinode->block, INODE_INLINE_COUNT,
                          &(parentinode->ptr_block), NULL, start);
    parentinode->entries--;
    return 0;
}

//! Attempts to resolve the given path, and places the corrosponding
//! inode number into *inode_return.
//! Returns 0 on success, -1 on failure.
int resolvepath(const char *path, inodenum_t *inode_return,
                struct start_t *start, int *errnoptr) {
    inodenum_t inode;
#ifdef DEBUG
    assert((path[0] == '/'));
#else
    if (path[0] != '/') {
        //I don't know how to resolve this, fuse is meant to call with all absolute
        *errnoptr = ENOENT;
        return -1;
    }
#endif

    inode = 0;
    char name[CHAR_LIMIT_INCLUDE_NULL];

    size_t first = 1, len = 0;

    while (path[first] != '\0') {
        //Validate the path is in fact a directory
        if (!S_ISDIR(INODE_T_ZERO(start)[inode].mode)) {
            *errnoptr = ENOTDIR;
            return -1;
        }

        // Resolve all duplicate slashes
        if (path[first] == '/') {
            first++;
            continue;
        }
        const char *ptr = path + first;
        len = 0;
        while (ptr[len] != '/' && ptr[len] != '\0') {
            len++;
        }
        if (len >= CHAR_LIMIT_INCLUDE_NULL) {
            *errnoptr = ENOENT;
            return -1;
        }
        strncpy(name, ptr, len);
        name[len] = '\0';
        inodenum_t next;
        if (getentry(name, inode, &next, start, errnoptr) == -1) {
            return -1;
        }
        first += len;
        inode = next;
    }

    *inode_return = inode;
    return 0;
}

//! Pops the last directory off the top of the path in-place.
//! /etc/fstab would become /etc which would become /.
//! len is modified to have the new shorter length as well.
//! Len should not inlcude the null character and not be 0,
//! and path should not be null.
void popname(char *path, size_t *len) {
#ifdef DEBUG
    assert((path[0] == '/'));
#endif
    if (*len == 1) {
        //Can't shorten anymore
        return;
    }
    char *ptr = path + *len - 1;
    //Remove all trailing slashes
    while (*ptr == '/') {
        if (--(*len) == 1) {
            *ptr = '\0';
            return;
        }
        ptr--;
    }
    //Remove all charcters until the next slash
    while (*ptr != '/') {
        if (--(*len) == 1) {
            *ptr = '\0';
            return;
        }
        ptr--;
    }
    //Remove all trailing slashes
    while (*ptr == '/') {
        if (--(*len) == 1) {
            *ptr = '\0';
            return;
        }
        ptr--;
    }
    return;
}

//! Shortens the path, removing all . and .. as well as duplicate slashes.
//! Returned memory must be freed. Will do weird things if your path isn't
//! absolute. len may be NULL.
//! Returns NULL on error.
char *getshortname(const char *path, size_t *len) {
    char *newname;
    size_t oldlen = strlen(path), newlen = 0;
    newname = malloc(oldlen);
    if (newname == NULL) {
        return newname;
    }

    size_t i = 0;
    // When this loop reaches the beginning, we need to copy one slash then
    // a name.
    do {
        //Copy one slash and skip the rest
        if (newlen != 1) {
            // If we arrived at this position from a previous loop that ended with
            // newname being "/"
            newname[newlen++] = '/';
        }
        do {
            i++;
            if (path[i] == '\0') {
                break;
            }
        } while (path[i] == '/');
        //Copy the next part of the name out
        do {
            newname[newlen++] = path[i++];
        } while (path[i] != '\0');
        //! Did we just copy "." or ".."?
        if (path[newlen - 1] == '.') {
            if (path[newlen - 2] == '/') {
                //newlen is at least 2, don't need to check here.
                popname(newname, &newlen);
            }
            else if (newlen >= 3 && path[newlen - 2] == '.'
                     && path[newlen - 3] == '/') {
                popname(newname, &newlen);
                popname(newname, &newlen);
            }
        }
    } while (path[i] != '\0');

    newname[newlen] = '\0';
    if (len != NULL) {
        *len = newlen;
    }
    return newname;
}

//! Creates a directory. Links already set to 1. Inode returned in inodenum if
//! call succeeded. Uses the lowest inode it can.
//! WARNING: Does not check if parent is actually a directory!
//! uid/gid/mode must be set by caller.
//! Returns 0 on success, -1 on failure.
int createdir(inodenum_t *child_return, struct start_t *start,
              inodenum_t parent, int *errnoptr) {
    if (getinode(child_return, start, errnoptr) == -1) {
        return -1;
    }

    struct block_t newblock;
    if (getblock(&newblock, 1, start, errnoptr) == -1) {
        freeinode(*child_return, start);
        return -1;
    }
    struct inode_t *inode = INODE_T_ZERO(start) + *child_return;
    inode->entries = 0;
    inode->block[0] = newblock;
    inode->block[0].dircount = 0;
    inode->block[0].dirindex = 0;

    if (addentry(".", *child_return, *child_return, start, errnoptr) == -1
        || addentry("..", parent, *child_return, start, errnoptr) == -1) {
        freeinode(*child_return, start);
        return -1;
    }

    inode->links = 1;
    clock_gettime(CLOCK_REALTIME, &inode->atime);
    inode->mtime = inode->atime;
    return 0;
}


//! Creates the filesystem, or does nothing if already created.
//! Returns 0 on success, -1 on failure
int createfs(void *fsptr, size_t fssize, int *errnoptr) {
    struct start_t *start = (struct start_t *)fsptr;
    if (start->magic == MAGIC_NUM) {
        return 0;
    }

    start->inodes = fssize / SIZE_PER_INODE;
    if (start->inodes < MINIMUM_INODE_COUNT) {
        // Ensure we have inodes, fills the whole first block.
        start->inodes = MINIMUM_INODE_COUNT;
        start->firstfree = BLOCKSIZE;
    }
    else {
        // How many blocks are used by inodes, cieling division
        offset_t blocks =
          (START_SIZE + sizeof(struct inode_t) * start->inodes + BLOCKSIZE - 1)
          / BLOCKSIZE;
        start->firstfree = blocks * BLOCKSIZE;
        //Set inode count to as many as can fill that space.
        start->inodes =
          ((blocks * BLOCKSIZE) - START_SIZE) / sizeof(struct inode_t);
    }

    // Mark all inodes as free
    struct inode_t *inode = INODE_T_ZERO(start);
    for (inodenum_t i = 0; i < start->inodes; i++, inode++) {
        inode->isfree = 1;
    }

    // Really silly way to ensure there's an integer number of blocks
    // likely optimized to shift right and shift left
    start->size = fssize / BLOCKSIZE * BLOCKSIZE;

    // Add linked list of free space
    struct freespace_t *firstfree =
      (struct freespace_t *)((void *)start + start->firstfree);
    firstfree->next = 0;
    firstfree->prev = 0;
    firstfree->freeblocks = (start->size - start->firstfree) / BLOCKSIZE;

    // Create root directory. Guarenteed to use inode 0, since there's no
    // inodes used yet.
    inodenum_t created;
    int err = createdir(&created, start, 0, errnoptr);
    if (err == -1) {
        return err;
    }
    struct inode_t *root = INODE_T_ZERO(start);
    root->gid = getgid();
    root->uid = getuid();
    root->mode = S_IFDIR | 0755;
    clock_gettime(CLOCK_REALTIME, &(root->atime));
    root->mtime = root->atime;
    start->magic = MAGIC_NUM;
    return 0;
}

//! Gets parent and child from path. Both permitted to not exist.
//! parent is allocated large enough to hold parent + "/" + child.
//! Caller must free both.
//! Ensures child is less than CHAR_LIMIT_INCLUDE_NULL.
//! Returns 0 on success, -1 on failure.
int getparentchild(const char *path, char **parentpath_return,
                   char **childname_return, struct start_t *start,
                   int *errnoptr) {
    size_t parentlen, childlen;
    if (path[0] != '/') {
        *errnoptr = ENOENT;
        return -1;
    }
    char *parentpath = getshortname(path, &parentlen), *childname;
    if (parentpath == NULL) {
        *errnoptr = ENOMEM;
        return -1;
    }

    //Ensure child length is less than CHAR_LIMIT_INCLUDE_NULL
    for (childlen = 1; childlen < parentlen; childlen++) {
        // Find the last trailing slash from the end
        if (parentpath[parentlen - childlen - 1] == '/') {
            break;
        }
    }
    if (childlen > CHAR_LIMIT_INCLUDE_NULL - 1) {
        free(parentpath);
        *errnoptr = ENAMETOOLONG;
        return -1;
    }

    // Copy child and shorten parent
    childname = strndup(parentpath + parentlen - childlen, childlen);
    if (childname == NULL) {
        free(parentpath);
        *errnoptr = ENOMEM;
        return -1;
    }
#ifdef DEBUG
    size_t fullchildlen = parentlen;
    popname(parentpath, &parentlen);
    assert(fullchildlen == (parentlen == 1 ? 1 : parentlen + 1) + childlen);
#else
    popname(parentpath, &parentlen);
#endif

    *parentpath_return = parentpath;
    *childname_return = childname;
    return 0;
}


//! Creates an entry in a directory with specified mode. Caller must finish
//! initialization as correct for each type of item (dir, link, file, etc).
//! Caller must set uid, gid, links.
//! Path must be rooted.
//! Returns 0 on success, -1 on failure
int mkentry(const char *path, mode_t mode, inodenum_t *child_return, uid_t uid,
            gid_t gid, struct start_t *start, int *errnoptr) {
    __label__ failexitandfree;
    char *parentpath, *childname;
    inodenum_t parentnum, childnum;
    if (path[0] != '/') {
        *errnoptr = ENOENT;
        return -1;
    }

    if (getparentchild(path, &parentpath, &childname, start, errnoptr) == -1) {
        return -1;
    }

    //Ensure parent exists and is directory
    if (resolvepath(parentpath, &parentnum, start, errnoptr) == -1) {
        goto failexitandfree;
    }
    if (!S_ISDIR(INODE_T_ZERO(start)[parentnum].mode)) {
        *errnoptr = ENOTDIR;
        goto failexitandfree;
    }
    //Ensure child doesn't exist
    if (getentry(childname, parentnum, &childnum, start, errnoptr) == 0) {
        *errnoptr = EEXIST;
        goto failexitandfree;
    }

    //Get an inode for the kid
    if (getinode(&childnum, start, errnoptr) == -1) {
        goto failexitandfree;
    }

    struct inode_t *inode = INODE_T_ZERO(start) + childnum;
    inode->mode = mode;
    inode->uid = uid;
    inode->gid = gid;
    clock_gettime(CLOCK_REALTIME, &inode->atime);
    inode->mtime = inode->atime;
    inode->links = 1;
    if (S_ISDIR(mode)) {
        inode->entries = 0;
        struct block_t newblock;
        if (getblock(&newblock, 1, start, errnoptr) == -1) {
            freeinode(childnum, start);
            goto failexitandfree;
        }
        inode->block[0] = newblock;
        inode->block[0].dircount = 0;
        inode->block[0].dirindex = 0;
        if (addentry(".", childnum, childnum, start, errnoptr) == -1
            || addentry("..", childnum, parentnum, start, errnoptr) == -1) {
            freeinode(childnum, start);
            goto failexitandfree;
        }
    }
    else if (S_ISREG(mode)) {
        inode->size = 0;
    }
    else {
#ifdef DEBUG
        assert(0);
#endif
        freeinode(childnum, start);
        goto failexitandfree;
    }

    //Add it to parent
    if (addentry(childname, parentnum, childnum, start, errnoptr) == -1) {
        //Free inode if it fails.
        freeinode(childnum, start);
        goto failexitandfree;
    }

    free(parentpath);
    free(childname);
    return 0;

failexitandfree:
    free(parentpath);
    free(childname);
    return -1;
}

/* End of helper functions */

/* Implements an emulation of the stat system call on the filesystem
   of size fssize pointed to by fsptr.

   If path can be followed and describes a file or directory
   that exists and is accessable, the access information is
   put into stbuf.

   On success, 0 is returned. On failure, -1 is returned and
   the appropriate error code is put into *errnoptr.

   man 2 stat documents all possible error codes and gives more detail
   on what fields of stbuf need to be filled in. Essentially, only the
   following fields need to be supported:

   st_uid      the value passed in argument
   st_gid      the value passed in argument
   st_mode     (as fixed values S_IFDIR | 0755 for directories,
                                S_IFREG | 0755 for files)
   st_nlink    (as many as there are subdirectories (not files) for directories
                (including . and ..),
                1 for files)
   st_size     (supported only for files, where it is the real file size)
   st_atim
   st_mtim

*/
int __myfs_getattr_implem(void *fsptr, size_t fssize, int *errnoptr, uid_t uid,
                          gid_t gid, const char *path, struct stat *stbuf) {
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }
    struct start_t *start = fsptr;

    inodenum_t inode;
    if (resolvepath(path, &inode, start, errnoptr) == -1) {
        return -1;
    }

    struct inode_t *inodeptr = INODE_T_ZERO(start) + inode;

    stbuf->st_uid = inodeptr->uid;
    stbuf->st_gid = inodeptr->gid;
    stbuf->st_mode = inodeptr->mode;
    stbuf->st_nlink = inodeptr->links;
    stbuf->st_size = inodeptr->size;
    stbuf->st_atim = inodeptr->atime;
    stbuf->st_mtim = inodeptr->mtime;
    return 0;
}

/* Implements an emulation of the readdir system call on the filesystem
   of size fssize pointed to by fsptr.

   If path can be followed and describes a directory that exists and
   is accessable, the names of the subdirectories and files
   contained in that directory are output into *namesptr. The . and ..
   directories must not be included in that listing.

   If it needs to output file and subdirectory names, the function
   starts by allocating (with calloc) an array of pointers to
   characters of the right size (n entries for n names). Sets
   *namesptr to that pointer. It then goes over all entries
   in that array and allocates, for each of them an array of
   characters of the right size (to hold the i-th name, together
   with the appropriate '\0' terminator). It puts the pointer
   into that i-th array entry and fills the allocated array
   of characters with the appropriate name. The calling function
   will call free on each of the entries of *namesptr and
   on *namesptr.

   The function returns the number of names that have been
   put into namesptr.

   If no name needs to be reported because the directory does
   not contain any file or subdirectory besides . and .., 0 is
   returned and no allocation takes place.

   On failure, -1 is returned and the *errnoptr is set to
   the appropriate error code.

   The error codes are documented in man 2 readdir.

   In the case memory allocation with malloc/calloc fails, failure is
   indicated by returning -1 and setting *errnoptr to EINVAL.

*/
int __myfs_readdir_implem(void *fsptr, size_t fssize, void *buf,
                          fuse_fill_dir_t filler, int *errnoptr,
                          const char *path) {
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }
    inodenum_t inodenum;
    struct start_t *start = fsptr;
    // Verify path exists
    if (resolvepath(path, &inodenum, start, errnoptr) == -1) {
        return -1;
    }
    struct inode_t *inode = INODE_T_ZERO(start) + inodenum;
#ifdef DEBUG
    assert(inode->entries >= 2); // Should always contain . and ..
#endif

    //Loop through directory
    link_t entrynum = 0; //!< The entry we are currently interested in
    struct direntry_t *entries;
    //For each block
    for (size_t blocknum = 0; blocknum < INODE_INLINE_COUNT; blocknum++) {
        struct block_t *block = &(inode->block[blocknum]); //!< The current block
        entries = (void *)start + block->location;         //!< The array of entries
        //For each entry in block
        for (size_t i = 0; i < block->dircount; i++) {
            if (filler(buf, entries[i].name, NULL, 0) != 0) {
                *errnoptr = ENOMEM;
                return -1;
            }
            if (++entrynum == inode->entries) {
                //Have copied all, return
                return 0;
            }
        }
    }

    //There must be pointer blocks if we made it this far
#ifdef DEBUG
    assert(inode->ptr_block != 0);
#endif
    struct ptrblock_t *ptrblock = (void *)start + inode->ptr_block;
    while (1) {
        //For each block
        for (size_t blocknum = 0; blocknum < PTR_PER_PTRBLOCK; blocknum++) {
            struct block_t *block =
              &(ptrblock->blocks[blocknum]);           //!< The current block
            entries = (void *)start + block->location; //!< The array of entries
            //For each entry in block
            for (size_t i = 0; i < block->dircount; i++) {
                if (filler(buf, entries[i].name, NULL, 0) != 0) {
                    *errnoptr = ENOMEM;
                    return -1;
                }
                if (++entrynum == inode->entries) {
                    //Have copied all, return
                    return 0;
                }
            }
        }

        //There's still more pointer blocks
        ptrblock = (void *)start + ptrblock->next;
    }
}

/* Implements an emulation of the mknod system call for regular files
   on the filesystem of size fssize pointed to by fsptr.

   This function is called only for the creation of regular files.

   If a file gets created, it is of size zero and has default
   ownership and mode bits.

   The call creates the file indicated by path.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 mknod.

*/
int __myfs_mknod_implem(void *fsptr, size_t fssize, int *errnoptr,
                        const char *path) {
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }

    inodenum_t child;
    return mkentry(path, S_IFREG | 0755, &child, getuid(), getgid(), fsptr,
                   errnoptr);
}

/* Implements an emulation of the unlink system call for regular files
   on the filesystem of size fssize pointed to by fsptr.

   This function is called only for the deletion of regular files.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 unlink.

*/
int __myfs_unlink_implem(void *fsptr, size_t fssize, int *errnoptr,
                         const char *path) {
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }
    if (path[0] != '/') {
        *errnoptr = ENOENT;
        return -1;
    }
    struct start_t *start = fsptr;
    inodenum_t parentnum, childnum;
    struct inode_t *childinode;

    //Ensure path exists and isn't a directory
    if (resolvepath(path, &childnum, start, errnoptr) == -1) {
        return -1;
    }
    childinode = INODE_T_ZERO(start) + childnum;
    if (S_ISDIR(childinode->mode)) {
        *errnoptr = EISDIR;
        return -1;
    }

    //Get parent directory
    char *parentpath, *childname;
    if (getparentchild(path, &parentpath, &childname, start, errnoptr) == -1) {
        *errnoptr = ENOMEM;
        return -1;
    }

    // Parent directories must exist, since we successfully got the child
    // Drop the entry from the parent.
#ifdef DEBUG
    assert(resolvepath(parentpath, &parentnum, start, errnoptr) == 0
           && dropentry(childname, parentnum, start, errnoptr) == 0);
#else
    resolvepath(parentpath, &parentnum, start, errnoptr);
    dropentry(childname, parentnum, start, errnoptr);
#endif

    childinode->links--;
    if (childinode->links == 0) {
        freeinode(childnum, start);
    }

    free(parentpath);
    free(childname);
    return 0;
}

/* Implements an emulation of the rmdir system call on the filesystem
   of size fssize pointed to by fsptr.

   The call deletes the directory indicated by path.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The function call must fail when the directory indicated by path is
   not empty (if there are files or subdirectories other than . and ..).

   The error codes are documented in man 2 rmdir.

*/
int __myfs_rmdir_implem(void *fsptr, size_t fssize, int *errnoptr,
                        const char *path) {
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }
    if (path[0] != '/') {
        *errnoptr = ENOENT;
        return -1;
    }
    struct start_t *start = fsptr;
    inodenum_t parentnum, childnum;
    struct inode_t *childinode;

    //Ensure path exists and is a directory
    if (resolvepath(path, &childnum, start, errnoptr) == -1) {
        return -1;
    }
    childinode = INODE_T_ZERO(start) + childnum;
    if (!S_ISDIR(childinode->mode)) {
        *errnoptr = ENOTDIR;
        return -1;
    }

    // Ensure isn't the root, you can't remove that.
    if (childnum == 0) {
        *errnoptr = EBUSY; // Is there maybe a more appropriate one?
        return -1;
    }

    // Ensure the directory is empty
#ifdef DEBUG
    assert(childinode->entries >= 2);
#endif
    if (childinode->entries != 2) {
        *errnoptr = ENOTEMPTY;
        return -1;
    }

    //Get parent directory
    char *parentpath, *childname;
    if (getparentchild(path, &parentpath, &childname, start, errnoptr) == -1) {
        *errnoptr = ENOMEM;
        return -1;
    }

    // Parent directories must exist, since we successfully got the child
    // and the child isn't the root
    // Drop the entry from the parent.
#ifdef DEBUG
    assert(resolvepath(parentpath, &parentnum, start, errnoptr) == 0
           && dropentry(childname, parentnum, start, errnoptr) == 0);
#else
    resolvepath(parentpath, &parentnum, start, errnoptr);
    dropentry(childname, parentnum, start, errnoptr);
#endif

    childinode->links--;
    if (childinode->links == 0) {
        freeinode(childnum, start);
    }

    free(parentpath);
    free(childname);
    return 0;
    return -1;
}

/* Implements an emulation of the mkdir system call on the filesystem
   of size fssize pointed to by fsptr.

   The call creates the directory indicated by path.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 mkdir.

*/
int __myfs_mkdir_implem(void *fsptr, size_t fssize, int *errnoptr,
                        const char *path) {
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }

    inodenum_t child;
    return mkentry(path, S_IFDIR | 0755, &child, getuid(), getgid(), fsptr,
                   errnoptr);
}

/* Implements an emulation of the rename system call on the filesystem
   of size fssize pointed to by fsptr.

   The call moves the file or directory indicated by from to to.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   Caution: the function does more than what is hinted to by its name.
   In cases the from and to paths differ, the file is moved out of
   the from path and added to the to path.

   The error codes are documented in man 2 rename.

*/
int __myfs_rename_implem(void *fsptr, size_t fssize, int *errnoptr,
                         const char *from, const char *to) {
    __label__ freenamesreturn;
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }
    inodenum_t fromnum, tonum;
    struct inode_t *frominode, *toinode;
    int toexists, istodir, isfromdir;
    struct start_t *start = fsptr;

    //Ensure paths make sense
    if (to[0] != '/' || from[0] != '/') {
        *errnoptr = ENOENT;
        return -1;
    }

    //Get inodes
    if (resolvepath(from, &fromnum, start, errnoptr) == -1) {
        return -1;
    }
    toexists = (resolvepath(from, &tonum, start, errnoptr) == -1) ? 0 : 1;

    // Hard links referring to the same file
    if (toexists && fromnum == tonum) {
        return 0;
    }
    //Trying to create something that's a parent of itself
    // Other EINVAL is handled by to never being empty if it is a directory
    // would be ENOTEMPTY.
    if (fromnum == 0) /* from == '/' */ {
        *errnoptr = EINVAL;
        return -1;
    }
    //Can't replace root, it's not empty.
    if (toexists && tonum == 0) {
        *errnoptr = ENOTEMPTY;
        return -1;
    }

    // Get children and parents
    char *fromparentpath, *fromchildname, *toparentpath, *tochildname;
    if (getparentchild(from, &fromparentpath, &fromchildname, start, errnoptr)
        == -1) {
        *errnoptr = ENOMEM;
        return -1;
    }
    if (getparentchild(from, &toparentpath, &tochildname, start, errnoptr)
        == -1) {
        free(fromparentpath);
        free(fromchildname);
        *errnoptr = ENOMEM;
        return -1;
    }
    int returnval = 0;

    // to's parent must exist and be a directory.
    inodenum_t toparentnum, fromparentnum;
    if (resolvepath(toparentpath, &toparentnum, start, errnoptr) == -1) {
        returnval = -1;
        goto freenamesreturn;
    }
    if (!S_ISDIR(INODE_T_ZERO(start)[toparentnum].mode)) {
        *errnoptr = ENOTDIR;
        returnval = -1;
        goto freenamesreturn;
    }

    // Get from's parent
    // Cannot fail, as we resolved from successfully
#ifdef DEBUG
    assert(resolvepath(fromparentpath, &fromparentnum, start, errnoptr) == 0);
#else
    resolvepath(fromparentpath, &fromparentnum, start, errnoptr);
#endif

    // To doesn't exist, move the file/directory
    // Create a new entry in toparent, and remove the entry from fromparent
    if (!toexists) {
        // Add the entry first, that might fail
        if (addentry(tochildname, toparentnum, fromnum, start, errnoptr) == -1) {
            returnval = -1;
            goto freenamesreturn;
        }
        dropentry(fromchildname, fromparentnum, start, errnoptr);
        returnval = 0;
        goto freenamesreturn;
    }

    isfromdir = S_ISDIR((frominode = INODE_T_ZERO(start) + fromnum)->mode);
    istodir = S_ISDIR((toinode = INODE_T_ZERO(start) + tonum)->mode);

    // is from a directory?
    if (isfromdir) {
        // to must be a directory or nonexistant.
        if (toexists && !istodir) {
            *errnoptr = ENOTDIR;
            returnval = -1;
            goto freenamesreturn;
        }
        // is to an empty directory (entries = 2)?
        // else fail.
        if (toinode->entries != 2) {
#ifdef DEBUG
            assert(toinode->entries > 2);
#endif
            *errnoptr = ENOTEMPTY;
            returnval = -1;
            goto freenamesreturn;
        }
    }
    // is tonum a directory? fail.
    else if (istodir) {
        *errnoptr = EISDIR;
        returnval = -1;
        goto freenamesreturn;
    }

    // If we've arrived here, then we need to change the inode in toparentnum
    // and remove fromchildname in fromparentnum.
    // We've already determined these all exist, so there's no failures possible.
#ifdef DEBUG
    assert(setentry(tochildname, toparentnum, &fromnum, start, errnoptr) == 0
           && dropentry(fromchildname, fromparentnum, start, errnoptr) == 0);
#else
    setentry(tochildname, toparentnum, &fromnum, start, errnoptr);
    dropentry(fromchildname, fromparentnum, start, errnoptr);
#endif
    toinode->links--;
    if (toinode->links == 0) {
        freeinode(tonum, start);
    }
    returnval = 0;

freenamesreturn:
    free(fromparentpath);
    free(fromchildname);
    free(toparentpath);
    free(tochildname);
    return returnval;
}

/* Implements an emulation of the truncate system call on the filesystem
   of size fssize pointed to by fsptr.

   The call changes the size of the file indicated by path to offset
   bytes.

   When the file becomes smaller due to the call, the extending bytes are
   removed. When it becomes larger, zeros are appended.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 truncate.

*/
int __write_to_file(struct start_t *start, struct inode_t *inode, const char *buffer, size_t size, off_t offset);
int __get_rem_space_in_file_block(struct start_t *start, struct inode_t *inode, off_t offset, size_t *rem_space);
int __request_blocks(struct start_t *start, struct inode_t *inode, int *errnoptr, size_t bytes_requested);

int __myfs_truncate_implem(void *fsptr, size_t fssize, int *errnoptr,
                           const char *path, off_t offset) {
    inodenum_t inodenum;
    size_t rem_space, file_size;
    struct start_t *start;
    struct inode_t *inode;

    if (createfs(fsptr, fssize, errnoptr) == -1) {
    *errnoptr = EFAULT;
      return -1;
    }

    start = fsptr;

    // Verify path exists
    if (resolvepath(path, &inodenum, start, errnoptr) == -1) {
      *errnoptr = ENOENT;
      return -1;
    }

    inode = INODE_T_ZERO(start) + inodenum;

    // check if directory
    if (S_ISDIR(inode->mode)) {
    *errnoptr = EISDIR;
    return -1;
    }

    file_size = inode->size;

    if (offset < file_size) {
        // if shrinking the file size
        size_t null_size = file_size - offset;
        void *null_buffer = malloc(null_size);
        if (null_buffer == NULL) {
            *errnoptr = ENOMEM;
            return -1;
        }
        memset(null_buffer, 0, null_size);
        __write_to_file(start, inode, null_buffer, null_size, offset);
    }
    else if (offset > file_size) {
        size_t expand_by = offset-file_size;
        // if expanding the file size
        if (__get_rem_space_in_file_block(start, inode, file_size, &rem_space) == -1) {
        // seek error;
            *errnoptr = EOVERFLOW;
        return -1;
        }

        int space_needed = (int)expand_by - (int)rem_space;
        if (space_needed > 0l) {
        __request_blocks(start, inode, errnoptr, (size_t)space_needed);
        }
        // should have space to write contiguously now
        void *zero_buffer = malloc(expand_by);
        if (zero_buffer == NULL) {
            *errnoptr = ENOMEM;
            return -1;
        }
        memset(zero_buffer, 0, expand_by);
        __write_to_file(start, inode, zero_buffer, expand_by, file_size);
    }
    return 0;
}

/* Implements an emulation of the open system call on the filesystem
   of size fssize pointed to by fsptr, without actually performing the opening
   of the file (no file descriptor is returned).

   The call just checks if the file (or directory) indicated by path
   can be accessed, i.e. if the path can be followed to an existing
   object for which the access rights are granted.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The two only interesting error codes are

   * EFAULT: the filesystem is in a bad state, we can't do anything

   * ENOENT: the file that we are supposed to open doesn't exist (or a
             subpath).

   It is possible to restrict ourselves to only these two error
   conditions. It is also possible to implement more detailed error
   condition answers.

   The error codes are documented in man 2 open.

*/
int __myfs_open_implem(void *fsptr, size_t fssize, int *errnoptr,
                       const char *path) {
    inodenum_t ret;
    return resolvepath(path, &ret, fsptr, errnoptr);
}

/*  Returns the ith block in the file's pointer blocks, i goes from 0 to n-1
        get_file_block_from_ptrblock(0) -> returns the file's 0th file block in the ptrs.
        ie file block 8 is ptr block 0 */
struct block_t* __get_file_block_from_ptrblock(struct start_t *start, struct inode_t *inode, size_t index) {
    if (inode->ptr_block == 0) {
        // indicate that the inode needs to setup a new ptr block
        return NULL;
    }
  struct ptrblock_t *this_ptrblock = (void*)start + inode->ptr_block;
  size_t rem_index = index;
  while (rem_index >= PTR_PER_PTRBLOCK) {
      rem_index -= PTR_PER_PTRBLOCK;
      this_ptrblock = (void*)start + this_ptrblock->next;
        if (this_ptrblock->next == 0) {
            // basically new ptr block must be set up
            return NULL;
        }
  }
  return &this_ptrblock->blocks[rem_index];
}

/*  Find the ith (index) block from the inode including ptrblock blocks
        Return NULL if block is not initialized
        Index goes from 0 to n-1 */
struct block_t* __get_file_block(struct start_t *start, struct inode_t *inode, size_t index) {
  if (index < INODE_INLINE_COUNT) {
    return &inode->block[index];
  } else {
    return __get_file_block_from_ptrblock(start, inode, index-INODE_INLINE_COUNT);
  }
}

/*  finds the inode's block that corresponds to the offset,
        changes rem_offset to the remaining_offset for that block ie 4108 -> 12
        returns -1 if the offset seeks over empty blocks*/
int __get_file_block_at_offset(struct start_t *start, struct inode_t *inode, size_t *file_index, off_t *rem_offset) {
  size_t block_index = 0;
  struct block_t *file_block;

  file_block = __get_file_block(start, inode, block_index);
  while (file_block->bytecount < *rem_offset) {
      if (file_block->bytecount == 0){
          // cannot seek as file is not there
      return -1;
      }
      *rem_offset -= file_block->bytecount;
      block_index++;
      file_block = __get_file_block(start, inode, block_index);
  }
  *file_index = block_index;
  return 0;
}

/*  Read starting from inode's ith block at first_offset,
        continue reading from every block for size bytes */
size_t __read_from_file_block(struct start_t *start, struct inode_t *inode, char *buffer, size_t *block_i, off_t *first_offset, size_t size) {
  size_t rem_size = size;
  size_t read_in = 0;
  struct block_t *file_block = __get_file_block(start, inode, *block_i);

  void *data_location = (void*)start+file_block->location+*first_offset;
  size_t data_remaining = file_block->bytecount - *first_offset;
  size_t max_data_in_block = file_block->num*BLOCKSIZE - *first_offset;

  while (rem_size > 0) {
      // if there's more data that needs to be put into buffer than what is left in the current file's block
    if (data_remaining >= max_data_in_block) {
      // put whole block at a time into buffer
      memcpy(buffer, data_location, max_data_in_block);
      rem_size -= max_data_in_block;
      read_in += max_data_in_block;
      // point to next block
      *block_i += 1;
      file_block = __get_file_block(start, inode, *block_i);
      data_location = (void*)start+file_block->location;
      data_remaining = file_block->bytecount;
      max_data_in_block = file_block->num*BLOCKSIZE;
    }
    else {
      // put rest of data
      memcpy(buffer, data_location, data_remaining);
      rem_size -= data_remaining;
      read_in += data_remaining;
      break;
    }
  }
  return read_in;
}

size_t __read_file_from_offset(struct start_t *start, struct inode_t *inode, char* buffer, off_t offset, size_t size) {
  off_t rem_offset = offset;
  size_t file_index = 0;
  size_t read_in = 0;

  __get_file_block_at_offset(start, inode, &file_index, &rem_offset);
  read_in = __read_from_file_block(start, inode, buffer, &file_index, &rem_offset, size);
  return read_in;
}

/* Implements an emulation of the read system call on the filesystem
   of size fssize pointed to by fsptr.

   The call copies up to size bytes from the file indicated by
   path into the buffer, starting to read at offset. See the man page
   for read for the details when offset is beyond the end of the file etc.

   On success, the appropriate number of bytes read into the buffer is
   returned. The value zero is returned on an end-of-file condition.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 read.
*/
int __myfs_read_implem(void *fsptr, size_t fssize, int *errnoptr,
                       const char *path, char *buf, size_t size, off_t offset) {

  inodenum_t inodenum;
  struct start_t *start;
  struct inode_t *inode;
  size_t size_copied;

  if (createfs(fsptr, fssize, errnoptr) == -1) {
      *errnoptr = EFAULT;
      return -1;
  }

  start = fsptr;

  // Verify path exists
  if (resolvepath(path, &inodenum, start, errnoptr) == -1) {
      *errnoptr = ENOENT;
      return -1;
  }

  inode = INODE_T_ZERO(start) + inodenum;

  // check if directory
  if (S_ISDIR(inode->mode)) {
     *errnoptr = EISDIR;
     return -1;
  }

  size_copied = __read_file_from_offset(start, inode, buf, offset, size);
  return (int)size_copied;
}


int __write_to_file(struct start_t *start, struct inode_t *inode, const char *buffer, size_t size, off_t offset) {
  size_t rem_size = size;
  size_t block_i = 0;
  off_t rem_offset = offset;
  struct block_t *file_block;
  void *data_location;
  int max_size;
  size_t write_out = 0;

  if (__get_file_block_at_offset(start, inode, &block_i, &rem_offset) == -1) {
      return -1;
  }
  // offset 0 or offset 10 but empty block or has 9 chars
  file_block = __get_file_block(start, inode, block_i);
  data_location = (void*)start + file_block->location+rem_offset;

  max_size = file_block->num*BLOCKSIZE-rem_offset;
    while (rem_size > 0) {
      if (max_size < rem_size) {
          memcpy(data_location, buffer, max_size);
          rem_size -= (size_t)max_size;
          write_out += (size_t)max_size;
          file_block->bytecount += max_size;
          inode->size += max_size;
          // next block
          block_i += 1;
          file_block = __get_file_block(start, inode, block_i);
                if (file_block->location == 0) {
                    // file block was not allocated
                    return -1;
                }
          data_location = (void*)start + file_block->location;
          max_size = file_block->num*BLOCKSIZE;
      } else {
          memcpy(data_location, buffer, rem_size);
          file_block->bytecount += rem_size;
          inode->size += rem_size;
          write_out += rem_size;
          rem_size -= rem_size;
      }
    }
  return (int)write_out;
}


int __get_rem_space_in_file_block(struct start_t *start, struct inode_t *inode, off_t offset, size_t *rem_space) {
  size_t block_i = 0;
  off_t rem_offset = offset;
  struct block_t *file_block;

  if (__get_file_block_at_offset(start, inode, &block_i, &rem_offset) == -1) {
      // seeking beyond what's already written skipping over blocks, assuming file has to be 1 continuous string
      return -1;
  }
  file_block = __get_file_block(start, inode, block_i);
  if (offset > file_block->bytecount+1) {
      // seeking beyond what is already written within block
      return -1;
  }
  *rem_space = file_block->num*BLOCKSIZE-offset;
  return 0;
}

int __request_ptr_block(struct start_t *start, struct inode_t *inode, int *errnoptr, size_t blocks_needed) {
    offset_t next_ptr_offset;
    struct ptrblock_t *next_ptr_block;
    int check_success;

    next_ptr_offset = inode->ptr_block;
    while (next_ptr_offset != 0) {
        next_ptr_block = (struct ptrblock_t*)((void*)start+next_ptr_offset);
        next_ptr_offset = next_ptr_block->next;
    }

    // make next_ptr_offset point to an actual ptr_block
    check_success = getptrblock(&next_ptr_offset, blocks_needed, start, errnoptr);
    if (check_success == -1) {
        return -1;
    }
    return 0;
}

int __request_blocks(struct start_t *start, struct inode_t *inode, int *errnoptr, size_t bytes_requested) {
  size_t blocks_needed = (bytes_requested / BLOCKSIZE) + 1;
  size_t block_i = 0;
  struct block_t *new_block;
  int check_success = 0;

  while (blocks_needed > 0) {
      new_block = __get_file_block(start, inode, block_i);
            if (new_block == NULL) {
                __request_ptr_block(start, inode, errnoptr, blocks_needed);
                new_block = __get_file_block(start, inode, block_i);
                if (new_block == NULL) {
                    // out of space / could not set up new ptr block
                    return -1;
                }
                blocks_needed -= new_block->num;
            }
      if (new_block->location == 0) {
          check_success = getblock(new_block,(off_t)blocks_needed, start, errnoptr);
          if (check_success == -1) {
              return -1;
          }
          blocks_needed -= new_block->num;
      }
            block_i += 1;
  }
  return 0;
}

/* Implements an emulation of the write system call on the filesystem
   of size fssize pointed to by fsptr.

   The call copies up to size bytes to the file indicated by
   path into the buffer, starting to write at offset. See the man page
   for write for the details when offset is beyond the end of the file etc.

   On success, the appropriate number of bytes written into the file is
   returned. The value zero is returned on an end-of-file condition.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 write.

*/
int __myfs_write_implem(void *fsptr, size_t fssize, int *errnoptr,
                        const char *path, const char *buf, size_t size,
                        off_t offset) {
    inodenum_t inodenum;
    struct start_t *start;
    struct inode_t *inode;
    size_t rem_space;

    if (createfs(fsptr, fssize, errnoptr) == -1) {
      *errnoptr = EFAULT;
      return -1;
    }

    start = fsptr;

    // Verify path exists
    if (resolvepath(path, &inodenum, start, errnoptr) == -1) {
      *errnoptr = ENOENT;
      return -1;
    }

    inode = INODE_T_ZERO(start) + inodenum;

    // check if directory
    if (S_ISDIR(inode->mode)) {
        *errnoptr = EISDIR;
        return -1;
    }

    if (__get_rem_space_in_file_block(start, inode, offset, &rem_space) == -1) {
        // seek error;
            *errnoptr = EOVERFLOW;
        return -1;
    }

    int space_needed = (int)size - (int)rem_space;
    if (space_needed > 0l) {
        __request_blocks(start, inode, errnoptr, (size_t)space_needed);
    }
    // should have space to write contiguously now
    return __write_to_file(start, inode, buf, size, offset);
}
/* Implements an emulation of the utimensat system call on the filesystem
   of size fssize pointed to by fsptr.

   The call changes the access and modification times of the file
   or directory indicated by path to the values in ts.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 utimensat.

*/
int __myfs_utimens_implem(void *fsptr, size_t fssize, int *errnoptr,
                          const char *path, const struct timespec ts[2]) {
    inodenum_t inodenum;
    struct inode_t *inode;
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }

    if (resolvepath(path, &inodenum, fsptr, errnoptr) == -1) {
        return -1;
    }
    inode = INODE_T_ZERO((struct start_t *)fsptr) + inodenum;
    inode->atime = ts[0];
    inode->mtime = ts[1];
    return 0;
}

/* Implements an emulation of the statfs system call on the filesystem
   of size fssize pointed to by fsptr.

   The call gets information of the filesystem usage and puts in
   into stbuf.

   On success, 0 is returned.

   On failure, -1 is returned and *errnoptr is set appropriately.

   The error codes are documented in man 2 statfs.

   Essentially, only the following fields of struct statvfs need to be
   supported:

   f_bsize   fill with what you call a block (typically 1024 bytes)
   f_blocks  fill with the total number of blocks in the filesystem
   f_bfree   fill with the free number of blocks in the filesystem
   f_bavail  fill with same value as f_bfree
   f_namemax fill with your maximum file/directory name, if your
             filesystem has such a maximum

*/
int __myfs_statfs_implem(void *fsptr, size_t fssize, int *errnoptr,
                         struct statvfs *stbuf) {
    if (createfs(fsptr, fssize, errnoptr) == -1) {
        return -1;
    }
    stbuf->f_namemax = CHAR_LIMIT_INCLUDE_NULL - 1;
    stbuf->f_bsize = BLOCKSIZE;
    stbuf->f_blocks = ((struct start_t *)fsptr)->size / BLOCKSIZE;
    stbuf->f_bfree = 0;

    // If start->firstfree is not 0, add up all blocks.
    if (((struct start_t *)fsptr)->firstfree != 0) {
        struct freespace_t *space = fsptr + ((struct start_t *)fsptr)->firstfree;
        while (1) {
            stbuf->f_bfree += space->freeblocks;
            if (space->next == 0) {
                break;
            }
            space = (void *)space + space->next;
        }
    }
    stbuf->f_bavail = stbuf->f_bfree;
    return 0;
}