Backup

1 files changed, 222 insertions, 29 deletions

diff --git a/ext2fs.c b/ext2fs.c
index 176742e..3c88ce1 100644
--- a/ext2fs.c
+++ b/ext2fs.c
@@ -16,9 +16,10 @@
 
 /* If you want debugging output, use the following macro.  When you hand
  * in, remove the #define DEBUG line. */
-#undef DEBUG
+// #undef DEBUG
+// #define DEBUG
 #ifdef DEBUG
-#define debug(...) printf(__VA_ARGS__)
+#define debug(...) fprintf(stderr, __VA_ARGS__)
 #else
 #define debug(...)
 #endif
@@ -119,6 +120,9 @@ static blk_t *blk_alloc(void) {
   if (!TAILQ_EMPTY(&freelst)) {
 #ifdef STUDENT
     /* TODO */
+    blk = TAILQ_FIRST(&freelst);
+    blk->b_refcnt = 0;
+    TAILQ_REMOVE(&freelst, blk, b_link);
 #endif /* !STUDENT */
     return blk;
   }
@@ -128,6 +132,11 @@ static blk_t *blk_alloc(void) {
   if (!TAILQ_EMPTY(&lrulst)) {
 #ifdef STUDENT
     /* TODO */
+    blk = TAILQ_FIRST(&lrulst);
+    TAILQ_REMOVE(&lrulst, blk, b_link);
+
+    blk_list_t *bucket = &buckets[BUCKET(blk->b_inode, blk->b_index)];
+    TAILQ_REMOVE(bucket, blk, b_hash);
 #endif /* !STUDENT */
     return blk;
   }
@@ -147,6 +156,12 @@ static blk_t *blk_get(uint32_t ino, uint32_t idx) {
   /* Locate a block in the buffer and return it if found. */
 #ifdef STUDENT
   /* TODO */
+  TAILQ_FOREACH (blk, bucket, b_hash) {
+    if (blk->b_inode == ino && blk->b_index == idx) {
+      blk->b_refcnt++;
+      return blk;
+    }
+  }
 #endif /* !STUDENT */
 
   long blkaddr = ext2_blkaddr_read(ino, idx);
@@ -195,6 +210,28 @@ int ext2_block_used(uint32_t blkaddr) {
   int used = 0;
 #ifdef STUDENT
   /* TODO */
+  /* MY-TODO: What should be returned if the blkaddr points to meta-data? */
+  // debug("ext2_block_used(%d)?\n", blkaddr);
+  uint32_t grp_no = (blkaddr - first_data_block) / blocks_per_group;
+  uint32_t b_bitmap_addr = group_desc[grp_no].gd_b_bitmap;
+  blk_t *bitmap_blk = blk_get(0, b_bitmap_addr);
+  uint8_t *bitmap = bitmap_blk->b_data;
+  /* index of the data block pointed by blkaddr in the group is blkaddr
+   * minus (the offset of b_bitmap_addr + 2 (for data bitmap and inode
+   * bitmap) + blocks used for inode table.)*/
+  uint32_t local_idx = (blkaddr - first_data_block) % blocks_per_group;
+
+  // debug("Group: %u, bitmap at %u\n", grp_no, b_bitmap_addr);
+  // debug("local idx: %u\n", local_idx);
+#ifdef DEBUG
+  assert(bitmap_blk->b_inode == 0);
+  assert(bitmap_blk->b_blkaddr == b_bitmap_addr);
+  assert(local_idx < BLKSIZE * 8);
+#endif
+
+  used = (bitmap[local_idx / 8] & (1 << (local_idx % 8))) > 0;
+
+  blk_put(bitmap_blk);
 #endif /* !STUDENT */
   return used;
 }
@@ -207,6 +244,23 @@ int ext2_inode_used(uint32_t ino) {
   int used = 0;
 #ifdef STUDENT
   /* TODO */
+  /* MY-TODO: Similar to ext2_block_used. */
+  uint32_t grp_no = (ino - 1) / inodes_per_group;
+  uint32_t i_bitmap_addr = group_desc[grp_no].gd_i_bitmap;
+  blk_t *i_bitmap = blk_get(0, i_bitmap_addr);
+
+  uint32_t local_idx = (ino - 1) % inodes_per_group;
+
+#ifdef DEBUG
+  assert(i_bitmap->b_inode == 0);
+  assert(i_bitmap->b_blkaddr == i_bitmap_addr);
+  assert(local_idx < BLKSIZE * 8);
+#endif
+
+  used =
+    (((char *)i_bitmap->b_data)[local_idx / 8] & (1 << (local_idx % 8))) > 0;
+
+  blk_put(i_bitmap);
 #endif /* !STUDENT */
   return used;
 }
@@ -216,9 +270,19 @@ int ext2_inode_used(uint32_t ino) {
 static int ext2_inode_read(off_t ino, ext2_inode_t *inode) {
 #ifdef STUDENT
   /* TODO */
-  (void)ino;
-  (void)inode;
-  return ENOENT;
+
+  if (!ext2_inode_used(ino))
+    return ENOENT;
+
+  uint32_t grp_no = (ino - 1) / inodes_per_group;
+  uint32_t local_idx = (ino - 1) % inodes_per_group;
+  uint32_t inode_blk_addr =
+    group_desc[grp_no].gd_i_tables + (local_idx / BLK_INODES);
+  blk_t *i_blk = blk_get(0, inode_blk_addr);
+
+  memcpy(inode, i_blk->b_data + sizeof(ext2_inode_t) * (local_idx % BLK_INODES),
+         sizeof(ext2_inode_t));
+  blk_put(i_blk);
 #endif /* !STUDENT */
   return 0;
 }
@@ -227,8 +291,14 @@ static int ext2_inode_read(off_t ino, ext2_inode_t *inode) {
 static uint32_t ext2_blkptr_read(uint32_t blkaddr, uint32_t blkidx) {
 #ifdef STUDENT
   /* TODO */
-  (void)blkaddr;
-  (void)blkidx;
+  /* MY-TODO -- I don't get the hint from the task statement */
+  blk_t *blk = blk_get(0, blkaddr);
+#ifdef DEGUG
+  assert(blkidx <= (BLKSIZE / sizeof(uint32_t)));
+#endif
+  uint32_t addr = ((uint32_t *)blk->b_data)[blkidx];
+  blk_put(blk);
+  return addr;
 #endif /* !STUDENT */
   return 0;
 }
@@ -247,7 +317,37 @@ long ext2_blkaddr_read(uint32_t ino, uint32_t blkidx) {
     /* Read direct pointers or pointers from indirect blocks. */
 #ifdef STUDENT
   /* TODO */
-  (void)ext2_blkptr_read;
+  // debug("Pytanko: %d %d, %d\n", ino, blkidx, inode.i_size);
+  const uint32_t direct_blocks = EXT2_NDADDR;
+  const uint32_t ind1_blks = BLKSIZE / sizeof(uint32_t);
+  const uint32_t ind2_blks = ind1_blks * BLKSIZE / sizeof(uint32_t);
+  const uint32_t ind3_blks = ind2_blks * BLKSIZE / sizeof(uint32_t);
+  /* Maybe direct block? */
+  if (blkidx < direct_blocks) {
+    return inode.i_blocks[blkidx];
+  }
+  /* Maybe 1st-indirect? */
+  blkidx -= direct_blocks;
+  if (blkidx < ind1_blks) {
+    return ext2_blkptr_read(inode.i_blocks[EXT2_NDADDR], blkidx);
+  }
+  /* Maybe 2nd-indirect? */
+  blkidx -= ind1_blks;
+  if (blkidx < ind2_blks) {
+    /* Get addres of the block that points to blkidx block */
+    uint32_t ind_blk =
+      ext2_blkptr_read(inode.i_blocks[EXT2_NDADDR + 1], blkidx / ind1_blks);
+    return ext2_blkptr_read(ind_blk, blkidx % ind1_blks);
+  }
+  /* Maybe 3rd-indirect? */
+  if (blkidx < ind3_blks) {
+    blkidx -= ind2_blks;
+    uint32_t ind_blk =
+      ext2_blkptr_read(inode.i_blocks[EXT2_NDADDR + 2], blkidx / ind2_blks);
+    blkidx %= ind2_blks;
+    ind_blk = ext2_blkptr_read(ind_blk, blkidx / ind1_blks);
+    return ext2_blkptr_read(ind_blk, blkidx % ind1_blks);
+  }
 #endif /* !STUDENT */
   return -1;
 }
@@ -260,12 +360,43 @@ long ext2_blkaddr_read(uint32_t ino, uint32_t blkidx) {
 int ext2_read(uint32_t ino, void *data, size_t pos, size_t len) {
 #ifdef STUDENT
   /* TODO */
-  (void)ino;
-  (void)data;
-  (void)pos;
-  (void)len;
-  (void)blk_get;
-  (void)blk_put;
+  size_t end_pos = pos + len;
+  if (ino != 0) {
+    ext2_inode_t inode;
+    ext2_inode_read(ino, &inode);
+    if (inode.i_size < end_pos) {
+      return EINVAL;
+    }
+  }
+  blk_t *blk;
+  uint32_t blkidx;
+  uint32_t bytes_copied = 0;
+  for (blkidx = pos / BLKSIZE; blkidx < (end_pos + BLKSIZE - 1) / BLKSIZE;
+       blkidx++) {
+    // debug("Trying to get %d %d\n", ino, blkidx);
+    blk = blk_get(ino, blkidx);
+    uint32_t len_to_cpy;
+    if (bytes_copied == 0) {
+      len_to_cpy = BLKSIZE - (pos % BLKSIZE);
+    } else {
+      len_to_cpy = BLKSIZE;
+    }
+    len_to_cpy = min(len_to_cpy, len - bytes_copied);
+    void *dest = data + bytes_copied;
+
+    if (blk == BLK_ZERO) {
+      memset(dest, 0, len_to_cpy);
+      bytes_copied += len_to_cpy;
+      continue;
+    }
+
+    void *src = blk->b_data + (bytes_copied == 0 ? pos % BLKSIZE : 0);
+    memcpy(dest, src, len_to_cpy);
+    bytes_copied += len_to_cpy;
+    blk_put(blk);
+  }
+
+  return 0;
 #endif /* !STUDENT */
   return EINVAL;
 }
@@ -280,9 +411,23 @@ int ext2_read(uint32_t ino, void *data, size_t pos, size_t len) {
 int ext2_readdir(uint32_t ino, uint32_t *off_p, ext2_dirent_t *de) {
 #ifdef STUDENT
   /* TODO */
-  (void)ino;
-  (void)off_p;
-  (void)de;
+  ext2_inode_t inode;
+  ext2_inode_read(ino, &inode);
+  if (*off_p >= inode.i_size)
+    return 0;
+
+  ext2_read(ino, de, *off_p, de_name_offset);
+  while (de->de_ino == 0) {
+    *off_p += de->de_reclen;
+    if (*off_p >= inode.i_size)
+      return 0;
+    ext2_read(ino, de, *off_p, de_name_offset);
+  }
+
+  ext2_read(ino, de->de_name, *off_p + de_name_offset, de->de_namelen);
+  de->de_name[de->de_namelen] = 0;
+  *off_p += de->de_reclen;
+  return 1;
 #endif /* !STUDENT */
   return 0;
 }
@@ -300,8 +445,17 @@ int ext2_readlink(uint32_t ino, char *buf, size_t buflen) {
     /* Check if it's a symlink and read it. */
 #ifdef STUDENT
   /* TODO */
-  (void)buf;
-  (void)buflen;
+  if (!(inode.i_mode & EXT2_IFLNK))
+    return EINVAL;
+  if (inode.i_size > buflen)
+    return EINVAL;
+
+  if (inode.i_size <= sizeof(inode.i_blocks)) {
+    memcpy(buf, (char *)inode.i_blocks, inode.i_size);
+  } else {
+    ext2_read(ino, buf, 0, inode.i_size);
+  }
+  return 0;
 #endif /* !STUDENT */
   return ENOTSUP;
 }
@@ -318,7 +472,21 @@ int ext2_stat(uint32_t ino, struct stat *st) {
     /* Convert the metadata! */
 #ifdef STUDENT
   /* TODO */
-  (void)st;
+  st->st_ino = ino;
+  st->st_mode = inode.i_mode;
+  st->st_nlink = inode.i_nlink;
+  st->st_uid = inode.i_uid;
+  st->st_gid = inode.i_gid;
+  st->st_size = inode.i_size;
+  st->st_blksize = BLKSIZE;
+  st->st_blocks = (blkcnt_t)inode.i_blocks;
+  st->st_atim.tv_nsec = 0;
+  st->st_atim.tv_sec = inode.i_atime;
+  st->st_ctim.tv_nsec = 0;
+  st->st_ctim.tv_sec = inode.i_ctime;
+  st->st_mtim.tv_nsec = 0;
+  st->st_mtim.tv_sec = inode.i_mtime;
+  return 0;
 #endif /* !STUDENT */
   return ENOTSUP;
 }
@@ -341,8 +509,21 @@ int ext2_lookup(uint32_t ino, const char *name, uint32_t *ino_p,
 
 #ifdef STUDENT
   /* TODO */
-  (void)ino_p;
-  (void)type_p;
+  // (void)ino_p;
+  // (void)type_p;
+  if (!(inode.i_mode & EXT2_IFDIR))
+    return ENOTDIR;
+  ext2_dirent_t de;
+  uint32_t off = 0;
+  while (ext2_readdir(ino, &off, &de)) {
+    if (!strcmp(de.de_name, name)) {
+      if (ino_p)
+        *ino_p = de.de_ino;
+      if (type_p)
+        *type_p = de.de_type;
+      return 0;
+    }
+  }
 #endif /* !STUDENT */
 
   return ENOENT;
@@ -387,13 +568,25 @@ int ext2_mount(const char *fspath) {
      * Read group descriptor table into memory. */
 #ifdef STUDENT
   /* TODO */
-  (void)inodes_per_group;
-  (void)blocks_per_group;
-  (void)group_desc_count;
-  (void)block_count;
-  (void)inode_count;
-  (void)first_data_block;
-  (void)group_desc;
+  inodes_per_group = sb.sb_ipg;
+  blocks_per_group = sb.sb_bpg;
+  group_desc_count = (sb.sb_bcount + sb.sb_bpg - 1) / sb.sb_bpg; // ceil
+  block_count = sb.sb_bcount;
+  inode_count = sb.sb_icount;
+  first_data_block = sb.sb_first_dblock;
+
+  size_t group_desc_table_sz = group_desc_count * sizeof(*group_desc);
+  debug("group_desc_table_sz: %ld\n", group_desc_table_sz);
+  debug("group_desc_count: %ld\n", group_desc_count);
+  debug("first_data_block: %ld\n", first_data_block);
+  debug("blkdata: %p\n", blkdata);
+  for (int i = 0; i < NBLOCKS; i++) {
+    debug("blkdata[%d]: %p\n", i, blkdata[i]);
+  }
+  group_desc = malloc(group_desc_table_sz);
+  ext2_read(0, group_desc, EXT2_GDOFF, group_desc_table_sz);
+
+  return 0;
 #endif /* !STUDENT */
   return ENOTSUP;
 }