MyFilesystem

/*

  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
                Austin Williams
                ...

  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 <stddef.h>
#include <sys/stat.h>
#include <sys/statvfs.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <stdio.h>


/* 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 and functions */
typedef enum{
  Empty,
  File,
  Directory,
  Stockpile,
} blockTypes;

typedef uint32_t offset_t;

typedef struct FS_header_t {
  offset_t freeblock_tail; // points to the tail block of the linked list of available freeblock numbers (stored in blocks)
  int freeblock_count; // might need later
  _Bool is_setup;
  int total_blocks;
  struct timespec tempTime;
  int root_dir;
} FS_header_t;

#define TRUE 1
#define FALSE 0
#define BLOCK_SIZE 4096
#define CHAR_LIMIT_INCLUDE_NULL 256
#define START_OFFSET sizeof(FS_header_t)
#define PATH_SEPARATOR ("/")
#define PATH_CHAR ('/')

typedef struct entry_t {
  char file_name[CHAR_LIMIT_INCLUDE_NULL];
  int block_num;
} entry_t;

typedef struct block_t {
  int block_num;
  blockTypes content_type;
  size_t bytes_occupied;
} block_t;

typedef struct file_t {
  int next_block;
  struct timespec atim;
  struct timespec mtim;
} file_t;

typedef struct directory_t {
  int next_block;
  struct timespec atim;
  struct timespec mtim;
  int entry_count;
  int furthest_index;
  // entries written under it (up to 15)
} directory_t;

// a linked list of blocks holding a stack of empty block numbers
typedef struct freeblock_t {
  int next_block;
  int prev_block;
  int freeblock_count;
} freeblock_t;

#define FREE_BLOCK_NUMBERS_PER_BLOCK (BLOCK_SIZE - sizeof(block_t) - sizeof(freeblock_t))/sizeof(int)
#define ENTRIES_PER_BLOCK (BLOCK_SIZE-sizeof(block_t)-sizeof(directory_t))/sizeof(entry_t)

// typedef struct file_header_t {
//
// } file_header_t;
//
// typedef struct block_header_t {
//
// } block_header_t;

/* YOUR HELPER FUNCTIONS GO HERE */
// FS_header_t* initialize_FS(void* fsptr, size_t fssize) {
//   return (FS_header_t*) fsptr;
// }
// start_fs()
// get_free_block()
// return_free_block()
// typedef struct freeblock {
//
// }




// block goes from 0 to total_blocks-1
block_t* retrieve_block(void *fsptr, int n) {
  offset_t offset = n*BLOCK_SIZE;
  block_t *block = (block_t*) (fsptr+START_OFFSET+offset);
  //sizeof(block_t)
  return block;
}

// initializes each block with its block number, needed for pointing to next/prev, (could also give them number in retrieve block function if takes too long)
int initialize_blocks(FS_header_t *handle) {
  for (int i=0; i<handle->total_blocks; i++) {
    block_t *block = retrieve_block((void*)handle, i);
    block->block_num = i;
    block->bytes_occupied = sizeof(block_t);
  }
  return 0;
}

freeblock_t* get_stockpile_header(block_t*);
int* get_stockpile_num_array(block_t*);


// returns pointer under the block header
void* __get_header(block_t* block) {
  void *ptr = (void*)block;
  return ptr+sizeof(block_t);
}

file_t* get_file_header(block_t *file_block) {
  if (file_block->content_type != File) {
    fprintf(stderr, "file_block is not a file block\n");
    return NULL;
  }
  return (file_t*)__get_header(file_block);
}

void* get_file_content(block_t *file_block) {
  if (file_block->content_type != File) {
    fprintf(stderr, "file_block is not a file block\n");
    return NULL;
  }
  return ((void*)file_block)+sizeof(file_t)+sizeof(block_t);
}

directory_t* get_directory_header(block_t *dir_block) {
  if (dir_block->content_type != Directory) {
    fprintf(stderr, "dir_block is not a directory block\n");
    return NULL;
  }
  return (directory_t*)__get_header(dir_block);
}

