2 * Copyright (C) 2008, Robin Rosenberg <robin.rosenberg@dewire.com>
3 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
7 * Redistribution and use in source and binary forms, with or
8 * without modification, are permitted provided that the following
11 * - Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
14 * - Redistributions in binary form must reproduce the above
15 * copyright notice, this list of conditions and the following
16 * disclaimer in the documentation and/or other materials provided
17 * with the distribution.
19 * - Neither the name of the Git Development Community nor the
20 * names of its contributors may be used to endorse or promote
21 * products derived from this software without specific prior
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
25 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
26 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
27 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
29 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
31 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
34 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
36 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 package org
.spearce
.jgit
.transport
;
41 import java
.io
.BufferedOutputStream
;
42 import java
.io
.EOFException
;
44 import java
.io
.FileOutputStream
;
45 import java
.io
.IOException
;
46 import java
.io
.InputStream
;
47 import java
.io
.RandomAccessFile
;
48 import java
.security
.MessageDigest
;
49 import java
.util
.ArrayList
;
50 import java
.util
.Arrays
;
51 import java
.util
.HashMap
;
52 import java
.util
.zip
.DataFormatException
;
53 import java
.util
.zip
.Deflater
;
54 import java
.util
.zip
.Inflater
;
56 import org
.spearce
.jgit
.errors
.CorruptObjectException
;
57 import org
.spearce
.jgit
.lib
.AnyObjectId
;
58 import org
.spearce
.jgit
.lib
.BinaryDelta
;
59 import org
.spearce
.jgit
.lib
.Constants
;
60 import org
.spearce
.jgit
.lib
.InflaterCache
;
61 import org
.spearce
.jgit
.lib
.MutableObjectId
;
62 import org
.spearce
.jgit
.lib
.ObjectId
;
63 import org
.spearce
.jgit
.lib
.ObjectIdMap
;
64 import org
.spearce
.jgit
.lib
.ObjectLoader
;
65 import org
.spearce
.jgit
.lib
.ProgressMonitor
;
66 import org
.spearce
.jgit
.lib
.Repository
;
67 import org
.spearce
.jgit
.util
.NB
;
69 /** Indexes Git pack files for local use. */
70 public class IndexPack
{
71 /** Progress message when reading raw data from the pack. */
72 public static final String PROGRESS_DOWNLOAD
= "Receiving objects";
74 /** Progress message when computing names of delta compressed objects. */
75 public static final String PROGRESS_RESOLVE_DELTA
= "Resolving deltas";
77 private static final byte[] SIGNATURE
= { 'P', 'A', 'C', 'K' };
79 private static final int BUFFER_SIZE
= 2048;
82 * Create an index pack instance to load a new pack into a repository.
84 * The received pack data and generated index will be saved to temporary
85 * files within the repository's <code>objects</code> directory. To use
86 * the data contained within them call {@link #renameAndOpenPack()} once the
87 * indexing is complete.
90 * the repository that will receive the new pack.
92 * stream to read the pack data from.
93 * @return a new index pack instance.
95 * a temporary file could not be created.
97 public static IndexPack
create(final Repository db
, final InputStream is
)
99 final String suffix
= ".pack";
100 final File objdir
= db
.getObjectsDirectory();
101 final File tmp
= File
.createTempFile("incoming_", suffix
, objdir
);
102 final String n
= tmp
.getName();
105 base
= new File(objdir
, n
.substring(0, n
.length() - suffix
.length()));
106 return new IndexPack(db
, is
, base
);
109 private final Repository repo
;
111 private Inflater inflater
;
113 private final MessageDigest objectDigest
;
115 private final MutableObjectId tempObjectId
;
117 private InputStream in
;
127 private boolean fixThin
;
129 private final File dstPack
;
131 private final File dstIdx
;
133 private long objectCount
;
135 private ObjectEntry
[] entries
;
137 private int deltaCount
;
139 private int entryCount
;
141 private ObjectIdMap
<ArrayList
<UnresolvedDelta
>> baseById
;
143 private HashMap
<Long
, ArrayList
<UnresolvedDelta
>> baseByPos
;
145 private byte[] objectData
;
147 private MessageDigest packDigest
;
149 private RandomAccessFile packOut
;
151 private byte[] packcsum
;
154 * Create a new pack indexer utility.
159 * @throws IOException
160 * the output packfile could not be created.
162 public IndexPack(final Repository db
, final InputStream src
,
163 final File dstBase
) throws IOException
{
166 inflater
= InflaterCache
.get();
167 buf
= new byte[BUFFER_SIZE
];
168 objectData
= new byte[BUFFER_SIZE
];
169 objectDigest
= Constants
.newMessageDigest();
170 tempObjectId
= new MutableObjectId();
171 packDigest
= Constants
.newMessageDigest();
173 if (dstBase
!= null) {
174 final File dir
= dstBase
.getParentFile();
175 final String nam
= dstBase
.getName();
176 dstPack
= new File(dir
, nam
+ ".pack");
177 dstIdx
= new File(dir
, nam
+ ".idx");
178 packOut
= new RandomAccessFile(dstPack
, "rw");
179 packOut
.setLength(0);
187 * Configure this index pack instance to make a thin pack complete.
189 * Thin packs are sometimes used during network transfers to allow a delta
190 * to be sent without a base object. Such packs are not permitted on disk.
191 * They can be fixed by copying the base object onto the end of the pack.
194 * true to enable fixing a thin pack.
196 public void setFixThin(final boolean fix
) {
201 * Consume data from the input stream until the packfile is indexed.
206 * @throws IOException
208 public void index(final ProgressMonitor progress
) throws IOException
{
209 progress
.start(2 /* tasks */);
214 entries
= new ObjectEntry
[(int) objectCount
];
215 baseById
= new ObjectIdMap
<ArrayList
<UnresolvedDelta
>>();
216 baseByPos
= new HashMap
<Long
, ArrayList
<UnresolvedDelta
>>();
218 progress
.beginTask(PROGRESS_DOWNLOAD
, (int) objectCount
);
219 for (int done
= 0; done
< objectCount
; done
++) {
222 if (progress
.isCancelled())
223 throw new IOException("Download cancelled");
228 if (deltaCount
> 0) {
230 throw new IOException("need packOut");
231 resolveDeltas(progress
);
232 if (entryCount
< objectCount
) {
234 throw new IOException("pack has "
235 + (objectCount
- entryCount
)
236 + " unresolved deltas");
238 fixThinPack(progress
);
250 final Inflater inf
= inflater
;
252 InflaterCache
.release(inf
);
260 dstPack
.setReadOnly();
262 dstIdx
.setReadOnly();
263 } catch (IOException err
) {
272 private void resolveDeltas(final ProgressMonitor progress
)
274 progress
.beginTask(PROGRESS_RESOLVE_DELTA
, deltaCount
);
275 final int last
= entryCount
;
276 for (int i
= 0; i
< last
; i
++) {
277 final int before
= entryCount
;
278 resolveDeltas(entries
[i
]);
279 progress
.update(entryCount
- before
);
280 if (progress
.isCancelled())
281 throw new IOException("Download cancelled during indexing");
286 private void resolveDeltas(final ObjectEntry oe
) throws IOException
{
287 if (baseById
.containsKey(oe
) || baseByPos
.containsKey(new Long(oe
.pos
)))
288 resolveDeltas(oe
.pos
, Constants
.OBJ_BAD
, null, oe
);
291 private void resolveDeltas(final long pos
, int type
, byte[] data
,
292 ObjectEntry oe
) throws IOException
{
294 int c
= readFromFile();
295 final int typeCode
= (c
>> 4) & 7;
298 while ((c
& 0x80) != 0) {
300 sz
+= (c
& 0x7f) << shift
;
305 case Constants
.OBJ_COMMIT
:
306 case Constants
.OBJ_TREE
:
307 case Constants
.OBJ_BLOB
:
308 case Constants
.OBJ_TAG
:
310 data
= inflateFromFile((int) sz
);
312 case Constants
.OBJ_OFS_DELTA
: {
313 c
= readFromInput() & 0xff;
314 while ((c
& 128) != 0)
315 c
= readFromInput() & 0xff;
316 data
= BinaryDelta
.apply(data
, inflateFromFile((int) sz
));
319 case Constants
.OBJ_REF_DELTA
: {
322 data
= BinaryDelta
.apply(data
, inflateFromFile((int) sz
));
326 throw new IOException("Unknown object type " + typeCode
+ ".");
330 objectDigest
.update(Constants
.encodedTypeString(type
));
331 objectDigest
.update((byte) ' ');
332 objectDigest
.update(Constants
.encodeASCII(data
.length
));
333 objectDigest
.update((byte) 0);
334 objectDigest
.update(data
);
335 tempObjectId
.fromRaw(objectDigest
.digest(), 0);
336 oe
= new ObjectEntry(pos
, tempObjectId
);
337 entries
[entryCount
++] = oe
;
340 resolveChildDeltas(pos
, type
, data
, oe
);
343 private void resolveChildDeltas(final long pos
, int type
, byte[] data
,
344 ObjectEntry oe
) throws IOException
{
345 final ArrayList
<UnresolvedDelta
> a
= baseById
.remove(oe
);
346 final ArrayList
<UnresolvedDelta
> b
= baseByPos
.remove(new Long(pos
));
348 if (a
!= null && b
!= null) {
349 while (ai
< a
.size() && bi
< b
.size()) {
350 final UnresolvedDelta ad
= a
.get(ai
);
351 final UnresolvedDelta bd
= b
.get(bi
);
352 if (ad
.position
< bd
.position
) {
353 resolveDeltas(ad
.position
, type
, data
, null);
356 resolveDeltas(bd
.position
, type
, data
, null);
362 while (ai
< a
.size())
363 resolveDeltas(a
.get(ai
++).position
, type
, data
, null);
365 while (bi
< b
.size())
366 resolveDeltas(b
.get(bi
++).position
, type
, data
, null);
369 private void fixThinPack(final ProgressMonitor progress
) throws IOException
{
372 final Deflater def
= new Deflater(Deflater
.DEFAULT_COMPRESSION
, false);
373 long end
= packOut
.length() - 20;
374 while (!baseById
.isEmpty()) {
375 final ObjectId baseId
= baseById
.keySet().iterator().next();
376 final ObjectLoader ldr
= repo
.openObject(baseId
);
377 final byte[] data
= ldr
.getBytes();
378 final int typeCode
= ldr
.getType();
379 final ObjectEntry oe
;
381 oe
= new ObjectEntry(end
, baseId
);
382 entries
[entryCount
++] = oe
;
384 writeWhole(def
, typeCode
, data
);
385 end
= packOut
.getFilePointer();
387 resolveChildDeltas(oe
.pos
, typeCode
, data
, oe
);
388 if (progress
.isCancelled())
389 throw new IOException("Download cancelled during indexing");
396 private void writeWhole(final Deflater def
, final int typeCode
,
397 final byte[] data
) throws IOException
{
398 int sz
= data
.length
;
400 buf
[hdrlen
++] = (byte) ((typeCode
<< 4) | sz
& 15);
403 buf
[hdrlen
- 1] |= 0x80;
404 buf
[hdrlen
++] = (byte) (sz
& 0x7f);
407 packOut
.write(buf
, 0, hdrlen
);
411 while (!def
.finished())
412 packOut
.write(buf
, 0, def
.deflate(buf
));
415 private void fixHeaderFooter() throws IOException
{
417 if (packOut
.read(buf
, 0, 12) != 12)
418 throw new IOException("Cannot re-read pack header to fix count");
419 NB
.encodeInt32(buf
, 8, entryCount
);
421 packOut
.write(buf
, 0, 12);
424 packDigest
.update(buf
, 0, 12);
426 final int n
= packOut
.read(buf
);
429 packDigest
.update(buf
, 0, n
);
432 packcsum
= packDigest
.digest();
433 packOut
.write(packcsum
);
436 private void growEntries() {
437 final ObjectEntry
[] ne
;
439 ne
= new ObjectEntry
[(int) objectCount
+ baseById
.size()];
440 System
.arraycopy(entries
, 0, ne
, 0, entryCount
);
444 private void writeIdx() throws IOException
{
445 Arrays
.sort(entries
, 0, entryCount
);
446 final int[] fanout
= new int[256];
447 for (int i
= 0; i
< entryCount
; i
++)
448 fanout
[entries
[i
].getFirstByte() & 0xff]++;
449 for (int i
= 1; i
< 256; i
++)
450 fanout
[i
] += fanout
[i
- 1];
452 final BufferedOutputStream os
= new BufferedOutputStream(
453 new FileOutputStream(dstIdx
), BUFFER_SIZE
);
455 final byte[] rawoe
= new byte[4 + Constants
.OBJECT_ID_LENGTH
];
456 final MessageDigest d
= Constants
.newMessageDigest();
457 for (int i
= 0; i
< 256; i
++) {
458 NB
.encodeInt32(rawoe
, 0, fanout
[i
]);
459 os
.write(rawoe
, 0, 4);
460 d
.update(rawoe
, 0, 4);
462 for (int i
= 0; i
< entryCount
; i
++) {
463 final ObjectEntry oe
= entries
[i
];
464 if (oe
.pos
>>> 1 > Integer
.MAX_VALUE
)
465 throw new IOException("Pack too large for index version 1");
466 NB
.encodeInt32(rawoe
, 0, (int) oe
.pos
);
467 oe
.copyRawTo(rawoe
, 4);
473 os
.write(d
.digest());
479 private void readPackHeader() throws IOException
{
480 final int hdrln
= SIGNATURE
.length
+ 4 + 4;
481 final int p
= fillFromInput(hdrln
);
482 for (int k
= 0; k
< SIGNATURE
.length
; k
++)
483 if (buf
[p
+ k
] != SIGNATURE
[k
])
484 throw new IOException("Not a PACK file.");
486 final long vers
= NB
.decodeUInt32(buf
, p
+ 4);
487 if (vers
!= 2 && vers
!= 3)
488 throw new IOException("Unsupported pack version " + vers
+ ".");
489 objectCount
= NB
.decodeUInt32(buf
, p
+ 8);
493 private void readPackFooter() throws IOException
{
495 final byte[] cmpcsum
= packDigest
.digest();
496 final int c
= fillFromInput(20);
497 packcsum
= new byte[20];
498 System
.arraycopy(buf
, c
, packcsum
, 0, 20);
501 packOut
.write(packcsum
);
503 if (!Arrays
.equals(cmpcsum
, packcsum
))
504 throw new CorruptObjectException("Packfile checksum incorrect.");
507 // Cleanup all resources associated with our input parsing.
508 private void endInput() {
513 // Read one entire object or delta from the input.
514 private void indexOneObject() throws IOException
{
515 final long pos
= position();
517 int c
= readFromInput();
518 final int typeCode
= (c
>> 4) & 7;
521 while ((c
& 0x80) != 0) {
523 sz
+= (c
& 0x7f) << shift
;
528 case Constants
.OBJ_COMMIT
:
529 case Constants
.OBJ_TREE
:
530 case Constants
.OBJ_BLOB
:
531 case Constants
.OBJ_TAG
:
532 whole(typeCode
, pos
, sz
);
534 case Constants
.OBJ_OFS_DELTA
: {
535 c
= readFromInput() & 0xff;
537 while ((c
& 128) != 0) {
539 c
= readFromInput() & 0xff;
543 final Long base
= new Long(pos
- ofs
);
544 ArrayList
<UnresolvedDelta
> r
= baseByPos
.get(base
);
546 r
= new ArrayList
<UnresolvedDelta
>(8);
547 baseByPos
.put(base
, r
);
549 r
.add(new UnresolvedDelta(pos
));
551 inflateFromInput(false);
554 case Constants
.OBJ_REF_DELTA
: {
555 c
= fillFromInput(20);
556 final byte[] ref
= new byte[20];
557 System
.arraycopy(buf
, c
, ref
, 0, 20);
559 final ObjectId base
= ObjectId
.fromRaw(ref
);
560 ArrayList
<UnresolvedDelta
> r
= baseById
.get(base
);
562 r
= new ArrayList
<UnresolvedDelta
>(8);
563 baseById
.put(base
, r
);
565 r
.add(new UnresolvedDelta(pos
));
567 inflateFromInput(false);
571 throw new IOException("Unknown object type " + typeCode
+ ".");
575 private void whole(final int type
, final long pos
, final long sz
)
577 objectDigest
.update(Constants
.encodedTypeString(type
));
578 objectDigest
.update((byte) ' ');
579 objectDigest
.update(Constants
.encodeASCII(sz
));
580 objectDigest
.update((byte) 0);
581 inflateFromInput(true);
582 tempObjectId
.fromRaw(objectDigest
.digest(), 0);
583 entries
[entryCount
++] = new ObjectEntry(pos
, tempObjectId
);
586 // Current position of {@link #bOffset} within the entire file.
587 private long position() {
588 return bBase
+ bOffset
;
591 private void position(final long pos
) throws IOException
{
598 // Consume exactly one byte from the buffer and return it.
599 private int readFromInput() throws IOException
{
603 return buf
[bOffset
++] & 0xff;
606 // Consume exactly one byte from the buffer and return it.
607 private int readFromFile() throws IOException
{
611 return buf
[bOffset
++] & 0xff;
614 // Consume cnt bytes from the buffer.
615 private void use(final int cnt
) {
620 // Ensure at least need bytes are available in in {@link #buf}.
621 private int fillFromInput(final int need
) throws IOException
{
622 while (bAvail
< need
) {
623 int next
= bOffset
+ bAvail
;
624 int free
= buf
.length
- next
;
625 if (free
+ bAvail
< need
) {
628 free
= buf
.length
- next
;
630 next
= in
.read(buf
, next
, free
);
632 throw new EOFException("Packfile is truncated.");
638 // Ensure at least need bytes are available in in {@link #buf}.
639 private int fillFromFile() throws IOException
{
641 final int next
= packOut
.read(buf
, 0, buf
.length
);
643 throw new EOFException("Packfile is truncated.");
650 // Store consumed bytes in {@link #buf} up to {@link #bOffset}.
651 private void sync() throws IOException
{
652 packDigest
.update(buf
, 0, bOffset
);
654 packOut
.write(buf
, 0, bOffset
);
656 System
.arraycopy(buf
, bOffset
, buf
, 0, bAvail
);
661 private void inflateFromInput(final boolean digest
) throws IOException
{
662 final Inflater inf
= inflater
;
664 final byte[] dst
= objectData
;
666 while (!inf
.finished()) {
667 if (inf
.needsInput()) {
668 final int p
= fillFromInput(1);
669 inf
.setInput(buf
, p
, bAvail
);
673 int free
= dst
.length
- n
;
676 objectDigest
.update(dst
, 0, n
);
681 n
+= inf
.inflate(dst
, n
, free
);
684 objectDigest
.update(dst
, 0, n
);
685 use(-inf
.getRemaining());
686 } catch (DataFormatException dfe
) {
693 private byte[] inflateFromFile(final int sz
) throws IOException
{
694 final Inflater inf
= inflater
;
696 final byte[] dst
= new byte[sz
];
698 while (!inf
.finished()) {
699 if (inf
.needsInput()) {
700 final int p
= fillFromFile();
701 inf
.setInput(buf
, p
, bAvail
);
704 n
+= inf
.inflate(dst
, n
, sz
- n
);
706 use(-inf
.getRemaining());
708 } catch (DataFormatException dfe
) {
715 private static CorruptObjectException
corrupt(final DataFormatException dfe
) {
716 return new CorruptObjectException("Packfile corruption detected: "
720 private static class ObjectEntry
extends ObjectId
{
723 ObjectEntry(final long headerOffset
, final AnyObjectId id
) {
729 private static class UnresolvedDelta
{
732 UnresolvedDelta(final long headerOffset
) {
733 position
= headerOffset
;
738 * Rename the pack to it's final name and location and open it.
740 * If the call completes successfully the repository this IndexPack instance
741 * was created with will have the objects in the pack available for reading
742 * and use, without needing to scan for packs.
744 * @throws IOException
745 * The pack could not be inserted into the repository's objects
746 * directory. The pack no longer exists on disk, as it was
747 * removed prior to throwing the exception to the caller.
749 public void renameAndOpenPack() throws IOException
{
750 final MessageDigest d
= Constants
.newMessageDigest();
751 final byte[] oeBytes
= new byte[Constants
.OBJECT_ID_LENGTH
];
752 for (int i
= 0; i
< entryCount
; i
++) {
753 final ObjectEntry oe
= entries
[i
];
754 oe
.copyRawTo(oeBytes
, 0);
758 final ObjectId name
= ObjectId
.fromRaw(d
.digest());
759 final File packDir
= new File(repo
.getObjectsDirectory(), "pack");
760 final File finalPack
= new File(packDir
, "pack-" + name
+ ".pack");
761 final File finalIdx
= new File(packDir
, "pack-" + name
+ ".idx");
763 if (finalPack
.exists()) {
764 // If the pack is already present we should never replace it.
766 cleanupTemporaryFiles();
770 if (!dstPack
.renameTo(finalPack
)) {
771 cleanupTemporaryFiles();
772 throw new IOException("Cannot move pack to " + finalPack
);
775 if (!dstIdx
.renameTo(finalIdx
)) {
776 cleanupTemporaryFiles();
777 if (!finalPack
.delete())
778 finalPack
.deleteOnExit();
779 throw new IOException("Cannot move index to " + finalIdx
);
783 repo
.openPack(finalPack
, finalIdx
);
784 } catch (IOException err
) {
791 private void cleanupTemporaryFiles() {
792 if (!dstIdx
.delete())
793 dstIdx
.deleteOnExit();
794 if (!dstPack
.delete())
795 dstPack
.deleteOnExit();