histext2fs.cpp

#include "ext2fs.h"
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fcntl.h>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unistd.h>
#include <vector>

/* ── Constants ── */
constexpr uint32_t MAX_BLOCK_GROUPS = 128;
constexpr uint32_t REC_LEN(uint32_t n) { return (8 + n + 3) & ~3; }

/* ── DFS Stack ── */
struct StackEntry {
  uint32_t inode_num;
  int depth;
  std::string name;
  bool is_ghost;
  StackEntry *next;
};

struct Stack {
  StackEntry *top = nullptr;
  ~Stack() {
    while (top) {
      StackEntry *e = top;
      top = top->next;
      delete e;
    }
  }
};

static void push(Stack *s, uint32_t ino, int depth, const char *name,
                 bool ghost) {
  auto *e = new StackEntry;
  e->inode_num = ino;
  e->depth = depth;
  e->name = name ? name : "";
  e->is_ghost = ghost;
  e->next = s->top;
  s->top = e;
}

static StackEntry *pop(Stack *s) {
  if (!s->top)
    return nullptr;
  StackEntry *e = s->top;
  s->top = e->next;
  return e;
}

/* ── Read inode from disk ── */
static int read_inode(int fd, const ext2_super_block *sb,
                      const ext2_block_group_descriptor *bgd, uint32_t ino,
                      ext2_inode *out) {
  if (ino == 0 || ino > sb->inode_count)
    return -1;
  uint32_t grp = (ino - 1) / sb->inodes_per_group;
  uint32_t idx = (ino - 1) % sb->inodes_per_group;
  uint32_t bsize = EXT2_UNLOG(sb->log_block_size);
  off_t off = static_cast<off_t>(bgd[grp].inode_table) * bsize +
              static_cast<off_t>(idx) * sb->inode_size;
  return pread(fd, out, sizeof(*out), off) == sizeof(*out) ? 0 : -1;
}

/* ── Directory-entry info for history reconstruction ── */
struct DirEntryInfo {
  uint32_t parent_inode;
  std::string name;
  bool is_ghost;
};

/* ── Temporary holder used while collecting entries for a directory block ── */
struct ChildEntry {
  uint32_t inode_num;
  std::string name;
  bool is_ghost;
};

