[PATCH JGIT] Computation of average could overflow

The code computes the average of two integers using either division or
signed right shift, and then uses the result as the
index of an array. If the values being averaged are very large, this can
overflow (resulting in the computation of a negative
average). Assuming that the result is intended to be nonnegative, you
can use an unsigned right shift instead. In other
words, rather that using (low+high)/2, use (low+high) >>> 1

This bug exists in many earlier implementations of binary search and
merge sort. Martin Buchholz found and fixed it
(http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6412541) in the JDK
libraries, and Joshua Bloch widely publicized
the bug pattern
(http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-i
t-nearly.html).

Signed-off-by: Matthias Sohn <redacted>
---
 .../src/org/spearce/jgit/dircache/DirCache.java    |    2 +-
 .../src/org/spearce/jgit/lib/Tree.java             |    2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

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 58da014..fa906fa 100644

--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java

@@ -593,7 +593,7 @@ int findEntry(final byte[] p, final int pLen) {
 		int low = 0;
 		int high = entryCnt;
 		do {
-			int mid = (low + high) >> 1;
+			int mid = (low + high) >>> 1;
 			final int cmp = cmp(p, pLen,

sortedEntries[mid]);
 			if (cmp < 0)
 				high = mid;

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java

b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java
index 0ecd04d..ff9e666 100644

--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java

@@ -136,7 +136,7 @@ private static final int binarySearch(final

TreeEntry[] entries,
 		int high = entries.length;
 		int low = 0;
 		do {
-			final int mid = (low + high) / 2;
+			final int mid = (low + high) >>> 1;
 			final int cmp =
compareNames(entries[mid].getNameUTF8(), nameUTF8,
 					nameStart, nameEnd,
TreeEntry.lastChar(entries[mid]), nameUTF8last);
 			if (cmp < 0)
-- 
1.6.2.2.1669.g7eaf8

Using new Integer(int) is guaranteed to always result in a new object
whereas Integer.valueOf(int) allows caching of values
to be done by the compiler, class library, or JVM. Using of cached
values avoids object allocation and the code will be faster.

Values between -128 and 127 are guaranteed to have corresponding cached
instances and using valueOf is approximately
3.5 times faster than using constructor. For values outside the constant
range the performance of both styles is the same.

Unless the class must be compatible with JVMs predating Java 1.5, use
either autoboxing or the valueOf() method when
creating instances of Long, Integer, Short, Character, and Byte.

Signed-off-by: Matthias Sohn <redacted>
---
 .../src/org/spearce/jgit/transport/IndexPack.java  |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git
a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java
b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java
index e0e4855..04ef59d 100644

--- a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java

@@ -383,7 +383,7 @@ private void resolveDeltas(final ProgressMonitor

progress)
 	private void resolveDeltas(final PackedObjectInfo oe) throws
IOException {
 		final int oldCRC = oe.getCRC();
 		if (baseById.containsKey(oe)
-				|| baseByPos.containsKey(new
Long(oe.getOffset())))
+				||
baseByPos.containsKey(Long.valueOf(oe.getOffset())))
 			resolveDeltas(oe.getOffset(), oldCRC,
Constants.OBJ_BAD, null, oe);
 	}
 

@@ -448,7 +448,7 @@ private void resolveDeltas(final long pos, final int

oldCRC, int type,
 	private void resolveChildDeltas(final long pos, int type, byte[]
data,
 			PackedObjectInfo oe) throws IOException {
 		final ArrayList<UnresolvedDelta> a =
baseById.remove(oe);
-		final ArrayList<UnresolvedDelta> b =
baseByPos.remove(new Long(pos));
+		final ArrayList<UnresolvedDelta> b =
baseByPos.remove(Long.valueOf(pos));
 		int ai = 0, bi = 0;
 		if (a != null && b != null) {
 			while (ai < a.size() && bi < b.size()) {

@@ -679,7 +679,7 @@ private void indexOneObject() throws IOException {
 				ofs <<= 7;
 				ofs += (c & 127);
 			}
-			final Long base = new Long(pos - ofs);
+			final Long base = Long.valueOf(pos - ofs);
 			ArrayList<UnresolvedDelta> r =

baseByPos.get(base);
 			if (r == null) {
 				r = new ArrayList<UnresolvedDelta>(8);
-- 
1.6.2.2.1669.g7eaf8

This method ignores the return value of java.io.InputStream.skip() which
can skip multiple bytes.  If the return value is not
checked, the caller will not be able to correctly handle the case where
fewer bytes were skipped than the caller requested.
This is a particularly insidious kind of bug, because in many programs,
skips from input streams usually do skip the full amount
of data requested, causing the program to fail only sporadically. With
Buffered streams, however, skip() will only skip data
in the buffer, and will routinely fail to skip the requested number of
bytes.

Signed-off-by: Matthias Sohn <redacted>
---
 .../jgit/transport/BundleFetchConnection.java      |   16
++++++++++++++--
 1 files changed, 14 insertions(+), 2 deletions(-)

diff --git
a/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.
java
b/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.
java
index 40bf7db..642c984 100644
---
a/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.
java
+++
b/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.
java

@@ -39,6 +39,7 @@
 package org.spearce.jgit.transport;
 
 import java.io.BufferedInputStream;
+import java.io.EOFException;
 import java.io.IOException;
 import java.io.InputStream;
 import java.util.ArrayList;

@@ -139,12 +140,23 @@ private String readLine(final byte[] hdrbuf)

throws IOException {
 		while (lf < cnt && hdrbuf[lf] != '\n')
 			lf++;
 		bin.reset();
-		bin.skip(lf);
+		skipFully(bin, lf);
 		if (lf < cnt && hdrbuf[lf] == '\n')
-			bin.skip(1);
+			skipFully(bin, 1);
 		return RawParseUtils.decode(Constants.CHARSET, hdrbuf,
0, lf);
 	}
 
+	// skip given number of bytes on InputStream respecting return
value of InputStream.skip()
+	static private void skipFully(InputStream in, long nBytes)
throws IOException {
+		long remaining = nBytes;
+		while (remaining != 0) {
+			long skipped = in.skip(remaining);
+			if (skipped == 0) // EOF
+				throw new EOFException();
+			remaining -= skipped;
+		}
+	}
+	
 	public boolean didFetchTestConnectivity() {
 		return false;
 	}
-- 
1.6.2.2.1669.g7eaf8

"Sohn, Matthias" [off-list ref] wrote:

Using new Integer(int) is guaranteed to always result in a new object
whereas Integer.valueOf(int) allows caching of values
to be done by the compiler, class library, or JVM. Using of cached
values avoids object allocation and the code will be faster.

NAK.

This thread came up about 5 weeks ago.  Please see my reply here:

  http://thread.gmane.org/gmane.comp.version-control.git/113738/focus=113785

 
-- 
Shawn.

"Sohn, Matthias" [off-list ref] wrote:

Using the java.lang.String(String) constructor wastes memory because the
object so constructed will be functionally
indistinguishable from the String passed as a parameter.  Just use the
argument String directly.

NAK.

Like the Long.valueOf() case this came up before:

http://thread.gmane.org/gmane.comp.version-control.git/113739/focus=113787
 
-- 
Shawn.

"Sohn, Matthias" [off-list ref] wrote:

The code computes the average of two integers using either division or
signed right shift, and then uses the result as the
index of an array. If the values being averaged are very large, this can
overflow (resulting in the computation of a negative
average). Assuming that the result is intended to be nonnegative, you
can use an unsigned right shift instead. In other
words, rather that using (low+high)/2, use (low+high) >>> 1

Thanks, applied.  But your patch was line wrapped.  I had to unwrap
it by hand.  Please try to configure your MUA not to line wrap
patches when it sends them.  :-|
 

 .../src/org/spearce/jgit/dircache/DirCache.java    |    2 +-
 .../src/org/spearce/jgit/lib/Tree.java             |    2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

-- 
Shawn.

"Sohn, Matthias" [off-list ref] wrote:

This method ignores the return value of java.io.InputStream.skip()

Doh.  In theory the skip should always succeed because the buffer
held the entire block we want to skip over due to the mark/reset
usage around this region.  But I agree, a skipFully() pattern is
better here.
 

We already have this method; see NB.skipFully().

NB also has readFully() and a few other useful functions for
dealing with common IO related patterns.

Please respin by calling NB.skipFully above rather than creating
a new package level method, and fix the line wrapping issue so we
can more easily apply it.  :-)

-- 
Shawn.

Using the java.lang.String(String) constructor wastes memory because the
object so constructed will be functionally
indistinguishable from the String passed as a parameter.  Just use the
argument String directly.

Signed-off-by: Matthias Sohn <redacted>
---
 .../src/org/spearce/jgit/lib/RefDatabase.java      |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java

b/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java
index 87f26bf..49da538 100644

--- a/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/RefDatabase.java

@@ -447,7 +447,7 @@ private synchronized void refreshPackedRefs() {
 
 					final int sp = p.indexOf(' ');
 					final ObjectId id =

ObjectId.fromString(p.substring(0, sp));
-					final String name = new
String(p.substring(sp + 1));
+					final String name =
p.substring(sp + 1);
 					last = new
Ref(Ref.Storage.PACKED, name, name, id);
 
newPackedRefs.put(last.getName(), last);
 				}
-- 
1.6.2.2.1669.g7eaf8

This method ignores the return value of java.io.InputStream.skip() which can skip multiple bytes.  If the return value is not checked, the caller will not be able to correctly handle the case where fewer bytes were skipped than the caller requested. This is a particularly insidious kind of bug, because in many programs, skips from input streams usually do skip the full amount of data requested, causing the program to fail only sporadically. With buffered streams, however, skip() will only skip data in the buffer, and will routinely fail to skip the requested number of bytes.

Signed-off-by: Matthias Sohn <redacted>
---
hopefully this time Exchange server doesn't mangle the patch

 .../jgit/transport/BundleFetchConnection.java      |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.java
index 40bf7db..2e2977e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/BundleFetchConnection.java

@@ -60,6 +60,7 @@
 import org.spearce.jgit.revwalk.RevFlag;
 import org.spearce.jgit.revwalk.RevObject;
 import org.spearce.jgit.revwalk.RevWalk;
+import org.spearce.jgit.util.NB;
 import org.spearce.jgit.util.RawParseUtils;
 
 /**

@@ -139,9 +140,9 @@ private String readLine(final byte[] hdrbuf) throws IOException {
 		while (lf < cnt && hdrbuf[lf] != '\n')
 			lf++;
 		bin.reset();
-		bin.skip(lf);
+		NB.skipFully(bin, lf);
 		if (lf < cnt && hdrbuf[lf] == '\n')
-			bin.skip(1);
+			NB.skipFully(bin, 1);
 		return RawParseUtils.decode(Constants.CHARSET, hdrbuf, 0, lf);
 	}
 

-- 
1.6.2.2.1669.g7eaf8