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 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 class Nonlocal:
  44     pass
  45
  46
  47 def count_objects(dir, verbosity):
  48     # For now we'll just use open_idx(), but we could probably be much
  49     # more efficient since all we need is a single integer (the last
  50     # fanout entry) from each index.
  51     object_count = 0
  52     indexes = glob.glob(os.path.join(dir, '*.idx'))
  53     for i, idx_name in enumerate(indexes):
  54         if verbosity:
  55             log('found %d objects (%d/%d %s)\r'
  56                 % (object_count, i + 1, len(indexes), basename(idx_name)))
  57         idx = git.open_idx(idx_name)
  58         object_count += len(idx)
  59     return object_count
  60
  61
  62 def report_live_item(n, total, ref_name, ref_id, item, verbosity):
  63     status = 'scanned %02.2f%%' % (n * 100.0 / total)
  64     hex_id = ref_id.encode('hex')
  65     dirslash = '/' if item.type == 'tree' else ''
  66     chunk_path = item.chunk_path
  67
  68     if chunk_path:
  69         if verbosity < 4:
  70             return
  71         ps = '/'.join(item.path)
  72         chunk_ps = '/'.join(chunk_path)
  73         log('%s %s:%s/%s%s\n' % (status, hex_id, ps, chunk_ps, dirslash))
  74         return
  75
  76     # Top commit, for example has none.
  77     demangled = git.demangle_name(item.path[-1], item.mode)[0] if item.path \
  78                 else None
  79
  80     # Don't print mangled paths unless the verbosity is over 3.
  81     if demangled:
  82         ps = '/'.join(item.path[:-1] + [demangled])
  83         if verbosity == 1:
  84             qprogress('%s %s:%s%s\r' % (status, hex_id, ps, dirslash))
  85         elif (verbosity > 1 and item.type == 'tree') \
  86              or (verbosity > 2 and item.type == 'blob'):
  87             log('%s %s:%s%s\n' % (status, hex_id, ps, dirslash))
  88     elif verbosity > 3:
  89         ps = '/'.join(item.path)
  90         log('%s %s:%s%s\n' % (status, hex_id, ps, dirslash))
  91
  92
  93 def find_live_objects(existing_count, cat_pipe, verbosity=0):
  94     prune_visited_trees = True # In case we want a command line option later
  95     pack_dir = git.repo('objects/pack')
  96     ffd, bloom_filename = tempfile.mkstemp('.bloom', 'tmp-gc-', pack_dir)
  97     os.close(ffd)
  98     # FIXME: allow selection of k?
  99     # FIXME: support ephemeral bloom filters (i.e. *never* written to disk)
 100     live_objs = bloom.create(bloom_filename, expected=existing_count, k=None)
 101     stop_at, trees_visited = None, None
 102     if prune_visited_trees:
 103         trees_visited = set()
 104         stop_at = lambda (x): x.decode('hex') in trees_visited
 105     approx_live_count = 0
 106     for ref_name, ref_id in git.list_refs():
 107         for item in walk_object(cat_pipe, ref_id.encode('hex'),
 108                                 stop_at=stop_at,
 109                                 include_data=None):
 110             # FIXME: batch ids
 111             if verbosity:
 112                 report_live_item(approx_live_count, existing_count,
 113                                  ref_name, ref_id, item, verbosity)
 114             bin_id = item.id.decode('hex')
 115             if trees_visited is not None and item.type == 'tree':
 116                 trees_visited.add(bin_id)
 117             if verbosity:
 118                 if not live_objs.exists(bin_id):
 119                     live_objs.add(bin_id)
 120                     approx_live_count += 1
 121             else:
 122                 live_objs.add(bin_id)
 123     trees_visited = None
 124     if verbosity:
 125         log('expecting to retain about %.2f%% unnecessary objects\n'
 126             % live_objs.pfalse_positive())
 127     return live_objs
 128
 129
 130 def sweep(live_objects, existing_count, cat_pipe, threshold, compression,
 131           verbosity):
 132     # Traverse all the packs, saving the (probably) live data.
 133
 134     ns = Nonlocal()
 135     ns.stale_files = []
 136     def remove_stale_files(new_pack_prefix):
 137         if verbosity and new_pack_prefix:
 138             log('created ' + basename(new_pack_prefix) + '\n')
 139         for p in ns.stale_files:
 140             if verbosity:
 141                 log('removing ' + basename(p) + '\n')
 142             os.unlink(p)
 143         ns.stale_files = []
 144
 145     writer = git.PackWriter(objcache_maker=None,
 146                             compression_level=compression,
 147                             run_midx=False,
 148                             on_pack_finish=remove_stale_files)
 149
 150     # FIXME: sanity check .idx names vs .pack names?
 151     collect_count = 0
 152     for idx_name in glob.glob(os.path.join(git.repo('objects/pack'), '*.idx')):
 153         if verbosity:
 154             qprogress('preserving live data (%d%% complete)\r'
 155                       % ((float(collect_count) / existing_count) * 100))
 156         idx = git.open_idx(idx_name)
 157
 158         idx_live_count = 0
 159         for i in xrange(0, len(idx)):
 160             sha = idx.shatable[i * 20 : (i + 1) * 20]
 161             if live_objects.exists(sha):
 162                 idx_live_count += 1
 163
 164         collect_count += idx_live_count
 165         if idx_live_count == 0:
 166             if verbosity:
 167                 log('deleting %s\n'
 168                     % git.repo_rel(basename(idx_name)))
 169             ns.stale_files.append(idx_name)
 170             ns.stale_files.append(idx_name[:-3] + 'pack')
 171             continue
 172
 173         live_frac = idx_live_count / float(len(idx))
 174         if live_frac > ((100 - threshold) / 100.0):
 175             if verbosity:
 176                 log('keeping %s (%d%% live)\n' % (git.repo_rel(basename(idx_name)),
 177                                                   live_frac * 100))
 178             continue
 179
 180         if verbosity:
 181             log('rewriting %s (%.2f%% live)\n' % (basename(idx_name),
 182                                                   live_frac * 100))
 183         for i in xrange(0, len(idx)):
 184             sha = idx.shatable[i * 20 : (i + 1) * 20]
 185             if live_objects.exists(sha):
 186                 item_it = cat_pipe.get(sha.encode('hex'))
 187                 type = item_it.next()
 188                 writer.write(sha, type, ''.join(item_it))
 189
 190         ns.stale_files.append(idx_name)
 191         ns.stale_files.append(idx_name[:-3] + 'pack')
 192
 193     if verbosity:
 194         progress('preserving live data (%d%% complete)\n'
 195                  % ((float(collect_count) / existing_count) * 100))
 196
 197     # Nothing should have recreated midx/bloom yet.
 198     pack_dir = git.repo('objects/pack')
 199     assert(not os.path.exists(os.path.join(pack_dir, 'bup.bloom')))
 200     assert(not glob.glob(os.path.join(pack_dir, '*.midx')))
 201
 202     # try/catch should call writer.abort()?
 203     # This will finally run midx.
 204     writer.close()  # Can only change refs (if needed) after this.
 205     remove_stale_files(None)  # In case we didn't write to the writer.
 206
 207     if verbosity:
 208         log('discarded %d%% of objects\n'
 209             % ((existing_count - count_objects(pack_dir, verbosity))
 210                / float(existing_count) * 100))
 211
 212
 213 def bup_gc(threshold=10, compression=1, verbosity=0):
 214     cat_pipe = git.cp()
 215     existing_count = count_objects(git.repo('objects/pack'), verbosity)
 216     if verbosity:
 217         log('found %d objects\n' % existing_count)
 218     if not existing_count:
 219         if verbosity:
 220             log('nothing to collect\n')
 221     else:
 222         try:
 223             live_objects = find_live_objects(existing_count, cat_pipe,
 224                                              verbosity=verbosity)
 225         except MissingObject as ex:
 226             log('bup: missing object %r \n' % ex.id.encode('hex'))
 227             sys.exit(1)
 228         try:
 229             # FIXME: just rename midxes and bloom, and restore them at the end if
 230             # we didn't change any packs?
 231             if verbosity: log('clearing midx files\n')
 232             midx.clear_midxes()
 233             if verbosity: log('clearing bloom filter\n')
 234             bloom.clear_bloom(git.repo('objects/pack'))
 235             if verbosity: log('clearing reflog\n')
 236             expirelog_cmd = ['git', 'reflog', 'expire', '--all', '--expire=all']
 237             expirelog = subprocess.Popen(expirelog_cmd, preexec_fn = git._gitenv())
 238             git._git_wait(' '.join(expirelog_cmd), expirelog)
 239             if verbosity: log('removing unreachable data\n')
 240             sweep(live_objects, existing_count, cat_pipe,
 241                   threshold, compression,
 242                   verbosity)
 243         finally:
 244             live_objects.close()
 245             os.unlink(live_objects.name)