GC failure w/ THREAD_LOCAL_ALLOC ?

[Bryce McKinlay <bryce at waitaki dot otago dot ac dot nz>]

While testing thread local allocation on PowerPC, I ran into a problem 
which is also reproducable on x86. The attached stress-test-case 
GCTest.java will lock up with ~100% reproducability with 
THREAD_LOCAL_ALLOC enabled. It runs fine without THREAD_LOCAL_ALLOC.

What I am seeing in the debugger is most threads waiting in 
GC_suspend_handler, but one thread segfaulting in GC_mark_read. 
libjava's segv handler gets called and the collector is re-entered 
during the stack trace, causing the freeze.

Here's an example:

(gdb) thread 13
[Switching to thread 13 (Thread 11276 (LWP 25862))]#0  0x40632b85 in 
__sigsuspend (
    set=0x41d810d4) at ../sysdeps/unix/sysv/linux/sigsuspend.c:45
45      in ../sysdeps/unix/sysv/linux/sigsuspend.c
(gdb) bt
#0  0x40632b85 in __sigsuspend (set=0x41d810d4)
    at ../sysdeps/unix/sysv/linux/sigsuspend.c:45
#1  0x405f41c9 in __pthread_wait_for_restart_signal (self=0x41d81be0) at 
pthread.c:969
#2  0x405f5f09 in __pthread_alt_lock (lock=0x40533f88, self=0x0) at 
restart.h:34
#3  0x405f2d16 in __pthread_mutex_lock (mutex=0x40533f78) at mutex.c:120
#4  0x403ed4c7 in GC_lock () at ../../../boehm-gc/linux_threads.c:1603
#5  0x403edcfd in GC_malloc_atomic (lb=88) at ../../../boehm-gc/malloc.c:256
#6  0x403ebf47 in GC_local_malloc_atomic (bytes=88)
    at ../../../boehm-gc/linux_threads.c:367
#7  0x40223913 in _Jv_NewPrimArray (eltype=0x8091f50, count=80) at 
include/java-gc.h:53
#8  0x402583c6 in java::lang::Throwable::fillInStackTrace() (this=0x8092ff0)
    at ../../../libjava/gcj/array.h:91
#9  0x40222e32 in _Jv_ThrowSignal (throwable=0x50) at 
../../../libjava/prims.cc:111
#10 0x40222e66 in catch_segv(int) () at ../../../libjava/prims.cc:121
#11 <signal handler called>
#12 0x403efb8e in GC_mark_from (mark_stack_top=0x40599d74, 
mark_stack=0x41d81944,
    mark_stack_limit=0x403e62ac) at ../../../boehm-gc/mark.c:654
#13 0x403ef423 in GC_mark_some (
    cold_gc_frame=0x41d81908 
"¨\020\005\b£ö>@t\235Y@D\031ØA¬b>@x\\>@ì\030¸Aì\030¸At\235Y@ì") at 
../../../boehm-gc/mark.c:357
#14 0x403e660f in GC_stopped_mark (stop_func=0x403e5c78 
<GC_never_stop_func>)
    at ../../../boehm-gc/alloc.c:489
#15 0x403e62ac in GC_try_to_collect_inner (stop_func=0x403e5c78 
<GC_never_stop_func>)
    at ../../../boehm-gc/alloc.c:350
#16 0x403e6be3 in GC_try_to_collect (stop_func=0x403e5c78 
<GC_never_stop_func>)
    at ../../../boehm-gc/alloc.c:735
#17 0x403e6c39 in GC_gcollect () at ../../../boehm-gc/alloc.c:746
#18 0x403e38b9 in _Jv_RunGC() () at ../../../libjava/boehm.cc:401
#19 0x40253d59 in java::lang::Runtime::gc() (this=0x8076fa0)
    at ../../../libjava/java/lang/natRuntime.cc:118
#20 0x40272e9f in java.lang.System.gc() () at 
../../../libjava/java/lang/System.java:129
#21 0x08049651 in GCTest.gc() (this=0x40599d74) at GCTest.java:141
#22 0x080498ec in GCTest.testObjArray() (this=0x8076f30) at GCTest.java:187
#23 0x0804939a in GCTest.run() (this=0x8076f30) at GCTest.java:104
#24 0x40273673 in java.lang.Thread.run() (this=0x40599d74)
    at ../../../libjava/java/lang/Thread.java:132
