Reimplement Windows Monitors.

runtime/platform/thread_win.h

Index: runtime/platform/thread_win.h
diff --git a/runtime/platform/thread_win.h b/runtime/platform/thread_win.h
index 02165df2fa7c2c04a0238762d055df97b6a170a9..978e73fe9140ccd3a283f2573153c2f3c0af109c 100644
--- a/runtime/platform/thread_win.h
+++ b/runtime/platform/thread_win.h
@@ -48,28 +48,53 @@ class MutexData {
 };
 
 
+class MonitorWaitData {
+ private:
+  explicit MonitorWaitData(HANDLE event) : event_(event), next_(NULL) {}
+
+  // ThreadLocalKey used to fetch and store the MonitorWaitData object
+  // for a given thread.
+  static ThreadLocalKey monitor_wait_data_key_;
+
+  // Auto-reset event used for waiting.
+  HANDLE event_;

[cshapiro, 2012/02/21 18:49:36]

This event handle should be stored in Thread thereby eliminating the need for
MonitorWaitData.  A thread can only be waiting on a single monitor at a time. 
There is no need to allocate and reallocate these objects separately from each
thread.

[Mads Ager (google), 2012/02/22 12:32:51]

I don't understand. I allocate exactly one event per thread on demand and stuff
it in thread-local storage. So there is no reallocation. Also, we do not have a
Thread object at this point and I don't think this requirement on Windows alone
is enough to warant one.

+  // Link to next element in the singly-linked list of waiters.
+  MonitorWaitData* next_;
+
+  friend class Monitor;
+  friend class MonitorData;
+
+  DISALLOW_COPY_AND_ASSIGN(MonitorWaitData);
+};
+
+
 class MonitorData {
  private:
   MonitorData() {}
   ~MonitorData() {}
 
+  // Helper methods to manipulate the list of waiters for this
+  // monitor.
+  void AddWaiter(MonitorWaitData* wait_data);
+  void RemoveWaiter(MonitorWaitData* wait_data);
+  MonitorWaitData* RemoveFirstWaiter();
+  MonitorWaitData** RemoveAllWaiters();
+  MonitorWaitData* GetMonitorWaitDataForThread();
+
+  // The external critical section for the monitor.
   CRITICAL_SECTION cs_;
 
   // Condition variables are only available since Windows Vista. To
   // support at least Windows XP, we implement our own condition
   // variables using SetEvent on Event objects.
 
-  // The notify_event_ is an auto-reset event which means that
-  // SetEvent only wakes up one waiter.
-  HANDLE notify_event_;
-
-  // The notify_all_event_ is a manual-reset event which means that
-  // SetEvent wakes up all waiters.
-  HANDLE notify_all_event_;
-
-  // Counter with protection used to determine the right time to reset
-  // the notify_all_event_.
+  // Singly-linked list of event objects, one for each thread waiting
+  // on this monitor. New waiters are added at the end of the list.
+  // Notify signals the first element of the list (FIFO
+  // order). NotifyAll, signals all the elements of the list.

[cshapiro, 2012/02/21 18:49:36]

This behavior is not performance sensitive.  NotifyAll should not signal all
threads.  This creates a "thundering herd".

A monitor one lock and two queues.

The lock protects the queues.

One queue is needed to link together threads which are waiting on a monitor. 
The other queue links together threads which are entering a monitor.

Notify should unlink the thread at the head of the wait queue and link it on to
the end of the entry queue.

NotifyAll should unlink all threads from the wait queue and link them on to the
end of the entry queue.

When a thread waits, it acquires the internal monitor lock, links itself on to
the wait queue, sets its event, releases the monitor lock, and sleeps on its
event.

When a thread enters a monitor it either acquires the monitor straight away if
it is unowned.  It the monitor is owned, it must queue itself just like a
waiting thread would.  When the thread is woken it contends for the internal
monitor lock and unlinks itself if there is no owner, otherwise it goes back to
sleep.

Modeling queues this way has the added bonus of being easily profiled.

[Mads Ager (google), 2012/02/22 12:32:51]

This design does sound nice. I would like to go with the current version first.
It is way better than what we had. I will update the bug with this information
and we can take another round on this when time permits (or the current
implementation becomes a problem).

   CRITICAL_SECTION waiters_cs_;
+  MonitorWaitData* waiters_head_;
+  MonitorWaitData* waiters_tail_;
   intptr_t waiters_;
 
   friend class Monitor;