cmd/midx-cmd.py

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