entry_t* get_directory_entries(block_t *dir_block) {
  if (dir_block->content_type != Directory) {
    fprintf(stderr, "dir_block is not a directory block\n");
    return NULL;
  }
  return (entry_t*)(((void*)dir_block)+sizeof(directory_t)+sizeof(block_t));
}

freeblock_t* get_stockpile_header(block_t *stockpile_block) {
  if (stockpile_block->content_type != Stockpile) {
    fprintf(stderr, "stockpile_block is not a stockpile block\n");
    return NULL;
  }
  return (freeblock_t*)__get_header(stockpile_block);
}

int* get_stockpile_num_array(block_t *stockpile_block) {
  if (stockpile_block->content_type != Stockpile) {
    fprintf(stderr, "stockpile_block is not a stockpile block\n");
    return NULL;
  }
  return (int*)(((void*)stockpile_block)+sizeof(freeblock_t)+sizeof(block_t));
}

// only called by setup_filesystem
// initializes the root directory
// store_file(int startingBlock)
struct timespec get_time(FS_header_t* globals) {
  // are we allowed to use the stack or no?
  // get deleted after moving out of stack
  clock_gettime(CLOCK_REALTIME, &(globals->tempTime));
  return globals->tempTime;
}

int set_dir_time(directory_t *header, _Bool has_been_modified) {
  struct timespec temp_time;
  clock_gettime(CLOCK_REALTIME, &(temp_time));
  header->atim = temp_time;
  if (has_been_modified) {
    header->mtim = temp_time;
  }
  return 0;
}

int set_file_time(file_t *header, _Bool has_been_modified) {
  struct timespec temp_time;
  clock_gettime(CLOCK_REALTIME, &(temp_time));
  header->atim = temp_time;
  if (has_been_modified) {
    header->mtim = temp_time;
  }
  return 0;
}

int set_block_time(block_t *block, _Bool has_been_modified) {
  int return_value;
  if (block->content_type == Directory) {
    return_value = set_dir_time(get_directory_header(block), has_been_modified);
  } else if (block->content_type == File) {
    return_value = set_file_time(get_file_header(block), has_been_modified);
  }
  return return_value;
}

block_t* clean_block(FS_header_t *handle, block_t *block) {
  if (block->content_type == Empty) {
    fprintf(stderr, "block is already clean\n");
    return NULL;
  }
  else if (block->content_type == File){
    /*STUB*/
  }
  else if (block->content_type == Directory){
    /*STUB*/
  }
  else if (block->content_type == Stockpile){
    freeblock_t *header = get_stockpile_header(block);
    // make sure stockpile is tail end of linked list;
    if (header->prev_block == -1 || header->next_block != -1) {
      fprintf(stderr, "only tail end of stockpile block may be deleted\n");
      return NULL;
    }
    // make sure there are no entries
    if (header->freeblock_count > 0) {
      fprintf(stderr, "must store no freeblocks to format\n");
      return NULL;
    }
    // make sure it is pointed to by handle / if block num is accurate
    if (handle->freeblock_tail != block->block_num) {
      fprintf(stderr, "handle->freeblock_tail is not storing this block's number\n");
      return NULL;
    }
    // finally do stuff
    // make previous block's next to -1
    block_t* prev_block = retrieve_block((void*)handle, header->prev_block);
    freeblock_t* prev_block_header = get_stockpile_header(prev_block);
    prev_block_header->next_block = -1;

    // make handle->tail point to prev block
    handle->freeblock_tail = header->prev_block;

    //format block
    char *zeroes = (char*)header;
    for (int i=0; i<BLOCK_SIZE-sizeof(block_t); i++) {
      zeroes[i] = 0;
    }

    // convert block type to Empty
    block->content_type = Empty;

    // put size to initial
    block->bytes_occupied = sizeof(block_t);

    return block;
  }
  fprintf(stderr, "invalid block content type\n");
  return NULL;
}