static void
scan_dir_block(char *blk, uint32_t bsize, int fd, const ext2_super_block *sb,
               const ext2_block_group_descriptor *bgd, uint32_t parent_inode,
               std::vector<ChildEntry> &children, /* for DFS push   */
               std::map<uint32_t, std::vector<DirEntryInfo>> &inode_entries,
               std::map<uint32_t, ext2_inode> &all_inodes,
               bool record_only) /* true = don't collect children */
{
  /* First pass: collect live entry inode numbers so we can skip
     ghost entries for the same inode (e.g. renamed in-place) */
  std::set<uint32_t> live_inodes_in_block;
  for (uint32_t off = 0; off < bsize;) {
    auto *de = reinterpret_cast<ext2_dir_entry *>(blk + off);
    if (de->length < 8 || de->length > bsize - off)
      break;
    if (de->inode != 0 && de->name_length > 0 &&
        de->name_length <= EXT2_MAX_NAME_LENGTH) {
      std::string name(de->name, de->name_length);
      if (name != "." && name != "..")
        live_inodes_in_block.insert(de->inode);
    }
    off += de->length;
  }

  for (uint32_t off = 0; off < bsize;) {
    auto *de = reinterpret_cast<ext2_dir_entry *>(blk + off);
    if (de->length < 8 || de->length > bsize - off)
      break;

    /* Compute slack space occupied by ghost entries */
    uint32_t slack_start = off + REC_LEN(de->name_length);
    slack_start = (slack_start + 3) & ~3;
    uint32_t slack_end = off + de->length;

    /* ── Live entry ── */
    if (de->inode != 0 && de->name_length > 0 &&
        de->name_length <= EXT2_MAX_NAME_LENGTH) {
      std::string name(de->name, de->name_length);
      if (name != "." && name != "..") {
        /* Read child inode if needed */
        if (all_inodes.find(de->inode) == all_inodes.end()) {
          ext2_inode ci;
          if (read_inode(fd, sb, bgd, de->inode, &ci) == 0)
            all_inodes[de->inode] = ci;
        }
        inode_entries[de->inode].push_back({parent_inode, name, false});
        if (!record_only) {
          ext2_inode ci;
          if (read_inode(fd, sb, bgd, de->inode, &ci) == 0 &&
              ci.deletion_time == 0)
            children.push_back({de->inode, name, false});
        }
      }
    }

    /* ── Ghost entries in slack space ── */
    uint32_t cur = slack_start;
    while (cur + 8 <= slack_end) {
      auto *g = reinterpret_cast<ext2_dir_entry *>(blk + cur);
      if (g->inode == 0 || g->name_length == 0 ||
          g->name_length > EXT2_MAX_NAME_LENGTH) {
        cur += 4;
        continue;
      }
      /* Validate inode number is within range */
      if (g->inode > sb->inode_count) {
        cur += 4;
        continue;
      }
      std::string name(g->name, g->name_length);
      if (name != "." && name != "..") {
        ext2_inode gi;
        if (read_inode(fd, sb, bgd, g->inode, &gi) == 0) {
          if (all_inodes.find(g->inode) == all_inodes.end())
            all_inodes[g->inode] = gi;
          inode_entries[g->inode].push_back({parent_inode, name, true});
          /* Only push for DFS display if this inode doesn't already
             have a live entry in this same directory block */
          if (!record_only &&
              live_inodes_in_block.find(g->inode) == live_inodes_in_block.end())
            children.push_back({g->inode, name, true});
        }
      }
      /* Advance by the minimum record length for this entry.
         Don't trust g->length as it may be stale/overwritten. */
      uint32_t advance = REC_LEN(g->name_length);
      advance = (advance + 3) & ~3;
      if (advance < 12)
        advance = 12;
      cur += advance;
      cur = (cur + 3) & ~3;
    }

    off += de->length;
  }
}

/* ── Process all direct blocks of a directory inode ── */
static void process_dir_blocks(
    int fd, const ext2_super_block *sb, const ext2_block_group_descriptor *bgd,
    const ext2_inode *dir, uint32_t parent_inode,
    std::vector<ChildEntry> &children,
    std::map<uint32_t, std::vector<DirEntryInfo>> &inode_entries,
    std::map<uint32_t, ext2_inode> &all_inodes, bool record_only) {
  uint32_t bsize = EXT2_UNLOG(sb->log_block_size);
  char *buf = (char *)malloc(bsize);
  if (!buf)
    return;

  for (int i = 0; i < EXT2_NUM_DIRECT_BLOCKS; ++i) {
    uint32_t bn = dir->direct_blocks[i];
    if (!bn)
      continue;
    if (pread(fd, buf, bsize, static_cast<off_t>(bn) * bsize) !=
        static_cast<ssize_t>(bsize))
      continue;
    scan_dir_block(buf, bsize, fd, sb, bgd, parent_inode, children,
                   inode_entries, all_inodes, record_only);
  }

  /* Single indirect block */
  if (dir->single_indirect) {
    uint32_t *ind = (uint32_t *)malloc(bsize);
    if (ind && pread(fd, ind, bsize,
                     static_cast<off_t>(dir->single_indirect) * bsize) ==
                   static_cast<ssize_t>(bsize)) {
      uint32_t nptrs = bsize / 4;
      for (uint32_t j = 0; j < nptrs; ++j) {
        if (!ind[j])
          continue;
        if (pread(fd, buf, bsize, static_cast<off_t>(ind[j]) * bsize) ==
            static_cast<ssize_t>(bsize))
          scan_dir_block(buf, bsize, fd, sb, bgd, parent_inode, children,
                         inode_entries, all_inodes, record_only);
      }
    }
    free(ind);
  }

  free(buf);
}

