// CSC_4730 | P8 | Crusade Against File System Corruption; with c++11| Caleb A. Collar | 12.4.21

// Includes:
#include "fs.h"
#include "types.h"
#include <algorithm>
#include <fcntl.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#include <vector>

// Definitions:
#define T_UNUSED 0 // Unused
#define T_DIR 1    // Directory
#define T_FILE 2   // File
#define T_DEV 3    // Special device

// Set the file's namespace:
using namespace std;

// Globals:
const uint pad = 25;

struct inode {
  uint inode;
  uint numLinks;
  uint links;
  uint type;
  bool allocated;
  bool inDir = false;
};

struct block {
  uint block;
  uint references = 0;
  bool allocated = false;
};

struct dir {
  uint inode;
  uint numLinks;
  uint links;
  uint type;
};

struct fsMembers {
  void *fsImage;
  superblock *sb;
  vector<inode> files;
  vector<dinode *> dinodeDirs;
  vector<dir> dirs;
  vector<inode> unused;
  vector<dinode *> special;
  vector<dirent *> dirents;
  vector<block> bitmappedBlocks;
  vector<dinode *> dinodes;
};

// Method declarations:
// Create a pointer to Superblock, this is the return of the handle function. Handle printouts of superblock.
superblock *HandleSuperblock(char **const &argv, void *fs) {
  superblock *sb = (superblock *)((char *)fs + BSIZE);
  struct stat fileSystem;
  stat(argv[1], &fileSystem);
  // If Superblock is not the correct size.
  if (fileSystem.st_size / BSIZE != sb->size) { // If the file system size is disputed.
    cout << "Superblock Info:" << endl;
    cout << left << setw(pad) << "FS Size in blocks:" << sb->size << endl;
    cout << left << setw(pad) << "Number of data blocks:" << sb->nblocks << endl;
    cout << left << setw(pad) << "Number of inodes:" << sb->ninodes << endl;
    cout << left << setw(pad) << "Number of log blocks:" << sb->nlog << endl;
    cout << left << setw(pad) << "Log start block:" << sb->logstart << endl;
    cout << left << setw(pad) << "BM start block:" << sb->bmapstart << endl;
    cout << left << setw(pad) << "Data blocks start at: " << sb->inodestart << endl;
    cout << left << setw(pad) << "Superblock Status:" << "BAD" << endl;
    cout << "Incorrect size of Superblock..." << endl;
    cout << left << setw(pad) << "Superblock reported size:" << sb->size << endl;
    munmap(fs, BSIZE * 1024);
    exit(1);
  } else { // Else print out the qualities that are needed.
    cout << "Superblock Info:" << endl;
    cout << left << setw(pad) << "FS Size in blocks:" << sb->size << endl;
    cout << left << setw(pad) << "Number of data blocks:" << sb->nblocks << endl;
    cout << left << setw(pad) << "Number of inodes:" << sb->ninodes << endl;
    cout << left << setw(pad) << "Number of log blocks:" << sb->nlog << endl;
    cout << left << setw(pad) << "Log start block:" << sb->logstart << endl;
    cout << left << setw(pad) << "BM start block:" << sb->bmapstart << endl;
    cout << left << setw(pad) << "Data blocks start at: " << sb->inodestart << endl;
    cout << left << setw(pad) << "Superblock Status:" << "OK" << endl;
  }
  return sb;
}

// pass CheckInodeSize the array of inodes
bool CheckInodeSize(vector<dinode *> d, uint size) {
  bool valid = true;
  // check if each one's -size is < (512 * MAXFILE)
  for (uint i = 0; i < size; i++) {
    if ((d[i])->size > (512 * MAXFILE)) {
      cout << "inode " << i << " has invalid size." << endl;
      valid = false;
      break;
    }
  }
  return valid;
}

// Check number of blocks.
bool NumBlocks(superblock *sb) {
  bool retval = false;
  if ((sb->nblocks + sb->bmapstart + 1) != sb->size) {
    retval = true;
    cout << "There is an invalid number of blocks listed in the superblock. The number should be " << (sb->size - sb->bmapstart - 1) << endl;
  }
  return retval;
}

