From 5ef1605f0a2afc0baed14bad60a5b44450ba7fbc Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Sun, 18 May 2008 16:56:29 -0400 Subject: [PATCH] Refactor WindowCache to allow dynamic changes in configuration We want to allow applications to alter the WindowCache configuration on the fly, such as in IDEs when the user changes our parameters and expects the IDE to respond immediately to the modification. This means we cannot safely access our window size data from outside of WindowCache, as the ids for windows can change when the size of a window is modified by the caller. Instead we must work with the full file position anytime we want data, which forces us into using a 64 bit value where we had been using only a 32 bit window id. Signed-off-by: Shawn O. Pearce --- .../src/org/spearce/jgit/lib/ByteArrayWindow.java | 9 +- .../src/org/spearce/jgit/lib/ByteBufferWindow.java | 5 +- .../src/org/spearce/jgit/lib/ByteWindow.java | 80 ++++++++++++- .../src/org/spearce/jgit/lib/WindowCache.java | 133 +++++++++++++++------ .../src/org/spearce/jgit/lib/WindowCursor.java | 48 ++++---- .../src/org/spearce/jgit/lib/WindowedFile.java | 48 ++------ 6 files changed, 218 insertions(+), 105 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java index aa2797d6..a9e8dbcf 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java @@ -28,14 +28,17 @@ final class ByteArrayWindow extends ByteWindow { * * @param o * the WindowedFile providing data access + * @param p + * the file offset. * @param d * an id provided by the WindowedFile. See - * {@link WindowCache#get(WindowCursor, WindowedFile, int)}. + * {@link WindowCache#get(WindowCursor, WindowedFile, long)}. * @param b * byte array for storage */ - ByteArrayWindow(final WindowedFile o, final int d, final byte[] b) { - super(o, d, b, b.length); + ByteArrayWindow(final WindowedFile o, final long p, final int d, + final byte[] b) { + super(o, p, d, b, b.length); } int copy(final byte[] array, final int p, final byte[] b, final int o, int n) { diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java index 40f85430..a2273f10 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java @@ -32,12 +32,13 @@ final class ByteBufferWindow extends ByteWindow { * @See ByteWindow * * @param o The WindowedFile + * @param p the file offset. * @param d Window id * @param b ByteBuffer storage */ - ByteBufferWindow(final WindowedFile o, final int d, + ByteBufferWindow(final WindowedFile o, final long p, final int d, final ByteBuffer b) { - super(o, d, b, b.capacity()); + super(o, p, d, b, b.capacity()); } final int copy(final ByteBuffer buffer, final int p, final byte[] b, diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java index 9d098deb..abd93517 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java @@ -30,7 +30,8 @@ import java.util.zip.Inflater; * bytes from a window is very inexpensive. *

* - * @param type of object reference used to manage the window data. + * @param + * type of object reference used to manage the window data. */ abstract class ByteWindow extends SoftReference { final WindowedFile provider; @@ -41,25 +42,61 @@ abstract class ByteWindow extends SoftReference { int lastAccessed; + final long start; + + final long end; + /** * Constructor for ByteWindow. * * @param o * the WindowedFile providing data access + * @param pos + * the position in the file the data comes from. * @param d * an id provided by the WindowedFile. See - * {@link WindowCache#get(WindowCursor, WindowedFile, int)}. + * {@link WindowCache#get(WindowCursor, WindowedFile, long)}. * @param ref * the object value required to perform data access. * @param sz * the total number of bytes in this window. */ @SuppressWarnings("unchecked") - ByteWindow(final WindowedFile o, final int d, final T ref, final int sz) { - super(ref, (ReferenceQueue)WindowCache.clearedWindowQueue); + ByteWindow(final WindowedFile o, final long pos, final int d, final T ref, + final int sz) { + super(ref, (ReferenceQueue) WindowCache.clearedWindowQueue); provider = o; size = sz; id = d; + start = pos; + end = start + size; + } + + final boolean contains(final WindowedFile neededFile, final long neededPos) { + return provider == neededFile && start <= neededPos && neededPos < end; + } + + /** + * Copy bytes from the window to a caller supplied buffer. + * + * @param ref + * the object value required to perform data access. + * @param pos + * offset within the file to start copying from. + * @param dstbuf + * destination buffer to copy into. + * @param dstoff + * offset within dstbuf to start copying into. + * @param cnt + * number of bytes to copy. This value may exceed the number of + * bytes remaining in the window starting at offset + * pos. + * @return number of bytes actually copied; this may be less than + * cnt if cnt exceeded the number of + * bytes available. + */ + final int copy(T ref, long pos, byte[] dstbuf, int dstoff, int cnt) { + return copy(ref, (int) (pos - start), dstbuf, dstoff, cnt); } /** @@ -106,8 +143,39 @@ abstract class ByteWindow extends SoftReference { * another window's data must still be supplied as input to finish * decompression. * @throws DataFormatException - * the inflater encountered an invalid chunk of data. Data stream - * corruption is likely. + * the inflater encountered an invalid chunk of data. Data + * stream corruption is likely. + */ + final int inflate(T ref, long pos, byte[] dstbuf, int dstoff, Inflater inf) + throws DataFormatException { + return inflate(ref, (int) (pos - start), dstbuf, dstoff, inf); + } + + /** + * Pump bytes into the supplied inflater as input. + * + * @param ref + * the object value required to perform data access. + * @param pos + * offset within the window to start supplying input from. + * @param dstbuf + * destination buffer the inflater should output decompressed + * data to. + * @param dstoff + * current offset within dstbuf to inflate into. + * @param inf + * the inflater to feed input to. The caller is responsible for + * initializing the inflater as multiple windows may need to + * supply data to the same inflater to completely decompress + * something. + * @return updated dstoff based on the number of bytes + * successfully copied into dstbuf by + * inf. If the inflater is not yet finished then + * another window's data must still be supplied as input to finish + * decompression. + * @throws DataFormatException + * the inflater encountered an invalid chunk of data. Data + * stream corruption is likely. */ abstract int inflate(T ref, int pos, byte[] dstbuf, int dstoff, Inflater inf) throws DataFormatException; diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java index fbb07849..1377c727 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java @@ -36,19 +36,17 @@ public class WindowCache { return Integer.numberOfTrailingZeros(newSize); } - private static final int maxByteCount; + private static int maxByteCount; - static final int sz; + private static int windowSize; - static final int szb; + private static int windowSizeShift; - static final int szm; - - static final boolean mmap; + static boolean mmap; static final ReferenceQueue clearedWindowQueue; - private static final ByteWindow[] windows; + private static ByteWindow[] windows; private static int openWindowCount; @@ -58,11 +56,10 @@ public class WindowCache { static { maxByteCount = 10 * MB; - szb = bits(8 * KB); - sz = 1 << szb; - szm = (1 << szb) - 1; + windowSizeShift = bits(8 * KB); + windowSize = 1 << windowSizeShift; mmap = false; - windows = new ByteWindow[maxByteCount / sz]; + windows = new ByteWindow[maxByteCount / windowSize]; clearedWindowQueue = new ReferenceQueue(); } @@ -85,10 +82,62 @@ public class WindowCache { public static void reconfigure(final int packedGitLimit, final int packedGitWindowSize, final boolean packedGitMMAP, final int deltaBaseCacheLimit) { - // fix me + reconfigureImpl(packedGitLimit, packedGitWindowSize, packedGitMMAP); UnpackedObjectCache.reconfigure(deltaBaseCacheLimit); } + private static synchronized void reconfigureImpl(final int packedGitLimit, + final int packedGitWindowSize, final boolean packedGitMMAP) { + boolean prune = false; + boolean evictAll = false; + + if (maxByteCount < packedGitLimit) { + maxByteCount = packedGitLimit; + } else if (maxByteCount > packedGitLimit) { + maxByteCount = packedGitLimit; + prune = true; + } + + if (bits(packedGitWindowSize) != windowSizeShift) { + windowSizeShift = bits(packedGitWindowSize); + windowSize = 1 << windowSizeShift; + evictAll = true; + } + + if (mmap != packedGitMMAP) { + mmap = packedGitMMAP; + evictAll = true; + } + + if (evictAll) { + // We have to throw away every window we have. None + // of them are suitable for the new configuration. + // + for (int i = 0; i < openWindowCount; i++) { + final ByteWindow win = windows[i]; + if (--win.provider.openCount == 0) + win.provider.cacheClose(); + windows[i] = null; + } + windows = new ByteWindow[maxByteCount / windowSize]; + openWindowCount = 0; + openByteCount = 0; + } else if (prune) { + // Our memory limit was decreased so we should try + // to drop windows to ensure we meet the new lower + // limit we were just given. + // + final int wincnt = maxByteCount / windowSize; + releaseMemory(wincnt, null, 0, 0); + + if (wincnt != windows.length) { + final ByteWindow[] n = new ByteWindow[wincnt]; + System.arraycopy(windows, 0, n, 0, openWindowCount); + windows = n; + } + } + } + /** * Get a specific window. * @@ -98,17 +147,16 @@ public class WindowCache { * @param wp * the provider of the window. If the window is not currently in * the cache then the provider will be asked to load it. - * @param id - * the id, unique only within the scope of the specific provider - * wp. Typically this id is the byte offset - * within the file divided by the window size, but its meaning is - * left open to the provider. + * @param position + * offset (in bytes) within the file that the caller needs access + * to. * @throws IOException * the window was not found in the cache and the given provider * was unable to load the window on demand. */ public static synchronized final void get(final WindowCursor curs, - final WindowedFile wp, final int id) throws IOException { + final WindowedFile wp, final long position) throws IOException { + final int id = (int) (position >> windowSizeShift); int idx = binarySearch(wp, id); if (0 <= idx) { final ByteWindow w = windows[idx]; @@ -149,6 +197,22 @@ public class WindowCache { } idx = -(idx + 1); + final int wSz = windowSize(wp, id); + idx = releaseMemory(windows.length, wp, idx, wSz); + + if (idx < 0) + idx = 0; + final int toMove = openWindowCount - idx; + if (toMove > 0) + System.arraycopy(windows, idx, windows, idx + 1, toMove); + wp.loadWindow(curs, id, id << windowSizeShift, wSz); + windows[idx] = curs.window; + openWindowCount++; + openByteCount += curs.window.size; + } + + private static int releaseMemory(final int maxWindowCount, + final WindowedFile willRead, int insertionIndex, final int willAdd) { for (;;) { final ByteWindow w = (ByteWindow) clearedWindowQueue.poll(); if (w == null) @@ -158,7 +222,7 @@ public class WindowCache { continue; // Must have been evicted by our other controls. final WindowedFile p = w.provider; - if (--p.openCount == 0 && p != wp) + if (--p.openCount == 0 && p != willRead) p.cacheClose(); openByteCount -= w.size; @@ -166,13 +230,12 @@ public class WindowCache { if (toMove > 0) System.arraycopy(windows, oldest + 1, windows, oldest, toMove); windows[--openWindowCount] = null; - if (oldest < idx) - idx--; + if (oldest < insertionIndex) + insertionIndex--; } - final int wSz = wp.getWindowSize(id); - while (openWindowCount == windows.length - || (openWindowCount > 0 && openByteCount + wSz > maxByteCount)) { + while (openWindowCount >= maxWindowCount + || (openWindowCount > 0 && openByteCount + willAdd > maxByteCount)) { int oldest = 0; for (int k = openWindowCount - 1; k > 0; k--) { if (windows[k].lastAccessed < windows[oldest].lastAccessed) @@ -181,7 +244,7 @@ public class WindowCache { final ByteWindow w = windows[oldest]; final WindowedFile p = w.provider; - if (--p.openCount == 0 && p != wp) + if (--p.openCount == 0 && p != willRead) p.cacheClose(); openByteCount -= w.size; @@ -190,19 +253,11 @@ public class WindowCache { System.arraycopy(windows, oldest + 1, windows, oldest, toMove); windows[--openWindowCount] = null; w.enqueue(); - if (oldest < idx) - idx--; + if (oldest < insertionIndex) + insertionIndex--; } - if (idx < 0) - idx = 0; - final int toMove = openWindowCount - idx; - if (toMove > 0) - System.arraycopy(windows, idx, windows, idx + 1, toMove); - wp.loadWindow(curs, id); - windows[idx] = curs.window; - openWindowCount++; - openByteCount += curs.window.size; + return insertionIndex; } private static final int binarySearch(final WindowedFile sprov, @@ -255,6 +310,12 @@ public class WindowCache { } } + private static int windowSize(final WindowedFile file, final int id) { + final long len = file.length(); + final long pos = id << windowSizeShift; + return len < pos + windowSize ? (int) (len - pos) : windowSize; + } + private WindowCache() { throw new UnsupportedOperationException(); } diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java index 3f6281e3..55eef025 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java @@ -18,10 +18,8 @@ public final class WindowCursor { * * @param provider * the file the desired window is stored within. - * @param id - * unique id number of this window within the file. - * @param pos - * offset within the window to start copying from. + * @param position + * position within the file to read from. * @param dstbuf * destination buffer to copy into. * @param dstoff @@ -37,11 +35,18 @@ public final class WindowCursor { * this cursor does not match the provider or id and the proper * window could not be acquired through the provider's cache. */ - int copy(final WindowedFile provider, final int id, final int pos, - final byte[] dstbuf, final int dstoff, final int cnt) - throws IOException { - pin(provider, id); - return window.copy(handle, pos, dstbuf, dstoff, cnt); + int copy(final WindowedFile provider, long position, final byte[] dstbuf, + int dstoff, final int cnt) throws IOException { + final long length = provider.length(); + int need = cnt; + while (need > 0 && position < length) { + pin(provider, position); + final int r = window.copy(handle, position, dstbuf, dstoff, need); + position += r; + dstoff += r; + need -= r; + } + return cnt - need; } /** @@ -49,10 +54,8 @@ public final class WindowCursor { * * @param provider * the file the desired window is stored within. - * @param id - * unique id number of this window within the file. - * @param pos - * offset within the window to start supplying input from. + * @param position + * position within the file to read from. * @param dstbuf * destination buffer the inflater should output decompressed * data to. @@ -75,18 +78,23 @@ public final class WindowCursor { * the inflater encountered an invalid chunk of data. Data * stream corruption is likely. */ - int inflate(final WindowedFile provider, final int id, final int pos, - final byte[] dstbuf, final int dstoff, final Inflater inf) + int inflate(final WindowedFile provider, long position, + final byte[] dstbuf, int dstoff, final Inflater inf) throws IOException, DataFormatException { - pin(provider, id); - return window.inflate(handle, pos, dstbuf, dstoff, inf); + for (;;) { + pin(provider, position); + dstoff = window.inflate(handle, position, dstbuf, dstoff, inf); + if (inf.finished()) + return dstoff; + position = window.end; + } } - private void pin(final WindowedFile provider, final int id) + private void pin(final WindowedFile provider, final long position) throws IOException { final ByteWindow w = window; - if (w == null || w.provider != provider || w.id != id) - WindowCache.get(this, provider, id); + if (w == null || !w.contains(provider, position)) + WindowCache.get(this, provider, position); } /** Release the current window cursor. */ diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java index 8f8ac729..c5b2b416 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java @@ -143,16 +143,7 @@ public class WindowedFile { */ public int read(long position, final byte[] dstbuf, int dstoff, final int cnt, final WindowCursor curs) throws IOException { - int remaining = cnt; - while (remaining > 0 && position < length) { - final int r = curs.copy(this, (int) (position >> WindowCache.szb), - ((int) position) & WindowCache.szm, dstbuf, dstoff, - remaining); - position += r; - dstoff += r; - remaining -= r; - } - return cnt - remaining; + return curs.copy(this, position, dstbuf, dstoff, cnt); } /** @@ -187,24 +178,13 @@ public class WindowedFile { final WindowCursor curs) throws IOException, DataFormatException { final Inflater inf = InflaterCache.get(); try { - readCompressed(position, dstbuf, curs, inf); + if (curs.inflate(this, position, dstbuf, 0, inf) != dstbuf.length) + throw new EOFException("Short compressed stream at " + position); } finally { InflaterCache.release(inf); } } - void readCompressed(long pos, final byte[] dstbuf, final WindowCursor curs, - final Inflater inf) throws IOException, DataFormatException { - int dstoff = 0; - dstoff = curs.inflate(this, (int) (pos >> WindowCache.szb), ((int) pos) - & WindowCache.szm, dstbuf, dstoff, inf); - pos >>= WindowCache.szb; - while (!inf.finished()) - dstoff = curs.inflate(this, (int) ++pos, 0, dstbuf, dstoff, inf); - if (dstoff != dstbuf.length) - throw new EOFException(); - } - /** * Overridable hook called after the file is opened. *

@@ -255,19 +235,17 @@ public class WindowedFile { fd = null; } - void loadWindow(final WindowCursor curs, final int windowId) - throws IOException { - final long position = windowId << WindowCache.szb; - final int windowSize = getWindowSize(windowId); + void loadWindow(final WindowCursor curs, final int windowId, + final long pos, final int windowSize) throws IOException { if (WindowCache.mmap) { final MappedByteBuffer map = fd.getChannel().map(MapMode.READ_ONLY, - position, windowSize); + pos, windowSize); if (map.hasArray()) { final byte[] b = map.array(); - curs.window = new ByteArrayWindow(this, windowId, b); + curs.window = new ByteArrayWindow(this, pos, windowId, b); curs.handle = b; } else { - curs.window = new ByteBufferWindow(this, windowId, map); + curs.window = new ByteBufferWindow(this, pos, windowId, map); curs.handle = map; } return; @@ -275,16 +253,10 @@ public class WindowedFile { final byte[] b = new byte[windowSize]; synchronized (fd) { - fd.seek(position); + fd.seek(pos); fd.readFully(b); } - curs.window = new ByteArrayWindow(this, windowId, b); + curs.window = new ByteArrayWindow(this, pos, windowId, b); curs.handle = b; } - - int getWindowSize(final int id) { - final int sz = WindowCache.sz; - final long position = id << WindowCache.szb; - return length < position + sz ? (int) (length - position) : sz; - } } -- 2.11.4.GIT