cmd/gc-cmd.py

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