// Parse image for directories, files, special, or unused.
void ParseFs(fsMembers *members) {
  for (uint i = 0; i < members->sb->ninodes - 1; i++) {
    // Is unused
    if (members->dinodes[i]->type == T_UNUSED) {
      inode temp;
      temp.inode = i;
      temp.numLinks = members->dinodes[i]->nlink;
      temp.type = members->dinodes[i]->type;
      members->unused.push_back(temp);
    }
    // Is directory
    else if (members->dinodes[i]->type == T_DIR) {
      dir temp;
      temp.numLinks = members->dinodes[i]->nlink;
      temp.inode = i;
      temp.type = members->dinodes[i]->type;
      members->dirs.push_back(temp);
      members->dinodeDirs.push_back(members->dinodes[i]);
    }
    // Is file
    else if (members->dinodes[i]->type == T_FILE) {
      inode temp;
      temp.inode = i;
      temp.numLinks = members->dinodes[i]->nlink;
      temp.type = members->dinodes[i]->type;
      members->files.push_back(temp);
    }
    // Is special
    else if (members->dinodes[i]->type == T_DEV) {
      members->special.push_back(members->dinodes[i]);
    }
  }
}

//Check if inode 0 should be allocated.
bool InodeZeroDir(vector<dinode *> d) {
  bool retval = false;
  if (d[0]->type != 0) {
    cout << "The first inode is allocated." << endl;
    retval = true;
  }
  return retval;
}

// Check if inode 1 is not a directory.
bool InodeOneDir(vector<dinode *> d) {
  bool retval = false;
  if (d[1]->type != 1) {
    cout << "Inode one is not a directory." << endl;
    retval = true;
  }
  return retval;
}

// Check if first two names are . and ..
bool FirstNamesInDir(vector<dirent *> dirents) {
  bool retval = false;
  if (dirents.at(0)->name[0] != '.') {
    cout << "Directory " << dirents.at(0)->inum << ", does not have its first directory set to \".\" " << endl;
    retval = true;
  }
  else if (dirents.at(1)->name[0] != '.' || dirents.at(1)->name[1] != '.') {
    cout << "Directory " << dirents.at(1)->inum << ", does not have its second directory set to \"..\" " << endl;
  }
  return retval;
}

// Check if an inode is unused.
bool InodeUnused(vector<inode> inode_vec) {
  bool retval = false;
  for (uint i = 0; i < inode_vec.size(); i++) {
    if (inode_vec.at(i).type != 0 && inode_vec.at(i).inDir == false) {
      cout << "Inode " << inode_vec.at(i).inode << ", is marked as valid but is not referenced by a directory. " << endl;
      retval = true;
      break;
    }
  }
  return retval;
}

// An inode is found in a valid directory but is not marked as allocated.
bool InodeMissing(vector<inode> unused_inode_vec) {
  bool retval = false;
  for (uint i = 0; i < unused_inode_vec.size(); i++) {
    if (unused_inode_vec.at(i).type == 0 && unused_inode_vec.at(i).inDir == true) {
      cout << "Inode Number " << unused_inode_vec.at(i).inode << ", is found in a valid directory but is not marked as allocated." << endl;
      retval = true;
      break;
    }
  }
  return retval;
}

//Check for missing blocks.
bool MissingBlock(fsMembers *members) {
  bool retval = false;
  vector<uint> referenceToBlock;
  for (uint i = 0; i < members->sb->ninodes - 1; i++) { 
    for (uint j = 0; j < NDIRECT + 1; j++) {
      if (j == NDIRECT) {                                   
        uint indirect = members->dinodes[i]->addrs[j]; 
        referenceToBlock.push_back(members->dinodes[i]->addrs[j]);
        uint *ptr = (uint *)members->fsImage + (indirect * BSIZE) / 4;
        for (int k = 0; k < 128; k++) {
          referenceToBlock.push_back(*ptr); 
          ptr++;                           
        }

      } else {
        referenceToBlock.push_back(members->dinodes[i]->addrs[j]); 
      }
    }
  }
  bool found = false;
  for (uint i = members->sb->bmapstart + 1; i < members->bitmappedBlocks.size(); i++) {
    if (members->bitmappedBlocks[i].allocated == true) {
      found = false;
      for (uint j = 0; j < referenceToBlock.size(); j++) {
        if (referenceToBlock[j] == i) {
          found = true; 
          break;
        }
      }
      if (found == false) {
        cout << "Bitmap data suggests block " << i
             << " is allocated, but it does not belong to any file or "
                "directory."
             << endl;
        retval = true;
        break;
      }
    }
  }
  return retval;
}