#25 0x40257edc in _Jv_ThreadRun(java::lang::Thread*) (thread=0x8076f30)
    at ../../../libjava/java/lang/natThread.cc:285
#26 0x403e43a0 in really_start (x=0x8076f30) at 
../../../libjava/posix-threads.cc:375
#27 0x403ed1ea in GC_start_routine (arg=0x807bfe0)
    at ../../../boehm-gc/linux_threads.c:1369
#28 0x405f1c6f in pthread_start_thread (arg=0x41d81be0) at manager.c:284

/*
 * GCTest.java
 *
 * Test that spawns a lot of threads, have each thread allocate various 
 * objects.  Then the gc is invoked, and afterwards the objects are checked
 * to make sure they didn't get freed or munged.  This test helped discover
 * two race conditions in the garbage collector.
 *
 * Courtesy Pat Tullmann (tullmann@cs.utah.edu)
 */
public class GCTest 
	implements Runnable
{
	class GCTest_Object
	{
		public GCTest_Object(int id_, GCTest_Object next_, String name_)
		{
			id = id_;
			next = next_;
			name = name_;
		}

		public int id;
		public GCTest_Object next;
		public String name;

		public void finalize()
		{
			id = -1;
			next = null;
			name = null;
		}
	}

	private static int ct_ = 113;
	private static boolean exitOnFailure_ = false;

	private int id_;

	public GCTest(int id)
	{
		id_ = id;
		
		Thread th = new Thread(this);
		th.start();
	}
	

	public static void main(String[] args)
	{
		int i;
		int thCt;

		// when run as part of testsuite, set some defaults
		thCt = 45;
		ct_ = 60;

		if (args.length < 2)
		{
			// in interactive use make this true
			if (false) {
				System.out.println("Usage: GCTest " 
				    + "<thread count> <block size (count)>");
				System.exit(1);
			} 
		} else {

			thCt = Integer.parseInt(args[0]);
			ct_ = Integer.parseInt(args[1]);

		}
		
		for (i = 0; i < thCt; i++)
			new GCTest(i);
	}

	public void run()
	{
		// Test various stack references
		try
		{
			testObj();
			// out("obj Success");
		}
		catch (Throwable t)
		{
			t.printStackTrace();
			failure("testObj: Caught exception: " + t.getMessage());
		}

		try
		{
			testPrimArray();
			// out("primarray Success");
		}
		catch (Throwable t)
		{
			t.printStackTrace();
			failure("testPrimArray: Caught exception: " + t.getMessage());
		}

		try
		{
			testObjArray();
			// out("objarray Success");
		}
		catch (Throwable t)
		{
			t.printStackTrace();
			failure("testObjArray: Caught exception: " + t.getMessage());
		}

		try
		{
			testArrayOfArray();
			// out("arrayofarray Success");
		}
		catch (Throwable t)
		{
			t.printStackTrace();
			failure("testArrayOfArray: Caught exception: " + t.getMessage());
		}

		try
		{
			testObjChain();
			// out("objChain Success");
		}
		catch (Throwable t)
		{
			t.printStackTrace();
			failure("testObjChain: Caught exception: " + t.getMessage());
		}
		out ("Success");
	}
	
	public void gc() 
	{
	    if (true) {
		// out("invoking gc");
		System.gc();

		// Sleep to see if the finalizer gets invoked..
		try
		{
			Thread.sleep(1);
		} 
		catch (Exception e)
		{
			out("sleep failure");
			System.exit(13);
		}
	    }
	}
	
	public void testObj()
	{
		Integer i = new Integer(42);
		gc();
		if (i.intValue() != 42)
			failure("testObj");
	}
	
	public void testPrimArray()
	{
		int[] intArray = new int[ct_];
		int i;
		
		for (i = 0; i < ct_; i++)
			intArray[i] = i;
		
		gc();
		
		for (i = 0; i < ct_; i++)
			if (intArray[i] != i)
				failure("testPrimArray: wanted " +i+ "; got " +intArray[i]+ ".");
	}
	
	public void testObjArray()
	{
		String[] strs = new String[ct_];
		int i;
		
		for (i = 0; i < ct_; i++)
			strs[i] = new String(Integer.toString(i));
		
		gc();
		
		for (i = 0; i < ct_; i++)
		{
			String cmp = new String(Integer.toString(i));
			if (!strs[i].equals(cmp))
				failure("testObjArray: wanted " +cmp+ "; got " +strs[i]+ ".");
		}
	}
			
	public void testArrayOfArray()
	{
		int[][] intArray = new int[ct_][ct_];
		int[][] intArray2 = new int[ct_][];
		int i, j;

		// test 1
		for (i = 0; i < ct_; i++)
			for (j = 0; j < ct_; j++)
				intArray[i][j] = id_;
		
		gc();
		
		for (j = 0; j < ct_; j++)
			for (i = 0; i < ct_; i++)
				if (intArray[i][j] != id_)
					failure("testArrayOfArray(1): " +intArray+ "[" +i+ "][" +j+ "].  Got " +intArray[i][j]+ "; expected " +id_+ ".");

		
		gc();

		// test 2

		intArray = new int[ct_][];
		for (i = 0; i < ct_; i++)
		{
			intArray[i] = intArray2[i] = new int[ct_];
			// out(intArray[i].toString());
			for (j = 0; j < ct_; j++)
				intArray[i][j] = id_;
		}
		
		gc();
		
		for (j = 0; j < ct_; j++) {
			if (intArray[j] != intArray2[j])
				failure("testArrayOfArray(3): " +intArray+ "[" +j+ "].  Got " +intArray[j]+ "; expected " +intArray2[j]+ ".");
			for (i = 0; i < ct_; i++)
				if (intArray[i][j] != id_)
					failure("testArrayOfArray(2): " +intArray+ "[" +i+ "][" +j+ "].  Got " +intArray[i][j]+ "; expected " +id_+ ".");
		}
	}

	public void testObjChain()
	{
		GCTest_Object head, next;
		int i;
		
		head = new GCTest_Object(0, null, "0");
		next = head;
		
		for (i = 1; i < 100; i++)
		{
			next.next = new GCTest_Object(i, null, Integer.toString(i));
			next = next.next;
		}

		gc();

		next = head;
		for (i = 0; i < 99; i++)
		{
			if ((next.id != i)
			    || (next.next == null)
			    || (!next.name.equals(Integer.toString(i))))
				failure("testObjChain at " +i+ "(0x" +next.hashCode()+ "):"
					+ " id is " +next.id+ " (should be " +i+ ");" 
					+ " name is " +next.name+ " (should be '" +i+ "').");
			next = next.next;
		}
		
		if ((next.id != 99)
		    || (next.next != null)
		    || (!next.name.equals("99")))
			failure("testObjChain at 99");
	}

	public void failure(String msg)
	{
		out("Failure: " +msg);

		if (exitOnFailure_)
			System.exit(11);
	}

	public void out(String msg)
	{
	    synchronized (GCTest.class) {
		System.out.println("[" +id_+ "]:  " +msg);
	    }
	}
}

// Sort output
/* Expected Output:
[0]:  Success
[10]:  Success
[11]:  Success
[12]:  Success
[13]:  Success
[14]:  Success
[15]:  Success
[16]:  Success
[17]:  Success
[18]:  Success
[19]:  Success
[1]:  Success
[20]:  Success
[21]:  Success
[22]:  Success
[23]:  Success
[24]:  Success
[25]:  Success
[26]:  Success
[27]:  Success
[28]:  Success
[29]:  Success
[2]:  Success
[30]:  Success
[31]:  Success
[32]:  Success
[33]:  Success
[34]:  Success
[35]:  Success
[36]:  Success
[37]:  Success
[38]:  Success
[39]:  Success
[3]:  Success
[40]:  Success
[41]:  Success
[42]:  Success
[43]:  Success
[44]:  Success
[4]:  Success
[5]:  Success
[6]:  Success
[7]:  Success
[8]:  Success
[9]:  Success
*/