cmd/midx-cmd.py

   1 #!/usr/bin/env python
   2 import sys, math, struct, glob, resource
   3 import tempfile, shutil
   4 from bup import options, git
   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 create .midx from any unindexed .idx files
  15 f,force    automatically create .midx from *all* .idx files
  16 p,print    print names of generated midx files
  17 max-files= maximum number of idx files to open at once [-1]
  18 dir=       directory containing idx/midx files
  19 """
  20
  21 def _group(l, count):
  22     for i in xrange(0, len(l), count):
  23         yield l[i:i+count]
  24
  25
  26 def max_files():
  27     mf = min(resource.getrlimit(resource.RLIMIT_NOFILE))
  28     if mf > 32:
  29         mf -= 20  # just a safety margin
  30     else:
  31         mf -= 6   # minimum safety margin
  32     return mf
  33
  34
  35 def merge_into(tf_sha, tf_nmap, idxlist, bits, entries, total):
  36     prefix = 0
  37     it = git.idxmerge(idxlist, final_progress=False, total=total)
  38     for i, (e, idx) in enumerate(it):
  39         new_prefix = git.extract_bits(e, bits)
  40         if new_prefix != prefix:
  41             for p in xrange(prefix, new_prefix):
  42                 yield i
  43             prefix = new_prefix
  44         tf_sha.write(e)
  45         tf_nmap.write(struct.pack('!I', idx))
  46     i += 1
  47     for p in xrange(prefix, entries):
  48         yield i
  49
  50
  51 def _do_midx(outdir, outfilename, infilenames, prefixstr):
  52     if not outfilename:
  53         assert(outdir)
  54         sum = Sha1('\0'.join(infilenames)).hexdigest()
  55         outfilename = '%s/midx-%s.midx' % (outdir, sum)
  56
  57     inp = []
  58     total = 0
  59     allfilenames = []
  60     for name in infilenames:
  61         ix = git.open_idx(name)
  62         inp.append(ix.iter_with_idx_i(len(allfilenames)))
  63         for n in ix.idxnames:
  64             allfilenames.append(os.path.basename(n))
  65         total += len(ix)
  66
  67     log('midx: %screating from %d files (%d objects).\n'
  68         % (prefixstr, len(infilenames), total))
  69     if (not opt.force and (total < 1024 and len(infilenames) < 3)) \
  70        or len(infilenames) < 2 \
  71        or (opt.force and not total):
  72         debug1('midx: nothing to do.\n')
  73         return
  74
  75     pages = int(total/SHA_PER_PAGE) or 1
  76     bits = int(math.ceil(math.log(pages, 2)))
  77     entries = 2**bits
  78     debug1('midx: table size: %d (%d bits)\n' % (entries*4, bits))
  79
  80     try:
  81         os.unlink(outfilename)
  82     except OSError:
  83         pass
  84     f = open(outfilename + '.tmp', 'w+')
  85     f.write('MIDX')
  86     f.write(struct.pack('!II', git.MIDX_VERSION, bits))
  87     assert(f.tell() == 12)
  88
  89     tf_sha = tempfile.TemporaryFile(dir=outdir)
  90     tf_nmap = tempfile.TemporaryFile(dir=outdir)
  91     for t in merge_into(tf_sha, tf_nmap, inp, bits, entries, total):
  92         f.write(struct.pack('!I', t))
  93     assert(f.tell() == 12 + 4*entries)
  94
  95     tf_sha.seek(0)
  96     shutil.copyfileobj(tf_sha, f)
  97     tf_sha.close()
  98     assert(f.tell() == 12 + 4*entries + 20*t) # t may be < total due to dupes
  99
 100     tf_nmap.seek(0)
 101     shutil.copyfileobj(tf_nmap, f)
 102     tf_nmap.close()
 103     assert(f.tell() == 12 + 4*entries + 24*t) # t may be < total due to dupes
 104
 105     f.write('\0'.join(allfilenames))
 106     f.close()
 107     os.rename(outfilename + '.tmp', outfilename)
 108
 109     # this is just for testing
 110     if 0:
 111         p = git.PackMidx(outfilename)
 112         assert(len(p.idxnames) == len(infilenames))
 113         print p.idxnames
 114         assert(len(p) == total)
 115         for pe, e in p, git.idxmerge(inp, final_progress=False):
 116             assert(i == pi.next())
 117             assert(p.exists(i))
 118
 119     return total, outfilename
 120
 121
 122 def do_midx(outdir, outfilename, infilenames, prefixstr):
 123     rv = _do_midx(outdir, outfilename, infilenames, prefixstr)
 124     if rv and opt['print']:
 125         print rv[1]
 126
 127
 128 def do_midx_dir(path):
 129     already = {}
 130     sizes = {}
 131     if opt.force and not opt.auto:
 132         midxs = []   # don't use existing midx files
 133     else:
 134         midxs = glob.glob('%s/*.midx' % path)
 135         contents = {}
 136         for mname in midxs:
 137             m = git.open_idx(mname)
 138             contents[mname] = [('%s/%s' % (path,i)) for i in m.idxnames]
 139             sizes[mname] = len(m)
 140
 141         # sort the biggest midxes first, so that we can eliminate smaller
 142         # redundant ones that come later in the list
 143         midxs.sort(lambda x,y: -cmp(sizes[x], sizes[y]))
 144
 145         for mname in midxs:
 146             any = 0
 147             for iname in contents[mname]:
 148                 if not already.get(iname):
 149                     already[iname] = 1
 150                     any = 1
 151             if not any:
 152                 debug1('%r is redundant\n' % mname)
 153                 unlink(mname)
 154                 already[mname] = 1
 155
 156     midxs = [k for k in midxs if not already.get(k)]
 157     idxs = [k for k in glob.glob('%s/*.idx' % path) if not already.get(k)]
 158
 159     for iname in idxs:
 160         i = git.open_idx(iname)
 161         sizes[iname] = len(i)
 162
 163     all = [(sizes[n],n) for n in (midxs + idxs)]
 164
 165     # FIXME: what are the optimal values?  Does this make sense?
 166     DESIRED_HWM = opt.force and 1 or 5
 167     DESIRED_LWM = opt.force and 1 or 2
 168     existed = dict((name,1) for sz,name in all)
 169     debug1('midx: %d indexes; want no more than %d.\n'
 170            % (len(all), DESIRED_HWM))
 171     if len(all) <= DESIRED_HWM:
 172         debug1('midx: nothing to do.\n')
 173     while len(all) > DESIRED_HWM:
 174         all.sort()
 175         part1 = [name for sz,name in all[:len(all)-DESIRED_LWM+1]]
 176         part2 = all[len(all)-DESIRED_LWM+1:]
 177         all = list(do_midx_group(path, part1)) + part2
 178         if len(all) > DESIRED_HWM:
 179             debug1('\nStill too many indexes (%d > %d).  Merging again.\n'
 180                    % (len(all), DESIRED_HWM))
 181
 182     if opt['print']:
 183         for sz,name in all:
 184             if not existed.get(name):
 185                 print name
 186
 187
 188 def do_midx_group(outdir, infiles):
 189     groups = list(_group(infiles, opt.max_files))
 190     gprefix = ''
 191     for n,sublist in enumerate(groups):
 192         if len(groups) != 1:
 193             gprefix = 'Group %d: ' % (n+1)
 194         rv = _do_midx(path, None, sublist, gprefix)
 195         if rv:
 196             yield rv
 197
 198
 199 handle_ctrl_c()
 200
 201 o = options.Options(optspec)
 202 (opt, flags, extra) = o.parse(sys.argv[1:])
 203
 204 if extra and (opt.auto or opt.force):
 205     o.fatal("you can't use -f/-a and also provide filenames")
 206
 207 git.check_repo_or_die()
 208
 209 if opt.max_files < 0:
 210     opt.max_files = max_files()
 211 assert(opt.max_files >= 5)
 212
 213 if extra:
 214     do_midx(git.repo('objects/pack'), opt.output, extra, '')
 215 elif opt.auto or opt.force:
 216     if opt.dir:
 217         paths = [opt.dir]
 218     else:
 219         paths = [git.repo('objects/pack')]
 220         paths += glob.glob(git.repo('index-cache/*/.'))
 221     for path in paths:
 222         debug1('midx: scanning %s\n' % path)
 223         do_midx_dir(path)
 224         debug1('\n')
 225 else:
 226     o.fatal("you must use -f or -a or provide input filenames")