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