threads / discuss / 20225

[JGIT] Re: blinking test WindowCacheGetTest.testCache_TooSmallLimit

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

## tl;dr

6 messages between Jul 24, 2009 and Jul 25, 2009.

replies: 5people: 2as markdown or json

Shawn O. Pearce· Jul 24, 2009, 22:51 UTC · lore

Constantine Plotnikov <constantine.plotnikov@gmail.com> wrote:

Show 12 quoted lines

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

Robin Rosenberg· Jul 25, 2009, 17:34 UTC · re: Shawn O. Pearce · lore

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

lördag 25 juli 2009 00:51:18 skrev "Shawn O. Pearce" <spearce@spearce.org>:

Show 17 quoted lines

> 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

Shawn O. Pearce· Jul 25, 2009, 19:42 UTC · re: Robin Rosenberg · lore

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

Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:

Show 8 quoted lines

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

Shawn O. Pearce· Jul 25, 2009, 20:00 UTC · re: Shawn O. Pearce · lore

[JGIT PATCH] Fix WindowCacheGetTest.testCache_TooSmallLimit failures

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

Robin Rosenberg· Jul 25, 2009, 23:25 UTC · re: Shawn O. Pearce · lore

Re: [JGIT PATCH] Fix WindowCacheGetTest.testCache_TooSmallLimit failures

lördag 25 juli 2009 22:00:56 skrev "Shawn O. Pearce" <spearce@spearce.org>:

Show 14 quoted lines

> 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

Shawn O. Pearce· Jul 25, 2009, 23:30 UTC · re: Robin Rosenberg · lore

Re: [JGIT PATCH] Fix WindowCacheGetTest.testCache_TooSmallLimit failures

Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:

Show 17 quoted lines

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