block_t* get_stockpile_block(void *fsptr, int block_num) {
  block_t *empty_block = retrieve_block(fsptr, block_num);
  // error if block specified is not empty
  if (empty_block->content_type != Empty || empty_block->bytes_occupied > sizeof(block_t)) {
    fprintf(stderr, "ERROR: cannot convert non-empty block\n");
    return NULL;
  }
  // initialize default stockpile values
  empty_block->content_type = Stockpile;

  freeblock_t *freeblock_header = (freeblock_t*)(((void*)empty_block)+sizeof(block_t));
  freeblock_header->next_block = -1;
  freeblock_header->prev_block = -1;
  empty_block->bytes_occupied = sizeof(block_t)+sizeof(freeblock_t);

  return empty_block;
}

// internal function to push the number into the stockpile block, does not check if full or if it will fit
int __push_free_block_num(FS_header_t *handle, block_t *stockpile_block, int block_num) {
  freeblock_t *header = (freeblock_t*)(((void*)stockpile_block)+sizeof(block_t));
  int *numbers = (int*)(((void*)header)+sizeof(freeblock_t));

  int count = header->freeblock_count;
  numbers[count] = block_num;
  stockpile_block->bytes_occupied += sizeof(int);
  header->freeblock_count++;
  handle->freeblock_count++;
  return 0;
}

// used to push the cleared block back on the stack for others to use
int push_free_block_num(FS_header_t *handle, int block_num) {
  _Bool is_empty = retrieve_block((void*)handle, block_num)->content_type == Empty;
  if (!is_empty) {
    fprintf(stderr, "block_num describes non-empty block\n");
    return -1;
  }

  block_t* stockpile = retrieve_block((void*)handle, handle->freeblock_tail);

  _Bool array_is_full = BLOCK_SIZE-stockpile->bytes_occupied < sizeof(int);
  if (array_is_full) {
    block_t* new_stockpile = get_stockpile_block((void*)handle, block_num);
    freeblock_t* new_header = get_stockpile_header(new_stockpile);
    new_header->prev_block = handle->freeblock_tail;
    handle->freeblock_tail = block_num;
  }
  else {
    __push_free_block_num(handle, stockpile, block_num);
  }
  return 0;
}

int pop_free_block_num(FS_header_t *handle) {
  // if there is no freeblocks in the stockpile, empty stockpile and offer it as freeblock, change handle tail to prev block
  if (handle->freeblock_tail == -1) {
    fprintf(stderr, "ERROR: Out of space\n");
    return -1;
  }
  block_t* stockpile = retrieve_block((void*)handle, handle->freeblock_tail);
  freeblock_t* header = get_stockpile_header(stockpile);
  int* array = get_stockpile_num_array(stockpile);

  int last_element = header->freeblock_count-1;
  if (header->freeblock_count > 0) {
    int block_num = array[last_element];
    // delete the remnants
    array[last_element] = 0;
    header->freeblock_count--;
    handle->freeblock_count--;
    return block_num;
  } else if (header->freeblock_count == 0){
    // convert block into free block
    block_t* cleared_block = clean_block(handle, stockpile);
    return cleared_block->block_num;
  } else {
    fprintf(stderr, "ERROR: freeblock count is off\n");
    return -1;
  }
  return 0;
}

int setup_free_blocks(FS_header_t *handle, int starting_block) {
  block_t *stockpile_block = get_stockpile_block((void*)handle, starting_block);
  freeblock_t *header = (freeblock_t*)(((void*)stockpile_block)+sizeof(block_t));

  _Bool has_enough_space = 1;
  // goes from n-2 to 0, uinitialized points to 0 (reserved for root directory "/")
  for (int i=handle->total_blocks-2; i>=0; i--) {
    has_enough_space = BLOCK_SIZE - stockpile_block->bytes_occupied >= 4;
    if (has_enough_space) {
      __push_free_block_num(handle, stockpile_block, i);
    } else {
      // append to linked list, update handle->tail
      int prev_num = stockpile_block->block_num;
      header->next_block = i;
      handle->freeblock_tail = i;
      stockpile_block = get_stockpile_block((void*)handle, i);
      header = get_stockpile_header(stockpile_block);
      header->prev_block = prev_num;
    }
  }
  return 0;
}

block_t* get_free_block(FS_header_t *handle) {
  return retrieve_block((void*)handle, pop_free_block_num(handle));
}

