3 bup_python="$(dirname "$0")/bup-python" || exit $?
4 exec "$bup_python" "$0" ${1+"$@"}
7 import glob, os, stat, subprocess, sys, tempfile
8 from bup import bloom, git, midx, options, vfs
9 from bup.git import MissingObject, walk_object
10 from bup.helpers import handle_ctrl_c, log, progress, qprogress, saved_errors
11 from os.path import basename
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.
19 # The collection proceeds as follows:
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".
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.
29 # - Traverse all of the pack files, consulting the liveness filter
30 # to decide which objects to keep.
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.
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.
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.
46 # FIXME: add a bloom filter tuning parameter?
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
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.
69 indexes = glob.glob(os.path.join(dir, '*.idx'))
70 for i, idx_name in enumerate(indexes):
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)
80 def report_live_item(n, total, ref_name, ref_id, item):
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
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))
95 # Top commit, for example has none.
96 demangled = git.demangle_name(item.path[-1], item.mode)[0] if item.path \
99 # Don't print mangled paths unless the verbosity is over 3.
101 ps = '/'.join(item.path[:-1] + [demangled])
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))
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)
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'),
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)
137 if not live_objs.exists(bin_id):
138 live_objs.add(bin_id)
139 approx_live_count += 1
141 live_objs.add(bin_id)
144 log('expecting to retain about %.2f%% unnecessary objects\n'
145 % live_objs.pfalse_positive())
149 def sweep(live_objects, existing_count, cat_pipe, opt):
150 # Traverse all the packs, saving the (probably) live data.
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:
159 log('removing ' + basename(p) + '\n')
163 writer = git.PackWriter(objcache_maker=None,
164 compression_level=opt.compress,
166 on_pack_finish=remove_stale_files)
168 # FIXME: sanity check .idx names vs .pack names?
170 for idx_name in glob.glob(os.path.join(git.repo('objects/pack'), '*.idx')):
172 qprogress('preserving live data (%d%% complete)\r'
173 % ((float(collect_count) / existing_count) * 100))
174 idx = git.open_idx(idx_name)
177 for i in xrange(0, len(idx)):
178 sha = idx.shatable[i * 20 : (i + 1) * 20]
179 if live_objects.exists(sha):
182 collect_count += idx_live_count
183 if idx_live_count == 0:
186 % git.repo_rel(basename(idx_name)))
187 ns.stale_files.append(idx_name)
188 ns.stale_files.append(idx_name[:-3] + 'pack')
191 live_frac = idx_live_count / float(len(idx))
192 if live_frac > ((100 - opt.threshold) / 100.0):
194 log('keeping %s (%d%% live)\n' % (git.repo_rel(basename(idx_name)),
199 log('rewriting %s (%.2f%% live)\n' % (basename(idx_name),
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))
208 ns.stale_files.append(idx_name)
209 ns.stale_files.append(idx_name[:-3] + 'pack')
212 progress('preserving live data (%d%% complete)\n'
213 % ((float(collect_count) / existing_count) * 100))
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')))
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.
226 log('discarded %d%% of objects\n'
227 % ((existing_count - count_objects(pack_dir))
228 / float(existing_count) * 100))
231 # FIXME: server mode?
232 # FIXME: make sure client handles server-side changes reasonably
236 o = options.Options(optspec)
237 (opt, flags, extra) = o.parse(sys.argv[1:])
240 o.fatal('refusing to run dangerous, experimental command without --unsafe')
243 o.fatal('no positional parameters expected')
247 opt.threshold = int(opt.threshold)
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')
253 git.check_repo_or_die()
256 existing_count = count_objects(git.repo('objects/pack'))
258 log('found %d objects\n' % existing_count)
259 if not existing_count:
261 log('nothing to collect\n')
264 live_objects = find_live_objects(existing_count, cat_pipe, opt)
265 except MissingObject as ex:
266 log('bup: missing object %r \n' % ex.id.encode('hex'))
269 # FIXME: just rename midxes and bloom, and restore them at the end if
270 # we didn't change any packs?
271 if opt.verbose: log('clearing midx files\n')
273 if opt.verbose: log('clearing bloom filter\n')
274 bloom.clear_bloom(git.repo('objects/pack'))
275 if opt.verbose: log('clearing reflog\n')
276 expirelog_cmd = ['git', 'reflog', 'expire', '--all', '--expire=all']
277 expirelog = subprocess.Popen(expirelog_cmd, preexec_fn = git._gitenv())
278 git._git_wait(' '.join(expirelog_cmd), expirelog)
279 if opt.verbose: log('removing unreachable data\n')
280 sweep(live_objects, existing_count, cat_pipe, opt)
283 os.unlink(live_objects.name)
286 log('WARNING: %d errors encountered during gc\n' % len(saved_errors))