#!/usr/bin/env python

import collections
import errno
import itertools
import logging
import os
import os.path
import stat
import struct
import sys

try:
    import isi.fs.extattr
    import isi.fs.ifs_types
    import isi.fs.lin
    import isi.fs.prot_group
    import isi.fs.sbt
    import isi.ui.lib.format

    from isi.fs.ifs_types import IFS_BSIZE
    from isi.ui.lib.format import fmtLin
    from isi.ui.lib.format import fmtLinsid
except ImportError as e:
    logging.warn("%s", e)

# XXX
ENOATTR = 87 # ENOATTR is not in errno!
STAT_BSIZE = 512
O_NOSEMLOCK = 0x08000000

def prefetch_iterate(linsids, depth, flags=0):
    """Generate linsids, prefetching depth ahead."""

    q = collections.deque()
    it = iter(linsids)

    # Initial phase, build up buffer queue.
    for i in xrange(depth):
        try:
            item = next(it)
        except StopIteration:
            break
        q.append(item)

    # Prefetch initial items.
    if q:
        isi.fs.lin.prefetch(q, flags)

    # Steady phase, yield and prefetch ahead.
    while q:
        item = q.popleft()
        yield item
        try:
            item = next(it)
        except StopIteration:
            break
        isi.fs.lin.prefetch((item,), flags)
        q.append(item)

    # Final phase, yield remaining items.
    while q:
        item = q.popleft()
        yield item

def get_extattr(fd, attrname, fmt):
    attr_bin = isi.fs.extattr.get_fd(fd, isi.fs.extattr.NAMESPACE_IFS,
        attrname)
    return struct.unpack(fmt, attr_bin)

def get_snapid_range(fd):
    try:
        min_snapid, max_snapid = get_extattr(fd, "snapid_range", "QQ")
        return (min_snapid, max_snapid)
    except IOError as e:
        if e.errno == ENOATTR:
            return (isi.fs.lin.HEAD_SNAPID, isi.fs.lin.HEAD_SNAPID)
        raise e

def get_max_snapid(fd):
    snapid_range = get_snapid_range(fd)
    return snapid_range[1]

def get_shadow_refs(fd):
    shadow_refs, = get_extattr(fd, "shadow_refs", "Q")
    return shadow_refs

def get_logical_data_size(fd):
    logical_data_size, = get_extattr(fd, "logical_data_size", "Q")
    return logical_data_size

def account_stat(stats, st, logical_data_size=0, shadow_refs=0):
    mode = stat.S_IFMT(st.st_mode)
    blocks = st.st_blocks
    if shadow_refs:
        blocks -= shadow_refs * IFS_BSIZE / STAT_BSIZE
    if mode not in stats:
        stats_mode = {
            "count": 0,
            "blocks": 0,
            "size": 0,
            "logical_data_size": 0
        }
        stats[mode] = stats_mode
    else:
        stats_mode = stats[mode]
    stats_mode["count"] += 1
    stats_mode["blocks"] += blocks
    stats_mode["size"] += st.st_size
    stats_mode["logical_data_size"] += logical_data_size

def get_ifs_dev():
    try:
        import isi.fs.lin
    except ImportError:
        return None
    try:
        ifs_st = os.stat("/ifs")
    except OSError as e:
        logging.warn("get_ifs_dev: could not stat /ifs: %s", e)
        return None
    if ifs_st.st_ino != isi.fs.lin.ROOT_LIN:
        return None
    return ifs_st.st_dev

# Cache the device id of /ifs.
g_ifs_dev = get_ifs_dev()