//Check if inode ine is root.
bool InodeOneIsNotRoot(vector<dirent *> dirents) {
  bool retval = false;
  for (uint i = 2; i < dirents.size(); i++) {
    if (dirents.at(i)->name[0] == '.' && dirents.at(i)->name[1] != '.' && dirents.at(i)->inum == 1) {
      cout << "A non-root directory lists itself as inode 1." << endl;
      retval = true;
      break;
    }
  }
  return retval;
}

//Directory links more than once not including . or ..
bool DirectoryLoop(vector<dirent *> dirents) {
  vector<char *> names;
  bool retval = false;
  for (uint i = 0; i < dirents.size(); i++) {
    if (dirents.at(i)->name[0] == '.')
      continue;
    if (std::find(names.begin(), names.end(), dirents.at(i)->name) != names.end()) {
      cout << "Directory " << dirents.at(i)->name << " appears more than once. " << endl;
      retval = true;
      break;
    } else {
      names.push_back(dirents.at(i)->name);
    }
  }
  return retval;
}

//Check for valid links.
bool ValidDir(vector<dirent *> dirents, vector<dinode *> d) {
  bool retval = false;
  for (uint i = 0; i < dirents.size(); i++) {
    // if name is . or ..
    if (dirents.at(i)->name[0] == '.') {
      if (d[dirents.at(i)->inum]->type != 1) {
        cout << "Name of File in inode " << dirents.at(i)->inum << ", is \".\", or \"..\" but doesn't link to a directory." << endl;
        retval = true;
        break;
      }
    }
  }
  return retval;
}

// Check number of links is valid.
bool LinkCount(vector<dirent *> dirents, vector<inode> files) {
  bool retval = false;
  for (uint i = 0; i < files.size(); i++) {
    uint referenced = files.at(i).numLinks;
    uint linked = 0;
    for (uint j = 0; j < dirents.size(); j++) {
      if (dirents.at(j)->inum == files.at(i).inode)
        linked++;
    }
    if (linked != referenced) {
      cout << "File " << files.at(i).inode << " has a disputed file link count. The reported correct link number is " << linked << endl;
      retval = true;
      break;
    }
  }
  return retval;
}

// Check directory link number is valid.
bool DirLinkCount(vector<dirent *> dirents, vector<dir> dirs) {
  bool retval = false;
  for (uint i = 0; i < dirs.size(); i++) {
    uint referenced = dirs.at(i).numLinks;
    uint linked = 0;
    for (uint j = 0; j < dirents.size(); j++) {
      if (dirents.at(j)->inum == dirs.at(i).inode)
        linked++;
    }
    if (linked != referenced) {
      cout << "Directory " << dirs.at(i).inode << " has a disputed file link count. The reported correct link number is " << linked << endl;
      retval = true;
      break;
    }
  }
  return retval;
}

//Check for unallocated blocks.
bool UnallocatedBlock(fsMembers *members) {
  bool retval = false;
  for (uint i = 0; i < members->sb->ninodes - 1; i++) {
    for (int j = 0; j < NDIRECT + 1; j++) {
      if (members->dinodes[i]->addrs[j] > members->bitmappedBlocks.size()) {
        continue;
      } else if (j == NDIRECT) {
        uint indirectBlock = (members->dinodes[i]->addrs[j]);
        if (indirectBlock > (members->sb->nblocks)) { 
          break;
        }
        if (members->dinodes[i]->addrs[j] == 1) {
          continue;
        }
        uint *ptr = (uint *)members->fsImage + (indirectBlock * BSIZE) / 4;
        for (int k = 0; k < 128; k++) { 
          if (*ptr > members->sb->nblocks) {
            cout << "Inode address points to an unallocated block." << endl;
            retval = true;
            goto end;
          }
          if ((*ptr != 0) && (members->bitmappedBlocks[*ptr].allocated == false)) {
            cout << "Bitmap data suggests block, " << *ptr << " is free but it is referenced in a valid Inode." << endl;
            retval = true;
            goto end;
          }
          ptr++;
        }
      }
      else if ((members->dinodes[i]->addrs[j + 1] != 0) && (members->bitmappedBlocks[members->dinodes[i]->addrs[j + 1]].allocated == false)) {
        cout << "Bitmap data suggests block, " << members->bitmappedBlocks[members->dinodes[i]->addrs[j + 1]].block << " is free but it is referenced in a valid Inode." << endl;
        retval = true;
        break;
      }
    }
  }
  end:
  return retval;
}

