Reimplement Windows Monitors.

Reimplement Windows Monitors.

Now using an event object per thread which is linked into a list
of waiters for the monitor.

Notify takes the first element of the list and notifies (FIFO order).

Notify all extracts the entire list and notifies each of them. This
avoids the issues with fairness and correctness of the previous version.

The MonitorWaitData object holding the event and a pointer to the
next waiter is stored in thread local storage and lazily initialized.

R=sgjesse@google.com,asiva@google.com
BUG=1614
TEST=

Committed: https://code.google.com/p/dart/source/detail?r=4537

[Mads Ager (google), 2012-02-21 13:14:31]

Please wait with reviewing this. I'm pretty sure this implementation is
incorrect if timeouts occur.

[Mads Ager (google), 2012-02-21 15:34:15]

OK, ready for review.

[Søren Gjesse, 2012-02-21 16:00:45]

LGTM!

https://chromiumcodereview.appspot.com/9424050/diff/5001/runtime/platform/thr...
File runtime/platform/thread_win.cc (right):

https://chromiumcodereview.appspot.com/9424050/diff/5001/runtime/platform/thr...
runtime/platform/thread_win.cc:172: if (waiters_tail_ == NULL) {
ASSERT(waiters_head_ == NULL)

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

NotifyAll is quadratic.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win.cc
File runtime/platform/thread_win.cc (right):

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.cc:339: //
When a thread waits on a monitor and the wait times out, the thread must
reacquire the monitor internal lock to unlink itself from the wait queue.  By
following this protocol, the link structure should not change if a thread wakes
up during a notify.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.cc:347: for (intptr_t i = 0; waiters[i] != NULL;
i++) {
As noted in the header, this should be written as an appending of the wait queue
onto the entry queue.  Waking up each of the threads can become very, very
expensive.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win.h
File runtime/platform/thread_win.h (right):

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.h:60: HANDLE event_;
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.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.h:94: // order). NotifyAll, signals all the elements
of the list.
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:50]

Thanks for the comments!

I don't see how NotifyAll is quadratic. It runs through the list of waiters and
signal all of them. The thing that can be quadratic is if the waiters all
timeout in the reverse order of when they started waiting.

I would like to use the current implementation as the next (correct) stepping
stone towards something even better.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win.cc
File runtime/platform/thread_win.cc (right):

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.cc:172: if (waiters_tail_ == NULL) {
On 2012/02/21 16:00:48, Søren Gjesse wrote:
> ASSERT(waiters_head_ == NULL)

Done.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.cc:339: //
On 2012/02/21 18:49:36, cshapiro wrote:
> When a thread waits on a monitor and the wait times out, the thread must
> reacquire the monitor internal lock to unlink itself from the wait queue.  By
> following this protocol, the link structure should not change if a thread
wakes
> up during a notify.

I don't understand. The notification loop over the structure is done without
having any lock on the list. Therefore, the wait can time out and change the
link structure. Therefore, we have to not use that link structure as it could
lead to notification being lost or the wrong waiters being signaled.

The alternative is to keep the internal lock during the loop below at which
point you are right that a waiting thread that times out cannot continue and
change the link structure before moving on. That would simplify at the cost of
holding the lock during the loop. I'll do that so we avoid the allocation and
copying out here.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.cc:347: for (intptr_t i = 0; waiters[i] != NULL;
i++) {
On 2012/02/21 18:49:36, cshapiro wrote:
> As noted in the header, this should be written as an appending of the wait
queue
> onto the entry queue.  Waking up each of the threads can become very, very
> expensive.

This could be expensive, I agree. However, it is much better than what we had
before. There are multiple things we can do here. We can follow the design that
you described, we can attempt to load the Vista ConditionVariables so this is
only in play for pre-Vista users. All of that I would like to do in a separate
changelist. I agree that this solution is not ideal and I will keep the bug
open. However, I don't think we need to spent more time on this at this point.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win.h
File runtime/platform/thread_win.h (right):

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.h:60: HANDLE event_;
On 2012/02/21 18:49:36, cshapiro wrote:
> 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.

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.

http://codereview.chromium.org/9424050/diff/5001/runtime/platform/thread_win....
runtime/platform/thread_win.h:94: // order). NotifyAll, signals all the elements
of the list.
On 2012/02/21 18:49:36, cshapiro wrote:
> 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.

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