def account(stats, linsids, links, rootname, filename=None, defer=True):
    if filename == None:
        fpath = rootname
    else:
        fpath = os.path.join(rootname, filename)

    # Account non-regular files.
    st = os.lstat(fpath)
    if not stat.S_ISREG(st.st_mode):
        account_stat(stats, st)
        return

    # Account non-ifs files now.
    if st.st_dev != g_ifs_dev:
        if st.st_nlink > 1:
            links_key = (st.st_dev, st.st_ino)
            if links_key in links:
                return
            links.add(links_key)
        account_stat(stats, st)
        return

    # Need a canonical snapid.
    try:
        fd = os.open(fpath, os.O_RDONLY | os.O_NOFOLLOW | os.O_OPENLINK |
            O_NOSEMLOCK)
    except OSError as e:
        if e.errno == errno.ENOENT:
            return
        raise e
    try:
        # Handle the rename race between the lstat and the open.
        st = os.fstat(fd)
        if not stat.S_ISREG(st.st_mode):
            account_stat(stats, st)
            return

        lin = st.st_ino
        max_snapid = get_max_snapid(fd)
        linsid = (lin, max_snapid)

        if defer:
            # Accounting done later.
            linsids.append(linsid)
        else:
            if st.st_nlink > 1:
                links_key = (st.st_dev, linsid)
                if links_key in links:
                    return
                links.add(links_key)
            logical_data_size = get_logical_data_size(fd)
            account_stat(stats, st, logical_data_size)
    except IOError as e:
        if e.errno != errno.ENOENT and e.errno != errno.ESTALE:
            raise e
    finally:
        os.close(fd)

def account_linsid(stats, linsid):
    try:
        fd = isi.fs.lin.open(linsid, os.O_RDONLY | O_NOSEMLOCK)
    except IOError as e:
        if e.errno == errno.ENOENT:
            return
        raise e
    try:
        st = os.fstat(fd)
        logical_data_size = 0
        shadow_refs = 0
        if stat.S_ISREG(st.st_mode):
            logical_data_size = get_logical_data_size(fd)
            shadow_refs = get_shadow_refs(fd)
        account_stat(stats, st, logical_data_size, shadow_refs)
    except IOError as e:
        if e.errno != errno.ESTALE:
            raise e
    finally:
        os.close(fd)

def account_sin_partial(stats, sin, count):
    assert count >= 0
    if count == 0:
        return

    linsid = (sin, isi.fs.lin.HEAD_SNAPID)
    try:
        fd = isi.fs.lin.open(linsid, os.O_RDONLY | O_NOSEMLOCK)
    except IOError as e:
        if e.errno == errno.ENOENT:
            return
        raise e
    try:
        st = os.fstat(fd)
        assert stat.S_ISREG(st.st_mode)
        logical_data_size = get_logical_data_size(fd)
        shadow_refs = get_shadow_refs(fd)
    except IOError as e:
        if e.errno != errno.ESTALE:
            raise e
    finally:
        os.close(fd)

    # This scheme accounts the portion count/incoming of the shadow store's
    # physical blocks.  Blocks that have one reference (that ShadowStoreDelete
    # can be expected to free) are still counted.  An option should perhaps be
    # added to act as if to-be-freed blocks are already free.

    blocks = st.st_blocks
    blocks -= shadow_refs * IFS_BSIZE / STAT_BSIZE
    incoming = shadow_refs - logical_data_size / IFS_BSIZE
    if count > incoming:
        portion = 1
    else:
        portion = float(count) / incoming
    assert 0 <= portion <= 1
    blocks *= portion

    mode = stat.S_IFMT(st.st_mode)
    if mode not in stats:
        stats_mode = {
            "count": 0,
            "blocks": 0,
            "size": 0,
            "logical_data_size": 0
        }
        stats[mode] = stats_mode
    else:
        stats_mode = stats[mode]
    stats_mode["count"] += 1
    stats_mode["blocks"] += blocks
    stats_mode["size"] += st.st_size
    stats_mode["logical_data_size"] += logical_data_size