int find_empty_entry(block_t *dir_block) {
  // assume push and pop for now
  directory_t *dir_header = get_directory_header(dir_block);
  entry_t *dir_entries = get_directory_entries(dir_block);
  int search_this_many = dir_header->entry_count+1;
  for (int i = 0; i<search_this_many; i++) {
    if (strncmp(dir_entries[i].file_name,"\0\0\0\0\0",5)) {
      return i;
    }
  }
  return -1;
}

block_t* get_file_block(FS_header_t *handle) {
  // creates an inode referring to all the files as well as the file_t
  block_t *file_block = get_free_block(handle);
  file_block->content_type = File;
  file_t *file_header = get_file_header(file_block);

  // set the time
  set_file_time(file_header, TRUE);

  return file_block;
}

block_t* get_dir_block(FS_header_t *handle) {
  block_t *dir_block = get_free_block(handle);
  dir_block->content_type = Directory;
  directory_t *dir_header = get_directory_header(dir_block);
  dir_header->next_block = -1;
  dir_header->entry_count = 0;

  // set the time
  set_dir_time(dir_header, TRUE);

  return dir_block;
}

int __update_furthest_index(int furthest, entry_t *entries) {
  for (int i = furthest-1; i>=0; i--) {
    if (strncmp(entries[i].file_name, "\0", 1) != 0) {
      return i;
    }
  }
  return 0;
}

int __clear_entry(entry_t *entries, int i) {
  // only have to clear to the first null
  entries[i].block_num = 0;
  char *fill_null = (char*)(&entries[i]);
  for (int i=0; i<CHAR_LIMIT_INCLUDE_NULL; i++) {
    if (fill_null[i] == '\0') {
      break;
    }
    fill_null[i] = '\0';
  }
  return 0;
}

// removes file/ directory entry from directory entry array
int __remove_entry(block_t *dir_block, int block_num) {
  directory_t *dir_header = get_directory_header(dir_block);
  entry_t *dir_entries = get_directory_entries(dir_block);
  // find if there's any entries not in use
  for (int i=0; i<=dir_header->furthest_index; i++) {
    if (strncmp(dir_entries[i].file_name, "\0", 1) != 0) {
      if (dir_entries[i].block_num == block_num) {
        __clear_entry(dir_entries, i);
        dir_header->entry_count--;
        dir_block->bytes_occupied -= sizeof(entry_t);
        if (i >= dir_header->furthest_index-1) {
          dir_header->furthest_index -= 1; // __update_furthest_index(dir_header->furthest_index, dir_entries);
        }
        set_dir_time(dir_header, TRUE);
        return 0;
      }
    }
  }
  return -1;
}

// inserts the file/directory content into the directory's entry array
int __insert_entry(block_t *dir_block, char *name, int block_num) {
  directory_t *dir_header = get_directory_header(dir_block);
  entry_t *dir_entries = get_directory_entries(dir_block);
  // check if there's space
  _Bool has_space = BLOCK_SIZE - dir_block->bytes_occupied > sizeof(int);
  if (!has_space) {
    // todo: add new page to directory
    fprintf(stderr, "directory is out of space!\n");
    return -1;
  }
  // find if there's any entries not in use
  for (int i=0; i<=dir_header->furthest_index; i++) {
    if (strncmp(dir_entries[i].file_name, "\0", 1) == 0) {
      // add entry HERE
      strcpy(dir_entries[i].file_name, name);
      dir_entries[i].block_num = block_num;
      dir_header->entry_count++;
      if (i >= dir_header->furthest_index-1) {
        dir_header->furthest_index = i+1;
      }
      dir_block->bytes_occupied += sizeof(entry_t);
      // modify time
      set_dir_time(dir_header, TRUE);
      return 0;
    }
  }
  return -1;
}

int new_entry(block_t *parent, block_t *content_block, char *name) {
  // check if parent is directory_t
  if (parent->content_type != Directory) {
    fprintf(stderr, "parent must be a directory\n");
    return -1;
  }
  if (!(content_block->content_type == File || content_block->content_type == Directory)) {
    fprintf(stderr, "can only insert new directories and files\n");
    return -1;
  }
  return __insert_entry(parent, name, content_block->block_num);
}