/* ── Build parent map (BFS from root) ── */
static void build_parent_map(
    std::map<uint32_t, uint32_t> &parent_map,
    std::map<uint32_t, std::string> &child_name_map,
    const std::map<uint32_t, std::vector<DirEntryInfo>> &inode_entries,
    const std::map<uint32_t, ext2_inode> &all_inodes) {
  std::queue<uint32_t> q;
  q.push(EXT2_ROOT_INODE);
  parent_map[EXT2_ROOT_INODE] = 0;

  while (!q.empty()) {
    uint32_t cur = q.front();
    q.pop();
    for (const auto &ie : inode_entries) {
      uint32_t child = ie.first;
      for (const auto &de : ie.second) {
        if (de.parent_inode != cur)
          continue;
        auto it = all_inodes.find(child);
        if (it == all_inodes.end())
          continue;
        if (!(it->second.mode & EXT2_I_DTYPE))
          continue;
        if (parent_map.find(child) != parent_map.end())
          continue;
        parent_map[child] = cur;
        child_name_map[child] = de.name;
        q.push(child);
      }
    }
  }
}

/* ── Build a full path for an inode ── */
static std::string
build_path(uint32_t inode, const std::map<uint32_t, uint32_t> &parent_map,
           const std::map<uint32_t, std::string> &child_name_map) {
  if (inode == EXT2_ROOT_INODE)
    return "/";
  if (parent_map.find(inode) == parent_map.end())
    return "?";

  std::vector<std::string> parts;
  uint32_t cur = inode;
  while (cur != EXT2_ROOT_INODE && cur != 0) {
    auto pi = parent_map.find(cur);
    if (pi == parent_map.end())
      return "?";
    parts.push_back(child_name_map.at(cur));
    cur = pi->second;
  }
  std::reverse(parts.begin(), parts.end());
  std::string p = "/";
  for (size_t i = 0; i < parts.size(); ++i) {
    p += parts[i];
    if (i + 1 < parts.size())
      p += "/";
  }
  return p;
}

static std::string join_path(const std::string &parent,
                             const std::string &name) {
  return parent == "/" ? "/" + name : parent + "/" + name;
}

/* ── Event for history output ── */
struct Event {
  uint32_t timestamp;
  bool has_timestamp;
  std::string action;
  std::vector<std::string> args;
  std::vector<uint32_t> affected_dirs;
  std::vector<uint32_t> affected_inodes;
};

