[PATCH JGIT] Computation of average could overflow

[PATCH JGIT] Computation of average could overflow

[Sohn, Matthias]

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 <matthias.sohn@sap.com>
---
 .../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

[PATCH JGIT] Method invokes inefficient new String(String) constructor

[Sohn, Matthias]

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 <matthias.sohn@sap.com>
---
 .../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

[PATCH JGIT] Method invokes inefficient Number constructor; use static valueOf instead

[Sohn, Matthias]

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 <matthias.sohn@sap.com>
---
 .../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

[PATCH JGIT] Method ignores results of InputStream.skip()

[Sohn, Matthias]

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 <matthias.sohn@sap.com>
---
 .../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

Re: [PATCH JGIT] Method ignores results of InputStream.skip()

[Shawn O. Pearce]

"Sohn, Matthias" <matthias.sohn@sap.com> 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.
 
> @@ -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)

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.

[PATCH JGIT] Method ignores results of InputStream.skip()

[Sohn, Matthias]

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 <matthias.sohn@sap.com>
---
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

Re: [PATCH JGIT] Method invokes inefficient Number constructor; use static valueOf instead

[Shawn O. Pearce]

"Sohn, Matthias" <matthias.sohn@sap.com> 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.

Re: [PATCH JGIT] Method invokes inefficient new String(String) constructor

[Shawn O. Pearce]

"Sohn, Matthias" <matthias.sohn@sap.com> 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.

Re: [PATCH JGIT] Computation of average could overflow

[Shawn O. Pearce]

"Sohn, Matthias" <matthias.sohn@sap.com> 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.

[PATCH JGIT] Method invokes inefficient Number constructor; use static valueOf instead

[Yann Simon]

>From FindBugs:
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.

Signed-off-by: Yann Simon <yann.simon.fr@gmail.com>
---
 .../jgit/errors/NoClosingBracketException.java     |    4 ++--
 .../src/org/spearce/jgit/transport/IndexPack.java  |    6 +++---
 2 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/errors/NoClosingBracketException.java b/org.spearce.jgit/src/org/spearce/jgit/errors/NoClosingBracketException.java
index 8fe9ab1..b325b45 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/errors/NoClosingBracketException.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/errors/NoClosingBracketException.java
@@ -64,7 +64,7 @@ super(createMessage(indexOfOpeningBracket, openingBracket,
 	private static String createMessage(final int indexOfOpeningBracket,
 			final String openingBracket, final String closingBracket) {
 		return String.format("No closing %s found for %s at index %s.",
-				closingBracket, openingBracket, new Integer(
-						indexOfOpeningBracket));
+				closingBracket, openingBracket,
+				Integer.valueOf(indexOfOpeningBracket));
 	}
 }
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.1.2

Re: [PATCH JGIT] Method invokes inefficient Number constructor; use static valueOf instead

[Ferry Huberts (Pelagic)]

Yann Simon wrote:
> From FindBugs:

+1

also, junit would be another +1 AFAIC :-)

Re: [PATCH JGIT] Method invokes inefficient Number constructor; use static valueOf instead

[Shawn O. Pearce]

Yann Simon <yann.simon.fr@gmail.com> wrote:
> From FindBugs:
> 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.

Ah, yes.

> Values between -128 and 127 are guaranteed to have corresponding cached
> instances [...]
...
> 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())))

Why I box with new Long() over Long.valueOf():

 The standard only requires -128..127 to be cached.  A JRE can
 cache value outside of this range if it chooses, but long has a
 huge range, its unlikely to cache much beyond this required region.

 Most pack files are in the 10 MB...100+ MB range.  Most objects
 take more than 100 bytes in a pack, even compressed delta encoded.
 Thus any object after the first is going to have its offset outside
 of the cached range.

 In other words, why waste the CPU cycles on the "cached range
 bounds check" when I'm always going to fail and allocate.  I might
 as well just allocate

 These sections of code are rather performance critical for the
 indexing phase of a pack receive, on either side of a connection.
 I need to shave even more instructions out of the critical paths,
 as its not fast enough as-is.  Using new Long() is quicker than
 using Long.valueOf(), so new Long() it is.

> @@ -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);

See above for why these two hunks allocate rather than use valueOf()
or even the implicit compiler produced auto-boxing (which uses
valueOf).

But your first hunk (which I snipped) is fine to apply.

-- 
Shawn.

Re: [PATCH JGIT] Method invokes inefficient Number constructor; use static valueOf instead

[Yann Simon]

2009/3/19 Shawn O. Pearce <spearce@spearce.org>:
> Why I box with new Long() over Long.valueOf():
>
>  The standard only requires -128..127 to be cached.  A JRE can
>  cache value outside of this range if it chooses, but long has a
>  huge range, its unlikely to cache much beyond this required region.
>
>  Most pack files are in the 10 MB...100+ MB range.  Most objects
>  take more than 100 bytes in a pack, even compressed delta encoded.
>  Thus any object after the first is going to have its offset outside
>  of the cached range.
>
>  In other words, why waste the CPU cycles on the "cached range
>  bounds check" when I'm always going to fail and allocate.  I might
>  as well just allocate
>
>  These sections of code are rather performance critical for the
>  indexing phase of a pack receive, on either side of a connection.
>  I need to shave even more instructions out of the critical paths,
>  as its not fast enough as-is.  Using new Long() is quicker than
>  using Long.valueOf(), so new Long() it is.

It makes sense.
Thank you for the explanation.

Yann