| /* |
| * Copyright (C) 2010, 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.internal.storage.pack; |
| |
| import java.io.EOFException; |
| import java.io.IOException; |
| import java.io.OutputStream; |
| import java.util.zip.Deflater; |
| |
| import org.eclipse.jgit.errors.IncorrectObjectTypeException; |
| import org.eclipse.jgit.errors.LargeObjectException; |
| import org.eclipse.jgit.errors.MissingObjectException; |
| import org.eclipse.jgit.lib.ObjectReader; |
| import org.eclipse.jgit.lib.ProgressMonitor; |
| import org.eclipse.jgit.storage.pack.PackConfig; |
| import org.eclipse.jgit.util.TemporaryBuffer; |
| |
| final class DeltaWindow { |
| private static final boolean NEXT_RES = false; |
| private static final boolean NEXT_SRC = true; |
| |
| private final PackConfig config; |
| private final DeltaCache deltaCache; |
| private final ObjectReader reader; |
| private final ProgressMonitor monitor; |
| private final long bytesPerUnit; |
| private long bytesProcessed; |
| |
| /** Maximum number of bytes to admit to the window at once. */ |
| private final long maxMemory; |
| |
| /** Maximum depth we should create for any delta chain. */ |
| private final int maxDepth; |
| |
| private final ObjectToPack[] toSearch; |
| private int cur; |
| private int end; |
| |
| /** Amount of memory we have loaded right now. */ |
| private long loaded; |
| |
| // The object we are currently considering needs a lot of state: |
| |
| /** Window entry of the object we are currently considering. */ |
| private DeltaWindowEntry res; |
| |
| /** If we have chosen a base, the window entry it was created from. */ |
| private DeltaWindowEntry bestBase; |
| private int deltaLen; |
| private Object deltaBuf; |
| |
| /** Used to compress cached deltas. */ |
| private Deflater deflater; |
| |
| DeltaWindow(PackConfig pc, DeltaCache dc, ObjectReader or, |
| ProgressMonitor pm, long bpu, |
| ObjectToPack[] in, int beginIndex, int endIndex) { |
| config = pc; |
| deltaCache = dc; |
| reader = or; |
| monitor = pm; |
| bytesPerUnit = bpu; |
| toSearch = in; |
| cur = beginIndex; |
| end = endIndex; |
| |
| maxMemory = Math.max(0, config.getDeltaSearchMemoryLimit()); |
| maxDepth = config.getMaxDeltaDepth(); |
| res = DeltaWindowEntry.createWindow(config.getDeltaSearchWindowSize()); |
| } |
| |
| synchronized DeltaTask.Slice remaining() { |
| int e = end; |
| int halfRemaining = (e - cur) >>> 1; |
| if (0 == halfRemaining) |
| return null; |
| |
| int split = e - halfRemaining; |
| int h = toSearch[split].getPathHash(); |
| |
| // Attempt to split on the next path after the 50% split point. |
| for (int n = split + 1; n < e; n++) { |
| if (h != toSearch[n].getPathHash()) |
| return new DeltaTask.Slice(n, e); |
| } |
| |
| if (h != toSearch[cur].getPathHash()) { |
| // Try to split on the path before the 50% split point. |
| // Do not split the path currently being processed. |
| for (int p = split - 1; cur < p; p--) { |
| if (h != toSearch[p].getPathHash()) |
| return new DeltaTask.Slice(p + 1, e); |
| } |
| } |
| return null; |
| } |
| |
| synchronized boolean tryStealWork(DeltaTask.Slice s) { |
| if (s.beginIndex <= cur || end <= s.beginIndex) |
| return false; |
| end = s.beginIndex; |
| return true; |
| } |
| |
| void search() throws IOException { |
| try { |
| for (;;) { |
| ObjectToPack next; |
| synchronized (this) { |
| if (end <= cur) |
| break; |
| next = toSearch[cur++]; |
| } |
| if (maxMemory != 0) { |
| clear(res); |
| final long need = estimateSize(next); |
| DeltaWindowEntry n = res.next; |
| for (; maxMemory < loaded + need && n != res; n = n.next) |
| clear(n); |
| } |
| res.set(next); |
| clearWindowOnTypeSwitch(); |
| |
| if (res.object.isEdge() || res.object.doNotAttemptDelta()) { |
| // We don't actually want to make a delta for |
| // them, just need to push them into the window |
| // so they can be read by other objects. |
| keepInWindow(); |
| } else { |
| // Search for a delta for the current window slot. |
| if (bytesPerUnit <= (bytesProcessed += next.getWeight())) { |
| int d = (int) (bytesProcessed / bytesPerUnit); |
| monitor.update(d); |
| bytesProcessed -= d * bytesPerUnit; |
| } |
| searchInWindow(); |
| } |
| } |
| } finally { |
| if (deflater != null) |
| deflater.end(); |
| } |
| } |
| |
| private static long estimateSize(ObjectToPack ent) { |
| return DeltaIndex.estimateIndexSize(ent.getWeight()); |
| } |
| |
| private static long estimateIndexSize(DeltaWindowEntry ent) { |
| if (ent.buffer == null) |
| return estimateSize(ent.object); |
| |
| int len = ent.buffer.length; |
| return DeltaIndex.estimateIndexSize(len) - len; |
| } |
| |
| private void clearWindowOnTypeSwitch() { |
| DeltaWindowEntry p = res.prev; |
| if (!p.empty() && res.type() != p.type()) { |
| for (; p != res; p = p.prev) { |
| clear(p); |
| } |
| } |
| } |
| |
| private void clear(DeltaWindowEntry ent) { |
| if (ent.index != null) |
| loaded -= ent.index.getIndexSize(); |
| else if (ent.buffer != null) |
| loaded -= ent.buffer.length; |
| ent.set(null); |
| } |
| |
| private void searchInWindow() throws IOException { |
| // Loop through the window backwards, considering every entry. |
| // This lets us look at the bigger objects that came before. |
| for (DeltaWindowEntry src = res.prev; src != res; src = src.prev) { |
| if (src.empty()) |
| break; |
| if (delta(src) /* == NEXT_SRC */) |
| continue; |
| bestBase = null; |
| deltaBuf = null; |
| return; |
| } |
| |
| // We couldn't find a suitable delta for this object, but it may |
| // still be able to act as a base for another one. |
| if (bestBase == null) { |
| keepInWindow(); |
| return; |
| } |
| |
| // Select this best matching delta as the base for the object. |
| // |
| ObjectToPack srcObj = bestBase.object; |
| ObjectToPack resObj = res.object; |
| if (srcObj.isEdge()) { |
| // The source (the delta base) is an edge object outside of the |
| // pack. Its part of the common base set that the peer already |
| // has on hand, so we don't want to send it. We have to store |
| // an ObjectId and *NOT* an ObjectToPack for the base to ensure |
| // the base isn't included in the outgoing pack file. |
| resObj.setDeltaBase(srcObj.copy()); |
| } else { |
| // The base is part of the pack we are sending, so it should be |
| // a direct pointer to the base. |
| resObj.setDeltaBase(srcObj); |
| } |
| |
| int depth = srcObj.getDeltaDepth() + 1; |
| resObj.setDeltaDepth(depth); |
| resObj.clearReuseAsIs(); |
| cacheDelta(srcObj, resObj); |
| |
| if (depth < maxDepth) { |
| // Reorder the window so that the best base will be tested |
| // first for the next object, and the current object will |
| // be the second candidate to consider before any others. |
| res.makeNext(bestBase); |
| res = bestBase.next; |
| } |
| |
| bestBase = null; |
| deltaBuf = null; |
| } |
| |
| private boolean delta(DeltaWindowEntry src) |
| throws IOException { |
| // If the sizes are radically different, this is a bad pairing. |
| if (res.size() < src.size() >>> 4) |
| return NEXT_SRC; |
| |
| int msz = deltaSizeLimit(src); |
| if (msz <= 8) // Nearly impossible to fit useful delta. |
| return NEXT_SRC; |
| |
| // If we have to insert a lot to make this work, find another. |
| if (res.size() - src.size() > msz) |
| return NEXT_SRC; |
| |
| DeltaIndex srcIndex; |
| try { |
| srcIndex = index(src); |
| } catch (LargeObjectException tooBig) { |
| // If the source is too big to work on, skip it. |
| return NEXT_SRC; |
| } catch (IOException notAvailable) { |
| if (src.object.isEdge()) // Missing edges are OK. |
| return NEXT_SRC; |
| throw notAvailable; |
| } |
| |
| byte[] resBuf; |
| try { |
| resBuf = buffer(res); |
| } catch (LargeObjectException tooBig) { |
| // If its too big, move on to another item. |
| return NEXT_RES; |
| } |
| |
| try { |
| OutputStream delta = msz <= (8 << 10) |
| ? new ArrayStream(msz) |
| : new TemporaryBuffer.Heap(msz); |
| if (srcIndex.encode(delta, resBuf, msz)) |
| selectDeltaBase(src, delta); |
| } catch (IOException deltaTooBig) { |
| // Unlikely, encoder should see limit and return false. |
| } |
| return NEXT_SRC; |
| } |
| |
| private void selectDeltaBase(DeltaWindowEntry src, OutputStream delta) { |
| bestBase = src; |
| |
| if (delta instanceof ArrayStream) { |
| ArrayStream a = (ArrayStream) delta; |
| deltaBuf = a.buf; |
| deltaLen = a.cnt; |
| } else { |
| TemporaryBuffer.Heap b = (TemporaryBuffer.Heap) delta; |
| deltaBuf = b; |
| deltaLen = (int) b.length(); |
| } |
| } |
| |
| private int deltaSizeLimit(DeltaWindowEntry src) { |
| if (bestBase == null) { |
| // Any delta should be no more than 50% of the original size |
| // (for text files deflate of whole form should shrink 50%). |
| int n = res.size() >>> 1; |
| |
| // Evenly distribute delta size limits over allowed depth. |
| // If src is non-delta (depth = 0), delta <= 50% of original. |
| // If src is almost at limit (9/10), delta <= 10% of original. |
| return n * (maxDepth - src.depth()) / maxDepth; |
| } |
| |
| // With a delta base chosen any new delta must be "better". |
| // Retain the distribution described above. |
| int d = bestBase.depth(); |
| int n = deltaLen; |
| |
| // If src is whole (depth=0) and base is near limit (depth=9/10) |
| // any delta using src can be 10x larger and still be better. |
| // |
| // If src is near limit (depth=9/10) and base is whole (depth=0) |
| // a new delta dependent on src must be 1/10th the size. |
| return n * (maxDepth - src.depth()) / (maxDepth - d); |
| } |
| |
| private void cacheDelta(ObjectToPack srcObj, ObjectToPack resObj) { |
| if (deltaCache.canCache(deltaLen, srcObj, resObj)) { |
| try { |
| byte[] zbuf = new byte[deflateBound(deltaLen)]; |
| ZipStream zs = new ZipStream(deflater(), zbuf); |
| if (deltaBuf instanceof byte[]) |
| zs.write((byte[]) deltaBuf, 0, deltaLen); |
| else |
| ((TemporaryBuffer.Heap) deltaBuf).writeTo(zs, null); |
| deltaBuf = null; |
| int len = zs.finish(); |
| |
| resObj.setCachedDelta(deltaCache.cache(zbuf, len, deltaLen)); |
| resObj.setCachedSize(deltaLen); |
| } catch (IOException | OutOfMemoryError err) { |
| deltaCache.credit(deltaLen); |
| } |
| } |
| } |
| |
| private static int deflateBound(int insz) { |
| return insz + ((insz + 7) >> 3) + ((insz + 63) >> 6) + 11; |
| } |
| |
| private void keepInWindow() { |
| res = res.next; |
| } |
| |
| private DeltaIndex index(DeltaWindowEntry ent) |
| throws MissingObjectException, IncorrectObjectTypeException, |
| IOException, LargeObjectException { |
| DeltaIndex idx = ent.index; |
| if (idx == null) { |
| checkLoadable(ent, estimateIndexSize(ent)); |
| |
| try { |
| idx = new DeltaIndex(buffer(ent)); |
| } catch (OutOfMemoryError noMemory) { |
| LargeObjectException.OutOfMemory e; |
| e = new LargeObjectException.OutOfMemory(noMemory); |
| e.setObjectId(ent.object); |
| throw e; |
| } |
| if (maxMemory != 0) |
| loaded += idx.getIndexSize() - idx.getSourceSize(); |
| ent.index = idx; |
| } |
| return idx; |
| } |
| |
| private byte[] buffer(DeltaWindowEntry ent) throws MissingObjectException, |
| IncorrectObjectTypeException, IOException, LargeObjectException { |
| byte[] buf = ent.buffer; |
| if (buf == null) { |
| checkLoadable(ent, ent.size()); |
| |
| buf = PackWriter.buffer(config, reader, ent.object); |
| if (maxMemory != 0) |
| loaded += buf.length; |
| ent.buffer = buf; |
| } |
| return buf; |
| } |
| |
| private void checkLoadable(DeltaWindowEntry ent, long need) { |
| if (maxMemory == 0) |
| return; |
| |
| DeltaWindowEntry n = res.next; |
| for (; maxMemory < loaded + need; n = n.next) { |
| clear(n); |
| if (n == ent) |
| throw new LargeObjectException.ExceedsLimit( |
| maxMemory, loaded + need); |
| } |
| } |
| |
| private Deflater deflater() { |
| if (deflater == null) |
| deflater = new Deflater(config.getCompressionLevel()); |
| else |
| deflater.reset(); |
| return deflater; |
| } |
| |
| static final class ZipStream extends OutputStream { |
| private final Deflater deflater; |
| |
| private final byte[] zbuf; |
| |
| private int outPtr; |
| |
| ZipStream(Deflater deflater, byte[] zbuf) { |
| this.deflater = deflater; |
| this.zbuf = zbuf; |
| } |
| |
| int finish() throws IOException { |
| deflater.finish(); |
| for (;;) { |
| if (outPtr == zbuf.length) |
| throw new EOFException(); |
| |
| int n = deflater.deflate(zbuf, outPtr, zbuf.length - outPtr); |
| if (n == 0) { |
| if (deflater.finished()) |
| return outPtr; |
| throw new IOException(); |
| } |
| outPtr += n; |
| } |
| } |
| |
| @Override |
| public void write(byte[] b, int off, int len) throws IOException { |
| deflater.setInput(b, off, len); |
| for (;;) { |
| if (outPtr == zbuf.length) |
| throw new EOFException(); |
| |
| int n = deflater.deflate(zbuf, outPtr, zbuf.length - outPtr); |
| if (n == 0) { |
| if (deflater.needsInput()) |
| break; |
| throw new IOException(); |
| } |
| outPtr += n; |
| } |
| } |
| |
| @Override |
| public void write(int b) throws IOException { |
| throw new UnsupportedOperationException(); |
| } |
| } |
| |
| static final class ArrayStream extends OutputStream { |
| final byte[] buf; |
| int cnt; |
| |
| ArrayStream(int max) { |
| buf = new byte[max]; |
| } |
| |
| @Override |
| public void write(int b) throws IOException { |
| if (cnt == buf.length) |
| throw new IOException(); |
| buf[cnt++] = (byte) b; |
| } |
| |
| @Override |
| public void write(byte[] b, int off, int len) throws IOException { |
| if (len > buf.length - cnt) |
| throw new IOException(); |
| System.arraycopy(b, off, buf, cnt, len); |
| cnt += len; |
| } |
| } |
| } |