/* ── History reconstruction ── */
static std::vector<Event> process_events(
    const std::set<uint32_t> &timestamps,
    const std::map<uint32_t, ext2_inode> &all_inodes,
    const std::map<uint32_t, std::vector<DirEntryInfo>> &inode_entries,
    const std::map<uint32_t, uint32_t> &parent_map,
    const std::map<uint32_t, std::string> &child_name_map) {
  std::vector<Event> events;
  std::set<uint32_t> processed_creations; /* avoid duplicate create events */
  std::set<uint32_t> processed_deletions;

  /* ── Pass 1: stamped events (iterate chronologically) ── */
  for (uint32_t ts : timestamps) {
    /* Collect all inodes that changed at this timestamp */
    std::vector<uint32_t> affected;
    for (const auto &ip : all_inodes) {
      const ext2_inode &ino = ip.second;
      if (ino.access_time == ts || ino.change_time == ts ||
          ino.modification_time == ts || ino.deletion_time == ts)
        affected.push_back(ip.first);
    }
    if (affected.empty())
      continue;

    /* ── Check for DELETION ── */
    {
      bool found = false;
      for (uint32_t inum : affected) {
        const ext2_inode &ino = all_inodes.at(inum);
        if (ino.deletion_time != ts)
          continue;
        if (processed_deletions.count(inum))
          continue;
        processed_deletions.insert(inum);

        Event ev;
        ev.timestamp = ts;
        ev.has_timestamp = true;
        ev.action = (ino.mode & EXT2_I_DTYPE) ? "rmdir" : "rm";
        ev.affected_inodes.push_back(inum);

        /* Find path from inode_entries */
        if (inode_entries.count(inum)) {
          for (const auto &de : inode_entries.at(inum)) {
            std::string pp =
                build_path(de.parent_inode, parent_map, child_name_map);
            ev.args.push_back(join_path(pp, de.name));
            ev.affected_dirs.push_back(de.parent_inode);
            break;
          }
        }
        events.push_back(ev);
        found = true;
        break;
      }
      if (found)
        continue;
    }

    /* ── Check for CREATION ── */
    {
      bool found = false;
      for (uint32_t inum : affected) {
        const ext2_inode &ino = all_inodes.at(inum);
        if (ino.access_time != ts)
          continue;
        if (processed_creations.count(inum))
          continue;
        /* Skip reserved inodes (1-10) */
        if (inum <= 10)
          continue;

        processed_creations.insert(inum);

        Event ev;
        ev.timestamp = ts;
        ev.has_timestamp = true;
        ev.action = (ino.mode & EXT2_I_DTYPE) ? "mkdir" : "touch";
        ev.affected_inodes.push_back(inum);

        /* Determine creation path.
           — For files/dirs with only live entry: use that.
           — For files/dirs with ghost entries: the creation
             happened at the FIRST ghost entry's parent (that's
             the original location before any moves). */
        if (inode_entries.count(inum)) {
          const auto &entries = inode_entries.at(inum);
          const DirEntryInfo *chosen = nullptr;

          /* Prefer earliest ghost entry */
          for (const auto &de : entries) {
            if (de.is_ghost) {
              chosen = &de;
              break;
            }
          }
          /* Fall back to live entry */
          if (!chosen) {
            for (const auto &de : entries) {
              if (!de.is_ghost) {
                chosen = &de;
                break;
              }
            }
          }
          if (chosen) {
            std::string pp =
                build_path(chosen->parent_inode, parent_map, child_name_map);
            ev.args.push_back(join_path(pp, chosen->name));
            ev.affected_dirs.push_back(chosen->parent_inode);
          }
        }
        events.push_back(ev);
        found = true;
        break;
      }
      if (found)
        continue;
    }

    /* ── Check for MOVE (last move – has a recoverable timestamp) ── */
    {
      for (uint32_t inum : affected) {
        const ext2_inode &ino = all_inodes.at(inum);
        if (ino.change_time != ts)
          continue;
        if (ino.access_time == ts)
          continue; /* already handled as create */
        if (ino.deletion_time != 0 && ino.deletion_time <= ts)
          continue;

        if (!inode_entries.count(inum))
          continue;
        const auto &entries = inode_entries.at(inum);

        /* Need at least one ghost and at least one other entry */
        std::vector<const DirEntryInfo *> ghosts, non_ghosts;
        for (const auto &de : entries) {
          if (de.is_ghost)
            ghosts.push_back(&de);
          else
            non_ghosts.push_back(&de);
        }
        if (ghosts.empty() || non_ghosts.empty())
          continue;

        /* For chain moves (2+ ghosts), emit intermediate moves
           BEFORE the last timestamped move, with ? timestamp.
           Chain: ghosts[0]→ghosts[1]→...→ghosts[N-1]→live */
        for (size_t gi = 0; gi + 1 < ghosts.size(); ++gi) {
          const DirEntryInfo *isrc = ghosts[gi];
          const DirEntryInfo *idst = ghosts[gi + 1];
          std::string isrc_pp =
              build_path(isrc->parent_inode, parent_map, child_name_map);
          std::string idst_pp =
              build_path(idst->parent_inode, parent_map, child_name_map);

          Event iev;
          iev.timestamp = 0;
          iev.has_timestamp = false;
          iev.action = "mv";
          iev.args.push_back(join_path(isrc_pp, isrc->name));
          iev.args.push_back(join_path(idst_pp, idst->name));
          iev.affected_dirs.push_back(isrc->parent_inode);
          iev.affected_dirs.push_back(idst->parent_inode);
          iev.affected_inodes.push_back(inum);
          events.push_back(iev);
        }

        /* Last move: last ghost → live entry */
        const DirEntryInfo *src = ghosts.back();
        const DirEntryInfo *dst = non_ghosts[0];

        std::string src_pp =
            build_path(src->parent_inode, parent_map, child_name_map);
        std::string dst_pp =
            build_path(dst->parent_inode, parent_map, child_name_map);

        Event ev;
        ev.timestamp = ts;
        ev.has_timestamp = true;
        ev.action = "mv";
        ev.args.push_back(join_path(src_pp, src->name));
        ev.args.push_back(join_path(dst_pp, dst->name));
        ev.affected_dirs.push_back(src->parent_inode);
        ev.affected_dirs.push_back(dst->parent_inode);
        ev.affected_inodes.push_back(inum);
        events.push_back(ev);
        break;
      }
    }
  }

  return events;
}

