lib/cmd/margin-cmd.py

   1 #!/bin/sh
   2 """": # -*-python-*-
   3 # https://sourceware.org/bugzilla/show_bug.cgi?id=26034
   4 export "BUP_ARGV_0"="$0"
   5 arg_i=1
   6 for arg in "$@"; do
   7     export "BUP_ARGV_${arg_i}"="$arg"
   8     shift
   9     arg_i=$((arg_i + 1))
  10 done
  11 # Here to end of preamble replaced during install
  12 bup_python="$(dirname "$0")/../../config/bin/python" || exit $?
  13 exec "$bup_python" "$0"
  14 """
  15 # end of bup preamble
  16
  17 from __future__ import absolute_import
  18
  19 # Intentionally replace the dirname "$0" that python prepends
  20 import os, sys
  21 sys.path[0] = os.path.dirname(os.path.realpath(__file__)) + '/..'
  22
  23 import math, struct
  24
  25 from bup import compat, options, git, _helpers
  26 from bup.helpers import log
  27 from bup.io import byte_stream
  28
  29 POPULATION_OF_EARTH=6.7e9  # as of September, 2010
  30
  31 optspec = """
  32 bup margin
  33 --
  34 predict    Guess object offsets and report the maximum deviation
  35 ignore-midx  Don't use midx files; use only plain pack idx files.
  36 """
  37 o = options.Options(optspec)
  38 opt, flags, extra = o.parse(compat.argv[1:])
  39
  40 if extra:
  41     o.fatal("no arguments expected")
  42
  43 git.check_repo_or_die()
  44
  45 mi = git.PackIdxList(git.repo(b'objects/pack'), ignore_midx=opt.ignore_midx)
  46
  47 def do_predict(ix, out):
  48     total = len(ix)
  49     maxdiff = 0
  50     for count,i in enumerate(ix):
  51         prefix = struct.unpack('!Q', i[:8])[0]
  52         expected = prefix * total // (1 << 64)
  53         diff = count - expected
  54         maxdiff = max(maxdiff, abs(diff))
  55     out.write(b'%d of %d (%.3f%%) '
  56               % (maxdiff, len(ix), maxdiff * 100.0 / len(ix)))
  57     out.flush()
  58     assert(count+1 == len(ix))
  59
  60 sys.stdout.flush()
  61 out = byte_stream(sys.stdout)
  62
  63 if opt.predict:
  64     if opt.ignore_midx:
  65         for pack in mi.packs:
  66             do_predict(pack, out)
  67     else:
  68         do_predict(mi, out)
  69 else:
  70     # default mode: find longest matching prefix
  71     last = b'\0'*20
  72     longmatch = 0
  73     for i in mi:
  74         if i == last:
  75             continue
  76         #assert(str(i) >= last)
  77         pm = _helpers.bitmatch(last, i)
  78         longmatch = max(longmatch, pm)
  79         last = i
  80     out.write(b'%d\n' % longmatch)
  81     log('%d matching prefix bits\n' % longmatch)
  82     doublings = math.log(len(mi), 2)
  83     bpd = longmatch / doublings
  84     log('%.2f bits per doubling\n' % bpd)
  85     remain = 160 - longmatch
  86     rdoublings = remain / bpd
  87     log('%d bits (%.2f doublings) remaining\n' % (remain, rdoublings))
  88     larger = 2**rdoublings
  89     log('%g times larger is possible\n' % larger)
  90     perperson = larger/POPULATION_OF_EARTH
  91     log('\nEveryone on earth could have %d data sets like yours, all in one\n'
  92         'repository, and we would expect 1 object collision.\n'
  93         % int(perperson))