int remove_entry(block_t *parent, block_t *content_block) {
  // check if parent is directory_t
  if (parent->content_type != Directory) {
    fprintf(stderr, "parent must be a directory\n");
    return -1;
  }
  if (!(content_block->content_type == File || content_block->content_type == Directory)) {
    fprintf(stderr, "can only remove directories and files\n");
    return -1;
  }
  if (content_block->content_type == Directory) {
    directory_t *temp_header = get_directory_header(content_block);
    if (temp_header->entry_count > 0) {
      fprintf(stderr, "directory must be empty\n");
      return -1;
    }
  }
  return __remove_entry(parent, content_block->block_num);
}

// int create_directory(FS_header_t *handle, block_t *parent) {
//   block_t *dir_block = get_dir_block(handle);
//   block_t
// }

// int create_file(FS_header_t *handle, block_t *dir_block, const char *name) {
//   // check if dir_block is directory_t
//   directory_t *dir_header = get_directory_header(dir_block);
//   entry_t *dir_entries = get_directory_entries(dir_block);
//
//   int count = dir_header->entry_count;
//   strcpy(dir_entries[count].file_name, name);
//   int file_start = get_file_block(handle)->block_num;
//   dir_entries[count].block_num = file_start;
//   dir_header->entry_count++;
//   return 0;
// }

int create_root_directory(FS_header_t *handle) {
  block_t *dir_block = get_dir_block(handle);
  handle->root_dir = dir_block->block_num;
  return 0;
}

// allocates blocks for filesystem and sets up the globals_handle
int setup_filesystem(FS_header_t *handle, size_t fssize, int *errnoptr) {
  size_t total_storage_bytes = fssize - START_OFFSET;
  int total_blocks = total_storage_bytes/BLOCK_SIZE;
  handle->total_blocks = total_blocks;
  handle->is_setup = TRUE;
  handle->freeblock_tail = START_OFFSET;
  handle->freeblock_count = total_blocks;
  // setup up freeblock system (stockpiles grow from the bottom up)
  initialize_blocks(handle);
  setup_free_blocks(handle, total_blocks-1);
  // setup the root directory
  create_root_directory(handle);
  // add entry to directory
  return 0;
}




size_t str_len(char *str) {
  size_t length = 0;
  for (char *c = str; *c; c++) {
    length++;
  }
  return length;
}

_Bool is_dir(block_t *block) {
  if (block->content_type == Directory) {
    return 1;
  }
  return 0;
}

int search_directory(block_t *dir_block, char* file_name) {
  directory_t *dir_header;
  entry_t *dir_entries;

  if (!is_dir(dir_block)) {
    fprintf(stderr, "cannot search into non directory block\n");
    return -1;
  }

  dir_header = get_directory_header(dir_block);
  dir_entries = get_directory_entries(dir_block);
  // assumes push and pop directories for now
  int count = dir_header->entry_count;
  for (int i = 0; i < count; i++) {
    if (strncmp(dir_entries[i].file_name,"\0", 1) != 0) {
      if (strcmp(dir_entries[i].file_name, file_name) == 0) {
        return dir_entries[i].block_num;
      }
    }
  }
  return -1;
}

block_t* find_root (FS_header_t *handle) {
  return retrieve_block((void*)handle, handle->root_dir);
}

block_t* resolve_path(FS_header_t *handle, const char *path) {
  // working dir support?
  // if path begins with /
  char *temp,*found;
  block_t *root_dir = find_root(handle);
  block_t  *prev_dir;
  int result;

  if (strncmp(path, PATH_SEPARATOR, 1) != 0) {
    fprintf(stderr, "path must start with /\n");
    return NULL;
  }

  if (strcmp(path, PATH_SEPARATOR)==0) {
    return root_dir;
  }

  temp = strdup(path);
  prev_dir = root_dir;
  while ((found = strsep(&temp, PATH_SEPARATOR)) != NULL ) {
      if ((result=search_directory(prev_dir, found)) != -1) {
        prev_dir = retrieve_block((void*)handle, result);
      }
  }
  free(temp);
  return prev_dir;
  // split path into tokens / / /
  // get index of each / token
  // read between the slashes
  // find /, find root, find dir, find file.txt
}

