lib/bup/gc.py

   1 import glob, os, subprocess, sys, tempfile
   2 from bup import bloom, git, midx
   3 from bup.git import MissingObject, walk_object
   4 from bup.helpers import Nonlocal, log, progress, qprogress
   5 from os.path import basename
   6
   7 # This garbage collector uses a Bloom filter to track the live objects
   8 # during the mark phase.  This means that the collection is
   9 # probabilistic; it may retain some (known) percentage of garbage, but
  10 # it can also work within a reasonable, fixed RAM budget for any
  11 # particular percentage and repository size.
  12 #
  13 # The collection proceeds as follows:
  14 #
  15 #   - Scan all live objects by walking all of the refs, and insert
  16 #     every hash encountered into a new Bloom "liveness" filter.
  17 #     Compute the size of the liveness filter based on the total
  18 #     number of objects in the repository.  This is the "mark phase".
  19 #
  20 #   - Clear the data that's dependent on the repository's object set,
  21 #     i.e. the reflog, the normal Bloom filter, and the midxes.
  22 #
  23 #   - Traverse all of the pack files, consulting the liveness filter
  24 #     to decide which objects to keep.
  25 #
  26 #     For each pack file, rewrite it iff it probably contains more
  27 #     than (currently) 10% garbage (computed by an initial traversal
  28 #     of the packfile in consultation with the liveness filter).  To
  29 #     rewrite, traverse the packfile (again) and write each hash that
  30 #     tests positive against the liveness filter to a packwriter.
  31 #
  32 #     During the traversal of all of the packfiles, delete redundant,
  33 #     old packfiles only after the packwriter has finished the pack
  34 #     that contains all of their live objects.
  35 #
  36 # The current code unconditionally tracks the set of tree hashes seen
  37 # during the mark phase, and skips any that have already been visited.
  38 # This should decrease the IO load at the cost of increased RAM use.
  39
  40 # FIXME: add a bloom filter tuning parameter?
  41
  42
  43 def count_objects(dir, verbosity):
  44     # For now we'll just use open_idx(), but we could probably be much
  45     # more efficient since all we need is a single integer (the last
  46     # fanout entry) from each index.
  47     object_count = 0
  48     indexes = glob.glob(os.path.join(dir, '*.idx'))
  49     for i, idx_name in enumerate(indexes):
  50         if verbosity:
  51             log('found %d objects (%d/%d %s)\r'
  52                 % (object_count, i + 1, len(indexes), basename(idx_name)))
  53         idx = git.open_idx(idx_name)
  54         object_count += len(idx)
  55     return object_count
  56
  57
  58 def report_live_item(n, total, ref_name, ref_id, item, verbosity):
  59     status = 'scanned %02.2f%%' % (n * 100.0 / total)
  60     hex_id = ref_id.encode('hex')
  61     dirslash = '/' if item.type == 'tree' else ''
  62     chunk_path = item.chunk_path
  63
  64     if chunk_path:
  65         if verbosity < 4:
  66             return
  67         ps = '/'.join(item.path)
  68         chunk_ps = '/'.join(chunk_path)
  69         log('%s %s:%s/%s%s\n' % (status, hex_id, ps, chunk_ps, dirslash))
  70         return
  71
  72     # Top commit, for example has none.
  73     demangled = git.demangle_name(item.path[-1], item.mode)[0] if item.path \
  74                 else None
  75
  76     # Don't print mangled paths unless the verbosity is over 3.
  77     if demangled:
  78         ps = '/'.join(item.path[:-1] + [demangled])
  79         if verbosity == 1:
  80             qprogress('%s %s:%s%s\r' % (status, hex_id, ps, dirslash))
  81         elif (verbosity > 1 and item.type == 'tree') \
  82              or (verbosity > 2 and item.type == 'blob'):
  83             log('%s %s:%s%s\n' % (status, hex_id, ps, dirslash))
  84     elif verbosity > 3:
  85         ps = '/'.join(item.path)
  86         log('%s %s:%s%s\n' % (status, hex_id, ps, dirslash))
  87
  88
  89 def find_live_objects(existing_count, cat_pipe, verbosity=0):
  90     prune_visited_trees = True # In case we want a command line option later
  91     pack_dir = git.repo('objects/pack')
  92     ffd, bloom_filename = tempfile.mkstemp('.bloom', 'tmp-gc-', pack_dir)
  93     os.close(ffd)
  94     # FIXME: allow selection of k?
  95     # FIXME: support ephemeral bloom filters (i.e. *never* written to disk)
  96     live_objs = bloom.create(bloom_filename, expected=existing_count, k=None)
  97     # live_objs will hold on to the fd until close or exit
  98     os.unlink(bloom_filename)
  99     stop_at, trees_visited = None, None
 100     if prune_visited_trees:
 101         trees_visited = set()
 102         stop_at = lambda (x): x.decode('hex') in trees_visited
 103     approx_live_count = 0
 104     for ref_name, ref_id in git.list_refs():
 105         for item in walk_object(cat_pipe, ref_id.encode('hex'),
 106                                 stop_at=stop_at,
 107                                 include_data=None):
 108             # FIXME: batch ids
 109             if verbosity:
 110                 report_live_item(approx_live_count, existing_count,
 111                                  ref_name, ref_id, item, verbosity)
 112             if trees_visited is not None and item.type == 'tree':
 113                 trees_visited.add(item.oid)
 114             if verbosity:
 115                 if not live_objs.exists(item.oid):
 116                     live_objs.add(item.oid)
 117                     approx_live_count += 1
 118             else:
 119                 live_objs.add(item.oid)
 120     trees_visited = None
 121     if verbosity:
 122         log('expecting to retain about %.2f%% unnecessary objects\n'
 123             % live_objs.pfalse_positive())
 124     return live_objs
 125
 126
 127 def sweep(live_objects, existing_count, cat_pipe, threshold, compression,
 128           verbosity):
 129     # Traverse all the packs, saving the (probably) live data.
 130
 131     ns = Nonlocal()
 132     ns.stale_files = []
 133     def remove_stale_files(new_pack_prefix):
 134         if verbosity and new_pack_prefix:
 135             log('created ' + basename(new_pack_prefix) + '\n')
 136         for p in ns.stale_files:
 137             if new_pack_prefix and p.startswith(new_pack_prefix):
 138                 continue  # Don't remove the new pack file
 139             if verbosity:
 140                 log('removing ' + basename(p) + '\n')
 141             os.unlink(p)
 142         if ns.stale_files:  # So git cat-pipe will close them
 143             cat_pipe.restart()
 144         ns.stale_files = []
 145
 146     writer = git.PackWriter(objcache_maker=None,
 147                             compression_level=compression,
 148                             run_midx=False,
 149                             on_pack_finish=remove_stale_files)
 150
 151     # FIXME: sanity check .idx names vs .pack names?
 152     collect_count = 0
 153     for idx_name in glob.glob(os.path.join(git.repo('objects/pack'), '*.idx')):
 154         if verbosity:
 155             qprogress('preserving live data (%d%% complete)\r'
 156                       % ((float(collect_count) / existing_count) * 100))
 157         idx = git.open_idx(idx_name)
 158
 159         idx_live_count = 0
 160         for i in xrange(0, len(idx)):
 161             sha = idx.shatable[i * 20 : (i + 1) * 20]
 162             if live_objects.exists(sha):
 163                 idx_live_count += 1
 164
 165         collect_count += idx_live_count
 166         if idx_live_count == 0:
 167             if verbosity:
 168                 log('deleting %s\n'
 169                     % git.repo_rel(basename(idx_name)))
 170             ns.stale_files.append(idx_name)
 171             ns.stale_files.append(idx_name[:-3] + 'pack')
 172             continue
 173
 174         live_frac = idx_live_count / float(len(idx))
 175         if live_frac > ((100 - threshold) / 100.0):
 176             if verbosity:
 177                 log('keeping %s (%d%% live)\n' % (git.repo_rel(basename(idx_name)),
 178                                                   live_frac * 100))
 179             continue
 180
 181         if verbosity:
 182             log('rewriting %s (%.2f%% live)\n' % (basename(idx_name),
 183                                                   live_frac * 100))
 184         for i in xrange(0, len(idx)):
 185             sha = idx.shatable[i * 20 : (i + 1) * 20]
 186             if live_objects.exists(sha):
 187                 item_it = cat_pipe.get(sha.encode('hex'))
 188                 _, typ, _ = next(item_it)
 189                 writer.just_write(sha, typ, ''.join(item_it))
 190
 191         ns.stale_files.append(idx_name)
 192         ns.stale_files.append(idx_name[:-3] + 'pack')
 193
 194     if verbosity:
 195         progress('preserving live data (%d%% complete)\n'
 196                  % ((float(collect_count) / existing_count) * 100))
 197
 198     # Nothing should have recreated midx/bloom yet.
 199     pack_dir = git.repo('objects/pack')
 200     assert(not os.path.exists(os.path.join(pack_dir, 'bup.bloom')))
 201     assert(not glob.glob(os.path.join(pack_dir, '*.midx')))
 202
 203     # try/catch should call writer.abort()?
 204     # This will finally run midx.
 205     writer.close()  # Can only change refs (if needed) after this.
 206     remove_stale_files(None)  # In case we didn't write to the writer.
 207
 208     if verbosity:
 209         log('discarded %d%% of objects\n'
 210             % ((existing_count - count_objects(pack_dir, verbosity))
 211                / float(existing_count) * 100))
 212
 213
 214 def bup_gc(threshold=10, compression=1, verbosity=0):
 215     cat_pipe = git.cp()
 216     existing_count = count_objects(git.repo('objects/pack'), verbosity)
 217     if verbosity:
 218         log('found %d objects\n' % existing_count)
 219     if not existing_count:
 220         if verbosity:
 221             log('nothing to collect\n')
 222     else:
 223         try:
 224             live_objects = find_live_objects(existing_count, cat_pipe,
 225                                              verbosity=verbosity)
 226         except MissingObject as ex:
 227             log('bup: missing object %r \n' % ex.oid.encode('hex'))
 228             sys.exit(1)
 229         try:
 230             # FIXME: just rename midxes and bloom, and restore them at the end if
 231             # we didn't change any packs?
 232             packdir = git.repo('objects/pack')
 233             if verbosity: log('clearing midx files\n')
 234             midx.clear_midxes(packdir)
 235             if verbosity: log('clearing bloom filter\n')
 236             bloom.clear_bloom(packdir)
 237             if verbosity: log('clearing reflog\n')
 238             expirelog_cmd = ['git', 'reflog', 'expire', '--all', '--expire=all']
 239             expirelog = subprocess.Popen(expirelog_cmd, preexec_fn = git._gitenv())
 240             git._git_wait(' '.join(expirelog_cmd), expirelog)
 241             if verbosity: log('removing unreachable data\n')
 242             sweep(live_objects, existing_count, cat_pipe,
 243                   threshold, compression,
 244                   verbosity)
 245         finally:
 246             live_objects.close()