From dafcb8f6db82b899c917832768f1c240d273190c Mon Sep 17 00:00:00 2001 From: Colby Ranger Date: Mon, 6 Aug 2012 11:09:53 -0700 Subject: Support creating pack bitmap indexes in PackWriter. 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 --- .../org/eclipse/jgit/internal/JGitText.properties | 4 + .../src/org/eclipse/jgit/internal/JGitText.java | 4 + .../src/org/eclipse/jgit/revwalk/RevFlag.java | 10 + .../org/eclipse/jgit/storage/dfs/DfsReader.java | 12 + .../eclipse/jgit/storage/file/LocalCachedPack.java | 7 + .../jgit/storage/file/PackBitmapIndexRemapper.java | 197 +++++++++++ .../jgit/storage/file/PackBitmapIndexWriterV1.java | 12 +- .../eclipse/jgit/storage/file/PackIndexWriter.java | 44 ++- .../eclipse/jgit/storage/file/WindowCursor.java | 12 + .../eclipse/jgit/storage/pack/ObjectReuseAsIs.java | 19 ++ .../org/eclipse/jgit/storage/pack/PackConfig.java | 38 +++ .../org/eclipse/jgit/storage/pack/PackWriter.java | 208 +++++++++++- .../storage/pack/PackWriterBitmapPreparer.java | 373 +++++++++++++++++++++ .../jgit/storage/pack/PackWriterBitmapWalker.java | 164 +++++++++ 14 files changed, 1078 insertions(+), 26 deletions(-) create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java 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 28e0a4cc67..18f33147ce 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 388e0d325f..7a1efe89df 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 85982c7a0a..c767c033e5 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. + *

+ * 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. + *

+ * 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 455f1bbd99..6d131abe19 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 getCachedPacksAndUpdate( + BitmapBuilder needBitmap) throws IOException { + for (DfsPackFile pack : db.getPacks()) { + PackBitmapIndex bitmapIndex = pack.getPackBitmapIndex(this); + if (needBitmap.removeAllOrNone(bitmapIndex)) + return Collections. singletonList( + new DfsCachedPack(pack)); + } + return Collections.emptyList(); + } + @Override public Collection 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 82503b6d1e..c0e47eea12 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 packs) { + odb = null; + tips = null; + packNames = null; + this.packs = packs.toArray(new PackFile[packs.size()]); + } + @Override public Set 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 0000000000..1bc90c6df4 --- /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 { + + private final BasePackBitmapIndex oldPackIndex; + private final PackBitmapIndex newPackIndex; + private final ObjectIdOwnerMap 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(); + 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 iterator() { + if (oldPackIndex == null) + return Collections. emptyList().iterator(); + + final Iterator it = oldPackIndex.getBitmaps().iterator(); + return new Iterator() { + 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 8636eb3151..8ea4d15e5a 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 b78c5ae267..e1c2a3eba4 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 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. + *

+ * 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. + *

+ * 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 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 2af48edccb..d9906dec9e 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 getCachedPacksAndUpdate( + BitmapBuilder needBitmap) throws IOException { + for (PackFile pack : db.getPacks()) { + PackBitmapIndex index = pack.getBitmapIndex(); + if (needBitmap.removeAllOrNone(index)) + return Collections. singletonList( + new LocalCachedPack(Collections.singletonList(pack))); + } + return Collections.emptyList(); + } + @Override public Collection 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 ed0294ed30..8816ca495b 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. + *

+ * 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 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 58ee985ff5..fdff23085b 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; } /** @@ -614,6 +624,33 @@ public class PackConfig { indexVersion = version; } + /** + * 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. * @@ -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 77ebaf618b..470ffd343c 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 edgeObjects = new BlockList(); + // Objects the client is known to have already. + private BitmapBuilder haveObjects; + private List cachedPacks = new ArrayList(2); private Set 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 unshallowObjects; + private PackBitmapIndexBuilder writeBitmaps; + /** * Create writer for specified repository. *

@@ -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} @@ -791,6 +818,25 @@ public class PackWriter { return ObjectId.fromRaw(md.digest()); } + /** + * Returns the index format version that will be written. + *

+ * 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 objs : objectsLists) + indexVersion = Math.max(indexVersion, + PackIndexWriter.oldestPossibleFormat(objs)); + } + return indexVersion; + } + /** * Create an index file to match the pack file just written. *

@@ -810,14 +856,34 @@ public class PackWriter { throw new IOException(JGitText.get().cachedPacksPreventsIndexCreation); long writeStart = System.currentTimeMillis(); - final List 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. + *

+ * 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(want)); stats.uninterestingObjects = Collections.unmodifiableSet(new HashSet(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 all = new ArrayList(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 want, + Set 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 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 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 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 0000000000..11b2eccee0 --- /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 BUILDER_BY_CARDINALITY_DSC = + new Comparator() { + 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 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 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 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 selections = new BlockList( + 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> running = new ArrayList< + List>(); + + // 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> matches = new ArrayList< + List>(); + for (List list : running) { + BitmapCommit last = list.get(list.size() - 1); + if (fullBitmap.contains(last)) + matches.add(list); + } + + List match; + if (matches.isEmpty()) { + match = new ArrayList(); + running.add(match); + } else { + match = matches.get(0); + // Append to longest + for (List list : matches) { + if (list.size() > match.size()) + match = list; + } + } + match.add(new BitmapCommit(c, !match.isEmpty(), flags)); + writeBitmaps.addBitmap(c, fullBitmap, 0); + } + + for (List 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 reuse = new ArrayList(); + 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 paths = new ArrayList(want.size()); + Set peeledWant = new HashSet(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 distinctPaths = new ArrayList(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 { + private final Set peeledWant; + private final RevCommit[] commitsByOldest; + private final int commitStartPos; + private final List paths; + private final Iterable reuse; + + private WalkResult(Set peeledWant, + RevCommit[] commitsByOldest, int commitStartPos, + List paths, Iterable reuse) { + this.peeledWant = peeledWant; + this.commitsByOldest = commitsByOldest; + this.commitStartPos = commitStartPos; + this.paths = paths; + this.reuse = reuse; + } + + public Iterator iterator() { + return new Iterator() { + 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 0000000000..ced1fe4b82 --- /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 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; + } + } +} -- cgit v1.2.3