Source/WTF/wtf/ThreadingWin.cpp

   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@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 #include "DateMath.h"
  89 #include "dtoa.h"
  90 #include "dtoa/cached-powers.h"
  91
  92 #include "MainThread.h"
  93 #include "ThreadFunctionInvocation.h"
  94 #include <windows.h>
  95 #include <wtf/CurrentTime.h>
  96 #include <wtf/HashMap.h>
  97 #include <wtf/MathExtras.h>
  98 #include <wtf/OwnPtr.h>
  99 #include <wtf/PassOwnPtr.h>
 100 #include <wtf/RandomNumberSeed.h>
 101 #include <wtf/WTFThreadData.h>
 102
 103 #if !USE(PTHREADS) && OS(WINDOWS)
 104 #include "ThreadSpecific.h"
 105 #endif
 106
 107 #if !OS(WINCE)
 108 #include <process.h>
 109 #endif
 110
 111 #if HAVE(ERRNO_H)
 112 #include <errno.h>
 113 #endif
 114
 115 namespace WTF {
 116
 117 // MS_VC_EXCEPTION, THREADNAME_INFO, and setThreadNameInternal all come from <http://msdn.microsoft.com/en-us/library/xcb2z8hs.aspx>.
 118 static const DWORD MS_VC_EXCEPTION = 0x406D1388;
 119
 120 #pragma pack(push, 8)
 121 typedef struct tagTHREADNAME_INFO {
 122     DWORD dwType; // must be 0x1000
 123     LPCSTR szName; // pointer to name (in user addr space)
 124     DWORD dwThreadID; // thread ID (-1=caller thread)
 125     DWORD dwFlags; // reserved for future use, must be zero
 126 } THREADNAME_INFO;
 127 #pragma pack(pop)
 128
 129 void initializeCurrentThreadInternal(const char* szThreadName)
 130 {
 131 #if COMPILER(MINGW)
 132     // FIXME: Implement thread name setting with MingW.
 133     UNUSED_PARAM(szThreadName);
 134 #else
 135     THREADNAME_INFO info;
 136     info.dwType = 0x1000;
 137     info.szName = szThreadName;
 138     info.dwThreadID = GetCurrentThreadId();
 139     info.dwFlags = 0;
 140
 141     __try {
 142         RaiseException(MS_VC_EXCEPTION, 0, sizeof(info)/sizeof(ULONG_PTR), reinterpret_cast<ULONG_PTR*>(&info));
 143     } __except (EXCEPTION_CONTINUE_EXECUTION) {
 144     }
 145 #endif
 146 }
 147
 148 static Mutex* atomicallyInitializedStaticMutex;
 149
 150 void lockAtomicallyInitializedStaticMutex()
 151 {
 152     ASSERT(atomicallyInitializedStaticMutex);
 153     atomicallyInitializedStaticMutex->lock();
 154 }
 155
 156 void unlockAtomicallyInitializedStaticMutex()
 157 {
 158     atomicallyInitializedStaticMutex->unlock();
 159 }
 160
 161 static Mutex& threadMapMutex()
 162 {
 163     static Mutex mutex;
 164     return mutex;
 165 }
 166
 167 void initializeThreading()
 168 {
 169     if (atomicallyInitializedStaticMutex)
 170         return;
 171
 172     WTF::double_conversion::initialize();
 173     // StringImpl::empty() does not construct its static string in a threadsafe fashion,
 174     // so ensure it has been initialized from here.
 175     StringImpl::empty();
 176     atomicallyInitializedStaticMutex = new Mutex;
 177     threadMapMutex();
 178     initializeRandomNumberGenerator();
 179     wtfThreadData();
 180     s_dtoaP5Mutex = new Mutex;
 181     initializeDates();
 182 }
 183
 184 static HashMap<DWORD, HANDLE>& threadMap()
 185 {
 186     static HashMap<DWORD, HANDLE> map;
 187     return map;
 188 }
 189
 190 static void storeThreadHandleByIdentifier(DWORD threadID, HANDLE threadHandle)
 191 {
 192     MutexLocker locker(threadMapMutex());
 193     ASSERT(!threadMap().contains(threadID));
 194     threadMap().add(threadID, threadHandle);
 195 }
 196
 197 static HANDLE threadHandleForIdentifier(ThreadIdentifier id)
 198 {
 199     MutexLocker locker(threadMapMutex());
 200     return threadMap().get(id);
 201 }
 202
 203 static void clearThreadHandleForIdentifier(ThreadIdentifier id)
 204 {
 205     MutexLocker locker(threadMapMutex());
 206     ASSERT(threadMap().contains(id));
 207     threadMap().remove(id);
 208 }
 209
 210 static unsigned __stdcall wtfThreadEntryPoint(void* param)
 211 {
 212     OwnPtr<ThreadFunctionInvocation> invocation = adoptPtr(static_cast<ThreadFunctionInvocation*>(param));
 213     invocation->function(invocation->data);
 214
 215 #if !USE(PTHREADS) && OS(WINDOWS)
 216     // Do the TLS cleanup.
 217     ThreadSpecificThreadExit();
 218 #endif
 219
 220     return 0;
 221 }
 222
 223 ThreadIdentifier createThreadInternal(ThreadFunction entryPoint, void* data, const char* threadName)
 224 {
 225     unsigned threadIdentifier = 0;
 226     ThreadIdentifier threadID = 0;
 227     OwnPtr<ThreadFunctionInvocation> invocation = adoptPtr(new ThreadFunctionInvocation(entryPoint, data));
 228 #if OS(WINCE)
 229     // This is safe on WINCE, since CRT is in the core and innately multithreaded.
 230     // On desktop Windows, need to use _beginthreadex (not available on WinCE) if using any CRT functions
 231     HANDLE threadHandle = CreateThread(0, 0, (LPTHREAD_START_ROUTINE)wtfThreadEntryPoint, invocation.get(), 0, (LPDWORD)&threadIdentifier);
 232 #else
 233     HANDLE threadHandle = reinterpret_cast<HANDLE>(_beginthreadex(0, 0, wtfThreadEntryPoint, invocation.get(), 0, &threadIdentifier));
 234 #endif
 235     if (!threadHandle) {
 236 #if OS(WINCE)
 237         LOG_ERROR("Failed to create thread at entry point %p with data %p: %ld", entryPoint, data, ::GetLastError());
 238 #elif !HAVE(ERRNO_H)
 239         LOG_ERROR("Failed to create thread at entry point %p with data %p.", entryPoint, data);
 240 #else
 241         LOG_ERROR("Failed to create thread at entry point %p with data %p: %ld", entryPoint, data, errno);
 242 #endif
 243         return 0;
 244     }
 245
 246     // The thread will take ownership of invocation.
 247     ThreadFunctionInvocation* leakedInvocation = invocation.leakPtr();
 248     UNUSED_PARAM(leakedInvocation);
 249
 250     threadID = static_cast<ThreadIdentifier>(threadIdentifier);
 251     storeThreadHandleByIdentifier(threadIdentifier, threadHandle);
 252
 253     return threadID;
 254 }
 255
 256 int waitForThreadCompletion(ThreadIdentifier threadID)
 257 {
 258     ASSERT(threadID);
 259
 260     HANDLE threadHandle = threadHandleForIdentifier(threadID);
 261     if (!threadHandle)
 262         LOG_ERROR("ThreadIdentifier %u did not correspond to an active thread when trying to quit", threadID);
 263
 264     DWORD joinResult = WaitForSingleObject(threadHandle, INFINITE);
 265     if (joinResult == WAIT_FAILED)
 266         LOG_ERROR("ThreadIdentifier %u was found to be deadlocked trying to quit", threadID);
 267
 268     CloseHandle(threadHandle);
 269     clearThreadHandleForIdentifier(threadID);
 270
 271     return joinResult;
 272 }
 273
 274 void detachThread(ThreadIdentifier threadID)
 275 {
 276     ASSERT(threadID);
 277
 278     HANDLE threadHandle = threadHandleForIdentifier(threadID);
 279     if (threadHandle)
 280         CloseHandle(threadHandle);
 281     clearThreadHandleForIdentifier(threadID);
 282 }
 283
 284 void yield()
 285 {
 286     ::Sleep(1);
 287 }
 288
 289 ThreadIdentifier currentThread()
 290 {
 291     return static_cast<ThreadIdentifier>(GetCurrentThreadId());
 292 }
 293
 294 Mutex::Mutex()
 295 {
 296     m_mutex.m_recursionCount = 0;
 297     InitializeCriticalSection(&m_mutex.m_internalMutex);
 298 }
 299
 300 Mutex::~Mutex()
 301 {
 302     DeleteCriticalSection(&m_mutex.m_internalMutex);
 303 }
 304
 305 void Mutex::lock()
 306 {
 307     EnterCriticalSection(&m_mutex.m_internalMutex);
 308     ++m_mutex.m_recursionCount;
 309 }
 310
 311 bool Mutex::tryLock()
 312 {
 313     // This method is modeled after the behavior of pthread_mutex_trylock,
 314     // which will return an error if the lock is already owned by the
 315     // current thread.  Since the primitive Win32 'TryEnterCriticalSection'
 316     // treats this as a successful case, it changes the behavior of several
 317     // tests in WebKit that check to see if the current thread already
 318     // owned this mutex (see e.g., IconDatabase::getOrCreateIconRecord)
 319     DWORD result = TryEnterCriticalSection(&m_mutex.m_internalMutex);
 320
 321     if (result != 0) {       // We got the lock
 322         // If this thread already had the lock, we must unlock and
 323         // return false so that we mimic the behavior of POSIX's
 324         // pthread_mutex_trylock:
 325         if (m_mutex.m_recursionCount > 0) {
 326             LeaveCriticalSection(&m_mutex.m_internalMutex);
 327             return false;
 328         }
 329
 330         ++m_mutex.m_recursionCount;
 331         return true;
 332     }
 333
 334     return false;
 335 }
 336
 337 void Mutex::unlock()
 338 {
 339     ASSERT(m_mutex.m_recursionCount);
 340     --m_mutex.m_recursionCount;
 341     LeaveCriticalSection(&m_mutex.m_internalMutex);
 342 }
 343
 344 bool PlatformCondition::timedWait(PlatformMutex& mutex, DWORD durationMilliseconds)
 345 {
 346     // Enter the wait state.
 347     DWORD res = WaitForSingleObject(m_blockLock, INFINITE);
 348     ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
 349     ++m_waitersBlocked;
 350     res = ReleaseSemaphore(m_blockLock, 1, 0);
 351     ASSERT_UNUSED(res, res);
 352
 353     --mutex.m_recursionCount;
 354     LeaveCriticalSection(&mutex.m_internalMutex);
 355
 356     // Main wait - use timeout.
 357     bool timedOut = (WaitForSingleObject(m_blockQueue, durationMilliseconds) == WAIT_TIMEOUT);
 358
 359     res = WaitForSingleObject(m_unblockLock, INFINITE);
 360     ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
 361
 362     int signalsLeft = m_waitersToUnblock;
 363
 364     if (m_waitersToUnblock)
 365         --m_waitersToUnblock;
 366     else if (++m_waitersGone == (INT_MAX / 2)) { // timeout/canceled or spurious semaphore
 367         // timeout or spurious wakeup occured, normalize the m_waitersGone count
 368         // this may occur if many calls to wait with a timeout are made and
 369         // no call to notify_* is made
 370         res = WaitForSingleObject(m_blockLock, INFINITE);
 371         ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
 372         m_waitersBlocked -= m_waitersGone;
 373         res = ReleaseSemaphore(m_blockLock, 1, 0);
 374         ASSERT_UNUSED(res, res);
 375         m_waitersGone = 0;
 376     }
 377
 378     res = ReleaseMutex(m_unblockLock);
 379     ASSERT_UNUSED(res, res);
 380
 381     if (signalsLeft == 1) {
 382         res = ReleaseSemaphore(m_blockLock, 1, 0); // Open the gate.
 383         ASSERT_UNUSED(res, res);
 384     }
 385
 386     EnterCriticalSection (&mutex.m_internalMutex);
 387     ++mutex.m_recursionCount;
 388
 389     return !timedOut;
 390 }
 391
 392 void PlatformCondition::signal(bool unblockAll)
 393 {
 394     unsigned signalsToIssue = 0;
 395
 396     DWORD res = WaitForSingleObject(m_unblockLock, INFINITE);
 397     ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
 398
 399     if (m_waitersToUnblock) { // the gate is already closed
 400         if (!m_waitersBlocked) { // no-op
 401             res = ReleaseMutex(m_unblockLock);
 402             ASSERT_UNUSED(res, res);
 403             return;
 404         }
 405
 406         if (unblockAll) {
 407             signalsToIssue = m_waitersBlocked;
 408             m_waitersToUnblock += m_waitersBlocked;
 409             m_waitersBlocked = 0;
 410         } else {
 411             signalsToIssue = 1;
 412             ++m_waitersToUnblock;
 413             --m_waitersBlocked;
 414         }
 415     } else if (m_waitersBlocked > m_waitersGone) {
 416         res = WaitForSingleObject(m_blockLock, INFINITE); // Close the gate.
 417         ASSERT_UNUSED(res, res == WAIT_OBJECT_0);
 418         if (m_waitersGone != 0) {
 419             m_waitersBlocked -= m_waitersGone;
 420             m_waitersGone = 0;
 421         }
 422         if (unblockAll) {
 423             signalsToIssue = m_waitersBlocked;
 424             m_waitersToUnblock = m_waitersBlocked;
 425             m_waitersBlocked = 0;
 426         } else {
 427             signalsToIssue = 1;
 428             m_waitersToUnblock = 1;
 429             --m_waitersBlocked;
 430         }
 431     } else { // No-op.
 432         res = ReleaseMutex(m_unblockLock);
 433         ASSERT_UNUSED(res, res);
 434         return;
 435     }
 436
 437     res = ReleaseMutex(m_unblockLock);
 438     ASSERT_UNUSED(res, res);
 439
 440     if (signalsToIssue) {
 441         res = ReleaseSemaphore(m_blockQueue, signalsToIssue, 0);
 442         ASSERT_UNUSED(res, res);
 443     }
 444 }
 445
 446 static const long MaxSemaphoreCount = static_cast<long>(~0UL >> 1);
 447
 448 ThreadCondition::ThreadCondition()
 449 {
 450     m_condition.m_waitersGone = 0;
 451     m_condition.m_waitersBlocked = 0;
 452     m_condition.m_waitersToUnblock = 0;
 453     m_condition.m_blockLock = CreateSemaphore(0, 1, 1, 0);
 454     m_condition.m_blockQueue = CreateSemaphore(0, 0, MaxSemaphoreCount, 0);
 455     m_condition.m_unblockLock = CreateMutex(0, 0, 0);
 456
 457     if (!m_condition.m_blockLock || !m_condition.m_blockQueue || !m_condition.m_unblockLock) {
 458         if (m_condition.m_blockLock)
 459             CloseHandle(m_condition.m_blockLock);
 460         if (m_condition.m_blockQueue)
 461             CloseHandle(m_condition.m_blockQueue);
 462         if (m_condition.m_unblockLock)
 463             CloseHandle(m_condition.m_unblockLock);
 464     }
 465 }
 466
 467 ThreadCondition::~ThreadCondition()
 468 {
 469     CloseHandle(m_condition.m_blockLock);
 470     CloseHandle(m_condition.m_blockQueue);
 471     CloseHandle(m_condition.m_unblockLock);
 472 }
 473
 474 void ThreadCondition::wait(Mutex& mutex)
 475 {
 476     m_condition.timedWait(mutex.impl(), INFINITE);
 477 }
 478
 479 bool ThreadCondition::timedWait(Mutex& mutex, double absoluteTime)
 480 {
 481     DWORD interval = absoluteTimeToWaitTimeoutInterval(absoluteTime);
 482
 483     if (!interval) {
 484         // Consider the wait to have timed out, even if our condition has already been signaled, to
 485         // match the pthreads implementation.
 486         return false;
 487     }
 488
 489     return m_condition.timedWait(mutex.impl(), interval);
 490 }
 491
 492 void ThreadCondition::signal()
 493 {
 494     m_condition.signal(false); // Unblock only 1 thread.
 495 }
 496
 497 void ThreadCondition::broadcast()
 498 {
 499     m_condition.signal(true); // Unblock all threads.
 500 }
 501
 502 DWORD absoluteTimeToWaitTimeoutInterval(double absoluteTime)
 503 {
 504     double currentTime = WTF::currentTime();
 505
 506     // Time is in the past - return immediately.
 507     if (absoluteTime < currentTime)
 508         return 0;
 509
 510     // Time is too far in the future (and would overflow unsigned long) - wait forever.
 511     if (absoluteTime - currentTime > static_cast<double>(INT_MAX) / 1000.0)
 512         return INFINITE;
 513
 514     return static_cast<DWORD>((absoluteTime - currentTime) * 1000.0);
 515 }
 516
 517 } // namespace WTF