Home | History | Annotate | Download | only in wtf 
      1 /*
      2  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
      3  * Copyright (C) 2009 Google Inc. All rights reserved.
      4  * Copyright (C) 2009 Torch Mobile, Inc. All rights reserved.
      5  *
      6  * Redistribution and use in source and binary forms, with or without
      7  * modification, are permitted provided that the following conditions
      8  * are met:
      9  *
     10  * 1.  Redistributions of source code must retain the above copyright
     11  *     notice, this list of conditions and the following disclaimer.
     12  * 2.  Redistributions in binary form must reproduce the above copyright
     13  *     notice, this list of conditions and the following disclaimer in the
     14  *     documentation and/or other materials provided with the distribution.
     15  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
     16  *     its contributors may be used to endorse or promote products derived
     17  *     from this software without specific prior written permission.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
     20  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
     21  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
     22  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
     23  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
     24  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     25  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
     26  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     29  */
     30 
     31 /*
     32  * There are numerous academic and practical works on how to implement pthread_cond_wait/pthread_cond_signal/pthread_cond_broadcast
     33  * 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'
     34  * of modern attempts. There are several more or less proven implementations, one in Boost C++ library (http://www.boost.org) and another
     35  * in pthreads-win32 (http://sourceware.org/pthreads-win32/).
     36  *
     37  * The number of articles and discussions is the evidence of significant difficulties in implementing these primitives correctly.
     38  * The brief search of revisions, ChangeLog entries, discussions in comp.programming.threads and other places clearly documents
     39  * numerous pitfalls and performance problems the authors had to overcome to arrive to the suitable implementations.
     40  * Optimally, WebKit would use one of those supported/tested libraries directly. To roll out our own implementation is impractical,
     41  * if even for the lack of sufficient testing. However, a faithful reproduction of the code from one of the popular supported
     42  * libraries seems to be a good compromise.
     43  *
     44  * 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)
     45  * 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).
     46  * Current Boost uses yet another (although seemingly equivalent) algorithm which came from their 'thread rewrite' effort.
     47  *
     48  * This file includes timedWait/signal/broadcast implementations translated to WebKit coding style from the latest algorithm by
     49  * 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
     50  * It replaces the implementation of their previous algorithm, also documented in the same source above.
     51  * The naming and comments are left very close to original to enable easy cross-check.
     52  *
     53  * The corresponding Pthreads-win32 License is included below, and CONTRIBUTORS file which it refers to is added to
     54  * source directory (as CONTRIBUTORS.pthreads-win32).
     55  */
     56 
     57 /*
     58  *      Pthreads-win32 - POSIX Threads Library for Win32
     59  *      Copyright(C) 1998 John E. Bossom
     60  *      Copyright(C) 1999,2005 Pthreads-win32 contributors
     61  *
     62  *      Contact Email: rpj (at) callisto.canberra.edu.au
     63  *
     64  *      The current list of contributors is contained
     65  *      in the file CONTRIBUTORS included with the source
     66  *      code distribution. The list can also be seen at the
     67  *      following World Wide Web location:
     68  *      http://sources.redhat.com/pthreads-win32/contributors.html
     69  *
     70  *      This library is free software; you can redistribute it and/or
     71  *      modify it under the terms of the GNU Lesser General Public
     72  *      License as published by the Free Software Foundation; either
     73  *      version 2 of the License, or (at your option) any later version.
     74  *
     75  *      This library is distributed in the hope that it will be useful,
     76  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
     77  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     78  *      Lesser General Public License for more details.
     79  *
     80  *      You should have received a copy of the GNU Lesser General Public
     81  *      License along with this library in the file COPYING.LIB;
     82  *      if not, write to the Free Software Foundation, Inc.,
     83  *      59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
     84  */
     85 
     86 #include "config.h"
     87 #include "Threading.h"
     88 
     89 #if OS(WIN)
     90 
     91 #include "wtf/CurrentTime.h"
     92 #include "wtf/DateMath.h"
     93 #include "wtf/HashMap.h"
     94 #include "wtf/MainThread.h"
     95 #include "wtf/MathExtras.h"
     96 #include "wtf/OwnPtr.h"
     97 #include "wtf/PassOwnPtr.h"
     98 #include "wtf/ThreadFunctionInvocation.h"
     99 #include "wtf/ThreadSpecific.h"
    100 #include "wtf/ThreadingPrimitives.h"
    101 #include "wtf/WTFThreadData.h"
    102 #include "wtf/dtoa.h"
    103 #include "wtf/dtoa/cached-powers.h"
    104 #include <errno.h>
    105 #include <process.h>
    106 #include <windows.h>
    107 
    108 namespace WTF {
    109 
    110 // MS_VC_EXCEPTION, THREADNAME_INFO, and setThreadNameInternal all come from <http://msdn.microsoft.com/en-us/library/xcb2z8hs.aspx>.
    111 static const DWORD MS_VC_EXCEPTION = 0x406D1388;
    112 
    113 #pragma pack(push, 8)
    114 typedef struct tagTHREADNAME_INFO {
    115     DWORD dwType; // must be 0x1000
    116     LPCSTR szName; // pointer to name (in user addr space)
    117     DWORD dwThreadID; // thread ID (-1=caller thread)
    118     DWORD dwFlags; // reserved for future use, must be zero
    119 } THREADNAME_INFO;
    120 #pragma pack(pop)
    121 
    122 static Mutex* atomicallyInitializedStaticMutex;
    123 
    124 void lockAtomicallyInitializedStaticMutex()
    125 {
    126     ASSERT(atomicallyInitializedStaticMutex);
    127     atomicallyInitializedStaticMutex->lock();
    128 }
    129 
    130 void unlockAtomicallyInitializedStaticMutex()
    131 {
    132     atomicallyInitializedStaticMutex->unlock();
    133 }
    134 
    135 void initializeThreading()
    136 {
    137     // This should only be called once.
    138     ASSERT(!atomicallyInitializedStaticMutex);
    139 
    140     // StringImpl::empty() does not construct its static string in a threadsafe fashion,
    141     // so ensure it has been initialized from here.
    142     StringImpl::empty();
    143     StringImpl::empty16Bit();
    144     atomicallyInitializedStaticMutex = new Mutex;
    145     wtfThreadData();
    146     s_dtoaP5Mutex = new Mutex;
    147     initializeDates();
    148     // Force initialization of static DoubleToStringConverter converter variable
    149     // inside EcmaScriptConverter function while we are in single thread mode.
    150     double_conversion::DoubleToStringConverter::EcmaScriptConverter();
    151 }
    152 
    153 ThreadIdentifier currentThread()
    154 {
    155     return static_cast<ThreadIdentifier>(GetCurrentThreadId());
    156 }
    157 
    158 MutexBase::MutexBase(bool recursive)
    159 {
    160     m_mutex.m_recursionCount = 0;
    161     InitializeCriticalSection(&m_mutex.m_internalMutex);
    162 }
    163 
    164 MutexBase::~MutexBase()
    165 {
    166     DeleteCriticalSection(&m_mutex.m_internalMutex);
    167 }
    168 
    169 void MutexBase::lock()
    170 {
    171     EnterCriticalSection(&m_mutex.m_internalMutex);
    172     ++m_mutex.m_recursionCount;
    173 }
    174 
    175 void MutexBase::unlock()
    176 {
    177     ASSERT(m_mutex.m_recursionCount);
    178     --m_mutex.m_recursionCount;
    179     LeaveCriticalSection(&m_mutex.m_internalMutex);
    180 }
    181 
    182 bool Mutex::tryLock()
    183 {
    184     // This method is modeled after the behavior of pthread_mutex_trylock,
    185     // which will return an error if the lock is already owned by the
    186     // current thread.  Since the primitive Win32 'TryEnterCriticalSection'
    187     // treats this as a successful case, it changes the behavior of several
    188     // tests in WebKit that check to see if the current thread already
    189     // owned this mutex (see e.g., IconDatabase::getOrCreateIconRecord)
    190     DWORD result = TryEnterCriticalSection(&m_mutex.m_internalMutex);
    191 
    192     if (result != 0) {       // We got the lock
    193         // If this thread already had the lock, we must unlock and return
    194         // false since this is a non-recursive mutex. This is to mimic the
    195         // behavior of POSIX's pthread_mutex_trylock. We don't do this
    196         // check in the lock method (presumably due to performance?). This
    197         // means lock() will succeed even if the current thread has already
    198         // entered the critical section.
    199         if (m_mutex.m_recursionCount > 0) {
    200             LeaveCriticalSection(&m_mutex.m_internalMutex);
    201             return false;
    202         }
    203         ++m_mutex.m_recursionCount;
    204         return true;
    205     }
    206 
    207     return false;
    208 }
    209 
    210 bool RecursiveMutex::tryLock()
    211 {
    212     // CRITICAL_SECTION is recursive/reentrant so TryEnterCriticalSection will
    213     // succeed if the current thread is already in the critical section.
    214     DWORD result = TryEnterCriticalSection(&m_mutex.m_internalMutex);
    215     if (result == 0) { // We didn't get the lock.
    216         return false;
    217     }
    218     ++m_mutex.m_recursionCount;
    219     return true;
    220 }
    221 
    222 bool PlatformCondition::timedWait(PlatformMutex& mutex, DWORD durationMilliseconds)
    223 {
    224     // Enter the wait state.
    225     DWORD res = WaitForSingleObject(m_blockLock, INFINITE);
    226     ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
    227     ++m_waitersBlocked;
    228     res = ReleaseSemaphore(m_blockLock, 1, 0);
    229     ASSERT_UNUSED(res, res);
    230 
    231     --mutex.m_recursionCount;
    232     LeaveCriticalSection(&mutex.m_internalMutex);
    233 
    234     // Main wait - use timeout.
    235     bool timedOut = (WaitForSingleObject(m_blockQueue, durationMilliseconds) == WAIT_TIMEOUT);
    236 
    237     res = WaitForSingleObject(m_unblockLock, INFINITE);
    238     ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
    239 
    240     int signalsLeft = m_waitersToUnblock;
    241 
    242     if (m_waitersToUnblock)
    243         --m_waitersToUnblock;
    244     else if (++m_waitersGone == (INT_MAX / 2)) { // timeout/canceled or spurious semaphore
    245         // timeout or spurious wakeup occured, normalize the m_waitersGone count
    246         // this may occur if many calls to wait with a timeout are made and
    247         // no call to notify_* is made
    248         res = WaitForSingleObject(m_blockLock, INFINITE);
    249         ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
    250         m_waitersBlocked -= m_waitersGone;
    251         res = ReleaseSemaphore(m_blockLock, 1, 0);
    252         ASSERT_UNUSED(res, res);
    253         m_waitersGone = 0;
    254     }
    255 
    256     res = ReleaseMutex(m_unblockLock);
    257     ASSERT_UNUSED(res, res);
    258 
    259     if (signalsLeft == 1) {
    260         res = ReleaseSemaphore(m_blockLock, 1, 0); // Open the gate.
    261         ASSERT_UNUSED(res, res);
    262     }
    263 
    264     EnterCriticalSection (&mutex.m_internalMutex);
    265     ++mutex.m_recursionCount;
    266 
    267     return !timedOut;
    268 }
    269 
    270 void PlatformCondition::signal(bool unblockAll)
    271 {
    272     unsigned signalsToIssue = 0;
    273 
    274     DWORD res = WaitForSingleObject(m_unblockLock, INFINITE);
    275     ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
    276 
    277     if (m_waitersToUnblock) { // the gate is already closed
    278         if (!m_waitersBlocked) { // no-op
    279             res = ReleaseMutex(m_unblockLock);
    280             ASSERT_UNUSED(res, res);
    281             return;
    282         }
    283 
    284         if (unblockAll) {
    285             signalsToIssue = m_waitersBlocked;
    286             m_waitersToUnblock += m_waitersBlocked;
    287             m_waitersBlocked = 0;
    288         } else {
    289             signalsToIssue = 1;
    290             ++m_waitersToUnblock;
    291             --m_waitersBlocked;
    292         }
    293     } else if (m_waitersBlocked > m_waitersGone) {
    294         res = WaitForSingleObject(m_blockLock, INFINITE); // Close the gate.
    295         ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
    296         if (m_waitersGone != 0) {
    297             m_waitersBlocked -= m_waitersGone;
    298             m_waitersGone = 0;
    299         }
    300         if (unblockAll) {
    301             signalsToIssue = m_waitersBlocked;
    302             m_waitersToUnblock = m_waitersBlocked;
    303             m_waitersBlocked = 0;
    304         } else {
    305             signalsToIssue = 1;
    306             m_waitersToUnblock = 1;
    307             --m_waitersBlocked;
    308         }
    309     } else { // No-op.
    310         res = ReleaseMutex(m_unblockLock);
    311         ASSERT_UNUSED(res, res);
    312         return;
    313     }
    314 
    315     res = ReleaseMutex(m_unblockLock);
    316     ASSERT_UNUSED(res, res);
    317 
    318     if (signalsToIssue) {
    319         res = ReleaseSemaphore(m_blockQueue, signalsToIssue, 0);
    320         ASSERT_UNUSED(res, res);
    321     }
    322 }
    323 
    324 static const long MaxSemaphoreCount = static_cast<long>(~0UL >> 1);
    325 
    326 ThreadCondition::ThreadCondition()
    327 {
    328     m_condition.m_waitersGone = 0;
    329     m_condition.m_waitersBlocked = 0;
    330     m_condition.m_waitersToUnblock = 0;
    331     m_condition.m_blockLock = CreateSemaphore(0, 1, 1, 0);
    332     m_condition.m_blockQueue = CreateSemaphore(0, 0, MaxSemaphoreCount, 0);
    333     m_condition.m_unblockLock = CreateMutex(0, 0, 0);
    334 
    335     if (!m_condition.m_blockLock || !m_condition.m_blockQueue || !m_condition.m_unblockLock) {
    336         if (m_condition.m_blockLock)
    337             CloseHandle(m_condition.m_blockLock);
    338         if (m_condition.m_blockQueue)
    339             CloseHandle(m_condition.m_blockQueue);
    340         if (m_condition.m_unblockLock)
    341             CloseHandle(m_condition.m_unblockLock);
    342     }
    343 }
    344 
    345 ThreadCondition::~ThreadCondition()
    346 {
    347     CloseHandle(m_condition.m_blockLock);
    348     CloseHandle(m_condition.m_blockQueue);
    349     CloseHandle(m_condition.m_unblockLock);
    350 }
    351 
    352 void ThreadCondition::wait(MutexBase& mutex)
    353 {
    354     m_condition.timedWait(mutex.impl(), INFINITE);
    355 }
    356 
    357 bool ThreadCondition::timedWait(MutexBase& mutex, double absoluteTime)
    358 {
    359     DWORD interval = absoluteTimeToWaitTimeoutInterval(absoluteTime);
    360 
    361     if (!interval) {
    362         // Consider the wait to have timed out, even if our condition has already been signaled, to
    363         // match the pthreads implementation.
    364         return false;
    365     }
    366 
    367     return m_condition.timedWait(mutex.impl(), interval);
    368 }
    369 
    370 void ThreadCondition::signal()
    371 {
    372     m_condition.signal(false); // Unblock only 1 thread.
    373 }
    374 
    375 void ThreadCondition::broadcast()
    376 {
    377     m_condition.signal(true); // Unblock all threads.
    378 }
    379 
    380 DWORD absoluteTimeToWaitTimeoutInterval(double absoluteTime)
    381 {
    382     double currentTime = WTF::currentTime();
    383 
    384     // Time is in the past - return immediately.
    385     if (absoluteTime < currentTime)
    386         return 0;
    387 
    388     // Time is too far in the future (and would overflow unsigned long) - wait forever.
    389     if (absoluteTime - currentTime > static_cast<double>(INT_MAX) / 1000.0)
    390         return INFINITE;
    391 
    392     return static_cast<DWORD>((absoluteTime - currentTime) * 1000.0);
    393 }
    394 
    395 } // namespace WTF
    396 
    397 #endif // OS(WIN)
    398