derek alyssa fs.c

#include <cdefs.h>
#include <defs.h>
#include <file.h>
#include <fs.h>
#include <mmu.h>
#include <param.h>
#include <proc.h>
#include <sleeplock.h>
#include <spinlock.h>
#include <stat.h>

#include <buf.h>


// there should be one superblock per disk device, but we run with
// only one device
struct superblock sb;

// Read the super block.
void readsb(int dev, struct superblock *sb) {
  struct buf *bp;

  bp = bread(dev, 1);
  memmove(sb, bp->data, sizeof(*sb));
  brelse(bp);
}

// Inodes.
//
// An inode describes a single unnamed file.
// The inode disk structure holds metadata: the file's type,
// its size, the number of links referring to it, and the
// range of blocks holding the file's content.
//
// The inodes themselves are contained in a file known as the
// inodefile. This allows the number of inodes to grow dynamically
// appending to the end of the inode file. The inodefile has an
// inum of 1 and starts at sb.startinode.
//
// The kernel keeps a cache of in-use inodes in memory
// to provide a place for synchronizing access
// to inodes used by multiple processes. The cached
// inodes include book-keeping information that is
// not stored on disk: ip->ref and ip->flags.
//
// Since there is no writing to the file system there is no need
// for the callers to worry about coherence between the disk
// and the in memory copy, although that will become important
// if writing to the disk is introduced.
//
// Clients use iget() to populate an inode with valid information
// from the disk. idup() can be used to add an in memory reference
// to and inode. irelease() will decrement the in memory reference count
// and will free the inode if there are no more references to it,
// freeing up space in the cache for the inode to be used again.

struct {
  struct spinlock lock;
  struct inode inode[NINODE];
  struct inode inodefile;
} icache;

struct {
  struct buf bufs[LOGSIZE];
  struct sleeplock lock;
  uint size;
} log_cache;


// Find the inode file on the disk and load it into memory
// should only be called once, but is idempotent.
static void init_inodefile(int dev) {
  struct buf *b;
  struct dinode di;

  b = bread(dev, sb.inodestart);
  memmove(&di, b->data, sizeof(struct dinode));

  icache.inodefile.inum = INODEFILEINO;
  icache.inodefile.dev = dev;
  icache.inodefile.type = di.type;
  icache.inodefile.valid = 1;
  icache.inodefile.ref = 1;

  icache.inodefile.devid = di.devid;
  icache.inodefile.size = di.size;
  icache.inodefile.data[0] = di.data[0];
  for (int i = 1; i < 15; i++) {
    di.data[i].startblkno = 0;
    di.data[i].nblocks = 0;
    icache.inodefile.data[i] = di.data[i];
  }

  brelse(b);
}

void iinit(int dev) {
  int i;

  initlock(&icache.lock, "icache");
  for (i = 0; i < NINODE; i++) {
    initsleeplock(&icache.inode[i].lock, "inode");
  }
  initsleeplock(&icache.inodefile.lock, "inodefile");

  readsb(dev, &sb);
  cprintf("sb: size %d nblocks %d bmap start %d inodestart %d\n", sb.size,
          sb.nblocks, sb.bmapstart, sb.inodestart);
  log_recover();
  init_inodefile(dev);
}

static void read_dinode(uint inum, struct dinode *dip) {
  readi(&icache.inodefile, (char *)dip, INODEOFF(inum), sizeof(*dip));
}

// Find the inode with number inum on device dev
// and return the in-memory copy. Does not read
// the inode from from disk.
static struct inode *iget(uint dev, uint inum) {
  struct inode *ip, *empty;
  struct dinode dip;

  acquire(&icache.lock);

  // Is the inode already cached?
  empty = 0;
  for (ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++) {
    if (ip->ref > 0 && ip->dev == dev && ip->inum == inum) {
      ip->ref++;
      release(&icache.lock);
      return ip;
    }
    if (empty == 0 && ip->ref == 0) // Remember empty slot.
      empty = ip;
  }