def get_sin_count_map_fd(fd):
    sin_count_map = {}
    next_lbn = 0
    while next_lbn < isi.fs.prot_group.IFS_MAX_LBN:
        lbn = next_lbn
        try:
            pg = isi.fs.prot_group.getProtGroup(fd, lbn)
        except IOError as e:
            if e.errno == errno.ENOENT:
                break
            raise e
        next_lbn = pg["last_lbn"] + 1
        if pg["type"] != isi.fs.prot_group.PG_NORMAL:
            continue
        for extent in pg["extents"]:
            addr = extent["addr"]
            if addr["type"] != isi.fs.prot_group.ADDR_SHADOW:
                continue
            sin = addr["shadow"]["sin"]
            count = extent["count"]
            sin_count_map[sin] = sin_count_map.get(sin, 0) + count
    return sin_count_map

def get_sin_count_map_linsid(linsid):
    try:
        fd = isi.fs.lin.open(linsid, os.O_RDONLY)
    except IOError as e:
        if e.errno == errno.ENOENT:
            return {}
        raise e
    try:
        if get_shadow_refs(fd) == 0:
            return {}
        return get_sin_count_map_fd(fd)
    except IOError as e:
        if e.errno == errno.ESTALE:
            return {}
        raise e
    finally:
        os.close(fd)

def sinlin_get_lins(fd, sin):
    """Get all lins which might refer to the given sin."""
    lins = []
    key = (sin, 0)
    while key[0] == sin:
        entries, key = isi.fs.sbt.sbt_get_entries(fd, key, 1000)
        for entry in entries:
            ekey = entry[0]
            esin, lin = ekey
            if esin != sin:
                break
            lins.append(lin)
    return lins

def lin_foreach_snapid(lin):
    """Generate each snapid for the given lin in the lin tree."""
    cookie = isi.fs.lin.linIterateCreate(lin, lin + 1)
    done = False
    while not done:
        cookie, linsids, pct, done = isi.fs.lin.getLins(cookie)
        for linsid in linsids:
            lin, snapid = linsid
            yield snapid

def lins_foreach_linsid(lins):
    """For each given lin, generate each (lin, snapid) in the lin tree."""
    for lin in lins:
        for snapid in lin_foreach_snapid(lin):
            yield lin, snapid

def mode_fmt(mode):
    if stat.S_ISBLK(mode):
        return "BLK"
    elif stat.S_ISCHR(mode):
        return "CHR"
    elif stat.S_ISDIR(mode):
        return "DIR"
    elif stat.S_ISFIFO(mode):
        return "FIFO"
    elif stat.S_ISLNK(mode):
        return "LNK"
    elif stat.S_ISREG(mode):
        return "REG"
    elif stat.S_ISSOCK(mode):
        return "SOCK"
    else:
        return "0%o" % mode

def connect_lins_and_sins(linsids, prefetch_depth=10):
    linsids = set(linsids)
    sins = set()
    sins_to_visit = set()
    i = 0

    # Graph search to find all linsids and sins connected from the initial
    # linsids input.
    logging.info("connect initial: %d linsids" % len(linsids))

    # Build initial set of sins_to_visit.
    for linsid in prefetch_iterate(sorted(linsids), prefetch_depth):
        sin_count_map = get_sin_count_map_linsid(linsid)
        sins_to_visit.update(sin_count_map.iterkeys())

    while sins_to_visit:
        i += 1
        logging.info("connect round %i: %d linsids, %d sins to visit" %
            (i, len(linsids), len(sins_to_visit)))

        # Build list of lins which might refer to sins_to_visit.
        sinlin_lins = []
        SINLIN_MAP_LINSID = (isi.fs.lin.SINLIN_MAP_LIN, isi.fs.lin.HEAD_SNAPID)
        sinlin_fd = isi.fs.lin.open(SINLIN_MAP_LINSID, os.O_RDONLY)
        try:
            for sin in sorted(sins_to_visit):
                lins = sinlin_get_lins(sinlin_fd, sin)
                sinlin_lins.extend(lins)
        finally:
            os.close(sinlin_fd)
        sinlin_lins = sorted(set(sinlin_lins))
        logging.info("connect round %i: %d sinlin lins" %
            (i, len(sinlin_lins)))

        # Mark sins as visited.
        sins.update(sins_to_visit)
        sins_to_visit = set()

        # Generator for each linsid of lins not already visited.
        sinlin_linsids_gen = itertools.ifilter(
            lambda linsid: linsid not in linsids,
            lins_foreach_linsid(sinlin_lins))

        # Visit each candidate linsid.
        # If the candidate refers to a known sin, update the linsids set and
        # record any additional sins to which it may connect.
        for linsid in prefetch_iterate(sinlin_linsids_gen, prefetch_depth):
            sin_count_map = get_sin_count_map_linsid(linsid)
            if sins.isdisjoint(sin_count_map.viewkeys()):
                continue
            linsids.add(linsid)
            sins_to_visit.update(sin_count_map.iterkeys())

        # Remove any sins already visited.
        sins_to_visit.difference_update(sins)

    logging.info("connect final: %d linsids, %d sins", len(linsids), len(sins))
    return linsids, sins