//Check for multiply allocated blocks.
bool MultiplyAllocatedBlock(fsMembers *members) {
  bool retval = false;
  int blockLog[members->sb->nblocks];
  for (uint i = 0; i < members->sb->nblocks; i++) {
    blockLog[i] = 0;
  }
  for (uint i = 0; i < members->sb->ninodes - 1; i++) {
    for (uint j = 0; j < NDIRECT + 1; j++) {
      if (members->dinodes[i]->addrs[j] > members->bitmappedBlocks.size()) {
        continue;
      } else if (j == NDIRECT) {
        uint indirectBlock = (members->dinodes[i]->addrs[j]);
        if (indirectBlock > (members->sb->nblocks)) { 
          break;
        }
        if (members->dinodes[i]->addrs[j] == 1) {
          continue;
        }
        uint *ptr = (uint *)members->fsImage + (indirectBlock * BSIZE) / 4;
        for (int k = 0; k < 128; k++) { 
          if (*ptr > members->sb->nblocks) {
            cout << "Inode address points to an invalid block" << endl;
            retval = true;
            goto end;
          }
          blockLog[*ptr]++;
          ptr++;
        }
      } else {
        blockLog[members->dinodes[i]->addrs[j]]++;
      }
    }
  }
  for (uint i = 1; i < members->sb->nblocks; i++) {
    if (blockLog[i] > 1) {
      cout << "Block " << i << ", is found more than once in the inodes:" << endl;
      for (uint j = 0; j < members->sb->ninodes - 1; j++) {
        for (uint k = 0; k < NDIRECT + 1; k++)
          if (members->dinodes[j]->addrs[k] == i) {
            cout << j << endl;
          }
      }
      retval = true;
      goto end;
    }
  }
  end:
  return retval;
}

//Read in the image file.
void *ReadImageFile(char **const &argv) {
  int fd = -1;
  // Making sure file system was given in command line correctly.
  if ((fd = open(argv[1], O_RDONLY)) < 0) {
    perror("Image file failed to be read.");
    close(fd);
    exit(1);
  }
  // Reading in File System at 512*1024 size.
  void *fs = mmap(nullptr, BSIZE * 1024, PROT_READ, MAP_SHARED, fd, 0);
  if (fs == MAP_FAILED) {
    perror("Unable to map image file.");
    munmap(fs, BSIZE * 1024);
    close(fd);
    exit(1);
  }
  close(fd);
  return fs;
}

//Handle the bitmap block data.
void HandleBitmap(fsMembers *members) {
  members->bitmappedBlocks.resize(members->sb->size);
  uchar *bitmap_ptr = (uchar *)((char *)members->fsImage + (members->sb->bmapstart * BSIZE));
  uchar *bitmap[members->sb->size / 8];
  for (uint i = 0; i < members->sb->size / 8; i++) {
    bitmap[i] = bitmap_ptr;
    for (uint j = 0; j < 8; j++) {
      members->bitmappedBlocks[(i * 8) + j].allocated = ((*bitmap[i] >> (7 - j)) & 0x01);
      members->bitmappedBlocks[(i * 8) + j].block = (i * 8) + j;
    }
    bitmap_ptr++;
  }
  for (uint i = 0; i < members->sb->ninodes - 1; i++) {
    for (uint j = 0; j < NDIRECT; j++) {
      if (j == NDIRECT) {
        uint indirectBlock = (members->dinodes[i]->addrs[j]);
        if (indirectBlock > (members->sb->nblocks)) {
          break;
        }
        if (members->dinodes[i]->addrs[j] == 1) {
          continue;
        }
        uint *ptr = (uint *)members->fsImage + (indirectBlock * BSIZE) / 4;
        for (int k = 0; k < 128; k++) {
          members->bitmappedBlocks[(i * 8) + j].allocated = ((*bitmap[i] >> (7 - j)) & 0x01);
          ptr++;
        }
      }
      uint block_n = members->dinodes[i]->addrs[j];
      members->bitmappedBlocks[block_n].references++;
    }
  }
}

