| /* |
| * Copyright (C) 2012, Google Inc. |
| * and other copyright owners as documented in the project's IP log. |
| * |
| * This program and the accompanying materials are made available |
| * under the terms of the Eclipse Distribution License v1.0 which |
| * accompanies this distribution, is reproduced below, and is |
| * available at http://www.eclipse.org/org/documents/edl-v10.php |
| * |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or |
| * without modification, are permitted provided that the following |
| * conditions are met: |
| * |
| * - Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * - Redistributions in binary form must reproduce the above |
| * copyright notice, this list of conditions and the following |
| * disclaimer in the documentation and/or other materials provided |
| * with the distribution. |
| * |
| * - Neither the name of the Eclipse Foundation, Inc. nor the |
| * names of its contributors may be used to endorse or promote |
| * products derived from this software without specific prior |
| * written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND |
| * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, |
| * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER |
| * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF |
| * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| package org.eclipse.jgit.internal.storage.pack; |
| |
| import static org.eclipse.jgit.internal.storage.file.PackBitmapIndex.FLAG_REUSE; |
| import static org.eclipse.jgit.revwalk.RevFlag.SEEN; |
| |
| import java.io.IOException; |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Set; |
| |
| import org.eclipse.jgit.errors.IncorrectObjectTypeException; |
| import org.eclipse.jgit.errors.MissingObjectException; |
| import org.eclipse.jgit.internal.JGitText; |
| import org.eclipse.jgit.internal.revwalk.AddUnseenToBitmapFilter; |
| import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl; |
| import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl.CompressedBitmap; |
| import org.eclipse.jgit.internal.storage.file.PackBitmapIndex; |
| import org.eclipse.jgit.internal.storage.file.PackBitmapIndexBuilder; |
| import org.eclipse.jgit.internal.storage.file.PackBitmapIndexRemapper; |
| import org.eclipse.jgit.lib.AnyObjectId; |
| import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; |
| import org.eclipse.jgit.lib.Constants; |
| import org.eclipse.jgit.lib.ObjectId; |
| import org.eclipse.jgit.lib.ObjectReader; |
| import org.eclipse.jgit.lib.ProgressMonitor; |
| import org.eclipse.jgit.revwalk.BitmapWalker; |
| import org.eclipse.jgit.revwalk.ObjectWalk; |
| import org.eclipse.jgit.revwalk.RevCommit; |
| import org.eclipse.jgit.revwalk.RevObject; |
| import org.eclipse.jgit.revwalk.RevWalk; |
| import org.eclipse.jgit.revwalk.filter.RevFilter; |
| import org.eclipse.jgit.storage.pack.PackConfig; |
| import org.eclipse.jgit.util.BlockList; |
| import org.eclipse.jgit.util.SystemReader; |
| |
| import com.googlecode.javaewah.EWAHCompressedBitmap; |
| |
| /** |
| * Helper class for the {@link PackWriter} to select commits for which to build |
| * pack index bitmaps. |
| */ |
| class PackWriterBitmapPreparer { |
| |
| private static final int DAY_IN_SECONDS = 24 * 60 * 60; |
| |
| private static final Comparator<RevCommit> ORDER_BY_REVERSE_TIMESTAMP = new Comparator<RevCommit>() { |
| @Override |
| public int compare(RevCommit a, RevCommit b) { |
| return Integer.signum(b.getCommitTime() - a.getCommitTime()); |
| } |
| }; |
| |
| private final ObjectReader reader; |
| private final ProgressMonitor pm; |
| private final Set<? extends ObjectId> want; |
| private final PackBitmapIndexBuilder writeBitmaps; |
| private final BitmapIndexImpl commitBitmapIndex; |
| private final PackBitmapIndexRemapper bitmapRemapper; |
| private final BitmapIndexImpl bitmapIndex; |
| |
| private final int contiguousCommitCount; |
| private final int recentCommitCount; |
| private final int recentCommitSpan; |
| private final int distantCommitSpan; |
| private final int excessiveBranchCount; |
| private final long inactiveBranchTimestamp; |
| |
| PackWriterBitmapPreparer(ObjectReader reader, |
| PackBitmapIndexBuilder writeBitmaps, ProgressMonitor pm, |
| Set<? extends ObjectId> want, PackConfig config) |
| throws IOException { |
| this.reader = reader; |
| this.writeBitmaps = writeBitmaps; |
| this.pm = pm; |
| this.want = want; |
| this.commitBitmapIndex = new BitmapIndexImpl(writeBitmaps); |
| this.bitmapRemapper = PackBitmapIndexRemapper.newPackBitmapIndex( |
| reader.getBitmapIndex(), writeBitmaps); |
| this.bitmapIndex = new BitmapIndexImpl(bitmapRemapper); |
| this.contiguousCommitCount = config.getBitmapContiguousCommitCount(); |
| this.recentCommitCount = config.getBitmapRecentCommitCount(); |
| this.recentCommitSpan = config.getBitmapRecentCommitSpan(); |
| this.distantCommitSpan = config.getBitmapDistantCommitSpan(); |
| this.excessiveBranchCount = config.getBitmapExcessiveBranchCount(); |
| long now = SystemReader.getInstance().getCurrentTime(); |
| long ageInSeconds = config.getBitmapInactiveBranchAgeInDays() |
| * DAY_IN_SECONDS; |
| this.inactiveBranchTimestamp = (now / 1000) - ageInSeconds; |
| } |
| |
| /** |
| * Returns the commit objects for which bitmap indices should be built. |
| * |
| * @param expectedCommitCount |
| * count of commits in the pack |
| * @param excludeFromBitmapSelection |
| * commits that should be excluded from bitmap selection |
| * @return commit objects for which bitmap indices should be built |
| * @throws IncorrectObjectTypeException |
| * if any of the processed objects is not a commit |
| * @throws IOException |
| * on errors reading pack or index files |
| * @throws MissingObjectException |
| * if an expected object is missing |
| */ |
| Collection<BitmapCommit> selectCommits(int expectedCommitCount, |
| Set<? extends ObjectId> excludeFromBitmapSelection) |
| throws IncorrectObjectTypeException, IOException, |
| MissingObjectException { |
| /* |
| * Thinking of bitmap indices as a cache, if we find bitmaps at or at a |
| * close ancestor to 'old' and 'new' when calculating old..new, then all |
| * objects can be calculated with minimal graph walking. A distribution |
| * that favors creating bitmaps for the most recent commits maximizes |
| * the cache hits for clients that are close to HEAD, which is the |
| * majority of calculations performed. |
| */ |
| try (RevWalk rw = new RevWalk(reader); |
| RevWalk rw2 = new RevWalk(reader)) { |
| pm.beginTask(JGitText.get().selectingCommits, |
| ProgressMonitor.UNKNOWN); |
| rw.setRetainBody(false); |
| CommitSelectionHelper selectionHelper = captureOldAndNewCommits(rw, |
| expectedCommitCount, excludeFromBitmapSelection); |
| pm.endTask(); |
| |
| // Add reused bitmaps from the previous GC pack's bitmap indices. |
| // Currently they are always fully reused, even if their spans don't |
| // match this run's PackConfig values. |
| int newCommits = selectionHelper.getCommitCount(); |
| BlockList<BitmapCommit> selections = new BlockList<>( |
| selectionHelper.reusedCommits.size() |
| + newCommits / recentCommitSpan + 1); |
| for (BitmapCommit reuse : selectionHelper.reusedCommits) { |
| selections.add(reuse); |
| } |
| |
| if (newCommits == 0) { |
| for (AnyObjectId id : selectionHelper.newWants) { |
| selections.add(new BitmapCommit(id, false, 0)); |
| } |
| return selections; |
| } |
| |
| pm.beginTask(JGitText.get().selectingCommits, newCommits); |
| int totalWants = want.size(); |
| BitmapBuilder seen = commitBitmapIndex.newBitmapBuilder(); |
| seen.or(selectionHelper.reusedCommitsBitmap); |
| rw2.setRetainBody(false); |
| rw2.setRevFilter(new NotInBitmapFilter(seen)); |
| |
| // For each branch, do a revwalk to enumerate its commits. Exclude |
| // both reused commits and any commits seen in a previous branch. |
| // Then iterate through all new commits from oldest to newest, |
| // selecting well-spaced commits in this branch. |
| for (RevCommit rc : selectionHelper.newWantsByNewest) { |
| BitmapBuilder tipBitmap = commitBitmapIndex.newBitmapBuilder(); |
| rw2.markStart((RevCommit) rw2.peel(rw2.parseAny(rc))); |
| RevCommit rc2; |
| while ((rc2 = rw2.next()) != null) { |
| tipBitmap.addObject(rc2, Constants.OBJ_COMMIT); |
| } |
| int cardinality = tipBitmap.cardinality(); |
| seen.or(tipBitmap); |
| |
| // Within this branch, keep ordered lists of commits |
| // representing chains in its history, where each chain is a |
| // "sub-branch". Ordering commits by these chains makes for |
| // fewer differences between consecutive selected commits, which |
| // in turn provides better compression/on the run-length |
| // encoding of the XORs between them. |
| List<List<BitmapCommit>> chains = new ArrayList<>(); |
| |
| // Mark the current branch as inactive if its tip commit isn't |
| // recent and there are an excessive number of branches, to |
| // prevent memory bloat of computing too many bitmaps for stale |
| // branches. |
| boolean isActiveBranch = true; |
| if (totalWants > excessiveBranchCount && !isRecentCommit(rc)) { |
| isActiveBranch = false; |
| } |
| |
| // Insert bitmaps at the offsets suggested by the |
| // nextSelectionDistance() heuristic. Only reuse bitmaps created |
| // for more distant commits. |
| int index = -1; |
| int nextIn = nextSpan(cardinality); |
| int nextFlg = nextIn == distantCommitSpan |
| ? PackBitmapIndex.FLAG_REUSE |
| : 0; |
| |
| // For the current branch, iterate through all commits from |
| // oldest to newest. |
| for (RevCommit c : selectionHelper) { |
| // Optimization: if we have found all the commits for this |
| // branch, stop searching |
| int distanceFromTip = cardinality - index - 1; |
| if (distanceFromTip == 0) { |
| break; |
| } |
| |
| // Ignore commits that are not in this branch |
| if (!tipBitmap.contains(c)) { |
| continue; |
| } |
| |
| index++; |
| nextIn--; |
| pm.update(1); |
| |
| // Always pick the items in wants, prefer merge commits. |
| if (selectionHelper.newWants.remove(c)) { |
| if (nextIn > 0) { |
| nextFlg = 0; |
| } |
| } else { |
| boolean stillInSpan = nextIn >= 0; |
| boolean isMergeCommit = c.getParentCount() > 1; |
| // Force selection if: |
| // a) we have exhausted the window looking for merges |
| // b) we are in the top commits of an active branch |
| // c) we are at a branch tip |
| boolean mustPick = (nextIn <= -recentCommitSpan) |
| || (isActiveBranch |
| && (distanceFromTip <= contiguousCommitCount)) |
| || (distanceFromTip == 1); // most recent commit |
| if (!mustPick && (stillInSpan || !isMergeCommit)) { |
| continue; |
| } |
| } |
| |
| // This commit is selected. |
| // Calculate where to look for the next one. |
| int flags = nextFlg; |
| nextIn = nextSpan(distanceFromTip); |
| nextFlg = nextIn == distantCommitSpan |
| ? PackBitmapIndex.FLAG_REUSE |
| : 0; |
| |
| // Create the commit bitmap for the current commit |
| BitmapBuilder bitmap = commitBitmapIndex.newBitmapBuilder(); |
| rw.reset(); |
| rw.markStart(c); |
| rw.setRevFilter(new AddUnseenToBitmapFilter( |
| selectionHelper.reusedCommitsBitmap, bitmap)); |
| while (rw.next() != null) { |
| // The filter adds the reachable commits to bitmap. |
| } |
| |
| // Sort the commits by independent chains in this branch's |
| // history, yielding better compression when building |
| // bitmaps. |
| List<BitmapCommit> longestAncestorChain = null; |
| for (List<BitmapCommit> chain : chains) { |
| BitmapCommit mostRecentCommit = chain |
| .get(chain.size() - 1); |
| if (bitmap.contains(mostRecentCommit)) { |
| if (longestAncestorChain == null |
| || longestAncestorChain.size() < chain |
| .size()) { |
| longestAncestorChain = chain; |
| } |
| } |
| } |
| |
| if (longestAncestorChain == null) { |
| longestAncestorChain = new ArrayList<>(); |
| chains.add(longestAncestorChain); |
| } |
| longestAncestorChain.add(new BitmapCommit(c, |
| !longestAncestorChain.isEmpty(), flags)); |
| writeBitmaps.addBitmap(c, bitmap, 0); |
| } |
| |
| for (List<BitmapCommit> chain : chains) { |
| selections.addAll(chain); |
| } |
| } |
| writeBitmaps.clearBitmaps(); // Remove the temporary commit bitmaps. |
| |
| // Add the remaining peeledWant |
| for (AnyObjectId remainingWant : selectionHelper.newWants) { |
| selections.add(new BitmapCommit(remainingWant, false, 0)); |
| } |
| |
| pm.endTask(); |
| return selections; |
| } |
| } |
| |
| private boolean isRecentCommit(RevCommit revCommit) { |
| return revCommit.getCommitTime() > inactiveBranchTimestamp; |
| } |
| |
| /** |
| * A RevFilter that excludes the commits named in a bitmap from the walk. |
| * <p> |
| * If a commit is in {@code bitmap} then that commit is not emitted by the |
| * walk and its parents are marked as SEEN so the walk can skip them. The |
| * bitmaps passed in have the property that the parents of any commit in |
| * {@code bitmap} are also in {@code bitmap}, so marking the parents as |
| * SEEN speeds up the RevWalk by saving it from walking down blind alleys |
| * and does not change the commits emitted. |
| */ |
| private static class NotInBitmapFilter extends RevFilter { |
| private final BitmapBuilder bitmap; |
| |
| NotInBitmapFilter(BitmapBuilder bitmap) { |
| this.bitmap = bitmap; |
| } |
| |
| @Override |
| public final boolean include(RevWalk rw, RevCommit c) { |
| if (!bitmap.contains(c)) { |
| return true; |
| } |
| for (RevCommit p : c.getParents()) { |
| p.add(SEEN); |
| } |
| return false; |
| } |
| |
| @Override |
| public final NotInBitmapFilter clone() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| @Override |
| public final boolean requiresCommitBody() { |
| return false; |
| } |
| } |
| |
| /** |
| * Records which of the {@code wants} can be found in the previous GC pack's |
| * bitmap indices and which are new. |
| * |
| * @param rw |
| * a {@link RevWalk} to find reachable objects in this repository |
| * @param expectedCommitCount |
| * expected count of commits. The actual count may be less due to |
| * unreachable garbage. |
| * @param excludeFromBitmapSelection |
| * commits that should be excluded from bitmap selection |
| * @return a {@link CommitSelectionHelper} capturing which commits are |
| * covered by a previous pack's bitmaps and which new commits need |
| * bitmap coverage |
| * @throws IncorrectObjectTypeException |
| * if any of the processed objects is not a commit |
| * @throws IOException |
| * on errors reading pack or index files |
| * @throws MissingObjectException |
| * if an expected object is missing |
| */ |
| private CommitSelectionHelper captureOldAndNewCommits(RevWalk rw, |
| int expectedCommitCount, |
| Set<? extends ObjectId> excludeFromBitmapSelection) |
| throws IncorrectObjectTypeException, IOException, |
| MissingObjectException { |
| // Track bitmaps and commits from the previous GC pack bitmap indices. |
| BitmapBuilder reuse = commitBitmapIndex.newBitmapBuilder(); |
| List<BitmapCommit> reuseCommits = new ArrayList<>(); |
| for (PackBitmapIndexRemapper.Entry entry : bitmapRemapper) { |
| // More recent commits did not have the reuse flag set, so skip them |
| if ((entry.getFlags() & FLAG_REUSE) != FLAG_REUSE) { |
| continue; |
| } |
| RevObject ro = rw.peel(rw.parseAny(entry)); |
| if (!(ro instanceof RevCommit)) { |
| continue; |
| } |
| |
| RevCommit rc = (RevCommit) ro; |
| reuseCommits.add(new BitmapCommit(rc, false, entry.getFlags())); |
| if (!reuse.contains(rc)) { |
| EWAHCompressedBitmap bitmap = bitmapRemapper.ofObjectType( |
| bitmapRemapper.getBitmap(rc), Constants.OBJ_COMMIT); |
| reuse.or(new CompressedBitmap(bitmap, commitBitmapIndex)); |
| } |
| } |
| |
| // Add branch tips that are not represented in a previous pack's bitmap |
| // indices. Set up a RevWalk to find new commits not in the old packs. |
| List<RevCommit> newWantsByNewest = new ArrayList<>(want.size()); |
| Set<RevCommit> newWants = new HashSet<>(want.size()); |
| for (AnyObjectId objectId : want) { |
| RevObject ro = rw.peel(rw.parseAny(objectId)); |
| if (!(ro instanceof RevCommit) || reuse.contains(ro) |
| || excludeFromBitmapSelection.contains(ro)) { |
| continue; |
| } |
| |
| RevCommit rc = (RevCommit) ro; |
| rw.markStart(rc); |
| newWants.add(rc); |
| newWantsByNewest.add(rc); |
| } |
| |
| // Create a list of commits in reverse order (older to newer) that are |
| // not in the previous bitmap indices and are reachable. |
| rw.setRevFilter(new NotInBitmapFilter(reuse)); |
| RevCommit[] commits = new RevCommit[expectedCommitCount]; |
| int pos = commits.length; |
| RevCommit rc; |
| while ((rc = rw.next()) != null && pos > 0) { |
| commits[--pos] = rc; |
| pm.update(1); |
| } |
| |
| // Sort the new wants by reverse commit time. |
| Collections.sort(newWantsByNewest, ORDER_BY_REVERSE_TIMESTAMP); |
| return new CommitSelectionHelper(newWants, commits, pos, |
| newWantsByNewest, reuse, reuseCommits); |
| } |
| |
| /*- |
| * Returns the desired distance to the next bitmap based on the distance |
| * from the tip commit. Only differentiates recent from distant spans, |
| * selectCommits() handles the contiguous commits at the tip for active |
| * or inactive branches. |
| * |
| * A graph of this function looks like this, where |
| * the X axis is the distance from the tip commit and the Y axis is the |
| * bitmap selection distance. |
| * |
| * 5000 ____... |
| * / |
| * / |
| * / |
| * / |
| * 100 _____/ |
| * 0 20100 25000 |
| * |
| * Linear scaling between 20100 and 25000 prevents spans >100 for distances |
| * <20000 (otherwise, a span of 5000 would be returned for a distance of |
| * 21000, and the range 16000-20000 would have no selections). |
| */ |
| int nextSpan(int distanceFromTip) { |
| if (distanceFromTip < 0) { |
| throw new IllegalArgumentException(); |
| } |
| |
| // Commits more toward the start will have more bitmaps. |
| if (distanceFromTip <= recentCommitCount) { |
| return recentCommitSpan; |
| } |
| |
| int next = Math.min(distanceFromTip - recentCommitCount, |
| distantCommitSpan); |
| return Math.max(next, recentCommitSpan); |
| } |
| |
| BitmapWalker newBitmapWalker() { |
| return new BitmapWalker( |
| new ObjectWalk(reader), bitmapIndex, null); |
| } |
| |
| /** |
| * A commit object for which a bitmap index should be built. |
| */ |
| static final class BitmapCommit extends ObjectId { |
| private final boolean reuseWalker; |
| private final int flags; |
| |
| BitmapCommit(AnyObjectId objectId, boolean reuseWalker, int flags) { |
| super(objectId); |
| this.reuseWalker = reuseWalker; |
| this.flags = flags; |
| } |
| |
| boolean isReuseWalker() { |
| return reuseWalker; |
| } |
| |
| int getFlags() { |
| return flags; |
| } |
| } |
| |
| /** |
| * Container for state used in the first phase of selecting commits, which |
| * walks all of the reachable commits via the branch tips that are not |
| * covered by a previous pack's bitmaps ({@code newWants}) and stores them |
| * in {@code newCommitsByOldest}. {@code newCommitsByOldest} is initialized |
| * with an expected size of all commits, but may be smaller if some commits |
| * are unreachable and/or some commits are covered by a previous pack's |
| * bitmaps. {@code commitStartPos} will contain a positive offset to either |
| * the root commit or the oldest commit not covered by previous bitmaps. |
| */ |
| private static final class CommitSelectionHelper implements Iterable<RevCommit> { |
| final Set<? extends ObjectId> newWants; |
| |
| final List<RevCommit> newWantsByNewest; |
| final BitmapBuilder reusedCommitsBitmap; |
| |
| final List<BitmapCommit> reusedCommits; |
| |
| final RevCommit[] newCommitsByOldest; |
| |
| final int newCommitStartPos; |
| |
| CommitSelectionHelper(Set<? extends ObjectId> newWants, |
| RevCommit[] commitsByOldest, int commitStartPos, |
| List<RevCommit> newWantsByNewest, |
| BitmapBuilder reusedCommitsBitmap, |
| List<BitmapCommit> reuse) { |
| this.newWants = newWants; |
| this.newCommitsByOldest = commitsByOldest; |
| this.newCommitStartPos = commitStartPos; |
| this.newWantsByNewest = newWantsByNewest; |
| this.reusedCommitsBitmap = reusedCommitsBitmap; |
| this.reusedCommits = reuse; |
| } |
| |
| @Override |
| public Iterator<RevCommit> iterator() { |
| // Member variables referenced by this iterator will have synthetic |
| // accessors generated for them if they are made private. |
| return new Iterator<RevCommit>() { |
| int pos = newCommitStartPos; |
| |
| @Override |
| public boolean hasNext() { |
| return pos < newCommitsByOldest.length; |
| } |
| |
| @Override |
| public RevCommit next() { |
| return newCommitsByOldest[pos++]; |
| } |
| |
| @Override |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| }; |
| } |
| |
| int getCommitCount() { |
| return newCommitsByOldest.length - newCommitStartPos; |
| } |
| } |
| } |