threads / patch / 18788

patchImprove end-of-file detection in DirCache

Subject: [EGIT PATCH] Improve end-of-file detection in DirCache

## tl;dr

6 messages between Apr 8, 2009 and Apr 13, 2009. Diffs are folded; open one to read it.

replies: 5people: 2as markdown or json

Robin Rosenberg· Apr 8, 2009, 15:50 UTC · lore

When reading from an BufferInputStream attached to a FileInputStream the available() method seems to return the number of unread bytes in the buffer plus the unread number of bytes in the file.

There is no guarantee for this behaviour so this quick fix might not be as stable as we would wish.

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
  http://code.google.com/p/egit/issues/detail?id=66
---
 .../src/org/spearce/jgit/dircache/DirCache.java    |   16 ++++++++++------
 1 files changed, 10 insertions(+), 6 deletions(-)
Show changes to org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java +10 −6
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
index 8eb4022..657762e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
@@ -45,7 +45,6 @@
 import java.io.IOException;
 import java.io.OutputStream;
 import java.nio.ByteBuffer;
-import java.nio.channels.FileChannel;
 import java.security.DigestOutputStream;
 import java.security.MessageDigest;
 import java.util.Comparator;
@@ -344,8 +343,6 @@ public void clear() {
 
 	private void readFrom(final FileInputStream inStream) throws IOException,
 			CorruptObjectException {
-		final FileChannel fd = inStream.getChannel();
-		final long sizeOnDisk = fd.size();
 		final BufferedInputStream in = new BufferedInputStream(inStream);
 
 		// Read the index header and verify we understand it.
@@ -369,9 +366,16 @@ private void readFrom(final FileInputStream inStream) throws IOException,
 			sortedEntries[i] = new DirCacheEntry(infos, i * INFO_LEN, in);
 		lastModified = liveFile.lastModified();
 
-		// After the file entries are index extensions.
-		//
-		while (fd.position() - in.available() < sizeOnDisk - 20) {
+		/*
+		 * InputStream.available() on file input streams seems to return the
+		 * rest of the file i.e. buffer size + unread file on disk. There is no
+		 * guarantee for this so we need to fix this or we may miss extensions
+		 * when reading the index in a few races cases.
+		 *
+		 * That is currently no disaster though.
+		 */
+		while (in.available() > 20) {
+			// After the file entries are index extensions.
 			NB.readFully(in, hdr, 0, 8);
 			switch (NB.decodeInt32(hdr, 0)) {
 			case EXT_TREE: {
-- 
1.6.2.2.446.gfbdc0
Shawn O. Pearce· Apr 9, 2009, 15:28 UTC · re: Robin Rosenberg · lore

[JGIT PATCH 1/2] Improve end-of-file detection in DirCache

When reading from a BufferInputStream attached to a FileInputStream the available() method seems to return the number of unread bytes in the buffer plus the unread number of bytes in the file. There is no guarantee for this behavior, so we can't rely on it.

Instead we read the expected 20 byte SHA1 trailer into a temporary buffer, and then poll for a remaining byte. If another byte is still present in the input stream it indicates that there is more than 20 bytes worth of data remaining, which means an extension must be available at the current position. If there is in fact an extension we put back the 21 bytes we read and proceed to do an 8 byte read for the extension header.

This relies on BufferInputStream's ability to buffer at least 21 bytes of data, and put them all back in the event that we found an extension. This is a much more common usage of the stream API and is something we can rely on working correctly all of the time, on any standard library implementation.

Found-by: Robin Rosenberg <robin.rosenberg@dewire.com>
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 I'd rather do this instead.  Its accurate 100% of the time and isn't
 a hack.  So I'm dropping the patch I'm replying to and asking you
 to review and apply this 2 patch series (or at least this first
 one which should fix the problem).
 
 .../src/org/spearce/jgit/dircache/DirCache.java    |   20 +++++++++++++-------
 1 files changed, 13 insertions(+), 7 deletions(-)
Show changes to org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java +13 −7
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
index 8eb4022..5df0f59 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
@@ -45,7 +45,6 @@
 import java.io.IOException;
 import java.io.OutputStream;
 import java.nio.ByteBuffer;
-import java.nio.channels.FileChannel;
 import java.security.DigestOutputStream;
 import java.security.MessageDigest;
 import java.util.Comparator;
@@ -344,13 +343,11 @@ public void clear() {
 
 	private void readFrom(final FileInputStream inStream) throws IOException,
 			CorruptObjectException {
-		final FileChannel fd = inStream.getChannel();
-		final long sizeOnDisk = fd.size();
 		final BufferedInputStream in = new BufferedInputStream(inStream);
 
 		// Read the index header and verify we understand it.
 		//
-		final byte[] hdr = new byte[12];
+		final byte[] hdr = new byte[20];
 		NB.readFully(in, hdr, 0, 12);
 		if (!is_DIRC(hdr))
 			throw new CorruptObjectException("Not a DIRC file.");
@@ -369,13 +366,22 @@ private void readFrom(final FileInputStream inStream) throws IOException,
 			sortedEntries[i] = new DirCacheEntry(infos, i * INFO_LEN, in);
 		lastModified = liveFile.lastModified();
 
-		// After the file entries are index extensions.
+		// After the file entries are index extensions, and then a footer.
 		//
-		while (fd.position() - in.available() < sizeOnDisk - 20) {
-			NB.readFully(in, hdr, 0, 8);
+		for (;;) {
+			in.mark(21);
+			NB.readFully(in, hdr, 0, 20);
+			if (in.read() < 0) {
+				// No extensions present; the file ended where we expected.
+				//
+				break;
+			}
+			in.reset();
+
 			switch (NB.decodeInt32(hdr, 0)) {
 			case EXT_TREE: {
 				final byte[] raw = new byte[NB.decodeInt32(hdr, 4)];
+				NB.skipFully(in, 8);
 				NB.readFully(in, raw, 0, raw.length);
 				tree = new DirCacheTree(raw, new MutableInteger(), null);
 				break;
-- 
1.6.2.2.600.g24c24
Shawn O. Pearce· Apr 9, 2009, 15:28 UTC · re: Shawn O. Pearce · lore

[JGIT PATCH 2/2] Validate the DIRC footer during read

To ensure we didn't read a partial file, or a file that has a corrupt content (e.g. due power failure on a buggy unjournaled filesystem) we now validate the entire content of the DIRC file through its final SHA1 checksum at the end of the stream.

This slightly slows down the read path, as we now have to process a lot of small buffers (info and path objects) through the digest, but we're better off ensuring the content is reasonably sane.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 This isn't strictly necessary to fix the bug you identified, but
 I was in the neighboorhood and stronger data validation on input
 is potentially worthwhile...
 .../src/org/spearce/jgit/dircache/DirCache.java    |   12 +++++++++++-
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |   13 +++++++++++--
 2 files changed, 22 insertions(+), 3 deletions(-)
Show changes to 2 files +22 −3

org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java, org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
index 5df0f59..58da014 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
@@ -47,6 +47,7 @@
 import java.nio.ByteBuffer;
 import java.security.DigestOutputStream;
 import java.security.MessageDigest;
+import java.util.Arrays;
 import java.util.Comparator;
 
 import org.spearce.jgit.errors.CorruptObjectException;
@@ -344,11 +345,13 @@ public void clear() {
 	private void readFrom(final FileInputStream inStream) throws IOException,
 			CorruptObjectException {
 		final BufferedInputStream in = new BufferedInputStream(inStream);
+		final MessageDigest md = Constants.newMessageDigest();
 
 		// Read the index header and verify we understand it.
 		//
 		final byte[] hdr = new byte[20];
 		NB.readFully(in, hdr, 0, 12);
+		md.update(hdr, 0, 12);
 		if (!is_DIRC(hdr))
 			throw new CorruptObjectException("Not a DIRC file.");
 		final int ver = NB.decodeInt32(hdr, 4);
@@ -363,7 +366,7 @@ private void readFrom(final FileInputStream inStream) throws IOException,
 		final byte[] infos = new byte[INFO_LEN * entryCnt];
 		sortedEntries = new DirCacheEntry[entryCnt];
 		for (int i = 0; i < entryCnt; i++)
-			sortedEntries[i] = new DirCacheEntry(infos, i * INFO_LEN, in);
+			sortedEntries[i] = new DirCacheEntry(infos, i * INFO_LEN, in, md);
 		lastModified = liveFile.lastModified();
 
 		// After the file entries are index extensions, and then a footer.
@@ -381,8 +384,10 @@ private void readFrom(final FileInputStream inStream) throws IOException,
 			switch (NB.decodeInt32(hdr, 0)) {
 			case EXT_TREE: {
 				final byte[] raw = new byte[NB.decodeInt32(hdr, 4)];
+				md.update(hdr, 0, 8);
 				NB.skipFully(in, 8);
 				NB.readFully(in, raw, 0, raw.length);
+				md.update(raw, 0, raw.length);
 				tree = new DirCacheTree(raw, new MutableInteger(), null);
 				break;
 			}
@@ -405,6 +410,11 @@ private void readFrom(final FileInputStream inStream) throws IOException,
 				}
 			}
 		}
+
+		final byte[] exp = md.digest();
+		if (!Arrays.equals(exp, hdr)) {
+			throw new CorruptObjectException("DIRC checksum mismatch");
+		}
 	}
 
 	private static boolean is_DIRC(final byte[] hdr) {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
index 6d46648..47b1cc5 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
@@ -43,6 +43,7 @@
 import java.io.InputStream;
 import java.io.OutputStream;
 import java.nio.ByteBuffer;
+import java.security.MessageDigest;
 import java.util.Arrays;
 
 import org.spearce.jgit.lib.AnyObjectId;
@@ -113,17 +114,19 @@
 	final byte[] path;
 
 	DirCacheEntry(final byte[] sharedInfo, final int infoAt,
-			final InputStream in) throws IOException {
+			final InputStream in, final MessageDigest md) throws IOException {
 		info = sharedInfo;
 		infoOffset = infoAt;
 
 		NB.readFully(in, info, infoOffset, INFO_LEN);
+		md.update(info, infoOffset, INFO_LEN);
 
 		int pathLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & NAME_MASK;
 		int skipped = 0;
 		if (pathLen < NAME_MASK) {
 			path = new byte[pathLen];
 			NB.readFully(in, path, 0, pathLen);
+			md.update(path, 0, pathLen);
 		} else {
 			final ByteArrayOutputStream tmp = new ByteArrayOutputStream();
 			{
@@ -142,6 +145,8 @@ DirCacheEntry(final byte[] sharedInfo, final int infoAt,
 			path = tmp.toByteArray();
 			pathLen = path.length;
 			skipped = 1; // we already skipped 1 '\0' above to break the loop.
+			md.update(path, 0, pathLen);
+			md.update((byte) 0);
 		}
 
 		// Index records are padded out to the next 8 byte alignment
@@ -149,7 +154,11 @@ DirCacheEntry(final byte[] sharedInfo, final int infoAt,
 		//
 		final int actLen = INFO_LEN + pathLen;
 		final int expLen = (actLen + 8) & ~7;
-		NB.skipFully(in, expLen - actLen - skipped);
+		final int padLen = expLen - actLen - skipped;
+		if (padLen > 0) {
+			NB.skipFully(in, padLen);
+			md.update(nullpad, 0, padLen);
+		}
 	}
 
 	/**
-- 
1.6.2.2.600.g24c24
Robin Rosenberg· Apr 10, 2009, 02:35 UTC · re: Shawn O. Pearce · lore

Re: [JGIT PATCH 1/2] Improve end-of-file detection in DirCache

torsdag 09 april 2009 17:28:18 skrev "Shawn O. Pearce" <spearce@spearce.org>:
Show 18 quoted lines
> When reading from a BufferInputStream attached to a FileInputStream
> the available() method seems to return the number of unread bytes
> in the buffer plus the unread number of bytes in the file.  There is
> no guarantee for this behavior, so we can't rely on it.
> 
> Instead we read the expected 20 byte SHA1 trailer into a temporary
> buffer, and then poll for a remaining byte.  If another byte is
> still present in the input stream it indicates that there is more
> than 20 bytes worth of data remaining, which means an extension
> must be available at the current position.  If there is in fact
> an extension we put back the 21 bytes we read and proceed to do
> an 8 byte read for the extension header.
> 
> This relies on BufferInputStream's ability to buffer at least 21
> bytes of data, and put them all back in the event that we found
> an extension.  This is a much more common usage of the stream API
> and is something we can rely on working correctly all of the time,
> on any standard library implementation.
Much better. Here's a regression test, fails before, but not after.
-- robin
>From b6561578a5ff48309f69a8d442cf47ec1b51bc49 Mon Sep 17 00:00:00 2001
From: Robin Rosenberg <robin.rosenberg@dewire.com>
Date: Fri, 10 Apr 2009 04:16:31 +0200
Subject: [EGIT PATCH] Test case for the DirCache reading code.
Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../spearce/jgit/dircache/DirCacheTreeTest.java    |   33 ++++++++++++++++++++
 1 files changed, 33 insertions(+), 0 deletions(-)
Show changes to org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheTreeTest.java +33 −0
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheTreeTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheTreeTest.java
index b37095d..aca0b90 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheTreeTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheTreeTest.java
@@ -37,6 +37,9 @@
 
 package org.spearce.jgit.dircache;
 
+import java.io.IOException;
+
+import org.spearce.jgit.errors.CorruptObjectException;
 import org.spearce.jgit.lib.RepositoryTestCase;
 
 public class DirCacheTreeTest extends RepositoryTestCase {
@@ -147,4 +150,34 @@ public void testTwoLevelSubtree() throws Exception {
 		assertEquals(acLast - acFirst + 1, acTree.getEntrySpan());
 		assertFalse(acTree.isValid());
 	}
+
+	/**
+	 * We had bugs related to buffer size in the DirCache. This test creates an
+	 * index larger than the default BufferedInputStream buffer size. This made
+	 * the DirCache unable to read the extensions when index size exceeded the
+	 * buffer size (in some cases at least).
+	 * 
+	 * @throws CorruptObjectException
+	 * @throws IOException
+	 */
+	public void testWriteReadTree() throws CorruptObjectException, IOException {
+		final DirCache dc = DirCache.lock(db);
+
+		final String A = String.format("a%2000s", "a");
+		final String B = String.format("b%2000s", "b");
+		final String[] paths = { A + ".", A + "." + B, A + "/" + B, A + "0" + B };
+		final DirCacheEntry[] ents = new DirCacheEntry[paths.length];
+		for (int i = 0; i < paths.length; i++)
+			ents[i] = new DirCacheEntry(paths[i]);
+
+		final DirCacheBuilder b = dc.builder();
+		for (int i = 0; i < ents.length; i++)
+			b.add(ents[i]);
+
+		b.commit();
+		DirCache read = DirCache.read(db);
+
+		assertEquals(paths.length, read.getEntryCount());
+		assertEquals(1, read.getCacheTree(true).getChildCount());
+	}
 }
Robin Rosenberg· Apr 13, 2009, 11:53 UTC · re: Shawn O. Pearce · lore

Re: [JGIT PATCH 1/2] Improve end-of-file detection in DirCache

As a consequence, I'll reapply the GitMoveDeleteHook reverts we made just prior to 0.4 and start deprecating GitIndex. Any preference for re-apply or reverting the reverts?

The reverts are in e7307f14c531d52cf231c39d844841c4adaf5e5a and 2066e55e4740d9e9cfaf455596f832ff694f853a

I think the original patches are valid.
-- robin
Shawn O. Pearce· Apr 13, 2009, 15:42 UTC · re: Robin Rosenberg · lore

Re: [JGIT PATCH 1/2] Improve end-of-file detection in DirCache

Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
Show 9 quoted lines
> 
> As a consequence, I'll reapply the GitMoveDeleteHook reverts we made just
> prior to 0.4 and start deprecating GitIndex. Any preference for re-apply or
> reverting the reverts?
> 
> The reverts are in  e7307f14c531d52cf231c39d844841c4adaf5e5a and 
> 2066e55e4740d9e9cfaf455596f832ff694f853a
> 
> I think the original patches are valid.
Hmmph.

I would cherry-pick with --no-commit and then make two notes in the final commit message, e.g.:

  ...
  Temporary-revert: $REVERTCOMMIT
  Originally: $FIRSTCOMMIT
  Signed-off-by: ...
so we can "thread" them with hyperlinks in viewers.
-- 
Shawn.

← back to recent threads