  // Recycle an inode cache entry.
  if (empty == 0)
    panic("iget: no inodes");

  ip = empty;
  ip->ref = 1;
  ip->valid = 0;
  ip->dev = dev;
  ip->inum = inum;

  release(&icache.lock);

  //memset(&dip, 2, sizeof(dip));
  read_dinode(ip->inum, &dip);
  ip->type = dip.type;
  ip->devid = dip.devid;
  ip->size = dip.size;
  for (int i = 0; i < 15; i++) {
    ip->data[i] = dip.data[i];
    //memmove(ip->data, dip.data, 15 * sizeof(struct extent));
  }
  return ip;
}

// Increment reference count for ip.
// Returns ip to enable ip = idup(ip1) idiom.
struct inode *idup(struct inode *ip) {
  acquire(&icache.lock);
  ip->ref++;
  release(&icache.lock);
  return ip;
}

// Drop a reference to an in-memory inode.
// If that was the last reference, the inode cache entry can
// be recycled.
void irelease(struct inode *ip) {
  acquire(&icache.lock);
  // inode has no other references release
  if (ip->ref == 1)
    ip->type = 0;
  ip->ref--;
  release(&icache.lock);
}

// Lock the given inode.
// Reads the inode from disk if necessary.
void ilock(struct inode *ip) {
  struct dinode dip;

  if(ip == 0 || ip->ref < 1)
    panic("ilock");

  acquiresleep(&ip->lock);

  if (ip->valid == 0) {
    ilock(&icache.inodefile);
    read_dinode(ip->inum, &dip);
    iunlock(&icache.inodefile);

    ip->type = dip.type;
    ip->devid = dip.devid;

    ip->size = dip.size;
    //ip->data = dip.data;
    for (int i = 0; i < 15; i++) {
      ip->data[i] = dip.data[i];
    }

    ip->valid = 1;

    if (ip->type == 0)
      panic("iget: no type");
  }
}

// Unlock the given inode.
void iunlock(struct inode *ip) {
  if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
    panic("iunlock");

  releasesleep(&ip->lock);
}

// Lock the inode and copy stat information for inode.
void stati_wrapper(struct inode *ip, struct stat *st) {
  ilock(ip);
  stati(ip, st);
  iunlock(ip);
}

// Copy stat information from inode.
// Caller must hold ip->lock.
void stati(struct inode *ip, struct stat *st) {
  st->dev = ip->dev;
  st->ino = ip->inum;
  st->type = ip->type;
  st->size = ip->size;
}

// Lock the inode and read data from inode.
int readi_wrapper(struct inode *ip, char *dst, uint off, uint n) {
  int retval;

  ilock(ip);
  retval = readi(ip, dst, off, n);
  iunlock(ip);

  return retval;
}

// Read data from inode.
// Caller must hold ip->lock.
int readi(struct inode *ip, char *dst, uint off, uint n) {
  uint tot, m;
  struct buf *bp;

  if (ip->type == T_DEV) {
    if (ip->devid < 0 || ip->devid >= NDEV || !devsw[ip->devid].read)
      return -1;
    return devsw[ip->devid].read(ip, dst, n);
  }

  if (off > ip->size || off + n < off)
    return -1;
  if (off + n > ip->size)
    n = ip->size - off;

  struct extent *data = ip->data;
  uint cur_off = off;
  while (cur_off >= (data->nblocks * BSIZE) && data->nblocks > 0) {
    cur_off -= data->nblocks * BSIZE;
    data++;
  }

  for (tot = 0; tot < n; tot += m, cur_off += m, dst += m) {
    if (cur_off < (data->nblocks * BSIZE)) {
      bp = bread(ip->dev, data->startblkno + cur_off / BSIZE);
      m = min(n - tot, BSIZE - cur_off % BSIZE);
      memmove(dst, bp->data + cur_off % BSIZE, m);
      brelse(bp);
    } else {
      data++;
      m = 0;
      cur_off = 0;
    }
  }
  return n;
}

