{"thread":{"id":"19293","subject":"[JGIT PATCH] Fix data corruption in DirCacheIterator when EmptyTreeIterator is used","startedAt":"2009-05-11T17:52:28Z","lastAt":"2009-05-11T19:44:29Z","messageCount":3,"participants":["Shawn O. Pearce","Robin Rosenberg"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"113559","messageId":"1242064348-13197-1-git-send-email-spearce@spearce.org","threadId":"19293","inReplyTo":null,"subject":"[JGIT PATCH] Fix data corruption in DirCacheIterator when EmptyTreeIterator is used","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-05-11T17:52:28Z","receivedAt":"2009-05-11T17:52:28Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"When a DirCacheIterator was wrapped in an EmptyTreeIterator (such\nas during a parallel TreeWalk where the other trees contain a\npath that does not appear in the DirCachIterator) we corrupted\nthe DirCacheEntry path buffers by overwriting part of file name\ncomponents with '/' to match the other tree iterators' path length.\n\nThis happened because DirCacheIterator violated the iterator\nassumption that the path buffer is always mutable.  Instead of\ncreating a mutable path, DirCacheIterator reused the path buffer\nfrom the DirCacheEntry or the DirCacheTree.  These reused byte\narrays aren't mutable.\n\nBy delegating the EmptyTreeIterator creation to each iterator type\nwe can permit DirCacheIterator to control how it builds the empty\ntree for the caller, ensuring that it copies the path buffer before\nwriting the '/' suffix onto it.\n\nWhen EmptyTreeIterator has to grow the path buffer to create a new\niterator around itself, we can't just blindly replace every parent\niterator buffer with the larger path buffer.  DirCacheIterators will\nbe using a different path buffer, and they want to retain their\nold path buffer, not the new larger buffer.\n\nNoticed-by: Mark Struberg <struberg@yahoo.de>\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n\n So uhm, test cases...  I can't come up with a simple test case\n which causes the data corruption, but Mark found a very complex\n one in egit.git.\n\n Now that I understand what the heck was wrong, its obvious we\n need to do this, as DirCacheIterator was breaking the contract.\n\n I'd love to have a test case, but I just spent an hour trying to\n come up with one and failed.  I'd rather have the data corruption\n fix without tests than not at all, since its obviously wrong as-is.\n But if you want a test, propose one.  I'm just not seeing the\n magic necessary to get the corruption to trigger.\n\n .../spearce/jgit/dircache/DirCacheIterator.java    |    9 ++++++++\n .../jgit/treewalk/AbstractTreeIterator.java        |   19 +++++++++++++---\n .../spearce/jgit/treewalk/EmptyTreeIterator.java   |   22 ++++++++++++++++++++\n .../src/org/spearce/jgit/treewalk/TreeWalk.java    |    2 +-\n 4 files changed, 47 insertions(+), 5 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\nindex 356d735..6fb9510 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n@@ -45,6 +45,7 @@\n import org.spearce.jgit.lib.FileMode;\n import org.spearce.jgit.lib.Repository;\n import org.spearce.jgit.treewalk.AbstractTreeIterator;\n+import org.spearce.jgit.treewalk.EmptyTreeIterator;\n \n /**\n  * Iterate a {@link DirCache} as part of a <code>TreeWalk</code>.\n@@ -126,6 +127,14 @@ public AbstractTreeIterator createSubtreeIterator(final Repository repo)\n \t}\n \n \t@Override\n+\tpublic EmptyTreeIterator createEmptyTreeIterator() {\n+\t\tfinal byte[] n = new byte[Math.max(pathLen + 1, DEFAULT_PATH_SIZE)];\n+\t\tSystem.arraycopy(path, 0, n, 0, pathLen);\n+\t\tn[pathLen] = '/';\n+\t\treturn new EmptyTreeIterator(this, n, pathLen + 1);\n+\t}\n+\n+\t@Override\n \tpublic byte[] idBuffer() {\n \t\tif (currentSubtree != null)\n \t\t\treturn subtreeId;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex 2ff3b99..057250e 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -73,7 +73,8 @@\n  * @see CanonicalTreeParser\n  */\n public abstract class AbstractTreeIterator {\n-\tstatic final int DEFAULT_PATH_SIZE = 128;\n+\t/** Default size for the {@link #path} buffer. */\n+\tprotected static final int DEFAULT_PATH_SIZE = 128;\n \n \t/** A dummy object id buffer that matches the zero ObjectId. */\n \tprotected static final byte[] zeroid = new byte[Constants.OBJECT_ID_LENGTH];\n@@ -251,9 +252,10 @@ protected AbstractTreeIterator(final AbstractTreeIterator p,\n \t *            be moved into the larger buffer.\n \t */\n \tprotected void growPath(final int len) {\n-\t\tfinal byte[] n = new byte[path.length << 1];\n-\t\tSystem.arraycopy(path, 0, n, 0, len);\n-\t\tfor (AbstractTreeIterator p = this; p != null; p = p.parent)\n+\t\tfinal byte[] o = path;\n+\t\tfinal byte[] n = new byte[o.length << 1];\n+\t\tSystem.arraycopy(o, 0, n, 0, len);\n+\t\tfor (AbstractTreeIterator p = this; p != null && p.path == o; p = p.parent)\n \t\t\tp.path = n;\n \t}\n \n@@ -400,6 +402,15 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)\n \t\t\tthrows IncorrectObjectTypeException, IOException;\n \n \t/**\n+\t * Create a new iterator as though the current entry were a subtree.\n+\t *\n+\t * @return a new empty tree iterator.\n+\t */\n+\tpublic EmptyTreeIterator createEmptyTreeIterator() {\n+\t\treturn new EmptyTreeIterator(this);\n+\t}\n+\n+\t/**\n \t * Create a new iterator for the current entry's subtree.\n \t * <p>\n \t * The parent reference of the iterator must be <code>this</code>, otherwise\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\nindex eaca04e..cc5ea99 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\n@@ -57,6 +57,28 @@ EmptyTreeIterator(final AbstractTreeIterator p) {\n \t\tpathLen = pathOffset;\n \t}\n \n+\t/**\n+\t * Create an iterator for a subtree of an existing iterator.\n+\t * <p>\n+\t * The caller is responsible for setting up the path of the child iterator.\n+\t *\n+\t * @param p\n+\t *            parent tree iterator.\n+\t * @param childPath\n+\t *            path array to be used by the child iterator. This path must\n+\t *            contain the path from the top of the walk to the first child\n+\t *            and must end with a '/'.\n+\t * @param childPathOffset\n+\t *            position within <code>childPath</code> where the child can\n+\t *            insert its data. The value at\n+\t *            <code>childPath[childPathOffset-1]</code> must be '/'.\n+\t */\n+\tpublic EmptyTreeIterator(final AbstractTreeIterator p,\n+\t\t\tfinal byte[] childPath, final int childPathOffset) {\n+\t\tsuper(p, childPath, childPathOffset);\n+\t\tpathLen = childPathOffset - 1;\n+\t}\n+\n \t@Override\n \tpublic AbstractTreeIterator createSubtreeIterator(final Repository repo)\n \t\t\tthrows IncorrectObjectTypeException, IOException {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\nindex a41ca58..250b213 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n@@ -800,7 +800,7 @@ public void enterSubtree() throws MissingObjectException,\n \t\t\tif (t.matches == ch && !t.eof() && FileMode.TREE.equals(t.mode))\n \t\t\t\tn = t.createSubtreeIterator(db, idBuffer, curs);\n \t\t\telse\n-\t\t\t\tn = new EmptyTreeIterator(t);\n+\t\t\t\tn = t.createEmptyTreeIterator();\n \t\t\ttmp[i] = n;\n \t\t}\n \t\tdepth++;\n-- \n1.6.3.48.g99c76\n"},{"id":"113560","messageId":"200905112059.58212.robin.rosenberg.lists@dewire.com","threadId":"19293","inReplyTo":"1242064348-13197-1-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH] Fix data corruption in DirCacheIterator when EmptyTreeIterator is used","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2009-05-11T18:59:57Z","receivedAt":"2009-05-11T18:59:57Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"\nShouldn't we update some unit tests too? The dircache must be reliable.\n\n-- robin\n"},{"id":"113577","messageId":"20090511194429.GM30527@spearce.org","threadId":"19293","inReplyTo":"200905112059.58212.robin.rosenberg.lists@dewire.com","subject":"Re: [JGIT PATCH] Fix data corruption in DirCacheIterator when EmptyTreeIterator is used","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-05-11T19:44:29Z","receivedAt":"2009-05-11T19:44:29Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:\n> \n> Shouldn't we update some unit tests too? The dircache must be reliable.\n\nI see you ignored the remark I put in the cover letter below the ---.\n\nI think we should have unit tests too.  I just can't come up with\na way test the fix to prevent regression.  And I don't have any\nmore time for it probably the rest of this week.  I'd rather have\nthe corruption fix in the tree with no test than continue to have\nsurprising corruption under certain cases.  But if you or Mark can\noffer a test, I'd love to have it.\n\n-- \nShawn.\n"}]}