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

diff --git a/src/threads/lock.cpp b/src/threads/lock.cpp
index 06ba2b341646fad5aeab0821a82f74c7f0ed086d..5bcee690db131362a170ab9dbd3d3132e8afce3b 100644 (file)
--- 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 baf99798118e543495505e8b5df4ae3d906c4dd2..424ab84973ae45e08ee0b980b1cba389fbdf02d9 100644 (file)
--- 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 (file)
index 0000000..184dc31
--- /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 (file)
index 0000000..f83a4a6
--- /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;