// Lock the inode and write data to inode.
int writei_wrapper(struct inode *ip, char *src, uint off, uint n) {
  int retval;

  ilock(ip);
  //acquiresleep(&(ip->lock));
  retval = writei(ip, src, off, n);
  //updatei(ip);
  //commit_tx();
  //releasesleep(&(ip->lock));
  iunlock(ip);

  return retval;
}

uint getstartblkno(int dev, int size) {
  uint start = sb.bmapstart;
  struct buf *bp;
  uint count = 0;
  int set = 0;

  for (; start < sb.inodestart; start++) {
    bp = bread(dev, start);
    for (uint j = 0; j < BSIZE; j++) {
      uchar c = bp->data[j];

      for (int i = 0; i < 8; i++) {
	if (((c >> i) & 0x1) == 0) {
	  set = 1;
	  bp->data[j] |= (0x1 << (i % 8));
	  size--;
	  if (size == 0) {
            bwrite(bp);
	    //log_write(bp);
	    brelse(bp);
            //commit_tx();

	    //cprintf("Allocated at startblockno: %d\n", count);
	    return count;
	  }
	}

	if (!set) {
	  count++;
	}
      }
    }
    brelse(bp);
  }
  cprintf("Not allocating anything\n");
  return -1;
}

// Updates the dinode corresponding to given inode
void updatei(struct inode *ip) {
  struct dinode dip;
  struct inode *inodefile = &(icache.inodefile);

  //if (ip != &icache.inodefile) {
    // ilock(&icache.inodefile);
  //}
  read_dinode(ip->inum, &dip);

  //if (dip.size != ip->size) {
  dip.size = ip->size;
  for (int i = 0; i < 15; i++) {
    dip.data[i].startblkno = ip->data[i].startblkno;
    dip.data[i].nblocks = ip->data[i].nblocks;
  }
  //dip.type = ip->type;

  writei(inodefile, (char*)&dip, INODEOFF(ip->inum), sizeof(struct dinode));
    //}
  //if (ip != &icache.inodefile) {
  // iunlock(&icache.inodefile);
  //}
}

// Now changed to only extend by one extent
void appendi(struct inode *ip, char *src, uint append) {

  // Search for next empty extent
  struct extent *data = ip->data;
  while (data->nblocks != 0) {
    data++;
  }

  // Allocate the extent dynamically by append size
  data->nblocks = 20;//(append + (BSIZE - 1)) / BSIZE;
  if ((data->startblkno = getstartblkno(ip->dev, data->nblocks)) < 0) {
    cprintf("startblkno is -1\n");
  }
}

// Write data to inode.
// Caller must hold ip->lock.
int writei(struct inode *ip, char *src, uint off, uint n) {
  uint tot, m;
  struct buf *bp;

  if (ip->type == T_DEV) {
    if (ip->devid < 0 || ip->devid >= NDEV || !devsw[ip->devid].write)
      return -1;
    return devsw[ip->devid].write(ip, src, n);
  }

  if (off > ip->size || off + n < off) {
    return -1;
  }

  // Case 1: offset within the extents allocate
  // Case 2: offset + n goes out of bounds of ip->size
  // Case 3: offset overwrites some data and goes either into new extent or stays in same extent while increasing size

  // Must allocate the new extent first
  struct extent *data = ip->data;
  uint cur_off = off;
  uint total_block_size = 0;

  // Finds the extent the offset is in
  while (data->nblocks > 0) {
    if (cur_off >= (data->nblocks *BSIZE)) {
      cur_off -= (BSIZE * data->nblocks);
    }
    total_block_size += (BSIZE * data->nblocks);
    data++;
  }

  // append is the amount of the data left after capping the data at current extent
  uint append = 0;
  if (total_block_size < (off + n)) {
    // n = total to write; cap = current total - off
    // n - cap is amount left to write into extent
    append = n - (total_block_size - off);
    // Allocates a new extent
    appendi(ip, src, append);
  }

  data = ip->data;
  cur_off = off;
  while (cur_off >= (data->nblocks * BSIZE)) {
    cur_off -= (data->nblocks * BSIZE);
    data++;
  }

  // Writes the src across the extents
  for (tot = 0; tot < n; tot += m, cur_off += m, src += m) {
    // Checks offset within current extent
    if (cur_off < (data->nblocks * BSIZE)) {
      bp = bread(ip->dev, data->startblkno + cur_off / BSIZE);
      m = min(n - tot, BSIZE - cur_off % BSIZE);
      memmove(bp->data + cur_off % BSIZE, src, m);
      bwrite(bp);
      //log_write(bp);
      brelse(bp);
    } else {
      // Jumps to next extent; resets offset for next extent
      data++;
      m = 0;
      cur_off = 0;
    }
  }

  // Update current size
  if ((off + n) >= ip->size) {
    ip->size = off + n;
  }

  return n;
  }