def map_add(dst, acc):
    """Add acc to dst, modifying dst in place."""
    for key, val in acc.iteritems():
        if key in dst:
            dst[key] += val
        else:
            dst[key] = val

def get_sin_count_map_linsids(linsids, prefetch_depth=10):
    sin_count_map = {}
    for linsid in prefetch_iterate(sorted(set(linsids)), prefetch_depth):
        sin_count_map_single = get_sin_count_map_linsid(linsid)
        map_add(sin_count_map, sin_count_map_single)
    return sin_count_map

SHADOWMODES = ("none", "quick", "span")
def get_storage_statistics(paths, shadowmode="quick", prefetch_depth=10):
    assert shadowmode in SHADOWMODES

    lin_stats = {}
    sin_stats = {}

    # Build nonreg lin stats and set of file linsids.
    linsids = []
    links = set()
    defer = shadowmode != "none"
    for path in paths:
        st = os.lstat(path)
        if not stat.S_ISDIR(st.st_mode):
            account(lin_stats, linsids, links, path, defer=defer)
            continue
        for root, dirs, files in os.walk(path):
            account(lin_stats, linsids, links, root, defer=defer)
            for file_ in files:
                account(lin_stats, linsids, links, root, file_, defer=defer)
    linsids = set(linsids)

    nonreg_lins = sum(lin_stats[mode]["count"]
        for mode in lin_stats.iterkeys()
        if not stat.S_ISREG(mode))
    nonreg_blks = sum(lin_stats[mode]["blocks"]
        for mode in lin_stats.iterkeys()
        if not stat.S_ISREG(mode))
    logging.info("reg_lins=%d, nonreg_lins=%d, nonreg_blks=%d" %
        (len(linsids), nonreg_lins, nonreg_blks))

    sins = set()
    sin_count_map = {}
    if shadowmode == "quick":
        sin_count_map = get_sin_count_map_linsids(linsids, prefetch_depth)
    elif shadowmode == "span":
        linsids, sins = connect_lins_and_sins(linsids, prefetch_depth)

    # Account lins.
    for linsid in prefetch_iterate(sorted(linsids), prefetch_depth):
        account_linsid(lin_stats, linsid)

    logging.info("lin_stats=%s" % str(lin_stats))

    # Account shadow stores which are being fully accounted.
    for sin in prefetch_iterate(sorted(sins), prefetch_depth):
        linsid = (sin, isi.fs.lin.HEAD_SNAPID)
        account_linsid(sin_stats, linsid)

    # Account shadow stores which are being partially accounted.
    assert sins.isdisjoint(sin_count_map.viewkeys())
    for sin in prefetch_iterate(sorted(sin_count_map.iterkeys()),
            prefetch_depth):
        account_sin_partial(sin_stats, sin, sin_count_map[sin])

    logging.info("sin_stats=%s" % str(sin_stats))

    return lin_stats, sin_stats

