#!/usr/bin/env python3
#
# diskinspect.py: show what an xv6 file system image (fs.img) contains.
#
#   ./diskinspect.py [--img fs.img]                    root directory + checks
#   ./diskinspect.py [--img fs.img] /y                 everything about file /y
#   ./diskinspect.py --diff before.img [--img fs.img]  blocks that changed
#   ./diskinspect.py --log                         what recovery will install
#   ./diskinspect.py --replay [/y]                 the disk after recovery
#
# Demo:  rm fs.img; make qemu; Ctrl-a x  (first boot creates console)
#        cp fs.img before.img
#        make qemu; echo hi > y; Ctrl-a x
#        ./diskinspect.py /y; ./diskinspect.py --diff before.img
#        after ./crashdemo.py --keep: ./diskinspect.py  (shows the bad dirent)
#        after ./xv6logpanic: ./diskinspect.py --log; ./diskinspect.py --replay /x
#
# Reads the image only; layout comes from the superblock.  BSIZE,
# NDIRECT, and DIRSIZ must match kernel/fs.h.

import argparse, os, struct, sys

BSIZE = 1024
NDIRECT = 12
NINDIRECT = BSIZE // 4
DIRSIZ = 14
FSMAGIC = 0x10203040
ROOTINO = 1
TYPES = {0: 'free', 1: 'dir', 2: 'file', 3: 'dev'}
DINODE = struct.Struct('<hhhhI13I')   # 64 bytes
DIRENT = struct.Struct('<H14s')       # 16 bytes
IPB = BSIZE // DINODE.size

COLOR = sys.stdout.isatty()
def hl(s):   return '\033[1;34m%s\033[0m' % s if COLOR else s
def rev(s):  return '\033[1;7m%s\033[0m' % s if COLOR else '*'
def bad(s):  return '\033[1;31m%s\033[0m' % s if COLOR else s
def dim(s):  return '\033[2m%s\033[0m' % s if COLOR else s

class Inode:
    def __init__(self, inum, raw):
        f = DINODE.unpack(raw)
        self.inum = inum
        self.type, self.major, self.minor, self.nlink, self.size = f[:5]
        self.addrs = list(f[5:])

