From b3fcee8ffd162b32e3a4d03ba7045e7dee2798b1 Mon Sep 17 00:00:00 2001
From: Stefan Ring <stefan@complang.tuwien.ac.at>
Date: Thu, 11 Sep 2008 15:23:12 +0200
Subject: [PATCH] * src/threads/lock.cpp (sable_flc_waiting): Slight
 optimization, avoiding pathological behavior. *
 src/threads/posix/thread-posix.hpp: Added field required for this. *
 tests/threads/sableContention.java: Illustrative testcase. *
 tests/threads/sableContention.patch: Patch for printing the FLC list length.

---
 src/threads/lock.cpp                |  6 ++
 src/threads/posix/thread-posix.hpp  |  1 +
 tests/threads/sableContention.java  | 91 +++++++++++++++++++++++++++++
 tests/threads/sableContention.patch | 29 +++++++++
 4 files changed, 127 insertions(+)
 create mode 100644 tests/threads/sableContention.java
 create mode 100644 tests/threads/sableContention.patch

diff --git a/src/threads/lock.cpp b/src/threads/lock.cpp
index 06ba2b341..5bcee690d 100644
--- a/src/threads/lock.cpp
+++ b/src/threads/lock.cpp
@@ -705,10 +705,14 @@ static void sable_flc_waiting(Lockword *lockword, threadobject *t, java_handle_t
 	/* Lockword is still the way it was seen before */
 	if (lockword->is_thin_lock() && (lockword->get_thin_lock_thread_index() == index))
 	{
+		threadobject *f;
 		/* Add tuple (t, o) to the other thread's FLC list */
 		t->flc_object = o;
 		t->flc_next = t_other->flc_list;
 		t_other->flc_list = t;
+		if (t->flc_next == 0)
+			t_other->flc_tail = t;
+		f = t_other->flc_tail;
 
 		for (;;)
 		{
@@ -718,6 +722,8 @@ static void sable_flc_waiting(Lockword *lockword, threadobject *t, java_handle_t
 			// us of unlocking.
 			t->flc_cond->wait(t_other->flc_lock);
 
+			if (t_other->flc_tail != f)
+				break;
 			/* Traverse FLC list looking if we're still there */
 			current = t_other->flc_list;
 			while (current && current != t)
diff --git a/src/threads/posix/thread-posix.hpp b/src/threads/posix/thread-posix.hpp
index baf997981..424ab8497 100644
--- a/src/threads/posix/thread-posix.hpp
+++ b/src/threads/posix/thread-posix.hpp
@@ -81,6 +81,7 @@ struct threadobject {
 	/* for the sable tasuki lock extension */
 	bool                  flc_bit;
 	struct threadobject  *flc_list;     /* FLC list head for this thread      */
+	struct threadobject  *flc_tail;     /* tail pointer for FLC list          */
 	struct threadobject  *flc_next;     /* next pointer for FLC list          */
 	java_handle_t        *flc_object;
 	Mutex*                flc_lock;     /* controlling access to these fields */
diff --git a/tests/threads/sableContention.java b/tests/threads/sableContention.java
new file mode 100644
index 000000000..184dc3132
--- /dev/null
+++ b/tests/threads/sableContention.java
@@ -0,0 +1,91 @@
+// This pathological test tries to grow a FLC list as long as possible before
+// the threads from the previous FLC list have resumed running. Every one on
+// the old list then has to scan the entire new list.
+
+// The CACAO patch in file sableContention.patch can be used to examine the
+// maximum length. With 500 threads on a quad-core system, I managed to get to
+// about 120.
+
+class sableContention {
+	public Object a[] = null;
+	public tt ts[] = null;
+	final int NUM = 500;
+
+	class tt extends Thread {
+		sableContention y;
+		int x;
+		tt(sableContention y, int x) {
+			this.y = y;
+			this.x = x;
+		}
+		public void run() {
+			int i = 1;
+			synchronized(y.a[x]) {
+				if (x==0) {
+					for (; i<NUM*3/4; i++)
+						y.ts[i].start();
+					y.a[x].notify();
+				}
+			}
+			if (x==0)
+				for (; i<NUM; i++)
+					y.ts[i].start();
+			for (int j=0; j<NUM/10; j++)
+				synchronized(y.a[(x+j)%(NUM-1)+1]) {
+				}
+		}
+	}
+
+	private void l(int f) {
+		try {
+			synchronized(a[NUM-1-f]) {
+				if (f > 0) {
+					l(f-1);
+					if (f<10)
+						Thread.sleep(0, f*100 * 1000);
+				}
+				else {
+					ts = new tt[NUM];
+					for (int i=0; i<NUM; i++)
+						ts[i] = new tt(this, i);
+					ts[0].start();
+					a[0].wait();
+				}
+			}
+		} catch (InterruptedException e) {
+		}
+	}
+
+	private void r() {
+		for (;;) {
+			a = new Object[NUM];
+			for (int i=0; i<NUM; i++)
+				a[i] = new Object();
+			l(NUM-1);
+			for (int i=0; i<NUM; i++)
+				try {
+					ts[i].join();
+				} catch (InterruptedException e) {
+				}
+			System.out.println("running");
+		}
+	}
+
+	public static void main(String[] args) {
+		new sableContention().r();
+	}
+}
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: java
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ * vim:noexpandtab:sw=4:ts=4:
+ */
diff --git a/tests/threads/sableContention.patch b/tests/threads/sableContention.patch
new file mode 100644
index 000000000..f83a4a664
--- /dev/null
+++ b/tests/threads/sableContention.patch
@@ -0,0 +1,29 @@
+--- a/src/threads/lock.cpp	Thu Sep 11 14:52:50 2008 +0200
++++ b/src/threads/lock.cpp	Thu Sep 11 15:13:24 2008 +0200
+@@ -717,6 +717,7 @@
+ 		for (;;)
+ 		{
+ 			threadobject *current;
++			int i = 0;
+ 
+ 			// Wait until another thread sees the flc bit and notifies
+ 			// us of unlocking.
+@@ -726,8 +727,17 @@
+ 				break;
+ 			/* Traverse FLC list looking if we're still there */
+ 			current = t_other->flc_list;
+-			while (current && current != t)
++			while (current && current != t) {
++				i++;
+ 				current = current->flc_next;
++			}
++			{
++				static int umax = 0;
++				if (i>umax) {
++					printf("sable len %d\n", i);
++					umax = i;
++				}
++			}
+ 			if (!current)
+ 				/* not in list anymore, can stop waiting */
+ 				break;
-- 
2.25.1