[JGIT] Re: blinking test WindowCacheGetTest.testCache_TooSmallLimit

[JGIT] Re: blinking test WindowCacheGetTest.testCache_TooSmallLimit

[Shawn O. Pearce]

Constantine Plotnikov <constantine.plotnikov@gmail.com> wrote:
> The test WindowCacheGetTest.testCache_TooSmallLimit sometimes fails
> (on less than third of runs on Windows) with the following stacktrace:
> 
> junit.framework.AssertionFailedError
> at junit.framework.Assert.fail(Assert.java:47)
> at junit.framework.Assert.assertTrue(Assert.java:20)
> at junit.framework.Assert.assertTrue(Assert.java:27)
> at org.spearce.jgit.lib.WindowCacheGetTest.checkLimits(WindowCacheGetTest.java:112)
> at org.spearce.jgit.lib.WindowCacheGetTest.testCache_TooSmallLimit(WindowCacheGetTest.java:106)
> 
> This happens on Windows and Linux, but I do not know about
> frequency on Linux.

I'd say the frequency on Linux is about 1/6 for me.  I have yet to
be bothered enough to track it down, but its starting to get there.
Maybe I'll try to look at it tomorrow.

-- 
Shawn.

Re: [JGIT] Re: blinking test WindowCacheGetTest.testCache_TooSmallLimit

[Robin Rosenberg]

lördag 25 juli 2009 00:51:18 skrev "Shawn O. Pearce" <spearce@spearce.org>:
> Constantine Plotnikov <constantine.plotnikov@gmail.com> wrote:
> > The test WindowCacheGetTest.testCache_TooSmallLimit sometimes fails
> > (on less than third of runs on Windows) with the following stacktrace:
> > 
> > junit.framework.AssertionFailedError
> > at junit.framework.Assert.fail(Assert.java:47)
> > at junit.framework.Assert.assertTrue(Assert.java:20)
> > at junit.framework.Assert.assertTrue(Assert.java:27)
> > at org.spearce.jgit.lib.WindowCacheGetTest.checkLimits(WindowCacheGetTest.java:112)
> > at org.spearce.jgit.lib.WindowCacheGetTest.testCache_TooSmallLimit(WindowCacheGetTest.java:106)
> > 
> > This happens on Windows and Linux, but I do not know about
> > frequency on Linux.
> 
> I'd say the frequency on Linux is about 1/6 for me.  I have yet to
> be bothered enough to track it down, but its starting to get there.
> Maybe I'll try to look at it tomorrow.

Could it be threading-related (cache). I've never seen it on the machine where I build for
the update site and it is a single core machine, but I "this" machine that has two cores it happens, not
as offen as 1/6, but enough to annoy me a bit, perhaps 1/20. If it is related to bad synchronization
it should happen more often the more cores you have.

-- robin

Re: [JGIT] Re: blinking test WindowCacheGetTest.testCache_TooSmallLimit

[Shawn O. Pearce]

Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
> > Constantine Plotnikov <constantine.plotnikov@gmail.com> wrote:
> > > The test WindowCacheGetTest.testCache_TooSmallLimit sometimes fails
> > > (on less than third of runs on Windows) with the following stacktrace:
> 
> Could it be threading-related (cache). I've never seen it on the machine where I build for
> the update site and it is a single core machine, but I "this" machine that has two cores it happens, not
> as offen as 1/6, but enough to annoy me a bit, perhaps 1/20. If it is related to bad synchronization
> it should happen more often the more cores you have.

No, its not threading related.  I think I at least partially
understand what is going on.

WindowCache's base class, OffsetCache, does evictions by randomly
selecting a starting point in the table, and then scanning at most
evictBatch segments of the table before giving up.

When testCache_TooSmallLimit needs to access another window it must
first evict the current window, as the cache size is set to exactly
1 window in this test.

If the RNG selects the starting point at an empty segment, and
evictBatch is smaller than the total table size, we may not scan
the segment which contains an open window.  The eviction stops
before it actually expires an entry, and the cache is permitted to
allocate more than it was supposed to.

The test failure is random due to two different things going on:

 - The starting point for eviction is determined by an RNG, whose
   seed is initialized randomly at the start of the tests.

 - The position of a given entry in the segment table is partially
   determined by the System.identityHashCode of the PackFile instance
   it is being loaded for.  Since that differs as the JVM allocs
   and reclaims objects, there is some randomness caused by the
   order tests are run in.