block_t* resolve_parent(FS_header_t *handle, const char *path) {
  // working dir support?
  // if path begins with /
  char *temp,*found;
  block_t *root_dir = find_root(handle);
  block_t  *prev_dir, *parent;
  int result;

  if (strncmp(path, PATH_SEPARATOR, 1) != 0) {
    fprintf(stderr, "path must start with /\n");
    return NULL;
  }

  if (strcmp(path, PATH_SEPARATOR)==0) {
    return root_dir;
  }
  temp = strdup(path);
  prev_dir = root_dir;
  while ((found = strsep(&temp, PATH_SEPARATOR)) != NULL ) {
      if ((result=search_directory(prev_dir, found)) != -1) {
        parent = prev_dir;
        prev_dir = retrieve_block((void*)handle, result);
      }
  }
  free(temp);
  return parent;
  // split path into tokens / / /
  // get index of each / token
  // read between the slashes
  // find /, find root, find dir, find file.txt
}

void test_program(FS_header_t *handle, size_t fssize, int *errnoptr) {
  block_t *root = get_dir_block(handle);
  block_t *dir = get_dir_block(handle);
  block_t *file = get_file_block(handle);
  block_t *file2 = get_file_block(handle);

  new_entry(find_root(handle), root, "root");
  new_entry(root, dir, "dir");
  new_entry(dir, file, "file.txt");
  new_entry(dir, file2, "file2.txt");

  block_t *result_block = resolve_path(handle, "/root/dir/file.txt");

  remove_entry(dir, result_block);
  remove_entry(root, dir);
  remove_entry(dir, file2);
  block_t *new = get_dir_block(handle);
  new_entry(dir, new, "new");
  remove_entry(dir, file);
  remove_entry(root, dir);

  block_t *text = get_file_block(handle);
  new_entry(new, text, "text.txt");
}

FS_header_t* get_handle(void *fsptr, size_t fssize, int *errnoptr) {
  // write some stuff at 0
  FS_header_t *handle = (FS_header_t *) fsptr;
  if (!handle->is_setup) {
    setup_filesystem(handle, fssize, errnoptr);
  }
  // get a block, cast it into a file struct, write a long string into the file, read the string
  // test_program(handle, fssize, errnoptr);
  return handle;

}





/* End of helper functions */

/* Implemegetnts 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) {
  // get the handle / table of everything
  FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
  if (handle == NULL) {
    *errnoptr = EFAULT;
    return -1;
  }
  block_t* block = resolve_path(handle, path);
  if (block == NULL) {
    *errnoptr = ENOENT;
    return -1;
  }
  // flush buffer
  memset(stbuf, 0, sizeof(struct stat));

  stbuf->st_uid = uid;
  stbuf->st_gid = gid;
  if (block->content_type == Directory) {
    directory_t *dir_header = get_directory_header(block);
    stbuf->st_mode = S_IFDIR | 0755;
    stbuf->st_nlink = get_directory_header(block)->entry_count+2; //+2 counts . and ..
    stbuf->st_atim = dir_header->atim;
    stbuf->st_mtim = dir_header->mtim;
  }
  else if (block->content_type == File) {
    file_t *file_header = get_file_header(block);
    stbuf->st_mode = S_IFREG | 0755;
    stbuf->st_nlink = 1;
    stbuf->st_size = block->bytes_occupied;
    stbuf->st_atim = file_header->atim;
    stbuf->st_mtim = file_header->mtim;
  }

  // figure out if it's a directory or file
  //struct timespec currTime; // this variable is on the stack so is that ok?
  //clock_gettime(CLOCK_REALTIME, &currTime);
  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.

*/

void free_string_array(char **names, int entries) {
  for (int i=0; i<entries; i++) {
    free(names[i]);
  }
  free(names);
}

