Ignore:
Timestamp:
Jan 22, 2009, 12:32:45 AM (16 years ago)
Author:
[email protected]
Message:

2009-01-22 Dmitry Titov <​[email protected]>

Reviewed by Alexey Proskuryakov.

​https://bugs.webkit.org/show_bug.cgi?id=23373

Implement ThreadCondition::timedWait().
Since we borrow the code for condition variables from other sources,
I did the same for timedWait(). See comments in ThreadingWin.cpp for
rationale and more info.

  • wtf/CONTRIBUTORS.pthreads-win32: Added. A list of Pthreads-win32 contributors mentioned in their license. The license itself is included into wtf/ThreadingWin32.cpp.
  • wtf/Threading.h:
  • wtf/ThreadingWin.cpp: Additional info and Pthreads-win32 license at the beginning. (WTF::PlatformCondition::timedWait): new method, derived from Pthreads-win32. (WTF::PlatformCondition::signal): same (WTF::ThreadCondition::ThreadCondition): (WTF::ThreadCondition::~ThreadCondition): (WTF::ThreadCondition::wait): this now calls PlatformCondition::timedWait. (WTF::ThreadCondition::timedWait): same (WTF::ThreadCondition::signal): this now calls PlatformCondition::signal. (WTF::ThreadCondition::broadcast): same
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/wtf/ThreadingWin.cpp

    r39908 r40122  
    11/*
    22 * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
     3 * Copyright (C) 2009 Google Inc. All rights reserved.
    34 *
    45 * Redistribution and use in source and binary forms, with or without
    … …  
    2526 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    2627 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27  *
    28  * =============================================================================
    29  * Note:  The implementation of condition variables under the Windows
    30  * plaform was based on that of the excellent BOOST C++ library.  It
    31  * has been rewritten to fit in with the WebKit architecture and to
    32  * use its coding conventions.
    33  * =============================================================================
    34  *
    35  * The Boost license is virtually identical to the Apple variation at the
    36  * top of this file, but is included here for completeness:
    37  *
    38  * Boost Software License - Version 1.0 - August 17th, 2003
    39  *
    40  * Permission is hereby granted, free of charge, to any person or organization
    41  * obtaining a copy of the software and accompanying documentation covered by
    42  * this license (the "Software") to use, reproduce, display, distribute,
    43  * execute, and transmit the Software, and to prepare derivative works of the
    44  * Software, and to permit third-parties to whom the Software is furnished to
    45  * do so, all subject to the following:
    46  *
    47  * The copyright notices in the Software and this entire statement, including
    48  * the above license grant, this restriction and the following disclaimer,
    49  * must be included in all copies of the Software, in whole or in part, and
    50  * all derivative works of the Software, unless such copies or derivative
    51  * works are solely in the form of machine-executable object code generated by
    52  * a source language processor.
    53  *
    54  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    55  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    56  * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
    57  * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
    58  * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
    59  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    60  * DEALINGS IN THE SOFTWARE.
     28 */
     29
     30/*
     31 * There are numerous academic and practical works on how to implement pthread_cond_wait/pthread_cond_signal/pthread_cond_broadcast
     32 * functions on Win32. Here is one example: http://www.cs.wustl.edu/~schmidt/win32-cv-1.html which is widely credited as a 'starting point'
     33 * of modern attempts. There are several more or less proven implementations, one in Boost C++ library (http://www.boost.org) and another
     34 * in pthreads-win32 (http://sourceware.org/pthreads-win32/).
     35 *
     36 * The number of articles and discussions is the evidence of significant difficulties in implementing these primitives correctly.
     37 * The brief search of revisions, ChangeLog entries, discussions in comp.programming.threads and other places clearly documents
     38 * numerous pitfalls and performance problems the authors had to overcome to arrive to the suitable implementations.
     39 * Optimally, WebKit would use one of those supported/tested libraries directly. To roll out our own implementation is impractical,
     40 * if even for the lack of sufficient testing. However, a faithful reproduction of the code from one of the popular supported
     41 * libraries seems to be a good compromise.
     42 *
     43 * The early Boost implementation (http://www.boxbackup.org/trac/browser/box/nick/win/lib/win32/boost_1_32_0/libs/thread/src/condition.cpp?rev=30)
     44 * is identical to pthreads-win32 (http://sourceware.org/cgi-bin/cvsweb.cgi/pthreads/pthread_cond_wait.c?rev=1.10&content-type=text/x-cvsweb-markup&cvsroot=pthreads-win32).
     45 * Current Boost uses yet another (although seemingly equivalent) algorithm which came from their 'thread rewrite' effort.
     46 *
     47 * This file includes timedWait/signal/broadcast implementations translated to WebKit coding style from the latest algorithm by
     48 * Alexander Terekhov and Louis Thomas, as captured here: http://sourceware.org/cgi-bin/cvsweb.cgi/pthreads/pthread_cond_wait.c?rev=1.10&content-type=text/x-cvsweb-markup&cvsroot=pthreads-win32
     49 * It replaces the implementation of their previous algorithm, also documented in the same source above.
     50 * The naming and comments are left very close to original to enable easy cross-check.
     51 *
     52 * The corresponding Pthreads-win32 License is included below, and CONTRIBUTORS file which it refers to is added to
     53 * source directory (as CONTRIBUTORS.pthreads-win32).
     54 */
     55
     56/*
     57 *      Pthreads-win32 - POSIX Threads Library for Win32
     58 *      Copyright(C) 1998 John E. Bossom
     59 *      Copyright(C) 1999,2005 Pthreads-win32 contributors
     60 *
     61 *      Contact Email: [email protected]
     62 *
     63 *      The current list of contributors is contained
     64 *      in the file CONTRIBUTORS included with the source
     65 *      code distribution. The list can also be seen at the
     66 *      following World Wide Web location:
     67 *      http://sources.redhat.com/pthreads-win32/contributors.html
     68 *
     69 *      This library is free software; you can redistribute it and/or
     70 *      modify it under the terms of the GNU Lesser General Public
     71 *      License as published by the Free Software Foundation; either
     72 *      version 2 of the License, or (at your option) any later version.
     73 *
     74 *      This library is distributed in the hope that it will be useful,
     75 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
     76 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     77 *      Lesser General Public License for more details.
     78 *
     79 *      You should have received a copy of the GNU Lesser General Public
     80 *      License along with this library in the file COPYING.LIB;
     81 *      if not, write to the Free Software Foundation, Inc.,
     82 *      59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
    6183 */
    6284
    … …  
    7092#include <process.h>
    7193#include <windows.h>
     94#include <wtf/CurrentTime.h>
    7295#include <wtf/HashMap.h>
    7396#include <wtf/MathExtras.h>
    … …  
    215238        LOG_ERROR("ThreadIdentifier %u did not correspond to an active thread when trying to quit", threadID);
    216239 
    217     DWORD joinResult = ::WaitForSingleObject(threadHandle, INFINITE);
     240    DWORD joinResult = WaitForSingleObject(threadHandle, INFINITE);
    218241    if (joinResult == WAIT_FAILED)
    219242        LOG_ERROR("ThreadIdentifier %u was found to be deadlocked trying to quit", threadID);
    220243
    221     ::CloseHandle(threadHandle);
     244    CloseHandle(threadHandle);
    222245    clearThreadHandleForIdentifier(threadID);
    223246
    … …  
    231254    HANDLE threadHandle = threadHandleForIdentifier(threadID);
    232255    if (threadHandle)
    233         ::CloseHandle(threadHandle);
     256        CloseHandle(threadHandle);
    234257    clearThreadHandleForIdentifier(threadID);
    235258}
    … …  
    237260ThreadIdentifier currentThread()
    238261{
    239     return static_cast<ThreadIdentifier>(::GetCurrentThreadId());
     262    return static_cast<ThreadIdentifier>(GetCurrentThreadId());
    240263}
    241264
    … …  
    248271{
    249272    m_mutex.m_recursionCount = 0;
    250     ::InitializeCriticalSection(&m_mutex.m_internalMutex);
     273    InitializeCriticalSection(&m_mutex.m_internalMutex);
    251274}
    252275
    253276Mutex::~Mutex()
    254277{
    255     ::DeleteCriticalSection(&m_mutex.m_internalMutex);
     278    DeleteCriticalSection(&m_mutex.m_internalMutex);
    256279}
    257280
    258281void Mutex::lock()
    259282{
    260     ::EnterCriticalSection(&m_mutex.m_internalMutex);
     283    EnterCriticalSection(&m_mutex.m_internalMutex);
    261284    ++m_mutex.m_recursionCount;
    262285}
    … …  
    270293    // tests in WebKit that check to see if the current thread already
    271294    // owned this mutex (see e.g., IconDatabase::getOrCreateIconRecord)
    272     DWORD result = ::TryEnterCriticalSection(&m_mutex.m_internalMutex);
     295    DWORD result = TryEnterCriticalSection(&m_mutex.m_internalMutex);
    273296   
    274297    if (result != 0) {       // We got the lock
    … …  
    277300        // pthread_mutex_trylock:
    278301        if (m_mutex.m_recursionCount > 0) {
    279             ::LeaveCriticalSection(&m_mutex.m_internalMutex);
     302            LeaveCriticalSection(&m_mutex.m_internalMutex);
    280303            return false;
    281304        }
    … …  
    291314{
    292315    --m_mutex.m_recursionCount;
    293     ::LeaveCriticalSection(&m_mutex.m_internalMutex);
    294 }
    295 
    296 static const long MaxSemaphoreCount = static_cast<long>(~0UL >> 1);
    297 
    298 ThreadCondition::ThreadCondition()
    299 {
    300     m_condition.m_timedOut = 0;
    301     m_condition.m_blocked = 0;
    302     m_condition.m_waitingForRemoval = 0;
    303     m_condition.m_gate = ::CreateSemaphore(0, 1, 1, 0);
    304     m_condition.m_queue = ::CreateSemaphore(0, 0, MaxSemaphoreCount, 0);
    305     m_condition.m_mutex = ::CreateMutex(0, 0, 0);
    306 
    307     if (!m_condition.m_gate || !m_condition.m_queue || !m_condition.m_mutex) {
    308         if (m_condition.m_gate)
    309             ::CloseHandle(m_condition.m_gate);
    310         if (m_condition.m_queue)
    311             ::CloseHandle(m_condition.m_queue);
    312         if (m_condition.m_mutex)
    313             ::CloseHandle(m_condition.m_mutex);
    314     }
    315 }
    316 
    317 ThreadCondition::~ThreadCondition()
    318 {
    319     ::CloseHandle(m_condition.m_gate);
    320     ::CloseHandle(m_condition.m_queue);
    321     ::CloseHandle(m_condition.m_mutex);
    322 }
    323    
    324 void ThreadCondition::wait(Mutex& mutex)
    325 {
    326     PlatformMutex& cs = mutex.impl();
    327 
     316    LeaveCriticalSection(&m_mutex.m_internalMutex);
     317}
     318
     319bool PlatformCondition::timedWait(PlatformMutex& mutex, DWORD durationMilliseconds)
     320{
    328321    // Enter the wait state.
    329     DWORD res = ::WaitForSingleObject(m_condition.m_gate, INFINITE);
     322    DWORD res = WaitForSingleObject(m_blockLock, INFINITE);
    330323    ASSERT(res == WAIT_OBJECT_0);
    331     ++m_condition.m_blocked;
    332     res = ::ReleaseSemaphore(m_condition.m_gate, 1, 0);
     324    ++m_waitersBlocked;
     325    res = ReleaseSemaphore(m_blockLock, 1, 0);
    333326    ASSERT(res);
    334327
    335     ::LeaveCriticalSection(&cs.m_internalMutex);
    336 
    337     res = ::WaitForSingleObject(m_condition.m_queue, INFINITE);
     328    LeaveCriticalSection(&mutex.m_internalMutex);
     329
     330    // Main wait - use timeout.
     331    bool timedOut = (WaitForSingleObject(m_blockQueue, durationMilliseconds) == WAIT_TIMEOUT);
     332
     333    res = WaitForSingleObject(m_unblockLock, INFINITE);
    338334    ASSERT(res == WAIT_OBJECT_0);
    339335
    340     res = ::WaitForSingleObject(m_condition.m_mutex, INFINITE);
    341     ASSERT(res == WAIT_OBJECT_0);
    342     size_t wasWaiting = m_condition.m_waitingForRemoval;
    343     size_t wasTimedOut = m_condition.m_timedOut;
    344     if (wasWaiting != 0) {
    345         if (--m_condition.m_waitingForRemoval == 0) {
    346             if (m_condition.m_blocked != 0) {
    347                 res = ::ReleaseSemaphore(m_condition.m_gate, 1, 0);  // open m_gate
    348                 ASSERT(res);
    349                 wasWaiting = 0;
    350             }
    351             else if (m_condition.m_timedOut != 0)
    352                 m_condition.m_timedOut = 0;
    353         }
    354     } else if (++m_condition.m_timedOut == ((std::numeric_limits<unsigned>::max)() / 2)) {
    355         // timeout occured, normalize the m_condition.m_timedOut count
     336    int signalsLeft = m_waitersToUnblock;
     337
     338    if (m_waitersToUnblock)
     339        --m_waitersToUnblock;
     340    else if (++m_waitersGone == (INT_MAX / 2)) { // timeout/canceled or spurious semaphore
     341        // timeout or spurious wakeup occured, normalize the m_waitersGone count
    356342        // this may occur if many calls to wait with a timeout are made and
    357343        // no call to notify_* is made
    358         res = ::WaitForSingleObject(m_condition.m_gate, INFINITE);
     344        res = WaitForSingleObject(m_blockLock, INFINITE);
    359345        ASSERT(res == WAIT_OBJECT_0);
    360         m_condition.m_blocked -= m_condition.m_timedOut;
    361         res = ::ReleaseSemaphore(m_condition.m_gate, 1, 0);
     346        m_waitersBlocked -= m_waitersGone;
     347        res = ReleaseSemaphore(m_blockLock, 1, 0);
    362348        ASSERT(res);
    363         m_condition.m_timedOut = 0;
    364     }
    365     res = ::ReleaseMutex(m_condition.m_mutex);
     349        m_waitersGone = 0;
     350    }
     351
     352    res = ReleaseMutex(m_unblockLock);
    366353    ASSERT(res);
    367354
    368     if (wasWaiting == 1) {
    369         for (/**/ ; wasTimedOut; --wasTimedOut) {
    370             // better now than spurious later
    371             res = ::WaitForSingleObject(m_condition.m_queue, INFINITE);
    372             ASSERT(res == WAIT_OBJECT_0);
    373         }
    374         res = ::ReleaseSemaphore(m_condition.m_gate, 1, 0);
     355    if (signalsLeft == 1) {
     356        res = ReleaseSemaphore(m_blockLock, 1, 0); // Open the gate.
    375357        ASSERT(res);
    376358    }
    377359
    378     ::EnterCriticalSection (&cs.m_internalMutex);
    379 }
    380 
    381 bool ThreadCondition::timedWait(Mutex& mutex, double absoluteTime)
    382 {
    383     // FIXME: Implement.
    384     ASSERT(false);
    385     return false;
    386 }
    387 
    388 void ThreadCondition::signal()
    389 {
    390     unsigned signals = 0;
    391 
    392     DWORD res = ::WaitForSingleObject(m_condition.m_mutex, INFINITE);
     360    EnterCriticalSection (&mutex.m_internalMutex);
     361
     362    return !timedOut;
     363}
     364
     365void PlatformCondition::signal(bool unblockAll)
     366{
     367    unsigned signalsToIssue = 0;
     368
     369    DWORD res = WaitForSingleObject(m_unblockLock, INFINITE);
    393370    ASSERT(res == WAIT_OBJECT_0);
    394371
    395     if (m_condition.m_waitingForRemoval != 0) { // the m_gate is already closed
    396         if (m_condition.m_blocked == 0) {
    397             res = ::ReleaseMutex(m_condition.m_mutex);
     372    if (m_waitersToUnblock) { // the gate is already closed
     373        if (!m_waitersBlocked) { // no-op
     374            res = ReleaseMutex(m_unblockLock);
    398375            ASSERT(res);
    399376            return;
    400377        }
    401378
    402         ++m_condition.m_waitingForRemoval;
    403         --m_condition.m_blocked;
    404 
    405         signals = 1;
    406     } else {
    407         res = ::WaitForSingleObject(m_condition.m_gate, INFINITE);
     379        if (unblockAll) {
     380            signalsToIssue = m_waitersBlocked;
     381            m_waitersToUnblock += m_waitersBlocked;
     382            m_waitersBlocked = 0;
     383        } else {
     384            signalsToIssue = 1;
     385            ++m_waitersToUnblock;
     386            --m_waitersBlocked;
     387        }
     388    } else if (m_waitersBlocked > m_waitersGone) {
     389        res = WaitForSingleObject(m_blockLock, INFINITE); // Close the gate.
    408390        ASSERT(res == WAIT_OBJECT_0);
    409         if (m_condition.m_blocked > m_condition.m_timedOut) {
    410             if (m_condition.m_timedOut != 0) {
    411                 m_condition.m_blocked -= m_condition.m_timedOut;
    412                 m_condition.m_timedOut = 0;
    413             }
    414             signals = m_condition.m_waitingForRemoval = 1;
    415             --m_condition.m_blocked;
     391        if (m_waitersGone != 0) {
     392            m_waitersBlocked -= m_waitersGone;
     393            m_waitersGone = 0;
     394        }
     395        if (unblockAll) {
     396            signalsToIssue = m_waitersBlocked;
     397            m_waitersToUnblock = m_waitersBlocked;
     398            m_waitersBlocked = 0;
    416399        } else {
    417             res = ::ReleaseSemaphore(m_condition.m_gate, 1, 0);
    418             ASSERT(res);
     400            signalsToIssue = 1;
     401            m_waitersToUnblock = 1;
     402            --m_waitersBlocked;
    419403        }
    420     }
    421 
    422     res =::ReleaseMutex(m_condition.m_mutex);
     404    } else { // No-op.
     405        res = ReleaseMutex(m_unblockLock);
     406        ASSERT(res);
     407        return;
     408    }
     409
     410    res = ReleaseMutex(m_unblockLock);
    423411    ASSERT(res);
    424412
    425     if (signals) {
    426         res = ::ReleaseSemaphore(m_condition.m_queue, signals, 0);
     413    if (signalsToIssue) {
     414        res = ReleaseSemaphore(m_blockQueue, signalsToIssue, 0);
    427415        ASSERT(res);
    428416    }
    429417}
    430418
     419static const long MaxSemaphoreCount = static_cast<long>(~0UL >> 1);
     420
     421ThreadCondition::ThreadCondition()
     422{
     423    m_condition.m_waitersGone = 0;
     424    m_condition.m_waitersBlocked = 0;
     425    m_condition.m_waitersToUnblock = 0;
     426    m_condition.m_blockLock = CreateSemaphore(0, 1, 1, 0);
     427    m_condition.m_blockQueue = CreateSemaphore(0, 0, MaxSemaphoreCount, 0);
     428    m_condition.m_unblockLock = CreateMutex(0, 0, 0);
     429
     430    if (!m_condition.m_blockLock || !m_condition.m_blockQueue || !m_condition.m_unblockLock) {
     431        if (m_condition.m_blockLock)
     432            CloseHandle(m_condition.m_blockLock);
     433        if (m_condition.m_blockQueue)
     434            CloseHandle(m_condition.m_blockQueue);
     435        if (m_condition.m_unblockLock)
     436            CloseHandle(m_condition.m_unblockLock);
     437    }
     438}
     439
     440ThreadCondition::~ThreadCondition()
     441{
     442    CloseHandle(m_condition.m_blockLock);
     443    CloseHandle(m_condition.m_blockQueue);
     444    CloseHandle(m_condition.m_unblockLock);
     445}
     446
     447void ThreadCondition::wait(Mutex& mutex)
     448{
     449    m_condition.timedWait(mutex.impl(), INFINITE);
     450}
     451
     452bool ThreadCondition::timedWait(Mutex& mutex, double absoluteTime)
     453{
     454    double currentTime = WTF::currentTime();
     455
     456    // Time is in the past - return immediately.
     457    if (absoluteTime < currentTime)
     458        return false;
     459
     460    double intervalMilliseconds = (absoluteTime - currentTime) * 1000.0;
     461    if (intervalMilliseconds >= INT_MAX)
     462        intervalMilliseconds = INT_MAX;
     463
     464    return m_condition.timedWait(mutex.impl(), static_cast<unsigned long>(intervalMilliseconds));
     465}
     466
     467void ThreadCondition::signal()
     468{
     469    m_condition.signal(false); // Unblock only 1 thread.
     470}
     471
    431472void ThreadCondition::broadcast()
    432473{
    433     unsigned signals = 0;
    434 
    435     DWORD res = ::WaitForSingleObject(m_condition.m_mutex, INFINITE);
    436     ASSERT(res == WAIT_OBJECT_0);
    437 
    438     if (m_condition.m_waitingForRemoval != 0) { // the m_gate is already closed
    439         if (m_condition.m_blocked == 0) {
    440             res = ::ReleaseMutex(m_condition.m_mutex);
    441             ASSERT(res);
    442             return;
    443         }
    444 
    445         m_condition.m_waitingForRemoval += (signals = m_condition.m_blocked);
    446         m_condition.m_blocked = 0;
    447     } else {
    448         res = ::WaitForSingleObject(m_condition.m_gate, INFINITE);
    449         ASSERT(res == WAIT_OBJECT_0);
    450         if (m_condition.m_blocked > m_condition.m_timedOut) {
    451             if (m_condition.m_timedOut != 0) {
    452                 m_condition.m_blocked -= m_condition.m_timedOut;
    453                 m_condition.m_timedOut = 0;
    454             }
    455             signals = m_condition.m_waitingForRemoval = m_condition.m_blocked;
    456             m_condition.m_blocked = 0;
    457         } else {
    458             res = ::ReleaseSemaphore(m_condition.m_gate, 1, 0);
    459             ASSERT(res);
    460         }
    461     }
    462 
    463     res = ::ReleaseMutex(m_condition.m_mutex);
    464     ASSERT(res);
    465 
    466     if (signals) {
    467         res = ::ReleaseSemaphore(m_condition.m_queue, signals, 0);
    468         ASSERT(res);
    469     }
     474    m_condition.signal(true); // Unblock all threads.
    470475}
    471476
Note: See TracChangeset for help on using the changeset viewer.