aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorColby Ranger2012-08-06 14:09:53 (EDT)
committerColby Ranger2013-03-05 14:14:45 (EST)
commitdafcb8f6db82b899c917832768f1c240d273190c (patch)
tree96ff22dbf1b95b3bdad4ce9f2f1614ffddd83088
parent3b325917a5c928caadd88a0ec718b1632f088fd5 (diff)
downloadjgit-dafcb8f6db82b899c917832768f1c240d273190c.zip
jgit-dafcb8f6db82b899c917832768f1c240d273190c.tar.gz
jgit-dafcb8f6db82b899c917832768f1c240d273190c.tar.bz2
Support creating pack bitmap indexes in PackWriter.refs/changes/40/7940/18
Update the PackWriter to support writing out pack bitmap indexes, a parallel ".bitmap" file to the ".pack" file. Bitmaps are selected at commits every 1 to 5,000 commits for each unique path from the start. The most recent 100 commits are all bitmapped. The next 19,000 commits have a bitmaps every 100 commits. The remaining commits have a bitmap every 5,000 commits. Commits with more than 1 parent are prefered over ones with 1 or less. Furthermore, previously computed bitmaps are reused, if the previous entry had the reuse flag set, which is set when the bitmap was placed at the max allowed distance. Bitmaps are used to speed up the counting phase when packing, for requests that are not shallow. The PackWriterBitmapWalker uses a RevFilter to proactively mark commits with RevFlag.SEEN, when they appear in a bitmap. The walker produces the full closure of reachable ObjectIds, given the collection of starting ObjectIds. For fetch request, two ObjectWalks are executed to compute the ObjectIds reachable from the haves and from the wants. The ObjectIds needed to be written are determined by taking all the resulting wants AND NOT the haves. For clone requests, we get cached pack support for "free" since it is possible to determine if all of the ObjectIds in a pack file are included in the resulting list of ObjectIds to write. On my machine, the best times for clones and fetches of the linux kernel repository (with about 2.6M objects and 300K commits) are tabulated below: Operation Index V2 Index VE003 Clone 37530ms (524.06 MiB) 82ms (524.06 MiB) Fetch (1 commit back) 75ms 107ms Fetch (10 commits back) 456ms (269.51 KiB) 341ms (265.19 KiB) Fetch (100 commits back) 449ms (269.91 KiB) 337ms (267.28 KiB) Fetch (1000 commits back) 2229ms ( 14.75 MiB) 189ms ( 14.42 MiB) Fetch (10000 commits back) 2177ms ( 16.30 MiB) 254ms ( 15.88 MiB) Fetch (100000 commits back) 14340ms (185.83 MiB) 1655ms (189.39 MiB) Change-Id: Icdb0cdd66ff168917fb9ef17b96093990cc6a98d
-rw-r--r--org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties4
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java4
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java10
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java12
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java7
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java197
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java12
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java44
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java12
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java19
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java38
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java208
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java373
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java164
14 files changed, 1078 insertions, 26 deletions
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 28e0a4c..18f3314 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -25,10 +25,13 @@ badSectionEntry=Bad section entry: {0}
bareRepositoryNoWorkdirAndIndex=Bare Repository has neither a working tree, nor an index
base64InputNotProperlyPadded=Base64 input not properly padded.
baseLengthIncorrect=base length incorrect
+bitmapMissingObject=Bitmap at {0} is missing {1}.
+bitmapsMustBePrepared=Bitmaps must be prepared before they may be written.
blameNotCommittedYet=Not Committed Yet
blobNotFound=Blob not found: {0}
blobNotFoundForPath=Blob not found: {0} for path: {1}
branchNameInvalid=Branch name {0} is not allowed
+buildingBitmaps=Building bitmaps
cachedPacksPreventsIndexCreation=Using cached packs prevents index creation
cachedPacksPreventsListingObjects=Using cached packs prevents listing objects
cannotBeCombined=Cannot be combined.
@@ -426,6 +429,7 @@ rewinding=Rewinding to commit {0}
searchForReuse=Finding sources
searchForSizes=Getting sizes
secondsAgo={0} seconds ago
+selectingCommits=Selecting commits
sequenceTooLargeForDiffAlgorithm=Sequence too large for difference algorithm.
serviceNotEnabledNoName=Service not enabled
serviceNotPermitted={0} not permitted
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
index 388e0d3..7a1efe8 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -87,10 +87,13 @@ public class JGitText extends TranslationBundle {
/***/ public String bareRepositoryNoWorkdirAndIndex;
/***/ public String base64InputNotProperlyPadded;
/***/ public String baseLengthIncorrect;
+ /***/ public String bitmapMissingObject;
+ /***/ public String bitmapsMustBePrepared;
/***/ public String blameNotCommittedYet;
/***/ public String blobNotFound;
/***/ public String blobNotFoundForPath;
/***/ public String branchNameInvalid;
+ /***/ public String buildingBitmaps;
/***/ public String cachedPacksPreventsIndexCreation;
/***/ public String cachedPacksPreventsListingObjects;
/***/ public String cannotBeCombined;
@@ -488,6 +491,7 @@ public class JGitText extends TranslationBundle {
/***/ public String searchForReuse;
/***/ public String searchForSizes;
/***/ public String secondsAgo;
+ /***/ public String selectingCommits;
/***/ public String sequenceTooLargeForDiffAlgorithm;
/***/ public String serviceNotEnabledNoName;
/***/ public String serviceNotPermitted;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java
index 85982c7..c767c03 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java
@@ -66,6 +66,16 @@ public class RevFlag {
public static final RevFlag UNINTERESTING = new StaticRevFlag(
"UNINTERESTING", RevWalk.UNINTERESTING); //$NON-NLS-1$
+ /**
+ * Set on RevCommit instances added to {@link RevWalk#pending} queue.
+ * <p>
+ * We use this flag to avoid adding the same commit instance twice to our
+ * queue, especially if we reached it by more than one path.
+ * <p>
+ * This is a static flag. Its RevWalk is not available.
+ */
+ public static final RevFlag SEEN = new StaticRevFlag("SEEN", RevWalk.SEEN);
+
final RevWalk walker;
final String name;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java
index 455f1bb..6d131ab 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java
@@ -76,6 +76,7 @@ import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.AsyncObjectLoaderQueue;
import org.eclipse.jgit.lib.AsyncObjectSizeQueue;
import org.eclipse.jgit.lib.BitmapIndex;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.InflaterCache;
import org.eclipse.jgit.lib.ObjectId;
@@ -152,6 +153,17 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs {
return null;
}
+ public Collection<CachedPack> getCachedPacksAndUpdate(
+ BitmapBuilder needBitmap) throws IOException {
+ for (DfsPackFile pack : db.getPacks()) {
+ PackBitmapIndex bitmapIndex = pack.getPackBitmapIndex(this);
+ if (needBitmap.removeAllOrNone(bitmapIndex))
+ return Collections.<CachedPack> singletonList(
+ new DfsCachedPack(pack));
+ }
+ return Collections.emptyList();
+ }
+
@Override
public Collection<ObjectId> resolve(AbbreviatedObjectId id)
throws IOException {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java
index 82503b6..c0e47ee 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java
@@ -77,6 +77,13 @@ class LocalCachedPack extends CachedPack {
this.packNames = packNames.toArray(new String[packNames.size()]);
}
+ LocalCachedPack(List<PackFile> packs) {
+ odb = null;
+ tips = null;
+ packNames = null;
+ this.packs = packs.toArray(new PackFile[packs.size()]);
+ }
+
@Override
public Set<ObjectId> getTips() {
return tips;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java
new file mode 100644
index 0000000..1bc90c6
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java
@@ -0,0 +1,197 @@
+/*
+ * Copyright (C) 2013, 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.storage.file;
+
+import java.util.Collections;
+import java.util.Iterator;
+
+import javaewah.EWAHCompressedBitmap;
+import javaewah.IntIterator;
+
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.BitmapIndex;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectIdOwnerMap;
+import org.eclipse.jgit.storage.file.BasePackBitmapIndex.StoredBitmap;
+
+/**
+ * A PackBitmapIndex that remaps the bitmaps in the previous index to the
+ * positions in the new pack index. Note, unlike typical PackBitmapIndex
+ * implementations this implementation is not thread safe, as it is intended to
+ * be used with a PackBitmapIndexBuilder, which is also not thread safe.
+ */
+public class PackBitmapIndexRemapper extends PackBitmapIndex
+ implements Iterable<PackBitmapIndexRemapper.Entry> {
+
+ private final BasePackBitmapIndex oldPackIndex;
+ private final PackBitmapIndex newPackIndex;
+ private final ObjectIdOwnerMap<StoredBitmap> convertedBitmaps;
+ private final BitSet inflated;
+ private final int[] prevToNewMapping;
+
+ /**
+ * A PackBitmapIndex that maps the positions in the prevBitmapIndex to the
+ * ones in the newIndex.
+ *
+ * @param prevBitmapIndex
+ * the bitmap index with the old mapping.
+ * @param newIndex
+ * the bitmap index with the new mapping.
+ * @return a bitmap index that attempts to do the mapping between the two.
+ */
+ public static PackBitmapIndexRemapper newPackBitmapIndex(
+ BitmapIndex prevBitmapIndex, PackBitmapIndex newIndex) {
+ if (!(prevBitmapIndex instanceof BitmapIndexImpl))
+ return new PackBitmapIndexRemapper(newIndex);
+
+ PackBitmapIndex prevIndex = ((BitmapIndexImpl) prevBitmapIndex)
+ .getPackBitmapIndex();
+ if (!(prevIndex instanceof BasePackBitmapIndex))
+ return new PackBitmapIndexRemapper(newIndex);
+
+ return new PackBitmapIndexRemapper(
+ (BasePackBitmapIndex) prevIndex, newIndex);
+ }
+
+ private PackBitmapIndexRemapper(PackBitmapIndex newPackIndex) {
+ this.oldPackIndex = null;
+ this.newPackIndex = newPackIndex;
+ this.convertedBitmaps = null;
+ this.inflated = null;
+ this.prevToNewMapping = null;
+ }
+
+ private PackBitmapIndexRemapper(
+ BasePackBitmapIndex oldPackIndex, PackBitmapIndex newPackIndex) {
+ this.oldPackIndex = oldPackIndex;
+ this.newPackIndex = newPackIndex;
+ convertedBitmaps = new ObjectIdOwnerMap<StoredBitmap>();
+ inflated = new BitSet(newPackIndex.getObjectCount());
+
+ prevToNewMapping = new int[oldPackIndex.getObjectCount()];
+ for (int pos = 0; pos < prevToNewMapping.length; pos++)
+ prevToNewMapping[pos] = newPackIndex.findPosition(
+ oldPackIndex.getObject(pos));
+ }
+
+ @Override
+ public int findPosition(AnyObjectId objectId) {
+ return newPackIndex.findPosition(objectId);
+ }
+
+ @Override
+ public ObjectId getObject(int position) throws IllegalArgumentException {
+ return newPackIndex.getObject(position);
+ }
+
+ @Override
+ public int getObjectCount() {
+ return newPackIndex.getObjectCount();
+ }
+
+ @Override
+ public EWAHCompressedBitmap ofObjectType(
+ EWAHCompressedBitmap bitmap, int type) {
+ return newPackIndex.ofObjectType(bitmap, type);
+ }
+
+ public Iterator<Entry> iterator() {
+ if (oldPackIndex == null)
+ return Collections.<Entry> emptyList().iterator();
+
+ final Iterator<StoredBitmap> it = oldPackIndex.getBitmaps().iterator();
+ return new Iterator<Entry>() {
+ public boolean hasNext() {
+ return it.hasNext();
+ }
+
+ public Entry next() {
+ StoredBitmap sb = it.next();
+ return new Entry(sb, sb.getFlags());
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+
+ @Override
+ public EWAHCompressedBitmap getBitmap(AnyObjectId objectId) {
+ EWAHCompressedBitmap bitmap = newPackIndex.getBitmap(objectId);
+ if (bitmap != null || oldPackIndex == null)
+ return bitmap;
+
+ StoredBitmap stored = convertedBitmaps.get(objectId);
+ if (stored != null)
+ return stored.getBitmap();
+
+ StoredBitmap oldBitmap = oldPackIndex.getBitmaps().get(objectId);
+ if (oldBitmap == null)
+ return null;
+
+ inflated.clear();
+ for (IntIterator i = oldBitmap.getBitmap().intIterator(); i.hasNext();)
+ inflated.set(prevToNewMapping[i.next()]);
+ bitmap = inflated.toEWAHCompressedBitmap();
+ convertedBitmaps.add(
+ new StoredBitmap(objectId, bitmap, null, oldBitmap.getFlags()));
+ return bitmap;
+ }
+
+ /** An entry in the old PackBitmapIndex. */
+ public final class Entry extends ObjectId {
+ private final int flags;
+
+ private Entry(AnyObjectId src, int flags) {
+ super(src);
+ this.flags = flags;
+ }
+
+ /** @return the flags associated with the bitmap. */
+ public int getFlags() {
+ return flags;
+ }
+ }
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java
index 8636eb3..8ea4d15 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java
@@ -62,11 +62,17 @@ import org.eclipse.jgit.util.io.SafeBufferedOutputStream;
*
* @see PackBitmapIndexV1
*/
-class PackBitmapIndexWriterV1 {
+public class PackBitmapIndexWriterV1 {
private final DigestOutputStream out;
private final DataOutput dataOutput;
- PackBitmapIndexWriterV1(final OutputStream dst) {
+ /**
+ * Creates the version 1 pack bitmap index files.
+ *
+ * @param dst
+ * the output stream to which the index will be written.
+ */
+ public PackBitmapIndexWriterV1(final OutputStream dst) {
out = new DigestOutputStream(dst instanceof BufferedOutputStream ? dst
: new SafeBufferedOutputStream(dst),
Constants.newMessageDigest());
@@ -140,7 +146,7 @@ class PackBitmapIndexWriterV1 {
}
private void writeBitmapEntry(StoredEntry entry) throws IOException {
- // Write object, xor offset, and bitmap
+ // Write object, XOR offset, and bitmap
dataOutput.writeInt((int) entry.getObjectId());
out.write(entry.getXorOffset());
out.write(entry.getFlags());
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java
index b78c5ae..e1c2a3e 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java
@@ -94,24 +94,44 @@ public abstract class PackIndexWriter {
* @throws IllegalArgumentException
* no recognized pack index version can support the supplied
* objects. This is likely a bug in the implementation.
+ * @see #oldestPossibleFormat(List)
*/
- @SuppressWarnings("fallthrough")
public static PackIndexWriter createOldestPossible(final OutputStream dst,
final List<? extends PackedObjectInfo> objs) {
- int version = 1;
- LOOP: for (final PackedObjectInfo oe : objs) {
- switch (version) {
- case 1:
- if (PackIndexWriterV1.canStore(oe))
- continue;
- version = 2;
- case 2:
- break LOOP;
- }
+ return createVersion(dst, oldestPossibleFormat(objs));
+ }
+
+ /**
+ * Return the oldest (most widely understood) index format.
+ * <p>
+ * This method selects an index format that can accurate describe the
+ * supplied objects and that will be the most compatible format with older
+ * Git implementations.
+ * <p>
+ * Index version 1 is widely recognized by all Git implementations, but
+ * index version 2 (and later) is not as well recognized as it was
+ * introduced more than a year later. Index version 1 can only be used if
+ * the resulting pack file is under 4 gigabytes in size; packs larger than
+ * that limit must use index version 2.
+ *
+ * @param objs
+ * the objects the caller needs to store in the index. Entries
+ * will be examined until a format can be conclusively selected.
+ * @return the index format.
+ * @throws IllegalArgumentException
+ * no recognized pack index version can support the supplied
+ * objects. This is likely a bug in the implementation.
+ */
+ public static int oldestPossibleFormat(
+ final List<? extends PackedObjectInfo> objs) {
+ for (final PackedObjectInfo oe : objs) {
+ if (!PackIndexWriterV1.canStore(oe))
+ return 2;
}
- return createVersion(dst, version);
+ return 1;
}
+
/**
* Create a new writer instance for a specific index format version.
*
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java
index 2af48ed..d9906de 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java
@@ -63,6 +63,7 @@ import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.AbbreviatedObjectId;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.BitmapIndex;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.InflaterCache;
import org.eclipse.jgit.lib.ObjectId;
@@ -113,6 +114,17 @@ final class WindowCursor extends ObjectReader implements ObjectReuseAsIs {
return null;
}
+ public Collection<CachedPack> getCachedPacksAndUpdate(
+ BitmapBuilder needBitmap) throws IOException {
+ for (PackFile pack : db.getPacks()) {
+ PackBitmapIndex index = pack.getBitmapIndex();
+ if (needBitmap.removeAllOrNone(index))
+ return Collections.<CachedPack> singletonList(
+ new LocalCachedPack(Collections.singletonList(pack)));
+ }
+ return Collections.emptyList();
+ }
+
@Override
public Collection<ObjectId> resolve(AbbreviatedObjectId id)
throws IOException {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java
index ed0294e..8816ca4 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java
@@ -50,6 +50,7 @@ import java.util.List;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException;
import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
import org.eclipse.jgit.lib.ObjectReader;
import org.eclipse.jgit.lib.ProgressMonitor;
@@ -232,4 +233,22 @@ public interface ObjectReuseAsIs {
*/
public abstract void copyPackAsIs(PackOutputStream out, CachedPack pack,
boolean validate) throws IOException;
+
+ /**
+ * Obtain the available cached packs that match the bitmap and update
+ * the bitmap by removing the items that are in the CachedPack.
+ * <p>
+ * A cached pack has known starting points and may be sent entirely as-is,
+ * with almost no effort on the sender's part.
+ *
+ * @param needBitmap
+ * the bitmap that contains all of the objects the client wants.
+ * @return the available cached packs.
+ * @throws IOException
+ * the cached packs cannot be listed from the repository.
+ * Callers may choose to ignore this and continue as-if there
+ * were no cached packs.
+ */
+ public Collection<CachedPack> getCachedPacksAndUpdate(
+ BitmapBuilder needBitmap) throws IOException;
}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java
index 58ee985..fdff230 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java
@@ -130,6 +130,13 @@ public class PackConfig {
*/
public static final int DEFAULT_INDEX_VERSION = 2;
+ /**
+ * Default value of the build bitmaps option: {@value}
+ *
+ * @see #setBuildBitmaps(boolean)
+ */
+ public static final boolean DEFAULT_BUILD_BITMAPS = false;
+
private int compressionLevel = Deflater.DEFAULT_COMPRESSION;
@@ -159,6 +166,8 @@ public class PackConfig {
private int indexVersion = DEFAULT_INDEX_VERSION;
+ private boolean buildBitmaps = DEFAULT_BUILD_BITMAPS;
+
/** Create a default configuration. */
public PackConfig() {
@@ -210,6 +219,7 @@ public class PackConfig {
this.threads = cfg.threads;
this.executor = cfg.executor;
this.indexVersion = cfg.indexVersion;
+ this.buildBitmaps = cfg.buildBitmaps;
}
/**
@@ -615,6 +625,33 @@ public class PackConfig {
}
/**
+ * True if writer is allowed to build bitmaps for indexes.
+ *
+ * Default setting: {@value #DEFAULT_BUILD_BITMAPS}
+ *
+ * @return true if delta base is the writer can choose to output an index
+ * with bitmaps.
+ */
+ public boolean isBuildBitmaps() {
+ return buildBitmaps;
+ }
+
+ /**
+ * Set writer to allow building bitmaps for supported pack files.
+ *
+ * Index files can include bitmaps to speed up future ObjectWalks.
+ *
+ * Default setting: {@value #DEFAULT_BUILD_BITMAPS}
+ *
+ * @param buildBitmaps
+ * boolean indicating whether bitmaps may be included in the
+ * index.
+ */
+ public void setBuildBitmaps(boolean buildBitmaps) {
+ this.buildBitmaps = buildBitmaps;
+ }
+
+ /**
* Update properties by setting fields from the configuration.
*
* If a property's corresponding variable is not defined in the supplied
@@ -646,5 +683,6 @@ public class PackConfig {
setReuseObjects(rc.getBoolean("pack", "reuseobjects", isReuseObjects())); //$NON-NLS-1$ //$NON-NLS-2$
setDeltaCompress(rc.getBoolean(
"pack", "deltacompression", isDeltaCompress())); //$NON-NLS-1$ //$NON-NLS-2$
+ setBuildBitmaps(rc.getBoolean("pack", "buildbitmaps", isBuildBitmaps())); //$NON-NLS-1$ //$NON-NLS-2$
}
}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java
index 77ebaf6..470ffd3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java
@@ -84,6 +84,9 @@ import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.AsyncObjectSizeQueue;
import org.eclipse.jgit.lib.BatchingProgressMonitor;
+import org.eclipse.jgit.lib.BitmapIndex;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
+import org.eclipse.jgit.lib.BitmapObject;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.NullProgressMonitor;
import org.eclipse.jgit.lib.ObjectId;
@@ -103,6 +106,8 @@ import org.eclipse.jgit.revwalk.RevObject;
import org.eclipse.jgit.revwalk.RevSort;
import org.eclipse.jgit.revwalk.RevTag;
import org.eclipse.jgit.revwalk.RevTree;
+import org.eclipse.jgit.storage.file.PackBitmapIndexBuilder;
+import org.eclipse.jgit.storage.file.PackBitmapIndexWriterV1;
import org.eclipse.jgit.storage.file.PackIndexWriter;
import org.eclipse.jgit.util.BlockList;
import org.eclipse.jgit.util.TemporaryBuffer;
@@ -213,6 +218,9 @@ public class PackWriter {
// edge objects for thin packs
private List<ObjectToPack> edgeObjects = new BlockList<ObjectToPack>();
+ // Objects the client is known to have already.
+ private BitmapBuilder haveObjects;
+
private List<CachedPack> cachedPacks = new ArrayList<CachedPack>(2);
private Set<ObjectId> tagTargets = Collections.emptySet();
@@ -254,16 +262,22 @@ public class PackWriter {
private boolean useCachedPacks;
+ private boolean useBitmaps;
+
private boolean ignoreMissingUninteresting = true;
private boolean pruneCurrentObjectList;
private boolean shallowPack;
+ private boolean canBuildBitmaps;
+
private int depth;
private Collection<? extends ObjectId> unshallowObjects;
+ private PackBitmapIndexBuilder writeBitmaps;
+
/**
* Create writer for specified repository.
* <p>
@@ -441,6 +455,19 @@ public class PackWriter {
useCachedPacks = useCached;
}
+ /** @return true to use bitmaps for ObjectWalks, if available. */
+ public boolean isUseBitmaps() {
+ return useBitmaps;
+ }
+
+ /**
+ * @param useBitmaps
+ * if set to true, bitmaps will be used when preparing a pack.
+ */
+ public void setUseBitmaps(boolean useBitmaps) {
+ this.useBitmaps = useBitmaps;
+ }
+
/**
* @return true to ignore objects that are uninteresting and also not found
* on local disk; false to throw a {@link MissingObjectException}
@@ -792,6 +819,25 @@ public class PackWriter {
}
/**
+ * Returns the index format version that will be written.
+ * <p>
+ * This method can only be invoked after
+ * {@link #writePack(ProgressMonitor, ProgressMonitor, OutputStream)} has
+ * been invoked and completed successfully.
+ *
+ * @return the index format version.
+ */
+ public int getIndexVersion() {
+ int indexVersion = config.getIndexVersion();
+ if (indexVersion <= 0) {
+ for (BlockList<ObjectToPack> objs : objectsLists)
+ indexVersion = Math.max(indexVersion,
+ PackIndexWriter.oldestPossibleFormat(objs));
+ }
+ return indexVersion;
+ }
+
+ /**
* Create an index file to match the pack file just written.
* <p>
* This method can only be invoked after
@@ -810,14 +856,34 @@ public class PackWriter {
throw new IOException(JGitText.get().cachedPacksPreventsIndexCreation);
long writeStart = System.currentTimeMillis();
- final List<ObjectToPack> list = sortByName();
- final PackIndexWriter iw;
- int indexVersion = config.getIndexVersion();
- if (indexVersion <= 0)
- iw = PackIndexWriter.createOldestPossible(indexStream, list);
- else
- iw = PackIndexWriter.createVersion(indexStream, indexVersion);
- iw.write(list, packcsum);
+ final PackIndexWriter iw = PackIndexWriter.createVersion(
+ indexStream, getIndexVersion());
+ iw.write(sortByName(), packcsum);
+ stats.timeWriting += System.currentTimeMillis() - writeStart;
+ }
+
+ /**
+ * Create a bitmap index file to match the pack file just written.
+ * <p>
+ * This method can only be invoked after
+ * {@link #prepareBitmapIndex(ProgressMonitor, Set)} has been invoked and
+ * completed successfully. Writing a corresponding bitmap index is an
+ * optional feature that not all pack users may require.
+ *
+ * @param bitmapIndexStream
+ * output for the bitmap index data. Caller is responsible for
+ * closing this stream.
+ * @throws IOException
+ * the index data could not be written to the supplied stream.
+ */
+ public void writeBitmapIndex(final OutputStream bitmapIndexStream)
+ throws IOException {
+ if (writeBitmaps == null)
+ throw new IOException(JGitText.get().bitmapsMustBePrepared);
+
+ long writeStart = System.currentTimeMillis();
+ final PackBitmapIndexWriterV1 iw = new PackBitmapIndexWriterV1(bitmapIndexStream);
+ iw.write(writeBitmaps, packcsum);
stats.timeWriting += System.currentTimeMillis() - writeStart;
}
@@ -859,6 +925,9 @@ public class PackWriter {
case WRITING:
task = JGitText.get().writingObjects;
break;
+ case BUILDING_BITMAPS:
+ task = JGitText.get().buildingBitmaps;
+ break;
default:
throw new IllegalArgumentException(
MessageFormat.format(JGitText.get().illegalPackingPhase, phase));
@@ -1540,6 +1609,24 @@ public class PackWriter {
stats.interestingObjects = Collections.unmodifiableSet(new HashSet<ObjectId>(want));
stats.uninterestingObjects = Collections.unmodifiableSet(new HashSet<ObjectId>(have));
+ walker.setRetainBody(false);
+
+ canBuildBitmaps = config.isBuildBitmaps()
+ && !shallowPack
+ && have.isEmpty()
+ && (excludeInPacks == null || excludeInPacks.length == 0);
+ if (!shallowPack && useBitmaps) {
+ BitmapIndex bitmapIndex = reader.getBitmapIndex();
+ if (bitmapIndex != null) {
+ PackWriterBitmapWalker bitmapWalker = new PackWriterBitmapWalker(
+ walker, bitmapIndex, countingMonitor);
+ findObjectsToPackUsingBitmaps(bitmapWalker, want, have);
+ endPhase(countingMonitor);
+ stats.timeCounting = System.currentTimeMillis() - countingStart;
+ return;
+ }
+ }
+
List<ObjectId> all = new ArrayList<ObjectId>(want.size() + have.size());
all.addAll(want);
all.addAll(have);
@@ -1552,7 +1639,6 @@ public class PackWriter {
final RevFlagSet keepOnRestart = new RevFlagSet();
keepOnRestart.add(inCachedPack);
- walker.setRetainBody(false);
walker.carry(include);
int haveEst = have.size();
@@ -1761,6 +1847,34 @@ public class PackWriter {
stats.timeCounting = System.currentTimeMillis() - countingStart;
}
+ private void findObjectsToPackUsingBitmaps(
+ PackWriterBitmapWalker bitmapWalker, Set<? extends ObjectId> want,
+ Set<? extends ObjectId> have)
+ throws MissingObjectException, IncorrectObjectTypeException,
+ IOException {
+ BitmapBuilder haveBitmap = bitmapWalker.findObjects(have, null);
+ bitmapWalker.reset();
+ BitmapBuilder wantBitmap = bitmapWalker.findObjects(want, haveBitmap);
+ BitmapBuilder needBitmap = wantBitmap.andNot(haveBitmap);
+
+ if (useCachedPacks && reuseSupport != null
+ && (excludeInPacks == null || excludeInPacks.length == 0))
+ cachedPacks.addAll(
+ reuseSupport.getCachedPacksAndUpdate(needBitmap));
+
+ for (BitmapObject obj : needBitmap) {
+ ObjectId objectId = obj.getObjectId();
+ if (exclude(objectId)) {
+ needBitmap.remove(objectId);
+ continue;
+ }
+ addObject(objectId, obj.getType(), 0);
+ }
+
+ if (thin)
+ haveObjects = haveBitmap;
+ }
+
private static void pruneEdgesFromObjectList(List<ObjectToPack> list) {
final int size = list.size();
int src = 0;
@@ -1892,7 +2006,7 @@ public class PackWriter {
if (ptr != null && !ptr.isEdge()) {
otp.setDeltaBase(ptr);
otp.setReuseAsIs();
- } else if (thin && ptr != null && ptr.isEdge()) {
+ } else if (thin && have(ptr, baseId)) {
otp.setDeltaBase(baseId);
otp.setReuseAsIs();
} else {
@@ -1920,6 +2034,75 @@ public class PackWriter {
otp.select(next);
}
+ private final boolean have(ObjectToPack ptr, AnyObjectId objectId) {
+ return (ptr != null && ptr.isEdge())
+ || (haveObjects != null && haveObjects.contains(objectId));
+ }
+
+ /**
+ * Prepares the bitmaps to be written to the pack index. Bitmaps can be used
+ * to speed up fetches and clones by storing the entire object graph at
+ * selected commits.
+ *
+ * This method can only be invoked after
+ * {@link #writePack(ProgressMonitor, ProgressMonitor, OutputStream)} has
+ * been invoked and completed successfully. Writing a corresponding bitmap
+ * index is an optional feature that not all pack users may require.
+ *
+ * @param pm
+ * progress monitor to report bitmap building work.
+ * @param want
+ * collection of objects to be marked as interesting (start
+ * points of graph traversal).
+ * @return whether a bitmap index may be written.
+ * @throws IOException
+ * when some I/O problem occur during reading objects.
+ */
+ public boolean prepareBitmapIndex(
+ ProgressMonitor pm, Set<? extends ObjectId> want)
+ throws IOException {
+ if (!canBuildBitmaps || getObjectCount() > Integer.MAX_VALUE
+ || !cachedPacks.isEmpty())
+ return false;
+
+ if (pm == null)
+ pm = NullProgressMonitor.INSTANCE;
+
+ writeBitmaps = new PackBitmapIndexBuilder(sortByName());
+ PackWriterBitmapPreparer bitmapPreparer =
+ new PackWriterBitmapPreparer(reader, writeBitmaps, pm, want);
+
+ int numCommits = objectsLists[Constants.OBJ_COMMIT].size();
+ Collection<PackWriterBitmapPreparer.BitmapCommit> selectedCommits =
+ bitmapPreparer.doCommitSelection(numCommits);
+
+ beginPhase(PackingPhase.BUILDING_BITMAPS, pm, selectedCommits.size());
+
+ PackWriterBitmapWalker walker = bitmapPreparer.newBitmapWalker();
+ AnyObjectId last = null;
+ for (PackWriterBitmapPreparer.BitmapCommit cmit : selectedCommits) {
+ if (cmit.isReuseWalker())
+ walker.reset();
+ else
+ walker = bitmapPreparer.newBitmapWalker();
+
+ BitmapBuilder bitmap = walker.findObjects(
+ Collections.singleton(cmit), null);
+
+ if (last != null && cmit.isReuseWalker() && !bitmap.contains(last))
+ throw new IllegalStateException(MessageFormat.format(
+ JGitText.get().bitmapMissingObject, cmit.name(),
+ last.name()));
+ last = cmit;
+ writeBitmaps.addBitmap(cmit, bitmap.build(), cmit.getFlags());
+
+ pm.update(1);
+ }
+
+ endPhase(pm);
+ return true;
+ }
+
private boolean reuseDeltaFor(ObjectToPack otp) {
switch (otp.getType()) {
case Constants.OBJ_COMMIT:
@@ -2296,7 +2479,10 @@ public class PackWriter {
COMPRESSING,
/** Writing objects phase. */
- WRITING;
+ WRITING,
+
+ /** Building bitmaps phase. */
+ BUILDING_BITMAPS;
}
/** Summary of the current state of a PackWriter. */
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java
new file mode 100644
index 0000000..11b2ecc
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java
@@ -0,0 +1,373 @@
+/*
+ * 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.storage.pack;
+
+import static org.eclipse.jgit.storage.file.PackBitmapIndex.FLAG_REUSE;
+
+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 javaewah.EWAHCompressedBitmap;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.lib.AnyObjectId;
+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.lib.BitmapIndex.BitmapBuilder;
+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.storage.file.BitmapIndexImpl;
+import org.eclipse.jgit.storage.file.PackBitmapIndex;
+import org.eclipse.jgit.storage.file.PackBitmapIndexBuilder;
+import org.eclipse.jgit.storage.file.PackBitmapIndexRemapper;
+import org.eclipse.jgit.util.BlockList;
+
+/** Helper class for the PackWriter to select commits for pack index bitmaps. */
+class PackWriterBitmapPreparer {
+
+ private static final Comparator<BitmapBuilder> BUILDER_BY_CARDINALITY_DSC =
+ new Comparator<BitmapBuilder>() {
+ public int compare(BitmapBuilder a, BitmapBuilder b) {
+ return Integer.signum(b.cardinality() - a.cardinality());
+ }
+ };
+
+ 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 minCommits = 100;
+ private final int maxCommits = 5000;
+
+ PackWriterBitmapPreparer(ObjectReader reader,
+ PackBitmapIndexBuilder writeBitmaps, ProgressMonitor pm,
+ Set<? extends ObjectId> want) 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);
+ }
+
+ Collection<BitmapCommit> doCommitSelection(int expectedNumCommits)
+ throws MissingObjectException, IncorrectObjectTypeException,
+ IOException {
+ pm.beginTask(JGitText.get().selectingCommits, ProgressMonitor.UNKNOWN);
+ RevWalk rw = new RevWalk(reader);
+ WalkResult result = findPaths(rw, expectedNumCommits);
+ pm.endTask();
+
+ int totCommits = result.commitsByOldest.length - result.commitStartPos;
+ BlockList<BitmapCommit> selections = new BlockList<BitmapCommit>(
+ totCommits / minCommits + 1);
+ for (BitmapCommit reuse : result.reuse)
+ selections.add(reuse);
+
+ if (totCommits == 0) {
+ for (AnyObjectId id : result.peeledWant)
+ selections.add(new BitmapCommit(id, false, 0));
+ return selections;
+ }
+
+ pm.beginTask(JGitText.get().selectingCommits, totCommits);
+
+ for (BitmapBuilder bitmapableCommits : result.paths) {
+ int cardinality = bitmapableCommits.cardinality();
+
+ List<List<BitmapCommit>> running = new ArrayList<
+ List<BitmapCommit>>();
+
+ // Insert bitmaps at the offsets suggested by the
+ // nextSelectionDistance() heuristic.
+ int index = -1;
+ int nextIn = nextSelectionDistance(0, cardinality);
+ int nextFlg = nextIn == maxCommits ? PackBitmapIndex.FLAG_REUSE : 0;
+ boolean mustPick = nextIn == 0;
+ for (RevCommit c : result) {
+ if (!bitmapableCommits.contains(c))
+ continue;
+
+ index++;
+ nextIn--;
+ pm.update(1);
+
+ // Always pick the items in want and prefer merge commits.
+ if (result.peeledWant.remove(c)) {
+ if (nextIn > 0)
+ nextFlg = 0;
+ } else if (!mustPick && ((nextIn > 0)
+ || (c.getParentCount() <= 1 && nextIn > -minCommits))) {
+ continue;
+ }
+
+ int flags = nextFlg;
+ nextIn = nextSelectionDistance(index, cardinality);
+ nextFlg = nextIn == maxCommits ? PackBitmapIndex.FLAG_REUSE : 0;
+ mustPick = nextIn == 0;
+
+ BitmapBuilder fullBitmap = commitBitmapIndex.newBitmapBuilder();
+ rw.reset();
+ rw.markStart(c);
+ for (AnyObjectId objectId : result.reuse)
+ rw.markUninteresting(rw.parseCommit(objectId));
+ rw.setRevFilter(
+ PackWriterBitmapWalker.newRevFilter(null, fullBitmap));
+
+ while (rw.next() != null) {
+ // Work is done in the RevFilter.
+ }
+
+ List<List<BitmapCommit>> matches = new ArrayList<
+ List<BitmapCommit>>();
+ for (List<BitmapCommit> list : running) {
+ BitmapCommit last = list.get(list.size() - 1);
+ if (fullBitmap.contains(last))
+ matches.add(list);
+ }
+
+ List<BitmapCommit> match;
+ if (matches.isEmpty()) {
+ match = new ArrayList<BitmapCommit>();
+ running.add(match);
+ } else {
+ match = matches.get(0);
+ // Append to longest
+ for (List<BitmapCommit> list : matches) {
+ if (list.size() > match.size())
+ match = list;
+ }
+ }
+ match.add(new BitmapCommit(c, !match.isEmpty(), flags));
+ writeBitmaps.addBitmap(c, fullBitmap, 0);
+ }
+
+ for (List<BitmapCommit> list : running)
+ selections.addAll(list);
+ }
+ writeBitmaps.clearBitmaps(); // Remove the temporary commit bitmaps.
+
+ // Add the remaining peeledWant
+ for (AnyObjectId remainingWant : result.peeledWant)
+ selections.add(new BitmapCommit(remainingWant, false, 0));
+
+ pm.endTask();
+ return selections;
+ }
+
+ private WalkResult findPaths(RevWalk rw, int expectedNumCommits)
+ throws MissingObjectException, IOException {
+ BitmapBuilder reuseBitmap = commitBitmapIndex.newBitmapBuilder();
+ List<BitmapCommit> reuse = new ArrayList<BitmapCommit>();
+ for (PackBitmapIndexRemapper.Entry entry : bitmapRemapper) {
+ if ((entry.getFlags() & FLAG_REUSE) != FLAG_REUSE)
+ continue;
+
+ RevObject ro = rw.peel(rw.parseAny(entry));
+ if (ro instanceof RevCommit) {
+ RevCommit rc = (RevCommit) ro;
+ reuse.add(new BitmapCommit(rc, false, entry.getFlags()));
+ rw.markUninteresting(rc);
+
+ EWAHCompressedBitmap bitmap = bitmapRemapper.ofObjectType(
+ bitmapRemapper.getBitmap(rc), Constants.OBJ_COMMIT);
+ writeBitmaps.addBitmap(rc, bitmap, 0);
+ reuseBitmap.add(rc, Constants.OBJ_COMMIT);
+ }
+ }
+ writeBitmaps.clearBitmaps(); // Remove temporary bitmaps
+
+ // Do a RevWalk by commit time descending. Keep track of all the paths
+ // from the wants.
+ List<BitmapBuilder> paths = new ArrayList<BitmapBuilder>(want.size());
+ Set<RevCommit> peeledWant = new HashSet<RevCommit>(want.size());
+ for (AnyObjectId objectId : want) {
+ RevObject ro = rw.peel(rw.parseAny(objectId));
+ if (ro instanceof RevCommit && !reuseBitmap.contains(ro)) {
+ RevCommit rc = (RevCommit) ro;
+ peeledWant.add(rc);
+ rw.markStart(rc);
+
+ BitmapBuilder bitmap = commitBitmapIndex.newBitmapBuilder();
+ bitmap.or(reuseBitmap);
+ bitmap.add(rc, Constants.OBJ_COMMIT);
+ paths.add(bitmap);
+ }
+ }
+
+ // Update the paths from the wants and create a list of commits in
+ // reverse iteration order.
+ RevCommit[] commits = new RevCommit[expectedNumCommits];
+ int pos = commits.length;
+ RevCommit rc;
+ while ((rc = rw.next()) != null) {
+ commits[--pos] = rc;
+ for (BitmapBuilder path : paths) {
+ if (path.contains(rc)) {
+ for (RevCommit c : rc.getParents())
+ path.add(c, Constants.OBJ_COMMIT);
+ }
+ }
+
+ pm.update(1);
+ }
+
+ // Remove the reused bitmaps from the paths
+ if (!reuse.isEmpty())
+ for (BitmapBuilder bitmap : paths)
+ bitmap.andNot(reuseBitmap);
+
+ // Sort the paths
+ List<BitmapBuilder> distinctPaths = new ArrayList<BitmapBuilder>(paths.size());
+ while (!paths.isEmpty()) {
+ Collections.sort(paths, BUILDER_BY_CARDINALITY_DSC);
+ BitmapBuilder largest = paths.remove(0);
+ distinctPaths.add(largest);
+
+ // Update the remaining paths, by removing the objects from
+ // the path that was just added.
+ for (int i = paths.size() - 1; i >= 0; i--)
+ paths.get(i).andNot(largest);
+ }
+
+ return new WalkResult(peeledWant, commits, pos, distinctPaths, reuse);
+ }
+
+ private int nextSelectionDistance(int idx, int cardinality) {
+ if (idx > cardinality)
+ throw new IllegalArgumentException();
+ int idxFromStart = cardinality - idx;
+ int mustRegionEnd = 100;
+ if (idxFromStart <= mustRegionEnd)
+ return 0;
+
+ // Commits more toward the start will have more bitmaps.
+ int minRegionEnd = 20000;
+ if (idxFromStart <= minRegionEnd)
+ return Math.min(idxFromStart - mustRegionEnd, minCommits);
+
+ // Commits more toward the end will have fewer.
+ int next = Math.min(idxFromStart - minRegionEnd, maxCommits);
+ return Math.max(next, minCommits);
+ }
+
+ PackWriterBitmapWalker newBitmapWalker() {
+ return new PackWriterBitmapWalker(
+ new ObjectWalk(reader), bitmapIndex, null);
+ }
+
+ static final class BitmapCommit extends ObjectId {
+ private final boolean reuseWalker;
+ private final int flags;
+
+ private BitmapCommit(
+ AnyObjectId objectId, boolean reuseWalker, int flags) {
+ super(objectId);
+ this.reuseWalker = reuseWalker;
+ this.flags = flags;
+ }
+
+ boolean isReuseWalker() {
+ return reuseWalker;
+ }
+
+ int getFlags() {
+ return flags;
+ }
+ }
+
+ private static final class WalkResult implements Iterable<RevCommit> {
+ private final Set<? extends ObjectId> peeledWant;
+ private final RevCommit[] commitsByOldest;
+ private final int commitStartPos;
+ private final List<BitmapBuilder> paths;
+ private final Iterable<BitmapCommit> reuse;
+
+ private WalkResult(Set<? extends ObjectId> peeledWant,
+ RevCommit[] commitsByOldest, int commitStartPos,
+ List<BitmapBuilder> paths, Iterable<BitmapCommit> reuse) {
+ this.peeledWant = peeledWant;
+ this.commitsByOldest = commitsByOldest;
+ this.commitStartPos = commitStartPos;
+ this.paths = paths;
+ this.reuse = reuse;
+ }
+
+ public Iterator<RevCommit> iterator() {
+ return new Iterator<RevCommit>() {
+ int pos = commitStartPos;
+
+ public boolean hasNext() {
+ return pos < commitsByOldest.length;
+ }
+
+ public RevCommit next() {
+ return commitsByOldest[pos++];
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
+ }
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java
new file mode 100644
index 0000000..ced1fe4
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java
@@ -0,0 +1,164 @@
+/*
+ * 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.storage.pack;
+
+import java.io.IOException;
+import java.util.Set;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.lib.BitmapIndex;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.lib.NullProgressMonitor;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.BitmapIndex.Bitmap;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.revwalk.ObjectWalk;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevFlag;
+import org.eclipse.jgit.revwalk.RevObject;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.revwalk.filter.RevFilter;
+
+/** Helper class for PackWriter to do ObjectWalks with pack index bitmaps. */
+final class PackWriterBitmapWalker {
+
+ private final ObjectWalk walker;
+
+ private final BitmapIndex bitmapIndex;
+
+ private final ProgressMonitor pm;
+
+ PackWriterBitmapWalker(
+ ObjectWalk walker, BitmapIndex bitmapIndex, ProgressMonitor pm) {
+ this.walker = walker;
+ this.bitmapIndex = bitmapIndex;
+ this.pm = (pm == null) ? NullProgressMonitor.INSTANCE : pm;
+ }
+
+ BitmapBuilder findObjects(Set<? extends ObjectId> start, BitmapBuilder seen)
+ throws MissingObjectException, IncorrectObjectTypeException,
+ IOException {
+ final BitmapBuilder bitmapResult = bitmapIndex.newBitmapBuilder();
+
+ for (ObjectId obj : start) {
+ Bitmap bitmap = bitmapIndex.getBitmap(obj);
+ if (bitmap != null)
+ bitmapResult.or(bitmap);
+ }
+
+ boolean marked = false;
+ for (ObjectId obj : start) {
+ if (!bitmapResult.contains(obj)) {
+ walker.markStart(walker.parseAny(obj));
+ marked = true;
+ }
+ }
+
+ if (marked) {
+ walker.setRevFilter(newRevFilter(seen, bitmapResult));
+
+ while (walker.next() != null) {
+ // Iterate through all of the commits. The BitmapRevFilter does
+ // the work.
+ pm.update(1);
+ }
+
+ RevObject ro;
+ while ((ro = walker.nextObject()) != null) {
+ bitmapResult.add(ro, ro.getType());
+ pm.update(1);
+ }
+ }
+
+ return bitmapResult;
+ }
+
+ void reset() {
+ walker.reset();
+ }
+
+ static RevFilter newRevFilter(
+ final BitmapBuilder seen, final BitmapBuilder bitmapResult) {
+ if (seen != null) {
+ return new BitmapRevFilter() {
+ protected boolean load(RevCommit cmit) {
+ if (seen.contains(cmit))
+ return false;
+ return bitmapResult.add(cmit, Constants.OBJ_COMMIT);
+ }
+ };
+ }
+ return new BitmapRevFilter() {
+ @Override
+ protected boolean load(RevCommit cmit) {
+ return bitmapResult.add(cmit, Constants.OBJ_COMMIT);
+ }
+ };
+ }
+
+ static abstract class BitmapRevFilter extends RevFilter {
+ protected abstract boolean load(RevCommit cmit);
+
+ @Override
+ public final boolean include(RevWalk walker, RevCommit cmit) {
+ if (load(cmit))
+ return true;
+ for (RevCommit p : cmit.getParents())
+ p.add(RevFlag.SEEN);
+ return false;
+ }
+
+ @Override
+ public final RevFilter clone() {
+ return this;
+ }
+
+ @Override
+ public final boolean requiresCommitBody() {
+ return false;
+ }
+ }
+}