char** get_names_array(block_t *block, int entries, int *errnoptr) {
  entry_t *dir_entries = get_directory_entries(block);
  char **names = calloc(entries, sizeof(char *));
  if (names == NULL) {
    *errnoptr = EINVAL;
    return NULL;
  }
  for (int i = 0; i < entries; i++) {
    // duplicate file name to name
    char *name = strdup(dir_entries[i].file_name);
    // fail if memory alloc didnt work
    if (name == NULL) {
      free_string_array(names, i);
      *errnoptr = EINVAL;
      return NULL;
    }
    // add to names
    names[i] = name;
  }
  return names;
}


int __myfs_readdir_implem(void *fsptr, size_t fssize, int *errnoptr,
                          const char *path, char ***namesptr) {

  FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
  if (handle == NULL) {
    *errnoptr = EFAULT;
    return -1;
  }

  block_t* block = resolve_path(handle, path);
  if (block == NULL) {
    *errnoptr = ENOENT;
    return -1;
  }
  // check that its a dir
  if (!(block->content_type == Directory)) {
    *errnoptr = ENOTDIR;
    return -1;
  }
  directory_t *dir_header = get_directory_header(block);
  int entries = dir_header->entry_count;
  // set the time
  set_dir_time(dir_header, FALSE);
  // check that it has children
  if (entries <= 0) {
    return 0;
  }
  // point the array of strings pointer to an array of the file names
  *namesptr = get_names_array(block, entries, errnoptr);
  if (*namesptr == NULL) {
    return -1;
  }
  return entries;
}

/* 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.

*/
void get_new_name(const char *path, char **new_name) {
  *new_name = strrchr(path, PATH_CHAR)+1;
}

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

  FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
  if (handle == NULL) {
    *errnoptr = EFAULT;
    return -1;
  }

  block_t *parent = resolve_parent(handle, path);
  block_t *file = get_file_block(handle);
  char *new_name;
  get_new_name(path, &new_name);

  new_entry(parent, file, new_name);
  // block_t* block = resolve_path(handle, path);
  // if (block == NULL) {
  //   *errnoptr = ENOENT;
  //   return -1;
  // }

  return 0;
}

/* 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) {
  /* STUB */
  return -1;
}

/* 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) {
  /* STUB */
  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) {
  char *new_name;
  block_t *parent, *directory;

  if (path == NULL) {
    *errnoptr = ENOENT;
    return -1;
  }

  FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
  if (handle == NULL) {
    *errnoptr = EFAULT;
    return -1;
  }

  parent = resolve_parent(handle, path);
  directory = get_dir_block(handle);

  get_new_name(path, &new_name);

  new_entry(parent, directory, new_name);
  return 0;
}

/* 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) {
  /* STUB */
  return -1;
}

/* 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 __myfs_truncate_implem(void *fsptr, size_t fssize, int *errnoptr,
                           const char *path, off_t offset) {
  /* STUB */
  return -1;
}

/* 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) {

  FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
  if (handle == NULL) {
   *errnoptr = EFAULT;
   return -1;
  }

  block_t* block = resolve_path(handle, path);
  if (block == NULL) {
    *errnoptr = ENOENT;
    return -1;
  }

  return 0;
}

/* 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) {
  /* STUB */
  return -1;
}

/* 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) {
  /* STUB */
  return -1;
}

/* 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]) {

  FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
  if (handle == NULL) {
    *errnoptr = EFAULT;
    return -1;
  }

  block_t* block = resolve_path(handle, path);
  if (block == NULL) {
    *errnoptr = ENOENT;
    return -1;
  }

  if (block->content_type == Directory) {
    directory_t *dir_header = get_directory_header(block);
    dir_header->atim = ts[0];
    dir_header->mtim = ts[1];
  }
  else if (block->content_type == File) {
    file_t *file_header = get_file_header(block);
    file_header->atim = ts[0];
    file_header->mtim = 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) {
 FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
 if (handle == NULL) {
   *errnoptr = EFAULT;
   return -1;
 }

 stbuf->f_bsize = BLOCK_SIZE;
 stbuf->f_blocks = handle->total_blocks;
 stbuf->f_bfree = handle->freeblock_count;
 stbuf->f_bavail = handle->freeblock_count;
 stbuf->f_namemax = CHAR_LIMIT_INCLUDE_NULL;
 return 0;
}