However, in this test I'm still not quite sure why its failing,
because evictBatch is equal to the table size (both 2), so any
eviction here should have scanned the full table.

-- 
Shawn.

[JGIT PATCH] Fix WindowCacheGetTest.testCache_TooSmallLimit failures

[Shawn O. Pearce]

Ever since 2d77d30b5f when I rewrote WindowCache we have been seeing
random failures inside of the TooSmallLimit test case.

These test failures have been occurring because the cache contained
more open bytes than it was configured to permit.

The cache was permitted to open more bytes than its configured limit
because the eviction routine was always skipping the last bucket
under some conditions.  If the cache table was sized the same as its
evictBatch, which happens for any fairly small table, the eviction
routine broke too early if it started at a non-zero position in the
table and wrapped around during its search.  By breaking too early
the routine did not actually perform an eviction, leaving windows
open it should have closed.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
  > Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
  > > > Constantine Plotnikov <constantine.plotnikov@gmail.com> wrote:
  > > > > The test WindowCacheGetTest.testCache_TooSmallLimit sometimes fails
  > > > > (on less than third of runs on Windows) with the following stacktrace:
  > > 
  > > Could it be threading-related (cache). I've never seen it on the machine where I build for
  > > the update site and it is a single core machine, but I "this" machine that has two cores it happens, not
  > > as offen as 1/6, but enough to annoy me a bit, perhaps 1/20. If it is related to bad synchronization
  > > it should happen more often the more cores you have.
  
  I think this fixes it.

 .../src/org/spearce/jgit/lib/OffsetCache.java      |    7 ++-----
 1 files changed, 2 insertions(+), 5 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java
index b81c7e0..7ac532d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/OffsetCache.java
@@ -253,12 +253,11 @@ private void hit(final Ref<V> r) {
 	}
 
 	private void evict() {
-		final int start = rng.nextInt(tableSize);
-		int ptr = start;
 		while (isFull()) {
+			int ptr = rng.nextInt(tableSize);
 			Entry<V> old = null;
 			int slot = 0;
-			for (int b = evictBatch - 1; b >= 0; b--) {
+			for (int b = evictBatch - 1; b >= 0; b--, ptr++) {
 				if (tableSize <= ptr)
 					ptr = 0;
 				for (Entry<V> e = table.get(ptr); e != null; e = e.next) {
@@ -269,8 +268,6 @@ private void evict() {
 						slot = ptr;
 					}
 				}
-				if (++ptr == start)
-					return;
 			}
 			if (old != null) {
 				old.kill();
-- 
1.6.4.rc2.216.g769fa

Re: [JGIT PATCH] Fix WindowCacheGetTest.testCache_TooSmallLimit failures

[Robin Rosenberg]

lördag 25 juli 2009 22:00:56 skrev "Shawn O. Pearce" <spearce@spearce.org>:
> Ever since 2d77d30b5f when I rewrote WindowCache we have been seeing
> random failures inside of the TooSmallLimit test case.
> 
> These test failures have been occurring because the cache contained
> more open bytes than it was configured to permit.
> 
> The cache was permitted to open more bytes than its configured limit
> because the eviction routine was always skipping the last bucket
> under some conditions.  If the cache table was sized the same as its
> evictBatch, which happens for any fairly small table, the eviction
> routine broke too early if it started at a non-zero position in the
> table and wrapped around during its search.  By breaking too early
> the routine did not actually perform an eviction, leaving windows
> open it should have closed.

We should have a test for that then.

-- robin

Re: [JGIT PATCH] Fix WindowCacheGetTest.testCache_TooSmallLimit failures

[Shawn O. Pearce]

Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
> l?rdag 25 juli 2009 22:00:56 skrev "Shawn O. Pearce" <spearce@spearce.org>:
> > Ever since 2d77d30b5f when I rewrote WindowCache we have been seeing
> > random failures inside of the TooSmallLimit test case.
> > 
> > These test failures have been occurring because the cache contained
> > more open bytes than it was configured to permit.
> > 
> > The cache was permitted to open more bytes than its configured limit
> > because the eviction routine was always skipping the last bucket
> > under some conditions.  If the cache table was sized the same as its
> > evictBatch, which happens for any fairly small table, the eviction
> > routine broke too early if it started at a non-zero position in the
> > table and wrapped around during its search.  By breaking too early
> > the routine did not actually perform an eviction, leaving windows
> > open it should have closed.
> 
> We should have a test for that then.

We did, this one.  :-)

-- 
Shawn.