def format_accounts(lin_stats, sin_stats=None):
    line_fmt = "%4s %16d %19d %19d %17d"
    header = "%4s %16s %19s %19s %17s" % (
        "Mode", "Count", "Logical data size", "Size", "Blocks")
    lines = [header]

    modes = sorted(lin_stats.keys())
    for mode in modes:
        st = lin_stats[mode]
        line = line_fmt % (mode_fmt(mode), st["count"],
            st["logical_data_size"], st["size"], st["blocks"])
        lines.append(line)

    if sin_stats and stat.S_IFREG in sin_stats:
        st = sin_stats[stat.S_IFREG]
        line = line_fmt % ("SIN", st["count"],
            st["logical_data_size"], st["size"], st["blocks"])
        lines.append(line)

    return "\n".join(lines)

def calc_efficiencies_overall(lin_stats, sin_stats=None):
    """Compute overall storage efficiency."""
    size = 0
    logical_data_size = 0
    blocks = 0

    for st in lin_stats.itervalues():
        size += st["size"]
        logical_data_size += st["logical_data_size"]
        blocks += st["blocks"]
    if sin_stats and stat.S_IFREG in sin_stats:
        blocks += sin_stats[stat.S_IFREG]["blocks"]

    used_bytes = blocks * STAT_BSIZE
    if used_bytes == 0:
        size_eff = 0
        ldsz_eff = 0
    else:
        size_eff = float(size) / used_bytes
        ldsz_eff = float(logical_data_size) / used_bytes

    return size_eff, ldsz_eff

def calc_efficiencies_regular(lin_stats, sin_stats=None):
    """Compute storage efficiency of regular files."""
    size = 0
    logical_data_size = 0
    blocks = 0

    if stat.S_IFREG in lin_stats:
        st = lin_stats[stat.S_IFREG]
        size += st["size"]
        logical_data_size += st["logical_data_size"]
        blocks += st["blocks"]
    if sin_stats and stat.S_IFREG in sin_stats:
        blocks += sin_stats[stat.S_IFREG]["blocks"]

    used_bytes = blocks * STAT_BSIZE
    if used_bytes == 0:
        size_eff = 0
        ldsz_eff = 0
    else:
        size_eff = float(size) / used_bytes
        ldsz_eff = float(logical_data_size) / used_bytes

    return size_eff, ldsz_eff

def make_option_parser():
    import optparse
    usage = "usage: %prog [options] [file ...]"
    parser = optparse.OptionParser(usage=usage)

    parser.add_option("-d", "--debug", action="count", default=0,
        help="Output debug logging.")
    parser.add_option("-s", "--shadow-mode", choices=SHADOWMODES,
        default="quick",
        help="Method of accounting for shadow references: %s.  "
        "Default is quick." % ", ".join(SHADOWMODES))

    return parser

def main(args):
    option_parser = make_option_parser()
    (options, paths) = option_parser.parse_args(args=args)

    if not paths:
        paths = ["."]

    if options.debug > 1:
        logging.getLogger().setLevel(logging.DEBUG)
    elif options.debug > 0:
        logging.getLogger().setLevel(logging.INFO)

    lin_stats, sin_stats = get_storage_statistics(paths,
        shadowmode=options.shadow_mode)

    print format_accounts(lin_stats, sin_stats)
    if sin_stats:
        print "Shadow store usage may be affected by the ShadowStoreDelete " \
            "job."

    size_eff, ldsz_eff = calc_efficiencies_overall(lin_stats, sin_stats)
    fsize_eff, fldsz_eff = calc_efficiencies_regular(lin_stats, sin_stats)

    print
    print "                  Storage efficiency"
    print "File data        ", fsize_eff
    print "File logical data", fldsz_eff
    print "Overall          ", size_eff
    print "Overall logical  ", ldsz_eff

if __name__ == '__main__':
    main(sys.argv[1:])