struct inode *icreate(char *filepath) {
  struct inode *ip = &(icache.inodefile);
  struct dinode dip;
  //ilock(ip);
  acquiresleep(&(icache.inodefile.lock));
  dip.type = T_FILE;
  dip.devid = T_DEV;
  dip.size = 0;
  for (int i = 0; i < 15; i++) {
    dip.data[i].startblkno = 0;
    dip.data[i].nblocks = 0;
  }

  if (writei(ip, (char *) &dip, ip->size, sizeof(struct dinode)) < 0) {
    cprintf("failed to add dinode in sys open\n");
    iunlock(ip);
  }

  struct inode *root = iget(ROOTDEV, ROOTINO);
  ilock(root);


  struct dirent dir;
  dir.inum = ((ip->size) - 1) / sizeof(struct dinode);
  memmove(dir.name, filepath, DIRSIZ);

  if (writei(root, (char *)&dir, root->size, sizeof(struct dirent)) < 0) {
    cprintf("failed to add dinode in sys open\n");
    iunlock(root);
  }

  updatei(ip);
  //iunlock(ip);
  updatei(root);
  //commit_tx();
  //iunlock(root);
  releasesleep(&(icache.inodefile.lock));
  iunlock(root);
  // ROOTDEV?
  return iget(ROOTDEV, dir.inum);
}

// Directories

int namecmp(const char *s, const char *t) { return strncmp(s, t, DIRSIZ); }

struct inode *rootlookup(char *name) {
  return dirlookup(namei("/"), name, 0);
}

// Look for a directory entry in a directory.
// If found, set *poff to byte offset of entry.
struct inode *dirlookup(struct inode *dp, char *name, uint *poff) {
  uint off, inum;
  struct dirent de;

  if (dp->type != T_DIR)
    panic("dirlookup not DIR");