/* ── main ── */
int main(int argc, char *argv[]) {
  if (argc != 4) {
    fprintf(stderr, "Usage: %s image state_out history_out\n", argv[0]);
    return 1;
  }
  const char *img_path = argv[1];
  const char *state_out = argv[2];
  const char *history_out = argv[3];

  int fd = open(img_path, O_RDONLY);
  if (fd < 0) {
    perror("open");
    return 1;
  }

  /* ── Superblock ── */
  ext2_super_block sb;
  if (pread(fd, &sb, sizeof(sb), EXT2_SUPER_BLOCK_POSITION) != sizeof(sb) ||
      sb.magic != EXT2_SUPER_MAGIC) {
    fprintf(stderr, "Not a valid ext2 image\n");
    close(fd);
    return 1;
  }

  uint32_t bsize = EXT2_UNLOG(sb.log_block_size);
  uint32_t bgcnt =
      (sb.block_count + sb.blocks_per_group - 1) / sb.blocks_per_group;
  ext2_block_group_descriptor bgd[MAX_BLOCK_GROUPS];

  off_t bgd_offset = (EXT2_SUPER_BLOCK_POSITION / bsize + 1) * bsize;
  if (pread(fd, bgd, bgcnt * sizeof(*bgd), bgd_offset) !=
      static_cast<ssize_t>(bgcnt * sizeof(*bgd))) {
    perror("pread(bgd)");
    close(fd);
    return 1;
  }

  /* ══════ PART 1: STATE OUTPUT ══════ */
  FILE *state_fp = fopen(state_out, "w");
  if (!state_fp) {
    perror("fopen");
    close(fd);
    return 1;
  }

  /* Data structures shared with Part 2 */
  std::map<uint32_t, std::vector<DirEntryInfo>> inode_entries;
  std::map<uint32_t, ext2_inode> all_inodes;
  std::set<uint32_t> all_timestamps;

  /* Seed root inode */
  ext2_inode root_ino;
  if (read_inode(fd, &sb, bgd, EXT2_ROOT_INODE, &root_ino) == 0)
    all_inodes[EXT2_ROOT_INODE] = root_ino;

  /* DFS traversal */
  Stack stk;
  push(&stk, EXT2_ROOT_INODE, 1, "root", false);

  while (stk.top) {
    StackEntry *e = pop(&stk);
    ext2_inode ino;
    if (read_inode(fd, &sb, bgd, e->inode_num, &ino)) {
      delete e;
      continue;
    }
    all_inodes[e->inode_num] = ino;

    /* Print entry */
    for (int i = 0; i < e->depth; ++i)
      fputc('-', state_fp);
    if (e->is_ghost)
      fprintf(state_fp, " (%u:%s", e->inode_num, e->name.c_str());
    else
      fprintf(state_fp, " %u:%s", e->inode_num, e->name.c_str());
    if (ino.mode & EXT2_I_DTYPE)
      fputc('/', state_fp);
    if (e->is_ghost)
      fputc(')', state_fp);
    fputc('\n', state_fp);

    /* For ghost directories: record their children for history
       but do NOT recurse into them for tree display. */
    if (e->is_ghost && (ino.mode & EXT2_I_DTYPE)) {
      std::vector<ChildEntry> dummy;
      process_dir_blocks(fd, &sb, bgd, &ino, e->inode_num, dummy, inode_entries,
                         all_inodes, true);
    }
    /* For live directories: collect children, push in reverse
       so they pop in correct (disk) order. */
    else if (!e->is_ghost && (ino.mode & EXT2_I_DTYPE) &&
             ino.deletion_time == 0) {
      std::vector<ChildEntry> children;
      process_dir_blocks(fd, &sb, bgd, &ino, e->inode_num, children,
                         inode_entries, all_inodes, false);

      /* Push in reverse so first-on-disk pops first */
      for (int j = static_cast<int>(children.size()) - 1; j >= 0; --j) {
        push(&stk, children[j].inode_num, e->depth + 1,
             children[j].name.c_str(), children[j].is_ghost);
      }
    }

    delete e;
  }
  fclose(state_fp);

  /* ── Post-DFS: scan deleted directories' children for history ── */
  /* Deleted directories were collected as ghost entries but their
     own child entries may not have been discovered (only recorded
     at depth=1 without recursion). Recursively scan them. */
  {
    std::queue<uint32_t> to_scan;
    std::set<uint32_t> scanned;

    for (const auto &ip : all_inodes) {
      if ((ip.second.mode & EXT2_I_DTYPE) && ip.second.deletion_time != 0)
        to_scan.push(ip.first);
    }

    while (!to_scan.empty()) {
      uint32_t dino = to_scan.front();
      to_scan.pop();
      if (scanned.count(dino))
        continue;
      scanned.insert(dino);

      auto it = all_inodes.find(dino);
      if (it == all_inodes.end())
        continue;

      std::vector<ChildEntry> dummy;
      process_dir_blocks(fd, &sb, bgd, &it->second, dino, dummy, inode_entries,
                         all_inodes, true);

      /* Check if any newly discovered inodes are also deleted dirs */
      for (const auto &c : dummy) {
        auto ci = all_inodes.find(c.inode_num);
        if (ci != all_inodes.end() && (ci->second.mode & EXT2_I_DTYPE) &&
            ci->second.deletion_time != 0 && !scanned.count(c.inode_num))
          to_scan.push(c.inode_num);
      }
    }
  }

  /* ══════ PART 2: HISTORY OUTPUT ══════ */

  /* Build parent map & child name map for path construction */
  std::map<uint32_t, uint32_t> parent_map;
  std::map<uint32_t, std::string> child_name_map;
  build_parent_map(parent_map, child_name_map, inode_entries, all_inodes);

  /* Collect all timestamps */
  for (const auto &ip : all_inodes) {
    const ext2_inode &ino = ip.second;
    if (ino.access_time)
      all_timestamps.insert(ino.access_time);
    if (ino.change_time)
      all_timestamps.insert(ino.change_time);
    if (ino.modification_time)
      all_timestamps.insert(ino.modification_time);
    if (ino.deletion_time)
      all_timestamps.insert(ino.deletion_time);
  }

  /* Process events */
  std::vector<Event> events = process_events(
      all_timestamps, all_inodes, inode_entries, parent_map, child_name_map);

  /* Write history file */
  FILE *hfp = fopen(history_out, "w");
  if (!hfp) {
    perror("fopen");
    close(fd);
    return 1;
  }

  for (const Event &ev : events) {
    if (ev.action.empty())
      continue;

    /* Print timestamp or "?" */
    if (ev.has_timestamp)
      fprintf(hfp, "%u", ev.timestamp);
    else
      fprintf(hfp, "?");

    fprintf(hfp, " %s [", ev.action.c_str());
    for (size_t i = 0; i < ev.args.size(); ++i) {
      fprintf(hfp, "%s", ev.args[i].c_str());
      if (i + 1 < ev.args.size())
        fputc(' ', hfp);
    }
    fprintf(hfp, "] [");
    for (size_t i = 0; i < ev.affected_dirs.size(); ++i) {
      fprintf(hfp, "%u", ev.affected_dirs[i]);
      if (i + 1 < ev.affected_dirs.size())
        fputc(' ', hfp);
    }
    fprintf(hfp, "] [");
    for (size_t i = 0; i < ev.affected_inodes.size(); ++i) {
      fprintf(hfp, "%u", ev.affected_inodes[i]);
      if (i + 1 < ev.affected_inodes.size())
        fputc(' ', hfp);
    }
    fprintf(hfp, "]\n");
  }
  fclose(hfp);

  close(fd);
  return 0;
}