cmd/midx-cmd.py

   1 #!/usr/bin/env python
   2 import sys, math, struct, glob, resource
   3 import tempfile
   4 from bup import options, git, midx, _helpers, xstat
   5 from bup.helpers import *
   6
   7 PAGE_SIZE=4096
   8 SHA_PER_PAGE=PAGE_SIZE/20.
   9
  10 optspec = """
  11 bup midx [options...] <idxnames...>
  12 --
  13 o,output=  output midx filename (default: auto-generated)
  14 a,auto     automatically use all existing .midx/.idx files as input
  15 f,force    merge produce exactly one .midx containing all objects
  16 p,print    print names of generated midx files
  17 check      validate contents of the given midx files (with -a, all midx files)
  18 max-files= maximum number of idx files to open at once [-1]
  19 d,dir=     directory containing idx/midx files
  20 """
  21
  22 merge_into = _helpers.merge_into
  23
  24
  25 def _group(l, count):
  26     for i in xrange(0, len(l), count):
  27         yield l[i:i+count]
  28
  29
  30 def max_files():
  31     mf = min(resource.getrlimit(resource.RLIMIT_NOFILE))
  32     if mf > 32:
  33         mf -= 20  # just a safety margin
  34     else:
  35         mf -= 6   # minimum safety margin
  36     return mf
  37
  38
  39 def check_midx(name):
  40     nicename = git.repo_rel(name)
  41     log('Checking %s.\n' % nicename)
  42     try:
  43         ix = git.open_idx(name)
  44     except git.GitError, e:
  45         add_error('%s: %s' % (name, e))
  46         return
  47     for count,subname in enumerate(ix.idxnames):
  48         sub = git.open_idx(os.path.join(os.path.dirname(name), subname))
  49         for ecount,e in enumerate(sub):
  50             if not (ecount % 1234):
  51                 qprogress('  %d/%d: %s %d/%d\r'
  52                           % (count, len(ix.idxnames),
  53                              git.shorten_hash(subname), ecount, len(sub)))
  54             if not sub.exists(e):
  55                 add_error("%s: %s: %s missing from idx"
  56                           % (nicename, git.shorten_hash(subname),
  57                              str(e).encode('hex')))
  58             if not ix.exists(e):
  59                 add_error("%s: %s: %s missing from midx"
  60                           % (nicename, git.shorten_hash(subname),
  61                              str(e).encode('hex')))
  62     prev = None
  63     for ecount,e in enumerate(ix):
  64         if not (ecount % 1234):
  65             qprogress('  Ordering: %d/%d\r' % (ecount, len(ix)))
  66         if not e >= prev:
  67             add_error('%s: ordering error: %s < %s'
  68                       % (nicename,
  69                          str(e).encode('hex'), str(prev).encode('hex')))
  70         prev = e
  71
  72
  73 _first = None
  74 def _do_midx(outdir, outfilename, infilenames, prefixstr):
  75     global _first
  76     if not outfilename:
  77         assert(outdir)
  78         sum = Sha1('\0'.join(infilenames)).hexdigest()
  79         outfilename = '%s/midx-%s.midx' % (outdir, sum)
  80
  81     inp = []
  82     total = 0
  83     allfilenames = []
  84     for name in infilenames:
  85         ix = git.open_idx(name)
  86         inp.append((
  87             ix.map,
  88             len(ix),
  89             ix.sha_ofs,
  90             isinstance(ix, midx.PackMidx) and ix.which_ofs or 0,
  91             len(allfilenames),
  92         ))
  93         for n in ix.idxnames:
  94             allfilenames.append(os.path.basename(n))
  95         total += len(ix)
  96     inp.sort(lambda x,y: cmp(str(y[0][y[2]:y[2]+20]),str(x[0][x[2]:x[2]+20])))
  97
  98     if not _first: _first = outdir
  99     dirprefix = (_first != outdir) and git.repo_rel(outdir)+': ' or ''
 100     debug1('midx: %s%screating from %d files (%d objects).\n'
 101            % (dirprefix, prefixstr, len(infilenames), total))
 102     if (opt.auto and (total < 1024 and len(infilenames) < 3)) \
 103        or ((opt.auto or opt.force) and len(infilenames) < 2) \
 104        or (opt.force and not total):
 105         debug1('midx: nothing to do.\n')
 106         return
 107
 108     pages = int(total/SHA_PER_PAGE) or 1
 109     bits = int(math.ceil(math.log(pages, 2)))
 110     entries = 2**bits
 111     debug1('midx: table size: %d (%d bits)\n' % (entries*4, bits))
 112
 113     unlink(outfilename)
 114     f = open(outfilename + '.tmp', 'w+b')
 115     f.write('MIDX')
 116     f.write(struct.pack('!II', midx.MIDX_VERSION, bits))
 117     assert(f.tell() == 12)
 118
 119     f.truncate(12 + 4*entries + 20*total + 4*total)
 120     f.flush()
 121     fdatasync(f.fileno())
 122
 123     fmap = mmap_readwrite(f, close=False)
 124
 125     count = merge_into(fmap, bits, total, inp)
 126     del fmap # Assume this calls msync() now.
 127
 128     f.seek(0, os.SEEK_END)
 129     f.write('\0'.join(allfilenames))
 130     f.close()
 131     os.rename(outfilename + '.tmp', outfilename)
 132
 133     # this is just for testing
 134     if 0:
 135         p = midx.PackMidx(outfilename)
 136         assert(len(p.idxnames) == len(infilenames))
 137         print p.idxnames
 138         assert(len(p) == total)
 139         for pe, e in p, git.idxmerge(inp, final_progress=False):
 140             pin = pi.next()
 141             assert(i == pin)
 142             assert(p.exists(i))
 143
 144     return total, outfilename
 145
 146
 147 def do_midx(outdir, outfilename, infilenames, prefixstr):
 148     rv = _do_midx(outdir, outfilename, infilenames, prefixstr)
 149     if rv and opt['print']:
 150         print rv[1]
 151
 152
 153 def do_midx_dir(path):
 154     already = {}
 155     sizes = {}
 156     if opt.force and not opt.auto:
 157         midxs = []   # don't use existing midx files
 158     else:
 159         midxs = glob.glob('%s/*.midx' % path)
 160         contents = {}
 161         for mname in midxs:
 162             m = git.open_idx(mname)
 163             contents[mname] = [('%s/%s' % (path,i)) for i in m.idxnames]
 164             sizes[mname] = len(m)
 165
 166         # sort the biggest+newest midxes first, so that we can eliminate
 167         # smaller (or older) redundant ones that come later in the list
 168         midxs.sort(key=lambda ix: (-sizes[ix], -xstat.stat(ix).st_mtime))
 169
 170         for mname in midxs:
 171             any = 0
 172             for iname in contents[mname]:
 173                 if not already.get(iname):
 174                     already[iname] = 1
 175                     any = 1
 176             if not any:
 177                 debug1('%r is redundant\n' % mname)
 178                 unlink(mname)
 179                 already[mname] = 1
 180
 181     midxs = [k for k in midxs if not already.get(k)]
 182     idxs = [k for k in glob.glob('%s/*.idx' % path) if not already.get(k)]
 183
 184     for iname in idxs:
 185         i = git.open_idx(iname)
 186         sizes[iname] = len(i)
 187
 188     all = [(sizes[n],n) for n in (midxs + idxs)]
 189
 190     # FIXME: what are the optimal values?  Does this make sense?
 191     DESIRED_HWM = opt.force and 1 or 5
 192     DESIRED_LWM = opt.force and 1 or 2
 193     existed = dict((name,1) for sz,name in all)
 194     debug1('midx: %d indexes; want no more than %d.\n'
 195            % (len(all), DESIRED_HWM))
 196     if len(all) <= DESIRED_HWM:
 197         debug1('midx: nothing to do.\n')
 198     while len(all) > DESIRED_HWM:
 199         all.sort()
 200         part1 = [name for sz,name in all[:len(all)-DESIRED_LWM+1]]
 201         part2 = all[len(all)-DESIRED_LWM+1:]
 202         all = list(do_midx_group(path, part1)) + part2
 203         if len(all) > DESIRED_HWM:
 204             debug1('\nStill too many indexes (%d > %d).  Merging again.\n'
 205                    % (len(all), DESIRED_HWM))
 206
 207     if opt['print']:
 208         for sz,name in all:
 209             if not existed.get(name):
 210                 print name
 211
 212
 213 def do_midx_group(outdir, infiles):
 214     groups = list(_group(infiles, opt.max_files))
 215     gprefix = ''
 216     for n,sublist in enumerate(groups):
 217         if len(groups) != 1:
 218             gprefix = 'Group %d: ' % (n+1)
 219         rv = _do_midx(path, None, sublist, gprefix)
 220         if rv:
 221             yield rv
 222
 223
 224 handle_ctrl_c()
 225
 226 o = options.Options(optspec)
 227 (opt, flags, extra) = o.parse(sys.argv[1:])
 228
 229 if extra and (opt.auto or opt.force):
 230     o.fatal("you can't use -f/-a and also provide filenames")
 231 if opt.check and (not extra and not opt.auto):
 232     o.fatal("if using --check, you must provide filenames or -a")
 233
 234 git.check_repo_or_die()
 235
 236 if opt.max_files < 0:
 237     opt.max_files = max_files()
 238 assert(opt.max_files >= 5)
 239
 240 if opt.check:
 241     # check existing midx files
 242     if extra:
 243         midxes = extra
 244     else:
 245         midxes = []
 246         paths = opt.dir and [opt.dir] or git.all_packdirs()
 247         for path in paths:
 248             debug1('midx: scanning %s\n' % path)
 249             midxes += glob.glob(os.path.join(path, '*.midx'))
 250     for name in midxes:
 251         check_midx(name)
 252     if not saved_errors:
 253         log('All tests passed.\n')
 254 else:
 255     if extra:
 256         do_midx(git.repo('objects/pack'), opt.output, extra, '')
 257     elif opt.auto or opt.force:
 258         paths = opt.dir and [opt.dir] or git.all_packdirs()
 259         for path in paths:
 260             debug1('midx: scanning %s\n' % path)
 261             do_midx_dir(path)
 262     else:
 263         o.fatal("you must use -f or -a or provide input filenames")
 264
 265 if saved_errors:
 266     log('WARNING: %d errors encountered.\n' % len(saved_errors))
 267     sys.exit(1)