{"thread":{"id":"19126","subject":"[JGIT PATCH v2 00/11] WindowCache rewrite... with tests","startedAt":"2009-04-29T18:54:37Z","lastAt":"2009-04-29T23:46:30Z","messageCount":13,"participants":["Shawn O. Pearce","Robin Rosenberg"],"isPatch":true,"patchVersion":2,"patchTotal":11},"messages":[{"id":"112658","messageId":"1241031288-23437-1-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":null,"subject":"[JGIT PATCH v2 00/11] WindowCache rewrite... with tests","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:37Z","receivedAt":"2009-04-29T18:54:37Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Actually, this is my entire outstanding patch set series.\n\n1 and 2 should be trivial to apply.\n\n3-6 should be fairly straightforward.\n\n7 maybe we delay until later, but I don't think any applications\nuse that map type.\n\n8 is pretty trivial, and is needed to prevent 9 from deadlocking.\n\n9-11 is the rewrite of WindowCache, with new unit tests to get higher\nlevels of coverage in this section of the code. Actually doing\nbetter is really hard, as we'd need to cause thread race conditions\ndeep within critical sections. The only way I can think to do that\nis to add injection points where we can insert \"evil other thread\"\nlogic during the unit test, and rely on the JIT to compile them\nout in normal application usage. Ick. Its also quite fragile.\n\nShawn O. Pearce (11):\n Fix more computation of integer average overflows\n Fix performance problem recently introduced to\n DeltaPackedObjectLoader\n Replace inefficient new String(String) constructor to silence\n FindBugs\n Replace inefficient new Long(long) constructor to silence FindBugs\n Change IndexPack to use ObjectIdSubclassMap instead of ObjectIdMap\n Use getCachedBytes in IndexPack to avoid an unnecessary copy\n Remove ObjectIdMap from the JGit library\n Don't use ByteWindows when checking pack file headers/footers\n Rewrite WindowCache to be easier to follow and maintain\n Add tests for WindowCache.reconfigure cases\n Add tests to increase coverage of WindowCache\n\n .../jgit/test/resources/all_packed_objects.txt | 96 ++++\n .../org/spearce/jgit/lib/ConcurrentRepackTest.java | 4 -\n .../tst/org/spearce/jgit/lib/ObjectIdMapTest.java | 103 ----\n .../org/spearce/jgit/lib/WindowCacheGetTest.java | 143 ++++++\n .../jgit/lib/WindowCacheReconfigureTest.java | 119 +++++\n .../src/org/spearce/jgit/lib/ByteArrayWindow.java | 57 +--\n .../src/org/spearce/jgit/lib/ByteBufferWindow.java | 41 +-\n .../src/org/spearce/jgit/lib/ByteWindow.java | 91 +---\n .../spearce/jgit/lib/DeltaPackedObjectLoader.java | 1 +\n .../src/org/spearce/jgit/lib/ObjectIdMap.java | 201 --------\n .../org/spearce/jgit/lib/ObjectIdSubclassMap.java | 31 ++-\n .../src/org/spearce/jgit/lib/OffsetCache.java | 534 ++++++++++++++++++++\n .../src/org/spearce/jgit/lib/PackFile.java | 128 +++--\n .../src/org/spearce/jgit/lib/PackIndexV1.java | 2 +-\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 6 +-\n .../org/spearce/jgit/lib/PackedObjectLoader.java | 11 +-\n .../src/org/spearce/jgit/lib/RefDatabase.java | 3 +-\n .../src/org/spearce/jgit/lib/WindowCache.java | 424 +++++-----------\n .../src/org/spearce/jgit/lib/WindowCursor.java | 42 +-\n .../src/org/spearce/jgit/transport/IndexPack.java | 129 +++--\n .../src/org/spearce/jgit/transport/LongMap.java | 152 ++++++\n org.spearce.jgit/src/org/spearce/jgit/util/NB.java | 32 ++\n 22 files changed, 1465 insertions(+), 885 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst-rsrc/org/spearce/jgit/test/resources/all_packed_objects.txt\n delete mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheGetTest.java\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheReconfigureTest.java\n delete mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdMap.java\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java\n"},{"id":"112659","messageId":"1241031288-23437-2-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-1-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 01/11] Fix more computation of integer average overflows","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:38Z","receivedAt":"2009-04-29T18:54:38Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"In 1d99aaab8e364c6ad722437e43c77fd54e13b071 Matthias Sohn pointed\nout that (low+high)/2 can overflow, so (low+high)>>>1 is a better\nchoice when the result will be used as an array index.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n Unchanged.\n\n .../src/org/spearce/jgit/lib/PackIndexV1.java | 2 +-\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 6 +++---\n 2 files changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\nindex fdaa094..0ad29e1 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n@@ -129,7 +129,7 @@ long findOffset(final AnyObjectId objId) {\n \t\tint high = data.length / (4 + Constants.OBJECT_ID_LENGTH);\n \t\tint low = 0;\n \t\tdo {\n-\t\t\tfinal int mid = (low + high) / 2;\n+\t\t\tfinal int mid = (low + high) >>> 1;\n \t\t\tfinal int pos = ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;\n \t\t\tfinal int cmp = objId.compareTo(data, pos);\n \t\t\tif (cmp < 0)\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\nindex eb56ed9..b539547 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n@@ -108,7 +108,7 @@ PackIndexV2(final InputStream fd) throws IOException {\n \n \t\t\tfinal int intNameLen = (int) nameLen;\n \t\t\tfinal byte[] raw = new byte[intNameLen];\n-\t\t\tfinal int[] bin = new int[intNameLen >> 2];\n+\t\t\tfinal int[] bin = new int[intNameLen >>> 2];\n \t\t\tNB.readFully(fd, raw, 0, raw.length);\n \t\t\tfor (int i = 0; i < bin.length; i++)\n \t\t\t\tbin[i] = NB.decodeInt32(raw, i << 2);\n@@ -212,12 +212,12 @@ boolean hasCRC32Support() {\n \n \tprivate int binarySearchLevelTwo(final AnyObjectId objId, final int levelOne) {\n \t\tfinal int[] data = names[levelOne];\n-\t\tint high = offset32[levelOne].length >> 2;\n+\t\tint high = offset32[levelOne].length >>> 2;\n \t\tif (high == 0)\n \t\t\treturn -1;\n \t\tint low = 0;\n \t\tdo {\n-\t\t\tfinal int mid = (low + high) >> 1;\n+\t\t\tfinal int mid = (low + high) >>> 1;\n \t\t\tfinal int mid4 = mid << 2;\n \t\t\tfinal int cmp;\n \n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112661","messageId":"1241031288-23437-3-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-2-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 02/11] Fix performance problem recently introduced to DeltaPackedObjectLoader","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:39Z","receivedAt":"2009-04-29T18:54:39Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"In fe6c8248e1ed6bd9db76a8314103081a02d55393 (\"Fully materialize an\nObjectLoader before returning it from ObjectDatabase\") I missed a\ncrucial return call here in DeltaPackedObjectLoadeder. That one\nmissing line caused cache hits in the UnpackedObjectCache to then\nfall through and unpack the delta base, and apply the delta onto\nit, ignoring the fact that we had a successful cache hit.\n\nWhen packing and serving e.g. the Linux kernel repository this\nresulted in a 10x increase in the number of WindowCache.get()\ninvocations we saw, as the UnpackedObjectCache was useless.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n Unchanged.\n\n .../spearce/jgit/lib/DeltaPackedObjectLoader.java | 1 +\n 1 files changed, 1 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\nindex 8194d94..7d3f30d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\n@@ -69,6 +69,7 @@ public void materialize(final WindowCursor curs) throws IOException {\n \t\t\t\tobjectType = cache.type;\n \t\t\t\tobjectSize = cache.data.length;\n \t\t\t\tcachedBytes = cache.data;\n+\t\t\t\treturn;\n \t\t\t}\n \t\t}\n \n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112660","messageId":"1241031288-23437-4-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-3-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 03/11] Replace inefficient new String(String) constructor to silence FindBugs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:40Z","receivedAt":"2009-04-29T18:54:40Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"FindBugs keeps reporting that our usage of new String(String)\nis not the most efficient way to construct a string.\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/113739/focus=113787\n> I had a specific reason for forcing a new String object here.\n>\n> The line in question, p, is from the packed-refs file and\n> contains the entire SHA-1 in hex form at the beginning of it.\n> We've converted that into binary as an ObjectId, it uses 1/4 the\n> space of the string portion.\n>\n> The Ref object, its ObjectId, and its name string, are going to be\n> cached in a Map, probably long-term. We're better off shedding the\n> 80 bytes of memory used to hold the hex SHA-1 then risk substring()\n> deciding its \"faster\" to reuse the char[] then to make a copy of it.\n\nAnother way to force this new unique String instance with its own\nprivate char[] is to use a StringBuilder and append onto it the\nref name. This shouldn't be a warning for FindBugs, but it would\naccomplish the same goal of producing 1 clean copy, with no extra\ntransient temporary array.\n\nSigned-off-by: Shawn O. Pearce \nCC: Yann Simon \nCC: Matthias Sohn \n---\n\n Unchanged.\n\n .../src/org/spearce/jgit/lib/RefDatabase.java | 3 ++-\n 1 files changed, 2 insertions(+), 1 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java b/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java\nindex 87f26bf..bccf2d0 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java\n@@ -447,7 +447,8 @@ private synchronized void refreshPackedRefs() {\n \n \t\t\t\t\tfinal int sp = p.indexOf(' ');\n \t\t\t\t\tfinal ObjectId id = ObjectId.fromString(p.substring(0, sp));\n-\t\t\t\t\tfinal String name = new String(p.substring(sp + 1));\n+\t\t\t\t\tfinal String name = new StringBuilder(p.length() - (sp + 1))\n+\t\t\t\t\t\t\t.append(p, sp + 1, p.length()).toString();\n \t\t\t\t\tlast = new Ref(Ref.Storage.PACKED, name, name, id);\n \t\t\t\t\tnewPackedRefs.put(last.getName(), last);\n \t\t\t\t}\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112669","messageId":"1241031288-23437-5-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-4-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 04/11] Replace inefficient new Long(long) constructor to silence FindBugs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:41Z","receivedAt":"2009-04-29T18:54:41Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"FindBugs keeps warning us that new Long(long) is inefficient because\nit doesn't permit using cached values in the -128..127 range.\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/113738/focus=113785\n> Why I box with new Long() over Long.valueOf():\n>\n> The standard only requires -128..127 to be cached. A JRE can\n> cache value outside of this range if it chooses, but long has a\n> huge range, its unlikely to cache much beyond this required region.\n>\n> Most pack files are in the 10 MB...100+ MB range. Most objects\n> take more than 100 bytes in a pack, even compressed delta encoded.\n> Thus any object after the first is going to have its offset outside\n> of the cached range.\n>\n> In other words, why waste the CPU cycles on the \"cached range\n> bounds check\" when I'm always going to fail and allocate. I might\n> as well just allocate\n>\n> These sections of code are rather performance critical for the\n> indexing phase of a pack receive, on either side of a connection.\n> I need to shave even more instructions out of the critical paths,\n> as its not fast enough as-is. Using new Long() is quicker than\n> using Long.valueOf(), so new Long() it is.\n\nWe now use a custom Map implementation which supports primitive long\nas the hash key, rather than requiring boxing for java.util.HashMap.\nThis removes the issue FindBugs was identifying.\n\nThis version performs slightly better than before.\nindex-pack on linux-2.6:\n\n parent commit: 2m58.611s\n this commit : 2m57.068s\n\nSigned-off-by: Shawn O. Pearce \nCC: Yann Simon \nCC: Matthias Sohn \n---\n\n Unchanged.\n \n .../src/org/spearce/jgit/transport/IndexPack.java | 12 +-\n .../src/org/spearce/jgit/transport/LongMap.java | 152 ++++++++++++++++++++\n 2 files changed, 157 insertions(+), 7 deletions(-)\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\nindex e0e4855..59fdeae 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\n@@ -47,7 +47,6 @@\n import java.security.MessageDigest;\n import java.util.ArrayList;\n import java.util.Arrays;\n-import java.util.HashMap;\n import java.util.List;\n import java.util.zip.CRC32;\n import java.util.zip.DataFormatException;\n@@ -163,7 +162,7 @@ public static IndexPack create(final Repository db, final InputStream is)\n \n \tprivate ObjectIdMap> baseById;\n \n-\tprivate HashMap> baseByPos;\n+\tprivate LongMap> baseByPos;\n \n \tprivate byte[] objectData;\n \n@@ -303,7 +302,7 @@ public void index(final ProgressMonitor progress) throws IOException {\n \n \t\t\t\tentries = new PackedObjectInfo[(int) objectCount];\n \t\t\t\tbaseById = new ObjectIdMap>();\n-\t\t\t\tbaseByPos = new HashMap>();\n+\t\t\t\tbaseByPos = new LongMap>();\n \n \t\t\t\tprogress.beginTask(PROGRESS_DOWNLOAD, (int) objectCount);\n \t\t\t\tfor (int done = 0; done < objectCount; done++) {\n@@ -382,8 +381,7 @@ private void resolveDeltas(final ProgressMonitor progress)\n \n \tprivate void resolveDeltas(final PackedObjectInfo oe) throws IOException {\n \t\tfinal int oldCRC = oe.getCRC();\n-\t\tif (baseById.containsKey(oe)\n-\t\t\t\t|| baseByPos.containsKey(new Long(oe.getOffset())))\n+\t\tif (baseById.containsKey(oe) || baseByPos.containsKey(oe.getOffset()))\n \t\t\tresolveDeltas(oe.getOffset(), oldCRC, Constants.OBJ_BAD, null, oe);\n \t}\n \n@@ -448,7 +446,7 @@ private void resolveDeltas(final long pos, final int oldCRC, int type,\n \tprivate void resolveChildDeltas(final long pos, int type, byte[] data,\n \t\t\tPackedObjectInfo oe) throws IOException {\n \t\tfinal ArrayList a = baseById.remove(oe);\n-\t\tfinal ArrayList b = baseByPos.remove(new Long(pos));\n+\t\tfinal ArrayList b = baseByPos.remove(pos);\n \t\tint ai = 0, bi = 0;\n \t\tif (a != null && b != null) {\n \t\t\twhile (ai < a.size() && bi < b.size()) {\n@@ -679,7 +677,7 @@ private void indexOneObject() throws IOException {\n \t\t\t\tofs <<= 7;\n \t\t\t\tofs += (c & 127);\n \t\t\t}\n-\t\t\tfinal Long base = new Long(pos - ofs);\n+\t\t\tfinal long base = pos - ofs;\n \t\t\tArrayList r = baseByPos.get(base);\n \t\t\tif (r == null) {\n \t\t\t\tr = new ArrayList(8);\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java b/org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java\nnew file mode 100644\nindex 0000000..ac41f56\n--- /dev/null\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java\n@@ -0,0 +1,152 @@\n+/*\n+ * Copyright (C) 2009, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.transport;\n+\n+/**\n+ * Simple Map helper for {@link IndexPack}.\n+ *\n+ * @param \n+ * type of the value instance.\n+ */\n+final class LongMap {\n+\tprivate static final float LOAD_FACTOR = 0.75f;\n+\n+\tprivate Node[] table;\n+\n+\t/** Number of entries currently in the map. */\n+\tprivate int size;\n+\n+\t/** Next {@link #size} to trigger a {@link #grow()}. */\n+\tprivate int growAt;\n+\n+\tLongMap() {\n+\t\ttable = createArray(64);\n+\t\tgrowAt = (int) (table.length * LOAD_FACTOR);\n+\t}\n+\n+\tboolean containsKey(final long key) {\n+\t\treturn get(key) != null;\n+\t}\n+\n+\tV get(final long key) {\n+\t\tfor (Node n = table[index(key)]; n != null; n = n.next) {\n+\t\t\tif (n.key == key)\n+\t\t\t\treturn n.value;\n+\t\t}\n+\t\treturn null;\n+\t}\n+\n+\tV remove(final long key) {\n+\t\tNode n = table[index(key)];\n+\t\tNode prior = null;\n+\t\twhile (n != null) {\n+\t\t\tif (n.key == key) {\n+\t\t\t\tif (prior == null)\n+\t\t\t\t\ttable[index(key)] = n.next;\n+\t\t\t\telse\n+\t\t\t\t\tprior.next = n.next;\n+\t\t\t\tsize--;\n+\t\t\t\treturn n.value;\n+\t\t\t}\n+\t\t\tprior = n;\n+\t\t\tn = n.next;\n+\t\t}\n+\t\treturn null;\n+\t}\n+\n+\tV put(final long key, final V value) {\n+\t\tfor (Node n = table[index(key)]; n != null; n = n.next) {\n+\t\t\tif (n.key == key) {\n+\t\t\t\tfinal V o = n.value;\n+\t\t\t\tn.value = value;\n+\t\t\t\treturn o;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (++size == growAt)\n+\t\t\tgrow();\n+\t\tinsert(new Node(key, value));\n+\t\treturn null;\n+\t}\n+\n+\tprivate void insert(final Node n) {\n+\t\tfinal int idx = index(n.key);\n+\t\tn.next = table[idx];\n+\t\ttable[idx] = n;\n+\t}\n+\n+\tprivate void grow() {\n+\t\tfinal Node[] oldTable = table;\n+\t\tfinal int oldSize = table.length;\n+\n+\t\ttable = createArray(oldSize << 1);\n+\t\tgrowAt = (int) (table.length * LOAD_FACTOR);\n+\t\tfor (int i = 0; i < oldSize; i++) {\n+\t\t\tNode e = oldTable[i];\n+\t\t\twhile (e != null) {\n+\t\t\t\tfinal Node n = e.next;\n+\t\t\t\tinsert(e);\n+\t\t\t\te = n;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tprivate final int index(final long key) {\n+\t\tint h = ((int) key) >>> 1;\n+\t\th ^= (h >>> 20) ^ (h >>> 12);\n+\t\treturn h & (table.length - 1);\n+\t}\n+\n+\t@SuppressWarnings(\"unchecked\")\n+\tprivate static final Node[] createArray(final int sz) {\n+\t\treturn new Node[sz];\n+\t}\n+\n+\tprivate static class Node {\n+\t\tfinal long key;\n+\n+\t\tV value;\n+\n+\t\tNode next;\n+\n+\t\tNode(final long k, final V v) {\n+\t\t\tkey = k;\n+\t\t\tvalue = v;\n+\t\t}\n+\t}\n+}\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112665","messageId":"1241031288-23437-6-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-5-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 05/11] Change IndexPack to use ObjectIdSubclassMap instead of ObjectIdMap","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:42Z","receivedAt":"2009-04-29T18:54:42Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"The ObjectIdSubclassMap performs slightly better on average than the\nObjectIdMap, and uses a lot less memory as we don't need to allocate\na tree node per tracked object.\n\nThis reduces the memory footprint of IndexPack, by storing a linked\nlist of the UnresolvedDelta objects directly in each map, which is\nslightly smaller than using an ArrayList inside of a TreeMap.\n\nPerformance is marginally faster, but we now can declare ObjectIdMap\nto be fully deprecated and start removing it from the library.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n Unchanged.\n\n .../org/spearce/jgit/lib/ObjectIdSubclassMap.java | 31 +++++-\n .../src/org/spearce/jgit/transport/IndexPack.java | 123 +++++++++++++-------\n 2 files changed, 109 insertions(+), 45 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdSubclassMap.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdSubclassMap.java\nindex 2a13204..bdacec4 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdSubclassMap.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdSubclassMap.java\n@@ -37,6 +37,8 @@\n \n package org.spearce.jgit.lib;\n \n+import java.util.Iterator;\n+\n /**\n * Fast, efficient map specifically for {@link ObjectId} subclasses.\n *

\n@@ -51,7 +53,7 @@\n * @param \n * type of subclass of ObjectId that will be stored in the map.\n */\n-public class ObjectIdSubclassMap {\n+public class ObjectIdSubclassMap implements Iterable {\n \tprivate int size;\n \n \tprivate V[] obj_hash;\n@@ -114,6 +116,33 @@ public int size() {\n \t\treturn size;\n \t}\n \n+\tpublic Iterator iterator() {\n+\t\treturn new Iterator() {\n+\t\t\tprivate int found;\n+\n+\t\t\tprivate int i;\n+\n+\t\t\tpublic boolean hasNext() {\n+\t\t\t\treturn found < size;\n+\t\t\t}\n+\n+\t\t\tpublic V next() {\n+\t\t\t\twhile (i < obj_hash.length) {\n+\t\t\t\t\tfinal V v = obj_hash[i++];\n+\t\t\t\t\tif (v != null) {\n+\t\t\t\t\t\tfound++;\n+\t\t\t\t\t\treturn v;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t\tthrow new IllegalStateException();\n+\t\t\t}\n+\n+\t\t\tpublic void remove() {\n+\t\t\t\tthrow new UnsupportedOperationException();\n+\t\t\t}\n+\t\t};\n+\t}\n+\n \tprivate final int index(final AnyObjectId id) {\n \t\treturn (id.w1 >>> 1) % obj_hash.length;\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\nindex 59fdeae..eecad9c 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\n@@ -62,7 +62,7 @@\n import org.spearce.jgit.lib.MutableObjectId;\n import org.spearce.jgit.lib.ObjectChecker;\n import org.spearce.jgit.lib.ObjectId;\n-import org.spearce.jgit.lib.ObjectIdMap;\n+import org.spearce.jgit.lib.ObjectIdSubclassMap;\n import org.spearce.jgit.lib.ObjectLoader;\n import org.spearce.jgit.lib.PackIndexWriter;\n import org.spearce.jgit.lib.ProgressMonitor;\n@@ -160,9 +160,9 @@ public static IndexPack create(final Repository db, final InputStream is)\n \n \tprivate final CRC32 crc = new CRC32();\n \n-\tprivate ObjectIdMap> baseById;\n+\tprivate ObjectIdSubclassMap baseById;\n \n-\tprivate LongMap> baseByPos;\n+\tprivate LongMap baseByPos;\n \n \tprivate byte[] objectData;\n \n@@ -301,8 +301,8 @@ public void index(final ProgressMonitor progress) throws IOException {\n \t\t\t\treadPackHeader();\n \n \t\t\t\tentries = new PackedObjectInfo[(int) objectCount];\n-\t\t\t\tbaseById = new ObjectIdMap>();\n-\t\t\t\tbaseByPos = new LongMap>();\n+\t\t\t\tbaseById = new ObjectIdSubclassMap();\n+\t\t\t\tbaseByPos = new LongMap();\n \n \t\t\t\tprogress.beginTask(PROGRESS_DOWNLOAD, (int) objectCount);\n \t\t\t\tfor (int done = 0; done < objectCount; done++) {\n@@ -381,7 +381,7 @@ private void resolveDeltas(final ProgressMonitor progress)\n \n \tprivate void resolveDeltas(final PackedObjectInfo oe) throws IOException {\n \t\tfinal int oldCRC = oe.getCRC();\n-\t\tif (baseById.containsKey(oe) || baseByPos.containsKey(oe.getOffset()))\n+\t\tif (baseById.get(oe) != null || baseByPos.containsKey(oe.getOffset()))\n \t\t\tresolveDeltas(oe.getOffset(), oldCRC, Constants.OBJ_BAD, null, oe);\n \t}\n \n@@ -443,34 +443,45 @@ private void resolveDeltas(final long pos, final int oldCRC, int type,\n \t\tresolveChildDeltas(pos, type, data, oe);\n \t}\n \n+\tprivate UnresolvedDelta removeBaseById(final AnyObjectId id){\n+\t\tfinal DeltaChain d = baseById.get(id);\n+\t\treturn d != null ? d.remove() : null;\n+\t}\n+\n+\tprivate static UnresolvedDelta reverse(UnresolvedDelta c) {\n+\t\tUnresolvedDelta tail = null;\n+\t\twhile (c != null) {\n+\t\t\tfinal UnresolvedDelta n = c.next;\n+\t\t\tc.next = tail;\n+\t\t\ttail = c;\n+\t\t\tc = n;\n+\t\t}\n+\t\treturn tail;\n+\t}\n+\n \tprivate void resolveChildDeltas(final long pos, int type, byte[] data,\n \t\t\tPackedObjectInfo oe) throws IOException {\n-\t\tfinal ArrayList a = baseById.remove(oe);\n-\t\tfinal ArrayList b = baseByPos.remove(pos);\n-\t\tint ai = 0, bi = 0;\n-\t\tif (a != null && b != null) {\n-\t\t\twhile (ai < a.size() && bi < b.size()) {\n-\t\t\t\tfinal UnresolvedDelta ad = a.get(ai);\n-\t\t\t\tfinal UnresolvedDelta bd = b.get(bi);\n-\t\t\t\tif (ad.position < bd.position) {\n-\t\t\t\t\tresolveDeltas(ad.position, ad.crc, type, data, null);\n-\t\t\t\t\tai++;\n-\t\t\t\t} else {\n-\t\t\t\t\tresolveDeltas(bd.position, bd.crc, type, data, null);\n-\t\t\t\t\tbi++;\n-\t\t\t\t}\n+\t\tUnresolvedDelta a = reverse(removeBaseById(oe));\n+\t\tUnresolvedDelta b = reverse(baseByPos.remove(pos));\n+\t\twhile (a != null && b != null) {\n+\t\t\tif (a.position < b.position) {\n+\t\t\t\tresolveDeltas(a.position, a.crc, type, data, null);\n+\t\t\t\ta = a.next;\n+\t\t\t} else {\n+\t\t\t\tresolveDeltas(b.position, b.crc, type, data, null);\n+\t\t\t\tb = b.next;\n \t\t\t}\n \t\t}\n-\t\tif (a != null)\n-\t\t\twhile (ai < a.size()) {\n-\t\t\t\tfinal UnresolvedDelta ad = a.get(ai++);\n-\t\t\t\tresolveDeltas(ad.position, ad.crc, type, data, null);\n-\t\t\t}\n-\t\tif (b != null)\n-\t\t\twhile (bi < b.size()) {\n-\t\t\t\tfinal UnresolvedDelta bd = b.get(bi++);\n-\t\t\t\tresolveDeltas(bd.position, bd.crc, type, data, null);\n-\t\t\t}\n+\t\tresolveChildDeltaChain(type, data, a);\n+\t\tresolveChildDeltaChain(type, data, b);\n+\t}\n+\n+\tprivate void resolveChildDeltaChain(final int type, final byte[] data,\n+\t\t\tUnresolvedDelta a) throws IOException {\n+\t\twhile (a != null) {\n+\t\t\tresolveDeltas(a.position, a.crc, type, data, null);\n+\t\t\ta = a.next;\n+\t\t}\n \t}\n \n \tprivate void fixThinPack(final ProgressMonitor progress) throws IOException {\n@@ -479,11 +490,16 @@ private void fixThinPack(final ProgressMonitor progress) throws IOException {\n \t\tpackDigest.reset();\n \t\toriginalEOF = packOut.length() - 20;\n \t\tfinal Deflater def = new Deflater(Deflater.DEFAULT_COMPRESSION, false);\n+\t\tfinal List missing = new ArrayList(64);\n \t\tlong end = originalEOF;\n-\t\tfor (final ObjectId baseId : new ArrayList(baseById.keySet())) {\n+\t\tfor (final DeltaChain baseId : baseById) {\n+\t\t\tif (baseId.head == null)\n+\t\t\t\tcontinue;\n \t\t\tfinal ObjectLoader ldr = repo.openObject(readCurs, baseId);\n-\t\t\tif (ldr == null)\n+\t\t\tif (ldr == null) {\n+\t\t\t\tmissing.add(baseId);\n \t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tfinal byte[] data = ldr.getBytes();\n \t\t\tfinal int typeCode = ldr.getType();\n \t\t\tfinal PackedObjectInfo oe;\n@@ -501,9 +517,9 @@ private void fixThinPack(final ProgressMonitor progress) throws IOException {\n \t\t}\n \t\tdef.end();\n \n-\t\tif (!baseById.isEmpty()) {\n-\t\t\tfinal ObjectId need = baseById.keySet().iterator().next();\n-\t\t\tthrow new MissingObjectException(need, \"delta base\");\n+\t\tfor (final DeltaChain base : missing) {\n+\t\t\tif (base.head != null)\n+\t\t\t\tthrow new MissingObjectException(base, \"delta base\");\n \t\t}\n \n \t\tfixHeaderFooter(packcsum, packDigest.digest());\n@@ -678,13 +694,10 @@ private void indexOneObject() throws IOException {\n \t\t\t\tofs += (c & 127);\n \t\t\t}\n \t\t\tfinal long base = pos - ofs;\n-\t\t\tArrayList r = baseByPos.get(base);\n-\t\t\tif (r == null) {\n-\t\t\t\tr = new ArrayList(8);\n-\t\t\t\tbaseByPos.put(base, r);\n-\t\t\t}\n+\t\t\tfinal UnresolvedDelta n;\n \t\t\tskipInflateFromInput(sz);\n-\t\t\tr.add(new UnresolvedDelta(pos, (int) crc.getValue()));\n+\t\t\tn = new UnresolvedDelta(pos, (int) crc.getValue());\n+\t\t\tn.next = baseByPos.put(base, n);\n \t\t\tdeltaCount++;\n \t\t\tbreak;\n \t\t}\n@@ -693,10 +706,10 @@ private void indexOneObject() throws IOException {\n \t\t\tcrc.update(buf, c, 20);\n \t\t\tfinal ObjectId base = ObjectId.fromRaw(buf, c);\n \t\t\tuse(20);\n-\t\t\tArrayList r = baseById.get(base);\n+\t\t\tDeltaChain r = baseById.get(base);\n \t\t\tif (r == null) {\n-\t\t\t\tr = new ArrayList(8);\n-\t\t\t\tbaseById.put(base, r);\n+\t\t\t\tr = new DeltaChain(base);\n+\t\t\t\tbaseById.add(r);\n \t\t\t}\n \t\t\tskipInflateFromInput(sz);\n \t\t\tr.add(new UnresolvedDelta(pos, (int) crc.getValue()));\n@@ -937,11 +950,33 @@ private static CorruptObjectException corrupt(final DataFormatException dfe) {\n \t\t\t\t+ dfe.getMessage());\n \t}\n \n+\tprivate static class DeltaChain extends ObjectId {\n+\t\tUnresolvedDelta head;\n+\n+\t\tDeltaChain(final AnyObjectId id) {\n+\t\t\tsuper(id);\n+\t\t}\n+\n+\t\tUnresolvedDelta remove() {\n+\t\t\tfinal UnresolvedDelta r = head;\n+\t\t\tif (r != null)\n+\t\t\t\thead = null;\n+\t\t\treturn r;\n+\t\t}\n+\n+\t\tvoid add(final UnresolvedDelta d) {\n+\t\t\td.next = head;\n+\t\t\thead = d;\n+\t\t}\n+\t}\n+\n \tprivate static class UnresolvedDelta {\n \t\tfinal long position;\n \n \t\tfinal int crc;\n \n+\t\tUnresolvedDelta next;\n+\n \t\tUnresolvedDelta(final long headerOffset, final int crc32) {\n \t\t\tposition = headerOffset;\n \t\t\tcrc = crc32;\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112664","messageId":"1241031288-23437-7-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-6-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 06/11] Use getCachedBytes in IndexPack to avoid an unnecessary copy","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:43Z","receivedAt":"2009-04-29T18:54:43Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This is deep within the library code, where we know we won't overwrite\nthe cached buffer for an object. Using getCachedBytes saves a full\narray copy while fixing a thin pack and appending whole objects. The\nextra copy isn't so much an issue of CPU time as it is about creating\nunnecessary temporary garbage for the GC to clean up.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n Unchanged.\n\n .../src/org/spearce/jgit/transport/IndexPack.java | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\nindex eecad9c..eeeae16 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java\n@@ -500,7 +500,7 @@ private void fixThinPack(final ProgressMonitor progress) throws IOException {\n \t\t\t\tmissing.add(baseId);\n \t\t\t\tcontinue;\n \t\t\t}\n-\t\t\tfinal byte[] data = ldr.getBytes();\n+\t\t\tfinal byte[] data = ldr.getCachedBytes();\n \t\t\tfinal int typeCode = ldr.getType();\n \t\t\tfinal PackedObjectInfo oe;\n \n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112668","messageId":"1241031288-23437-8-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-7-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 07/11] Remove ObjectIdMap from the JGit library","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:44Z","receivedAt":"2009-04-29T18:54:44Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nobody within the library uses it anymore.\n\nApplications should consider ObjectIdSubclassMap, or just use a normal\nJDK map type like HashMap or TreeMap. In general ObjectIdSubclassMap\nsupports major map functionality, runs faster, and uses less memory for\nthe same sized data set.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n Unchanged.\n\n .../tst/org/spearce/jgit/lib/ObjectIdMapTest.java | 103 ----------\n .../src/org/spearce/jgit/lib/ObjectIdMap.java | 201 --------------------\n 2 files changed, 0 insertions(+), 304 deletions(-)\n delete mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java\n delete mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdMap.java\n\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java\ndeleted file mode 100644\nindex f1c1c0c..0000000\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java\n+++ /dev/null\n@@ -1,103 +0,0 @@\n-/*\n- * Copyright (C) 2008, Robin Rosenberg \n- *\n- * All rights reserved.\n- *\n- * Redistribution and use in source and binary forms, with or\n- * without modification, are permitted provided that the following\n- * conditions are met:\n- *\n- * - Redistributions of source code must retain the above copyright\n- * notice, this list of conditions and the following disclaimer.\n- *\n- * - Redistributions in binary form must reproduce the above\n- * copyright notice, this list of conditions and the following\n- * disclaimer in the documentation and/or other materials provided\n- * with the distribution.\n- *\n- * - Neither the name of the Git Development Community nor the\n- * names of its contributors may be used to endorse or promote\n- * products derived from this software without specific prior\n- * written permission.\n- *\n- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n- * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n- * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n- * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n- * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n- */\n-\n-package org.spearce.jgit.lib;\n-\n-import java.util.Arrays;\n-import java.util.Collection;\n-import java.util.Map;\n-import java.util.TreeMap;\n-\n-import junit.framework.TestCase;\n-\n-/**\n- * Test functionality of ObjectIdMap\n- *\n- * The reason this class exists is performance, but those figures\n- * are hard to make stable.\n- */\n-public class ObjectIdMapTest extends TestCase {\n-\n-\tObjectId[] ids = new ObjectId[500];\n-\t\n-\tprotected void setUp() throws Exception {\n-\t\tint b=0;\n-\t\tfor (int i=0; i\n- *\n- * All rights reserved.\n- *\n- * Redistribution and use in source and binary forms, with or\n- * without modification, are permitted provided that the following\n- * conditions are met:\n- *\n- * - Redistributions of source code must retain the above copyright\n- * notice, this list of conditions and the following disclaimer.\n- *\n- * - Redistributions in binary form must reproduce the above\n- * copyright notice, this list of conditions and the following\n- * disclaimer in the documentation and/or other materials provided\n- * with the distribution.\n- *\n- * - Neither the name of the Git Development Community nor the\n- * names of its contributors may be used to endorse or promote\n- * products derived from this software without specific prior\n- * written permission.\n- *\n- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n- * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n- * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n- * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n- * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n- */\n-\n-package org.spearce.jgit.lib;\n-\n-import java.lang.reflect.InvocationTargetException;\n-import java.lang.reflect.Method;\n-import java.util.AbstractMap;\n-import java.util.AbstractSet;\n-import java.util.Iterator;\n-import java.util.Map;\n-import java.util.Set;\n-import java.util.TreeMap;\n-\n-/**\n- * Very much like a map, but specialized to partition the data on the first byte\n- * of the key. This is about twice as fast. See test class.\n- *\n- * Inspiration is taken from the Git pack file format which uses this technique\n- * to improve lookup performance.\n- *\n- * @param \n- * The value we map ObjectId's to.\n- *\n- */\n-public class ObjectIdMap extends AbstractMap {\n-\n-\t@SuppressWarnings(\"unchecked\")\n-\tfinal Map[] level0 = new Map[256];\n-\t\n-\t/**\n-\t * Construct an ObjectIdMap with an underlying TreeMap implementation\n-\t */\n-\tpublic ObjectIdMap() {\n-\t\tthis(new TreeMap());\n-\t}\n-\n-\t/**\n-\t * Construct an ObjectIdMap with the same underlying map implementation as\n-\t * the provided example.\n-\t *\n-\t * @param sample\n-\t */\n-\t@SuppressWarnings(\"unchecked\")\n-\tpublic ObjectIdMap(Map sample) {\n-\t\ttry {\n-\t\t\tMethod m=sample.getClass().getMethod(\"clone\", (Class[])null);\n-\t\t\tfor (int i=0; i<256; ++i) {\n-\t\t\t\tlevel0[i] = (Map)m.invoke(sample, (Object[])null);\n-\t\t\t}\n-\t\t} catch (IllegalAccessException e) {\n-\t\t\tthrow new IllegalArgumentException(e);\n-\t\t} catch (IllegalArgumentException e) {\n-\t\t\tthrow new IllegalArgumentException(e);\n-\t\t} catch (InvocationTargetException e) {\n-\t\t\tthrow new IllegalArgumentException(e);\n-\t\t} catch (SecurityException e) {\n-\t\t\tthrow new IllegalArgumentException(e);\n-\t\t} catch (NoSuchMethodException e) {\n-\t\t\tthrow new IllegalArgumentException(e);\n-\t\t}\n-\t}\n-\t\n-\tpublic void clear() {\n-\t\tfor (int i=0; i<256; ++i)\n-\t\t\tlevel0[i].clear();\n-\t}\n-\n-\tpublic boolean containsKey(Object key) {\n-\t\treturn submap((ObjectId)key).containsKey(key);\n-\t}\n-\n-\tprivate final Map submap(ObjectId key) {\n-\t\treturn level0[key.getFirstByte()];\n-\t}\n-\n-\tpublic boolean containsValue(Object value) {\n-\t\tfor (int i=0; i<256; ++i)\n-\t\t\tif (level0[i].containsValue(value))\n-\t\t\t\treturn true;\n-\t\treturn false;\n-\t}\n-\n-\tprivate Set> entrySet =\n-\t\tnew AbstractSet>() {\n-\n-\t\t\t@Override\n-\t\t\tfinal public Iterator> iterator() {\n-\t\t\t\treturn new Iterator>() {\n-\t\t\t\t\tprivate int levelIndex;\n-\t\t\t\t\tprivate boolean hasNext;\n-\t\t\t\t\tprivate Iterator> levelIterator;\n-\t\t\t\t\tprivate Iterator> lastIterator;\n-\t\t\t\t\t{\n-\t\t\t\t\t\tstep();\n-\t\t\t\t\t}\n-\t\t\t\t\tpublic boolean hasNext() {\n-\t\t\t\t\t\treturn hasNext;\n-\t\t\t\t\t}\n-\t\t\t\t\tpublic java.util.Map.Entry next() {\n-\t\t\t\t\t\tEntry ret = levelIterator.next();\n-\t\t\t\t\t\tstep();\n-\t\t\t\t\t\treturn ret;\n-\t\t\t\t\t}\n-\t\t\t\t\tpublic void remove() {\n-\t\t\t\t\t\tlastIterator.remove();\n-\t\t\t\t\t}\n-\n-\t\t\t\t\tprivate void step() {\n-\t\t\t\t\t\thasNext = false;\n-\t\t\t\t\t\tlastIterator = levelIterator;\n-\t\t\t\t\t\twhile ((levelIterator==null || !(hasNext=levelIterator.hasNext()))) {\n-\t\t\t\t\t\t\tif (levelIndex < level0.length)\n-\t\t\t\t\t\t\t\tlevelIterator = level0[levelIndex++].entrySet().iterator();\n-\t\t\t\t\t\t\telse\n-\t\t\t\t\t\t\t\tbreak;\n-\t\t\t\t\t\t}\n-\t\t\t\t\t}\n-\t\t\t\t};\n-\t\t\t}\n-\n-\t\t\t@Override\n-\t\t\tpublic int size() {\n-\t\t\t\tint ret=0;\n-\t\t\t\tfor (int i=0; i<256; ++i)\n-\t\t\t\t\tret += level0[i].size();\n-\t\t\t\treturn ret;\n-\t\t\t}\n-\t};\n-\n-\n-\tpublic Set> entrySet() {\n-\t\treturn entrySet;\n-\t}\n-\n-\tpublic V get(Object key) {\n-\t\treturn submap((ObjectId)key).get(key);\n-\t}\n-\n-\tpublic boolean isEmpty() {\n-\t\tfor (int i=0; i<256; ++i)\n-\t\t\tif (!level0[i].isEmpty())\n-\t\t\t\treturn false;\n-\t\treturn true;\n-\t}\n-\n-\tpublic V put(ObjectId key, V value) {\n-\t\treturn submap(key).put(key, value);\n-\t}\n-\n-\tpublic void putAll(Map arg0) {\n-\t\tfor (Map.Entry entry : arg0.entrySet()) {\n-\t\t\tfinal ObjectId k = entry.getKey();\n-\t\t\tfinal V v = entry.getValue();\n-\t\t\tput(k,v);\n-\t\t}\n-\t}\n-\n-\tpublic V remove(Object key) {\n-\t\treturn submap((ObjectId) key).remove(key);\n-\t}\n-\n-\tpublic int size() {\n-\t\treturn entrySet().size();\n-\t}\n-\n-}\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112662","messageId":"1241031288-23437-9-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-8-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 08/11] Don't use ByteWindows when checking pack file headers/footers","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:45Z","receivedAt":"2009-04-29T18:54:45Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Its highly unlikely we need the 8 KiB surrounding the pack file header\nor footer immediately after opening the pack file. Reading those as\nfull blocks and registering them in the WindowCache is probably just\nchurning garbage through the cache. Instead, read the header with a\nsingle 12 byte read, and the footer with a single 20 byte read, and\nbypass the cache altogether.\n\nThis nicely removes a deadlock condition we had previously where the\nWindowCache was recursively calling itself during the pack file open,\nand got stuck on its own locks.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n Unchanged.\n\n .../src/org/spearce/jgit/lib/PackFile.java | 5 +--\n org.spearce.jgit/src/org/spearce/jgit/util/NB.java | 32 ++++++++++++++++++++\n 2 files changed, 34 insertions(+), 3 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\nindex 813ebc7..360442f 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n@@ -389,10 +389,9 @@ void allocWindow(final WindowCursor curs, final int windowId,\n \n \tprivate void onOpenPack() throws IOException {\n \t\tfinal PackIndex idx = idx();\n-\t\tfinal WindowCursor curs = new WindowCursor();\n \t\tfinal byte[] buf = new byte[20];\n \n-\t\treadFully(0, buf, 0, 12, curs);\n+\t\tNB.readFully(fd.getChannel(), 0, buf, 0, 12);\n \t\tif (RawParseUtils.match(buf, 0, Constants.PACK_SIGNATURE) != 4)\n \t\t\tthrow new IOException(\"Not a PACK file.\");\n \t\tfinal long vers = NB.decodeUInt32(buf, 4);\n@@ -406,7 +405,7 @@ private void onOpenPack() throws IOException {\n \t\t\t\t\t+ \" index \" + idx.getObjectCount()\n \t\t\t\t\t+ \": \" + getPackFile());\n \n-\t\treadFully(length - 20, buf, 0, 20, curs);\n+\t\tNB.readFully(fd.getChannel(), length - 20, buf, 0, 20);\n \t\tif (!Arrays.equals(buf, idx.packChecksum))\n \t\t\tthrow new PackMismatchException(\"Pack checksum mismatch:\"\n \t\t\t\t\t+ \" pack \" + ObjectId.fromRaw(buf).name()\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\nindex c65c6fa..032997f 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\n@@ -40,6 +40,8 @@\n import java.io.EOFException;\n import java.io.IOException;\n import java.io.InputStream;\n+import java.nio.ByteBuffer;\n+import java.nio.channels.FileChannel;\n \n /** Conversion utilities for network byte order handling. */\n public final class NB {\n@@ -71,6 +73,36 @@ public static void readFully(final InputStream fd, final byte[] dst,\n \t}\n \n \t/**\n+\t * Read the entire byte array into memory, or throw an exception.\n+\t *\n+\t * @param fd\n+\t * file to read the data from.\n+\t * @param pos\n+\t * position to read from the file at.\n+\t * @param dst\n+\t * buffer that must be fully populated, [off, off+len).\n+\t * @param off\n+\t * position within the buffer to start writing to.\n+\t * @param len\n+\t * number of bytes that must be read.\n+\t * @throws EOFException\n+\t * the stream ended before dst was fully populated.\n+\t * @throws IOException\n+\t * there was an error reading from the stream.\n+\t */\n+\tpublic static void readFully(final FileChannel fd, long pos,\n+\t\t\tfinal byte[] dst, int off, int len) throws IOException {\n+\t\twhile (len > 0) {\n+\t\t\tfinal int r = fd.read(ByteBuffer.wrap(dst, off, len), pos);\n+\t\t\tif (r <= 0)\n+\t\t\t\tthrow new EOFException(\"Short read of block.\");\n+\t\t\tpos += r;\n+\t\t\toff += r;\n+\t\t\tlen -= r;\n+\t\t}\n+\t}\n+\n+\t/**\n \t * Skip an entire region of an input stream.\n \t *

\n \t * The input stream's position is moved forward by the number of requested\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112670","messageId":"1241031288-23437-10-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-9-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH v2 09/11] Rewrite WindowCache to be easier to follow and maintain","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:46Z","receivedAt":"2009-04-29T18:54:46Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"The integration of WindowCache, ByteWindow, PackFile and WindowCursor\nwas a spaghetti of code that was impossible for even the original\nauthor (me) to follow. Due to the way the responsibility for the\nPackFile's open RandomAccessFile \"fd\" was distributed between these\nfour classes I could no longer prove to myself that the fd wouldn't\nbe closed while it was being accessed by another thread.\n\nThis rewrite generalizes most of the cache logic into a new class,\nOffsetCache. The hope is that we can later reuse this code to make\na rewrite of UnpackedObjectCache, which uses similiar caching rules\nas WindowCache, but applies a different hash function. That rewrite\nis deferred to another change, but is anticipated by this one.\n\nThe new OffsetCache class uses the Java 5 atomic APIs to create a\nmuch more concurrent hash table than we had before. We can now\nperform no-miss reads without taking any locks. Reads that do\nmiss acquire a lock in order to prevent concurrent threads from\nperforming duplicate work loading the same window from disk,\nhowever concurrent reads of different windows is still permitted.\n\nDue to the more concurrent nature of the OffsetCache, it is now\npossible for the cache to temporarily overshoot its resource limits.\nThis is a small temporary overshoot that is roughly bounded by the\nnumber of concurrent threads operating against the same cache.\n\nThe API of the ByteWindow subclasses is now simplified by removing\nthe base class of SoftReference. It was a horrible idea to pass\nthe byte[] or MappedByteBuffer down through the call stack when the\nimplementation knew what type it should be operating on. We now\ninstead use a more traditional OO pattern of allowing the subclass\nto directly specify its referent.\n\nResponsibility for the RandomAccessFile \"fd\" within PackFile is now\nstrictly within PackFile. Two open reference counts track how the\ncallers are using the fd, ensuring that the fd remains open, so long\nas the caller has made the appropriate begin*() invocation prior\nto data access. One counter, beginWindowCache() is exclusively\nfor the ByteWindows created by WindowCache. Another counter,\nbeginCopyRawData(), is exclusively for PackWriter's need to lock\nthe PackFile open while it performs object reuse.\n\nTo keep the code simple a WindowCache.reconfigure() now discards the\nentire current cache, and creates a new one. That invalidates every\nopen file, and every open ByteWindow, and forces them to load again.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n I squashed a lot of the follow-up patches into this one. They were\n all bug fixes to code introduced in this change anyway.\n\n .../org/spearce/jgit/lib/ConcurrentRepackTest.java | 4 -\n .../src/org/spearce/jgit/lib/ByteArrayWindow.java | 57 +--\n .../src/org/spearce/jgit/lib/ByteBufferWindow.java | 41 +-\n .../src/org/spearce/jgit/lib/ByteWindow.java | 91 +---\n .../src/org/spearce/jgit/lib/OffsetCache.java | 534 ++++++++++++++++++++\n .../src/org/spearce/jgit/lib/PackFile.java | 123 +++--\n .../org/spearce/jgit/lib/PackedObjectLoader.java | 4 +-\n .../src/org/spearce/jgit/lib/WindowCache.java | 418 ++++------------\n .../src/org/spearce/jgit/lib/WindowCursor.java | 42 +-\n 9 files changed, 787 insertions(+), 527 deletions(-)\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java\n\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ConcurrentRepackTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ConcurrentRepackTest.java\nindex b56e0f4..fa6345e 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ConcurrentRepackTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ConcurrentRepackTest.java\n@@ -170,10 +170,6 @@ public void testObjectMovedToNewPack2()\n \n \tprivate static void whackCache() {\n \t\tfinal WindowCacheConfig config = new WindowCacheConfig();\n-\n-\t\tconfig.setPackedGitOpenFiles(0);\n-\t\tWindowCache.reconfigure(config);\n-\n \t\tconfig.setPackedGitOpenFiles(1);\n \t\tWindowCache.reconfigure(config);\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\nindex 5dc3d28..6b96b10 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\n@@ -38,41 +38,29 @@\n \n package org.spearce.jgit.lib;\n \n-import java.io.IOException;\n-import java.nio.ByteBuffer;\n import java.util.zip.DataFormatException;\n import java.util.zip.Inflater;\n \n /**\n * A {@link ByteWindow} with an underlying byte array for storage.\n */\n-final class ByteArrayWindow extends ByteWindow {\n-\tboolean loaded;\n+final class ByteArrayWindow extends ByteWindow {\n+\tprivate final byte[] array;\n \n-\t/**\n-\t * Constructor for ByteWindow.\n-\t * \n-\t * @param o\n-\t * the PackFile providing data access\n-\t * @param p\n-\t * the file offset.\n-\t * @param d\n-\t * an id provided by the PackFile. See\n-\t * {@link WindowCache#get(WindowCursor, PackFile, long)}.\n-\t * @param b\n-\t * byte array for storage\n-\t */\n-\tByteArrayWindow(final PackFile o, final long p, final int d, final byte[] b) {\n-\t\tsuper(o, p, d, b, b.length);\n+\tByteArrayWindow(final PackFile pack, final long o, final byte[] b) {\n+\t\tsuper(pack, o, b.length);\n+\t\tarray = b;\n \t}\n \n-\tint copy(final byte[] array, final int p, final byte[] b, final int o, int n) {\n+\t@Override\n+\tprotected int copy(final int p, final byte[] b, final int o, int n) {\n \t\tn = Math.min(array.length - p, n);\n \t\tSystem.arraycopy(array, p, b, o, n);\n \t\treturn n;\n \t}\n \n-\tint inflate(final byte[] array, final int pos, final byte[] b, int o,\n+\t@Override\n+\tprotected int inflate(final int pos, final byte[] b, int o,\n \t\t\tfinal Inflater inf) throws DataFormatException {\n \t\twhile (!inf.finished()) {\n \t\t\tif (inf.needsInput()) {\n@@ -86,7 +74,8 @@ int inflate(final byte[] array, final int pos, final byte[] b, int o,\n \t\treturn o;\n \t}\n \n-\tvoid inflateVerify(final byte[] array, final int pos, final Inflater inf)\n+\t@Override\n+\tprotected void inflateVerify(final int pos, final Inflater inf)\n \t\t\tthrows DataFormatException {\n \t\twhile (!inf.finished()) {\n \t\t\tif (inf.needsInput()) {\n@@ -98,26 +87,4 @@ void inflateVerify(final byte[] array, final int pos, final Inflater inf)\n \t\twhile (!inf.finished() && !inf.needsInput())\n \t\t\tinf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);\n \t}\n-\n-\tvoid ensureLoaded(final byte[] array) {\n-\t\tboolean release = false;\n-\t\ttry {\n-\t\t\tsynchronized (this) {\n-\t\t\t\tif (!loaded) {\n-\t\t\t\t\trelease = true;\n-\t\t\t\t\ttry {\n-\t\t\t\t\t\tprovider.fd.getChannel().read(ByteBuffer.wrap(array),\n-\t\t\t\t\t\t\t\tstart);\n-\t\t\t\t\t} catch (IOException e) {\n-\t\t\t\t\t\tthrow new RuntimeException(\"Cannot fault in window\", e);\n-\t\t\t\t\t}\n-\t\t\t\t\tloaded = true;\n-\t\t\t\t}\n-\t\t\t}\n-\t\t} finally {\n-\t\t\tif (release) {\n-\t\t\t\tWindowCache.markLoaded(this);\n-\t\t\t}\n-\t\t}\n-\t}\n-}\n\\ No newline at end of file\n+}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java\nindex 01956fd..f9de9b4 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java\n@@ -47,24 +47,16 @@\n *\n * @see ByteWindow\n */\n-final class ByteBufferWindow extends ByteWindow {\n-\t/**\n-\t * Constructor.\n-\t *\n-\t * @See ByteWindow\n-\t *\n-\t * @param o The PackFile\n-\t * @param p the file offset.\n-\t * @param d Window id\n-\t * @param b ByteBuffer storage\n-\t */\n-\tByteBufferWindow(final PackFile o, final long p, final int d,\n-\t\t\tfinal ByteBuffer b) {\n-\t\tsuper(o, p, d, b, b.capacity());\n+final class ByteBufferWindow extends ByteWindow {\n+\tprivate final ByteBuffer buffer;\n+\n+\tByteBufferWindow(final PackFile pack, final long o, final ByteBuffer b) {\n+\t\tsuper(pack, o, b.capacity());\n+\t\tbuffer = b;\n \t}\n \n-\tfinal int copy(final ByteBuffer buffer, final int p, final byte[] b,\n-\t\t\tfinal int o, int n) {\n+\t@Override\n+\tprotected int copy(final int p, final byte[] b, final int o, int n) {\n \t\tfinal ByteBuffer s = buffer.slice();\n \t\ts.position(p);\n \t\tn = Math.min(s.remaining(), n);\n@@ -72,9 +64,9 @@ final int copy(final ByteBuffer buffer, final int p, final byte[] b,\n \t\treturn n;\n \t}\n \n-\tint inflate(final ByteBuffer buffer, final int pos, final byte[] b, int o,\n-\t\t\tfinal Inflater inf)\n-\t\t\tthrows DataFormatException {\n+\t@Override\n+\tprotected int inflate(final int pos, final byte[] b, int o,\n+\t\t\tfinal Inflater inf) throws DataFormatException {\n \t\tfinal byte[] tmp = new byte[512];\n \t\tfinal ByteBuffer s = buffer.slice();\n \t\ts.position(pos);\n@@ -91,8 +83,9 @@ int inflate(final ByteBuffer buffer, final int pos, final byte[] b, int o,\n \t\treturn o;\n \t}\n \n-\tvoid inflateVerify(final ByteBuffer buffer, final int pos,\n-\t\t\tfinal Inflater inf) throws DataFormatException {\n+\t@Override\n+\tprotected void inflateVerify(final int pos, final Inflater inf)\n+\t\t\tthrows DataFormatException {\n \t\tfinal byte[] tmp = new byte[512];\n \t\tfinal ByteBuffer s = buffer.slice();\n \t\ts.position(pos);\n@@ -107,8 +100,4 @@ void inflateVerify(final ByteBuffer buffer, final int pos,\n \t\twhile (!inf.finished() && !inf.needsInput())\n \t\t\tinf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);\n \t}\n-\n-\tvoid ensureLoaded(final ByteBuffer ref) {\n-\t\t// Do nothing.\n-\t}\n-}\n\\ No newline at end of file\n+}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\nindex 0d01fca..e0bda2d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n@@ -38,8 +38,6 @@\n \n package org.spearce.jgit.lib;\n \n-import java.lang.ref.ReferenceQueue;\n-import java.lang.ref.SoftReference;\n import java.util.zip.DataFormatException;\n import java.util.zip.Inflater;\n \n@@ -51,64 +49,31 @@\n * is very low and has paged part of this process out to disk. Therefore copying\n * bytes from a window is very inexpensive.\n *

\n- * \n- * @param \n- * type of object reference used to manage the window data.\n */\n-abstract class ByteWindow extends SoftReference {\n-\tboolean sizeActive = true;\n+abstract class ByteWindow {\n+\tprotected final PackFile pack;\n \n-\tByteWindow chainNext;\n+\tprotected final long start;\n \n-\tByteWindow lruPrev;\n+\tprotected final long end;\n \n-\tByteWindow lruNext;\n-\n-\tfinal PackFile provider;\n-\n-\tfinal int id;\n-\n-\tfinal int size;\n-\n-\tfinal long start;\n-\n-\tfinal long end;\n+\tprotected ByteWindow(final PackFile p, final long s, final int n) {\n+\t\tpack = p;\n+\t\tstart = s;\n+\t\tend = start + n;\n+\t}\n \n-\t/**\n-\t * Constructor for ByteWindow.\n-\t * \n-\t * @param o\n-\t * the PackFile providing data access\n-\t * @param pos\n-\t * the position in the file the data comes from.\n-\t * @param d\n-\t * an id provided by the PackFile. See\n-\t * {@link WindowCache#get(WindowCursor, PackFile, long)}.\n-\t * @param ref\n-\t * the object value required to perform data access.\n-\t * @param sz\n-\t * the total number of bytes in this window.\n-\t */\n-\t@SuppressWarnings(\"unchecked\")\n-\tByteWindow(final PackFile o, final long pos, final int d, final T ref,\n-\t\t\tfinal int sz) {\n-\t\tsuper(ref, (ReferenceQueue) WindowCache.clearedWindowQueue);\n-\t\tprovider = o;\n-\t\tsize = sz;\n-\t\tid = d;\n-\t\tstart = pos;\n-\t\tend = start + size;\n+\tfinal int size() {\n+\t\treturn (int) (end - start);\n \t}\n \n \tfinal boolean contains(final PackFile neededFile, final long neededPos) {\n-\t\treturn provider == neededFile && start <= neededPos && neededPos < end;\n+\t\treturn pack == neededFile && start <= neededPos && neededPos < end;\n \t}\n \n \t/**\n \t * Copy bytes from the window to a caller supplied buffer.\n \t * \n-\t * @param ref\n-\t * the object value required to perform data access.\n \t * @param pos\n \t * offset within the file to start copying from.\n \t * @param dstbuf\n@@ -123,15 +88,13 @@ final boolean contains(final PackFile neededFile, final long neededPos) {\n \t * cnt if cnt exceeded the number of\n \t * bytes available.\n \t */\n-\tfinal int copy(T ref, long pos, byte[] dstbuf, int dstoff, int cnt) {\n-\t\treturn copy(ref, (int) (pos - start), dstbuf, dstoff, cnt);\n+\tfinal int copy(long pos, byte[] dstbuf, int dstoff, int cnt) {\n+\t\treturn copy((int) (pos - start), dstbuf, dstoff, cnt);\n \t}\n \n \t/**\n \t * Copy bytes from the window to a caller supplied buffer.\n \t * \n-\t * @param ref\n-\t * the object value required to perform data access.\n \t * @param pos\n \t * offset within the window to start copying from.\n \t * @param dstbuf\n@@ -146,15 +109,13 @@ final int copy(T ref, long pos, byte[] dstbuf, int dstoff, int cnt) {\n \t * cnt if cnt exceeded the number of\n \t * bytes available.\n \t */\n-\tabstract int copy(T ref, int pos, byte[] dstbuf, int dstoff, int cnt);\n+\tprotected abstract int copy(int pos, byte[] dstbuf, int dstoff, int cnt);\n \n \t/**\n \t * Pump bytes into the supplied inflater as input.\n \t * \n-\t * @param ref\n-\t * the object value required to perform data access.\n \t * @param pos\n-\t * offset within the window to start supplying input from.\n+\t * offset within the file to start supplying input from.\n \t * @param dstbuf\n \t * destination buffer the inflater should output decompressed\n \t * data to.\n@@ -174,16 +135,14 @@ final int copy(T ref, long pos, byte[] dstbuf, int dstoff, int cnt) {\n \t * the inflater encountered an invalid chunk of data. Data\n \t * stream corruption is likely.\n \t */\n-\tfinal int inflate(T ref, long pos, byte[] dstbuf, int dstoff, Inflater inf)\n+\tfinal int inflate(long pos, byte[] dstbuf, int dstoff, Inflater inf)\n \t\t\tthrows DataFormatException {\n-\t\treturn inflate(ref, (int) (pos - start), dstbuf, dstoff, inf);\n+\t\treturn inflate((int) (pos - start), dstbuf, dstoff, inf);\n \t}\n \n \t/**\n \t * Pump bytes into the supplied inflater as input.\n \t * \n-\t * @param ref\n-\t * the object value required to perform data access.\n \t * @param pos\n \t * offset within the window to start supplying input from.\n \t * @param dstbuf\n@@ -205,18 +164,16 @@ final int inflate(T ref, long pos, byte[] dstbuf, int dstoff, Inflater inf)\n \t * the inflater encountered an invalid chunk of data. Data\n \t * stream corruption is likely.\n \t */\n-\tabstract int inflate(T ref, int pos, byte[] dstbuf, int dstoff, Inflater inf)\n-\t\t\tthrows DataFormatException;\n+\tprotected abstract int inflate(int pos, byte[] dstbuf, int dstoff,\n+\t\t\tInflater inf) throws DataFormatException;\n \n \tprotected static final byte[] verifyGarbageBuffer = new byte[2048];\n \n-\tfinal void inflateVerify(T ref, long pos, Inflater inf)\n+\tfinal void inflateVerify(final long pos, final Inflater inf)\n \t\t\tthrows DataFormatException {\n-\t\tinflateVerify(ref, (int) (pos - start), inf);\n+\t\tinflateVerify((int) (pos - start), inf);\n \t}\n \n-\tabstract void inflateVerify(T ref, int pos, Inflater inf)\n+\tprotected abstract void inflateVerify(int pos, Inflater inf)\n \t\t\tthrows DataFormatException;\n-\n-\tabstract void ensureLoaded(T ref);\n-}\n\\ No newline at end of file\n+}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java\nnew file mode 100644\nindex 0000000..a1cd4be\n--- /dev/null\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java\n@@ -0,0 +1,534 @@\n+/*\n+ * Copyright (C) 2009, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.lib;\n+\n+import java.io.IOException;\n+import java.lang.ref.ReferenceQueue;\n+import java.lang.ref.SoftReference;\n+import java.util.Random;\n+import java.util.concurrent.atomic.AtomicLong;\n+import java.util.concurrent.atomic.AtomicReferenceArray;\n+import java.util.concurrent.locks.ReentrantLock;\n+\n+/**\n+ * Least frequently used cache for objects specified by PackFile positions.\n+ *

\n+ * This cache maps a ({@link PackFile},position) tuple to an Object.\n+ *

\n+ * This cache is suitable for objects that are \"relative expensive\" to compute\n+ * from the underlying PackFile, given some known position in that file.\n+ *

\n+ * Whenever a cache miss occurs, {@link #load(PackFile, long)} is invoked by\n+ * exactly one thread for the given (PackFile,position) key tuple.\n+ * This is ensured by an array of locks, with the tuple hashed to a lock\n+ * instance.\n+ *

\n+ * During a miss, older entries are evicted from the cache so long as\n+ * {@link #isFull()} returns true.\n+ *

\n+ * Its too expensive during object access to be 100% accurate with a least\n+ * recently used (LRU) algorithm. Strictly ordering every read is a lot of\n+ * overhead that typically doesn't yield a corresponding benefit to the\n+ * application.\n+ *

\n+ * This cache implements a loose LRU policy by randomly picking a window\n+ * comprised of roughly 10% of the cache, and evicting the oldest accessed entry\n+ * within that window.\n+ *

\n+ * Entities created by the cache are held under SoftReferences, permitting the\n+ * Java runtime's garbage collector to evict entries when heap memory gets low.\n+ * Most JREs implement a loose least recently used algorithm for this eviction.\n+ *

\n+ * The internal hash table does not expand at runtime, instead it is fixed in\n+ * size at cache creation time. The internal lock table used to gate load\n+ * invocations is also fixed in size.\n+ *

\n+ * The key tuple is passed through to methods as a pair of parameters rather\n+ * than as a single Object, thus reducing the transient memory allocations of\n+ * callers. It is more efficient to avoid the allocation, as we can't be 100%\n+ * sure that a JIT would be able to stack-allocate a key tuple.\n+ *

\n+ * This cache has an implementation rule such that:\n+ *

    \n+ *
  • {@link #load(PackFile, long)} is invoked by at most one thread at a time\n+ * for a given (PackFile,position) tuple.
    • \n+ *
  • For every load() invocation there is exactly one\n+ * {@link #createRef(PackFile, long, Object)} invocation to wrap a SoftReference\n+ * around the cached entity.
    • \n+ *
  • For every Reference created by createRef() there will be\n+ * exactly one call to {@link #clear(Ref)} to cleanup any resources associated\n+ * with the (now expired) cached entity.
    • \n+ *
\n+ *

\n+ * Therefore, it is safe to perform resource accounting increments during the\n+ * {@link #load(PackFile, long)} or {@link #createRef(PackFile, long, Object)}\n+ * methods, and matching decrements during {@link #clear(Ref)}. Implementors may\n+ * need to override {@link #createRef(PackFile, long, Object)} in order to embed\n+ * additional accounting information into an implementation specific\n+ * {@link OffsetCache.Ref} subclass, as the cached entity may have already been\n+ * evicted by the JRE's garbage collector.\n+ *

\n+ * To maintain higher concurrency workloads, during eviction only one thread\n+ * performs the eviction work, while other threads can continue to insert new\n+ * objects in parallel. This means that the cache can be temporarily over limit,\n+ * especially if the nominated eviction thread is being starved relative to the\n+ * other threads.\n+ *\n+ * @param \n+ * type of value stored in the cache.\n+ * @param \n+ * type of {@link OffsetCache.Ref} subclass used by the cache.\n+ */\n+abstract class OffsetCache> {\n+\tprivate static final Random rng = new Random();\n+\n+\t/** ReferenceQueue that {@link #createRef(PackFile, long, Object)} must use. */\n+\tprotected final ReferenceQueue queue;\n+\n+\t/** Number of entries in {@link #table}. */\n+\tprivate final int tableSize;\n+\n+\t/** Access clock for loose LRU. */\n+\tprivate final AtomicLong clock;\n+\n+\t/** Hash bucket directory; entries are chained below. */\n+\tprivate final AtomicReferenceArray> table;\n+\n+\t/** Locks to prevent concurrent loads for same (PackFile,position). */\n+\tprivate final Lock[] locks;\n+\n+\t/** Lock to elect the eviction thread after a load occurs. */\n+\tprivate final ReentrantLock evictLock;\n+\n+\t/** Number of {@link #table} buckets to scan for an eviction window. */\n+\tprivate final int evictBatch;\n+\n+\t/**\n+\t * Create a new cache with a fixed size entry table and lock table.\n+\t *\n+\t * @param tSize\n+\t * number of entries in the entry hash table.\n+\t * @param lockCount\n+\t * number of entries in the lock table. This is the maximum\n+\t * concurrency rate for creation of new objects through\n+\t * {@link #load(PackFile, long)} invocations.\n+\t */\n+\tOffsetCache(final int tSize, final int lockCount) {\n+\t\tif (tSize < 1)\n+\t\t\tthrow new IllegalArgumentException(\"tSize must be >= 1\");\n+\t\tif (lockCount < 1)\n+\t\t\tthrow new IllegalArgumentException(\"lockCount must be >= 1\");\n+\n+\t\tqueue = new ReferenceQueue();\n+\t\ttableSize = tSize;\n+\t\tclock = new AtomicLong(1);\n+\t\ttable = new AtomicReferenceArray>(tableSize);\n+\t\tlocks = new Lock[lockCount];\n+\t\tfor (int i = 0; i < locks.length; i++)\n+\t\t\tlocks[i] = new Lock();\n+\t\tevictLock = new ReentrantLock();\n+\n+\t\tint eb = (int) (tableSize * .1);\n+\t\tif (64 < eb)\n+\t\t\teb = 64;\n+\t\telse if (eb < 4)\n+\t\t\teb = 4;\n+\t\tif (tableSize < eb)\n+\t\t\teb = tableSize;\n+\t\tevictBatch = eb;\n+\t}\n+\n+\t/**\n+\t * Lookup a cached object, creating and loading it if it doesn't exist.\n+\t *\n+\t * @param pack\n+\t * the pack that \"contains\" the cached object.\n+\t * @param position\n+\t * offset within pack of the object.\n+\t * @return the object reference.\n+\t * @throws IOException\n+\t * the object reference was not in the cache and could not be\n+\t * obtained by {@link #load(PackFile, long)}.\n+\t */\n+\tV getOrLoad(final PackFile pack, final long position) throws IOException {\n+\t\tfinal int slot = slot(pack, position);\n+\t\tfinal Entry e1 = table.get(slot);\n+\t\tV v = scan(e1, pack, position);\n+\t\tif (v != null)\n+\t\t\treturn v;\n+\n+\t\tsynchronized (lock(pack, position)) {\n+\t\t\tEntry e2 = table.get(slot);\n+\t\t\tif (e2 != e1) {\n+\t\t\t\tv = scan(e2, pack, position);\n+\t\t\t\tif (v != null)\n+\t\t\t\t\treturn v;\n+\t\t\t}\n+\n+\t\t\tv = load(pack, position);\n+\t\t\tfinal Ref ref = createRef(pack, position, v);\n+\t\t\thit(ref);\n+\t\t\tfor (;;) {\n+\t\t\t\tfinal Entry n = new Entry(clean(e2), ref);\n+\t\t\t\tif (table.compareAndSet(slot, e2, n))\n+\t\t\t\t\tbreak;\n+\t\t\t\te2 = table.get(slot);\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (evictLock.tryLock()) {\n+\t\t\ttry {\n+\t\t\t\tgc();\n+\t\t\t\tevict();\n+\t\t\t} finally {\n+\t\t\t\tevictLock.unlock();\n+\t\t\t}\n+\t\t}\n+\n+\t\treturn v;\n+\t}\n+\n+\tprivate V scan(Entry n, final PackFile pack, final long position) {\n+\t\tfor (; n != null; n = n.next) {\n+\t\t\tfinal Ref r = n.ref;\n+\t\t\tif (r.pack == pack && r.position == position) {\n+\t\t\t\tfinal V v = r.get();\n+\t\t\t\tif (v != null) {\n+\t\t\t\t\thit(r);\n+\t\t\t\t\treturn v;\n+\t\t\t\t}\n+\t\t\t\tn.kill();\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t\treturn null;\n+\t}\n+\n+\tprivate void hit(final Ref r) {\n+\t\t// We don't need to be 100% accurate here. Its sufficient that at least\n+\t\t// one thread performs the increment. Any other concurrent access at\n+\t\t// exactly the same time can simply use the same clock value.\n+\t\t//\n+\t\t// Consequently we attempt the set, but we don't try to recover should\n+\t\t// it fail. This is why we don't use getAndIncrement() here.\n+\t\t//\n+\t\tfinal long c = clock.get();\n+\t\tclock.compareAndSet(c, c + 1);\n+\t\tr.lastAccess = c;\n+\t}\n+\n+\tprivate void evict() {\n+\t\tfinal int start = rng.nextInt(tableSize);\n+\t\tint ptr = start;\n+\t\twhile (isFull()) {\n+\t\t\tEntry old = null;\n+\t\t\tint slot = 0;\n+\t\t\tfor (int b = evictBatch - 1; b >= 0; b--) {\n+\t\t\t\tif (tableSize <= ptr)\n+\t\t\t\t\tptr = 0;\n+\t\t\t\tfor (Entry e = table.get(ptr); e != null; e = e.next) {\n+\t\t\t\t\tif (e.dead)\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t\tif (old == null || e.ref.lastAccess < old.ref.lastAccess) {\n+\t\t\t\t\t\told = e;\n+\t\t\t\t\t\tslot = ptr;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t\tif (++ptr == start)\n+\t\t\t\t\treturn;\n+\t\t\t}\n+\t\t\tif (old != null) {\n+\t\t\t\told.kill();\n+\t\t\t\tgc();\n+\t\t\t\tfinal Entry e1 = table.get(slot);\n+\t\t\t\ttable.compareAndSet(slot, e1, clean(e1));\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/**\n+\t * Clear every entry from the cache.\n+\t *

\n+\t * This is a last-ditch effort to clear out the cache, such as before it\n+\t * gets replaced by another cache that is configured differently. This\n+\t * method tries to force every cached entry through {@link #clear(Ref)} to\n+\t * ensure that resources are correctly accounted for and cleaned up by the\n+\t * subclass. A concurrent reader loading entries while this method is\n+\t * running may cause resource accounting failures.\n+\t */\n+\tvoid removeAll() {\n+\t\tfor (int s = 0; s < tableSize; s++) {\n+\t\t\tEntry e1;\n+\t\t\tdo {\n+\t\t\t\te1 = table.get(s);\n+\t\t\t\tfor (Entry e = e1; e != null; e = e.next)\n+\t\t\t\t\te.kill();\n+\t\t\t} while (!table.compareAndSet(s, e1, null));\n+\t\t}\n+\t\tgc();\n+\t}\n+\n+\t/**\n+\t * Clear all entries related to a single file.\n+\t *

\n+\t * Typically this method is invoked during {@link PackFile#close()}, when we\n+\t * know the pack is never going to be useful to us again (for example, it no\n+\t * longer exists on disk). A concurrent reader loading an entry from this\n+\t * same pack may cause the pack to become stuck in the cache anyway.\n+\t *\n+\t * @param pack\n+\t * the file to purge all entries of.\n+\t */\n+\tvoid removeAll(final PackFile pack) {\n+\t\tfor (int s = 0; s < tableSize; s++) {\n+\t\t\tfinal Entry e1 = table.get(s);\n+\t\t\tboolean hasDead = false;\n+\t\t\tfor (Entry e = e1; e != null; e = e.next) {\n+\t\t\t\tif (e.ref.pack == pack) {\n+\t\t\t\t\te.kill();\n+\t\t\t\t\thasDead = true;\n+\t\t\t\t} else if (e.dead)\n+\t\t\t\t\thasDead = true;\n+\t\t\t}\n+\t\t\tif (hasDead)\n+\t\t\t\ttable.compareAndSet(s, e1, clean(e1));\n+\t\t}\n+\t\tgc();\n+\t}\n+\n+\t/**\n+\t * Materialize an object that doesn't yet exist in the cache.\n+\t *

\n+\t * This method is invoked by {@link #getOrLoad(PackFile, long)} when the\n+\t * specified entity does not yet exist in the cache. Internal locking\n+\t * ensures that at most one thread can call this method for each unique\n+\t * (pack,position), but multiple threads can call this method\n+\t * concurrently for different (pack,position) tuples.\n+\t *\n+\t * @param pack\n+\t * the file to materialize the entry from.\n+\t * @param position\n+\t * offset within the file of the entry.\n+\t * @return the materialized object. Must never be null.\n+\t * @throws IOException\n+\t * the method was unable to materialize the object for this\n+\t * input pair. The usual reasons would be file corruption, file\n+\t * not found, out of file descriptors, etc.\n+\t */\n+\tprotected abstract V load(PackFile pack, long position) throws IOException;\n+\n+\t/**\n+\t * Construct a Ref (SoftReference) around a cached entity.\n+\t *

\n+\t * Implementing this is only necessary if the subclass is performing\n+\t * resource accounting during {@link #load(PackFile, long)} and\n+\t * {@link #clear(Ref)} requires some information to update the accounting.\n+\t *

\n+\t * Implementors MUST ensure that the returned reference uses the\n+\t * {@link #queue} ReferenceQueue, otherwise {@link #clear(Ref)} will not be\n+\t * invoked at the proper time.\n+\t *\n+\t * @param pack\n+\t * the file to materialize the entry from.\n+\t * @param position\n+\t * offset within the file of the entry.\n+\t * @param v\n+\t * the object returned by {@link #load(PackFile, long)}.\n+\t * @return a soft reference subclass wrapped around v.\n+\t */\n+\t@SuppressWarnings(\"unchecked\")\n+\tprotected R createRef(final PackFile pack, final long position, final V v) {\n+\t\treturn (R) new Ref(pack, position, v, queue);\n+\t}\n+\n+\t/**\n+\t * Update accounting information now that an object has left the cache.\n+\t *

\n+\t * This method is invoked exactly once for the combined\n+\t * {@link #load(PackFile, long)} and\n+\t * {@link #createRef(PackFile, long, Object)} invocation pair that was used\n+\t * to construct and insert an object into the cache.\n+\t *\n+\t * @param ref\n+\t * the reference wrapped around the object. Implementations must\n+\t * be prepared for ref.get() to return null.\n+\t */\n+\tprotected void clear(final R ref) {\n+\t\t// Do nothing by default.\n+\t}\n+\n+\t/**\n+\t * Determine if the cache is full and requires eviction of entries.\n+\t *

\n+\t * By default this method returns false. Implementors may override to\n+\t * consult with the accounting updated by {@link #load(PackFile, long)},\n+\t * {@link #createRef(PackFile, long, Object)} and {@link #clear(Ref)}.\n+\t *\n+\t * @return true if the cache is still over-limit and requires eviction of\n+\t * more entries.\n+\t */\n+\tprotected boolean isFull() {\n+\t\treturn false;\n+\t}\n+\n+\t@SuppressWarnings(\"unchecked\")\n+\tprivate void gc() {\n+\t\tR r;\n+\t\twhile ((r = (R) queue.poll()) != null) {\n+\t\t\t// Sun's Java 5 and 6 implementation have a bug where a Reference\n+\t\t\t// can be enqueued and dequeued twice on the same reference queue\n+\t\t\t// due to a race condition within ReferenceQueue.enqueue(Reference).\n+\t\t\t//\n+\t\t\t// We CANNOT permit a Reference to come through us twice, as it will\n+\t\t\t// skew the resource counters we maintain. Our canClear() check here\n+\t\t\t// provides a way to skip the redundant dequeues, if any.\n+\t\t\t//\n+\t\t\tif (r.canClear()) {\n+\t\t\t\tclear(r);\n+\n+\t\t\t\tboolean found = false;\n+\t\t\t\tfinal int s = slot(r.pack, r.position);\n+\t\t\t\tfinal Entry e1 = table.get(s);\n+\t\t\t\tfor (Entry n = e1; n != null; n = n.next) {\n+\t\t\t\t\tif (n.ref == r) {\n+\t\t\t\t\t\tn.dead = true;\n+\t\t\t\t\t\tfound = true;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t\tif (found)\n+\t\t\t\t\ttable.compareAndSet(s, e1, clean(e1));\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/**\n+\t * Compute the hash code value for a (PackFile,position) tuple.\n+\t *

\n+\t * For example, return packHash + (int) (position >>> 4).\n+\t * Implementors must override with a suitable hash (for example, a different\n+\t * right shift on the position).\n+\t *\n+\t * @param packHash\n+\t * hash code for the file being accessed.\n+\t * @param position\n+\t * position within the file being accessed.\n+\t * @return a reasonable hash code mixing the two values.\n+\t */\n+\tprotected abstract int hash(int packHash, long position);\n+\n+\tprivate int slot(final PackFile pack, final long position) {\n+\t\treturn (hash(pack.hash, position) >>> 1) % tableSize;\n+\t}\n+\n+\tprivate Lock lock(final PackFile pack, final long position) {\n+\t\treturn locks[(hash(pack.hash, position) >>> 1) % locks.length];\n+\t}\n+\n+\tprivate static Entry clean(Entry top) {\n+\t\twhile (top != null && top.dead) {\n+\t\t\ttop.ref.enqueue();\n+\t\t\ttop = top.next;\n+\t\t}\n+\t\tif (top == null)\n+\t\t\treturn null;\n+\t\tfinal Entry n = clean(top.next);\n+\t\treturn n == top.next ? top : new Entry(n, top.ref);\n+\t}\n+\n+\tprivate static class Entry {\n+\t\t/** Next entry in the hash table's chain list. */\n+\t\tfinal Entry next;\n+\n+\t\t/** The referenced object. */\n+\t\tfinal Ref ref;\n+\n+\t\t/**\n+\t\t * Marked true when ref.get() returns null and the ref is dead.\n+\t\t *

\n+\t\t * A true here indicates that the ref is no longer accessible, and that\n+\t\t * we therefore need to eventually purge this Entry object out of the\n+\t\t * bucket's chain.\n+\t\t */\n+\t\tvolatile boolean dead;\n+\n+\t\tEntry(final Entry n, final Ref r) {\n+\t\t\tnext = n;\n+\t\t\tref = r;\n+\t\t}\n+\n+\t\tfinal void kill() {\n+\t\t\tdead = true;\n+\t\t\tref.enqueue();\n+\t\t}\n+\t}\n+\n+\t/**\n+\t * A soft reference wrapped around a cached object.\n+\t *\n+\t * @param \n+\t * type of the cached object.\n+\t */\n+\tprotected static class Ref extends SoftReference {\n+\t\tfinal PackFile pack;\n+\n+\t\tfinal long position;\n+\n+\t\tlong lastAccess;\n+\n+\t\tprivate boolean cleared;\n+\n+\t\tprotected Ref(final PackFile pack, final long position, final V v,\n+\t\t\t\tfinal ReferenceQueue queue) {\n+\t\t\tsuper(v, queue);\n+\t\t\tthis.pack = pack;\n+\t\t\tthis.position = position;\n+\t\t}\n+\n+\t\tfinal synchronized boolean canClear() {\n+\t\t\tif (cleared)\n+\t\t\t\treturn false;\n+\t\t\tcleared = true;\n+\t\t\treturn true;\n+\t\t}\n+\t}\n+\n+\tprivate static final class Lock {\n+\t\t// Used only for its implicit monitor.\n+\t}\n+}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\nindex 360442f..b107dfe 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n@@ -77,12 +77,13 @@ public int compare(final PackFile a, final PackFile b) {\n \n \tfinal int hash;\n \n-\tRandomAccessFile fd;\n+\tprivate RandomAccessFile fd;\n \n \tlong length;\n \n-\t/** Total number of windows actively in the associated cache. */\n-\tint openCount;\n+\tprivate int activeWindows;\n+\n+\tprivate int activeCopyRawData;\n \n \tprivate int packLastModified;\n \n@@ -310,27 +311,57 @@ private void copyToStream(long position, final byte[] buf, long cnt,\n \t\t}\n \t}\n \n-\tvoid cacheOpen() throws IOException {\n-\t\tfd = new RandomAccessFile(packFile, \"r\");\n-\t\tlength = fd.length();\n+\tsynchronized void beginCopyRawData() throws IOException {\n+\t\tif (++activeCopyRawData == 1 && activeWindows == 0)\n+\t\t\tdoOpen();\n+\t}\n+\n+\tsynchronized void endCopyRawData() {\n+\t\tif (--activeCopyRawData == 0 && activeWindows == 0)\n+\t\t\tdoClose();\n+\t}\n+\n+\tsynchronized boolean beginWindowCache() throws IOException {\n+\t\tif (++activeWindows == 1) {\n+\t\t\tif (activeCopyRawData == 0)\n+\t\t\t\tdoOpen();\n+\t\t\treturn true;\n+\t\t}\n+\t\treturn false;\n+\t}\n+\n+\tsynchronized boolean endWindowCache() {\n+\t\tfinal boolean r = --activeWindows == 0;\n+\t\tif (r && activeCopyRawData == 0)\n+\t\t\tdoClose();\n+\t\treturn r;\n+\t}\n+\n+\tprivate void doOpen() throws IOException {\n \t\ttry {\n+\t\t\tfd = new RandomAccessFile(packFile, \"r\");\n+\t\t\tlength = fd.length();\n \t\t\tonOpenPack();\n \t\t} catch (IOException ioe) {\n-\t\t\tinvalid = true;\n-\t\t\tcacheClose();\n+\t\t\topenFail();\n \t\t\tthrow ioe;\n \t\t} catch (RuntimeException re) {\n-\t\t\tinvalid = true;\n-\t\t\tcacheClose();\n+\t\t\topenFail();\n \t\t\tthrow re;\n \t\t} catch (Error re) {\n-\t\t\tinvalid = true;\n-\t\t\tcacheClose();\n+\t\t\topenFail();\n \t\t\tthrow re;\n \t\t}\n \t}\n \n-\tvoid cacheClose() {\n+\tprivate void openFail() {\n+\t\tactiveWindows = 0;\n+\t\tactiveCopyRawData = 0;\n+\t\tinvalid = true;\n+\t\tdoClose();\n+\t}\n+\n+\tprivate void doClose() {\n \t\tif (fd != null) {\n \t\t\ttry {\n \t\t\t\tfd.close();\n@@ -343,48 +374,34 @@ void cacheClose() {\n \t\t}\n \t}\n \n-\tvoid allocWindow(final WindowCursor curs, final int windowId,\n-\t\t\tfinal long pos, final int size) {\n-\t\tif (WindowCache.mmap) {\n-\t\t\tMappedByteBuffer map;\n-\t\t\ttry {\n-\t\t\t\tmap = fd.getChannel().map(MapMode.READ_ONLY, pos, size);\n-\t\t\t} catch (IOException e) {\n-\t\t\t\t// The most likely reason this failed is the JVM has run out\n-\t\t\t\t// of virtual memory. We need to discard quickly, and try to\n-\t\t\t\t// force the GC to finalize and release any existing mappings.\n-\t\t\t\ttry {\n-\t\t\t\t\tcurs.release();\n-\t\t\t\t\tSystem.gc();\n-\t\t\t\t\tSystem.runFinalization();\n-\t\t\t\t\tmap = fd.getChannel().map(MapMode.READ_ONLY, pos, size);\n-\t\t\t\t} catch (IOException ioe2) {\n-\t\t\t\t\t// Temporarily disable mmap and do buffered disk IO.\n-\t\t\t\t\t//\n-\t\t\t\t\tmap = null;\n-\t\t\t\t\tSystem.err.println(\"warning: mmap failure: \"+ioe2);\n-\t\t\t\t}\n-\t\t\t}\n-\t\t\tif (map != null) {\n-\t\t\t\tif (map.hasArray()) {\n-\t\t\t\t\tfinal byte[] b = map.array();\n-\t\t\t\t\tfinal ByteArrayWindow w;\n-\t\t\t\t\tw = new ByteArrayWindow(this, pos, windowId, b);\n-\t\t\t\t\tw.loaded = true;\n-\t\t\t\t\tcurs.window = w;\n-\t\t\t\t\tcurs.handle = b;\n-\t\t\t\t} else {\n-\t\t\t\t\tcurs.window = new ByteBufferWindow(this, pos, windowId, map);\n-\t\t\t\t\tcurs.handle = map;\n-\t\t\t\t}\n-\t\t\t\treturn;\n-\t\t\t}\n+\tByteArrayWindow read(final long pos, int size) throws IOException {\n+\t\tif (length < pos + size)\n+\t\t\tsize = (int) (length - pos);\n+\t\tfinal byte[] buf = new byte[size];\n+\t\tNB.readFully(fd.getChannel(), pos, buf, 0, size);\n+\t\treturn new ByteArrayWindow(this, pos, buf);\n+\t}\n+\n+\tByteWindow mmap(final long pos, int size) throws IOException {\n+\t\tif (length < pos + size)\n+\t\t\tsize = (int) (length - pos);\n+\n+\t\tMappedByteBuffer map;\n+\t\ttry {\n+\t\t\tmap = fd.getChannel().map(MapMode.READ_ONLY, pos, size);\n+\t\t} catch (IOException ioe1) {\n+\t\t\t// The most likely reason this failed is the JVM has run out\n+\t\t\t// of virtual memory. We need to discard quickly, and try to\n+\t\t\t// force the GC to finalize and release any existing mappings.\n+\t\t\t//\n+\t\t\tSystem.gc();\n+\t\t\tSystem.runFinalization();\n+\t\t\tmap = fd.getChannel().map(MapMode.READ_ONLY, pos, size);\n \t\t}\n \n-\t\tfinal byte[] b = new byte[size];\n-\t\tcurs.window = new ByteArrayWindow(this, pos, windowId, b);\n-\t\tcurs.handle = b;\n-\t\topenCount++; // Until the window loads, we must stay open.\n+\t\tif (map.hasArray())\n+\t\t\treturn new ByteArrayWindow(this, pos, map.array());\n+\t\treturn new ByteBufferWindow(this, pos, map);\n \t}\n \n \tprivate void onOpenPack() throws IOException {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\nindex d49562a..0c3e783 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n@@ -126,7 +126,7 @@ public final long getDataOffset() {\n \t * deleted, and the object has moved to another pack file.\n \t */\n \tpublic void beginCopyRawData() throws IOException {\n-\t\tWindowCache.pin(pack);\n+\t\tpack.beginCopyRawData();\n \t}\n \n \t/**\n@@ -154,7 +154,7 @@ public void copyRawData(OutputStream out, byte buf[], WindowCursor curs)\n \n \t/** Release resources after {@link #beginCopyRawData()}. */\n \tpublic void endCopyRawData() {\n-\t\tWindowCache.unpin(pack);\n+\t\tpack.endCopyRawData();\n \t}\n \n \t/**\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\nindex 51d149c..0102a2d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n@@ -40,12 +40,17 @@\n \n import java.io.IOException;\n import java.lang.ref.ReferenceQueue;\n+import java.util.concurrent.atomic.AtomicInteger;\n \n /**\n- * The WindowCache manages reusable Windows and inflaters used by\n- * the other windowed file access classes.\n+ * Caches slices of a {@link PackFile} in memory for faster read access.\n+ *

\n+ * The WindowCache serves as a Java based \"buffer cache\", loading segments of a\n+ * PackFile into the JVM heap prior to use. As JGit often wants to do reads of\n+ * only tiny slices of a file, the WindowCache tries to smooth out these tiny\n+ * reads into larger block-sized IO operations.\n */\n-public class WindowCache {\n+public class WindowCache extends OffsetCache {\n \tprivate static final int bits(int newSize) {\n \t\tif (newSize < 4096)\n \t\t\tthrow new IllegalArgumentException(\"Invalid window size\");\n@@ -54,41 +59,10 @@ private static final int bits(int newSize) {\n \t\treturn Integer.numberOfTrailingZeros(newSize);\n \t}\n \n-\tprivate static int maxFileCount;\n-\n-\tprivate static int maxByteCount;\n-\n-\tprivate static int windowSize;\n-\n-\tprivate static int windowSizeShift;\n-\n-\tstatic boolean mmap;\n-\n-\tstatic final ReferenceQueue clearedWindowQueue;\n-\n-\tprivate static ByteWindow[] cache;\n-\n-\tprivate static ByteWindow lruHead;\n-\n-\tprivate static ByteWindow lruTail;\n-\n-\tprivate static int openFileCount;\n-\n-\tprivate static int openByteCount;\n+\tprivate static volatile WindowCache cache;\n \n \tstatic {\n-\t\tfinal WindowCacheConfig c = new WindowCacheConfig();\n-\t\tmaxFileCount = c.getPackedGitOpenFiles();\n-\t\tmaxByteCount = c.getPackedGitLimit();\n-\t\twindowSizeShift = bits(c.getPackedGitWindowSize());\n-\t\twindowSize = 1 << windowSizeShift;\n-\t\tmmap = c.isPackedGitMMAP();\n-\t\tcache = new ByteWindow[cacheTableSize()];\n-\t\tclearedWindowQueue = new ReferenceQueue();\n-\t}\n-\n-\tprivate static int cacheTableSize() {\n-\t\treturn 5 * (maxByteCount / windowSize) / 2;\n+\t\treconfigure(new WindowCacheConfig());\n \t}\n \n \t/**\n@@ -128,322 +102,144 @@ public static void reconfigure(final int packedGitLimit,\n \t *\n \t * @param cfg\n \t * the new window cache configuration.\n+\t * @throws IllegalArgumentException\n+\t * the cache configuration contains one or more invalid\n+\t * settings, usually too low of a limit.\n \t */\n \tpublic static void reconfigure(final WindowCacheConfig cfg) {\n-\t\treconfigureImpl(cfg);\n+\t\tfinal WindowCache nc = new WindowCache(cfg);\n+\t\tfinal WindowCache oc = cache;\n+\t\tif (oc != null)\n+\t\t\toc.removeAll();\n+\t\tcache = nc;\n \t\tUnpackedObjectCache.reconfigure(cfg);\n \t}\n \n-\tprivate static synchronized void reconfigureImpl(final WindowCacheConfig cfg) {\n-\t\tboolean prune = false;\n-\t\tboolean evictAll = false;\n-\n-\t\tif (maxFileCount < cfg.getPackedGitOpenFiles())\n-\t\t\tmaxFileCount = cfg.getPackedGitOpenFiles();\n-\t\telse if (maxFileCount > cfg.getPackedGitOpenFiles()) {\n-\t\t\tmaxFileCount = cfg.getPackedGitOpenFiles();\n-\t\t\tprune = true;\n-\t\t}\n-\n-\t\tif (maxByteCount < cfg.getPackedGitLimit()) {\n-\t\t\tmaxByteCount = cfg.getPackedGitLimit();\n-\t\t} else if (maxByteCount > cfg.getPackedGitLimit()) {\n-\t\t\tmaxByteCount = cfg.getPackedGitLimit();\n-\t\t\tprune = true;\n-\t\t}\n-\n-\t\tif (bits(cfg.getPackedGitWindowSize()) != windowSizeShift) {\n-\t\t\twindowSizeShift = bits(cfg.getPackedGitWindowSize());\n-\t\t\twindowSize = 1 << windowSizeShift;\n-\t\t\tevictAll = true;\n-\t\t}\n-\n-\t\tif (mmap != cfg.isPackedGitMMAP()) {\n-\t\t\tmmap = cfg.isPackedGitMMAP();\n-\t\t\tevictAll = true;\n-\t\t}\n-\n-\t\tif (evictAll) {\n-\t\t\t// We have to throw away every window we have. None\n-\t\t\t// of them are suitable for the new configuration.\n+\tstatic final ByteWindow get(final PackFile pack, final long offset)\n+\t\t\tthrows IOException {\n+\t\tfinal WindowCache c = cache;\n+\t\tfinal ByteWindow r = c.getOrLoad(pack, c.toStart(offset));\n+\t\tif (c != cache) {\n+\t\t\t// The cache was reconfigured while we were using the old one\n+\t\t\t// to load this window. The window is still valid, but our\n+\t\t\t// cache may think its still live. Ensure the window is removed\n+\t\t\t// from the old cache so resources can be released.\n \t\t\t//\n-\t\t\tfor (ByteWindow e : cache) {\n-\t\t\t\tfor (; e != null; e = e.chainNext)\n-\t\t\t\t\tclear(e);\n-\t\t\t}\n-\t\t\trunClearedWindowQueue();\n-\t\t\tcache = new ByteWindow[cacheTableSize()];\n-\n-\t\t} else {\n-\t\t\tif (prune) {\n-\t\t\t\t// We should decrease our memory usage.\n-\t\t\t\t//\n-\t\t\t\treleaseMemory();\n-\t\t\t\trunClearedWindowQueue();\n-\t\t\t}\n-\n-\t\t\tif (cache.length != cacheTableSize()) {\n-\t\t\t\t// The cache table should be resized.\n-\t\t\t\t// Rehash every entry.\n-\t\t\t\t//\n-\t\t\t\tfinal ByteWindow[] priorTable = cache;\n-\n-\t\t\t\tcache = new ByteWindow[cacheTableSize()];\n-\t\t\t\tfor (ByteWindow e : priorTable) {\n-\t\t\t\t\tfor (ByteWindow n; e != null; e = n) {\n-\t\t\t\t\t\tn = e.chainNext;\n-\t\t\t\t\t\tfinal int idx = hash(e.provider, e.id);\n-\t\t\t\t\t\te.chainNext = cache[idx];\n-\t\t\t\t\t\tcache[idx] = e;\n-\t\t\t\t\t}\n-\t\t\t\t}\n-\t\t\t}\n-\t\t}\n-\t}\n-\n-\t/**\n-\t * Get a specific window.\n-\t * \n-\t * @param curs\n-\t * an active cursor object to maintain the window reference while\n-\t * the caller needs it.\n-\t * @param wp\n-\t * the provider of the window. If the window is not currently in\n-\t * the cache then the provider will be asked to load it.\n-\t * @param position\n-\t * offset (in bytes) within the file that the caller needs access\n-\t * to.\n-\t * @throws IOException\n-\t * the window was not found in the cache and the given provider\n-\t * was unable to load the window on demand.\n-\t */\n-\tpublic static final void get(final WindowCursor curs, final PackFile wp,\n-\t\t\tfinal long position) throws IOException {\n-\t\tgetImpl(curs, wp, position);\n-\t\tcurs.window.ensureLoaded(curs.handle);\n-\t}\n-\n-\tstatic synchronized final void pin(final PackFile wp) throws IOException {\n-\t\tif (++wp.openCount == 1) {\n-\t\t\topenFile(wp);\n+\t\t\tc.removeAll();\n \t\t}\n+\t\treturn r;\n \t}\n \n-\tstatic synchronized final void unpin(final PackFile wp) {\n-\t\tif (--wp.openCount == 0) {\n-\t\t\topenFileCount--;\n-\t\t\twp.cacheClose();\n-\t\t}\n+\tstatic final void purge(final PackFile pack) {\n+\t\tcache.removeAll(pack);\n \t}\n \n-\tprivate static synchronized final void getImpl(final WindowCursor curs,\n-\t\t\tfinal PackFile wp, final long position) throws IOException {\n-\t\tfinal int id = (int) (position >> windowSizeShift);\n-\t\tfinal int idx = hash(wp, id);\n-\t\tfor (ByteWindow e = cache[idx]; e != null; e = e.chainNext) {\n-\t\t\tif (e.provider == wp && e.id == id) {\n-\t\t\t\tif ((curs.handle = e.get()) != null) {\n-\t\t\t\t\tcurs.window = e;\n-\t\t\t\t\tmakeMostRecent(e);\n-\t\t\t\t\treturn;\n-\t\t\t\t}\n+\tprivate final int maxFiles;\n \n-\t\t\t\tclear(e);\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t}\n+\tprivate final int maxBytes;\n \n-\t\tif (wp.openCount == 0) {\n-\t\t\topenFile(wp);\n+\tprivate final boolean mmap;\n \n-\t\t\t// The cacheOpen may have mapped the window we are trying to\n-\t\t\t// map ourselves. Retrying the search ensures that does not\n-\t\t\t// happen to us.\n-\t\t\t//\n-\t\t\tfor (ByteWindow e = cache[idx]; e != null; e = e.chainNext) {\n-\t\t\t\tif (e.provider == wp && e.id == id) {\n-\t\t\t\t\tif ((curs.handle = e.get()) != null) {\n-\t\t\t\t\t\tcurs.window = e;\n-\t\t\t\t\t\tmakeMostRecent(e);\n-\t\t\t\t\t\treturn;\n-\t\t\t\t\t}\n+\tprivate final int windowSizeShift;\n \n-\t\t\t\t\tclear(e);\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t}\n-\t\t}\n+\tprivate final int windowSize;\n \n-\t\tfinal int wsz = windowSize(wp, id);\n-\t\twp.openCount++;\n-\t\topenByteCount += wsz;\n-\t\treleaseMemory();\n-\t\trunClearedWindowQueue();\n+\tprivate final AtomicInteger openFiles;\n \n-\t\twp.allocWindow(curs, id, (position >>> windowSizeShift) << windowSizeShift, wsz);\n-\t\tfinal ByteWindow e = curs.window;\n-\t\te.chainNext = cache[idx];\n-\t\tcache[idx] = e;\n-\t\tinsertLRU(e);\n-\t}\n+\tprivate final AtomicInteger openBytes;\n \n-\tprivate static void openFile(final PackFile wp) throws IOException {\n-\t\ttry {\n-\t\t\topenFileCount++;\n-\t\t\treleaseMemory();\n-\t\t\trunClearedWindowQueue();\n-\t\t\twp.openCount = 1;\n-\t\t\twp.cacheOpen();\n-\t\t} catch (IOException ioe) {\n-\t\t\topenFileCount--;\n-\t\t\twp.openCount = 0;\n-\t\t\tthrow ioe;\n-\t\t} catch (RuntimeException ioe) {\n-\t\t\topenFileCount--;\n-\t\t\twp.openCount = 0;\n-\t\t\tthrow ioe;\n-\t\t} catch (Error ioe) {\n-\t\t\topenFileCount--;\n-\t\t\twp.openCount = 0;\n-\t\t\tthrow ioe;\n-\t\t} finally {\n-\t\t\twp.openCount--;\n-\t\t}\n-\t}\n+\tprivate WindowCache(final WindowCacheConfig cfg) {\n+\t\tsuper(tableSize(cfg), lockCount(cfg));\n+\t\tmaxFiles = cfg.getPackedGitOpenFiles();\n+\t\tmaxBytes = cfg.getPackedGitLimit();\n+\t\tmmap = cfg.isPackedGitMMAP();\n+\t\twindowSizeShift = bits(cfg.getPackedGitWindowSize());\n+\t\twindowSize = 1 << windowSizeShift;\n \n-\tstatic synchronized void markLoaded(final ByteWindow w) {\n-\t\tif (--w.provider.openCount == 0) {\n-\t\t\topenFileCount--;\n-\t\t\tw.provider.cacheClose();\n-\t\t}\n-\t}\n+\t\topenFiles = new AtomicInteger();\n+\t\topenBytes = new AtomicInteger();\n \n-\tprivate static void makeMostRecent(ByteWindow e) {\n-\t\tif (lruHead != e) {\n-\t\t\tunlinkLRU(e);\n-\t\t\tinsertLRU(e);\n-\t\t}\n+\t\tif (maxFiles < 1)\n+\t\t\tthrow new IllegalArgumentException(\"Open files must be >= 1\");\n+\t\tif (maxBytes < windowSize)\n+\t\t\tthrow new IllegalArgumentException(\"Window size must be < limit\");\n \t}\n \n-\tprivate static void releaseMemory() {\n-\t\tByteWindow e = lruTail;\n-\t\twhile (isOverLimit() && e != null) {\n-\t\t\tfinal ByteWindow p = e.lruPrev;\n-\t\t\tclear(e);\n-\t\t\te = p;\n-\t\t}\n+\t@Override\n+\tprotected int hash(final int packHash, final long off) {\n+\t\treturn packHash + (int) (off >>> windowSizeShift);\n \t}\n \n-\tprivate static boolean isOverLimit() {\n-\t\treturn openByteCount > maxByteCount || openFileCount > maxFileCount;\n-\t}\n-\n-\t/**\n-\t * Remove all windows associated with a specific provider.\n-\t *

\n-\t * Providers should invoke this method as part of their cleanup/close\n-\t * routines, ensuring that the window cache releases all windows that cannot\n-\t * ever be requested again.\n-\t *

\n-\t * \n-\t * @param wp\n-\t * the window provider whose windows should be removed from the\n-\t * cache.\n-\t */\n-\tpublic static synchronized final void purge(final PackFile wp) {\n-\t\tfor (ByteWindow e : cache) {\n-\t\t\tfor (; e != null; e = e.chainNext) {\n-\t\t\t\tif (e.provider == wp)\n-\t\t\t\t\tclear(e);\n-\t\t\t}\n+\t@Override\n+\tprotected ByteWindow load(final PackFile pack, final long offset)\n+\t\t\tthrows IOException {\n+\t\tif (pack.beginWindowCache())\n+\t\t\topenFiles.incrementAndGet();\n+\t\ttry {\n+\t\t\tif (mmap)\n+\t\t\t\treturn pack.mmap(offset, windowSize);\n+\t\t\treturn pack.read(offset, windowSize);\n+\t\t} catch (IOException e) {\n+\t\t\tclose(pack);\n+\t\t\tthrow e;\n+\t\t} catch (RuntimeException e) {\n+\t\t\tclose(pack);\n+\t\t\tthrow e;\n+\t\t} catch (Error e) {\n+\t\t\tclose(pack);\n+\t\t\tthrow e;\n \t\t}\n-\t\trunClearedWindowQueue();\n \t}\n \n-\tprivate static void runClearedWindowQueue() {\n-\t\tByteWindow e;\n-\t\twhile ((e = (ByteWindow) clearedWindowQueue.poll()) != null) {\n-\t\t\tunlinkSize(e);\n-\t\t\tunlinkLRU(e);\n-\t\t\tunlinkCache(e);\n-\t\t\te.chainNext = null;\n-\t\t\te.lruNext = null;\n-\t\t\te.lruPrev = null;\n-\t\t}\n+\t@Override\n+\tprotected WindowRef createRef(final PackFile p, final long o,\n+\t\t\tfinal ByteWindow v) {\n+\t\tfinal WindowRef ref = new WindowRef(p, o, v, queue);\n+\t\topenBytes.addAndGet(ref.size);\n+\t\treturn ref;\n \t}\n \n-\tprivate static void clear(final ByteWindow e) {\n-\t\tunlinkSize(e);\n-\t\te.clear();\n-\t\te.enqueue();\n+\t@Override\n+\tprotected void clear(final WindowRef ref) {\n+\t\topenBytes.addAndGet(-ref.size);\n+\t\tclose(ref.pack);\n \t}\n \n-\tprivate static void unlinkSize(final ByteWindow e) {\n-\t\tif (e.sizeActive) {\n-\t\t\tif (--e.provider.openCount == 0) {\n-\t\t\t\topenFileCount--;\n-\t\t\t\te.provider.cacheClose();\n-\t\t\t}\n-\t\t\topenByteCount -= e.size;\n-\t\t\te.sizeActive = false;\n-\t\t}\n+\tprivate void close(final PackFile pack) {\n+\t\tif (pack.endWindowCache())\n+\t\t\topenFiles.decrementAndGet();\n \t}\n \n-\tprivate static void unlinkCache(final ByteWindow dead) {\n-\t\tfinal int idx = hash(dead.provider, dead.id);\n-\t\tByteWindow e = cache[idx], p = null, n;\n-\t\tfor (; e != null; p = e, e = n) {\n-\t\t\tn = e.chainNext;\n-\t\t\tif (e == dead) {\n-\t\t\t\tif (p == null)\n-\t\t\t\t\tcache[idx] = n;\n-\t\t\t\telse\n-\t\t\t\t\tp.chainNext = n;\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t}\n+\t@Override\n+\tprotected boolean isFull() {\n+\t\treturn maxFiles < openFiles.get() || maxBytes < openBytes.get();\n \t}\n \n-\tprivate static void unlinkLRU(final ByteWindow e) {\n-\t\tfinal ByteWindow prev = e.lruPrev;\n-\t\tfinal ByteWindow next = e.lruNext;\n-\n-\t\tif (prev != null)\n-\t\t\tprev.lruNext = next;\n-\t\telse\n-\t\t\tlruHead = next;\n-\n-\t\tif (next != null)\n-\t\t\tnext.lruPrev = prev;\n-\t\telse\n-\t\t\tlruTail = prev;\n+\tprivate long toStart(final long offset) {\n+\t\treturn (offset >>> windowSizeShift) << windowSizeShift;\n \t}\n \n-\tprivate static void insertLRU(final ByteWindow e) {\n-\t\tfinal ByteWindow h = lruHead;\n-\t\te.lruPrev = null;\n-\t\te.lruNext = h;\n-\t\tif (h != null)\n-\t\t\th.lruPrev = e;\n-\t\telse\n-\t\t\tlruTail = e;\n-\t\tlruHead = e;\n+\tprivate static int tableSize(final WindowCacheConfig cfg) {\n+\t\tfinal int wsz = cfg.getPackedGitWindowSize();\n+\t\tfinal int limit = cfg.getPackedGitLimit();\n+\t\tif (wsz <= 0)\n+\t\t\tthrow new IllegalArgumentException(\"Invalid window size\");\n+\t\tif (limit < wsz)\n+\t\t\tthrow new IllegalArgumentException(\"Window size must be < limit\");\n+\t\treturn 5 * (limit / wsz) / 2;\n \t}\n \n-\tprivate static int hash(final PackFile wp, final int id) {\n-\t\t// wp.hash was already \"stirred up\" a bit by * 31 when\n-\t\t// it was created. Its reasonable to just add here.\n-\t\t//\n-\t\treturn ((wp.hash + id) >>> 1) % cache.length;\n+\tprivate static int lockCount(final WindowCacheConfig cfg) {\n+\t\treturn Math.max(cfg.getPackedGitOpenFiles(), 32);\n \t}\n \n-\tprivate static int windowSize(final PackFile file, final int id) {\n-\t\tfinal long len = file.length;\n-\t\tfinal long pos = id << windowSizeShift;\n-\t\treturn len < pos + windowSize ? (int) (len - pos) : windowSize;\n-\t}\n+\tstatic class WindowRef extends OffsetCache.Ref {\n+\t\tfinal int size;\n \n-\tprivate WindowCache() {\n-\t\tthrow new UnsupportedOperationException();\n+\t\tWindowRef(final PackFile pack, final long position, final ByteWindow v,\n+\t\t\t\tfinal ReferenceQueue queue) {\n+\t\t\tsuper(pack, position, v, queue);\n+\t\t\tsize = v.size();\n+\t\t}\n \t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java\nindex fb9d348..0723a78 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java\n@@ -48,14 +48,12 @@\n \n \tprivate Inflater inf;\n \n-\tByteWindow window;\n-\n-\tObject handle;\n+\tprivate ByteWindow window;\n \n \t/**\n \t * Copy bytes from the window to a caller supplied buffer.\n \t * \n-\t * @param provider\n+\t * @param pack\n \t * the file the desired window is stored within.\n \t * @param position\n \t * position within the file to read from.\n@@ -74,13 +72,13 @@\n \t * this cursor does not match the provider or id and the proper\n \t * window could not be acquired through the provider's cache.\n \t */\n-\tint copy(final PackFile provider, long position, final byte[] dstbuf,\n+\tint copy(final PackFile pack, long position, final byte[] dstbuf,\n \t\t\tint dstoff, final int cnt) throws IOException {\n-\t\tfinal long length = provider.length;\n+\t\tfinal long length = pack.length;\n \t\tint need = cnt;\n \t\twhile (need > 0 && position < length) {\n-\t\t\tpin(provider, position);\n-\t\t\tfinal int r = window.copy(handle, position, dstbuf, dstoff, need);\n+\t\t\tpin(pack, position);\n+\t\t\tfinal int r = window.copy(position, dstbuf, dstoff, need);\n \t\t\tposition += r;\n \t\t\tdstoff += r;\n \t\t\tneed -= r;\n@@ -91,7 +89,7 @@ int copy(final PackFile provider, long position, final byte[] dstbuf,\n \t/**\n \t * Pump bytes into the supplied inflater as input.\n \t * \n-\t * @param provider\n+\t * @param pack\n \t * the file the desired window is stored within.\n \t * @param position\n \t * position within the file to read from.\n@@ -109,47 +107,53 @@ int copy(final PackFile provider, long position, final byte[] dstbuf,\n \t * the inflater encountered an invalid chunk of data. Data\n \t * stream corruption is likely.\n \t */\n-\tint inflate(final PackFile provider, long position, final byte[] dstbuf,\n+\tint inflate(final PackFile pack, long position, final byte[] dstbuf,\n \t\t\tint dstoff) throws IOException, DataFormatException {\n \t\tif (inf == null)\n \t\t\tinf = InflaterCache.get();\n \t\telse\n \t\t\tinf.reset();\n \t\tfor (;;) {\n-\t\t\tpin(provider, position);\n-\t\t\tdstoff = window.inflate(handle, position, dstbuf, dstoff, inf);\n+\t\t\tpin(pack, position);\n+\t\t\tdstoff = window.inflate(position, dstbuf, dstoff, inf);\n \t\t\tif (inf.finished())\n \t\t\t\treturn dstoff;\n \t\t\tposition = window.end;\n \t\t}\n \t}\n \n-\tvoid inflateVerify(final PackFile provider, long position)\n+\tvoid inflateVerify(final PackFile pack, long position)\n \t\t\tthrows IOException, DataFormatException {\n \t\tif (inf == null)\n \t\t\tinf = InflaterCache.get();\n \t\telse\n \t\t\tinf.reset();\n \t\tfor (;;) {\n-\t\t\tpin(provider, position);\n-\t\t\twindow.inflateVerify(handle, position, inf);\n+\t\t\tpin(pack, position);\n+\t\t\twindow.inflateVerify(position, inf);\n \t\t\tif (inf.finished())\n \t\t\t\treturn;\n \t\t\tposition = window.end;\n \t\t}\n \t}\n \n-\tprivate void pin(final PackFile provider, final long position)\n+\tprivate void pin(final PackFile pack, final long position)\n \t\t\tthrows IOException {\n \t\tfinal ByteWindow w = window;\n-\t\tif (w == null || !w.contains(provider, position))\n-\t\t\tWindowCache.get(this, provider, position);\n+\t\tif (w == null || !w.contains(pack, position)) {\n+\t\t\t// If memory is low, we may need what is in our window field to\n+\t\t\t// be cleaned up by the GC during the get for the next window.\n+\t\t\t// So we always clear it, even though we are just going to set\n+\t\t\t// it again.\n+\t\t\t//\n+\t\t\twindow = null;\n+\t\t\twindow = WindowCache.get(pack, position);\n+\t\t}\n \t}\n \n \t/** Release the current window cursor. */\n \tpublic void release() {\n \t\twindow = null;\n-\t\thandle = null;\n \t\ttry {\n \t\t\tInflaterCache.release(inf);\n \t\t} finally {\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112666","messageId":"1241031288-23437-11-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-10-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 10/11] Add tests for WindowCache.reconfigure cases","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:47Z","receivedAt":"2009-04-29T18:54:47Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Most of these cases occur when the window cache is misconfigured\nby the application. We should be throwing an exception out with\nsome sort of error message if they happen, so check for that.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n New test, to get better coverage.\n\n .../jgit/lib/WindowCacheReconfigureTest.java | 119 ++++++++++++++++++++\n 1 files changed, 119 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheReconfigureTest.java\n\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheReconfigureTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheReconfigureTest.java\nnew file mode 100644\nindex 0000000..9bd4d96\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheReconfigureTest.java\n@@ -0,0 +1,119 @@\n+/*\n+ * Copyright (C) 2009, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.lib;\n+\n+public class WindowCacheReconfigureTest extends RepositoryTestCase {\n+\tpublic void testConfigureCache_PackedGitLimit_0() {\n+\t\ttry {\n+\t\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\t\tcfg.setPackedGitLimit(0);\n+\t\t\tWindowCache.reconfigure(cfg);\n+\t\t\tfail(\"incorrectly permitted PackedGitLimit = 0\");\n+\t\t} catch (IllegalArgumentException e) {\n+\t\t\t//\n+\t\t}\n+\t}\n+\n+\tpublic void testConfigureCache_PackedGitWindowSize_0() {\n+\t\ttry {\n+\t\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\t\tcfg.setPackedGitWindowSize(0);\n+\t\t\tWindowCache.reconfigure(cfg);\n+\t\t\tfail(\"incorrectly permitted PackedGitWindowSize = 0\");\n+\t\t} catch (IllegalArgumentException e) {\n+\t\t\tassertEquals(\"Invalid window size\", e.getMessage());\n+\t\t}\n+\t}\n+\n+\tpublic void testConfigureCache_PackedGitWindowSize_512() {\n+\t\ttry {\n+\t\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\t\tcfg.setPackedGitWindowSize(512);\n+\t\t\tWindowCache.reconfigure(cfg);\n+\t\t\tfail(\"incorrectly permitted PackedGitWindowSize = 512\");\n+\t\t} catch (IllegalArgumentException e) {\n+\t\t\tassertEquals(\"Invalid window size\", e.getMessage());\n+\t\t}\n+\t}\n+\n+\tpublic void testConfigureCache_PackedGitWindowSize_4097() {\n+\t\ttry {\n+\t\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\t\tcfg.setPackedGitWindowSize(4097);\n+\t\t\tWindowCache.reconfigure(cfg);\n+\t\t\tfail(\"incorrectly permitted PackedGitWindowSize = 4097\");\n+\t\t} catch (IllegalArgumentException e) {\n+\t\t\tassertEquals(\"Window size must be power of 2\", e.getMessage());\n+\t\t}\n+\t}\n+\n+\tpublic void testConfigureCache_PackedGitOpenFiles_0() {\n+\t\ttry {\n+\t\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\t\tcfg.setPackedGitOpenFiles(0);\n+\t\t\tWindowCache.reconfigure(cfg);\n+\t\t\tfail(\"incorrectly permitted PackedGitOpenFiles = 0\");\n+\t\t} catch (IllegalArgumentException e) {\n+\t\t\tassertEquals(\"Open files must be >= 1\", e.getMessage());\n+\t\t}\n+\t}\n+\n+\tpublic void testConfigureCache_PackedGitWindowSizeAbovePackedGitLimit() {\n+\t\ttry {\n+\t\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\t\tcfg.setPackedGitLimit(1024);\n+\t\t\tcfg.setPackedGitWindowSize(8192);\n+\t\t\tWindowCache.reconfigure(cfg);\n+\t\t\tfail(\"incorrectly permitted PackedGitWindowSize > PackedGitLimit\");\n+\t\t} catch (IllegalArgumentException e) {\n+\t\t\tassertEquals(\"Window size must be < limit\", e.getMessage());\n+\t\t}\n+\t}\n+\n+\tpublic void testConfigureCache_Limits1() {\n+\t\t// This test is just to force coverage over some lower bounds for\n+\t\t// the table. We don't want the table to wind up with too small\n+\t\t// of a size. This is highly dependent upon the table allocation\n+\t\t// algorithm actually implemented in WindowCache.\n+\t\t//\n+\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\tcfg.setPackedGitLimit(6 * 4096 / 5);\n+\t\tcfg.setPackedGitWindowSize(4096);\n+\t\tWindowCache.reconfigure(cfg);\n+\t}\n+}\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112667","messageId":"1241031288-23437-12-git-send-email-spearce@spearce.org","threadId":"19126","inReplyTo":"1241031288-23437-11-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 11/11] Add tests to increase coverage of WindowCache","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-29T18:54:48Z","receivedAt":"2009-04-29T18:54:48Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"These tests run the WindowCache in different configurations with known\ninputs, forcing it through different code paths as the cache populates\nwith entries, and potentially overflows.\n\nThe list of objects was derived from `git verify-pack -v`, run over all\nof the pack files we install by default into a RepositoryTestCase.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n New test, to get better coverage.\n\n .../jgit/test/resources/all_packed_objects.txt | 96 +++++++++++++\n .../org/spearce/jgit/lib/WindowCacheGetTest.java | 143 ++++++++++++++++++++\n .../org/spearce/jgit/lib/PackedObjectLoader.java | 7 +\n .../src/org/spearce/jgit/lib/WindowCache.java | 12 ++\n 4 files changed, 258 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst-rsrc/org/spearce/jgit/test/resources/all_packed_objects.txt\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheGetTest.java\n\ndiff --git a/org.spearce.jgit.test/tst-rsrc/org/spearce/jgit/test/resources/all_packed_objects.txt b/org.spearce.jgit.test/tst-rsrc/org/spearce/jgit/test/resources/all_packed_objects.txt\nnew file mode 100644\nindex 0000000..a97f662\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst-rsrc/org/spearce/jgit/test/resources/all_packed_objects.txt\n@@ -0,0 +1,96 @@\n+4b825dc642cb6eb9a060e54bf8d69288fbee4904 tree 0 9 7782\n+540a36d136cf413e4b064c2b0e0a4db60f77feab commit 191 131 339\n+5b6e7c66c276e7610d4a73c70ec1a1f7c1003259 blob 11 40 516 1 6ff87c4664981e4397625791c8ea3bbb5f2279a3\n+6ff87c4664981e4397625791c8ea3bbb5f2279a3 blob 18787 7180 556\n+82c6b885ff600be425b4ea96dee75dca255b69e7 commit 245 166 12\n+902d5476fa249b7abc9d84c611577a81381f0327 tree 35 46 7736\n+aabf2ffaec9b497f0950352b3e582d73035c2035 tree 35 46 470\n+c59759f143fb1fe21c197981df75a7ee00290799 commit 240 161 178\n+02ba32d3649e510002c21651936b7077aa75ffa9 tree 122 127 3806\n+0966a434eb1a025db6b71485ab63a3bfbea520b6 commit 287 197 2611\n+09efc7e59a839528ac7bda9fa020dc9101278680 tree 68 71 5497\n+0a3d7772488b6b106fb62813c4d6d627918d9181 tree 98 95 3367\n+1004d0d7ac26fbf63050a234c9b88a46075719d3 tree 68 72 3504\n+10da5895682013006950e7da534b705252b03be6 blob 6 15 3591\n+1203b03dc816ccbb67773f28b3c19318654b0bc8 commit 222 152 758\n+15fae9e651043de0fd1deef588aa3fbf5a7a41c6 blob 6 15 3474\n+16f9ec009e5568c435f473ba3a1df732d49ce8c3 blob 3 12 4196\n+1fd7d579fb6ae3fe942dc09c2c783443d04cf21e blob 6 15 3678\n+20a8ade77639491ea0bd667bf95de8abf3a434c8 tree 66 77 5663\n+2675188fd86978d5bc4d7211698b2118ae3bf658 tree 68 72 4124\n+2c349335b7f797072cf729c4f3bb0914ecb6dec9 commit 221 154 2457\n+2cc3f4155a8eda5c3f1bc85de0988c0155c8cc1c tree 68 72 4717\n+30a7b072d441dbfcfe0266b1c5fce94c22c447da tree 38 48 5784\n+42e4e7c5e507e113ebbb7801b16b52cf867b7ce1 commit 184 133 1407\n+49322bb17d3acc9146f98c97d078513228bbf3c0 commit 338 223 12\n+49c5f851406e8004b816b8170f6f18e30ee877b9 tree 68 72 3606\n+55a1a760df4b86a02094a904dfa511deb5655905 blob 6 15 3693\n+58be4659bb571194ed4562d04b359d26216f526e commit 226 156 2962\n+59706a11bde2b9899a278838ef20a97e8f8795d2 commit 222 153 1692\n+5f25aaf573e7a094697987a927b833e088134674 tree 66 76 5184\n+6020a3b8d5d636e549ccbd0c53e2764684bb3125 tree 122 126 3241\n+62b15c9ddac853efbb00f59123f484b05b06d8b3 tree 28 37 4431\n+6462e7d8024396b14d7651e2ec11e2bbf07a05c4 commit 221 153 1254\n+6c83a9d0a09ce6d12292314ed3d9e1f60e39feb0 tree 66 76 5587\n+6c8b137b1c652731597c89668f417b8695f28dd7 commit 172 123 3118\n+6db9c2ebf75590eef973081736730a9ea169a0c4 commit 222 152 2153\n+6e1475206e57110fcef4b92320436c1e9872a322 commit 282 192 566\n+7f822839a2fe9760f386cbbbcb3f92c5fe81def7 commit 222 152 1540\n+81e462df7c747d5b8783af18bf83bffbef8dc2bc tree 34 45 5139\n+8230f48330e0055d9e0bc5a2a77718f6dd9324b8 blob 10 19 5568\n+82b1d08466e9505f8666b778744f9a3471a70c81 blob 20 22 3708\n+82fb2e7873759b74c41020a00abaea9c378a7a15 tree 66 76 4801\n+835da11381dee94c71a04164cdaa533d0673e4e5 tree 34 45 4468\n+83834a7afdaa1a1260568567f6ad90020389f664 commit 282 192 1062\n+83d2f0431bcdc9c2fd2c17b828143be6ee4fbe80 commit 221 155 1998\n+856ec208ae6cadac25a6d74f19b12bb27a24fe24 tree 66 76 5260\n+86265c33b19b2be71bdd7b8cb95823f2743d03a8 tree 94 102 4208\n+86cec6b57d80fda40300fb0d667965a5c3c3572f blob 6 15 3576\n+8d6a2f2af0b2b96f320dd62fb6d9916fd2497dd9 tree 66 77 5420\n+8f50ba15d49353813cc6e20298002c0d17b0a9ee tree 94 102 4961\n+9188910f5d18434c2c8a3d78e8bef1a469c5626e tree 68 72 3933\n+965361132e2f15897c9fd6c727beb5753057c38a blob 6 15 3489\n+968a4b6caa8b55a68098e0495fbd9e75a7d05efa tree 68 72 4310\n+a288d2cc3ee7d82f482e70ae7b6fedb4a039dd09 tree 28 37 4394\n+a33a091b7c8de98b3a2ad2f21f88ea86f395d787 tree 94 102 4615\n+a4e0e50de469ac6e2fdf2ee81808f253d5b78fd3 tree 68 72 5336\n+ac7e7e44c1885efb472ad54a78327d66bfc4ecef commit 221 154 2808\n+acd0220f06f7e4db50ea5ba242f0dfed297b27af tree 94 102 4513\n+ae9304576a6ec3419b231b2b9c8e33a06f97f9fb blob 3 12 4382\n+b9877f83f4c2ba0c3dd8fb2f6b5f04a0aaf18594 tree 66 76 5063\n+bab66b48f836ed950c99134ef666436fb07a09a0 commit 222 152 910\n+be9b45333b66013bde1c7314efc50fabd9b39c6d tree 7 18 4005 1 02ba32d3649e510002c21651936b7077aa75ffa9\n+c070ad8c08840c8116da865b2d65593a6bb9cd2a commit 282 192 235\n+c17b9ee9d0501fecadfac3b60ca485b14f5dbe98 tree 38 49 5832\n+c1827f07e114c20547dc6a7296588870a4b5b62c blob 3 12 5408\n+c9c6af7f78bc47490dbf3e822cf2f3c24d4b9061 blob 3 12 4949\n+cd4bcfc27da62c6b840de700be1c60a7e69952a5 tree 66 76 3730\n+d0114ab8ac326bab30e3a657a0397578c5a1af88 commit 84 95 427 1 c070ad8c08840c8116da865b2d65593a6bb9cd2a\n+d31f5a60d406e831d056b8ac2538d515100c2df2 commit 221 153 1845\n+d4b9b11fc8006af3b05cf2b4611077ed6a9b8c07 tree 68 72 4877\n+d86a2aada2f5e7ccf6f11880bfb9ab404e8a8864 commit 222 152 2305\n+da0f8ed91a8f2f0f067b3bdf26265d5ca48cf82c blob 3 12 3462\n+e4ff0b72cb0994dbf7a9da260aeb461c9d882bb5 tree 34 44 5740\n+e6bfff5c1d0f0ecd501552b43a1e13d8008abc31 blob 3 12 4789\n+f2aacb9368806d6502a03aa9da0834d4b50b9f0e tree 94 101 4023\n+f73b95671f326616d66b2afb3bdfcdbbce110b44 commit 33 44 522 2 d0114ab8ac326bab30e3a657a0397578c5a1af88\n+17768080a2318cd89bba4c8b87834401e2095703 tag 140 132 12\n+032c063ce34486359e3ee3d4f9e5c225b9e1a4c2 tag 152 138 12\n+1170b77a48d3ea2d58b043648b1ec63d606e3efa tag 150 138 971\n+214cae792433672d28b3aeb9f75c1ae84fd54628 tag 150 136 1109\n+8dfd42699e7b10e568fa1eaebe249e33e98da81e tag 150 138 833\n+a773cd2d9dbca00d08793dac0d7002a49f0428c0 tag 150 138 422\n+bf5123bb77c7b5a379f7de9c1293558e3e24dfb8 tag 150 135 287\n+d54e006ebbef94b7d3a5cd56d154f1e6f08efb94 tag 150 137 560\n+dd144af286452bfd6a1ea02b0d3745bcdb555e9d tag 150 137 150\n+efee904c794b943a06931c76c576dd552212e8bc tag 150 136 697\n+8bbde7aacf771a9afb6992434f1ae413e010c6d8 tag 630 436 1187\n+fd608fbe625a2b456d9f15c2b1dc41f252057dd7 blob 1512 1175 12\n+06b8692d5c4f29a6bc4987e1bec04e9bb2ec54a2 tree 29 40 330\n+164bf8c9e69a5c192acd28e95aefd9a5d6f254df blob 7 16 370\n+175d5b80bd9768884d8fced02e9bd33488174396 commit 56 68 160 1 47d3697c3747e8184e0dc479ccbd01e359023577\n+3d2770618bb1132e59c314dea328b83ac7c83232 tree 29 40 488\n+3df983efd6acdf73dfc7b451a2e30f7ed42e7736 blob 5 14 528\n+47d3697c3747e8184e0dc479ccbd01e359023577 commit 217 148 12\n+5e28f2d1ee99ddf4595a7a1ff31efa1a107c11e7 tree 94 102 386\n+737d98fe75742dd9a8f4bce5e176e7f8d99d9de3 tree 94 102 228\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheGetTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheGetTest.java\nnew file mode 100644\nindex 0000000..c19bb2b\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/WindowCacheGetTest.java\n@@ -0,0 +1,143 @@\n+/*\n+ * Copyright (C) 2009, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.lib;\n+\n+import java.io.BufferedReader;\n+import java.io.FileInputStream;\n+import java.io.IOException;\n+import java.io.InputStreamReader;\n+import java.util.ArrayList;\n+import java.util.List;\n+\n+import org.spearce.jgit.errors.CorruptObjectException;\n+import org.spearce.jgit.util.JGitTestUtil;\n+import org.spearce.jgit.util.MutableInteger;\n+\n+public class WindowCacheGetTest extends RepositoryTestCase {\n+\tprivate List toLoad;\n+\n+\t@Override\n+\tpublic void setUp() throws Exception {\n+\t\tsuper.setUp();\n+\n+\t\ttoLoad = new ArrayList();\n+\t\tfinal BufferedReader br = new BufferedReader(new InputStreamReader(\n+\t\t\t\tnew FileInputStream(JGitTestUtil\n+\t\t\t\t\t\t.getTestResourceFile(\"all_packed_objects.txt\")),\n+\t\t\t\tConstants.CHARSET));\n+\t\ttry {\n+\t\t\tString line;\n+\t\t\twhile ((line = br.readLine()) != null) {\n+\t\t\t\tfinal String[] parts = line.split(\" {1,}\");\n+\t\t\t\tfinal TestObject o = new TestObject();\n+\t\t\t\to.id = ObjectId.fromString(parts[0]);\n+\t\t\t\to.setType(parts[1]);\n+\t\t\t\to.rawSize = Integer.parseInt(parts[2]);\n+\t\t\t\t// parts[3] is the size-in-pack\n+\t\t\t\to.offset = Long.parseLong(parts[4]);\n+\t\t\t\ttoLoad.add(o);\n+\t\t\t}\n+\t\t} finally {\n+\t\t\tbr.close();\n+\t\t}\n+\t\tassertEquals(96, toLoad.size());\n+\t}\n+\n+\tpublic void testCache_Defaults() throws IOException {\n+\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\tWindowCache.reconfigure(cfg);\n+\t\tdoCacheTests();\n+\t\tcheckLimits(cfg);\n+\n+\t\tfinal WindowCache cache = WindowCache.getInstance();\n+\t\tassertEquals(6, cache.getOpenFiles());\n+\t\tassertEquals(17346, cache.getOpenBytes());\n+\t}\n+\n+\tpublic void testCache_TooFewFiles() throws IOException {\n+\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\tcfg.setPackedGitOpenFiles(2);\n+\t\tWindowCache.reconfigure(cfg);\n+\t\tdoCacheTests();\n+\t\tcheckLimits(cfg);\n+\t}\n+\n+\tpublic void testCache_TooSmallLimit() throws IOException {\n+\t\tfinal WindowCacheConfig cfg = new WindowCacheConfig();\n+\t\tcfg.setPackedGitWindowSize(4096);\n+\t\tcfg.setPackedGitLimit(4096);\n+\t\tWindowCache.reconfigure(cfg);\n+\t\tdoCacheTests();\n+\t\tcheckLimits(cfg);\n+\t}\n+\n+\tprivate void checkLimits(final WindowCacheConfig cfg) {\n+\t\tfinal WindowCache cache = WindowCache.getInstance();\n+\t\tassertTrue(cache.getOpenFiles() <= cfg.getPackedGitOpenFiles());\n+\t\tassertTrue(cache.getOpenBytes() <= cfg.getPackedGitLimit());\n+\t\tassertTrue(0 < cache.getOpenFiles());\n+\t\tassertTrue(0 < cache.getOpenBytes());\n+\t}\n+\n+\tprivate void doCacheTests() throws IOException {\n+\t\tfor (final TestObject o : toLoad) {\n+\t\t\tfinal ObjectLoader or = db.openObject(o.id);\n+\t\t\tassertNotNull(or);\n+\t\t\tassertTrue(or instanceof PackedObjectLoader);\n+\t\t\tassertEquals(o.type, or.getType());\n+\t\t\tassertEquals(o.rawSize, or.getRawSize());\n+\t\t\tassertEquals(o.offset, ((PackedObjectLoader) or).getObjectOffset());\n+\t\t}\n+\t}\n+\n+\tprivate class TestObject {\n+\t\tObjectId id;\n+\n+\t\tint type;\n+\n+\t\tint rawSize;\n+\n+\t\tlong offset;\n+\n+\t\tvoid setType(final String typeStr) throws CorruptObjectException {\n+\t\t\tfinal byte[] typeRaw = Constants.encode(typeStr + \" \");\n+\t\t\tfinal MutableInteger ptr = new MutableInteger();\n+\t\t\ttype = Constants.decodeTypeString(id, typeRaw, (byte) ' ', ptr);\n+\t\t}\n+\t}\n+}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\nindex 0c3e783..29ec6d3 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n@@ -99,6 +99,13 @@ public final long getSize() {\n \t}\n \n \t/**\n+\t * @return offset of object header within pack file\n+\t */\n+\tpublic final long getObjectOffset() {\n+\t\treturn objectOffset;\n+\t}\n+\n+\t/**\n \t * @return offset of object data within pack file\n \t */\n \tpublic final long getDataOffset() {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\nindex 0102a2d..0c60853 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n@@ -115,6 +115,10 @@ public static void reconfigure(final WindowCacheConfig cfg) {\n \t\tUnpackedObjectCache.reconfigure(cfg);\n \t}\n \n+\tstatic WindowCache getInstance() {\n+\t\treturn cache;\n+\t}\n+\n \tstatic final ByteWindow get(final PackFile pack, final long offset)\n \t\t\tthrows IOException {\n \t\tfinal WindowCache c = cache;\n@@ -165,6 +169,14 @@ private WindowCache(final WindowCacheConfig cfg) {\n \t\t\tthrow new IllegalArgumentException(\"Window size must be < limit\");\n \t}\n \n+\tint getOpenFiles() {\n+\t\treturn openFiles.get();\n+\t}\n+\n+\tint getOpenBytes() {\n+\t\treturn openBytes.get();\n+\t}\n+\n \t@Override\n \tprotected int hash(final int packHash, final long off) {\n \t\treturn packHash + (int) (off >>> windowSizeShift);\n-- \n1.6.3.rc3.199.g24398\n"},{"id":"112725","messageId":"200904300146.31062.robin.rosenberg.lists@dewire.com","threadId":"19126","inReplyTo":"1241031288-23437-1-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH v2 00/11] WindowCache rewrite... with tests","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2009-04-29T23:46:30Z","receivedAt":"2009-04-29T23:46:30Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"onsdag 29 april 2009 20:54:37 skrev \"Shawn O. Pearce\" :\n> 9-11 is the rewrite of WindowCache, with new unit tests to get higher\n> levels of coverage in this section of the code. Actually doing\n> better is really hard, as we'd need to cause thread race conditions\n> deep within critical sections. The only way I can think to do that\n> is to add injection points where we can insert \"evil other thread\"\n> logic during the unit test, and rely on the JIT to compile them\n> out in normal application usage. Ick. Its also quite fragile.\n\nTesting *is* hard. No news here. There are various techniques for \ninjecting code using AOP (AspjectJ) that may be useful for testing,\nsince we could inject failures that way without the overhead of\ninjection points in normal execution. \n\n-- robin\n"}]}