summaryrefslogtreecommitdiffstatsabout
diff options
context:
space:
mode:
authorroberto2010-12-30 18:08:31 (EST)
committer Shawn O. Pearce2010-12-30 19:49:24 (EST)
commitb5f0a7d7ffaae707b0d7ecf582192f5014bdae92 (patch)
tree15b9a215c012c206f16c388235e6176786e4cf2c
parent4170913b1bcc7d63813da4fd83d19ea2ba646775 (diff)
downloadjgit-b5f0a7d7ffaae707b0d7ecf582192f5014bdae92.zip
jgit-b5f0a7d7ffaae707b0d7ecf582192f5014bdae92.tar.gz
jgit-b5f0a7d7ffaae707b0d7ecf582192f5014bdae92.tar.bz2
IndexPack: Use stack-based recursion for delta resolutionrefs/changes/72/2172/5
Replace 'method' with 'heap'-based recursion for resolving deltas. Git packfile delta-chain depth can exceed 50 levels in certain files (the packfile of the JGit project itself has >800 objects with chain-length >50). Using method-based recursion on such packfiles will quickly throw a StackOverflowError on VMs with constrained stack. Benefits: * packfile delta-resolution no longer limited by the maximum number of stack frames permitted on the current thread. * slight performance improvement (3% speed increase on the packfile of the JGit project) Change-Id: I1d9b3a8ba3c6d874d83cb93ebf171c6ab193e6cc Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/transport/IndexPack.java183
1 files changed, 131 insertions, 52 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/IndexPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/IndexPack.java
index bb9edc2..f8dc391 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/IndexPack.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/IndexPack.java
@@ -490,15 +490,15 @@ public class IndexPack {
}
private void resolveDeltas(final PackedObjectInfo oe) throws IOException {
- final int oldCRC = oe.getCRC();
- if (baseById.get(oe) != null || baseByPos.containsKey(oe.getOffset()))
- resolveDeltas(oe.getOffset(), oldCRC, Constants.OBJ_BAD, null, oe);
- }
+ UnresolvedDelta children = firstChildOf(oe);
+ if (children == null)
+ return;
+
+ DeltaVisit visit = new DeltaVisit();
+ visit.nextChild = children;
- private void resolveDeltas(final long pos, final int oldCRC, int type,
- byte[] data, PackedObjectInfo oe) throws IOException {
crc.reset();
- position(pos);
+ position(oe.getOffset());
int c = readFrom(Source.FILE);
final int typeCode = (c >> 4) & 7;
long sz = c & 15;
@@ -514,43 +514,76 @@ public class IndexPack {
case Constants.OBJ_TREE:
case Constants.OBJ_BLOB:
case Constants.OBJ_TAG:
- type = typeCode;
- data = inflateAndReturn(Source.FILE, sz);
- break;
- case Constants.OBJ_OFS_DELTA: {
- c = readFrom(Source.FILE) & 0xff;
- while ((c & 128) != 0)
- c = readFrom(Source.FILE) & 0xff;
- data = BinaryDelta.apply(data, inflateAndReturn(Source.FILE, sz));
+ visit.data = inflateAndReturn(Source.FILE, sz);
break;
- }
- case Constants.OBJ_REF_DELTA: {
- crc.update(buf, fill(Source.FILE, 20), 20);
- use(20);
- data = BinaryDelta.apply(data, inflateAndReturn(Source.FILE, sz));
- break;
- }
default:
- throw new IOException(MessageFormat.format(JGitText.get().unknownObjectType, typeCode));
+ throw new IOException(MessageFormat.format(
+ JGitText.get().unknownObjectType, typeCode));
}
- final int crc32 = (int) crc.getValue();
- if (oldCRC != crc32)
- throw new IOException(MessageFormat.format(JGitText.get().corruptionDetectedReReadingAt, pos));
- if (oe == null) {
+ if (oe.getCRC() != (int) crc.getValue()) {
+ throw new IOException(MessageFormat.format(
+ JGitText.get().corruptionDetectedReReadingAt,
+ oe.getOffset()));
+ }
+
+ resolveDeltas(visit.next(), typeCode);
+ }
+
+ private void resolveDeltas(DeltaVisit visit, final int type)
+ throws IOException {
+ do {
+ final long pos = visit.delta.position;
+ crc.reset();
+ position(pos);
+ int c = readFrom(Source.FILE);
+ final int typeCode = (c >> 4) & 7;
+ long sz = c & 15;
+ int shift = 4;
+ while ((c & 0x80) != 0) {
+ c = readFrom(Source.FILE);
+ sz += (c & 0x7f) << shift;
+ shift += 7;
+ }
+
+ switch (typeCode) {
+ case Constants.OBJ_OFS_DELTA: {
+ c = readFrom(Source.FILE) & 0xff;
+ while ((c & 128) != 0)
+ c = readFrom(Source.FILE) & 0xff;
+ visit.data = BinaryDelta.apply(visit.parent.data, inflateAndReturn(Source.FILE, sz));
+ break;
+ }
+ case Constants.OBJ_REF_DELTA: {
+ crc.update(buf, fill(Source.FILE, 20), 20);
+ use(20);
+ visit.data = BinaryDelta.apply(visit.parent.data, inflateAndReturn(Source.FILE, sz));
+ break;
+ }
+ default:
+ throw new IOException(MessageFormat.format(JGitText.get().unknownObjectType, typeCode));
+ }
+
+ final int crc32 = (int) crc.getValue();
+ if (visit.delta.crc != crc32)
+ throw new IOException(MessageFormat.format(JGitText.get().corruptionDetectedReReadingAt, pos));
+
objectDigest.update(Constants.encodedTypeString(type));
objectDigest.update((byte) ' ');
- objectDigest.update(Constants.encodeASCII(data.length));
+ objectDigest.update(Constants.encodeASCII(visit.data.length));
objectDigest.update((byte) 0);
- objectDigest.update(data);
+ objectDigest.update(visit.data);
tempObjectId.fromRaw(objectDigest.digest(), 0);
- verifySafeObject(tempObjectId, type, data);
+ verifySafeObject(tempObjectId, type, visit.data);
+
+ PackedObjectInfo oe;
oe = new PackedObjectInfo(pos, crc32, tempObjectId);
addObjectAndTrack(oe);
- }
- resolveChildDeltas(pos, type, data, oe);
+ visit.nextChild = firstChildOf(oe);
+ visit = visit.next();
+ } while (visit != null);
}
private UnresolvedDelta removeBaseById(final AnyObjectId id){
@@ -569,29 +602,34 @@ public class IndexPack {
return tail;
}
- private void resolveChildDeltas(final long pos, int type, byte[] data,
- PackedObjectInfo oe) throws IOException {
+ private UnresolvedDelta firstChildOf(PackedObjectInfo oe) {
UnresolvedDelta a = reverse(removeBaseById(oe));
- UnresolvedDelta b = reverse(baseByPos.remove(pos));
- while (a != null && b != null) {
- if (a.position < b.position) {
- resolveDeltas(a.position, a.crc, type, data, null);
+ UnresolvedDelta b = reverse(baseByPos.remove(oe.getOffset()));
+
+ if (a == null)
+ return b;
+ if (b == null)
+ return a;
+
+ UnresolvedDelta first = null;
+ UnresolvedDelta last = null;
+ while (a != null || b != null) {
+ UnresolvedDelta curr;
+ if (b == null || (a != null && a.position < b.position)) {
+ curr = a;
a = a.next;
} else {
- resolveDeltas(b.position, b.crc, type, data, null);
+ curr = b;
b = b.next;
}
+ if (last != null)
+ last.next = curr;
+ else
+ first = curr;
+ last = curr;
+ curr.next = null;
}
- resolveChildDeltaChain(type, data, a);
- resolveChildDeltaChain(type, data, b);
- }
-
- private void resolveChildDeltaChain(final int type, final byte[] data,
- UnresolvedDelta a) throws IOException {
- while (a != null) {
- resolveDeltas(a.position, a.crc, type, data, null);
- a = a.next;
- }
+ return first;
}
private void fixThinPack(final ProgressMonitor progress) throws IOException {
@@ -617,18 +655,22 @@ public class IndexPack {
missing.add(baseId);
continue;
}
- final byte[] data = ldr.getCachedBytes(Integer.MAX_VALUE);
+
+ final DeltaVisit visit = new DeltaVisit();
+ visit.data = ldr.getCachedBytes(Integer.MAX_VALUE);
final int typeCode = ldr.getType();
final PackedObjectInfo oe;
crc.reset();
packOut.seek(end);
- writeWhole(def, typeCode, data);
+ writeWhole(def, typeCode, visit.data);
oe = new PackedObjectInfo(end, (int) crc.getValue(), baseId);
entries[entryCount++] = oe;
end = packOut.getFilePointer();
- resolveChildDeltas(oe.getOffset(), typeCode, data, oe);
+ visit.nextChild = firstChildOf(oe);
+ resolveDeltas(visit.next(), typeCode);
+
if (progress.isCancelled())
throw new IOException(JGitText.get().downloadCancelledDuringIndexing);
}
@@ -1076,6 +1118,43 @@ public class IndexPack {
}
}
+ private static class DeltaVisit {
+ final UnresolvedDelta delta;
+
+ byte[] data;
+
+ DeltaVisit parent;
+
+ UnresolvedDelta nextChild;
+
+ DeltaVisit() {
+ this.delta = null; // At the root of the stack we have a base.
+ }
+
+ DeltaVisit(DeltaVisit parent) {
+ this.parent = parent;
+ this.delta = parent.nextChild;
+ parent.nextChild = delta.next;
+ }
+
+ DeltaVisit next() {
+ // If our parent has no more children, discard it.
+ if (parent != null && parent.nextChild == null) {
+ parent.data = null;
+ parent = parent.parent;
+ }
+
+ if (nextChild != null)
+ return new DeltaVisit(this);
+
+ // If we have no child ourselves, our parent must (if it exists),
+ // due to the discard rule above. With no parent, we are done.
+ if (parent != null)
+ return new DeltaVisit(parent);
+ return null;
+ }
+ }
+
/**
* Rename the pack to it's final name and location and open it.
* <p>