cmd/midx: --auto mode can combine existing midx files now.

Previously, --auto would *only* create a midx from not-already-midxed .idx
files.  This wasn't optimal since you'd eventually end up with a tonne of
.midx files, which is just as bad as a tonne of .idx files.

Now we'll try to maintain a maximum number of midx files using a
highwater/lowwater mark.  That means the number of active midx files should
now stay between 2 and 5, and you can run 'bup midx -a' as often as you
want.

'bup midx -f' will still make sure everything is in a single .midx file,
which is an efficient thing to run every now and then.

'bup midx -af' is the same, but uses existing midx files rather than forcing
bup to start from only .idx files.  Theoretically this should always be
faster than, and never be worse than, 'bup midx -f'.

Bonus: 'bup midx -a' now works when there's a limited number of file
descriptors.  The previous fix only worked properly with 'bup midx -f'.
(This was rarely a problem since 'bup midx -a' would only ever touch the
last few .idx files, so it didn't need many file descriptors.)

Signed-off-by: Avery Pennarun <apenwarr@gmail.com>

diff --git a/cmd/midx-cmd.py b/cmd/midx-cmd.py
index e52920717e6b693049ec1eec626a9fe4de558d54..d0e96060d7e3732b30d426902a6644258949bec4 100755 (executable)
--- a/cmd/midx-cmd.py
+++ b/cmd/midx-cmd.py
@@ -6,6 +6,14 @@ from bup.helpers import *
 PAGE_SIZE=4096
 SHA_PER_PAGE=PAGE_SIZE/20.
 
+optspec = """
+bup midx [options...] <idxnames...>
+--
+o,output=  output midx filename (default: auto-generated)
+a,auto     automatically create .midx from any unindexed .idx files
+f,force    automatically create .midx from *all* .idx files
+max-files= maximum number of idx files to open at once [-1]
+"""
 
 def _group(l, count):
     for i in xrange(0, len(l), count):
@@ -30,7 +38,7 @@ def merge(idxlist, bits, table):
         yield e
 
 
-def do_midx(outdir, outfilename, infilenames):
+def _do_midx(outdir, outfilename, infilenames):
     if not outfilename:
         assert(outdir)
         sum = Sha1('\0'.join(infilenames)).hexdigest()
@@ -38,13 +46,17 @@ def do_midx(outdir, outfilename, infilenames):
     
     inp = []
     total = 0
+    allfilenames = {}
     for name in infilenames:
-        ix = git.PackIdx(name)
+        ix = git.open_idx(name)
+        for n in ix.idxnames:
+            allfilenames[n] = 1
         inp.append(ix)
         total += len(ix)
 
     log('Merging %d indexes (%d objects).\n' % (len(infilenames), total))
     if (not opt.force and (total < 1024 and len(infilenames) < 3)) \
+       or len(infilenames) < 2 \
        or (opt.force and not total):
         log('midx: nothing to do.\n')
         return
@@ -69,7 +81,7 @@ def do_midx(outdir, outfilename, infilenames):
     for e in merge(inp, bits, table):
         f.write(e)
         
-    f.write('\0'.join(os.path.basename(p) for p in infilenames))
+    f.write('\0'.join(os.path.basename(p) for p in allfilenames.keys()))
 
     f.seek(12)
     f.write(struct.pack('!%dI' % entries, *table))
@@ -87,16 +99,81 @@ def do_midx(outdir, outfilename, infilenames):
             assert(i == pi.next())
             assert(p.exists(i))
 
-    print outfilename
+    return total,outfilename
+
+
+def do_midx(outdir, outfilename, infilenames):
+    rv = _do_midx(outdir, outfilename, infilenames)
+    if rv:
+        print rv[1]
+
+
+def do_midx_dir(path):
+    already = {}
+    sizes = {}
+    if opt.force and not opt.auto:
+        midxs = []   # don't use existing midx files
+    else:
+        midxs = glob.glob('%s/*.midx' % path)
+        contents = {}
+        for mname in midxs:
+            m = git.open_idx(mname)
+            contents[mname] = [('%s/%s' % (path,i)) for i in m.idxnames]
+            sizes[mname] = len(m)
+                    
+        # sort the biggest midxes first, so that we can eliminate smaller
+        # redundant ones that come later in the list
+        midxs.sort(lambda x,y: -cmp(sizes[x], sizes[y]))
+        
+        for mname in midxs:
+            any = 0
+            for iname in contents[mname]:
+                if not already.get(iname):
+                    already[iname] = 1
+                    any = 1
+            if not any:
+                log('%r is redundant\n' % mname)
+                unlink(mname)
+                already[mname] = 1
+
+    midxs = [k for k in midxs if not already.get(k)]
+    idxs = [k for k in glob.glob('%s/*.idx' % path) if not already.get(k)]
+
+    for iname in idxs:
+        i = git.open_idx(iname)
+        sizes[iname] = len(i)
+
+    all = [(sizes[n],n) for n in (midxs + idxs)]
+    
+    # FIXME: what are the optimal values?  Does this make sense?
+    DESIRED_HWM = opt.force and 1 or 5
+    DESIRED_LWM = opt.force and 1 or 2
+    existed = dict((name,1) for sz,name in all)
+    log('%d indexes; want no more than %d.\n' % (len(all), DESIRED_HWM))
+    if len(all) <= DESIRED_HWM:
+        log('Nothing to do.\n')
+    while len(all) > DESIRED_HWM:
+        all.sort()
+        part1 = [name for sz,name in all[:len(all)-DESIRED_LWM+1]]
+        part2 = all[len(all)-DESIRED_LWM+1:]
+        all = list(do_midx_group(path, part1)) + part2
+        if len(all) > DESIRED_HWM:
+            log('\nStill too many indexes (%d > %d).  Merging again.\n'
+                % (len(all), DESIRED_HWM))
+
+    for sz,name in all:
+        if not existed.get(name):
+            print name
+
+
+def do_midx_group(outdir, infiles):
+    for sublist in _group(infiles, opt.max_files):
+        rv = _do_midx(path, None, sublist)
+        if rv:
+            yield rv
+
+
 
-optspec = """
-bup midx [options...] <idxnames...>
---
-o,output=  output midx filename (default: auto-generated)
-a,auto     automatically create .midx from any unindexed .idx files
-f,force    automatically create .midx from *all* .idx files
-max-files= maximum number of idx files to open at once [-1]
-"""
 o = options.Options('bup midx', optspec)
 (opt, flags, extra) = o.parse(sys.argv[1:])
 
@@ -116,18 +193,7 @@ elif opt.auto or opt.force:
     paths += glob.glob(git.repo('index-cache/*/.'))
     for path in paths:
         log('midx: scanning %s\n' % path)
-        if opt.force:
-            idxs = glob.glob('%s/*.idx' % path)
-            for sublist in _group(idxs, opt.max_files):
-                do_midx(path, opt.output, sublist)
-        elif opt.auto:
-            m = git.PackIdxList(path)
-            needed = {}
-            for pack in m.packs:  # only .idx files without a .midx are open
-                if pack.name.endswith('.idx'):
-                    needed[pack.name] = 1
-            del m
-            do_midx(path, opt.output, needed.keys())
+        do_midx_dir(path)
         log('\n')
 else:
     o.fatal("you must use -f or -a or provide input filenames")

diff --git a/lib/bup/git.py b/lib/bup/git.py
index 3bbd25a59c65ea523612ccc2fb3e5b9a27b44a1e..3612c836dbdec0bd296b63181657785767ae1ce7 100644 (file)
--- a/lib/bup/git.py
+++ b/lib/bup/git.py
@@ -133,6 +133,7 @@ class PackIdx:
     """Object representation of a Git pack index file."""
     def __init__(self, filename):
         self.name = filename
+        self.idxnames = [self.name]
         self.map = mmap_read(open(filename))
         assert(str(self.map[0:8]) == '\377tOc\0\0\0\2')
         self.fanout = list(struct.unpack('!256I',
@@ -411,6 +412,15 @@ def _shalist_sort_key(ent):
         return name
 
 
+def open_idx(filename):
+    if filename.endswith('.idx'):
+        return PackIdx(filename)
+    elif filename.endswith('.midx'):
+        return PackMidx(filename)
+    else:
+        raise GitError('idx filenames must end with .idx or .midx')
+
+
 def idxmerge(idxlist):
     """Generate a list of all the objects reachable in a PackIdxList."""
     total = sum(len(i) for i in idxlist)