From 8ac65d33ed7a94f77cb066271669feebf9b882fc Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Fri, 18 Mar 2011 10:23:21 -0700 Subject: [PATCH] PackWriter: Fix the way delta chain cycles are prevented Take a very simple approach to avoiding delta chains during object reuse: objects are now always selected from the oldest pack that contains them. This prevents cycles because a pack must not have a cycle in the delta chain. If both objects A and B are chosen out of the same source pack then there cannot be an A->B->A cycle. The oldest pack is also the most likely to have the smallest deltas. Its the biggest pack in the system and probably came from the clone (or last GC) of this repository, where all objects were previously considered and packed tightly together. If an object appears again (for example due to a revert and a push into this repository) the newer copy of won't be nearly as small as the older delta version of it, even if the newer one is also itself a delta. ObjectDirectory already enumerates objects during selection in this newest->oldest order, so it already is supplying these assumptions to PackWriter. Taking advantage of this can speed up selection by a tiny amount by avoiding some tests, but can also help to prevent a cycle needing to be broken on the fly during writing. The previous cycle breaking logic wasn't fully correct either. If a different delta base was chosen, the new delta base might not have been written into the output pack before the current object, forcing the use of REF_DELTA when OFS_DELTA is always smaller. This logic has now been reworked to always re-check the delta base and ensure it gets written before the current object. If a cycle occurs, it gets broken the same way as before, by disabling delta reuse and finding an alternative form of the object, which may require inflating/deflating in whole format. Change-Id: I9953ab8be54ceb8b588e1280d6f7edd688887747 Signed-off-by: Shawn O. Pearce --- .../eclipse/jgit/storage/pack/PackWriter.java | 107 ++++++++---------- 1 file changed, 49 insertions(+), 58 deletions(-) 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 c388ee17d4..8a912aeb6b 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 @@ -1085,17 +1085,35 @@ public class PackWriter { } void writeObject(PackOutputStream out, ObjectToPack otp) throws IOException { - if (otp.isWritten()) - return; // We shouldn't be here. + if (!otp.isWritten()) + writeObjectImpl(out, otp); + } + private void writeObjectImpl(PackOutputStream out, ObjectToPack otp) + throws IOException { + if (otp.wantWrite()) { + // A cycle exists in this delta chain. This should only occur if a + // selected object representation disappeared during writing + // (for example due to a concurrent repack) and a different base + // was chosen, forcing a cycle. Select something other than a + // delta, and write this object. + // + reuseDeltas = false; + otp.clearDeltaBase(); + otp.clearReuseAsIs(); + reuseSupport.selectObjectRepresentation(this, + NullProgressMonitor.INSTANCE, + Collections.singleton(otp)); + } otp.markWantWrite(); - if (otp.isDeltaRepresentation()) - writeBaseFirst(out, otp); - - out.resetCRC32(); - otp.setOffset(out.length()); while (otp.isReuseAsIs()) { + writeBase(out, otp.getDeltaBase()); + if (otp.isWritten()) + return; // Delta chain cycle caused this to write already. + + out.resetCRC32(); + otp.setOffset(out.length()); try { reuseSupport.copyObjectAsIs(out, otp, reuseValidate); out.endObject(); @@ -1108,7 +1126,12 @@ public class PackWriter { return; } catch (StoredObjectRepresentationNotAvailableException gone) { if (otp.getOffset() == out.length()) { - redoSearchForReuse(otp); + otp.setOffset(0); + otp.clearDeltaBase(); + otp.clearReuseAsIs(); + reuseSupport.selectObjectRepresentation(this, + NullProgressMonitor.INSTANCE, + Collections.singleton(otp)); continue; } else { // Object writing already started, we cannot recover. @@ -1131,39 +1154,10 @@ public class PackWriter { otp.setCRC(out.getCRC32()); } - private void writeBaseFirst(PackOutputStream out, final ObjectToPack otp) + private void writeBase(PackOutputStream out, ObjectToPack baseInPack) throws IOException { - ObjectToPack baseInPack = otp.getDeltaBase(); - if (baseInPack != null) { - if (!baseInPack.isWritten()) { - if (baseInPack.wantWrite()) { - // There is a cycle. Our caller is trying to write the - // object we want as a base, and called us. Turn off - // delta reuse so we can find another form. - // - reuseDeltas = false; - redoSearchForReuse(otp); - reuseDeltas = true; - } else { - writeObject(out, baseInPack); - } - } - } else if (!thin) { - // This should never occur, the base isn't in the pack and - // the pack isn't allowed to reference base outside objects. - // Write the object as a whole form, even if that is slow. - // - otp.clearDeltaBase(); - otp.clearReuseAsIs(); - } - } - - private void redoSearchForReuse(final ObjectToPack otp) throws IOException, - MissingObjectException { - otp.clearDeltaBase(); - otp.clearReuseAsIs(); - reuseSupport.selectObjectRepresentation(this, - NullProgressMonitor.INSTANCE, Collections.singleton(otp)); + if (baseInPack != null && !baseInPack.isWritten()) + writeObjectImpl(out, baseInPack); } private void writeWholeObjectDeflate(PackOutputStream out, @@ -1171,6 +1165,8 @@ public class PackWriter { final Deflater deflater = deflater(); final ObjectLoader ldr = reader.open(otp, otp.getType()); + out.resetCRC32(); + otp.setOffset(out.length()); out.writeHeader(otp, ldr.getSize()); deflater.reset(); @@ -1181,6 +1177,11 @@ public class PackWriter { private void writeDeltaObjectDeflate(PackOutputStream out, final ObjectToPack otp) throws IOException { + writeBase(out, otp.getDeltaBase()); + + out.resetCRC32(); + otp.setOffset(out.length()); + DeltaCache.Ref ref = otp.popCachedDelta(); if (ref != null) { byte[] zbuf = ref.get(); @@ -1551,38 +1552,28 @@ public class PackWriter { } } - int nWeight; - if (otp.isReuseAsIs()) { - // We've already chosen to reuse a packed form, if next - // cannot beat that break out early. - // - if (PACK_WHOLE < nFmt) - return; // next isn't packed - else if (PACK_DELTA < nFmt && otp.isDeltaRepresentation()) - return; // next isn't a delta, but we are - - nWeight = next.getWeight(); - if (otp.getWeight() <= nWeight) - return; // next would be bigger - } else - nWeight = next.getWeight(); - if (nFmt == PACK_DELTA && reuseDeltas && reuseDeltaFor(otp)) { ObjectId baseId = next.getDeltaBase(); ObjectToPack ptr = objectsMap.get(baseId); if (ptr != null && !ptr.isEdge()) { otp.setDeltaBase(ptr); otp.setReuseAsIs(); - otp.setWeight(nWeight); } else if (thin && ptr != null && ptr.isEdge()) { otp.setDeltaBase(baseId); otp.setReuseAsIs(); - otp.setWeight(nWeight); } else { otp.clearDeltaBase(); otp.clearReuseAsIs(); } } else if (nFmt == PACK_WHOLE && config.isReuseObjects()) { + int nWeight = next.getWeight(); + if (otp.isReuseAsIs() && !otp.isDeltaRepresentation()) { + // We've chosen another PACK_WHOLE format for this object, + // choose the one that has the smaller compressed size. + // + if (otp.getWeight() <= nWeight) + return; + } otp.clearDeltaBase(); otp.setReuseAsIs(); otp.setWeight(nWeight); -- 2.39.5