1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.dfs;
12
13 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.COMPACT;
14 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.GC;
15 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.GC_REST;
16 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.GC_TXN;
17 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.INSERT;
18 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.RECEIVE;
19 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.UNREACHABLE_GARBAGE;
20 import static org.eclipse.jgit.internal.storage.dfs.DfsPackCompactor.configureReftable;
21 import static org.eclipse.jgit.internal.storage.pack.PackExt.BITMAP_INDEX;
22 import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX;
23 import static org.eclipse.jgit.internal.storage.pack.PackExt.PACK;
24 import static org.eclipse.jgit.internal.storage.pack.PackExt.REFTABLE;
25 import static org.eclipse.jgit.internal.storage.pack.PackWriter.NONE;
26
27 import java.io.IOException;
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Calendar;
31 import java.util.Collection;
32 import java.util.EnumSet;
33 import java.util.GregorianCalendar;
34 import java.util.HashSet;
35 import java.util.List;
36 import java.util.Set;
37 import java.util.concurrent.TimeUnit;
38
39 import org.eclipse.jgit.internal.JGitText;
40 import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource;
41 import org.eclipse.jgit.internal.storage.file.PackIndex;
42 import org.eclipse.jgit.internal.storage.file.PackReverseIndex;
43 import org.eclipse.jgit.internal.storage.pack.PackExt;
44 import org.eclipse.jgit.internal.storage.pack.PackWriter;
45 import org.eclipse.jgit.internal.storage.reftable.ReftableCompactor;
46 import org.eclipse.jgit.internal.storage.reftable.ReftableConfig;
47 import org.eclipse.jgit.internal.storage.reftable.ReftableWriter;
48 import org.eclipse.jgit.internal.storage.reftree.RefTreeNames;
49 import org.eclipse.jgit.lib.AnyObjectId;
50 import org.eclipse.jgit.lib.Constants;
51 import org.eclipse.jgit.lib.NullProgressMonitor;
52 import org.eclipse.jgit.lib.ObjectId;
53 import org.eclipse.jgit.lib.ObjectIdSet;
54 import org.eclipse.jgit.lib.ProgressMonitor;
55 import org.eclipse.jgit.lib.Ref;
56 import org.eclipse.jgit.lib.RefDatabase;
57 import org.eclipse.jgit.revwalk.RevWalk;
58 import org.eclipse.jgit.storage.pack.PackConfig;
59 import org.eclipse.jgit.storage.pack.PackStatistics;
60 import org.eclipse.jgit.util.SystemReader;
61 import org.eclipse.jgit.util.io.CountingOutputStream;
62
63
64
65
66 public class DfsGarbageCollector {
67 private final DfsRepository repo;
68 private final RefDatabase refdb;
69 private final DfsObjDatabase objdb;
70
71 private final List<DfsPackDescription> newPackDesc;
72 private final List<PackStatistics> newPackStats;
73 private final List<ObjectIdSet> newPackObj;
74
75 private DfsReader ctx;
76
77 private PackConfig packConfig;
78 private ReftableConfig reftableConfig;
79 private boolean convertToReftable = true;
80 private boolean includeDeletes;
81 private long reftableInitialMinUpdateIndex = 1;
82 private long reftableInitialMaxUpdateIndex = 1;
83
84
85
86 private long coalesceGarbageLimit = 50 << 20;
87 private long garbageTtlMillis = TimeUnit.DAYS.toMillis(1);
88
89 private long startTimeMillis;
90 private List<DfsPackFile> packsBefore;
91 private List<DfsReftable> reftablesBefore;
92 private List<DfsPackFile> expiredGarbagePacks;
93
94 private Collection<Ref> refsBefore;
95 private Set<ObjectId> allHeadsAndTags;
96 private Set<ObjectId> allTags;
97 private Set<ObjectId> nonHeads;
98 private Set<ObjectId> txnHeads;
99 private Set<ObjectId> tagTargets;
100
101
102
103
104
105
106
107 public DfsGarbageCollector(DfsRepository repository) {
108 repo = repository;
109 refdb = repo.getRefDatabase();
110 objdb = repo.getObjectDatabase();
111 newPackDesc = new ArrayList<>(4);
112 newPackStats = new ArrayList<>(4);
113 newPackObj = new ArrayList<>(4);
114
115 packConfig = new PackConfig(repo);
116 packConfig.setIndexVersion(2);
117 }
118
119
120
121
122
123
124 public PackConfig getPackConfig() {
125 return packConfig;
126 }
127
128
129
130
131
132
133
134
135 public DfsGarbageCollector setPackConfig(PackConfig newConfig) {
136 packConfig = newConfig;
137 return this;
138 }
139
140
141
142
143
144
145
146
147
148 public DfsGarbageCollector setReftableConfig(ReftableConfig cfg) {
149 reftableConfig = cfg;
150 return this;
151 }
152
153
154
155
156
157
158
159
160
161
162
163
164 public DfsGarbageCollector setConvertToReftable(boolean convert) {
165 convertToReftable = convert;
166 return this;
167 }
168
169
170
171
172
173
174
175
176
177
178
179 public DfsGarbageCollector setIncludeDeletes(boolean include) {
180 includeDeletes = include;
181 return this;
182 }
183
184
185
186
187
188
189
190
191
192
193
194
195 public DfsGarbageCollector setReftableInitialMinUpdateIndex(long u) {
196 reftableInitialMinUpdateIndex = Math.max(u, 0);
197 return this;
198 }
199
200
201
202
203
204
205
206
207
208
209
210
211 public DfsGarbageCollector setReftableInitialMaxUpdateIndex(long u) {
212 reftableInitialMaxUpdateIndex = Math.max(0, u);
213 return this;
214 }
215
216
217
218
219
220
221
222 public long getCoalesceGarbageLimit() {
223 return coalesceGarbageLimit;
224 }
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249 public DfsGarbageCollector setCoalesceGarbageLimit(long limit) {
250 coalesceGarbageLimit = limit;
251 return this;
252 }
253
254
255
256
257
258
259
260
261 public long getGarbageTtlMillis() {
262 return garbageTtlMillis;
263 }
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279 public DfsGarbageCollector setGarbageTtl(long ttl, TimeUnit unit) {
280 garbageTtlMillis = unit.toMillis(ttl);
281 return this;
282 }
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300 public boolean pack(ProgressMonitor pm) throws IOException {
301 if (pm == null)
302 pm = NullProgressMonitor.INSTANCE;
303 if (packConfig.getIndexVersion() != 2)
304 throw new IllegalStateException(
305 JGitText.get().supportOnlyPackIndexVersion2);
306
307 startTimeMillis = SystemReader.getInstance().getCurrentTime();
308 ctx = objdb.newReader();
309 try {
310 refdb.refresh();
311 objdb.clearCache();
312
313 refsBefore = getAllRefs();
314 readPacksBefore();
315 readReftablesBefore();
316
317 Set<ObjectId> allHeads = new HashSet<>();
318 allHeadsAndTags = new HashSet<>();
319 allTags = new HashSet<>();
320 nonHeads = new HashSet<>();
321 txnHeads = new HashSet<>();
322 tagTargets = new HashSet<>();
323 for (Ref ref : refsBefore) {
324 if (ref.isSymbolic() || ref.getObjectId() == null) {
325 continue;
326 }
327 if (isHead(ref)) {
328 allHeads.add(ref.getObjectId());
329 } else if (isTag(ref)) {
330 allTags.add(ref.getObjectId());
331 } else if (RefTreeNames.isRefTree(refdb, ref.getName())) {
332 txnHeads.add(ref.getObjectId());
333 } else {
334 nonHeads.add(ref.getObjectId());
335 }
336 if (ref.getPeeledObjectId() != null) {
337 tagTargets.add(ref.getPeeledObjectId());
338 }
339 }
340
341 allTags.removeAll(allHeads);
342 allHeadsAndTags.addAll(allHeads);
343 allHeadsAndTags.addAll(allTags);
344
345
346 tagTargets.addAll(allHeadsAndTags);
347
348
349 if (packConfig.getSinglePack()) {
350 allHeadsAndTags.addAll(nonHeads);
351 nonHeads.clear();
352 }
353
354 boolean rollback = true;
355 try {
356 packHeads(pm);
357 packRest(pm);
358 packRefTreeGraph(pm);
359 packGarbage(pm);
360 objdb.commitPack(newPackDesc, toPrune());
361 rollback = false;
362 return true;
363 } finally {
364 if (rollback)
365 objdb.rollbackPack(newPackDesc);
366 }
367 } finally {
368 ctx.close();
369 }
370 }
371
372 private Collection<Ref> getAllRefs() throws IOException {
373 Collection<Ref> refs = refdb.getRefs();
374 List<Ref> addl = refdb.getAdditionalRefs();
375 if (!addl.isEmpty()) {
376 List<Ref> all = new ArrayList<>(refs.size() + addl.size());
377 all.addAll(refs);
378
379 for (Ref r : addl) {
380 if (r.getName().startsWith(Constants.R_REFS)) {
381 all.add(r);
382 }
383 }
384 return all;
385 }
386 return refs;
387 }
388
389 private void readPacksBefore() throws IOException {
390 DfsPackFile[] packs = objdb.getPacks();
391 packsBefore = new ArrayList<>(packs.length);
392 expiredGarbagePacks = new ArrayList<>(packs.length);
393
394 long now = SystemReader.getInstance().getCurrentTime();
395 for (DfsPackFile p : packs) {
396 DfsPackDescription d = p.getPackDescription();
397 if (d.getPackSource() != UNREACHABLE_GARBAGE) {
398 packsBefore.add(p);
399 } else if (packIsExpiredGarbage(d, now)) {
400 expiredGarbagePacks.add(p);
401 } else if (packIsCoalesceableGarbage(d, now)) {
402 packsBefore.add(p);
403 }
404 }
405 }
406
407 private void readReftablesBefore() throws IOException {
408 DfsReftable[] tables = objdb.getReftables();
409 reftablesBefore = new ArrayList<>(Arrays.asList(tables));
410 }
411
412 private boolean packIsExpiredGarbage(DfsPackDescription d, long now) {
413
414
415
416
417
418 return d.getPackSource() == UNREACHABLE_GARBAGE
419 && garbageTtlMillis > 0
420 && now - d.getLastModified() >= garbageTtlMillis;
421 }
422
423 private boolean packIsCoalesceableGarbage(DfsPackDescription d, long now) {
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443 if (d.getPackSource() != UNREACHABLE_GARBAGE
444 || d.getFileSize(PackExt.PACK) >= coalesceGarbageLimit) {
445 return false;
446 }
447
448 if (garbageTtlMillis == 0) {
449 return true;
450 }
451
452 long lastModified = d.getLastModified();
453 long dayStartLastModified = dayStartInMillis(lastModified);
454 long dayStartToday = dayStartInMillis(now);
455
456 if (dayStartLastModified != dayStartToday) {
457 return false;
458 }
459
460 if (garbageTtlMillis > TimeUnit.DAYS.toMillis(1)) {
461 return true;
462 }
463
464 long timeInterval = garbageTtlMillis / 3;
465 if (timeInterval == 0) {
466 return false;
467 }
468
469 long modifiedTimeSlot = (lastModified - dayStartLastModified) / timeInterval;
470 long presentTimeSlot = (now - dayStartToday) / timeInterval;
471 return modifiedTimeSlot == presentTimeSlot;
472 }
473
474 private static long dayStartInMillis(long timeInMillis) {
475 Calendar cal = new GregorianCalendar(
476 SystemReader.getInstance().getTimeZone());
477 cal.setTimeInMillis(timeInMillis);
478 cal.set(Calendar.HOUR_OF_DAY, 0);
479 cal.set(Calendar.MINUTE, 0);
480 cal.set(Calendar.SECOND, 0);
481 cal.set(Calendar.MILLISECOND, 0);
482 return cal.getTimeInMillis();
483 }
484
485
486
487
488
489
490 public Set<DfsPackDescription> getSourcePacks() {
491 return toPrune();
492 }
493
494
495
496
497
498
499 public List<DfsPackDescription> getNewPacks() {
500 return newPackDesc;
501 }
502
503
504
505
506
507
508
509
510 public List<PackStatistics> getNewPackStatistics() {
511 return newPackStats;
512 }
513
514 private Set<DfsPackDescription> toPrune() {
515 Set<DfsPackDescription> toPrune = new HashSet<>();
516 for (DfsPackFile pack : packsBefore) {
517 toPrune.add(pack.getPackDescription());
518 }
519 if (reftableConfig != null) {
520 for (DfsReftable table : reftablesBefore) {
521 toPrune.add(table.getPackDescription());
522 }
523 }
524 for (DfsPackFile pack : expiredGarbagePacks) {
525 toPrune.add(pack.getPackDescription());
526 }
527 return toPrune;
528 }
529
530 private void packHeads(ProgressMonitor pm) throws IOException {
531 if (allHeadsAndTags.isEmpty()) {
532 writeReftable();
533 return;
534 }
535
536 try (PackWriter pw = newPackWriter()) {
537 pw.setTagTargets(tagTargets);
538 pw.preparePack(pm, allHeadsAndTags, NONE, NONE, allTags);
539 if (0 < pw.getObjectCount()) {
540 long estSize = estimateGcPackSize(INSERT, RECEIVE, COMPACT, GC);
541 writePack(GC, pw, pm, estSize);
542 } else {
543 writeReftable();
544 }
545 }
546 }
547
548 private void packRest(ProgressMonitor pm) throws IOException {
549 if (nonHeads.isEmpty())
550 return;
551
552 try (PackWriter pw = newPackWriter()) {
553 for (ObjectIdSet packedObjs : newPackObj)
554 pw.excludeObjects(packedObjs);
555 pw.preparePack(pm, nonHeads, allHeadsAndTags);
556 if (0 < pw.getObjectCount())
557 writePack(GC_REST, pw, pm,
558 estimateGcPackSize(INSERT, RECEIVE, COMPACT, GC_REST));
559 }
560 }
561
562 private void packRefTreeGraph(ProgressMonitor pm) throws IOException {
563 if (txnHeads.isEmpty())
564 return;
565
566 try (PackWriter pw = newPackWriter()) {
567 for (ObjectIdSet packedObjs : newPackObj)
568 pw.excludeObjects(packedObjs);
569 pw.preparePack(pm, txnHeads, NONE);
570 if (0 < pw.getObjectCount())
571 writePack(GC_TXN, pw, pm, 0 );
572 }
573 }
574
575 private void packGarbage(ProgressMonitor pm) throws IOException {
576 PackConfig cfg = new PackConfig(packConfig);
577 cfg.setReuseDeltas(true);
578 cfg.setReuseObjects(true);
579 cfg.setDeltaCompress(false);
580 cfg.setBuildBitmaps(false);
581
582 try (PackWriternal/storage/pack/PackWriter.html#PackWriter">PackWriter pw = new PackWriter(cfg, ctx);
583 RevWalk pool = new RevWalk(ctx)) {
584 pw.setDeltaBaseAsOffset(true);
585 pw.setReuseDeltaCommits(true);
586 pm.beginTask(JGitText.get().findingGarbage, objectsBefore());
587 long estimatedPackSize = 12 + 20;
588 for (DfsPackFile oldPack : packsBefore) {
589 PackIndex oldIdx = oldPack.getPackIndex(ctx);
590 PackReverseIndex oldRevIdx = oldPack.getReverseIdx(ctx);
591 long maxOffset = oldPack.getPackDescription().getFileSize(PACK)
592 - 20;
593 for (PackIndex.MutableEntry ent : oldIdx) {
594 pm.update(1);
595 ObjectId id = ent.toObjectId();
596 if (pool.lookupOrNull(id) != null || anyPackHas(id))
597 continue;
598
599 long offset = ent.getOffset();
600 int type = oldPack.getObjectType(ctx, offset);
601 pw.addObject(pool.lookupAny(id, type));
602 long objSize = oldRevIdx.findNextOffset(offset, maxOffset)
603 - offset;
604 estimatedPackSize += objSize;
605 }
606 }
607 pm.endTask();
608 if (0 < pw.getObjectCount())
609 writePack(UNREACHABLE_GARBAGE, pw, pm, estimatedPackSize);
610 }
611 }
612
613 private boolean anyPackHas(AnyObjectId id) {
614 for (ObjectIdSet packedObjs : newPackObj)
615 if (packedObjs.contains(id))
616 return true;
617 return false;
618 }
619
620 private static boolean isHead(Ref ref) {
621 return ref.getName().startsWith(Constants.R_HEADS);
622 }
623
624 private static boolean isTag(Ref ref) {
625 return ref.getName().startsWith(Constants.R_TAGS);
626 }
627
628 private int objectsBefore() {
629 int cnt = 0;
630 for (DfsPackFile p : packsBefore)
631 cnt += (int) p.getPackDescription().getObjectCount();
632 return cnt;
633 }
634
635 private PackWriter newPackWriter() {
636 PackWriter pw = new PackWriter(packConfig, ctx);
637 pw.setDeltaBaseAsOffset(true);
638 pw.setReuseDeltaCommits(false);
639 return pw;
640 }
641
642 private long estimateGcPackSize(PackSource first, PackSource... rest) {
643 EnumSet<PackSource> sourceSet = EnumSet.of(first, rest);
644
645
646
647 long size = 32;
648 for (DfsPackDescription pack : getSourcePacks()) {
649 if (sourceSet.contains(pack.getPackSource())) {
650 size += pack.getFileSize(PACK) - 32;
651 }
652 }
653 return size;
654 }
655
656 private DfsPackDescription writePack(PackSource source, PackWriter pw,
657 ProgressMonitor pm, long estimatedPackSize) throws IOException {
658 DfsPackDescription pack = repo.getObjectDatabase().newPack(source,
659 estimatedPackSize);
660
661 if (source == GC && reftableConfig != null) {
662 writeReftable(pack);
663 }
664
665 try (DfsOutputStream out = objdb.writeFile(pack, PACK)) {
666 pw.writePack(pm, pm, out);
667 pack.addFileExt(PACK);
668 pack.setBlockSize(PACK, out.blockSize());
669 }
670
671 try (DfsOutputStream out = objdb.writeFile(pack, INDEX)) {
672 CountingOutputStream cnt = new CountingOutputStream(out);
673 pw.writeIndex(cnt);
674 pack.addFileExt(INDEX);
675 pack.setFileSize(INDEX, cnt.getCount());
676 pack.setBlockSize(INDEX, out.blockSize());
677 pack.setIndexVersion(pw.getIndexVersion());
678 }
679
680 if (pw.prepareBitmapIndex(pm)) {
681 try (DfsOutputStream out = objdb.writeFile(pack, BITMAP_INDEX)) {
682 CountingOutputStream cnt = new CountingOutputStream(out);
683 pw.writeBitmapIndex(cnt);
684 pack.addFileExt(BITMAP_INDEX);
685 pack.setFileSize(BITMAP_INDEX, cnt.getCount());
686 pack.setBlockSize(BITMAP_INDEX, out.blockSize());
687 }
688 }
689
690 PackStatistics stats = pw.getStatistics();
691 pack.setPackStats(stats);
692 pack.setLastModified(startTimeMillis);
693 newPackDesc.add(pack);
694 newPackStats.add(stats);
695 newPackObj.add(pw.getObjectSet());
696 return pack;
697 }
698
699 private void writeReftable() throws IOException {
700 if (reftableConfig != null) {
701 DfsPackDescription pack = objdb.newPack(GC);
702 newPackDesc.add(pack);
703 newPackStats.add(null);
704 writeReftable(pack);
705 }
706 }
707
708 private void writeReftable(DfsPackDescription pack) throws IOException {
709 if (convertToReftable && !hasGcReftable()) {
710 writeReftable(pack, refsBefore);
711 return;
712 }
713
714 try (DfsReftableStack stack = DfsReftableStack.open(ctx, reftablesBefore);
715 DfsOutputStream out = objdb.writeFile(pack, REFTABLE)) {
716 ReftableCompactor compact = new ReftableCompactor(out);
717 compact.addAll(stack.readers());
718 compact.setIncludeDeletes(includeDeletes);
719 compact.setConfig(configureReftable(reftableConfig, out));
720 compact.compact();
721 pack.addFileExt(REFTABLE);
722 pack.setReftableStats(compact.getStats());
723 }
724 }
725
726 private boolean hasGcReftable() {
727 for (DfsReftable table : reftablesBefore) {
728 if (table.getPackDescription().getPackSource() == GC) {
729 return true;
730 }
731 }
732 return false;
733 }
734
735 private void writeReftable(DfsPackDescription pack, Collection<Ref> refs)
736 throws IOException {
737 try (DfsOutputStream out = objdb.writeFile(pack, REFTABLE)) {
738 ReftableConfig cfg = configureReftable(reftableConfig, out);
739 ReftableWriter writer = new ReftableWriter(cfg, out)
740 .setMinUpdateIndex(reftableInitialMinUpdateIndex)
741 .setMaxUpdateIndex(reftableInitialMaxUpdateIndex).begin()
742 .sortAndWriteRefs(refs).finish();
743 pack.addFileExt(REFTABLE);
744 pack.setReftableStats(writer.getStats());
745 }
746 }
747 }