[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 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.

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 new String(String) constructor

[Yann Simon]

2009/3/19 Shawn O. Pearce <spearce@spearce.org>:
> Yann Simon <yann.simon.fr@gmail.com> wrote:
>> From FindBugs:
>> 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: Yann Simon <yann.simon.fr@gmail.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);
>
> I had a specific reason for forcing a new String object here.
>
> The line in question, p, is from the packed-refs file and
> contains the entire SHA-1 in hex form at the beginning of it.
> We've converted that into binary as an ObjectId, it uses 1/4 the
> space of the string portion.
>
> The Ref object, its ObjectId, and its name string, are going to be
> cached in a Map, probably long-term.  We're better off shedding the
> 80 bytes of memory used to hold the hex SHA-1 then risk substring()
> deciding its "faster" to reuse the char[] then to make a copy of it.

However, using the trick newString = new String(aString.substring(),
i) does not work on all JVM.
With an IBM JVM, the newString will still contain the original array of chars.

Another solution that work on all JVM could be:
newString = new String(aString.substring(i).toCharArray())
Or
newString = new String(aString.toCharArray(), i, aString.length() - i)

I like the latter one.

Yann

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

[Yann Simon]

2009/3/19 Shawn O. Pearce <spearce@spearce.org>:
> The line in question, p, is from the packed-refs file and
> contains the entire SHA-1 in hex form at the beginning of it.
> We've converted that into binary as an ObjectId, it uses 1/4 the
> space of the string portion.
>
> The Ref object, its ObjectId, and its name string, are going to be
> cached in a Map, probably long-term.  We're better off shedding the
> 80 bytes of memory used to hold the hex SHA-1 then risk substring()
> deciding its "faster" to reuse the char[] then to make a copy of it.

Thany you for the explanation.
I learn something, and my tests confirm it.
The p.substring(...) can keep the entire array of char by only
updating the intern offset value.
new String(p.subtring(...)) make sure that the variable contains only
the final chars.

Yann

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

[Shawn O. Pearce]

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

I had a specific reason for forcing a new String object here.

The line in question, p, is from the packed-refs file and
contains the entire SHA-1 in hex form at the beginning of it.
We've converted that into binary as an ObjectId, it uses 1/4 the
space of the string portion.

The Ref object, its ObjectId, and its name string, are going to be
cached in a Map, probably long-term.  We're better off shedding the
80 bytes of memory used to hold the hex SHA-1 then risk substring()
deciding its "faster" to reuse the char[] then to make a copy of it.

-- 
Shawn.

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

[Yann Simon]

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