//Handle inodes.
void HandleInodes(fsMembers *members, char **const &argv) {
  members->dinodes.resize(members->sb->ninodes);
  dinode *i_ptr = (dinode *)((char *)members->fsImage + (members->sb->inodestart * BSIZE));
  for (uint i = 0; i < members->sb->ninodes - 1; i++) {
    members->dinodes[i] = i_ptr;
    i_ptr += 1;
  }
  if (!CheckInodeSize(members->dinodes, members->sb->ninodes - 1)) {
    munmap(members->fsImage, BSIZE * 1024);
    exit(1);
  }
}

//Handle inodes that are in directories or unused.
void HandleReferences(fsMembers *members) {
  // Iterate through the inodes that are directories.
  for (uint i = 0; i < members->dinodeDirs.size(); i++) {
    // Every directory size will be a multiple of BSIZE.
    for (uint k = 0; k < 11; k++) {
      dirent *data = (dirent *)(((uchar *)members->fsImage) + members->dinodeDirs[i]->addrs[k] * BSIZE);
      for (dirent *ptr = data; ptr != data + (BSIZE / sizeof(dirent)); ptr++) {
        if (ptr->inum != 0) {
          members->dirents.push_back(ptr);
        }
      }
    }
  }
  //Label inodes in directories.
  for (uint i = 0; i < members->files.size(); i++) {
    for (uint j = 0; j < members->dirents.size(); j++) {
      if (members->dirents.at(j)->inum == members->files.at(i).inode) {
        members->files.at(i).inDir = true;
      }
    }
  }
  // Label inodes that are unused.
  for (uint i = 0; i < members->unused.size(); i++) {
    for (uint j = 0; j < members->dirents.size(); j++) {
      if (members->dirents.at(j)->inum == members->unused.at(i).inode) {
        members->unused.at(i).inDir = true;
      }
    }
  }
}

//Method to check for each error type.
//Will exit upon finding first error in order that they are checked.
void CheckForErrors(fsMembers *members) {
  if (InodeUnused(members->files)) goto endCheck;
  if (InodeMissing(members->unused)) goto endCheck;
  if (NumBlocks(members->sb)) goto endCheck;
  if (InodeOneIsNotRoot(members->dirents)) goto endCheck;
  if (InodeOneDir(members->dinodes)) goto endCheck;
  if (InodeZeroDir(members->dinodes)) goto endCheck;
  if (FirstNamesInDir(members->dirents)) goto endCheck;
  if (DirectoryLoop(members->dirents)) goto endCheck;
  if (ValidDir(members->dirents, members->dinodes)) goto endCheck;
  if (LinkCount(members->dirents, members->files)) goto endCheck;
  if (DirLinkCount(members->dirents, members->dirs)) goto endCheck;
  if (MultiplyAllocatedBlock(members)) goto endCheck;
  if (MissingBlock(members)) goto endCheck;
  if (UnallocatedBlock(members)) goto endCheck;
  else {
    cout << "No errors found in this image." << endl;
  endCheck:
    munmap(members->fsImage, BSIZE * 1024);
    exit(1);
  }
}

//The main method.
int main(int argc, char *argv[]) {
  fsMembers members; //This struct holds parsed information on blocks and inodes.
  members.fsImage = ReadImageFile(argv);
  members.sb = HandleSuperblock(argv, members.fsImage);
  HandleInodes(&members, argv);
  HandleBitmap(&members);
  ParseFs(&members);
  HandleReferences(&members);
  CheckForErrors(&members);
  return 0;
}