class FS:
    def __init__(self, path, data=None):
        self.path = path
        self.data = data if data is not None else open(path, 'rb').read()
        (self.magic, self.size, self.nblocks, self.ninodes, self.nlog,
         self.logstart, self.inodestart, self.bmapstart) = \
            struct.unpack_from('<8I', self.data, BSIZE)
        if self.magic != FSMAGIC:
            sys.exit('%s: bad superblock magic %#x' % (path, self.magic))
        self.ninodeblocks = (self.ninodes + IPB - 1) // IPB
        self.nbitmap = self.size // (BSIZE * 8) + 1
        self.datastart = self.bmapstart + self.nbitmap
        self._owners = None

    def block(self, b):
        return self.data[b * BSIZE:(b + 1) * BSIZE]

    # the image as it will be after recover_from_log()
    def replayed(self):
        n, blocks = self.loghead()
        d = bytearray(self.data)
        for slot, home in enumerate(blocks):
            src = (self.logstart + 1 + slot) * BSIZE
            d[home * BSIZE:(home + 1) * BSIZE] = d[src:src + BSIZE]
        struct.pack_into('<i', d, self.logstart * BSIZE, 0)
        return FS(self.path + ' after recovery', bytes(d))

    def iblock(self, inum):
        return self.inodestart + inum // IPB

    def inode(self, inum):
        off = self.iblock(inum) * BSIZE + (inum % IPB) * DINODE.size
        return Inode(inum, self.data[off:off + DINODE.size])

    def bit(self, b):
        byte = self.data[(self.bmapstart + b // (BSIZE * 8)) * BSIZE + (b % (BSIZE * 8)) // 8]
        return (byte >> (b % 8)) & 1

    def bitpos(self, b):
        return self.bmapstart + b // (BSIZE * 8), (b % (BSIZE * 8)) // 8, b % 8

    def loghead(self):
        n = struct.unpack_from('<i', self.data, self.logstart * BSIZE)[0]
        blocks = struct.unpack_from('<%di' % max(n, 0), self.data, self.logstart * BSIZE + 4) \
            if 0 <= n < self.nlog else ()
        return n, list(blocks)

    # data blocks of inode: list of (what, blockno), what = index or 'ind'
    def blocks(self, ip):
        out = [(i, a) for i, a in enumerate(ip.addrs[:NDIRECT]) if a]
        ind = ip.addrs[NDIRECT]
        if ind and ind < self.size:
            out.append(('ind', ind))
            for i, a in enumerate(struct.unpack_from('<%dI' % NINDIRECT, self.data, ind * BSIZE)):
                if a:
                    out.append((NDIRECT + i, a))
        return out

    def dirents(self, ip):
        out = []
        for _, b in self.blocks(ip):
            if _ == 'ind' or b >= self.size:
                continue
            for slot in range(BSIZE // DIRENT.size):
                inum, name = DIRENT.unpack_from(self.data, b * BSIZE + slot * DIRENT.size)
                out.append((b, slot, inum, name.split(b'\0')[0].decode(errors='replace')))
        return out

    def lookup(self, path):
        """returns (inode, parent inode, (dirblock, slot)) or exits"""
        ip, parent, where = self.inode(ROOTINO), None, None
        for name in [p for p in path.split('/') if p]:
            if ip.type != 1:
                sys.exit('%s: not a directory' % name)
            for b, slot, inum, n in self.dirents(ip):
                if inum and n == name:
                    parent, where, ip = ip, (b, slot), self.inode(inum)
                    break
            else:
                hint = ''
                if self.loghead()[0] > 0:
                    hint = ' (but the log is committed; try --replay)'
                sys.exit('%s: no such file in %s%s' % (path, self.path, hint))
        return ip, parent, where

    # map blockno -> (path, inum, what) for every block reachable from /
    def owners(self):
        if self._owners is not None:
            return self._owners
        own, seen = {}, set()
        def walk(inum, path):
            if inum in seen or not 0 < inum < self.ninodes:
                return
            seen.add(inum)
            ip = self.inode(inum)
            if ip.type == 0:
                return
            for what, b in self.blocks(ip):
                own.setdefault(b, (path, inum, what))
            if ip.type == 1:
                for _, _, ci, n in self.dirents(ip):
                    if ci and n not in ('.', '..'):
                        walk(ci, path.rstrip('/') + '/' + n)
        walk(ROOTINO, '/')
        self.reached = {i for i in seen if self.inode(i).type != 0}
        self._owners = own
        return own

    def region(self, b):
        if b == 0: return 'boot'
        if b == 1: return 'super'
        if b == self.logstart: return 'log header'
        if b < self.logstart + self.nlog: return 'log slot %d' % (b - self.logstart - 1)
        if b < self.bmapstart:
            i0 = (b - self.inodestart) * IPB
            return 'inodes %d-%d' % (i0, i0 + IPB - 1)
        if b < self.datastart: return 'bitmap'
        return 'data'

def ranges(nums):
    out, nums = [], sorted(nums)
    i = 0
    while i < len(nums):
        j = i
        while j + 1 < len(nums) and nums[j + 1] == nums[j] + 1:
            j += 1
        out.append(str(nums[i]) if i == j else '%d-%d' % (nums[i], nums[j]))
        i = j + 1
    return ' '.join(out)

def show_layout(fs):
    print('%s: %d blocks, %d inodes (%d per block), %d data blocks' %
          (fs.path, fs.size, fs.ninodes, IPB, fs.nblocks))
    print('  [0] boot  [1] super  [%d] log header  [%d-%d] log  [%d-%d] inodes  [%d] bitmap  [%d-%d] data' %
          (fs.logstart, fs.logstart + 1, fs.logstart + fs.nlog - 1, fs.inodestart,
           fs.bmapstart - 1, fs.bmapstart, fs.datastart, fs.size - 1))
    n, blocks = fs.loghead()
    if n == 0:
        print('  log header: n = 0 (empty)')
    else:
        print('  log header: ' + bad('n = %d, blocks %s: COMMITTED, will be replayed at boot' %
                                     (n, ' '.join(map(str, blocks)))))
        for slot, home in enumerate(blocks):
            print('    log slot %d (block %d) -> block %d (%s)%s' %
                  (slot, fs.logstart + 1 + slot, home, fs.region(home),
                   '' if fs.block(fs.logstart + 1 + slot) != fs.block(home) else ' same as home'))
        print('  (--log: what recovery will install; --replay: view the disk after recovery)')

# one char per block, 64 per row; only rows with something marked
def show_map(fs, marks):
    def ch(b):
        c = base(b)
        return rev(c) if b in marks else c
    def base(b):
        if b == 0: return 'B'
        if b == 1: return 'S'
        if b == fs.logstart: return 'H'
        if b < fs.inodestart: return 'L'
        if b < fs.bmapstart: return 'I'
        if b < fs.datastart: return 'M'
        return 'd' if fs.bit(b) else '.'
    rows = sorted({0} | {b // 64 for b in marks})
    print('\nblock map (B boot, S super, H log header, L log, I inodes, M bitmap, d used, . free):')
    print('        ' + ''.join(str(i // 10) if i % 10 == 0 else ' ' for i in range(64)))
    print('        ' + ''.join(str(i % 10) for i in range(64)))
    prev = None
    for r in rows:
        if prev is not None and r != prev + 1:
            print('   ...')
        print('  %4d  %s' % (r * 64, ''.join(ch(b) for b in range(r * 64, min(r * 64 + 64, fs.size)))))
        prev = r

def show_file(fs, path):
    ip, parent, where = fs.lookup(path)
    show_layout(fs)
    ib = fs.iblock(ip.inum)
    print('\n%s: inode %d' % (hl(path), ip.inum))
    if where:
        print('  dirent:  block %d (data of dir inode %d), slot %d, offset %d: inum %d, name "%s"' %
              (where[0], parent.inum, where[1], where[1] * DIRENT.size, ip.inum, path.rstrip('/').split('/')[-1]))
    print('  inode:   block %d, offset %d (inode %d of %d in block)' %
          (ib, (ip.inum % IPB) * DINODE.size, ip.inum % IPB, IPB))
    print('           type %d (%s), nlink %d, size %d' % (ip.type, TYPES.get(ip.type, '?'), ip.nlink, ip.size))
    if ip.type == 0:
        print(bad('           FREE INODE: this directory entry points to an unallocated inode!'))
    if ip.type == 3:
        print('           major %d, minor %d' % (ip.major, ip.minor))
    print('           addrs[] = ' + ' '.join(map(str, ip.addrs)))
    marks = {ib: 'i'}
    if where:
        marks[where[0]] = 'D'
    bl = fs.blocks(ip)
    if bl:
        print('  blocks:  (bitmap block %d)' % fs.bmapstart)
    shown = bl if len(bl) <= 16 else bl[:NDIRECT + 1]
    for what, b in bl:
        marks[b] = '^' if what == 'ind' else '#'
    for what, b in shown:
        bm, byte, bit = fs.bitpos(b)
        v = fs.bit(b)
        label = 'indirect' if what == 'ind' else 'addrs[%d]' % what if what < NDIRECT else 'ind[%d]' % (what - NDIRECT)
        bits = 'bitmap byte %d, bit %d = %d' % (byte, bit, v)
        print('    %-9s -> block %4d   %s' % (label, b, bits if v else bad(bits + ' FREE!')))
    if len(bl) > len(shown):
        rest = [b for _, b in bl[len(shown):]]
        nfree = sum(1 for b in rest if not fs.bit(b))
        print('    ... and %d more via the indirect block: %s (%s)' %
              (len(rest), ranges(rest), 'all marked used in bitmap' if nfree == 0 else bad('%d FREE!' % nfree)))
    if ip.type == 2 and bl:
        first = next(b for w, b in bl if w != 'ind')
        n = min(ip.size, 64)
        c = fs.block(first)[:n]
        if all(32 <= x < 127 or x in (9, 10) for x in c):
            print('  content: %r%s' % (c.decode(), ' ...' if ip.size > 64 else ''))
        else:
            print('  content: (binary) ' + c[:16].hex(' ') + ' ...')
    if ip.type == 1:
        print('  entries:')
        for b, slot, inum, n in fs.dirents(ip):
            if inum:
                t = fs.inode(inum).type
                print('    %-14s inum %3d  %s' % (n, inum, TYPES.get(t) if t else bad('FREE INODE!')))
    marks.setdefault(fs.bmapstart, 'M')
    show_map(fs, marks)
    print('  (%s = blocks of %s: inode, directory, bitmap, data, and indirect blocks)' %
          (rev('d') if COLOR else '*', path))

def show_root(fs):
    show_layout(fs)
    print('\n/:')
    problems = 0
    for b, slot, inum, n in fs.dirents(fs.inode(ROOTINO)):
        if not inum:
            continue
        ip = fs.inode(inum)
        line = '  %-14s inum %3d  %-4s nlink %d size %6d' % (n, inum, TYPES.get(ip.type, '?'), ip.nlink, ip.size)
        if ip.type == 0:
            problems += 1
            line = bad('  %-14s inum %3d  -> FREE INODE! (dirent in block %d, slot %d)' % (n, inum, b, slot))
        print(line)
    # consistency of blocks vs bitmap
    own = fs.owners()
    leaked = [b for b in range(fs.datastart, fs.size) if fs.bit(b) and b not in own]
    freed = [b for b in own if b >= fs.datastart and not fs.bit(b)]
    orphans = [i for i in range(1, fs.ninodes)
               if fs.inode(i).type != 0 and i not in fs.reached]
    print('\nchecks:')
    if problems:
        print(bad('  %d directory entr%s point%s to a free inode (ls/open of it panics: "ilock: no type")' %
                  (problems, 'y' if problems == 1 else 'ies', 's' if problems == 1 else '')))
    if freed:
        problems += 1
        print(bad('  blocks used by a file but free in bitmap: ' + ranges(freed)))
    if leaked:
        print('  blocks marked used but not in any file (leaked): ' + ranges(leaked))
    if orphans:
        print('  allocated inodes not in any directory (orphans): ' + ' '.join(map(str, orphans)))
    if not (problems or freed or leaked or orphans):
        print('  ok')

def show_diff(old, new, title=None):
    nb = min(old.size, new.size)
    changed = [b for b in range(nb) if old.block(b) != new.block(b)]
    if title is None:
        show_layout(new)
        title = '%d blocks differ between %s and %s:' % (len(changed), old.path, new.path)
    print('\n' + title)
    own_old, own_new = old.owners(), new.owners()
    for b in changed:
        r = new.region(b)
        print('\n' + hl('block %4d  %s' % (b, r)))
        if b == new.logstart:
            raw = lambda fs: [x for x in struct.unpack_from('<%di' % (fs.nlog - 1), fs.data, fs.logstart * BSIZE + 4)]
            ro, rn = raw(old), raw(new)
            k = max([i + 1 for i in range(len(rn)) if rn[i] or ro[i]] or [0])
            print('    n %d -> %d' % (old.loghead()[0], new.loghead()[0]))
            if ro[:k] != rn[:k]:
                print('    block[0..%d]: %s -> %s%s' % (k - 1, ro[:k], rn[:k],
                      '  (leftover from last commit; n = 0 says ignore)' if new.loghead()[0] == 0 else ''))
        elif r.startswith('log slot'):
            copy = [h for h in range(new.logstart + new.nlog, new.size)
                    if new.block(h) == new.block(b)]
            if copy:
                print('    copy of block %s' % ', '.join(map(str, copy[:3])))
            else:
                slot = b - new.logstart - 1
                home = struct.unpack_from('<i', new.data, new.logstart * BSIZE + 4 + 4 * slot)[0]
                print('    older version of block %d, left over from an earlier transaction' % home)
        elif r.startswith('inodes'):
            i0 = (b - new.inodestart) * IPB
            for i in range(i0, i0 + IPB):
                a, c = old.inode(i), new.inode(i)
                diffs = []
                for f in ('type', 'major', 'minor', 'nlink', 'size'):
                    if getattr(a, f) != getattr(c, f):
                        diffs.append('%s %d -> %d' % (f, getattr(a, f), getattr(c, f)))
                for k in range(NDIRECT + 1):
                    if a.addrs[k] != c.addrs[k]:
                        diffs.append('addrs[%d] %d -> %d' % (k, a.addrs[k], c.addrs[k]))
                if diffs:
                    print('    inode %d: %s' % (i, ', '.join(diffs)))
        elif r == 'bitmap':
            for x in range(BSIZE * 8):
                blk = (b - new.bmapstart) * BSIZE * 8 + x
                if old.bit(blk) != new.bit(blk):
                    print('    bit for block %d: %d -> %d' % (blk, old.bit(blk), new.bit(blk)))
        else:
            o = own_new.get(b) or own_old.get(b)
            if o is None:
                print('    (not in any file)')
                continue
            path, inum, what = o
            ip = new.inode(inum) if inum in {v[1] for v in own_new.values()} else old.inode(inum)
            print('    %s of %s (inode %d)' % ('indirect block' if what == 'ind' else 'data', path, inum))
            if ip.type == 1:
                for slot in range(BSIZE // DIRENT.size):
                    off = b * BSIZE + slot * DIRENT.size
                    a = DIRENT.unpack_from(old.data, off)
                    c = DIRENT.unpack_from(new.data, off)
                    if a != c:
                        fmt = lambda d: '(%d, "%s")' % (d[0], d[1].split(b'\0')[0].decode(errors='replace'))
                        print('    slot %d: %s -> %s' % (slot, fmt(a), fmt(c)))
            elif what != 'ind':
                ob, nb_ = old.block(b), new.block(b)
                i = next(k for k in range(BSIZE) if ob[k] != nb_[k])
                print('    bytes from offset %d: %r' % (i, nb_[i:i + 48].rstrip(b'\0').decode(errors='replace')))

def main():
    ap = argparse.ArgumentParser(description='show the contents of an xv6 fs.img')
    ap.add_argument('path', nargs='?', help='file to show, e.g. /y')
    ap.add_argument('--img', default='fs.img', help='image to read (default fs.img)')
    ap.add_argument('--diff', metavar='BEFORE', help='show blocks that differ from BEFORE')
    ap.add_argument('--log', action='store_true', help='show what recovery will install from the log')
    ap.add_argument('--replay', action='store_true', help='view the disk as it will be after recovery')
    ap.add_argument('--no-color', action='store_true')
    a = ap.parse_args()
    global COLOR
    if a.no_color:
        COLOR = False
    fs = FS(a.img)
    if a.log:
        show_layout(fs)
        n, blocks = fs.loghead()
        if n == 0:
            print('\nlog is empty: recovery installs nothing')
        else:
            show_diff(fs, fs.replayed(), 'recovery will install %d blocks from the log, changing:' % n)
        return
    if a.replay:
        fs = fs.replayed()
    if a.diff:
        show_diff(FS(a.diff), fs)
    elif a.path:
        show_file(fs, a.path if a.path.startswith('/') else '/' + a.path)
    else:
        show_root(fs)

if __name__ == '__main__':
    main()