  for (off = 0; off < dp->size; off += sizeof(de)) {
    if (readi(dp, (char *)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlink read");
    if (de.inum == 0)
      continue;
    if (namecmp(name, de.name) == 0) {
      // entry matches path element
      if (poff)
        *poff = off;
      inum = de.inum;
      return iget(dp->dev, inum);
    }
  }

  return 0;
}

// Paths

// Copy the next path element from path into name.
// Return a pointer to the element following the copied one.
// The returned path has no leading slashes,
// so the caller can check *path=='\0' to see if the name is the last one.
// If no name to remove, return 0.
//
// Examples:
//   skipelem("a/bb/c", name) = "bb/c", setting name = "a"
//   skipelem("///a//bb", name) = "bb", setting name = "a"
//   skipelem("a", name) = "", setting name = "a"
//   skipelem("", name) = skipelem("////", name) = 0
//
static char *skipelem(char *path, char *name) {
  char *s;
  int len;

  while (*path == '/')
    path++;
  if (*path == 0)
    return 0;
  s = path;
  while (*path != '/' && *path != 0)
    path++;
  len = path - s;
  if (len >= DIRSIZ)
    memmove(name, s, DIRSIZ);
  else {
    memmove(name, s, len);
    name[len] = 0;
  }
  while (*path == '/')
    path++;
  return path;
}

// Look up and return the inode for a path name.
// If parent != 0, return the inode for the parent and copy the final
// path element into name, which must have room for DIRSIZ bytes.
// Must be called inside a transaction since it calls iput().
static struct inode *namex(char *path, int nameiparent, char *name) {
  struct inode *ip, *next;

  if (*path == '/')
    ip = iget(ROOTDEV, ROOTINO);
  else
    ip = idup(namei("/"));

  while ((path = skipelem(path, name)) != 0) {
    ilock(ip);
    if (ip->type != T_DIR) {
      iunlock(ip);
      goto notfound;
    }

    // Stop one level early.
    if (nameiparent && *path == '\0') {
      iunlock(ip);
      return ip;
    }

    if ((next = dirlookup(ip, name, 0)) == 0) {
      iunlock(ip);
      goto notfound;
    }

    iunlock(ip);
    irelease(ip);
    ip = next;
  }
  if (nameiparent)
    goto notfound;

  return ip;

notfound:
  irelease(ip);
  return 0;
}

struct inode *namei(char *path) {
  char name[DIRSIZ];
  return namex(path, 0, name);
}

struct inode *nameiparent(char *path, char *name) {
  return namex(path, 1, name);
}

void log_write(struct buf *b) {
  acquiresleep(&log_cache.lock);
  // Add the block from buf to cache
  log_cache.bufs[log_cache.size] = *b;
  log_cache.size++;
  b->flags |= B_DIRTY;

  releasesleep(&log_cache.lock);
}

void begin_tx() {
  acquiresleep(&log_cache.lock);
}

void commit_tx() {
  acquiresleep(&log_cache.lock);
  // Get commit block
  struct buf *commit_buf = bread(ROOTDEV, sb.logstart);
  struct commit_block cb;
  memmove(&cb, commit_buf->data, BSIZE);
  brelse(commit_buf);

  // Write given bufs into log region while updating commit block copy
  for (int i = 0; i < log_cache.size; i++) {
    // Update commit block
    cb.dst_blocknos[i] = log_cache.bufs[i].blockno;
    cb.dst_blockdevs[i] = log_cache.bufs[i].dev;
    cb.size++;
    // Write the data to log region
    struct buf *log_buf = bread(ROOTDEV, sb.logstart + i + 1);
    memmove(log_buf->data, log_cache.bufs[i].data, BSIZE);
    bwrite(log_buf);
    brelse(log_buf);
  }

  // Zero out the log cache
  memset(log_cache.bufs, 0, sizeof(struct buf) * 40);
  log_cache.size = 0;

  // Update the commit block to reflect newly added block to log region
  commit_buf = bread(ROOTDEV, sb.logstart);
  cb.commit_flag = 1;
  memmove(commit_buf->data, &cb, BSIZE);
  bwrite(commit_buf);
  brelse(commit_buf);

  releasesleep(&log_cache.lock);
  log_recover();
}

void log_recover() {
  acquiresleep(&log_cache.lock);

  // Get the commit block
  struct buf *commit_buf = bread(ROOTDEV, sb.logstart);
  struct commit_block cb;
  memmove(&cb, commit_buf->data, BSIZE);
  brelse(commit_buf);

  if (cb.commit_flag == 1) {
    // Get the  blocks from log region and bwrite
    for (int i = 0; i < cb.size; i++) {
      // Get block from log region
      struct buf *src = bread(ROOTDEV, sb.logstart + i + 1);
      brelse(src);

      // Get actual block
      struct buf *dst = bread(cb.dst_blockdevs[i], cb.dst_blocknos[i]);
      memmove(dst->data, src->data, BSIZE);
      bwrite(dst);
      brelse(dst);
    }

    // Clear the log region of commit and logs
    //for (uint i = 0; i < cb.size + 1; i++) {
      commit_buf = bread(ROOTDEV, sb.logstart);
      memset(commit_buf->data, 0, BSIZE);
      bwrite(commit_buf);
      brelse(commit_buf);
      //}
  }

  releasesleep(&log_cache.lock);
}